ref: 6d429cf9e8418ec69d2516ccba370860e20afd63
dir: /sys/src/libmp/ntest.c/
/* tests missing for: mpint* strtomp(char *buf, char **rptr, int base, mpint *b) char* mptoa(mpint *b, int base, char *buf, int blen) mpint* betomp(uchar *buf, uint blen, mpint *b) int mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp) void mptober(mpint *b, uchar *buf, int blen) mpint* letomp(uchar *buf, uint blen, mpint *b) int mptole(mpint *b, uchar *buf, uint blen, uchar **bufp) void mptolel(mpint *b, uchar *buf, int blen) uint mptoui(mpint*) mpint* uitomp(uint, mpint*) int mptoi(mpint*) mpint* itomp(int, mpint*) mpint* vtomp(vlong, mpint*) vlong mptov(mpint*) mpint* uvtomp(uvlong, mpint*) uvlong mptouv(mpint*) mpint* dtomp(double, mpint*) double mptod(mpint*) void mpexp(mpint *b, mpint *e, mpint *m, mpint *res) void mpmod(mpint *b, mpint *m, mpint *remainder) void mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum) void mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff) void mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod) void mpsel(int s, mpint *b1, mpint *b2, mpint *res) void mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y) void mpinvert(mpint *b, mpint *m, mpint *res) void mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient) void mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum) void mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff) void mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p) int mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p) void mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,mpdigit *p) int mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen) */ #include <u.h> #include <libc.h> #include <mp.h> #include <libsec.h> typedef struct ldint ldint; struct ldint { int n; u8int *b; }; ldint _ldzero = {1, (u8int*)"\0"}; ldint _ldone = {2, (u8int*)"\1\0"}; ldint *ldzero = &_ldzero; ldint *ldone = &_ldone; static int ldget(ldint *a, int n) { if(n < 0) return 0; if(n >= a->n) return a->b[a->n - 1]&1; return a->b[n]&1; } static void ldbits(ldint *a, int n) { a->b = realloc(a->b, n); a->n = n; } static ldint * ldnorm(ldint *a) { int i; if(a->n > 0){ for(i = a->n - 2; i >= 0; i--) if(a->b[i] != a->b[a->n-1]) break; ldbits(a, i + 2); }else{ ldbits(a, 1); a->b[0] = 0; } return a; } static void ldneg(ldint *a) { int i, c; c = 1; for(i = 0; i < a->n; i++){ c += 1 ^ a->b[i] & 1; a->b[i] = c & 1; c >>= 1; } if(c != a->b[a->n - 1]){ ldbits(a, a->n + 1); a->b[a->n - 1] = c; } } static int max(int a, int b) { return a>b? a : b; } static ldint * ldnew(int n) { ldint *a; a = malloc(sizeof(ldint)); if(n <= 0) n = 1; a->b = malloc(n); a->n = n; return a; } static void ldfree(ldint *a) { if(a == nil) return; free(a->b); free(a); } static void ldsanity(ldint *a) { int i; assert(a->n > 0); for(i = 0; i < a->n; i++) assert(a->b[i] < 2); } static ldint * ldrand(int n, ldint *a) { int i; if(a == nil) a = ldnew(n); else ldbits(a, n); for(i = 0; i < n; i++) a->b[i] = rand() & 1; return a; } static mpint * ldtomp(ldint *a, mpint *b) { int s, c, i; if(b == nil) b = mpnew(0); mpbits(b, a->n); s = a->b[a->n - 1] & 1; b->sign = 1 - 2 * s; c = s; memset(b->p, 0, (a->n + Dbits - 1) / Dbits * Dbytes); for(i = 0; i < a->n; i++){ c += s ^ a->b[i] & 1; b->p[i / Dbits] |= (mpdigit)(c & 1) << (i & Dbits - 1); c >>= 1; } b->top = (a->n + Dbits - 1) / Dbits; mpnorm(b); return b; } static void mptold(mpint *b, ldint *a) { int i, j, n, c; n = mpsignif(b) + 1; ldbits(a, n); memset(a->b, 0, n); for(i = 0; i <= b->top; i++) for(j = 0; j < Dbits; j++) if(Dbits * i + j < n) a->b[Dbits * i + j] = b->p[i] >> j & 1; if(b->sign < 0){ c = 1; for(i = 0; i < a->n; i++){ c += 1 ^ a->b[i] & 1; a->b[i] = c & 1; c >>= 1; } } } static ldint * itold(int n, ldint *a) { int i; if(a == nil) a = ldnew(sizeof(n)*8); else ldbits(a, sizeof(n)*8); for(i = 0; i < sizeof(n)*8; i++) a->b[i] = n >> i & 1; ldnorm(a); return a; } static ldint * pow2told(int n, ldint *a) { int k; k = abs(n); if(a == nil) a = ldnew(k+2); else ldbits(a, k+2); memset(a->b, 0, k+2); a->b[k] = 1; if(n < 0) ldneg(a); ldnorm(a); return a; } static int ldfmt(Fmt *f) { ldint *a; char *b, *p; int i, d, s, c; a = va_arg(f->args, ldint *); d = (a->n + 3) / 4; b = calloc(1, d + 1); c = s = a->b[a->n - 1]; for(i = 0; i < a->n; i++){ c += s^ldget(a, i); b[d - 1 - (i >> 2)] |= (c & 1) << (i & 3); c >>= 1; } for(i = 0; i < d; i++) b[i] = "0123456789ABCDEF"[b[i]]; p = b; while(*p == '0' && p[1] != 0) p++; if(a->b[a->n - 1]) fmtrune(f, '-'); fmtprint(f, "0x%s", p); free(b); return 0; } static int mpdetfmt(Fmt *f) { mpint *a; int i, j; a = va_arg(f->args, mpint *); fmtprint(f, "(sign=%d,top=%d,size=%d,", a->sign, a->top, a->size); for(i=0;i<a->top;){ fmtprint(f, "%ullx", (uvlong)a->p[i]); if(++i == a->top) break; fmtrune(f, ','); for(j = i+1; j < a->top; j++) if(a->p[i] != a->p[j]) goto next; fmtprint(f, "..."); break; next:; } fmtrune(f, '|'); for(i=a->top;i<a->size;){ fmtprint(f, "%ullx", (uvlong)a->p[i]); if(++i == a->size) break; fmtrune(f, ','); for(j = i+1; j < a->top; j++) if(a->p[i] != a->p[j]) goto next2; fmtprint(f, "..."); break; next2:; } fmtrune(f, ')'); return 0; } static int ldcmp(ldint *a, ldint *b) { int x, y; int i, r; r = max(a->n, b->n); if(a->b[a->n-1] != b->b[b->n-1]) return b->b[b->n - 1] - a->b[a->n - 1]; for(i = r - 1; --i >= 0; ){ x = ldget(a, i); y = ldget(b, i); if(x != y) return x - y; } return 0; } static int ldmagcmp(ldint *a, ldint *b) { int s1, s2, r; s1 = a->b[a->n - 1]; s2 = b->b[b->n - 1]; if(s1) ldneg(a); if(s2) ldneg(b); r = ldcmp(a, b); if(s1) ldneg(a); if(s2) ldneg(b); return r; } static int ldmpeq(ldint *a, mpint *b) { int i, c; if(b->sign > 0){ for(i = 0; i < b->top * Dbits; i++) if(ldget(a, i) != (b->p[i / Dbits] >> (i & Dbits - 1) & 1)) return 0; for(; i < a->n; i++) if(a->b[i] != 0) return 0; return 1; }else{ c = 1; for(i = 0; i < b->top * Dbits; i++){ c += !ldget(a, i); if((c & 1) != (b->p[i / Dbits] >> (i & Dbits - 1) & 1)) return 0; c >>= 1; } for(; i < a->n; i++) if(a->b[i] != 1) return 0; return 1; } } static mpint * mptarget(void) { mpint *r; int i, n; r = mpnew(0); n = nrand(16); mpbits(r, n * Dbits); r->top = n; prng((void *) r->p, n * Dbytes); r->sign = 1 - 2 * (rand() & 1); return r; } static void ldadd(ldint *a, ldint *b, ldint *q) { int r, i, x, c; r = max(a->n, b->n) + 1; ldbits(q, r); c = 0; for(i = 0; i < r; i++){ c += ldget(a, i) + ldget(b, i); q->b[i] = c & 1; c >>= 1; } ldnorm(q); } static void ldmagadd(ldint *a, ldint *b, ldint *q) { int i, r, s1, s2, c1, c2, co; r = max(a->n, b->n) + 2; ldbits(q, r); co = 0; s1 = c1 = a->b[a->n - 1] & 1; s2 = c2 = b->b[b->n - 1] & 1; for(i = 0; i < r; i++){ c1 += s1 ^ ldget(a, i) & 1; c2 += s2 ^ ldget(b, i) & 1; co += (c1 & 1) + (c2 & 1); q->b[i] = co & 1; co >>= 1; c1 >>= 1; c2 >>= 1; } ldnorm(q); } static void ldmagsub(ldint *a, ldint *b, ldint *q) { int i, r, s1, s2, c1, c2, co; r = max(a->n, b->n) + 2; ldbits(q, r); co = 0; s1 = c1 = a->b[a->n - 1] & 1; s2 = c2 = 1 ^ b->b[b->n - 1] & 1; for(i = 0; i < r; i++){ c1 += s1 ^ ldget(a, i) & 1; c2 += s2 ^ ldget(b, i) & 1; co += (c1 & 1) + (c2 & 1); q->b[i] = co & 1; co >>= 1; c1 >>= 1; c2 >>= 1; } ldnorm(q); } static void ldsub(ldint *a, ldint *b, ldint *q) { int r, i, x, c; r = max(a->n, b->n) + 1; ldbits(q, r); c = 1; for(i = 0; i < r; i++){ c += ldget(a, i) + (1^ldget(b, i)); q->b[i] = c & 1; c >>= 1; } ldnorm(q); } static void ldmul(ldint *a, ldint *b, ldint *q) { int c1, c2, co, s1, s2, so, i, j; c1 = s1 = a->b[a->n - 1] & 1; s2 = b->b[b->n - 1] & 1; so = s1 ^ s2; ldbits(q, a->n + b->n + 1); memset(q->b, 0, a->n + b->n + 1); for(i = 0; i < a->n; i++){ c1 += s1 ^ a->b[i] & 1; if((c1 & 1) != 0){ c2 = s2; for(j = 0; j < b->n; j++){ c2 += (s2 ^ b->b[j] & 1) + q->b[i + j]; q->b[i + j] = c2 & 1; c2 >>= 1; } for(; c2 > 0; j++){ assert(i + j < q->n); q->b[i + j] = c2 & 1; c2 >>= 1; } } c1 >>= 1; } co = so; for(i = 0; i < q->n; i++){ co += so ^ q->b[i]; q->b[i] = co & 1; co >>= 1; } } static void lddiv(ldint *a, ldint *b, ldint *q, ldint *r) { int n, i, j, c, s, k; n = max(a->n, b->n) + 1; ldbits(q, n); ldbits(r, n); memset(r->b, 0, n); c = s = a->b[a->n-1]; for(i = 0; i < n; i++){ c += s ^ ldget(a, i); q->b[i] = c & 1; c >>= 1; } for(i = 0; i < n; i++){ for(j = n-1; --j >= 0; ) r->b[j + 1] = r->b[j]; r->b[0] = q->b[n - 1]; for(j = n-1; --j >= 0; ) q->b[j + 1] = q->b[j]; q->b[0] = !r->b[n - 1]; c = s = r->b[n - 1] == b->b[b->n - 1]; for(j = 0; j < n; j++){ c += r->b[j] + (s ^ ldget(b, j)); r->b[j] = c & 1; c >>= 1; } } for(j = n-1; --j >= 0; ) q->b[j + 1] = q->b[j]; q->b[0] = 1; if(r->b[r->n - 1]){ c = 0; for(j = 0; j < n; j++){ c += 1 + q->b[j]; q->b[j] = c & 1; c >>= 1; } c = s = b->b[b->n - 1]; for(j = 0; j < n; j++){ c += r->b[j] + (s ^ ldget(b, j)); r->b[j] = c & 1; c >>= 1; } } c = s = a->b[a->n-1] ^ b->b[b->n-1]; for(j = 0; j < n; j++){ c += s ^ q->b[j]; q->b[j] = c & 1; c >>= 1; } c = s = a->b[a->n-1]; for(j = 0; j < n; j++){ c += s ^ r->b[j]; r->b[j] = c & 1; c >>= 1; } ldnorm(q); ldnorm(r); } static void lddivq(ldint *a, ldint *b, ldint *q) { ldint *r; if(ldmpeq(b, mpzero)){ memset(q->b, 0, q->n); return; } r = ldnew(0); lddiv(a, b, q, r); ldfree(r); } static void mpdivq(mpint *a, mpint *b, mpint *q) { if(mpcmp(b, mpzero) == 0){ mpassign(mpzero, q); return; } mpdiv(a, b, q, nil); } static void lddivr(ldint *a, ldint *b, ldint *r) { ldint *q; if(ldmpeq(b, mpzero)){ memset(r->b, 0, r->n); return; } q = ldnew(0); lddiv(a, b, q, r); ldfree(q); } static void mpdivr(mpint *a, mpint *b, mpint *r) { if(mpcmp(b, mpzero) == 0){ mpassign(mpzero, r); return; } mpdiv(a, b, nil, r); } static void ldand(ldint *a, ldint *b, ldint *q) { int r, i, x, c; r = max(a->n, b->n); ldbits(q, r); for(i = 0; i < r; i++) q->b[i] = ldget(a, i) & ldget(b, i); ldnorm(q); } static void ldbic(ldint *a, ldint *b, ldint *q) { int r, i, x, c; r = max(a->n, b->n); ldbits(q, r); for(i = 0; i < r; i++) q->b[i] = ldget(a, i) & ~ldget(b, i); ldnorm(q); } static void ldor(ldint *a, ldint *b, ldint *q) { int r, i, x, c; r = max(a->n, b->n); ldbits(q, r); for(i = 0; i < r; i++) q->b[i] = ldget(a, i) | ldget(b, i); ldnorm(q); } static void ldxor(ldint *a, ldint *b, ldint *q) { int r, i, x, c; r = max(a->n, b->n); ldbits(q, r); for(i = 0; i < r; i++) q->b[i] = ldget(a, i) ^ ldget(b, i); ldnorm(q); } static void ldleft(ldint *a, int n, ldint *b) { int i, c; if(n < 0){ if(a->n <= -n){ b->n = 0; ldnorm(b); return; } c = 0; if(a->b[a->n - 1]) for(i = 0; i < -n; i++) if(a->b[i]){ c = 1; break; } ldbits(b, a->n + n); for(i = 0; i < a->n + n; i++){ c += a->b[i - n] & 1; b->b[i] = c & 1; c >>= 1; } }else{ ldbits(b, a->n + n); memmove(b->b + n, a->b, a->n); memset(b->b, 0, n); } ldnorm(b); } static void ldasr(ldint *a, int n, ldint *b) { if(n < 0){ ldleft(a, -n, b); return; } if(a->n <= n){ ldbits(b, 1); b->b[0] = a->b[a->n - 1]; return; } ldbits(b, a->n - n); memmove(b->b, a->b + n, a->n - n); ldnorm(b); } static void ldtrunc(ldint *a, int n, ldint *b) { ldbits(b, n+1); b->b[n] = 0; if(a->n >= n) memmove(b->b, a->b, n); else{ memmove(b->b, a->b, a->n); memset(b->b + a->n, a->b[a->n - 1], n - a->n); } ldnorm(b); } static void ldxtend(ldint *a, int n, ldint *b) { ldbits(b, n); if(a->n >= n) memmove(b->b, a->b, n); else{ memmove(b->b, a->b, a->n); memset(b->b + a->n, a->b[a->n - 1], n - a->n); } ldnorm(b); } static void mpnot_(mpint *a, int, mpint *b) { mpnot(a, b); } static void ldnot(ldint *a, int, ldint *b) { int i; ldbits(b, a->n); for(i = 0; i < a->n; i++) b->b[i] = a->b[i] ^ 1; } enum { NTEST = 2*257 }; static void testgen(int i, ldint *a) { if(i < 257) itold(i-128, a); else pow2told(i-385, a); } typedef struct Test2 Test2; struct Test2 { char *name; void (*dut)(mpint *, mpint *, mpint *); void (*ref)(ldint *, ldint *, ldint *); }; typedef struct Test1i Test1i; struct Test1i { char *name; enum { NONEG = 1 } flags; void (*dut)(mpint *, int, mpint *); void (*ref)(ldint *, int, ldint *); }; int validate(char *name, ldint *ex, mpint *res, char *str) { int rv; rv = 1; if(res->top == 0 && res->sign < 0){ fprint(2, "FAIL: %s: %s: got -0, shouldn't happen\n", name, str); rv =0; }else if(!ldmpeq(ex, res)){ fprint(2, "FAIL: %s: %s: got %#B, expected %L\n", name, str, res, ex); rv = 0; } free(str); return rv; } int test2(Test2 *t, ldint *a, ldint *b) { ldint *c; mpint *ma, *mb, *rc; int rv; c = ldnew(0); t->ref(a, b, c); ldsanity(a); ldsanity(b); ldsanity(c); ma = ldtomp(a, nil); mb = ldtomp(b, nil); rc = mptarget(); t->dut(ma, mb, rc); rv = validate(t->name, c, rc, smprint("%L and %L", a, b)); ldtomp(a, ma); ldtomp(b, mb); t->dut(ma, mb, mb); rv = validate(t->name, c, mb, smprint("%L and %L (aliased to result)", a, b)); ldtomp(a, ma); ldtomp(b, mb); t->dut(ma, mb, ma); rv = validate(t->name, c, ma, smprint("%L (aliased to result) and %L", a, b)); ldfree(c); mpfree(rc); mpfree(ma); mpfree(mb); return rv; } int test2x(Test2 *t, ldint *a) { ldint *c; mpint *ma, *rc; int rv; c = ldnew(0); t->ref(a, a, c); ldsanity(a); ldsanity(c); ma = ldtomp(a, nil); rc = mptarget(); t->dut(ma, ma, rc); rv = validate(t->name, c, rc, smprint("%L and %L (aliased to each other)", a, a)); ldtomp(a, ma); t->dut(ma, ma, ma); rv = validate(t->name, c, ma, smprint("%L and %L (both aliased to result)", a, a)); ldfree(c); mpfree(rc); mpfree(ma); return rv; } void run2(Test2 *t) { int i, j, ok; ldint *a, *b, *c; a = ldnew(32); b = ldnew(32); c = ldnew(32); ok = 1; for(i = 0; i < NTEST; i++){ for(j = 0; j < NTEST; j++){ testgen(i, a); testgen(j, b); ok &= test2(t, a, b); } itold(i, a); ok &= test2x(t, a); } for(i = 1; i <= 4; i++) for(j = 1; j <= 4; j++){ ldrand(i * Dbits, a); ldrand(j * Dbits, b); ok &= test2(t, a, b); } ldfree(a); ldfree(b); if(ok) fprint(2, "%s: passed\n", t->name); } Test2 tests2[] = { "mpadd", mpadd, ldadd, "mpmagadd", mpmagadd, ldmagadd, "mpsub", mpsub, ldsub, "mpmagsub", mpmagsub, ldmagsub, "mpand", mpand, ldand, "mpor", mpor, ldor, "mpbic", mpbic, ldbic, "mpxor", mpxor, ldxor, "mpmul", mpmul, ldmul, "mpdiv(q)", mpdivq, lddivq, "mpdiv(r)", mpdivr, lddivr, }; void all2(void) { Test2 *t; for(t = tests2; t < tests2 + nelem(tests2); t++) run2(t); } int test1i(Test1i *t, ldint *a, int b) { ldint *c; mpint *ma, *rc; int rv; c = ldnew(0); t->ref(a, b, c); ldsanity(a); ldsanity(c); ma = ldtomp(a, nil); rc = mptarget(); t->dut(ma, b, rc); rv = validate(t->name, c, rc, smprint("%L and %d", a, b)); ldtomp(a, ma); t->dut(ma, b, ma); rv = validate(t->name, c, ma, smprint("%L (aliased to result) and %d", a, b)); ldfree(c); mpfree(rc); mpfree(ma); return rv; } void run1i(Test1i *t) { int i, j, ok; ldint *a, *c; a = ldnew(32); c = ldnew(32); ok = 1; for(i = 0; i < NTEST; i++) for(j = (t->flags & NONEG) != 0 ? 0 : -128; j <= 128; j++){ testgen(i, a); ok &= test1i(t, a, j); } ldfree(a); ldfree(c); if(ok) fprint(2, "%s: passed\n", t->name); } Test1i tests1i[] = { "mpleft", 0, mpleft, ldleft, "mpasr", 0, mpasr, ldasr, "mptrunc", NONEG, mptrunc, ldtrunc, "mpxtend", NONEG, mpxtend, ldxtend, "mpnot", NONEG, mpnot_, ldnot, /* hack */ }; void all1i(void) { Test1i *t; for(t = tests1i; t < tests1i + nelem(tests1i); t++) run1i(t); } void siglo(void) { int i, j, k; ldint *a; mpint *ma; int sigok, lowok0; a = ldnew(32); ma = mpnew(0); sigok = 1; lowok0 = 1; for(i = 0; i < NTEST; i++){ testgen(i, a); for(j = 0; j < a->n; j++) if(a->b[j] != 0) break; if(j == a->n) j = 0; ldtomp(a, ma); k = mplowbits0(ma); if(k != j){ fprint(2, "FAIL: mplowbits0: %#B: got %d, expected %d\n", ma, k, j); lowok0 = 0; } for(j = a->n - 2; j >= 0; j--) if(a->b[j] != a->b[a->n-1]) break; for(k = j-1; k >= 0; k--) if(a->b[k] != 0) break; if(a->b[a->n - 1] && k < 0) j++; j++; ldtomp(a, ma); k = mpsignif(ma); if(k != j){ fprint(2, "FAIL: mpsignif: %#B: got %d, expected %d\n", ma, k, j); sigok = 0; } } if(sigok) fprint(2, "mpsignif: passed\n"); if(lowok0) fprint(2, "mplowbits0: passed\n"); ldfree(a); mpfree(ma); } void cmptest(void) { int i, j, k, l; ldint *a, *b; mpint *ma, *mb; int cmpok, magcmpok; a = ldnew(32); b = ldnew(32); ma = mpnew(0); mb = mpnew(0); cmpok = 1; magcmpok = 1; for(i = 0; i < NTEST; i++) for(j = 0; j < NTEST; j++){ testgen(i, a); testgen(j, b); ldtomp(a, ma); ldtomp(b, mb); l = ldcmp(a, b); k = mpcmp(ma, mb); if(k < 0) k = -1; if(k > 0) k = 1; if(k != l){ fprint(2, "FAIL: mpcmp: %L and %L: got %d, expected %d\n", a, b, k, l); cmpok = 1; } ldtomp(a, ma); ldtomp(b, mb); l = ldmagcmp(a, b); k = mpmagcmp(ma, mb); if(k < 0) k = -1; if(k > 0) k = 1; if(k != l){ fprint(2, "FAIL: mpmagcmp: %L and %L: got %d, expected %d\n", a, b, k, l); magcmpok = 1; } } ldfree(a); ldfree(b); mpfree(ma); mpfree(mb); if(cmpok) fprint(2, "mpcmp: passed\n"); if(magcmpok) fprint(2, "mpmagcmp: passed\n"); } void main() { fmtinstall('B', mpfmt); fmtinstall(L'β', mpdetfmt); fmtinstall('L', ldfmt); siglo(); cmptest(); all1i(); all2(); }