From: Mark Wooding Date: Tue, 16 Jan 2007 22:20:15 +0000 (+0000) Subject: Merge branch 'fixes' X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/d2d54c98e2d65c46c5fe6519812aa4c6ea55ea02?hp=d7f3f07d10ea7421546462f4d71c1f7455115d16 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 --- 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 --- 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 --- 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 --- 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 --- 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 --- 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 --- 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 --- 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 --- a/mptypes.c +++ b/mptypes.c @@ -30,6 +30,8 @@ /*----- Header files ------------------------------------------------------*/ #define _GNU_SOURCE +#include "config.h" + #include #include #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 --- 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 --- 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 --- 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 --- 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 --- 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 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 "}"