/* -*-c-*-
*
- * $Id: mpx.h,v 1.13 2002/10/06 22:52:50 mdw Exp $
+ * $Id: mpx.h,v 1.17 2004/03/27 00:04:46 mdw Exp $
*
* Low level multiprecision arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx.h,v $
+ * Revision 1.17 2004/03/27 00:04:46 mdw
+ * Implement efficient reduction for pleasant-looking primes.
+ *
+ * Revision 1.16 2003/05/16 09:09:24 mdw
+ * Fix @mp_lsl2c@. Turns out to be surprisingly tricky.
+ *
+ * Revision 1.15 2002/10/19 17:56:50 mdw
+ * Fix bit operations. Test them (a bit) better.
+ *
+ * Revision 1.14 2002/10/09 00:36:03 mdw
+ * Fix bounds on workspace for Karatsuba operations.
+ *
* Revision 1.13 2002/10/06 22:52:50 mdw
* Pile of changes for supporting two's complement properly.
*
memset(_v, 0, MPWS(_vl - _v)); \
} while (0)
+/* --- @MPX_ONE@ --- *
+ *
+ * Arguments: @v, vl@ = base and limit of vector to clear
+ *
+ * Use: Fills the area between the two vector pointers with ones.
+ */
+
+#define MPX_ONE(v, vl) do { \
+ mpw * _v = (v); \
+ const mpw *_vl = (vl); \
+ while (_v < _vl) \
+ *_v++ = MPW_MAX; \
+} while (0)
+
/*----- Loading and storing -----------------------------------------------*/
/* --- @mpx_storel@ --- *
const mpw */*av*/, const mpw */*avl*/,
size_t /*n*/);
+/* --- @mpx_lslc@ --- *
+ *
+ * Arguments: @mpw *dv, *dvl@ = destination vector base and limit
+ * @const mpw *av, *avl@ = source vector base and limit
+ * @size_t n@ = number of bit positions to shift by
+ *
+ * Returns: ---
+ *
+ * Use: Performs a logical shift left operation on an integer, only
+ * it fills in the bits with ones instead of zeroes.
+ */
+
+extern void mpx_lslc(mpw */*dv*/, mpw */*dvl*/,
+ const mpw */*av*/, const mpw */*avl*/,
+ size_t /*n*/);
+
/* --- @mpx_lsr@ --- *
*
* Arguments: @mpw *dv, *dvl@ = destination vector base and limit
/*----- Bitwise operations ------------------------------------------------*/
-/* --- How to implement them --- *
- *
- * x: 0011
- * y: 0101
- */
-
-#define MPX_B0000(x, y) (0u)
-#define MPX_B0001(x, y) ((x) & (y))
-#define MPX_B0010(x, y) ((x) & ~(y))
-#define MPX_B0011(x, y) (x)
-#define MPX_B0100(x, y) (~(x) & ~(y))
-#define MPX_B0101(x, y) (y)
-#define MPX_B0110(x, y) ((x) ^ (y))
-#define MPX_B0111(x, y) ((x) | (y))
-#define MPX_B1000(x, y) (~((x) | (y)))
-#define MPX_B1001(x, y) (~((x) ^ (y)))
-#define MPX_B1010(x, y) (~(y))
-#define MPX_B1011(x, y) ((x) | ~(y))
-#define MPX_B1100(x, y) (~(x))
-#define MPX_B1101(x, y) (~(x) | (y))
-#define MPX_B1110(x, y) (~((x) & (y)))
-#define MPX_B1111(x, y) (~0u)
-
/* --- @mpx_bitop@ --- *
*
* Arguments: @mpw *dv, *dvl@ = destination vector
extern void mpx_uaddn(mpw */*dv*/, mpw */*dvl*/, mpw /*n*/);
+/* --- @mpx_uaddnlsl@ --- *
+ *
+ * Arguments: @mpw *dv, *dvl@ = destination and first argument vector
+ * @mpw a@ = second argument
+ * @unsigned o@ = offset in bits
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d + 2^o a$%. If the result overflows then
+ * high-order bits are discarded, as usual. We must have
+ * @0 < o < MPW_BITS@.
+ */
+
+extern void mpx_uaddnlsl(mpw */*dv*/, mpw */*dvl*/,
+ mpw /*a*/, unsigned /*o*/);
+
/* --- @mpx_usub@ --- *
*
* Arguments: @mpw *dv, *dvl@ = destination vector base and limit
extern void mpx_usubn(mpw */*dv*/, mpw */*dvl*/, mpw /*n*/);
+/* --- @mpx_usubnlsl@ --- *
+ *
+ * Arguments: @mpw *dv, *dvl@ = destination and first argument vector
+ * @mpw a@ = second argument
+ * @unsigned o@ = offset in bits
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d - 2^o a$%. If the result overflows then
+ * high-order bits are discarded, as usual, so you get two's
+ * complement. Which might be what you wanted... We must have
+ * @0 < o < MPW_BITS@.
+ */
+
+extern void mpx_usubnlsl(mpw */*dv*/, mpw */*dvl*/,
+ mpw /*a*/, unsigned /*o*/);
+
/* --- @mpx_umul@ --- *
*
* Arguments: @mpw *dv, *dvl@ = destination vector base and limit
*
* This is the limiting length for using Karatsuba algorithms. It's best to
* use the simpler classical multiplication method on numbers smaller than
- * this.
+ * this. It is unsafe to make this constant less than four (i.e., the
+ * algorithms will fail).
*/
#define MPK_THRESH 16
-/* --- @MPK_SLOP@ --- *
- *
- * The extra number of words required as scratch space by the Karatsuba
- * routines. This is a (generous) guess, since the actual amount of space
- * required is proportional to the recursion depth.
- */
-
-#define MPK_SLOP 64
-
/* --- @mpx_kmul@ --- *
*
* Arguments: @mpw *dv, *dvl@ = pointer to destination buffer
* multiplication (e.g., @mpx_umul@) on large numbers, although
* more expensive on small ones.
*
- * The destination and scratch buffers must be twice as large as
- * the larger argument. The scratch space must be twice as
- * large as the larger argument, plus the magic number
- * @MPK_SLOP@.
+ * The destination must be three times as large as the larger
+ * argument. The scratch space must be five times as large as
+ * the larger argument.
*/
extern void mpx_kmul(mpw */*dv*/, mpw */*dvl*/,
* large numbers, although more expensive on small ones, and
* rather simpler than full-blown Karatsuba multiplication.
*
- * The destination must be twice as large as the argument. The
- * scratch space must be twice as large as the argument, plus
- * the magic number @MPK_SLOP@.
+ * The destination must be three times as large as the larger
+ * argument. The scratch space must be five times as large as
+ * the larger argument.
*/
extern void mpx_ksqr(mpw */*dv*/, mpw */*dvl*/,