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