Merge branch 'fixes'

* fixes:
  mpint: Fix misbehaviour on larger-than-mpw integer types.
  Fix various assumptions about mpw sizes.
  utils/mpreducetests.py: Tool to generate unpleasant mpreduce tests.
  mpreduce: Don't crash if we've accumulated no instructions.
  mpreduce: Don't stop bit scanner too early.
  mpreduce: Debug decomposition corrupts initial state for code generator.
  factorial: Fix usage message to fit in with conventions.
  cleanup: Various aesthetic fiddlings of little consequence.

diff --git a/configure.in b/configure.in
index f35a8df..aef91e0 100644 (file)
--- a/configure.in
+++ b/configure.in
@@ -84,6 +84,22 @@ dnl --- Support for the passphrase pixie ---
 mdw_CHECK_MANYLIBS(socket, socket)
 AC_CHECK_FUNCS(mlock)
 
+dnl --- Debugging things ---
+
+AC_ARG_ENABLE([mpw], 
+              [AS_HELP_STRING([--enable-mpw], 
+                              [force small-width mp digits])],
+              [case "$enableval" in
+                 y*|t*|short)
+                   AC_DEFINE([FORCE_MPW_SHORT], [1],
+                             [Define to force small-width mp digits.])
+                   ;;
+                 cussid)
+                   AC_DEFINE([FORCE_MPW_CUSSID], [1],
+                             [Define to force strange-width mp digits.])
+                   ;;
+               esac])
+
 dnl --- Done ---
 
 mdw_MLIB(2.0.0)

diff --git a/ec-info.c b/ec-info.c
index 925ff07..3a5b096 100644 (file)
--- a/ec-info.c
+++ b/ec-info.c
@@ -571,7 +571,7 @@ int main(int argc, char *argv[])
       e = ec_checkinfo(&ei, gr);
       ec_freeinfo(&ei);
       if (e) {
-       printf("  [%s fails: %s]", ee->name, e);
+       printf(" [%s fails: %s]", ee->name, e);
        ok = 0;
       } else
        printf(" %s", ee->name);

diff --git a/factorial.c b/factorial.c
index 54b9845..396e6e1 100644 (file)
--- a/factorial.c
+++ b/factorial.c
@@ -48,7 +48,7 @@
 
 static void usage(FILE *fp)
 {
-  pquis(fp, "Usage: $ [-r radix] integer\n");
+  pquis(fp, "Usage: $ [-r RADIX] INTEGER\n");
 }
 
 static void version(FILE *fp)

diff --git a/gfreduce.c b/gfreduce.c
index bdf3579..01ca678 100644 (file)
--- a/gfreduce.c
+++ b/gfreduce.c
@@ -90,7 +90,7 @@ void gfreduce_create(gfreduce *r, mp *p)
   unsigned long i;
   gfreduce_instr *ip;
   unsigned f = 0;
-  size_t w, ww, wi, wl, ll;
+  size_t w, ww, wi, wl, ll, bb;
 
   /* --- Sort out the easy stuff --- */
 
@@ -121,6 +121,7 @@ void gfreduce_create(gfreduce *r, mp *p)
   wi = DA_LEN(&iv);
   f = 0;
   ll = 0;
+  bb = MPW_BITS - dw;
   for (i = 0, mp_scan(&sc, p); mp_step(&sc) && i < d; i++) {
     if (!mp_bit(&sc))
       continue;
@@ -149,8 +150,8 @@ void gfreduce_create(gfreduce *r, mp *p)
       w = ww;
       wi = DA_LEN(&iv);
     }
-    INSTR(GFRI_LSL, (MPW_BITS + i - d)%MPW_BITS);
-    if ((MPW_BITS + i - d)%MPW_BITS)
+    INSTR(GFRI_LSL, (bb + i)%MPW_BITS);
+    if ((bb + i)%MPW_BITS)
       f |= f_lsr;
   }
   wl = DA_LEN(&iv);

diff --git a/mp-arith.c b/mp-arith.c
index 3af1447..9cb5178 100644 (file)
--- a/mp-arith.c
+++ b/mp-arith.c
@@ -652,16 +652,16 @@ mp *mp_odd(mp *d, mp *m, size_t *s)
     ss = 0;
   else {
     mpw x = *v;
-    mpw mask = MPW_MAX;
-    unsigned z = MPW_BITS / 2;
+    unsigned z = MPW_P2;
+    mpw mask = ((mpw)1 << z) - 1;
 
     while (z) {
-      mask >>= z;
       if (!(x & mask)) {
        x >>= z;
        ss += z;
       }
       z >>= 1;
+      mask >>= z;
     }
   }
 

diff --git a/mpint.h b/mpint.h
index 23378cd..e44c39e 100644 (file)
--- a/mpint.h
+++ b/mpint.h
@@ -63,42 +63,33 @@
   MP_DEST(_d, _sz, 0);                                                 \
   _d->f &= ~(MP_NEG | MP_UNDEF);                                       \
                                                                        \
-  /* --- Set the sign on the MP --- *                                  \
-   *                                                                   \
-   * If the input integer is *not* negative, then negate it.  This     \
-   * fixes a problem with two's complement machines where the most     \
-   * negative value actually has larger magnitude than the most                \
-   * positive, and hence -TYPE_MIN == TYPE_MIN but TYPE_MIN != 0.  If  \
-   * all the work is carried out on negative numbers there isn't a     \
-   * problem.                                                          \
-   */                                                                  \
-                                                                       \
-  if (_i >= 0)                                                         \
-    _i = -_i;                                                          \
-  else                                                                 \
+  if (_i >= 0) {                                                       \
+    while (_i) {                                                       \
+      if (_o == _sz) {                                                 \
+       _sz <<= 1;                                                      \
+       MP_ENSURE(_d, _sz);                                             \
+      }                                                                        \
+      _d->v[_o++] = MPW(_i);                                           \
+      if (_i < MPW_MAX)                                                        \
+       break;                                                          \
+      else                                                             \
+       _i /= (type)MPW_MAX + 1;                                        \
+    }                                                                  \
+  } else {                                                             \
     _d->f |= MP_NEG;                                                   \
-                                                                       \
-  while (_i) {                                                         \
-    if (_o == _sz) {                                                   \
-      _sz <<= 1;                                                       \
-      MP_ENSURE(_d, _sz);                                              \
+    while (_i) {                                                       \
+      if (_o == _sz) {                                                 \
+       _sz <<= 1;                                                      \
+       MP_ENSURE(_d, _sz);                                             \
+      }                                                                        \
+      _d->v[_o++] = MPW(-_i);                                          \
+      if (_i > -MPW_MAX)                                               \
+       break;                                                          \
+      else                                                             \
+       _i /= (type)MPW_MAX + 1;                                        \
     }                                                                  \
-    _d->v[_o++] = MPW(-_i);                                            \
-                                                                       \
-    /* --- More subtlety --- *                                         \
-     *                                                                 \
-     * Ideally, I'd like to just shift @i@ right by @MPW_BITS@.  But I \
-     * can't, because that might be more than I'm allowed.  I can't    \
-     * divide by @MPW_MAX + 1@ because that might turn out to be zero  \
-     * in my current type, and besides which it's unsigned which messes        \
-     * up all of my negative arithmetic.  So do an explicit test here. \
-     */                                                                        \
-                                                                       \
-    if (_i >= -MPW_MAX)                                                        \
-      break;                                                           \
-    else                                                               \
-      _i /= (type)MPW_MAX + 1;                                         \
   }                                                                    \
+                                                                       \
   _d->vl = _d->v + _o;                                                 \
   (d) = _d;                                                            \
 } while (0)

diff --git a/mpmont-exp.c b/mpmont-exp.c
index 0caf118..301a0d8 100644 (file)
--- a/mpmont-exp.c
+++ b/mpmont-exp.c
@@ -130,7 +130,6 @@ static int texp(dstr *v)
   return ok;
 }
 
-
 static test_chunk tests[] = {
   { "exp", texp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
   { 0, 0, { 0 } },

diff --git a/mpreduce.c b/mpreduce.c
index d99ff16..bc41f60 100644 (file)
--- a/mpreduce.c
+++ b/mpreduce.c
@@ -60,7 +60,7 @@ int mpreduce_create(mpreduce *r, mp *p)
   instr_v iv = DA_INIT;
   unsigned long d, i;
   unsigned op;
-  size_t w, b;
+  size_t w, b, bb;
 
   /* --- Fill in the easy stuff --- */
 
@@ -101,10 +101,12 @@ int mpreduce_create(mpreduce *r, mp *p)
       case X0 | 0: st =  Z; printf("+ %lu\n", i - 1); break;
     }
   }
-  if (st >= X) printf("+ %lu\n", i);
+  if (st >= X) printf("+ %lu\n", i - 1);
+  st = Z;
 #endif
 
-  for (i = 0, mp_scan(&sc, p); i < d  - 1 && mp_step(&sc); i++) {
+  bb = MPW_BITS - (d + 1)%MPW_BITS;
+  for (i = 0, mp_scan(&sc, p); i < d && mp_step(&sc); i++) {
     switch (st | mp_bit(&sc)) {
       case  Z | 1: st = Z1; break;
       case Z1 | 0: st =  Z; op = MPRI_SUB; goto instr;
@@ -114,11 +116,11 @@ int mpreduce_create(mpreduce *r, mp *p)
       case X0 | 0: st =  Z; op = MPRI_SUB; goto instr;
       instr:
        w = (d - i)/MPW_BITS + 1;
-       b = (MPW_BITS + i - d - 1)%MPW_BITS;
+       b = (bb + i)%MPW_BITS;
        INSTR(op | !!b, w, b);
     }
   }
-  if ((DA(&iv)[DA_LEN(&iv) - 1].op & ~1u) == MPRI_SUB) {
+  if (DA_LEN(&iv) && (DA(&iv)[DA_LEN(&iv) - 1].op & ~1u) == MPRI_SUB) {
     mp_drop(r->p);
     DA_DESTROY(&iv);
     return (-1);
@@ -129,7 +131,9 @@ int mpreduce_create(mpreduce *r, mp *p)
   /* --- Wrap up --- */
 
   r->in = DA_LEN(&iv);
-  if (!r->s) {
+  if (!r->in)
+    r->iv = 0;
+  else if (!r->s) {
     r->iv = xmalloc(r->in * sizeof(mpreduce_instr));
     memcpy(r->iv, DA(&iv), r->in * sizeof(mpreduce_instr));
   } else {
@@ -151,6 +155,10 @@ int mpreduce_create(mpreduce *r, mp *p)
     }
   }
   DA_DESTROY(&iv);
+
+#ifdef DEBUG
+  mpreduce_dump(r, stdout);
+#endif
   return (0);
 }
 
@@ -166,7 +174,7 @@ int mpreduce_create(mpreduce *r, mp *p)
 void mpreduce_destroy(mpreduce *r)
 {
   mp_drop(r->p);
-  xfree(r->iv);
+  if (r->iv) xfree(r->iv);
 }
 
 /* --- @mpreduce_dump@ --- *
@@ -285,9 +293,9 @@ mp *mpreduce_do(mpreduce *r, mp *d, mp *x)
        *vl = 0;
        run(r->iv, il, vl, z);
 #ifdef DEBUG
-  MP_PRINTX("x", x);
-  mp_div(0, &_rr, x, r->p);
-  assert(MP_EQ(_r, _rr));
+       MP_PRINTX("x", x);
+       mp_div(0, &_rr, x, r->p);
+       assert(MP_EQ(_r, _rr));
 #endif
       }
     }
@@ -297,9 +305,9 @@ mp *mpreduce_do(mpreduce *r, mp *d, mp *x)
        *vl &= ((1 << r->s) - 1);
        run(r->iv + r->in, il + r->in, vl, z);
 #ifdef DEBUG
-  MP_PRINTX("x", x);
-  mp_div(0, &_rr, x, r->p);
-  assert(MP_EQ(_r, _rr));
+       MP_PRINTX("x", x);
+       mp_div(0, &_rr, x, r->p);
+       assert(MP_EQ(_r, _rr));
 #endif
       }
     }

diff --git a/mptypes.c b/mptypes.c
index 922eae4..381f3dc 100644 (file)
--- a/mptypes.c
+++ b/mptypes.c
@@ -30,6 +30,8 @@
 /*----- Header files ------------------------------------------------------*/
 
 #define _GNU_SOURCE
+#include "config.h"
+
 #include <stdio.h>
 #include <limits.h>
 #if __STDC_VERSION__ >= 199900l
@@ -60,7 +62,7 @@
   typedef uintmax_t umax;
 # define P_UMAX PRIuMAX
 #elif defined(ULLONG_MAX)
-  __extension__ typedef unsigned long long umax;
+  EXT typedef unsigned long long umax;
 # define P_UMAX "llu"
 #else
   typedef unsigned long umax;
@@ -105,6 +107,7 @@ int main(int argc, char *argv[])
   itype *i;
   itype *largest, *mpw, *mpd;
   const static char *extstr = "CATACOMB_MPTYPES_EXTENSION ";
+  unsigned p2;
 
   /* --- Find the bitcounts --- */
 
@@ -123,6 +126,17 @@ int main(int argc, char *argv[])
    * which is twice as big as that one.
    */
 
+#if defined(FORCE_MPW_CUSSID)
+  largest = mpd = &tytab[3];
+  mpw = &tytab[2];
+  mpw->bits = 19; mpw->max = 0x7ffff;
+  mpd->bits = 38; mpd->max = 0x3fffffffffll;
+#elif defined(FORCE_MPW_SHORT)
+  largest = mpd = &tytab[2];
+  mpw = &tytab[1];
+  mpw->bits = 16; mpw->max = 0xffff;
+  mpd->bits = 32; mpd->max = 0xffffffff;
+#else
   largest = tytab;
   for (i = tytab; i->name; i++) {
     if (i->bits > largest->bits)
@@ -145,6 +159,8 @@ int main(int argc, char *argv[])
     d.bits = w.bits * 2; d.max = ~(~((umax)0) << d.bits);
     mpw = &w; mpd = &d;
   }    
+#endif
+  for (p2 = 1; (p2 << 1) < mpw->bits; p2 <<= 1);
 
   /* --- Output time --- */
 
@@ -176,6 +192,7 @@ int main(int argc, char *argv[])
   printf("\
 %stypedef %s mpw;\n\
 #define MPW_BITS %u\n\
+#define MPW_P2 %u\n\
 #define MPW_MAX %s%" P_UMAX "%s\n\
 \n\
 %stypedef %s mpd;\n\
@@ -185,7 +202,7 @@ int main(int argc, char *argv[])
 #endif\n\
 ",
   mpw->flags & f_ext ? extstr : "", mpw->name,
-  mpw->bits,
+  mpw->bits, p2,
   mpw->flags & f_ext ? extstr : "", mpw->max, mpw->suff,
   mpd->flags & f_ext ? extstr : "", mpd->name,
   mpd->bits,

diff --git a/mpx.c b/mpx.c
index 5fc522a..01264b1 100644 (file)
--- a/mpx.c
+++ b/mpx.c
@@ -462,11 +462,11 @@ void mpx_lsl(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, size_t n)
 
     while (avl > av) {
       mpw t = *--avl;
-      *--dvl = (t >> nr) | w;
+      *--dvl = MPW((t >> nr) | w);
       w = t << nb;
     }
 
-    *--dvl = w;
+    *--dvl = MPW(w);
     MPX_ZERO(dv, dvl);
   }
 
@@ -560,11 +560,11 @@ void mpx_lslc(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, size_t n)
 
     while (avl > av) {
       mpw t = *--avl;
-      *--dvl = (t >> nr) | w;
+      *--dvl = MPW((t >> nr) | w);
       w = t << nb;
     }
 
-    *--dvl = (MPW_MAX >> nr) | w;
+    *--dvl = MPW((MPW_MAX >> nr) | w);
     MPX_ONE(dv, dvl);
   }
 
@@ -919,7 +919,7 @@ void mpx_usubnlsl(mpw *dv, mpw *dvl, mpw a, unsigned o)
   a <<= o;
 
   if (dv < dvl) {
-    mpd x = (mpd)*dv - (mpd)a;
+    mpd x = (mpd)*dv - MPW(a);
     *dv++ = MPW(x);
     if (x >> MPW_BITS)
       b++;
@@ -995,9 +995,7 @@ void mpx_umul(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl,
  */
 
 void mpx_umuln(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, mpw m)
-{
-  MPX_UMULN(dv, dvl, av, avl, m);
-}
+  { MPX_UMULN(dv, dvl, av, avl, m); }
 
 /* --- @mpx_umlan@ --- *
  *
@@ -1012,9 +1010,7 @@ void mpx_umuln(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, mpw m)
  */
 
 void mpx_umlan(mpw *dv, mpw *dvl, const mpw *av, const mpw *avl, mpw m)
-{
-  MPX_UMLAN(dv, dvl, av, avl, m);
-}
+  { MPX_UMLAN(dv, dvl, av, avl, m); }
 
 /* --- @mpx_usqr@ --- *
  *
@@ -1120,7 +1116,7 @@ void mpx_udiv(mpw *qv, mpw *qvl, mpw *rv, mpw *rvl,
     unsigned b;
 
     d = dvl[-1];
-    for (b = MPW_BITS / 2; b; b >>= 1) {
+    for (b = MPW_P2; b; b >>= 1) {
       if (d <= (MPW_MAX >> b)) {
        d <<= b;
        norm += b;

diff --git a/mpx.h b/mpx.h
index f79cffd..15253ed 100644 (file)
--- a/mpx.h
+++ b/mpx.h
@@ -89,7 +89,7 @@
   else {                                                               \
     unsigned long _b = MPW_BITS * (_vl - _v - 1) + 1;                  \
     mpw _w = _vl[-1];                                                  \
-    unsigned _k = MPW_BITS / 2;                                                \
+    unsigned _k = MPW_P2;                                              \
     while (_k) {                                                       \
       if (_w >> _k) {                                                  \
        _w >>= _k;                                                      \

diff --git a/tests/mpint b/tests/mpint
index c4faa39..49157ba 100644 (file)
--- a/tests/mpint
+++ b/tests/mpint
@@ -9,6 +9,9 @@ fromuint {
   0 0;
   1 1;
   -5 0xfffffffb;
+  0x7ffff 0x7ffff;
+  0x80000 0x80000;
+  0xfffff 0xfffff;
   0x7fffffff 0x7fffffff;
   0x80000000 0x80000000;               # Bastard torture test
   0xffffffff 0xffffffff;
@@ -18,6 +21,9 @@ fromint {
   0 0;
   1 1;
   -5 -5;
+  0x7ffff 0x7ffff;
+  0x80000 0x80000;
+  0xfffff 0xfffff;
   0x7fffffff 0x7fffffff;
   -0x80000000 -0x80000000;             # Bastard torture test
 }
@@ -26,6 +32,9 @@ touint {
   0 0;
   1 1;
   -5 -5;
+  0x7ffff 0x7ffff;
+  0x80000 0x80000;
+  0xfffff 0xfffff;
   0x7fffffff 0x7fffffff;
   0x80000000 -0x80000000;              # Bastard torture test
   0xffffffff 0xffffffff;
@@ -35,6 +44,9 @@ toint {
   0 0;
   1 1;
   -5 -5;
+  0x7ffff 0x7ffff;
+  0x80000 0x80000;
+  0xfffff 0xfffff;
   0x7fffffff 0x7fffffff;
   -0x80000000 -0x80000000;             # Bastard torture test
 }

diff --git a/tests/mpreduce b/tests/mpreduce
index 1734b18..1216f2e 100644 (file)
--- a/tests/mpreduce
+++ b/tests/mpreduce
@@ -3,6 +3,15 @@
 # Tests for efficient reduction
 
 reduce {
+  0xc000 0x16cb3 0xacb3;
+  0x8000 0x345545 0x5545;
+
+  0xfffef 0x100000 0x11;
+
+  0x1ffffffe 0x26fc6567 0x6fc6569;
+  0x3ffffffe 0x45445dc0 0x5445dc2;
+  0x7ffffffe 0xd4827a70 0x54827a72;
+
   0x72e2c37447f8bca34c4a39b130ea8e5c9a7d8b54564aa88ea773
   0x367aa8f5ba9ac4e8e2ea198b8af2c3b3081deab392ffc05715783b245a62a6fa
   0x08e8c03ebf398c63d71d8fd7ca4ece12367a8dde180ca650afb6;
@@ -13,7 +22,7 @@ reduce {
 }
 
 modexp {
-  0xfffffffdffffffffffffffffffffffff 0xfffffffdfffffffffffffffffffffffe 0 1; 
+  0xfffffffdffffffffffffffffffffffff 0xfffffffdfffffffffffffffffffffffe 0 1;
   0xfffffffdffffffffffffffffffffffff 2 
     0xfffffffdfffffffffffffffffffffffe 1;
   0xfffffffdffffffffffffffffffffffff 2 

diff --git a/tests/mpx b/tests/mpx
index 7f6ff5e..1ebc869 100644 (file)
--- a/tests/mpx
+++ b/tests/mpx
@@ -885,4 +885,6 @@ udiv {
   ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a63a3620ffffffffffffffff
   7fffffffffffffffe487ed5110b4611a62633145c06e0e68948127044533e63a0105df531d89cd9128a5043cc71a026ef7ca8cd9e69d218d98158536f92f8a1ba7f09ab6b6a8e122f242dabb312f3f637a262174d31d1b107fffffffffffffff
   02 01;
+
+  26737e 0ffffc 02 067386;
 }

diff --git a/utils/mpreducetests.py b/utils/mpreducetests.py
new file mode 100644 (file)
index 0000000..406eacb
--- /dev/null
+++ b/utils/mpreducetests.py
@@ -0,0 +1,20 @@
+#! /usr/bin/python
+
+import random as R
+
+print "# mpreduce torture"
+
+print "reduce {"
+first = True
+for i in xrange(16, 90):
+  for j in xrange(1, i - 1):
+    m = (1L << i) - (1L << j)
+    for k in xrange(i + 1, i + 16):
+      x = R.randrange(1L << k)
+      print "  0x%x" % m
+      print "    0x%x" % x
+      print "    0x%x;" % (x%m)
+      if not first:
+        print
+      first = False
+print "}"