sys/src/libmp/ntest.c

   1 /*
   2
   3 tests missing for:
   4
   5           mpint*  strtomp(char *buf, char **rptr, int base, mpint *b)
   6           char*   mptoa(mpint *b, int base, char *buf, int blen)
   7           mpint*  betomp(uchar *buf, uint blen, mpint *b)
   8           int     mptobe(mpint *b, uchar *buf, uint blen, uchar **bufp)
   9           void    mptober(mpint *b, uchar *buf, int blen)
  10           mpint*  letomp(uchar *buf, uint blen, mpint *b)
  11           int     mptole(mpint *b, uchar *buf, uint blen, uchar **bufp)
  12           void    mptolel(mpint *b, uchar *buf, int blen)
  13           uint    mptoui(mpint*)
  14           mpint*  uitomp(uint, mpint*)
  15           int     mptoi(mpint*)
  16           mpint*  itomp(int, mpint*)
  17           mpint*  vtomp(vlong, mpint*)
  18           vlong   mptov(mpint*)
  19           mpint*  uvtomp(uvlong, mpint*)
  20           uvlong  mptouv(mpint*)
  21           mpint*  dtomp(double, mpint*)
  22           double  mptod(mpint*)
  23           void    mpexp(mpint *b, mpint *e, mpint *m, mpint *res)
  24           void    mpmod(mpint *b, mpint *m, mpint *remainder)
  25           void    mpmodadd(mpint *b1, mpint *b2, mpint *m, mpint *sum)
  26           void    mpmodsub(mpint *b1, mpint *b2, mpint *m, mpint *diff)
  27           void    mpmodmul(mpint *b1, mpint *b2, mpint *m, mpint *prod)
  28           void    mpsel(int s, mpint *b1, mpint *b2, mpint *res)
  29           void    mpextendedgcd(mpint *a, mpint *b, mpint *d, mpint *x, mpint *y)
  30           void    mpinvert(mpint *b, mpint *m, mpint *res)
  31           void    mpdigdiv(mpdigit *dividend, mpdigit divisor, mpdigit *quotient)
  32           void    mpvecadd(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *sum)
  33           void    mpvecsub(mpdigit *a, int alen, mpdigit *b, int blen, mpdigit *diff)
  34           void    mpvecdigmuladd(mpdigit *b, int n, mpdigit m, mpdigit *p)
  35           int     mpvecdigmulsub(mpdigit *b, int n, mpdigit m, mpdigit *p)
  36           void    mpvecmul(mpdigit *a, int alen, mpdigit *b, int blen,mpdigit *p)
  37           int     mpveccmp(mpdigit *a, int alen, mpdigit *b, int blen)
  38 */
  39
  40 #include <u.h>
  41 #include <libc.h>
  42 #include <mp.h>
  43 #include <libsec.h>
  44
  45 typedef struct ldint ldint;
  46
  47 struct ldint {
  48         int n;
  49         u8int *b;
  50 };
  51
  52 ldint _ldzero = {1, (u8int*)"\0"};
  53 ldint _ldone = {2, (u8int*)"\1\0"};
  54 ldint *ldzero = &_ldzero;
  55 ldint *ldone = &_ldone;
  56
  57 static int
  58 ldget(ldint *a, int n)
  59 {
  60         if(n < 0) return 0;
  61         if(n >= a->n) return a->b[a->n - 1]&1;
  62         return a->b[n]&1;
  63 }
  64
  65 static void
  66 ldbits(ldint *a, int n)
  67 {
  68         a->b = realloc(a->b, n);
  69         a->n = n;
  70 }
  71
  72 static ldint *
  73 ldnorm(ldint *a)
  74 {
  75         int i;
  76
  77         if(a->n > 0){
  78                 for(i = a->n - 2; i >= 0; i--)
  79                         if(a->b[i] != a->b[a->n-1])
  80                                 break;
  81                 ldbits(a, i + 2);
  82         }else{
  83                 ldbits(a, 1);
  84                 a->b[0] = 0;
  85         }
  86         return a;
  87 }
  88
  89 static void
  90 ldneg(ldint *a)
  91 {
  92         int i, c;
  93
  94         c = 1;
  95         for(i = 0; i < a->n; i++){
  96                 c += 1 ^ a->b[i] & 1;
  97                 a->b[i] = c & 1;
  98                 c >>= 1;
  99         }
 100         if(c != a->b[a->n - 1]){
 101                 ldbits(a, a->n + 1);
 102                 a->b[a->n - 1] = c;
 103         }
 104 }
 105
 106 static int
 107 max(int a, int b)
 108 {
 109         return a>b? a : b;
 110 }
 111
 112 static ldint *
 113 ldnew(int n)
 114 {
 115         ldint *a;
 116
 117         a = malloc(sizeof(ldint));
 118         if(n <= 0) n = 1;
 119         a->b = malloc(n);
 120         a->n = n;
 121         return a;
 122 }
 123
 124 static void
 125 ldfree(ldint *a)
 126 {
 127         if(a == nil) return;
 128         free(a->b);
 129         free(a);
 130 }
 131
 132 static void
 133 ldsanity(ldint *a)
 134 {
 135         int i;
 136
 137         assert(a->n > 0);
 138         for(i = 0; i < a->n; i++)
 139                 assert(a->b[i] < 2);
 140 }
 141
 142 static ldint *
 143 ldrand(int n, ldint *a)
 144 {
 145         int i;
 146
 147         if(a == nil)
 148                 a = ldnew(n);
 149         else
 150                 ldbits(a, n);
 151         for(i = 0; i < n; i++)
 152                 a->b[i] = rand() & 1;
 153         return a;
 154 }
 155
 156 static mpint *
 157 ldtomp(ldint *a, mpint *b)
 158 {
 159         int s, c, i;
 160
 161         if(b == nil)
 162                 b = mpnew(0);
 163         mpbits(b, a->n);
 164         s = a->b[a->n - 1] & 1;
 165         b->sign = 1 - 2 * s;
 166         c = s;
 167         memset(b->p, 0, (a->n + Dbits - 1) / Dbits * Dbytes);
 168         for(i = 0; i < a->n; i++){
 169                 c += s ^ a->b[i] & 1;
 170                 b->p[i / Dbits] |= (mpdigit)(c & 1) << (i & Dbits - 1);
 171                 c >>= 1;
 172         }
 173         b->top = (a->n + Dbits - 1) / Dbits;
 174         mpnorm(b);
 175         return b;
 176 }
 177
 178 static void
 179 mptold(mpint *b, ldint *a)
 180 {
 181         int i, j, n, c;
 182
 183         n = mpsignif(b) + 1;
 184         ldbits(a, n);
 185         memset(a->b, 0, n);
 186         for(i = 0; i <= b->top; i++)
 187                 for(j = 0; j < Dbits; j++)
 188                         if(Dbits * i + j < n)
 189                                 a->b[Dbits * i + j] = b->p[i] >> j & 1;
 190         if(b->sign < 0){
 191                 c = 1;
 192                 for(i = 0; i < a->n; i++){
 193                         c += 1 ^ a->b[i] & 1;
 194                         a->b[i] = c & 1;
 195                         c >>= 1;
 196                 }
 197         }
 198 }
 199
 200 static ldint *
 201 itold(int n, ldint *a)
 202 {
 203         int i;
 204
 205         if(a == nil)
 206                 a = ldnew(sizeof(n)*8);
 207         else
 208                 ldbits(a, sizeof(n)*8);
 209         for(i = 0; i < sizeof(n)*8; i++)
 210                 a->b[i] = n >> i & 1;
 211         ldnorm(a);
 212         return a;
 213 }
 214
 215 static ldint *
 216 pow2told(int n, ldint *a)
 217 {
 218         int k;
 219
 220         k = abs(n);
 221         if(a == nil)
 222                 a = ldnew(k+2);
 223         else
 224                 ldbits(a, k+2);
 225         memset(a->b, 0, k+2);
 226         a->b[k] = 1;
 227         if(n < 0) ldneg(a);
 228         ldnorm(a);
 229         return a;
 230 }
 231
 232 static int
 233 ldfmt(Fmt *f)
 234 {
 235         ldint *a;
 236         char *b, *p;
 237         int i, d, s, c;
 238
 239         a = va_arg(f->args, ldint *);
 240         d = (a->n + 3) / 4;
 241         b = calloc(1, d + 1);
 242         c = s = a->b[a->n - 1];
 243         for(i = 0; i < a->n; i++){
 244                 c += s^ldget(a, i);
 245                 b[d - 1 - (i >> 2)] |= (c & 1) << (i & 3);
 246                 c >>= 1;
 247         }
 248         for(i = 0; i < d; i++)
 249                 b[i] = "0123456789ABCDEF"[b[i]];
 250         p = b;
 251         while(*p == '0' && p[1] != 0) p++;
 252         if(a->b[a->n - 1]) fmtrune(f, '-');
 253         fmtprint(f, "0x%s", p);
 254         free(b);
 255         return 0;
 256 }
 257
 258 static int
 259 mpdetfmt(Fmt *f)
 260 {
 261         mpint *a;
 262         int i, j;
 263
 264         a = va_arg(f->args, mpint *);
 265         fmtprint(f, "(sign=%d,top=%d,size=%d,", a->sign, a->top, a->size);
 266         for(i=0;i<a->top;){
 267                 fmtprint(f, "%ullx", (uvlong)a->p[i]);
 268                 if(++i == a->top) break;
 269                 fmtrune(f, ',');
 270                 for(j = i+1; j < a->top;  j++)
 271                         if(a->p[i] != a->p[j])
 272                                 goto next;
 273                 fmtprint(f, "...");
 274                 break;
 275         next:;
 276         }
 277         fmtrune(f, '|');
 278         for(i=a->top;i<a->size;){
 279                 fmtprint(f, "%ullx", (uvlong)a->p[i]);
 280                 if(++i == a->size) break;
 281                 fmtrune(f, ',');
 282                 for(j = i+1; j < a->top;  j++)
 283                         if(a->p[i] != a->p[j])
 284                                 goto next2;
 285                 fmtprint(f, "...");
 286                 break;
 287         next2:;
 288         }
 289         fmtrune(f, ')');
 290         return 0;
 291 }
 292
 293 static int
 294 ldcmp(ldint *a, ldint *b)
 295 {
 296         int x, y;
 297         int i, r;
 298
 299         r = max(a->n, b->n);
 300         if(a->b[a->n-1] != b->b[b->n-1])
 301                 return b->b[b->n - 1] - a->b[a->n - 1];
 302         for(i = r - 1; --i >= 0; ){
 303                 x = ldget(a, i);
 304                 y = ldget(b, i);
 305                 if(x != y)
 306                         return x - y;
 307         }
 308         return 0;
 309 }
 310
 311 static int
 312 ldmagcmp(ldint *a, ldint *b)
 313 {
 314         int s1, s2, r;
 315
 316         s1 = a->b[a->n - 1];
 317         s2 = b->b[b->n - 1];
 318         if(s1) ldneg(a);
 319         if(s2) ldneg(b);
 320         r = ldcmp(a, b);
 321         if(s1) ldneg(a);
 322         if(s2) ldneg(b);
 323         return r;
 324 }
 325
 326 static int
 327 ldmpeq(ldint *a, mpint *b)
 328 {
 329         int i, c;
 330
 331         if(b->sign > 0){
 332                 for(i = 0; i < b->top * Dbits; i++)
 333                         if(ldget(a, i) != (b->p[i / Dbits] >> (i & Dbits - 1) & 1))
 334                                 return 0;
 335                 for(; i < a->n; i++)
 336                         if(a->b[i] != 0)
 337                                 return 0;
 338                 return 1;
 339         }else{
 340                 c = 1;
 341                 for(i = 0; i < b->top * Dbits; i++){
 342                         c += !ldget(a, i);
 343                         if((c & 1) != (b->p[i / Dbits] >> (i & Dbits - 1) & 1))
 344                                 return 0;
 345                         c >>= 1;
 346                 }
 347                 for(; i < a->n; i++)
 348                         if(a->b[i] != 1)
 349                                 return 0;
 350                 return 1;
 351         }
 352 }
 353
 354 static mpint *
 355 mptarget(void)
 356 {
 357         mpint *r;
 358         int i, n;
 359
 360         r = mpnew(0);
 361         n = nrand(16);
 362         mpbits(r, n * Dbits);
 363         r->top = n;
 364         prng((void *) r->p, n * Dbytes);
 365         r->sign = 1 - 2 * (rand() & 1);
 366         return r;
 367 }
 368
 369 static void
 370 ldadd(ldint *a, ldint *b, ldint *q)
 371 {
 372         int r, i, x, c;
 373
 374         r = max(a->n, b->n) + 1;
 375         ldbits(q, r);
 376         c = 0;
 377         for(i = 0; i < r; i++){
 378                 c += ldget(a, i) + ldget(b, i);
 379                 q->b[i] = c & 1;
 380                 c >>= 1;
 381         }
 382         ldnorm(q);
 383 }
 384
 385 static void
 386 ldmagadd(ldint *a, ldint *b, ldint *q)
 387 {
 388         int i, r, s1, s2, c1, c2, co;
 389
 390         r = max(a->n, b->n) + 2;
 391         ldbits(q, r);
 392         co = 0;
 393         s1 = c1 = a->b[a->n - 1] & 1;
 394         s2 = c2 = b->b[b->n - 1] & 1;
 395         for(i = 0; i < r; i++){
 396                 c1 += s1 ^ ldget(a, i) & 1;
 397                 c2 += s2 ^ ldget(b, i) & 1;
 398                 co += (c1 & 1) + (c2 & 1);
 399                 q->b[i] = co & 1;
 400                 co >>= 1;
 401                 c1 >>= 1;
 402                 c2 >>= 1;
 403         }
 404         ldnorm(q);
 405 }
 406
 407 static void
 408 ldmagsub(ldint *a, ldint *b, ldint *q)
 409 {
 410         int i, r, s1, s2, c1, c2, co;
 411
 412         r = max(a->n, b->n) + 2;
 413         ldbits(q, r);
 414         co = 0;
 415         s1 = c1 = a->b[a->n - 1] & 1;
 416         s2 = c2 = 1 ^ b->b[b->n - 1] & 1;
 417         for(i = 0; i < r; i++){
 418                 c1 += s1 ^ ldget(a, i) & 1;
 419                 c2 += s2 ^ ldget(b, i) & 1;
 420                 co += (c1 & 1) + (c2 & 1);
 421                 q->b[i] = co & 1;
 422                 co >>= 1;
 423                 c1 >>= 1;
 424                 c2 >>= 1;
 425         }
 426         ldnorm(q);
 427 }
 428
 429 static void
 430 ldsub(ldint *a, ldint *b, ldint *q)
 431 {
 432         int r, i, x, c;
 433
 434         r = max(a->n, b->n) + 1;
 435         ldbits(q, r);
 436         c = 1;
 437         for(i = 0; i < r; i++){
 438                 c += ldget(a, i) + (1^ldget(b, i));
 439                 q->b[i] = c & 1;
 440                 c >>= 1;
 441         }
 442         ldnorm(q);
 443 }
 444
 445 static void
 446 ldmul(ldint *a, ldint *b, ldint *q)
 447 {
 448         int c1, c2, co, s1, s2, so, i, j;
 449
 450         c1 = s1 = a->b[a->n - 1] & 1;
 451         s2 = b->b[b->n - 1] & 1;
 452         so = s1 ^ s2;
 453         ldbits(q, a->n + b->n + 1);
 454         memset(q->b, 0, a->n + b->n + 1);
 455         for(i = 0; i < a->n; i++){
 456                 c1 += s1 ^ a->b[i] & 1;
 457                 if((c1 & 1) != 0){
 458                         c2 = s2;
 459                         for(j = 0; j < b->n; j++){
 460                                 c2 += (s2 ^ b->b[j] & 1) + q->b[i + j];
 461                                 q->b[i + j] = c2 & 1;
 462                                 c2 >>= 1;
 463                         }
 464                         for(; c2 > 0; j++){
 465                                 assert(i + j < q->n);
 466                                 q->b[i + j] = c2 & 1;
 467                                 c2 >>= 1;
 468                         }
 469                 }
 470                 c1 >>= 1;
 471         }
 472         co = so;
 473         for(i = 0; i < q->n; i++){
 474                 co += so ^ q->b[i];
 475                 q->b[i] = co & 1;
 476                 co >>= 1;
 477         }
 478 }
 479
 480 static void
 481 lddiv(ldint *a, ldint *b, ldint *q, ldint *r)
 482 {
 483         int n, i, j, c, s, k;
 484
 485         n = max(a->n, b->n) + 1;
 486         ldbits(q, n);
 487         ldbits(r, n);
 488         memset(r->b, 0, n);
 489         c = s = a->b[a->n-1];
 490         for(i = 0; i < n; i++){
 491                 c += s ^ ldget(a, i);
 492                 q->b[i] = c & 1;
 493                 c >>= 1;
 494         }
 495         for(i = 0; i < n; i++){
 496                 for(j = n-1; --j >= 0; )
 497                         r->b[j + 1] = r->b[j];
 498                 r->b[0] = q->b[n - 1];
 499                 for(j = n-1; --j >= 0; )
 500                         q->b[j + 1] = q->b[j];
 501                 q->b[0] = !r->b[n - 1];
 502                 c = s = r->b[n - 1] == b->b[b->n - 1];
 503                 for(j = 0; j < n; j++){
 504                         c += r->b[j] + (s ^ ldget(b, j));
 505                         r->b[j] = c & 1;
 506                         c >>= 1;
 507                 }
 508         }
 509         for(j = n-1; --j >= 0; )
 510                 q->b[j + 1] = q->b[j];
 511         q->b[0] = 1;
 512         if(r->b[r->n - 1]){
 513                 c = 0;
 514                 for(j = 0; j < n; j++){
 515                         c += 1 + q->b[j];
 516                         q->b[j] = c & 1;
 517                         c >>= 1;
 518                 }
 519                 c = s = b->b[b->n - 1];
 520                 for(j = 0; j < n; j++){
 521                         c += r->b[j] + (s ^ ldget(b, j));
 522                         r->b[j] = c & 1;
 523                         c >>= 1;
 524                 }
 525         }
 526         c = s = a->b[a->n-1] ^ b->b[b->n-1];
 527         for(j = 0; j < n; j++){
 528                 c += s ^ q->b[j];
 529                 q->b[j] = c & 1;
 530                 c >>= 1;
 531         }
 532         c = s = a->b[a->n-1];
 533         for(j = 0; j < n; j++){
 534                 c += s ^ r->b[j];
 535                 r->b[j] = c & 1;
 536                 c >>= 1;
 537         }
 538         ldnorm(q);
 539         ldnorm(r);
 540 }
 541
 542 static void
 543 lddivq(ldint *a, ldint *b, ldint *q)
 544 {
 545         ldint *r;
 546
 547         if(ldmpeq(b, mpzero)){
 548                 memset(q->b, 0, q->n);
 549                 return;
 550         }
 551         r = ldnew(0);
 552         lddiv(a, b, q, r);
 553         ldfree(r);
 554 }
 555
 556 static void
 557 mpdivq(mpint *a, mpint *b, mpint *q)
 558 {
 559         if(mpcmp(b, mpzero) == 0){
 560                 mpassign(mpzero, q);
 561                 return;
 562         }
 563         mpdiv(a, b, q, nil);
 564 }
 565
 566 static void
 567 lddivr(ldint *a, ldint *b, ldint *r)
 568 {
 569         ldint *q;
 570
 571         if(ldmpeq(b, mpzero)){
 572                 memset(r->b, 0, r->n);
 573                 return;
 574         }
 575         q = ldnew(0);
 576         lddiv(a, b, q, r);
 577         ldfree(q);
 578 }
 579
 580 static void
 581 mpdivr(mpint *a, mpint *b, mpint *r)
 582 {
 583         if(mpcmp(b, mpzero) == 0){
 584                 mpassign(mpzero, r);
 585                 return;
 586         }
 587         mpdiv(a, b, nil, r);
 588 }
 589
 590 static void
 591 ldand(ldint *a, ldint *b, ldint *q)
 592 {
 593         int r, i, x, c;
 594
 595         r = max(a->n, b->n);
 596         ldbits(q, r);
 597         for(i = 0; i < r; i++)
 598                 q->b[i] = ldget(a, i) & ldget(b, i);
 599         ldnorm(q);
 600 }
 601
 602 static void
 603 ldbic(ldint *a, ldint *b, ldint *q)
 604 {
 605         int r, i, x, c;
 606
 607         r = max(a->n, b->n);
 608         ldbits(q, r);
 609         for(i = 0; i < r; i++)
 610                 q->b[i] = ldget(a, i) & ~ldget(b, i);
 611         ldnorm(q);
 612 }
 613
 614 static void
 615 ldor(ldint *a, ldint *b, ldint *q)
 616 {
 617         int r, i, x, c;
 618
 619         r = max(a->n, b->n);
 620         ldbits(q, r);
 621         for(i = 0; i < r; i++)
 622                 q->b[i] = ldget(a, i) | ldget(b, i);
 623         ldnorm(q);
 624 }
 625
 626 static void
 627 ldxor(ldint *a, ldint *b, ldint *q)
 628 {
 629         int r, i, x, c;
 630
 631         r = max(a->n, b->n);
 632         ldbits(q, r);
 633         for(i = 0; i < r; i++)
 634                 q->b[i] = ldget(a, i) ^ ldget(b, i);
 635         ldnorm(q);
 636 }
 637
 638 static void
 639 ldleft(ldint *a, int n, ldint *b)
 640 {
 641         int i, c;
 642
 643         if(n < 0){
 644                 if(a->n <= -n){
 645                         b->n = 0;
 646                         ldnorm(b);
 647                         return;
 648                 }
 649                 c = 0;
 650                 if(a->b[a->n - 1])
 651                         for(i = 0; i < -n; i++)
 652                                 if(a->b[i]){
 653                                         c = 1;
 654                                         break;
 655                                 }
 656                 ldbits(b, a->n + n);
 657                 for(i = 0; i < a->n + n; i++){
 658                         c += a->b[i - n] & 1;
 659                         b->b[i] = c & 1;
 660                         c >>= 1;
 661                 }
 662         }else{
 663                 ldbits(b, a->n + n);
 664                 memmove(b->b + n, a->b, a->n);
 665                 memset(b->b, 0, n);
 666         }
 667         ldnorm(b);
 668 }
 669
 670 static void
 671 ldasr(ldint *a, int n, ldint *b)
 672 {
 673         if(n < 0){
 674                 ldleft(a, -n, b);
 675                 return;
 676         }
 677         if(a->n <= n){
 678                 ldbits(b, 1);
 679                 b->b[0] = a->b[a->n - 1];
 680                 return;
 681         }
 682         ldbits(b, a->n - n);
 683         memmove(b->b, a->b + n, a->n - n);
 684         ldnorm(b);
 685 }
 686
 687 static void
 688 ldtrunc(ldint *a, int n, ldint *b)
 689 {
 690         ldbits(b, n+1);
 691         b->b[n] = 0;
 692         if(a->n >= n)
 693                 memmove(b->b, a->b, n);
 694         else{
 695                 memmove(b->b, a->b, a->n);
 696                 memset(b->b + a->n, a->b[a->n - 1], n - a->n);
 697         }
 698         ldnorm(b);
 699 }
 700
 701 static void
 702 ldxtend(ldint *a, int n, ldint *b)
 703 {
 704         ldbits(b, n);
 705         if(a->n >= n)
 706                 memmove(b->b, a->b, n);
 707         else{
 708                 memmove(b->b, a->b, a->n);
 709                 memset(b->b + a->n, a->b[a->n - 1], n - a->n);
 710         }
 711         ldnorm(b);
 712 }
 713
 714 static void
 715 mpnot_(mpint *a, int, mpint *b)
 716 {
 717         mpnot(a, b);
 718 }
 719
 720 static void
 721 ldnot(ldint *a, int, ldint *b)
 722 {
 723         int i;
 724
 725         ldbits(b, a->n);
 726         for(i = 0; i < a->n; i++)
 727                 b->b[i] = a->b[i] ^ 1;
 728 }
 729
 730 enum { NTEST = 2*257 };
 731 static void
 732 testgen(int i, ldint *a)
 733 {
 734         if(i < 257)
 735                 itold(i-128, a);
 736         else
 737                 pow2told(i-385, a);
 738 }
 739
 740 typedef struct Test2 Test2;
 741 struct Test2 {
 742         char *name;
 743         void (*dut)(mpint *, mpint *, mpint *);
 744         void (*ref)(ldint *, ldint *, ldint *);
 745 };
 746
 747 typedef struct Test1i Test1i;
 748 struct Test1i {
 749         char *name;
 750         enum { NONEG = 1 } flags;
 751         void (*dut)(mpint *, int, mpint *);
 752         void (*ref)(ldint *, int, ldint *);
 753 };
 754
 755 int
 756 validate(char *name, ldint *ex, mpint *res, char *str)
 757 {
 758         int rv;
 759
 760         rv = 1;
 761         if(res->top == 0 && res->sign < 0){
 762                 fprint(2, "FAIL: %s: %s: got -0, shouldn't happen\n", name, str);
 763                 rv =0;
 764         }else if(!ldmpeq(ex, res)){
 765                 fprint(2, "FAIL: %s: %s: got %#B, expected %L\n", name, str, res, ex);
 766                 rv = 0;
 767         }
 768         free(str);
 769         return rv;
 770 }
 771
 772 int
 773 test2(Test2 *t, ldint *a, ldint *b)
 774 {
 775         ldint *c;
 776         mpint *ma, *mb, *rc;
 777         int rv;
 778
 779         c = ldnew(0);
 780         t->ref(a, b, c);
 781         ldsanity(a);
 782         ldsanity(b);
 783         ldsanity(c);
 784         ma = ldtomp(a, nil);
 785         mb = ldtomp(b, nil);
 786         rc = mptarget();
 787         t->dut(ma, mb, rc);
 788         rv = validate(t->name, c, rc, smprint("%L and %L", a, b));
 789         ldtomp(a, ma);
 790         ldtomp(b, mb);
 791         t->dut(ma, mb, mb);
 792         rv = validate(t->name, c, mb, smprint("%L and %L (aliased to result)", a, b));
 793         ldtomp(a, ma);
 794         ldtomp(b, mb);
 795         t->dut(ma, mb, ma);
 796         rv = validate(t->name, c, ma, smprint("%L (aliased to result) and %L", a, b));
 797         ldfree(c);
 798         mpfree(rc);
 799         mpfree(ma);
 800         mpfree(mb);
 801         return rv;
 802 }
 803
 804 int
 805 test2x(Test2 *t, ldint *a)
 806 {
 807         ldint *c;
 808         mpint *ma, *rc;
 809         int rv;
 810
 811         c = ldnew(0);
 812         t->ref(a, a, c);
 813         ldsanity(a);
 814         ldsanity(c);
 815         ma = ldtomp(a, nil);
 816         rc = mptarget();
 817         t->dut(ma, ma, rc);
 818         rv = validate(t->name, c, rc, smprint("%L and %L (aliased to each other)", a, a));
 819         ldtomp(a, ma);
 820         t->dut(ma, ma, ma);
 821         rv = validate(t->name, c, ma, smprint("%L and %L (both aliased to result)", a, a));
 822         ldfree(c);
 823         mpfree(rc);
 824         mpfree(ma);
 825         return rv;
 826 }
 827
 828 void
 829 run2(Test2 *t)
 830 {
 831         int i, j, ok;
 832         ldint *a, *b, *c;
 833
 834         a = ldnew(32);
 835         b = ldnew(32);
 836         c = ldnew(32);
 837         ok = 1;
 838         for(i = 0; i < NTEST; i++){
 839                 for(j = 0; j < NTEST; j++){
 840                         testgen(i, a);
 841                         testgen(j, b);
 842                         ok &= test2(t, a, b);
 843                 }
 844                 itold(i, a);
 845                 ok &= test2x(t, a);
 846         }
 847         for(i = 1; i <= 4; i++)
 848                 for(j = 1; j <= 4; j++){
 849                         ldrand(i * Dbits, a);
 850                         ldrand(j * Dbits, b);
 851                         ok &= test2(t, a, b);
 852                 }
 853         ldfree(a);
 854         ldfree(b);
 855         if(ok)
 856                 fprint(2, "%s: passed\n", t->name);
 857 }
 858
 859 Test2 tests2[] = {
 860         "mpadd", mpadd, ldadd,
 861         "mpmagadd", mpmagadd, ldmagadd,
 862         "mpsub", mpsub, ldsub,
 863         "mpmagsub", mpmagsub, ldmagsub,
 864         "mpand", mpand, ldand,
 865         "mpor", mpor, ldor,
 866         "mpbic", mpbic, ldbic,
 867         "mpxor", mpxor, ldxor,
 868         "mpmul", mpmul, ldmul,
 869         "mpdiv(q)", mpdivq, lddivq,
 870         "mpdiv(r)", mpdivr, lddivr,
 871 };
 872
 873 void
 874 all2(void)
 875 {
 876         Test2 *t;
 877
 878         for(t = tests2; t < tests2 + nelem(tests2); t++)
 879                 run2(t);
 880 }
 881
 882 int
 883 test1i(Test1i *t, ldint *a, int b)
 884 {
 885         ldint *c;
 886         mpint *ma, *rc;
 887         int rv;
 888
 889         c = ldnew(0);
 890         t->ref(a, b, c);
 891         ldsanity(a);
 892         ldsanity(c);
 893         ma = ldtomp(a, nil);
 894         rc = mptarget();
 895         t->dut(ma, b, rc);
 896         rv = validate(t->name, c, rc, smprint("%L and %d", a, b));
 897         ldtomp(a, ma);
 898         t->dut(ma, b, ma);
 899         rv = validate(t->name, c, ma, smprint("%L (aliased to result) and %d", a, b));
 900         ldfree(c);
 901         mpfree(rc);
 902         mpfree(ma);
 903         return rv;
 904 }
 905
 906 void
 907 run1i(Test1i *t)
 908 {
 909         int i, j, ok;
 910         ldint *a, *c;
 911
 912         a = ldnew(32);
 913         c = ldnew(32);
 914         ok = 1;
 915         for(i = 0; i < NTEST; i++)
 916                 for(j = (t->flags & NONEG) != 0 ? 0 : -128; j <= 128; j++){
 917                         testgen(i, a);
 918                         ok &= test1i(t, a, j);
 919                 }
 920         ldfree(a);
 921         ldfree(c);
 922         if(ok)
 923                 fprint(2, "%s: passed\n", t->name);
 924 }
 925
 926
 927 Test1i tests1i[] = {
 928         "mpleft", 0, mpleft, ldleft,
 929         "mpasr", 0, mpasr, ldasr,
 930         "mptrunc", NONEG, mptrunc, ldtrunc,
 931         "mpxtend", NONEG, mpxtend, ldxtend,
 932         "mpnot", NONEG, mpnot_, ldnot, /* hack */
 933 };
 934
 935 void
 936 all1i(void)
 937 {
 938         Test1i *t;
 939
 940         for(t = tests1i; t < tests1i + nelem(tests1i); t++)
 941                 run1i(t);
 942 }
 943
 944 void
 945 siglo(void)
 946 {
 947         int i, j, k;
 948         ldint *a;
 949         mpint *ma;
 950         int sigok, lowok0;
 951
 952         a = ldnew(32);
 953         ma = mpnew(0);
 954         sigok = 1;
 955         lowok0 = 1;
 956         for(i = 0; i < NTEST; i++){
 957                 testgen(i, a);
 958                 for(j = 0; j < a->n; j++)
 959                         if(a->b[j] != 0)
 960                                 break;
 961                 if(j == a->n) j = 0;
 962                 ldtomp(a, ma);
 963                 k = mplowbits0(ma);
 964                 if(k != j){
 965                         fprint(2, "FAIL: mplowbits0: %#B: got %d, expected %d\n", ma, k, j);
 966                         lowok0 = 0;
 967                 }
 968                 for(j = a->n - 2; j >= 0; j--)
 969                         if(a->b[j] != a->b[a->n-1])
 970                                 break;
 971                 for(k = j-1; k >= 0; k--)
 972                         if(a->b[k] != 0)
 973                                 break;
 974                 if(a->b[a->n - 1] && k < 0) j++;
 975                 j++;
 976                 ldtomp(a, ma);
 977                 k = mpsignif(ma);
 978                 if(k != j){
 979                         fprint(2, "FAIL: mpsignif: %#B: got %d, expected %d\n", ma, k, j);
 980                         sigok = 0;
 981                 }
 982         }
 983         if(sigok) fprint(2, "mpsignif: passed\n");
 984         if(lowok0) fprint(2, "mplowbits0: passed\n");
 985         ldfree(a);
 986         mpfree(ma);
 987 }
 988
 989 void
 990 cmptest(void)
 991 {
 992         int i, j, k, l;
 993         ldint *a, *b;
 994         mpint *ma, *mb;
 995         int cmpok, magcmpok;
 996
 997         a = ldnew(32);
 998         b = ldnew(32);
 999         ma = mpnew(0);
1000         mb = mpnew(0);
1001         cmpok = 1;
1002         magcmpok = 1;
1003         for(i = 0; i < NTEST; i++)
1004                 for(j = 0; j < NTEST; j++){
1005                         testgen(i, a);
1006                         testgen(j, b);
1007                         ldtomp(a, ma);
1008                         ldtomp(b, mb);
1009                         l = ldcmp(a, b);
1010                         k = mpcmp(ma, mb);
1011                         if(k < 0) k = -1;
1012                         if(k > 0) k = 1;
1013                         if(k != l){
1014                                 fprint(2, "FAIL: mpcmp: %L and %L: got %d, expected %d\n", a, b, k, l);
1015                                 cmpok = 1;
1016                         }
1017                         ldtomp(a, ma);
1018                         ldtomp(b, mb);
1019                         l = ldmagcmp(a, b);
1020                         k = mpmagcmp(ma, mb);
1021                         if(k < 0) k = -1;
1022                         if(k > 0) k = 1;
1023                         if(k != l){
1024                                 fprint(2, "FAIL: mpmagcmp: %L and %L: got %d, expected %d\n", a, b, k, l);
1025                                 magcmpok = 1;
1026                         }
1027                 }
1028         ldfree(a);
1029         ldfree(b);
1030         mpfree(ma);
1031         mpfree(mb);
1032         if(cmpok) fprint(2, "mpcmp: passed\n");
1033         if(magcmpok) fprint(2, "mpmagcmp: passed\n");
1034 }
1035
1036 void
1037 main()
1038 {
1039         fmtinstall('B', mpfmt);
1040         fmtinstall(L'β', mpdetfmt);
1041         fmtinstall('L', ldfmt);
1042         siglo();
1043         cmptest();
1044         all1i();
1045         all2();
1046 }