chiark - git - mdw - catacomb/blob - math/group-test.c

   1 /* -*-c-*-
   2  *
   3  * Testing group operations
   4  *
   5  * (c) 2004 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <stdarg.h>
  31
  32 #include <mLib/testrig.h>
  33
  34 #include "group.h"
  35 #include "fibrand.h"
  36 #include "ec.h"
  37 #include "ec-test.h"
  38
  39 /*----- Main code ---------------------------------------------------------*/
  40
  41 static group *getgroup(const char *p) {
  42   group *g; qd_parse qd;
  43   qd.p = p; qd.e = 0; g = group_parse(&qd);
  44   if (g && !qd_eofp(&qd)) { G_DESTROYGROUP(g); g = 0; qd.e = "junk at eof"; }
  45   if (!g) {
  46     fprintf(stderr, "bad group string `%.*s|%s': %s\n",
  47             (int)(qd.p - p), p, qd.p, qd.e);
  48     exit(1);
  49   }
  50   return (g);
  51 }
  52
  53 static ge *getge(group *g, const char *p) {
  54   ge *x = G_CREATE(g);
  55   if (group_readstring(g, x, p, 0)) {
  56     fprintf(stderr, "bad group element `%s'\n", p);
  57     exit(1);
  58   }
  59   return (x);
  60 }
  61
  62 static void show(group *g, const char *p, ge *x) {
  63   fprintf(stderr, "*** %s = ", p); group_writefile(g, x, stderr);
  64   putc('\n', stderr);
  65 }
  66
  67 static void showec(const char *p, ec *q) {
  68   fprintf(stderr, "*** %s = ", p);
  69   if (EC_ATINF(q)) fprintf(stderr, "inf\n");
  70   else {
  71     mp_writefile(q->x, stderr, 16); fputs(", ", stderr);
  72     mp_writefile(q->x, stderr, 16); putchar('\n');
  73   }
  74 }
  75
  76 static void showmp(const char *p, mp *x, int r) {
  77   fprintf(stderr, "*** %s = ", p); mp_writefile(x, stderr, r);
  78   putc('\n', stderr);
  79 }
  80
  81 static int EXECL_LIKE(0)
  82   check(const char *op, const char *gd, group *g, ge *r, ge *c, ...)
  83 {
  84   va_list ap;
  85
  86   if (G_EQ(g, r, c)) return (1);
  87   fprintf(stderr, "\n*** %s failed\n", op);
  88   fprintf(stderr, "*** group: %s\n", gd);
  89   va_start(ap, c);
  90   for (;;) {
  91     const char *p; ge *x;
  92     p = va_arg(ap, const char *); if (!p) break;
  93     x = va_arg(ap, ge *); show(g, p, x);
  94   }
  95   show(g, "expected", r);
  96   show(g, "computed", c);
  97   return (0);
  98 }
  99
 100 /*----- Actual tests ------------------------------------------------------*/
 101
 102 static int vcheck(dstr *v)
 103 {
 104   group *g = getgroup(v[0].buf);
 105   grand *gr = fibrand_create(0);
 106   const char *e = G_CHECK(g, gr);
 107   int ok = 1;
 108   gr->ops->destroy(gr);
 109   if (!e) e = "ok";
 110   G_DESTROYGROUP(g);
 111   if (strcmp(e, v[1].buf)) {
 112     ok = 0;
 113     fprintf(stderr, "*** check failed\n");
 114     fprintf(stderr, "*** group: %s\n", v[0].buf);
 115     fprintf(stderr, "*** expected: %s\n", v[1].buf);
 116     fprintf(stderr, "*** returned: %s\n", e);
 117   }
 118   assert(mparena_count(MPARENA_GLOBAL) == 0);
 119   return (ok);
 120 }
 121
 122 static int vcheckelt(dstr *v)
 123 {
 124   group *g = getgroup(v[0].buf);
 125   ge *x = getge(g, v[1].buf);
 126   int ir = *(int *)v[2].buf;
 127   int ic = group_check(g, x);
 128   int ok = 1;
 129   if (ir != ic) {
 130     ok = 0;
 131     fprintf(stderr, "*** check failed\n");
 132     fprintf(stderr, "*** group: %s\n", v[0].buf);
 133     show(g, "x", x);
 134     fprintf(stderr, "*** expected %s\n", ir ? "failure" : "success");
 135   }
 136   G_DESTROY(g, x);
 137   G_DESTROYGROUP(g);
 138   assert(mparena_count(MPARENA_GLOBAL) == 0);
 139   return (ok);
 140 }
 141
 142 static int vmul(dstr *v)
 143 {
 144   group *g = getgroup(v[0].buf);
 145   ge *x = getge(g, v[1].buf);
 146   ge *y = getge(g, v[2].buf);
 147   ge *r = getge(g, v[3].buf);
 148   ge *c = G_CREATE(g);
 149   int ok = 1;
 150   G_MUL(g, c, x, y);
 151   ok &= check("mul", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
 152   G_DESTROY(g, x); G_DESTROY(g, y); G_DESTROY(g, r); G_DESTROY(g, c);
 153   G_DESTROYGROUP(g);
 154   assert(mparena_count(MPARENA_GLOBAL) == 0);
 155   return (ok);
 156 }
 157
 158 static int vsqr(dstr *v)
 159 {
 160   group *g = getgroup(v[0].buf);
 161   ge *x = getge(g, v[1].buf);
 162   ge *r = getge(g, v[2].buf);
 163   ge *c = G_CREATE(g);
 164   int ok = 1;
 165   G_SQR(g, c, x);
 166   ok &= check("sqr", v[0].buf, g, r, c, "x", x, (char *)0);
 167   G_DESTROY(g, x); G_DESTROY(g, r); G_DESTROY(g, c);
 168   G_DESTROYGROUP(g);
 169   assert(mparena_count(MPARENA_GLOBAL) == 0);
 170   return (ok);
 171 }
 172
 173 static int vinv(dstr *v)
 174 {
 175   group *g = getgroup(v[0].buf);
 176   ge *x = getge(g, v[1].buf);
 177   ge *r = getge(g, v[2].buf);
 178   ge *c = G_CREATE(g);
 179   int ok = 1;
 180   G_INV(g, c, x);
 181   ok &= check("inv", v[0].buf, g, r, c, "x", x, (char *)0);
 182   G_DESTROY(g, x); G_DESTROY(g, r); G_DESTROY(g, c);
 183   G_DESTROYGROUP(g);
 184   assert(mparena_count(MPARENA_GLOBAL) == 0);
 185   return (ok);
 186 }
 187
 188 static int vdiv(dstr *v)
 189 {
 190   group *g = getgroup(v[0].buf);
 191   ge *x = getge(g, v[1].buf);
 192   ge *y = getge(g, v[2].buf);
 193   ge *r = getge(g, v[3].buf);
 194   ge *c = G_CREATE(g);
 195   int ok = 1;
 196   G_DIV(g, c, x, y);
 197   ok &= check("div", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
 198   group_stddiv(g, c, x, y);
 199   ok &= check("stddiv", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
 200   G_DESTROY(g, x); G_DESTROY(g, y); G_DESTROY(g, r); G_DESTROY(g, c);
 201   G_DESTROYGROUP(g);
 202   assert(mparena_count(MPARENA_GLOBAL) == 0);
 203   return (ok);
 204 }
 205
 206 static int vexp(dstr *v)
 207 {
 208   group *g = getgroup(v[0].buf);
 209   ge *x = getge(g, v[1].buf);
 210   mp *n = *(mp **)v[2].buf;
 211   ge *r = getge(g, v[3].buf);
 212   ge *c = G_CREATE(g);
 213   int ok = 1;
 214   G_EXP(g, c, x, n);
 215   if (!G_EQ(g, r, c)) {
 216     ok = 0;
 217     fprintf(stderr, "\n*** exp failed\n");
 218     fprintf(stderr, "*** group: %s\n", v[0].buf);
 219     show(g, "x", x); showmp("n", n, 10);
 220     show(g, "expected", r); show(g, "computed", c);
 221   }
 222   group_stdexp(g, c, x, n);
 223   if (!G_EQ(g, r, c)) {
 224     ok = 0;
 225     fprintf(stderr, "\n*** stdexp failed\n");
 226     fprintf(stderr, "*** group: %s\n", v[0].buf);
 227     show(g, "x", x); showmp("n", n, 10);
 228     show(g, "expected", r); show(g, "computed", c);
 229   }
 230   G_DESTROY(g, x); MP_DROP(n); G_DESTROY(g, r); G_DESTROY(g, c);
 231   G_DESTROYGROUP(g);
 232   assert(mparena_count(MPARENA_GLOBAL) == 0);
 233   return (ok);
 234 }
 235
 236 static int vmexp(size_t n, dstr *v)
 237 {
 238   group *g = getgroup(v[0].buf);
 239   ge *c, *r;
 240   group_expfactor *f = xmalloc(n * sizeof(group_expfactor));
 241   int ok = 1;
 242   size_t i;
 243   for (i = 0; i < n; i++) {
 244     f[i].base = getge(g, v[1 + 2 * i].buf);
 245     f[i].exp = *(mp **)v[2 + 2 * i].buf;
 246   }
 247   r = getge(g, v[1 + 2 * n].buf);
 248   c = G_CREATE(g);
 249   G_MEXP(g, c, f, n);
 250   if (!G_EQ(g, r, c)) {
 251     ok = 0;
 252     fprintf(stderr, "\n*** mexp failed\n");
 253     fprintf(stderr, "*** group: %s\n", v[0].buf);
 254     for (i = 0; i < n; i++) {
 255       show(g, "base", f[i].base);
 256       showmp("exp", f[i].exp, 10);
 257     }
 258     show(g, "expected", r); show(g, "computed", c);
 259   }
 260   group_stdmexp(g, c, f, n);
 261   if (!G_EQ(g, r, c)) {
 262     ok = 0;
 263     fprintf(stderr, "\n*** stdmexp failed\n");
 264     fprintf(stderr, "*** group: %s\n", v[0].buf);
 265     for (i = 0; i < n; i++) {
 266       show(g, "base", f[i].base);
 267       showmp("exp", f[i].exp, 10);
 268     }
 269     show(g, "expected", r); show(g, "computed", c);
 270   }
 271   for (i = 0; i < n; i++) { G_DESTROY(g, f[i].base); MP_DROP(f[i].exp); }
 272   G_DESTROY(g, r); G_DESTROY(g, c);
 273   G_DESTROYGROUP(g);
 274   assert(mparena_count(MPARENA_GLOBAL) == 0);
 275   return (ok);
 276 }
 277
 278 static int vmexp1(dstr *v) { return vmexp(1, v); }
 279 static int vmexp2(dstr *v) { return vmexp(2, v); }
 280 static int vmexp3(dstr *v) { return vmexp(3, v); }
 281 static int vmexp4(dstr *v) { return vmexp(4, v); }
 282
 283 static int vtoint(dstr *v)
 284 {
 285   group *g = getgroup(v[0].buf);
 286   ge *x = getge(g, v[1].buf);
 287   int ir = *(int *)v[2].buf;
 288   mp *r = *(mp **)v[3].buf;
 289   mp *c;
 290   int ic;
 291   int ok = 1;
 292   c = G_TOINT(g, MP_NEW, x);
 293   ic = c ? 0 : -1;
 294   if (ir != ic || (!ic && !MP_EQ(r, c))) {
 295     ok = 0;
 296     fprintf(stderr, "\n*** toint failed\n");
 297     fprintf(stderr, "*** group: %s\n", v[0].buf);
 298     if (ir) fprintf(stderr, "*** expected failure\n");
 299     else { show(g, "x", x); showmp("expected", r, 16);
 300     showmp("computed", c, 16); }
 301   }
 302   G_DESTROY(g, x); mp_drop(r); mp_drop(c);
 303   G_DESTROYGROUP(g);
 304   assert(mparena_count(MPARENA_GLOBAL) == 0);
 305   return (ok);
 306 }
 307
 308 static int vfromint(dstr *v)
 309 {
 310   group *g = getgroup(v[0].buf);
 311   mp *x = *(mp **)v[1].buf;
 312   int ir = *(int *)v[2].buf;
 313   ge *r = getge(g, v[3].buf);
 314   int ic;
 315   ge *c = G_CREATE(g);
 316   int ok = 1;
 317   ic = G_FROMINT(g, c, x);
 318   if (ir != ic || (!ic && !G_EQ(g, r, c))) {
 319     ok = 0;
 320     fprintf(stderr, "\n*** fromint failed\n");
 321     fprintf(stderr, "*** group: %s\n", v[0].buf);
 322     showmp("x", x, 16); if (ir) fprintf(stderr, "*** should have failed\n");
 323     else { show(g, "expected", r); show(g, "computed", c); }
 324   }
 325   MP_DROP(x); G_DESTROY(g, r); G_DESTROY(g, c);
 326   G_DESTROYGROUP(g);
 327   assert(mparena_count(MPARENA_GLOBAL) == 0);
 328   return (ok);
 329 }
 330
 331 static int vtoec(dstr *v)
 332 {
 333   group *g = getgroup(v[0].buf);
 334   ge *x = getge(g, v[1].buf);
 335   int ir = *(int *)v[2].buf;
 336   ec *r = (ec *)v[3].buf;
 337   int ic;
 338   ec c = EC_INIT;
 339   int ok = 1;
 340   ic = G_TOEC(g, &c, x);
 341   if (ir != ic || (!ic && !EC_EQ(r, &c))) {
 342     ok = 0;
 343     fprintf(stderr, "\n*** toec failed\n");
 344     fprintf(stderr, "*** group: %s\n", v[0].buf);
 345     show(g, "x", x);
 346     if (ir) fprintf(stderr, "*** should have failed\n");
 347     else { showec("expected", r); showec("computed", &c); }
 348   }
 349   G_DESTROY(g, x); EC_DESTROY(&c); EC_DESTROY(r);
 350   G_DESTROYGROUP(g);
 351   assert(mparena_count(MPARENA_GLOBAL) == 0);
 352   return (ok);
 353 }
 354
 355 static int vfromec(dstr *v)
 356 {
 357   group *g = getgroup(v[0].buf);
 358   ec *p = (ec *)v[1].buf;
 359   int ir = *(int *)v[2].buf;
 360   ge *r = getge(g, v[3].buf);
 361   int ic;
 362   ge *c = G_CREATE(g);
 363   int ok = 1;
 364   ic = G_FROMEC(g, c, p);
 365   if (ir != ic || (!ic && !G_EQ(g, r, c))) {
 366     ok = 0;
 367     fprintf(stderr, "\n*** fromec failed\n");
 368     fprintf(stderr, "*** group: %s\n", v[0].buf);
 369     showec("p", p); if (ir) fprintf(stderr, "*** should have failed\n");
 370     else { show(g, "expected", r); show(g, "computed", c); }
 371   }
 372   EC_DESTROY(p); G_DESTROY(g, r); G_DESTROY(g, c);
 373   G_DESTROYGROUP(g);
 374   assert(mparena_count(MPARENA_GLOBAL) == 0);
 375   return (ok);
 376 }
 377
 378 static int vtobuf(dstr *v)
 379 {
 380   group *g = getgroup(v[0].buf);
 381   ge *x = getge(g, v[1].buf);
 382   int ir = *(int *)v[2].buf;
 383   dstr c = DSTR_INIT;
 384   int ic;
 385   buf b;
 386   int ok = 1;
 387
 388   dstr_ensure(&c, v[3].len);
 389   buf_init(&b, c.buf, v[3].len);
 390   ic = G_TOBUF(g, &b, x);
 391   c.len = BLEN(&b);
 392   if (ic != ir || (!ic && (c.len != v[3].len ||
 393                            memcmp(c.buf, v[3].buf, c.len)))) {
 394     ok = 0;
 395     fprintf(stderr, "*** tobuf failed\n");
 396     fprintf(stderr, "*** group: %s\n", v[0].buf);
 397     show(g, "x", x);
 398     if (ir) fprintf(stderr, "*** expected failure\n");
 399     else {
 400       fprintf(stderr, "*** expected: "); type_hex.dump(&v[3], stderr);
 401       fprintf(stderr, "\n*** computed: "); type_hex.dump(&c, stderr);
 402       fputc('\n', stderr);
 403     }
 404   }
 405   G_DESTROY(g, x); dstr_destroy(&c);
 406   G_DESTROYGROUP(g);
 407   assert(mparena_count(MPARENA_GLOBAL) == 0);
 408   return (ok);
 409 }
 410
 411 static int vfrombuf(dstr *v)
 412 {
 413   group *g = getgroup(v[0].buf);
 414   int ir = *(int *)v[2].buf;
 415   ge *r = getge(g, v[3].buf);
 416   int ic;
 417   ge *c = G_CREATE(g);
 418   buf b;
 419   int ok = 1;
 420
 421   buf_init(&b, v[1].buf, v[1].len);
 422   ic = G_FROMBUF(g, &b, c);
 423   if ((ic < 0) != (ir < 0) || (ir >= 0 &&
 424                                (ir != BLEN(&b) || !G_EQ(g, r, c)))) {
 425     ok = 0;
 426     fprintf(stderr, "*** frombuf failed\n");
 427     fprintf(stderr, "*** group: %s\n", v[0].buf);
 428     fprintf(stderr, "*** input string: "); type_hex.dump(&v[1], stderr);
 429     fputc('\n', stderr);
 430     if (ir < 0) fprintf(stderr, "*** expected failure\n");
 431     else {
 432       show(g, "expected", r); show(g, "computed", c);
 433       fprintf(stderr, "*** expected used = %d\n", ir);
 434       fprintf(stderr, "*** computed used = %lu\n", (unsigned long)BLEN(&b));
 435     }
 436   }
 437   G_DESTROY(g, r); G_DESTROY(g, c);
 438   G_DESTROYGROUP(g);
 439   assert(mparena_count(MPARENA_GLOBAL) == 0);
 440   return (ok);
 441 }
 442
 443 static int vtoraw(dstr *v)
 444 {
 445   group *g = getgroup(v[0].buf);
 446   ge *x = getge(g, v[1].buf);
 447   int ir = *(int *)v[2].buf;
 448   dstr c = DSTR_INIT;
 449   int ic;
 450   buf b;
 451   int ok = 1;
 452
 453   dstr_ensure(&c, v[3].len);
 454   buf_init(&b, c.buf, v[3].len);
 455   ic = G_TORAW(g, &b, x);
 456   c.len = BLEN(&b);
 457   if (ic != ir || (!ic && (c.len != v[3].len ||
 458                            memcmp(c.buf, v[3].buf, c.len)))) {
 459     ok = 0;
 460     fprintf(stderr, "*** toraw failed\n");
 461     fprintf(stderr, "*** group: %s\n", v[0].buf);
 462     show(g, "x", x);
 463     if (ir) fprintf(stderr, "*** expected failure\n");
 464     else {
 465       fprintf(stderr, "*** expected: "); type_hex.dump(&v[3], stderr);
 466       fprintf(stderr, "\n*** computed: "); type_hex.dump(&c, stderr);
 467       fputc('\n', stderr);
 468     }
 469   }
 470   G_DESTROY(g, x); dstr_destroy(&c);
 471   G_DESTROYGROUP(g);
 472   assert(mparena_count(MPARENA_GLOBAL) == 0);
 473   return (ok);
 474 }
 475
 476 static int vfromraw(dstr *v)
 477 {
 478   group *g = getgroup(v[0].buf);
 479   int ir = *(int *)v[2].buf;
 480   ge *r = getge(g, v[3].buf);
 481   int ic;
 482   ge *c = G_CREATE(g);
 483   buf b;
 484   int ok = 1;
 485
 486   buf_init(&b, v[1].buf, v[1].len);
 487   ic = G_FROMRAW(g, &b, c);
 488   if ((ic < 0) != (ir < 0) || (ir >= 0 &&
 489                                (ir != BLEN(&b) || !G_EQ(g, r, c)))) {
 490     ok = 0;
 491     fprintf(stderr, "*** fromraw failed\n");
 492     fprintf(stderr, "*** group: %s\n", v[0].buf);
 493     fprintf(stderr, "*** input string: "); type_hex.dump(&v[1], stderr);
 494     fputc('\n', stderr);
 495     if (ir < 0) fprintf(stderr, "*** expected failure\n");
 496     else {
 497       show(g, "expected", r); show(g, "computed", c);
 498       fprintf(stderr, "*** expected used = %d\n", ir);
 499       fprintf(stderr, "*** computed used = %lu\n", (unsigned long)BLEN(&b));
 500     }
 501   }
 502   G_DESTROY(g, r); G_DESTROY(g, c);
 503   G_DESTROYGROUP(g);
 504   assert(mparena_count(MPARENA_GLOBAL) == 0);
 505   return (ok);
 506 }
 507
 508 static const test_chunk tests[] = {
 509   { "check",    vcheck,         { &type_string, &type_string } },
 510   { "checkelt", vcheckelt,      { &type_string, &type_string, &type_int } },
 511   { "mul",      vmul,           { &type_string, &type_string,
 512                                   &type_string, &type_string } },
 513   { "sqr",      vsqr,           { &type_string, &type_string,
 514                                   &type_string } },
 515   { "inv",      vinv,           { &type_string, &type_string,
 516                                   &type_string } },
 517   { "div",      vdiv,           { &type_string, &type_string,
 518                                   &type_string, &type_string } },
 519   { "exp",      vexp,           { &type_string, &type_string,
 520                                   &type_mp, &type_string } },
 521   { "mexp-1",   vmexp1,         { &type_string,
 522                                   &type_string, &type_mp,
 523                                   &type_string } },
 524   { "mexp-2",   vmexp2,         { &type_string,
 525                                   &type_string, &type_mp,
 526                                   &type_string, &type_mp,
 527                                   &type_string } },
 528   { "mexp-3",   vmexp3,         { &type_string,
 529                                   &type_string, &type_mp,
 530                                   &type_string, &type_mp,
 531                                   &type_string, &type_mp,
 532                                   &type_string } },
 533   { "mexp-4",   vmexp4,         { &type_string,
 534                                   &type_string, &type_mp,
 535                                   &type_string, &type_mp,
 536                                   &type_string, &type_mp,
 537                                   &type_string, &type_mp,
 538                                   &type_string } },
 539   { "toint",    vtoint,         { &type_string, &type_string,
 540                                   &type_int, &type_mp } },
 541   { "fromint",  vfromint,       { &type_string, &type_mp,
 542                                   &type_int, &type_string } },
 543   { "toec",     vtoec,          { &type_string, &type_string,
 544                                   &type_int, &type_ec } },
 545   { "fromec",   vfromec,        { &type_string, &type_ec,
 546                                   &type_int, &type_string } },
 547   { "tobuf",    vtobuf,         { &type_string, &type_string,
 548                                   &type_int, &type_hex } },
 549   { "frombuf",  vfrombuf,       { &type_string, &type_hex,
 550                                   &type_int, &type_string } },
 551   { "toraw",    vtoraw,         { &type_string, &type_string,
 552                                   &type_int, &type_hex } },
 553   { "fromraw",  vfromraw,       { &type_string, &type_hex,
 554                                   &type_int, &type_string } },
 555   { 0 }
 556 };
 557
 558 int main(int argc, char *argv[])
 559 {
 560   sub_init();
 561   test_run(argc, argv, tests, SRCDIR "/t/group");
 562   return (0);
 563 }
 564
 565 /*----- That's all, folks -------------------------------------------------*/