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