pbc/oldpbc.c

   1 // Pairing-Based Calculator.
   2 // Mainly for demonstration purposes.
   3 //
   4 // It's times like these I wish C had garbage collection.
   5
   6 #include <string.h>
   7 #include <ctype.h>
   8 #include <stdarg.h>
   9 #include <unistd.h> //for getopt
  10 #include "pbc.h"
  11 #include "pbc_z.h"
  12 #include "pbc_fp.h"
  13
  14 #include "misc/darray.h"
  15 #include "misc/symtab.h"
  16
  17 char *pbc_getline(const char *);
  18
  19 enum {
  20   t_none = 0,
  21   t_id,
  22   t_int,
  23   t_string,
  24   t_comma,
  25   t_lparen,
  26   t_rparen,
  27   t_add,
  28   t_sub,
  29   t_mul,
  30   t_div,
  31   t_set,
  32   t_pow,
  33   t_unk,
  34   t_function,
  35   t_pairing,
  36   t_element,
  37   t_field,
  38   t_err,
  39 };
  40
  41 enum {
  42   pe_expect_factor = 100,
  43   pe_expect_rparen,
  44   pe_arglist,
  45   re_varnotfound = 200,
  46   re_badlvalue,
  47   re_funnotfound,
  48   re_unimplemented,
  49   re_badargcount,
  50   re_badarg,
  51   re_fieldmismatch,
  52 };
  53
  54 static int option_echo = 0;
  55
  56 static field_t Z;
  57
  58 static int tok_type;
  59 //TODO: dynamic allocation:
  60 static char word[1024];
  61
  62 struct id_s {
  63   char *data;
  64   int alloc;
  65 };
  66 typedef struct id_s *id_ptr;
  67
  68 id_ptr id_new(char *id) {
  69   id_ptr res = pbc_malloc(sizeof(struct id_s));
  70   res->alloc = strlen(id) + 1;
  71   res->data = pbc_malloc(res->alloc);
  72   strcpy(res->data, id);
  73   return res;
  74 }
  75
  76 void id_delete(id_ptr id) {
  77   pbc_free(id->data);
  78   pbc_free(id);
  79 }
  80
  81 struct tree_s {
  82   int type;
  83   void *data;
  84   darray_t child;
  85 };
  86 typedef struct tree_s *tree_ptr;
  87
  88 tree_ptr tree_new(int type, void *data) {
  89   tree_ptr res = pbc_malloc(sizeof(struct tree_s));
  90   res->type = type;
  91   res->data = data;
  92   darray_init(res->child);
  93   return res;
  94 }
  95
  96 static void delete_child(void *p) {
  97   tree_delete(p);
  98 }
  99
 100 void tree_delete(tree_ptr t) {
 101   darray_forall(t->child, delete_child);
 102   darray_clear(t->child);
 103   switch(t->type) {
 104     case t_id:
 105     case t_string:
 106     case t_function:
 107     case t_int:
 108       id_delete(t->data);
 109       break;
 110   }
 111   pbc_free(t);
 112 }
 113
 114 static char *currentline;
 115 static char *lexcp;
 116
 117
 118 static void lex(void) {
 119   char c;
 120   if (!lexcp) {
 121     tok_type = t_none;
 122     return;
 123   }
 124   c = *lexcp++;
 125   skipwhitespace:
 126   for (;;) {
 127     if (!strchr(" \t\r\n", c)) break;
 128     if (!c) {
 129       tok_type = t_none;
 130       return;
 131     }
 132     c = *lexcp++;
 133   }
 134
 135   //comments start with '#' and end at a newline
 136   if (c == '#') {
 137     for (;;) {
 138       c = *lexcp++;
 139       if (!c) {
 140         tok_type = t_none;
 141         return;
 142       }
 143       if (c == '\n') break;
 144     }
 145     goto skipwhitespace;
 146   }
 147
 148   //strings
 149   if (c == '"') {
 150     tok_type = t_string;
 151     int i = 0;
 152     for (;;) {
 153       c = *lexcp++;
 154       if (!c) {
 155         //string continues on next line
 156         word[i++] = '\n';
 157         pbc_free(currentline);
 158         currentline = pbc_getline(NULL);
 159         if (!currentline) break;
 160         if (option_echo) puts(currentline);
 161         lexcp = currentline;
 162         c = *lexcp++;
 163       }
 164       if (c == '"') {
 165         break;
 166       }
 167       word[i++] = c;
 168     }
 169     word[i] = '\0';
 170     return;
 171   }
 172
 173   if (isdigit(c)) {
 174     tok_type = t_int;
 175     word[0] = c;
 176
 177     int i = 1;
 178     for (;;) {
 179       c = *lexcp++;
 180       if (isdigit(c)) {
 181         word[i++] = c;
 182       } else {
 183         word[i] = '\0';
 184         lexcp--;
 185         break;
 186       }
 187     }
 188     return;
 189   }
 190
 191   if (isalpha(c) || c == '_') {
 192     tok_type = t_id;
 193     word[0] = c;
 194
 195     int i = 1;
 196     for (;;) {
 197       c = *lexcp++;
 198       if (isalnum(c) || c == '_') {
 199         word[i++] = c;
 200       } else {
 201         word[i] = '\0';
 202         lexcp--;
 203         break;
 204       }
 205     }
 206     return;
 207   }
 208
 209   switch(c) {
 210     case ',':
 211       tok_type = t_comma;
 212       break;
 213     case '=':
 214       tok_type = t_set;
 215       break;
 216     case '^':
 217       tok_type = t_pow;
 218       break;
 219     case '*':
 220       tok_type = t_mul;
 221       break;
 222     case '/':
 223       tok_type = t_div;
 224       break;
 225     case '+':
 226       tok_type = t_add;
 227       break;
 228     case '-':
 229       tok_type = t_sub;
 230       break;
 231     case '(':
 232       tok_type = t_lparen;
 233       break;
 234     case ')':
 235       tok_type = t_rparen;
 236       break;
 237     default:
 238       tok_type = t_unk;
 239       break;
 240   }
 241 }
 242
 243 static int lastparseerror;
 244 static void setparseerror(int i) {
 245   lastparseerror = i;
 246 }
 247
 248 static tree_ptr parsesetexpr(void);
 249
 250 static tree_ptr parseexprlist(tree_ptr t) {
 251   tree_ptr c;
 252   lex(); // expect lparen
 253   if (tok_type == t_rparen) {
 254     lex();
 255     return t;
 256   }
 257   c = parsesetexpr();
 258   if (!c) return NULL;
 259   darray_append(t->child, c);
 260   for (;;) {
 261     if (tok_type == t_rparen) {
 262       lex();
 263       return t;
 264     }
 265     if (tok_type != t_comma) {
 266       setparseerror(pe_arglist);
 267       return NULL;
 268     }
 269     lex(); //expect comma
 270     c = parsesetexpr();
 271     if (!c) return NULL;
 272     darray_append(t->child, c);
 273   }
 274 }
 275
 276 static tree_ptr parseprimitive(void) {
 277   tree_ptr t;
 278   switch(tok_type) {
 279     id_ptr id;
 280     case t_id:
 281       id = id_new(word);
 282       lex();
 283       if (tok_type == t_lparen) {
 284         if (parseexprlist(t = tree_new(t_function, id))) {
 285           return t;
 286         }
 287         tree_delete(t);
 288         return NULL;
 289       } else {
 290         return tree_new(t_id, id);
 291       }
 292     case t_string:
 293       lex();
 294       return tree_new(t_string, id_new(word));
 295     case t_lparen:
 296       lex();
 297       t = parsesetexpr();
 298       if (!t) return NULL;
 299       if (tok_type != t_rparen) {
 300         tree_delete(t);
 301         setparseerror(pe_expect_rparen);
 302         return NULL;
 303       }
 304       lex();
 305       return t;
 306     case t_int:
 307       id = id_new(word);
 308       lex();
 309       return tree_new(t_int, id);
 310     default:
 311       setparseerror(pe_expect_factor);
 312       return NULL;
 313   }
 314 }
 315
 316 static tree_ptr parsepow(void) {
 317   tree_ptr t1;
 318   t1 = parseprimitive();
 319   if (tok_type == t_pow) {
 320     tree_ptr t2, res;
 321     lex();
 322     t2 = parseprimitive();
 323     if (!t2) {
 324       tree_delete(t1);
 325       return NULL;
 326     }
 327     res = tree_new(t_function, id_new("pow"));
 328     darray_append(res->child, t1);
 329     darray_append(res->child, t2);
 330     return res;
 331   }
 332   return t1;
 333 }
 334
 335 static tree_ptr parsefactor(void) {
 336   tree_ptr t;
 337   if (tok_type == t_sub) {
 338     lex();
 339     t = parsefactor();
 340     if (!t) return NULL;
 341     tree_ptr t1 = tree_new(t_function, id_new("neg"));
 342     darray_append(t1->child, t);
 343     return t1;
 344   }
 345
 346   t = parsepow();
 347   return t;
 348 }
 349
 350 static tree_ptr parseterm(void) {
 351   tree_ptr t1, t2, res;
 352   res = parsefactor();
 353   if (!res) return NULL;
 354   for (;;) {
 355     switch(tok_type) {
 356       case t_mul:
 357         lex();
 358         t2 = parsefactor();
 359         if (!t2) {
 360           tree_delete(res);
 361           return NULL;
 362         }
 363         t1 = tree_new(t_function, id_new("mul"));
 364         darray_append(t1->child, res);
 365         darray_append(t1->child, t2);
 366         res = t1;
 367         break;
 368       case t_div:
 369         lex();
 370         t2 = parsefactor();
 371         if (!t2) {
 372           tree_delete(res);
 373           return NULL;
 374         }
 375         t1 = tree_new(t_function, id_new("div"));
 376         darray_append(t1->child, res);
 377         darray_append(t1->child, t2);
 378         res = t1;
 379         break;
 380       default:
 381         return res;
 382     }
 383   }
 384 }
 385
 386 static tree_ptr parseexpr(void) {
 387   tree_ptr t1, t2, res;
 388   res = parseterm();
 389   if (!res) {
 390     return NULL;
 391   }
 392   for (;;) {
 393     switch(tok_type) {
 394       case t_add:
 395         lex();
 396         t2 = parseterm();
 397         if (!t2) {
 398           tree_delete(res);
 399           return NULL;
 400         }
 401         //t1 = tree_new(t_add, NULL);
 402         t1 = tree_new(t_function, id_new("add"));
 403         darray_append(t1->child, res);
 404         darray_append(t1->child, t2);
 405         res = t1;
 406         break;
 407       case t_sub:
 408         lex();
 409         t2 = parseterm();
 410         if (!t2) {
 411           tree_delete(res);
 412           return NULL;
 413         }
 414         //t1 = tree_new(t_sub, NULL);
 415         t1 = tree_new(t_function, id_new("sub"));
 416         darray_append(t1->child, res);
 417         darray_append(t1->child, t2);
 418         res = t1;
 419         break;
 420       default:
 421         return res;
 422     }
 423   }
 424 }
 425
 426 static tree_ptr parsesetexpr(void) {
 427   tree_ptr t1, t2, res;
 428   t1 = parseexpr();
 429   if (!t1) return NULL;
 430   if (tok_type == t_set) {
 431     lex();
 432     t2 = parsesetexpr();
 433     if (!t2) {
 434       tree_delete(t1);
 435       return NULL;
 436     }
 437     res = tree_new(t_set, NULL);
 438     darray_append(res->child, t1);
 439     darray_append(res->child, t2);
 440     return res;
 441   }
 442   return t1;
 443 }
 444
 445 static void print_tree(tree_ptr t) {
 446   id_ptr id;
 447   int i;
 448   if (!t) {
 449     printf("NULL");
 450     return;
 451   }
 452   switch (t->type) {
 453     case t_set:
 454       print_tree(t->child->item[0]);
 455       printf(" = ");
 456       print_tree(t->child->item[1]);
 457       break;
 458     case t_id:
 459       id = t->data;
 460       printf("%s", id->data);
 461       break;
 462     case t_function:
 463       id = t->data;
 464       printf("%s(", id->data);
 465       for (i=0; i<t->child->count; i++) {
 466         print_tree(t->child->item[i]);
 467         if (i < t->child->count - 1) printf(", ");
 468       }
 469       printf(")");
 470       break;
 471     default:
 472       printf("?!?");
 473       break;
 474   }
 475 }
 476
 477 static symtab_t var;
 478 static symtab_t builtin;
 479
 480 struct val_s {
 481   int type;
 482   void *data;
 483 };
 484 typedef struct val_s *val_ptr;
 485
 486 static int lastruntimeerror;
 487 static val_ptr newruntimeerror(int i) {
 488   val_ptr res = pbc_malloc(sizeof(struct val_s));
 489   lastruntimeerror = i;
 490   res->type = t_err;
 491   res->data = int_to_voidp(i);
 492   return res;
 493 }
 494
 495 val_ptr val_new(int type, void *data) {
 496   val_ptr res = pbc_malloc(sizeof(struct val_s));
 497   res->type = type;
 498   res->data = data;
 499   return res;
 500 }
 501
 502 static void val_print(val_ptr v) {
 503   pairing_ptr pairing;
 504   field_ptr field;
 505   element_ptr e;
 506   switch (v->type) {
 507     case t_element:
 508       e = v->data;
 509       element_out_str(stdout, 0, e);
 510       printf("\n");
 511       break;
 512     case t_pairing:
 513       pairing = v->data;
 514       printf("pairing: G1bits=%d G2bits=%d GTbits=%d\n",
 515           pairing_length_in_bytes_x_only_G1(pairing) * 8,
 516           pairing_length_in_bytes_x_only_G2(pairing) * 8,
 517           pairing_length_in_bytes_GT(pairing) * 8);
 518       break;
 519     case t_field:
 520       field = v->data;
 521       field_out_info(stdout, field);
 522       break;
 523     case t_string:
 524       printf("%s", (char *) v->data);
 525       break;
 526     default:
 527       printf("val type %d unknown\n", v->type);
 528       break;
 529   }
 530 }
 531
 532 val_ptr val_copy(val_ptr v) {
 533   val_ptr res = pbc_malloc(sizeof(struct val_s));
 534   res->type = v->type;
 535   if (v->type == t_element) {
 536     //current policy: always clear elements, always copy elements
 537     res->data = pbc_malloc(sizeof(element_t));
 538     element_ptr e = v->data;
 539     element_init(res->data, e->field);
 540     element_set(res->data, e);
 541   } else if (v->type == t_string) {
 542     res->data = pbc_strdup(v->data);
 543   } else {
 544     res->data = v->data;
 545   }
 546
 547   return res;
 548 }
 549
 550 void val_delete(val_ptr v) {
 551   switch(v->type) {
 552     case t_element:
 553       //current policy: always clear elements, always copy elements
 554       element_clear(v->data);
 555       pbc_free(v->data);
 556       break;
 557     case t_string:
 558       pbc_free(v->data);
 559       break;
 560     case t_err:
 561       break;
 562     case t_pairing:
 563       break;
 564     case t_field:
 565       break;
 566     default:
 567       printf("val_delete: case %d not handled: memory leak\n", v->type);
 568       break;
 569   }
 570   pbc_free(v);
 571 }
 572
 573 struct fun_s {
 574   val_ptr (*f)(darray_ptr);
 575   int arity;
 576   int type[32]; //TODO: replace with darray? who needs more than 32 args?
 577 };
 578
 579 typedef val_ptr (*fun)(darray_ptr);
 580
 581 static val_ptr check_arg(darray_ptr arg, int n, ...) {
 582   va_list ap;
 583   int i;
 584   val_ptr res = NULL;
 585
 586   va_start(ap, n);
 587   if (arg->count != n) {
 588     printf("expect %d argument(s)\n", n);
 589     res = newruntimeerror(re_badargcount);
 590   } else for (i=0; i<n; i++) {
 591     int t = va_arg(ap, int);
 592     val_ptr vp = arg->item[i];
 593     if (vp->type != t) {
 594       printf("arg not type %d\n", t);
 595       return newruntimeerror(re_badarg);
 596       break;
 597     }
 598   }
 599
 600   va_end(ap);
 601   return res;
 602 }
 603
 604 static val_ptr f_pairing_get_group(
 605     field_ptr (*get_group)(pairing_ptr p), darray_ptr arg) {
 606   val_ptr res;
 607   res = check_arg(arg, 1, t_pairing);
 608   if (res) return res;
 609   val_ptr a0 = arg->item[0];
 610   pairing_ptr pairing = a0->data;
 611   res = val_new(t_field, get_group(pairing));
 612   return res;
 613 }
 614
 615 static val_ptr f_pairing_G1(darray_ptr arg) {
 616   field_ptr getG1(pairing_ptr p) { return p->G1; }
 617   return f_pairing_get_group(getG1, arg);
 618 }
 619
 620 static val_ptr f_pairing_G2(darray_ptr arg) {
 621   field_ptr getG2(pairing_ptr p) { return p->G2; }
 622   return f_pairing_get_group(getG2, arg);
 623 }
 624
 625 static val_ptr f_pairing_GT(darray_ptr arg) {
 626   field_ptr getGT(pairing_ptr p) { return p->GT; }
 627   return f_pairing_get_group(getGT, arg);
 628 }
 629
 630 static val_ptr f_pairing_Zr(darray_ptr arg) {
 631   field_ptr getZr(pairing_ptr p) { return p->Zr; }
 632   return f_pairing_get_group(getZr, arg);
 633 }
 634
 635 static val_ptr f_random(darray_ptr arg) {
 636   val_ptr res;
 637   res = check_arg(arg, 1, t_field);
 638   if (res) return res;
 639   val_ptr a0 = arg->item[0];
 640   field_ptr f = a0->data;
 641   element_ptr e = pbc_malloc(sizeof(element_t));
 642   element_init(e, f);
 643   element_random(e);
 644   res = val_new(t_element, e);
 645   return res;
 646 }
 647
 648 static val_ptr f_order(darray_ptr arg) {
 649   val_ptr res;
 650   res = check_arg(arg, 1, t_field);
 651   if (res) return res;
 652   val_ptr a0 = arg->item[0];
 653   field_ptr f = a0->data;
 654
 655   element_ptr e = pbc_malloc(sizeof(element_t));
 656   element_init(e, Z);
 657   element_set_mpz(e, f->order);
 658   res = val_new(t_element, e);
 659   return res;
 660 }
 661
 662 static val_ptr f_unary(
 663     void (*unary)(element_ptr, element_ptr), darray_ptr arg) {
 664   val_ptr res;
 665   res = check_arg(arg, 1, t_element);
 666   if (res) return res;
 667   val_ptr a0 = arg->item[0];
 668   element_ptr e0 = a0->data;
 669   element_ptr e = pbc_malloc(sizeof(element_t));
 670   element_init(e, e0->field);
 671   unary(e, e0);
 672   res = val_new(t_element, e);
 673   return res;
 674 }
 675
 676 static val_ptr f_bin_op(
 677     void (*binop)(element_ptr, element_ptr, element_ptr),
 678     darray_ptr arg) {
 679   val_ptr res;
 680   res = check_arg(arg, 2, t_element, t_element);
 681   if (res) return res;
 682   val_ptr a0 = arg->item[0];
 683   val_ptr a1 = arg->item[1];
 684   element_ptr e0 = a0->data;
 685   element_ptr e1 = a1->data;
 686   if (e0->field != e1->field) {
 687     printf("field mismatch!\n");
 688     return newruntimeerror(re_fieldmismatch);
 689   }
 690   element_ptr e = pbc_malloc(sizeof(element_t));
 691   element_init(e, e0->field);
 692   binop(e, e0, e1);
 693   res = val_new(t_element, e);
 694   return res;
 695 }
 696
 697
 698 static val_ptr f_add(darray_ptr arg) {
 699   return f_bin_op(element_add, arg);
 700 }
 701
 702 static val_ptr f_mul(darray_ptr arg) {
 703   return f_bin_op(element_mul, arg);
 704 }
 705
 706 static val_ptr f_sub(darray_ptr arg) {
 707   return f_bin_op(element_sub, arg);
 708 }
 709
 710 static val_ptr f_div(darray_ptr arg) {
 711   return f_bin_op(element_div, arg);
 712 }
 713
 714 static val_ptr f_inv(darray_ptr arg) {
 715   return f_unary(element_invert, arg);
 716 }
 717
 718 static val_ptr f_neg(darray_ptr arg) {
 719   return f_unary(element_neg, arg);
 720 }
 721
 722 static val_ptr f_pow(darray_ptr arg) {
 723   val_ptr res;
 724   res = check_arg(arg, 2, t_element, t_element);
 725   if (res) return res;
 726   val_ptr a0 = arg->item[0];
 727   val_ptr a1 = arg->item[1];
 728   element_ptr e0 = a0->data;
 729   element_ptr e1 = a1->data;
 730   element_ptr e = pbc_malloc(sizeof(element_t));
 731   mpz_t z;
 732   mpz_init(z);
 733   element_to_mpz(z, e1);
 734   element_init(e, e0->field);
 735   element_pow_mpz(e, e0, z);
 736   res = val_new(t_element, e);
 737   mpz_clear(z);
 738   return res;
 739 }
 740
 741 static pairing_ptr current_pairing;
 742 static val_ptr f_pairing(darray_ptr arg) {
 743   val_ptr res;
 744   if (arg->count != 2) {
 745     printf("expect two arguments\n");
 746     return newruntimeerror(re_badargcount);
 747   }
 748   val_ptr a0 = arg->item[0];
 749   val_ptr a1 = arg->item[1];
 750   if (a0->type != t_element) {
 751     printf("arg 1 not element!\n");
 752     return newruntimeerror(re_badarg);
 753   }
 754   if (a1->type != t_element) {
 755     printf("arg 2 not element!\n");
 756     return newruntimeerror(re_badarg);
 757   }
 758   pairing_ptr p;
 759   element_ptr e0 = a0->data;
 760   element_ptr e1 = a1->data;
 761   p = e0->field->pairing;
 762   if (e0->field != p->G1) {
 763     printf("arg 1 not from G1!\n");
 764     return newruntimeerror(re_badarg);
 765   }
 766   if (e1->field != p->G2) {
 767     printf("arg 2 not from G2!\n");
 768     return newruntimeerror(re_badarg);
 769   }
 770   element_ptr e = pbc_malloc(sizeof(element_t));
 771   element_init(e, p->GT);
 772   pairing_apply(e, e0, e1, p);
 773   res = val_new(t_element, e);
 774   return res;
 775 }
 776
 777 static val_ptr execute_tree(tree_ptr t) {
 778   darray_t arg;
 779   id_ptr id;
 780   fun fn;
 781   int i;
 782   val_ptr res, v;
 783   tree_ptr t1, t2;
 784
 785   switch (t->type) {
 786     case t_id:
 787       id = t->data;
 788       v = symtab_at(var, id->data);
 789       if (!v) {
 790         return newruntimeerror(re_varnotfound);
 791       }
 792       return val_copy(v);
 793     case t_set:
 794       t1 = t->child->item[0];
 795       if (t1->type != t_id) {
 796         return newruntimeerror(re_badlvalue);
 797       }
 798       t2 = t->child->item[1];
 799       v = execute_tree(t2);
 800       if (v->type == t_err) return v;
 801       id = t1->data;
 802       // clear what's there first
 803       if ((res = symtab_at(var, id->data))) {
 804         val_delete(res);
 805       }
 806       symtab_put(var, v, id->data);
 807       v = symtab_at(var, id->data);
 808       return val_copy(v);
 809     case t_function:
 810       id = t->data;
 811       fn = symtab_at(builtin, id->data);
 812       if (!fn) {
 813         return newruntimeerror(re_funnotfound);
 814       }
 815       darray_init(arg);
 816       for (i=0; i<t->child->count; i++) {
 817         v = execute_tree(t->child->item[i]);
 818         if (v->type == t_err) {
 819           darray_forall(arg, (void (*)(void *)) val_delete);
 820           return v;
 821         }
 822         darray_append(arg, v);
 823       }
 824       res = fn(arg);
 825       for (i=0; i<arg->count; i++) {
 826         val_delete(arg->item[i]);
 827       }
 828       darray_clear(arg);
 829       return res;
 830     case t_int:
 831       id = t->data;
 832       char *cp;
 833       mpz_t z;
 834       mpz_init(z);
 835       for (cp = id->data; *cp; cp++) {
 836         mpz_mul_ui(z, z, 10);
 837         mpz_add_ui(z, z, *cp - '0');
 838       }
 839       element_ptr e = pbc_malloc(sizeof(element_t));
 840       element_init(e, Z);
 841       element_set_mpz(e, z);
 842       mpz_clear(z);
 843       return val_new(t_element, e);
 844     case t_string:
 845       id = t->data;
 846       return val_new(t_string, pbc_strdup(id->data));
 847     default:
 848       return newruntimeerror(re_unimplemented);
 849   }
 850 }
 851
 852 static void parseline(void) {
 853   val_ptr v;
 854
 855   tree_ptr t;
 856   lex();
 857   if (tok_type == t_none) return;
 858   t = parsesetexpr();
 859   if (0) {
 860     print_tree(t);
 861     printf("\n");
 862   }
 863   if (t) {
 864     v = execute_tree(t);
 865     if (v) {
 866       if (v->type == t_err) {
 867         printf("runtime error (error code = %d)\n", lastruntimeerror);
 868       } else {
 869         if (t->type != t_set) val_print(v);
 870       }
 871       val_delete(v);
 872     }
 873     tree_delete(t);
 874   } else {
 875     printf("parse error (error code = %d)\n", lastparseerror);
 876   }
 877 }
 878
 879 static char *aparam =
 880 "type a\n"
 881 "q 8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791\n"
 882 "h 12016012264891146079388821366740534204802954401251311822919615131047207289359704531102844802183906537786776\n"
 883 "r 730750818665451621361119245571504901405976559617\n"
 884 "exp2 159\n"
 885 "exp1 107\n"
 886 "sign1 1\n"
 887 "sign0 1\n";
 888
 889 static char *dparam =
 890 "type d\n"
 891 "q 625852803282871856053922297323874661378036491717\n"
 892 "n 625852803282871856053923088432465995634661283063\n"
 893 "h 3\n"
 894 "r 208617601094290618684641029477488665211553761021\n"
 895 "a 581595782028432961150765424293919699975513269268\n"
 896 "b 517921465817243828776542439081147840953753552322\n"
 897 "k 6\n"
 898 "nk 60094290356408407130984161127310078516360031868417968262992864809623507269833854678414046779817844853757026858774966331434198257512457993293271849043664655146443229029069463392046837830267994222789160047337432075266619082657640364986415435746294498140589844832666082434658532589211525696\n"
 899 "hk 1380801711862212484403205699005242141541629761433899149236405232528956996854655261075303661691995273080620762287276051361446528504633283152278831183711301329765591450680250000592437612973269056\n"
 900 "coeff0 472731500571015189154958232321864199355792223347\n"
 901 "coeff1 352243926696145937581894994871017455453604730246\n"
 902 "coeff2 289113341693870057212775990719504267185772707305\n"
 903 "nqr 431211441436589568382088865288592347194866189652\n";
 904
 905 static char *eparam =
 906 "type e\n"
 907 "q 7245986106510086080714203333362098431608853335867425877960916928496629182991629664903654100214900946450053872786629995869445693724001299041657434948257845644905153122838458864000479326695430719258600053239930483226650953770354174712511646273516974069245462534034085895319225452125649979474047163305307830001\n"
 908 "r 730750862221594424981965739670091261094297337857\n"
 909 "h 13569343110918781839835249021482970252603216587988030044836106948825516930173270978617489032334001006615524543925753725725046733884363846960470444404747241287743773746682188521738728797153760275116924829183670000\n"
 910 "a 7130970454025799000067946137594446075551569949583815943390108723282396973737794273397246892274981883807989525599540630855644968426794929215599380425269625872763801485968007136000471718335185787206876242871042697778608875139078711621836858237429403052273312335081163896980825048123655535355411494046493419999\n"
 911 "b 7169309004853894693616698536183663527570664411678352588247044791687141043489072737232715961588288238022010974661903752526911876859197052490952065266265699130144252031591491045333807587788600764557450846327338626261289568016170532652061787582791926724597362401398804563093625182790987016728290050466098223333\n"
 912 "exp2 159\n"
 913 "exp1 135\n"
 914 "sign1 1\n"
 915 "sign0 1\n";
 916
 917 static char *fparam =
 918 "type f\n"
 919 "q 205523667896953300194896352429254920972540065223\n"
 920 "r 205523667896953300194895899082072403858390252929\n"
 921 "b 40218105156867728698573668525883168222119515413\n"
 922 "beta 115334401956802802075595682801335644058796914268\n"
 923 "alpha0 191079354656274778837764015557338301375963168470\n"
 924 "alpha1 71445317903696340296199556072836940741717506375\n";
 925
 926 static char *gparam =
 927 "type g\n"
 928 "q 503189899097385532598615948567975432740967203\n"
 929 "n 503189899097385532598571084778608176410973351\n"
 930 "h 1\n"
 931 "r 503189899097385532598571084778608176410973351\n"
 932 "a 465197998498440909244782433627180757481058321\n"
 933 "b 463074517126110479409374670871346701448503064\n"
 934 "k 10\n"
 935 "nk 1040684643531490707494989587381629956832530311976146077888095795458709511789670022388326295177424065807612879371896982185473788988016190582073591316127396374860265835641044035656044524481121528846249501655527462202999638159773731830375673076317719519977183373353791119388388468745670818193868532404392452816602538968163226713846951514831917487400267590451867746120591750902040267826351982737642689423713163967384383105678367875981348397359466338807\n"
 936 "hk 4110127713690841149713310614420858884651261781185442551927080083178682965171097172366598236129731931693425629387502221804555636704708008882811353539555915064049685663790355716130262332064327767695339422323460458479884756000782939428852120522712008037615051139080628734566850259704397643028017435446110322024094259858170303605703280329322675124728639532674407\n"
 937 "coeff0 67343110967802947677845897216565803152319250\n"
 938 "coeff1 115936772834120270862756636148166314916823221\n"
 939 "coeff2 87387877425076080433559927080662339215696505\n"
 940 "coeff3 433223145899090928132052677121692683015058909\n"
 941 "coeff4 405367866213598664862417230702935310328613596\n"
 942 "nqr 22204504160560785687198080413579021865783099\n";
 943
 944 static pairing_t pairing_A, pairing_D, pairing_E, pairing_F, pairing_G;
 945
 946 static void set_pairing_groups(pairing_ptr p) {
 947   symtab_put(var, val_new(t_field, p->G1), "G1");
 948   symtab_put(var, val_new(t_field, p->G2), "G2");
 949   symtab_put(var, val_new(t_field, p->GT), "GT");
 950   symtab_put(var, val_new(t_field, p->Zr), "Zr");
 951   symtab_put(var, val_new(t_pairing, p), "current_pairing");
 952   current_pairing = p;
 953 }
 954
 955 static val_ptr f_init_pairing(darray_ptr arg) {
 956   val_ptr res;
 957
 958   res = check_arg(arg, 1, t_pairing);
 959   if (res) return res;
 960
 961   val_ptr a0 = arg->item[0];
 962   pairing_ptr p = a0->data;
 963   set_pairing_groups(p);
 964   return NULL;
 965 }
 966
 967 static val_ptr f_nextprime(darray_ptr arg) {
 968   mpz_t p;
 969   val_ptr res;
 970
 971   res = check_arg(arg, 1, t_element);
 972   if (res) return res;
 973   val_ptr a0 = arg->item[0];
 974   element_ptr e0 = a0->data;
 975   if (e0->field != Z) {
 976     printf("arg not integer!\n");
 977     return newruntimeerror(re_badarg);
 978   }
 979   element_ptr e = pbc_malloc(sizeof(element_t));
 980   element_init(e, Z);
 981   mpz_init(p);
 982   element_to_mpz(p, e0);
 983   mpz_nextprime(p, p);
 984   element_set_mpz(e, p);
 985   res = val_new(t_element, e);
 986   mpz_clear(p);
 987   return res;
 988 }
 989
 990 static val_ptr f_brute_force_dlog(darray_ptr arg) {
 991   val_ptr res;
 992   res = check_arg(arg, 2, t_element, t_element);
 993   if (res) return res;
 994   val_ptr a0 = arg->item[0];
 995   val_ptr a1 = arg->item[1];
 996   element_ptr e0 = a0->data;
 997   element_ptr e1 = a1->data;
 998   if (e0->field != e1->field) {
 999     printf("arg field mismatch!\n");
1000     return newruntimeerror(re_badarg);
1001   }
1002   element_ptr e = pbc_malloc(sizeof(element_t));
1003   element_init(e, Z);
1004   element_dlog_brute_force(e, e0, e1);
1005   res = val_new(t_element, e);
1006   return res;
1007 }
1008 static val_ptr f_pollard_rho(darray_ptr arg) {
1009   val_ptr res;
1010   res = check_arg(arg, 3, t_element, t_element, t_field);
1011   if (res) return res;
1012   val_ptr a0 = arg->item[0];
1013   val_ptr a1 = arg->item[1];
1014   val_ptr a2 = arg->item[2];
1015   element_ptr e0 = a0->data;
1016   element_ptr e1 = a1->data;
1017   if (e0->field != e1->field) {
1018     printf("arg field mismatch!\n");
1019     return newruntimeerror(re_badarg);
1020   }
1021   field_ptr f = a2->data;
1022   element_ptr e = pbc_malloc(sizeof(element_t));
1023   element_init(e, f);
1024   element_dlog_pollard_rho(e, e0, e1);
1025   res = val_new(t_element, e);
1026   return res;
1027 }
1028
1029 static val_ptr f_zz(darray_ptr arg) {
1030   mpz_t p;
1031   val_ptr res;
1032   res = check_arg(arg, 1, t_element);
1033   if (res) return res;
1034   val_ptr a0 = arg->item[0];
1035   element_ptr e0 = a0->data;
1036   if (e0->field != Z) {
1037     printf("arg not integer!\n");
1038     return newruntimeerror(re_badarg);
1039   }
1040   field_ptr f = pbc_malloc(sizeof(field_t));
1041   mpz_init(p);
1042   element_to_mpz(p, e0);
1043   field_init_fp(f, p);
1044   res = val_new(t_field, f);
1045   mpz_clear(p);
1046   return res;
1047 }
1048
1049 static val_ptr f_gen_A(darray_ptr arg) {
1050   mpz_t rbits, qbits;
1051   pairing_ptr p;
1052   val_ptr res;
1053   res = check_arg(arg, 2, t_element, t_element);
1054   if (res) return res;
1055   val_ptr a0 = arg->item[0];
1056   val_ptr a1 = arg->item[1];
1057   element_ptr e0 = a0->data;
1058   if (e0->field != Z) {
1059     printf("arg not integer!\n");
1060     return newruntimeerror(re_badarg);
1061   }
1062   element_ptr e1 = a1->data;
1063   if (e1->field != Z) {
1064     printf("arg not integer!\n");
1065     return newruntimeerror(re_badarg);
1066   }
1067   mpz_init(rbits);
1068   mpz_init(qbits);
1069   element_to_mpz(rbits, e0);
1070   element_to_mpz(qbits, e1);
1071   //TODO: check rbits and qbits aren't too big
1072   pbc_param_t param;
1073   pbc_param_init_a_gen(param, mpz_get_ui(rbits), mpz_get_ui(qbits));
1074   p = pbc_malloc(sizeof(pairing_t));
1075   pairing_init_pbc_param(p, param);
1076   res = val_new(t_pairing, p);
1077   mpz_clear(rbits);
1078   mpz_clear(qbits);
1079   pbc_param_clear(param);
1080   return res;
1081 }
1082
1083 static val_ptr f_fromZZ(darray_ptr arg) {
1084   val_ptr res;
1085   res = check_arg(arg, 2, t_element, t_field);
1086   if (res) return res;
1087   val_ptr a0 = arg->item[0];
1088   val_ptr a1 = arg->item[1];
1089   element_ptr e = a0->data;
1090   field_ptr f = a1->data;
1091   if (e->field != Z) {
1092     printf("arg not integer!\n");
1093     return newruntimeerror(re_badarg);
1094   }
1095   element_ptr e1 = pbc_malloc(sizeof(element_t));
1096   element_init(e1, f);
1097   element_set_mpz(e1, e->data);
1098   res = val_new(t_element, e1);
1099   return res;
1100 }
1101
1102 static val_ptr f_fromstr(darray_ptr arg) {
1103   val_ptr res;
1104   res = check_arg(arg, 2, t_string, t_field);
1105   if (res) return res;
1106   val_ptr a0 = arg->item[0];
1107   val_ptr a1 = arg->item[1];
1108   field_ptr f = a1->data;
1109   element_ptr e1 = pbc_malloc(sizeof(element_t));
1110   element_init(e1, f);
1111   element_set_str(e1, a0->data, 0);
1112   res = val_new(t_element, e1);
1113   return res;
1114 }
1115
1116 /* I'll probably never finish this :(
1117 static val_ptr f_index_calculus(darray_ptr arg) {
1118   val_ptr res;
1119   res = check_arg(arg, 2, t_element, t_element);
1120   if (res) return res;
1121   val_ptr a0 = arg->item[0];
1122   val_ptr a1 = arg->item[1];
1123   element_ptr e0 = a0->data;
1124   element_ptr e1 = a1->data;
1125   element_ptr e = pbc_malloc(sizeof(element_t));
1126   mpz_t x, g, h, q1;
1127
1128   //TODO: check e0, e1 are from an integer mod ring
1129   mpz_init(x);
1130   mpz_init(g);
1131   mpz_init(h);
1132   mpz_init(q1);
1133
1134   mpz_sub_ui(q1, e0->field->order, 1);
1135
1136   element_init(e, Z);
1137   element_to_mpz(g, e0);
1138   element_to_mpz(h, e1);
1139   pbc_mpz_index_calculus(x, g, h, q1);
1140   element_set_mpz(e, x);
1141   res = val_new(t_element, e);
1142   mpz_clear(x);
1143   mpz_clear(g);
1144   mpz_clear(h);
1145   mpz_clear(q1);
1146   return res;
1147 }
1148 */
1149
1150 int main(int argc, char **argv) {
1151   for (;;) {
1152     int c = getopt(argc, argv, "e");
1153     if (c == -1) break;
1154     switch (c) {
1155       case 'e':
1156         option_echo = 1;
1157         break;
1158       default:
1159         fprintf(stderr, "unrecognized option: %c\n", c);
1160         break;
1161     }
1162   }
1163
1164   symtab_init(var);
1165   symtab_init(builtin);
1166
1167   pairing_init_set_str(pairing_A, aparam);
1168   pairing_init_set_str(pairing_D, dparam);
1169   pairing_init_set_str(pairing_E, eparam);
1170   pairing_init_set_str(pairing_F, fparam);
1171   pairing_init_set_str(pairing_G, gparam);
1172   symtab_put(var, val_new(t_pairing, pairing_A), "A");
1173   symtab_put(var, val_new(t_pairing, pairing_D), "D");
1174   symtab_put(var, val_new(t_pairing, pairing_E), "E");
1175   symtab_put(var, val_new(t_pairing, pairing_F), "F");
1176   symtab_put(var, val_new(t_pairing, pairing_G), "G");
1177
1178   set_pairing_groups(pairing_A);
1179
1180   symtab_put(builtin, f_init_pairing, "init_pairing");
1181   symtab_put(builtin, f_pairing_G1, "get_G1");
1182   symtab_put(builtin, f_pairing_G2, "get_G2");
1183   symtab_put(builtin, f_pairing_GT, "get_GT");
1184   symtab_put(builtin, f_pairing_Zr, "get_Zr");
1185   symtab_put(builtin, f_random, "random");
1186   symtab_put(builtin, f_random, "rand");
1187   symtab_put(builtin, f_random, "rnd");
1188   symtab_put(builtin, f_order, "order");
1189   symtab_put(builtin, f_order, "ord");
1190   symtab_put(builtin, f_neg, "neg");
1191   symtab_put(builtin, f_sub, "sub");
1192   symtab_put(builtin, f_add, "add");
1193   symtab_put(builtin, f_pow, "pow");
1194   symtab_put(builtin, f_mul, "mul");
1195   symtab_put(builtin, f_inv, "inv");
1196   symtab_put(builtin, f_inv, "invert");
1197   symtab_put(builtin, f_div, "div");
1198   symtab_put(builtin, f_pairing, "pairing");
1199   symtab_put(builtin, f_nextprime, "nextprime");
1200   symtab_put(builtin, f_brute_force_dlog, "element_dlog_brute_force");
1201   symtab_put(builtin, f_pollard_rho, "element_dlog_pollard_rho");
1202   //symtab_put(builtin, f_index_calculus, "index_calculus");
1203   symtab_put(builtin, f_zz, "ZZ");
1204   symtab_put(builtin, f_gen_A, "gen_A");
1205   symtab_put(builtin, f_fromZZ, "fromZZ");
1206   symtab_put(builtin, f_fromstr, "fromstr");
1207
1208   field_init_z(Z);
1209
1210   fprintf(stderr, "pbc\n");
1211
1212   for (;;) {
1213     currentline = pbc_getline(NULL);
1214     if (!currentline) break;
1215     if (option_echo) puts(currentline);
1216     lexcp = currentline;
1217     parseline();
1218     free(currentline);
1219   }
1220   return 0;
1221 }