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