From 3baeb11a8fbcfcdbc31976d421f17b85503b3ecd Mon Sep 17 00:00:00 2001 From: WuKong Date: Fri, 4 Sep 2015 09:25:34 +0200 Subject: init attribute-based encryption Change-Id: Iba1a3d722110abf747a0fba366f3ebc911d25b25 --- moon-abe/pbc-0.5.14/pbc/bilinear.test | 50 + moon-abe/pbc-0.5.14/pbc/g2_test.pbc | 37 + moon-abe/pbc-0.5.14/pbc/oldpbc.c | 1221 ++++++++++++++++++++++++ moon-abe/pbc-0.5.14/pbc/pairing_test.pbc | 21 + moon-abe/pbc-0.5.14/pbc/parser.lex | 56 ++ moon-abe/pbc-0.5.14/pbc/parser.y | 112 +++ moon-abe/pbc-0.5.14/pbc/pbc.c | 953 ++++++++++++++++++ moon-abe/pbc-0.5.14/pbc/pbc_getline.c | 17 + moon-abe/pbc-0.5.14/pbc/pbc_getline.readline.c | 10 + moon-abe/pbc-0.5.14/pbc/pbc_tree.h | 30 + 10 files changed, 2507 insertions(+) create mode 100644 moon-abe/pbc-0.5.14/pbc/bilinear.test create mode 100644 moon-abe/pbc-0.5.14/pbc/g2_test.pbc create mode 100644 moon-abe/pbc-0.5.14/pbc/oldpbc.c create mode 100644 moon-abe/pbc-0.5.14/pbc/pairing_test.pbc create mode 100644 moon-abe/pbc-0.5.14/pbc/parser.lex create mode 100644 moon-abe/pbc-0.5.14/pbc/parser.y create mode 100644 moon-abe/pbc-0.5.14/pbc/pbc.c create mode 100644 moon-abe/pbc-0.5.14/pbc/pbc_getline.c create mode 100644 moon-abe/pbc-0.5.14/pbc/pbc_getline.readline.c create mode 100644 moon-abe/pbc-0.5.14/pbc/pbc_tree.h (limited to 'moon-abe/pbc-0.5.14/pbc') diff --git a/moon-abe/pbc-0.5.14/pbc/bilinear.test b/moon-abe/pbc-0.5.14/pbc/bilinear.test new file mode 100644 index 00000000..956c792e --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/bilinear.test @@ -0,0 +1,50 @@ +define test_element_order(group) { + a := random(group); + o := order(group); + b := a^o; + CHECK(b == group(0)); +} + +define test_group_order() { + CHECK(order(G1) == order(G2)); + CHECK(order(G2) == order(GT)); + a := pairing(random(G1), random(G2)); + o := order(GT); + b := a^o; + CHECK(b == GT(0)); +} + +define test_pairing_with_zero() { + CHECK(GT(0) == GT(1)); + CHECK(pairing(G1(0), random(G2)) == GT(0)); + CHECK(pairing(random(G1), G2(0)) == GT(0)); + CHECK(pairing(G1(0), G2(0)) == GT(0)); +} + +define test_bilinear() { + a1 := random(G1); + b1 := random(G2); + x := random(Zr); + y := random(Zr); + CHECK(pairing(a1^x, b1) == pairing(a1, b1^x)); + CHECK(pairing(a1^x, b1) == pairing(a1, b1)^x); + CHECK(pairing(a1, b1^x) == pairing(a1, b1)^x); + CHECK(pairing(a1^x, b1^y) == pairing(a1, b1)^(x*y)); +} + +define test(initfn) { + initfn(); + test_element_order(G1); + test_element_order(G2); + test_element_order(GT); + test_group_order(); + test_pairing_with_zero(); + test_bilinear(); +} + +test(init_pairing_a); +test(init_pairing_d); +test(init_pairing_e); +test(init_pairing_f); +test(init_pairing_g); +test(init_pairing_i); diff --git a/moon-abe/pbc-0.5.14/pbc/g2_test.pbc b/moon-abe/pbc-0.5.14/pbc/g2_test.pbc new file mode 100644 index 00000000..892660f9 --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/g2_test.pbc @@ -0,0 +1,37 @@ +# Exercises a bug found by Zhang Ye. + +define test_cmp_0(initfn) { + initfn(); + CHECK(random(G2) != G2(0)); + CHECK(G2(0) != random(G2)); + CHECK(G2(0) == G2(0)); + CHECK(random(G1) != G1(0)); + CHECK(G1(0) != random(G1)); + CHECK(G1(0) == G1(0)); +} + +test_cmp_0(init_pairing_a); +test_cmp_0(init_pairing_d); +test_cmp_0(init_pairing_e); +test_cmp_0(init_pairing_f); +test_cmp_0(init_pairing_g); +test_cmp_0(init_pairing_i); + +# Exercises a bug found by Mario Di Raimondo. + +define test_g2_cmp(initfn) { + initfn(); + a := rnd(G2); + m := rnd(Zr); + n := rnd(Zr); + CHECK((a^m)^n == a^(m*n)); + CHECK(a != a^m); + CHECK(a != a^n); +} + +test_g2_cmp(init_pairing_a); +test_g2_cmp(init_pairing_d); +test_g2_cmp(init_pairing_e); +test_g2_cmp(init_pairing_f); +test_g2_cmp(init_pairing_g); +test_g2_cmp(init_pairing_i); diff --git a/moon-abe/pbc-0.5.14/pbc/oldpbc.c b/moon-abe/pbc-0.5.14/pbc/oldpbc.c new file mode 100644 index 00000000..525fe8f2 --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/oldpbc.c @@ -0,0 +1,1221 @@ +// Pairing-Based Calculator. +// Mainly for demonstration purposes. +// +// It's times like these I wish C had garbage collection. + +#include +#include +#include +#include //for getopt +#include "pbc.h" +#include "pbc_z.h" +#include "pbc_fp.h" + +#include "misc/darray.h" +#include "misc/symtab.h" + +char *pbc_getline(const char *); + +enum { + t_none = 0, + t_id, + t_int, + t_string, + t_comma, + t_lparen, + t_rparen, + t_add, + t_sub, + t_mul, + t_div, + t_set, + t_pow, + t_unk, + t_function, + t_pairing, + t_element, + t_field, + t_err, +}; + +enum { + pe_expect_factor = 100, + pe_expect_rparen, + pe_arglist, + re_varnotfound = 200, + re_badlvalue, + re_funnotfound, + re_unimplemented, + re_badargcount, + re_badarg, + re_fieldmismatch, +}; + +static int option_echo = 0; + +static field_t Z; + +static int tok_type; +//TODO: dynamic allocation: +static char word[1024]; + +struct id_s { + char *data; + int alloc; +}; +typedef struct id_s *id_ptr; + +id_ptr id_new(char *id) { + id_ptr res = pbc_malloc(sizeof(struct id_s)); + res->alloc = strlen(id) + 1; + res->data = pbc_malloc(res->alloc); + strcpy(res->data, id); + return res; +} + +void id_delete(id_ptr id) { + pbc_free(id->data); + pbc_free(id); +} + +struct tree_s { + int type; + void *data; + darray_t child; +}; +typedef struct tree_s *tree_ptr; + +tree_ptr tree_new(int type, void *data) { + tree_ptr res = pbc_malloc(sizeof(struct tree_s)); + res->type = type; + res->data = data; + darray_init(res->child); + return res; +} + +static void delete_child(void *p) { + tree_delete(p); +} + +void tree_delete(tree_ptr t) { + darray_forall(t->child, delete_child); + darray_clear(t->child); + switch(t->type) { + case t_id: + case t_string: + case t_function: + case t_int: + id_delete(t->data); + break; + } + pbc_free(t); +} + +static char *currentline; +static char *lexcp; + + +static void lex(void) { + char c; + if (!lexcp) { + tok_type = t_none; + return; + } + c = *lexcp++; + skipwhitespace: + for (;;) { + if (!strchr(" \t\r\n", c)) break; + if (!c) { + tok_type = t_none; + return; + } + c = *lexcp++; + } + + //comments start with '#' and end at a newline + if (c == '#') { + for (;;) { + c = *lexcp++; + if (!c) { + tok_type = t_none; + return; + } + if (c == '\n') break; + } + goto skipwhitespace; + } + + //strings + if (c == '"') { + tok_type = t_string; + int i = 0; + for (;;) { + c = *lexcp++; + if (!c) { + //string continues on next line + word[i++] = '\n'; + pbc_free(currentline); + currentline = pbc_getline(NULL); + if (!currentline) break; + if (option_echo) puts(currentline); + lexcp = currentline; + c = *lexcp++; + } + if (c == '"') { + break; + } + word[i++] = c; + } + word[i] = '\0'; + return; + } + + if (isdigit(c)) { + tok_type = t_int; + word[0] = c; + + int i = 1; + for (;;) { + c = *lexcp++; + if (isdigit(c)) { + word[i++] = c; + } else { + word[i] = '\0'; + lexcp--; + break; + } + } + return; + } + + if (isalpha(c) || c == '_') { + tok_type = t_id; + word[0] = c; + + int i = 1; + for (;;) { + c = *lexcp++; + if (isalnum(c) || c == '_') { + word[i++] = c; + } else { + word[i] = '\0'; + lexcp--; + break; + } + } + return; + } + + switch(c) { + case ',': + tok_type = t_comma; + break; + case '=': + tok_type = t_set; + break; + case '^': + tok_type = t_pow; + break; + case '*': + tok_type = t_mul; + break; + case '/': + tok_type = t_div; + break; + case '+': + tok_type = t_add; + break; + case '-': + tok_type = t_sub; + break; + case '(': + tok_type = t_lparen; + break; + case ')': + tok_type = t_rparen; + break; + default: + tok_type = t_unk; + break; + } +} + +static int lastparseerror; +static void setparseerror(int i) { + lastparseerror = i; +} + +static tree_ptr parsesetexpr(void); + +static tree_ptr parseexprlist(tree_ptr t) { + tree_ptr c; + lex(); // expect lparen + if (tok_type == t_rparen) { + lex(); + return t; + } + c = parsesetexpr(); + if (!c) return NULL; + darray_append(t->child, c); + for (;;) { + if (tok_type == t_rparen) { + lex(); + return t; + } + if (tok_type != t_comma) { + setparseerror(pe_arglist); + return NULL; + } + lex(); //expect comma + c = parsesetexpr(); + if (!c) return NULL; + darray_append(t->child, c); + } +} + +static tree_ptr parseprimitive(void) { + tree_ptr t; + switch(tok_type) { + id_ptr id; + case t_id: + id = id_new(word); + lex(); + if (tok_type == t_lparen) { + if (parseexprlist(t = tree_new(t_function, id))) { + return t; + } + tree_delete(t); + return NULL; + } else { + return tree_new(t_id, id); + } + case t_string: + lex(); + return tree_new(t_string, id_new(word)); + case t_lparen: + lex(); + t = parsesetexpr(); + if (!t) return NULL; + if (tok_type != t_rparen) { + tree_delete(t); + setparseerror(pe_expect_rparen); + return NULL; + } + lex(); + return t; + case t_int: + id = id_new(word); + lex(); + return tree_new(t_int, id); + default: + setparseerror(pe_expect_factor); + return NULL; + } +} + +static tree_ptr parsepow(void) { + tree_ptr t1; + t1 = parseprimitive(); + if (tok_type == t_pow) { + tree_ptr t2, res; + lex(); + t2 = parseprimitive(); + if (!t2) { + tree_delete(t1); + return NULL; + } + res = tree_new(t_function, id_new("pow")); + darray_append(res->child, t1); + darray_append(res->child, t2); + return res; + } + return t1; +} + +static tree_ptr parsefactor(void) { + tree_ptr t; + if (tok_type == t_sub) { + lex(); + t = parsefactor(); + if (!t) return NULL; + tree_ptr t1 = tree_new(t_function, id_new("neg")); + darray_append(t1->child, t); + return t1; + } + + t = parsepow(); + return t; +} + +static tree_ptr parseterm(void) { + tree_ptr t1, t2, res; + res = parsefactor(); + if (!res) return NULL; + for (;;) { + switch(tok_type) { + case t_mul: + lex(); + t2 = parsefactor(); + if (!t2) { + tree_delete(res); + return NULL; + } + t1 = tree_new(t_function, id_new("mul")); + darray_append(t1->child, res); + darray_append(t1->child, t2); + res = t1; + break; + case t_div: + lex(); + t2 = parsefactor(); + if (!t2) { + tree_delete(res); + return NULL; + } + t1 = tree_new(t_function, id_new("div")); + darray_append(t1->child, res); + darray_append(t1->child, t2); + res = t1; + break; + default: + return res; + } + } +} + +static tree_ptr parseexpr(void) { + tree_ptr t1, t2, res; + res = parseterm(); + if (!res) { + return NULL; + } + for (;;) { + switch(tok_type) { + case t_add: + lex(); + t2 = parseterm(); + if (!t2) { + tree_delete(res); + return NULL; + } + //t1 = tree_new(t_add, NULL); + t1 = tree_new(t_function, id_new("add")); + darray_append(t1->child, res); + darray_append(t1->child, t2); + res = t1; + break; + case t_sub: + lex(); + t2 = parseterm(); + if (!t2) { + tree_delete(res); + return NULL; + } + //t1 = tree_new(t_sub, NULL); + t1 = tree_new(t_function, id_new("sub")); + darray_append(t1->child, res); + darray_append(t1->child, t2); + res = t1; + break; + default: + return res; + } + } +} + +static tree_ptr parsesetexpr(void) { + tree_ptr t1, t2, res; + t1 = parseexpr(); + if (!t1) return NULL; + if (tok_type == t_set) { + lex(); + t2 = parsesetexpr(); + if (!t2) { + tree_delete(t1); + return NULL; + } + res = tree_new(t_set, NULL); + darray_append(res->child, t1); + darray_append(res->child, t2); + return res; + } + return t1; +} + +static void print_tree(tree_ptr t) { + id_ptr id; + int i; + if (!t) { + printf("NULL"); + return; + } + switch (t->type) { + case t_set: + print_tree(t->child->item[0]); + printf(" = "); + print_tree(t->child->item[1]); + break; + case t_id: + id = t->data; + printf("%s", id->data); + break; + case t_function: + id = t->data; + printf("%s(", id->data); + for (i=0; ichild->count; i++) { + print_tree(t->child->item[i]); + if (i < t->child->count - 1) printf(", "); + } + printf(")"); + break; + default: + printf("?!?"); + break; + } +} + +static symtab_t var; +static symtab_t builtin; + +struct val_s { + int type; + void *data; +}; +typedef struct val_s *val_ptr; + +static int lastruntimeerror; +static val_ptr newruntimeerror(int i) { + val_ptr res = pbc_malloc(sizeof(struct val_s)); + lastruntimeerror = i; + res->type = t_err; + res->data = int_to_voidp(i); + return res; +} + +val_ptr val_new(int type, void *data) { + val_ptr res = pbc_malloc(sizeof(struct val_s)); + res->type = type; + res->data = data; + return res; +} + +static void val_print(val_ptr v) { + pairing_ptr pairing; + field_ptr field; + element_ptr e; + switch (v->type) { + case t_element: + e = v->data; + element_out_str(stdout, 0, e); + printf("\n"); + break; + case t_pairing: + pairing = v->data; + printf("pairing: G1bits=%d G2bits=%d GTbits=%d\n", + pairing_length_in_bytes_x_only_G1(pairing) * 8, + pairing_length_in_bytes_x_only_G2(pairing) * 8, + pairing_length_in_bytes_GT(pairing) * 8); + break; + case t_field: + field = v->data; + field_out_info(stdout, field); + break; + case t_string: + printf("%s", (char *) v->data); + break; + default: + printf("val type %d unknown\n", v->type); + break; + } +} + +val_ptr val_copy(val_ptr v) { + val_ptr res = pbc_malloc(sizeof(struct val_s)); + res->type = v->type; + if (v->type == t_element) { + //current policy: always clear elements, always copy elements + res->data = pbc_malloc(sizeof(element_t)); + element_ptr e = v->data; + element_init(res->data, e->field); + element_set(res->data, e); + } else if (v->type == t_string) { + res->data = pbc_strdup(v->data); + } else { + res->data = v->data; + } + + return res; +} + +void val_delete(val_ptr v) { + switch(v->type) { + case t_element: + //current policy: always clear elements, always copy elements + element_clear(v->data); + pbc_free(v->data); + break; + case t_string: + pbc_free(v->data); + break; + case t_err: + break; + case t_pairing: + break; + case t_field: + break; + default: + printf("val_delete: case %d not handled: memory leak\n", v->type); + break; + } + pbc_free(v); +} + +struct fun_s { + val_ptr (*f)(darray_ptr); + int arity; + int type[32]; //TODO: replace with darray? who needs more than 32 args? +}; + +typedef val_ptr (*fun)(darray_ptr); + +static val_ptr check_arg(darray_ptr arg, int n, ...) { + va_list ap; + int i; + val_ptr res = NULL; + + va_start(ap, n); + if (arg->count != n) { + printf("expect %d argument(s)\n", n); + res = newruntimeerror(re_badargcount); + } else for (i=0; iitem[i]; + if (vp->type != t) { + printf("arg not type %d\n", t); + return newruntimeerror(re_badarg); + break; + } + } + + va_end(ap); + return res; +} + +static val_ptr f_pairing_get_group( + field_ptr (*get_group)(pairing_ptr p), darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 1, t_pairing); + if (res) return res; + val_ptr a0 = arg->item[0]; + pairing_ptr pairing = a0->data; + res = val_new(t_field, get_group(pairing)); + return res; +} + +static val_ptr f_pairing_G1(darray_ptr arg) { + field_ptr getG1(pairing_ptr p) { return p->G1; } + return f_pairing_get_group(getG1, arg); +} + +static val_ptr f_pairing_G2(darray_ptr arg) { + field_ptr getG2(pairing_ptr p) { return p->G2; } + return f_pairing_get_group(getG2, arg); +} + +static val_ptr f_pairing_GT(darray_ptr arg) { + field_ptr getGT(pairing_ptr p) { return p->GT; } + return f_pairing_get_group(getGT, arg); +} + +static val_ptr f_pairing_Zr(darray_ptr arg) { + field_ptr getZr(pairing_ptr p) { return p->Zr; } + return f_pairing_get_group(getZr, arg); +} + +static val_ptr f_random(darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 1, t_field); + if (res) return res; + val_ptr a0 = arg->item[0]; + field_ptr f = a0->data; + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, f); + element_random(e); + res = val_new(t_element, e); + return res; +} + +static val_ptr f_order(darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 1, t_field); + if (res) return res; + val_ptr a0 = arg->item[0]; + field_ptr f = a0->data; + + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, Z); + element_set_mpz(e, f->order); + res = val_new(t_element, e); + return res; +} + +static val_ptr f_unary( + void (*unary)(element_ptr, element_ptr), darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 1, t_element); + if (res) return res; + val_ptr a0 = arg->item[0]; + element_ptr e0 = a0->data; + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, e0->field); + unary(e, e0); + res = val_new(t_element, e); + return res; +} + +static val_ptr f_bin_op( + void (*binop)(element_ptr, element_ptr, element_ptr), + darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 2, t_element, t_element); + if (res) return res; + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + element_ptr e0 = a0->data; + element_ptr e1 = a1->data; + if (e0->field != e1->field) { + printf("field mismatch!\n"); + return newruntimeerror(re_fieldmismatch); + } + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, e0->field); + binop(e, e0, e1); + res = val_new(t_element, e); + return res; +} + + +static val_ptr f_add(darray_ptr arg) { + return f_bin_op(element_add, arg); +} + +static val_ptr f_mul(darray_ptr arg) { + return f_bin_op(element_mul, arg); +} + +static val_ptr f_sub(darray_ptr arg) { + return f_bin_op(element_sub, arg); +} + +static val_ptr f_div(darray_ptr arg) { + return f_bin_op(element_div, arg); +} + +static val_ptr f_inv(darray_ptr arg) { + return f_unary(element_invert, arg); +} + +static val_ptr f_neg(darray_ptr arg) { + return f_unary(element_neg, arg); +} + +static val_ptr f_pow(darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 2, t_element, t_element); + if (res) return res; + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + element_ptr e0 = a0->data; + element_ptr e1 = a1->data; + element_ptr e = pbc_malloc(sizeof(element_t)); + mpz_t z; + mpz_init(z); + element_to_mpz(z, e1); + element_init(e, e0->field); + element_pow_mpz(e, e0, z); + res = val_new(t_element, e); + mpz_clear(z); + return res; +} + +static pairing_ptr current_pairing; +static val_ptr f_pairing(darray_ptr arg) { + val_ptr res; + if (arg->count != 2) { + printf("expect two arguments\n"); + return newruntimeerror(re_badargcount); + } + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + if (a0->type != t_element) { + printf("arg 1 not element!\n"); + return newruntimeerror(re_badarg); + } + if (a1->type != t_element) { + printf("arg 2 not element!\n"); + return newruntimeerror(re_badarg); + } + pairing_ptr p; + element_ptr e0 = a0->data; + element_ptr e1 = a1->data; + p = e0->field->pairing; + if (e0->field != p->G1) { + printf("arg 1 not from G1!\n"); + return newruntimeerror(re_badarg); + } + if (e1->field != p->G2) { + printf("arg 2 not from G2!\n"); + return newruntimeerror(re_badarg); + } + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, p->GT); + pairing_apply(e, e0, e1, p); + res = val_new(t_element, e); + return res; +} + +static val_ptr execute_tree(tree_ptr t) { + darray_t arg; + id_ptr id; + fun fn; + int i; + val_ptr res, v; + tree_ptr t1, t2; + + switch (t->type) { + case t_id: + id = t->data; + v = symtab_at(var, id->data); + if (!v) { + return newruntimeerror(re_varnotfound); + } + return val_copy(v); + case t_set: + t1 = t->child->item[0]; + if (t1->type != t_id) { + return newruntimeerror(re_badlvalue); + } + t2 = t->child->item[1]; + v = execute_tree(t2); + if (v->type == t_err) return v; + id = t1->data; + // clear what's there first + if ((res = symtab_at(var, id->data))) { + val_delete(res); + } + symtab_put(var, v, id->data); + v = symtab_at(var, id->data); + return val_copy(v); + case t_function: + id = t->data; + fn = symtab_at(builtin, id->data); + if (!fn) { + return newruntimeerror(re_funnotfound); + } + darray_init(arg); + for (i=0; ichild->count; i++) { + v = execute_tree(t->child->item[i]); + if (v->type == t_err) { + darray_forall(arg, (void (*)(void *)) val_delete); + return v; + } + darray_append(arg, v); + } + res = fn(arg); + for (i=0; icount; i++) { + val_delete(arg->item[i]); + } + darray_clear(arg); + return res; + case t_int: + id = t->data; + char *cp; + mpz_t z; + mpz_init(z); + for (cp = id->data; *cp; cp++) { + mpz_mul_ui(z, z, 10); + mpz_add_ui(z, z, *cp - '0'); + } + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, Z); + element_set_mpz(e, z); + mpz_clear(z); + return val_new(t_element, e); + case t_string: + id = t->data; + return val_new(t_string, pbc_strdup(id->data)); + default: + return newruntimeerror(re_unimplemented); + } +} + +static void parseline(void) { + val_ptr v; + + tree_ptr t; + lex(); + if (tok_type == t_none) return; + t = parsesetexpr(); + if (0) { + print_tree(t); + printf("\n"); + } + if (t) { + v = execute_tree(t); + if (v) { + if (v->type == t_err) { + printf("runtime error (error code = %d)\n", lastruntimeerror); + } else { + if (t->type != t_set) val_print(v); + } + val_delete(v); + } + tree_delete(t); + } else { + printf("parse error (error code = %d)\n", lastparseerror); + } +} + +static char *aparam = +"type a\n" +"q 8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791\n" +"h 12016012264891146079388821366740534204802954401251311822919615131047207289359704531102844802183906537786776\n" +"r 730750818665451621361119245571504901405976559617\n" +"exp2 159\n" +"exp1 107\n" +"sign1 1\n" +"sign0 1\n"; + +static char *dparam = +"type d\n" +"q 625852803282871856053922297323874661378036491717\n" +"n 625852803282871856053923088432465995634661283063\n" +"h 3\n" +"r 208617601094290618684641029477488665211553761021\n" +"a 581595782028432961150765424293919699975513269268\n" +"b 517921465817243828776542439081147840953753552322\n" +"k 6\n" +"nk 60094290356408407130984161127310078516360031868417968262992864809623507269833854678414046779817844853757026858774966331434198257512457993293271849043664655146443229029069463392046837830267994222789160047337432075266619082657640364986415435746294498140589844832666082434658532589211525696\n" +"hk 1380801711862212484403205699005242141541629761433899149236405232528956996854655261075303661691995273080620762287276051361446528504633283152278831183711301329765591450680250000592437612973269056\n" +"coeff0 472731500571015189154958232321864199355792223347\n" +"coeff1 352243926696145937581894994871017455453604730246\n" +"coeff2 289113341693870057212775990719504267185772707305\n" +"nqr 431211441436589568382088865288592347194866189652\n"; + +static char *eparam = +"type e\n" +"q 7245986106510086080714203333362098431608853335867425877960916928496629182991629664903654100214900946450053872786629995869445693724001299041657434948257845644905153122838458864000479326695430719258600053239930483226650953770354174712511646273516974069245462534034085895319225452125649979474047163305307830001\n" +"r 730750862221594424981965739670091261094297337857\n" +"h 13569343110918781839835249021482970252603216587988030044836106948825516930173270978617489032334001006615524543925753725725046733884363846960470444404747241287743773746682188521738728797153760275116924829183670000\n" +"a 7130970454025799000067946137594446075551569949583815943390108723282396973737794273397246892274981883807989525599540630855644968426794929215599380425269625872763801485968007136000471718335185787206876242871042697778608875139078711621836858237429403052273312335081163896980825048123655535355411494046493419999\n" +"b 7169309004853894693616698536183663527570664411678352588247044791687141043489072737232715961588288238022010974661903752526911876859197052490952065266265699130144252031591491045333807587788600764557450846327338626261289568016170532652061787582791926724597362401398804563093625182790987016728290050466098223333\n" +"exp2 159\n" +"exp1 135\n" +"sign1 1\n" +"sign0 1\n"; + +static char *fparam = +"type f\n" +"q 205523667896953300194896352429254920972540065223\n" +"r 205523667896953300194895899082072403858390252929\n" +"b 40218105156867728698573668525883168222119515413\n" +"beta 115334401956802802075595682801335644058796914268\n" +"alpha0 191079354656274778837764015557338301375963168470\n" +"alpha1 71445317903696340296199556072836940741717506375\n"; + +static char *gparam = +"type g\n" +"q 503189899097385532598615948567975432740967203\n" +"n 503189899097385532598571084778608176410973351\n" +"h 1\n" +"r 503189899097385532598571084778608176410973351\n" +"a 465197998498440909244782433627180757481058321\n" +"b 463074517126110479409374670871346701448503064\n" +"k 10\n" +"nk 1040684643531490707494989587381629956832530311976146077888095795458709511789670022388326295177424065807612879371896982185473788988016190582073591316127396374860265835641044035656044524481121528846249501655527462202999638159773731830375673076317719519977183373353791119388388468745670818193868532404392452816602538968163226713846951514831917487400267590451867746120591750902040267826351982737642689423713163967384383105678367875981348397359466338807\n" +"hk 4110127713690841149713310614420858884651261781185442551927080083178682965171097172366598236129731931693425629387502221804555636704708008882811353539555915064049685663790355716130262332064327767695339422323460458479884756000782939428852120522712008037615051139080628734566850259704397643028017435446110322024094259858170303605703280329322675124728639532674407\n" +"coeff0 67343110967802947677845897216565803152319250\n" +"coeff1 115936772834120270862756636148166314916823221\n" +"coeff2 87387877425076080433559927080662339215696505\n" +"coeff3 433223145899090928132052677121692683015058909\n" +"coeff4 405367866213598664862417230702935310328613596\n" +"nqr 22204504160560785687198080413579021865783099\n"; + +static pairing_t pairing_A, pairing_D, pairing_E, pairing_F, pairing_G; + +static void set_pairing_groups(pairing_ptr p) { + symtab_put(var, val_new(t_field, p->G1), "G1"); + symtab_put(var, val_new(t_field, p->G2), "G2"); + symtab_put(var, val_new(t_field, p->GT), "GT"); + symtab_put(var, val_new(t_field, p->Zr), "Zr"); + symtab_put(var, val_new(t_pairing, p), "current_pairing"); + current_pairing = p; +} + +static val_ptr f_init_pairing(darray_ptr arg) { + val_ptr res; + + res = check_arg(arg, 1, t_pairing); + if (res) return res; + + val_ptr a0 = arg->item[0]; + pairing_ptr p = a0->data; + set_pairing_groups(p); + return NULL; +} + +static val_ptr f_nextprime(darray_ptr arg) { + mpz_t p; + val_ptr res; + + res = check_arg(arg, 1, t_element); + if (res) return res; + val_ptr a0 = arg->item[0]; + element_ptr e0 = a0->data; + if (e0->field != Z) { + printf("arg not integer!\n"); + return newruntimeerror(re_badarg); + } + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, Z); + mpz_init(p); + element_to_mpz(p, e0); + mpz_nextprime(p, p); + element_set_mpz(e, p); + res = val_new(t_element, e); + mpz_clear(p); + return res; +} + +static val_ptr f_brute_force_dlog(darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 2, t_element, t_element); + if (res) return res; + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + element_ptr e0 = a0->data; + element_ptr e1 = a1->data; + if (e0->field != e1->field) { + printf("arg field mismatch!\n"); + return newruntimeerror(re_badarg); + } + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, Z); + element_dlog_brute_force(e, e0, e1); + res = val_new(t_element, e); + return res; +} +static val_ptr f_pollard_rho(darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 3, t_element, t_element, t_field); + if (res) return res; + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + val_ptr a2 = arg->item[2]; + element_ptr e0 = a0->data; + element_ptr e1 = a1->data; + if (e0->field != e1->field) { + printf("arg field mismatch!\n"); + return newruntimeerror(re_badarg); + } + field_ptr f = a2->data; + element_ptr e = pbc_malloc(sizeof(element_t)); + element_init(e, f); + element_dlog_pollard_rho(e, e0, e1); + res = val_new(t_element, e); + return res; +} + +static val_ptr f_zz(darray_ptr arg) { + mpz_t p; + val_ptr res; + res = check_arg(arg, 1, t_element); + if (res) return res; + val_ptr a0 = arg->item[0]; + element_ptr e0 = a0->data; + if (e0->field != Z) { + printf("arg not integer!\n"); + return newruntimeerror(re_badarg); + } + field_ptr f = pbc_malloc(sizeof(field_t)); + mpz_init(p); + element_to_mpz(p, e0); + field_init_fp(f, p); + res = val_new(t_field, f); + mpz_clear(p); + return res; +} + +static val_ptr f_gen_A(darray_ptr arg) { + mpz_t rbits, qbits; + pairing_ptr p; + val_ptr res; + res = check_arg(arg, 2, t_element, t_element); + if (res) return res; + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + element_ptr e0 = a0->data; + if (e0->field != Z) { + printf("arg not integer!\n"); + return newruntimeerror(re_badarg); + } + element_ptr e1 = a1->data; + if (e1->field != Z) { + printf("arg not integer!\n"); + return newruntimeerror(re_badarg); + } + mpz_init(rbits); + mpz_init(qbits); + element_to_mpz(rbits, e0); + element_to_mpz(qbits, e1); + //TODO: check rbits and qbits aren't too big + pbc_param_t param; + pbc_param_init_a_gen(param, mpz_get_ui(rbits), mpz_get_ui(qbits)); + p = pbc_malloc(sizeof(pairing_t)); + pairing_init_pbc_param(p, param); + res = val_new(t_pairing, p); + mpz_clear(rbits); + mpz_clear(qbits); + pbc_param_clear(param); + return res; +} + +static val_ptr f_fromZZ(darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 2, t_element, t_field); + if (res) return res; + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + element_ptr e = a0->data; + field_ptr f = a1->data; + if (e->field != Z) { + printf("arg not integer!\n"); + return newruntimeerror(re_badarg); + } + element_ptr e1 = pbc_malloc(sizeof(element_t)); + element_init(e1, f); + element_set_mpz(e1, e->data); + res = val_new(t_element, e1); + return res; +} + +static val_ptr f_fromstr(darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 2, t_string, t_field); + if (res) return res; + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + field_ptr f = a1->data; + element_ptr e1 = pbc_malloc(sizeof(element_t)); + element_init(e1, f); + element_set_str(e1, a0->data, 0); + res = val_new(t_element, e1); + return res; +} + +/* I'll probably never finish this :( +static val_ptr f_index_calculus(darray_ptr arg) { + val_ptr res; + res = check_arg(arg, 2, t_element, t_element); + if (res) return res; + val_ptr a0 = arg->item[0]; + val_ptr a1 = arg->item[1]; + element_ptr e0 = a0->data; + element_ptr e1 = a1->data; + element_ptr e = pbc_malloc(sizeof(element_t)); + mpz_t x, g, h, q1; + + //TODO: check e0, e1 are from an integer mod ring + mpz_init(x); + mpz_init(g); + mpz_init(h); + mpz_init(q1); + + mpz_sub_ui(q1, e0->field->order, 1); + + element_init(e, Z); + element_to_mpz(g, e0); + element_to_mpz(h, e1); + pbc_mpz_index_calculus(x, g, h, q1); + element_set_mpz(e, x); + res = val_new(t_element, e); + mpz_clear(x); + mpz_clear(g); + mpz_clear(h); + mpz_clear(q1); + return res; +} +*/ + +int main(int argc, char **argv) { + for (;;) { + int c = getopt(argc, argv, "e"); + if (c == -1) break; + switch (c) { + case 'e': + option_echo = 1; + break; + default: + fprintf(stderr, "unrecognized option: %c\n", c); + break; + } + } + + symtab_init(var); + symtab_init(builtin); + + pairing_init_set_str(pairing_A, aparam); + pairing_init_set_str(pairing_D, dparam); + pairing_init_set_str(pairing_E, eparam); + pairing_init_set_str(pairing_F, fparam); + pairing_init_set_str(pairing_G, gparam); + symtab_put(var, val_new(t_pairing, pairing_A), "A"); + symtab_put(var, val_new(t_pairing, pairing_D), "D"); + symtab_put(var, val_new(t_pairing, pairing_E), "E"); + symtab_put(var, val_new(t_pairing, pairing_F), "F"); + symtab_put(var, val_new(t_pairing, pairing_G), "G"); + + set_pairing_groups(pairing_A); + + symtab_put(builtin, f_init_pairing, "init_pairing"); + symtab_put(builtin, f_pairing_G1, "get_G1"); + symtab_put(builtin, f_pairing_G2, "get_G2"); + symtab_put(builtin, f_pairing_GT, "get_GT"); + symtab_put(builtin, f_pairing_Zr, "get_Zr"); + symtab_put(builtin, f_random, "random"); + symtab_put(builtin, f_random, "rand"); + symtab_put(builtin, f_random, "rnd"); + symtab_put(builtin, f_order, "order"); + symtab_put(builtin, f_order, "ord"); + symtab_put(builtin, f_neg, "neg"); + symtab_put(builtin, f_sub, "sub"); + symtab_put(builtin, f_add, "add"); + symtab_put(builtin, f_pow, "pow"); + symtab_put(builtin, f_mul, "mul"); + symtab_put(builtin, f_inv, "inv"); + symtab_put(builtin, f_inv, "invert"); + symtab_put(builtin, f_div, "div"); + symtab_put(builtin, f_pairing, "pairing"); + symtab_put(builtin, f_nextprime, "nextprime"); + symtab_put(builtin, f_brute_force_dlog, "element_dlog_brute_force"); + symtab_put(builtin, f_pollard_rho, "element_dlog_pollard_rho"); + //symtab_put(builtin, f_index_calculus, "index_calculus"); + symtab_put(builtin, f_zz, "ZZ"); + symtab_put(builtin, f_gen_A, "gen_A"); + symtab_put(builtin, f_fromZZ, "fromZZ"); + symtab_put(builtin, f_fromstr, "fromstr"); + + field_init_z(Z); + + fprintf(stderr, "pbc\n"); + + for (;;) { + currentline = pbc_getline(NULL); + if (!currentline) break; + if (option_echo) puts(currentline); + lexcp = currentline; + parseline(); + free(currentline); + } + return 0; +} diff --git a/moon-abe/pbc-0.5.14/pbc/pairing_test.pbc b/moon-abe/pbc-0.5.14/pbc/pairing_test.pbc new file mode 100644 index 00000000..c57189f7 --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/pairing_test.pbc @@ -0,0 +1,21 @@ +# Tests sample type A pairing. + +g := G1([2382389466570123849673299401984867521337122094157231907755149435707124249269394670242462497382963719723036281844079382411446883273020125104982896098602669, 2152768906589770702756591740710760107878949212304343787392475836859241438597588807103470081101790991563152395601123682809718038151417122294066319979967168]); + +h := G2([5832612417453786541700129157230442590988122495898645678468800815872828277169950107203266157735206975228912899931278160262081308603240860553459187732968543, 5825590786822892934138376868455818413990615826926356662470129700411774690868351658310187202553513693344017463065909279569624651155563430675084173630054336]); + +a := 171583727262251826931173602797951212789946235851; +b := 233634857565210859330459959563397971304462340857; + +CHECK(pairing(g, h) == GT([1352478452661998164151215014828915385601138645645403926287105573769451214277485326392786454433874957123922454604362337349978217917242114505658729401276644, 2809858014072341042857607405424304552357466023841122154308055820747972163307396014445308786731013691659356362568425895483877936945589613445697089590886519])); + +CHECK(g^a == G1([3727290142167731134589933003026410141163353118002821914170365887139605219852868537686435214464927363733592858325260588072422405672197113236445369761687270, 8313413520789037477320458888316489483781506373846006723006557775349684878102042826049292521482530556981023752851151672326421296204733037418468523296005577])); + +CHECK(h^b == G2([302169045606583472168811217560382970305157511680176350745436990853463473855962841196184541109617397027480204774682450915021848512168573082843355648090809, 7428193877404140917518137438384425427600294220905786853638038223349096573857683866658575603565175187399696035468569929483731011292133989973187846752806084])); + +res := GT([5401677742232403160612802517983583823254857216272776607059355607024091426935935872461700304196658606704085604766577186374528948004140797833341187234647180, 4255900207739859478558185000995524505026245539159946661271849714832846423204570340979120001638894488614502770175520505048836617405342161594891740961421000]); + +CHECK(res == pairing(g^a, h^b)); +CHECK(res == pairing(g, h)^(Zr(a)*Zr(b))); +CHECK(res == pairing(g^a, h)^b); +CHECK(res == pairing(g, h^b)^a); diff --git a/moon-abe/pbc-0.5.14/pbc/parser.lex b/moon-abe/pbc-0.5.14/pbc/parser.lex new file mode 100644 index 00000000..1d0b9f23 --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/parser.lex @@ -0,0 +1,56 @@ +%{ +#include +#include +#include // for intptr_t +#include +#include "pbc_utils.h" +#include "pbc_field.h" + +#include "pbc_tree.h" +#define YYSTYPE tree_ptr +#include "parser.tab.h" + +extern int option_easy; + +%} + +%option nounput noinput + +%x COMMENT +%% +\/\* BEGIN(COMMENT); // Open C-style comment. +\*\/ BEGIN(0); // Close C-style comment. +. // Within a C-style comment. +\n // Within a C-style comment. +#.*$ // Comment. +[ \t\r]* // Whitespace. + +define return DEFINE; +[0-9]+ yylval = tree_new_z(yytext); return NUM; +[a-zA-Z_][a-zA-Z0-9_]* yylval = tree_new_id(yytext); return ID; +:= return ASSIGN; +== return EQ; +!= return NE; +\< return LT; +\> return T_GT; +\<= return LE; +\>= return GE; +\+ return PLUS; +- return MINUS; +\/ return DIVIDE; +\* return TIMES; +\^ return POW; +; return TERMINATOR; +\, return COMMA; +\? return QUESTION; +: return COLON; +\( return LPAR; +\) return RPAR; +\[ return LSQU; +\] return RSQU; +\{ return LBRACE; +\} return RBRACE; +\n if (option_easy) return TERMINATOR; += return option_easy ? ASSIGN : UNKNOWN; +. return UNKNOWN; +%% diff --git a/moon-abe/pbc-0.5.14/pbc/parser.y b/moon-abe/pbc-0.5.14/pbc/parser.y new file mode 100644 index 00000000..d51cebcc --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/parser.y @@ -0,0 +1,112 @@ +%{ +#include +#include +#include // for intptr_t +#include +#include "pbc_utils.h" +#include "pbc_field.h" + +#include "pbc_tree.h" +#define YYSTYPE tree_ptr +void yyerror(const char *s); +int yylex(void); + +#define YY_NO_INPUT +#define YY_NO_UNPUT + +extern int option_easy; +%} + +%error-verbose +%token DEFINE +%token TERMINATOR +%token NUM ID +%token LPAR RPAR LSQU RSQU LBRACE RBRACE COMMA +%right QUESTION COLON +%left EQ NE LT T_GT LE GE +%right ASSIGN +%left PLUS MINUS +%left DIVIDE TIMES +%right UMINUS +%right POW +%token UNKNOWN +%token END 0 "end of file" +%% +input + : // Empty. + | input stmt { tree_eval_stmt($2); } + ; + +stmt + : expr TERMINATOR + | DEFINE ID LPAR parms RPAR LBRACE stmtlist RBRACE { + $$ = tree_new_define($2, $4, $7); + } + ; + +stmtlist + : { $$ = tree_new_empty_stmt_list(); } // Empty. + | stmtlist stmt { tree_append($1, $2); } + ; + +parms + : { $$ = tree_new_empty_parms(); } // Empty. + | parms1 + ; + +parms1 + : ID { $$ = tree_new_empty_parms(); tree_append($$, $1); } + | parms1 COMMA ID { tree_append($1, $3); } + ; + +expr + : multinomial + | ID ASSIGN expr { $$ = tree_new_assign($1, $3); } + | expr QUESTION expr COLON expr { $$ = tree_new_ternary($1, $3, $5); } + | molecule + | molecule LSQU expr RSQU { $$ = tree_new_item($1, $3); } + | expr EQ expr { $$ = tree_new_eq($1, $3); } + | expr NE expr { $$ = tree_new_ne($1, $3); } + | expr LE expr { $$ = tree_new_le($1, $3); } + | expr GE expr { $$ = tree_new_ge($1, $3); } + | expr LT expr { $$ = tree_new_lt($1, $3); } + | expr T_GT expr { $$ = tree_new_gt($1, $3); } + | expr PLUS expr { $$ = tree_new_add($1, $3); } + | expr MINUS expr { $$ = tree_new_sub($1, $3); } + | expr TIMES expr { $$ = tree_new_mul($1, $3); } + | expr DIVIDE expr { $$ = tree_new_div($1, $3); } + | expr POW expr { $$ = tree_new_pow($1, $3); } + | MINUS expr %prec UMINUS { $$ = tree_new_neg($2); } + ; + +// Not quite atoms. +molecule + : molecule LPAR exprlist RPAR { $$ = $3; tree_set_fun($$, $1); } + | LPAR expr RPAR { $$ = $2; } + | ID + ; + +exprlist + : { $$ = tree_new_funcall(); } // Empty. + | nonemptyexprlist + ; + +nonemptyexprlist + : expr { tree_append($$ = tree_new_funcall(), $1); } + | nonemptyexprlist COMMA expr { tree_append($1, $3); } + ; + +multinomial + : NUM + | numlist + ; + +numlist + : LSQU sequence RSQU { $$ = $2; } + ; + +sequence + : expr { $$ = tree_new_list($1); } + | sequence COMMA expr { tree_append($1, $3); } + ; +%% diff --git a/moon-abe/pbc-0.5.14/pbc/pbc.c b/moon-abe/pbc-0.5.14/pbc/pbc.c new file mode 100644 index 00000000..6fb76046 --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/pbc.c @@ -0,0 +1,953 @@ +// Pairing-Based Calculator. + +// TODO: Garbage collection. +// TODO: Recursion (stack frames), anonymous functions. + +#include // For getopt. + +#include "pbc.h" +#include "pbc_fp.h" +#include "pbc_z.h" +#include "pbc_multiz.h" +#include "pbc_poly.h" + +#include "misc/darray.h" +#include "misc/symtab.h" + +#include "pbc_tree.h" + +#include "lex.yy.h" +#include "parser.tab.h" + +int option_easy = 0; +const char *option_prompt; + +char *pbc_getline(const char *prompt); + +void yyerror(char *s) { fprintf(stderr, "%s\n", s); } +int yyparse(void); + +// Symbol table holding built-in functions and variables. +static symtab_t reserved; +// Symbol table holding user-defined variable and function names. +static symtab_t tab; + +static field_t M; +static field_t Z; +static pairing_t pairing; + +struct val_s; +typedef struct val_s *val_ptr; + +struct fun_s; +typedef struct fun_s *fun_ptr; + +// Syntax tree node. +struct tree_s { + // Evaluates this node. + val_ptr (*eval)(tree_ptr); + union { + const char *id; + element_ptr elem; + // Built-in function. + fun_ptr fun; + // Child nodes. + darray_ptr child; + }; +}; + +enum { + ARITY_VARIABLE = -1, +}; + +// The interface of a val_ptr shared amongst many val_ptr objects. +// Analog of C++ class. +struct val_type_s { + // One of element, field, function, error. + char *name; + // Print out current value. + void (*out_str)(FILE *, val_ptr); + // Called when a variable is evaluated, e.g. "foo;". + val_ptr (*eval)(val_ptr); + // Called when a variable is used as a function, e.g. "foo();". + val_ptr (*funcall)(val_ptr, tree_ptr); +}; + +// Functions plus type checking data. +struct fun_s { + const char *name; + val_ptr (*run)(val_ptr[]); + int arity; + const struct val_type_s **sig; +}; +typedef struct fun_s fun_t[1]; + +// When interpreting, each node of the syntax tree recursively evaluates +// its children then returns a val_ptr. +struct val_s { + struct val_type_s *type; + union { + element_ptr elem; + // User-defined function. + tree_ptr def; + // Built-in function. + fun_ptr fun; + field_ptr field; + const char *msg; + }; +}; + +static val_ptr val_new_element(element_ptr e); +static val_ptr val_new_field(field_ptr e); +static val_ptr val_new_error(const char *msg, ...); + +// Evaluates syntax tree node. +static val_ptr tree_eval(tree_ptr t) { + return t->eval(t); +} + +static void v_elem_out(FILE* stream, val_ptr v) { + element_out_str(stream, 0, v->elem); +} + +static val_ptr v_elem_eval(val_ptr v) { + element_ptr e = pbc_malloc(sizeof(*e)); + element_init_same_as(e, v->elem); + element_set(e, v->elem); + return val_new_element(e); +} + +static void v_builtin_out(FILE* stream, val_ptr v) { + // TODO: Print types of arguments. + fprintf(stream, "built-in function %s, arity %d", + v->fun->name, v->fun->arity); +} + +static void v_define_out(FILE* stream, val_ptr v) { + fprintf(stream, "user-defined function %s", + ((tree_ptr) darray_at(v->def->child, 0))->id); +} + +static val_ptr v_builtin(val_ptr v, tree_ptr t) { + fun_ptr fun = v->fun; + int n = fun->arity; + if (1 + n != darray_count(t->child)) { + return val_new_error("%s: wrong number of arguments", fun->name); + } + val_ptr arg[n]; + int i; + for(i = 0; i < n; i++) { + arg[i] = tree_eval(darray_at(t->child, i)); + if (fun->sig[i] && arg[i]->type != fun->sig[i]) { + return val_new_error("%s: argument %d type mismatch", fun->name, i + 1); + } + } + return fun->run(arg); +} + +static void eval_stmt(void *ptr) { + tree_eval(ptr); +} + +static val_ptr v_def_call(val_ptr v, tree_ptr t) { + int i; + const char* name = ((tree_ptr) darray_at(v->def->child, 0))->id; + darray_ptr parm = ((tree_ptr) darray_at(v->def->child, 1))->child; + int n = darray_count(parm); + if (1 + n != darray_count(t->child)) { + return val_new_error("%s: wrong number of arguments", name); + } + for(i = 0; i < n; i++) { + const char *id = ((tree_ptr) darray_at(parm, i))->id; + val_ptr v1 = tree_eval(darray_at(t->child, i)); + // TODO: Stack frames for recursion. + symtab_put(tab, v1, id); + } + // Evaluate function body. + darray_ptr a = ((tree_ptr) darray_at(v->def->child, 2))->child; + darray_forall(a, eval_stmt); + return NULL; +} + +static val_ptr v_field_cast(val_ptr v, tree_ptr t) { + // TODO: Check args, x is an element. + val_ptr x = tree_eval(darray_at(t->child, 0)); + element_ptr e = x->elem; + if (e->field == M) { + if (v->field == M) return x; + element_ptr e2 = element_new(v->field); + if (element_is0(e)) // if 'set0' is not 'set1' in base field of GT, but we hope 'GT(0)' calls 'set1', we may directly call 'element_set0' here + element_set0(e2); + else if (element_is1(e)) // reason is same as above + element_set1(e2); + else + element_set_multiz(e2, e->data); + x->elem = e2; + return x; + } + if (v->field == M) { + // Map to/from integer. TODO: Map to/from multiz instead. + mpz_t z; + mpz_init(z); + element_to_mpz(z, e); + element_clear(e); + element_init(e, v->field); + element_set_mpz(e, z); + mpz_clear(z); + } + return x; +} + +static void v_field_out(FILE* stream, val_ptr v) { + field_out_info(stream, v->field); +} + +static val_ptr v_self(val_ptr v) { + return v; +} + +static void v_err_out(FILE* stream, val_ptr v) { + fprintf(stream, "%s", v->msg); +} + +static val_ptr v_errcall(val_ptr v, tree_ptr t) { + UNUSED_VAR(t); + return v; +} + +static struct val_type_s + // TODO: Replace NULL with get_coeff. + v_elem[1] = {{ "element", v_elem_out, v_elem_eval, NULL }}, + v_field[1] = {{ "field", v_field_out, v_self, v_field_cast }}, + v_fun[1] = {{ "builtin", v_builtin_out, v_self, v_builtin }}, + v_def[1] = {{ "function", v_define_out, v_self, v_def_call }}, + v_error[1] = {{ "error", v_err_out, v_self, v_errcall }}; + +// Function signature constants for type checking. +const struct val_type_s *sig_field[] = { v_field }; +const struct val_type_s *sig_elem[] = { v_elem }; +const struct val_type_s *sig_any[] = { NULL }; +const struct val_type_s *sig_elem_elem[] = { v_elem, v_elem }; +const struct val_type_s *sig_field_elem[] = { v_field, v_elem }; + +static val_ptr val_new_element(element_ptr e) { + val_ptr v = pbc_malloc(sizeof(*v)); + v->type = v_elem; + v->elem = e; + return v; +} + +static val_ptr val_new_field(field_ptr f) { + val_ptr v = pbc_malloc(sizeof(*v)); + v->type = v_field; + v->field = f; + return v; +} + +static val_ptr val_new_error(const char *msg, ...) { + va_list params; + char buf[80]; + + va_start(params, msg); + vsnprintf(buf, 80, msg, params); + va_end(params); + + val_ptr v = pbc_malloc(sizeof(*v)); + v->type = v_error; + v->msg = pbc_strdup(buf); + return v; +} + +static val_ptr val_new_fun(fun_ptr fun) { + val_ptr v = pbc_malloc(sizeof(*v)); + v->type = v_fun; + v->fun = fun; + return v; +} + +static val_ptr fun_bin( + void (*binop)(element_ptr, element_ptr, element_ptr), + val_ptr v[]) { + binop(v[0]->elem, v[0]->elem, v[1]->elem); + return v[0]; +} + +static val_ptr run_add(val_ptr v[]) { return fun_bin(element_add, v); } +static val_ptr run_sub(val_ptr v[]) { return fun_bin(element_sub, v); } +static val_ptr run_mul(val_ptr v[]) { return fun_bin(element_mul, v); } +static val_ptr run_div(val_ptr v[]) { return fun_bin(element_div, v); } +static val_ptr run_pow(val_ptr v[]) { return fun_bin(element_pow_zn, v); } + +static fun_t fun_add = {{ "add", run_add, 2, sig_elem_elem }}; +static fun_t fun_sub = {{ "sub", run_sub, 2, sig_elem_elem }}; +static fun_t fun_mul = {{ "mul", run_mul, 2, sig_elem_elem }}; +static fun_t fun_div = {{ "div", run_div, 2, sig_elem_elem }}; +static fun_t fun_pow = {{ "pow", run_pow, 2, sig_elem_elem }}; + +static val_ptr fun_cmp(val_ptr v[], int (*fun)(int)) { + int i = element_cmp(v[0]->elem, v[1]->elem); + element_ptr e = pbc_malloc(sizeof(*e)); + element_init(e, M); + element_set_si(e, fun(i)); + v[0]->elem = e; + return v[0]; +} + +static int is0(int i) { + return i == 0; +} + +static int isnot0(int i) { + return i != 0; +} + +static int isle(int i) { + return i <= 0; +} + +static int isge(int i) { + return i >= 0; +} + +static int islt(int i) { + return i < 0; +} + +static int isgt(int i) { + return i > 0; +} + +static val_ptr run_eq(val_ptr v[]) { + return fun_cmp(v, is0); +} + +static val_ptr run_ne(val_ptr v[]) { + return fun_cmp(v, isnot0); +} + +static val_ptr run_le(val_ptr v[]) { + return fun_cmp(v, isle); +} + +static val_ptr run_ge(val_ptr v[]) { + return fun_cmp(v, isge); +} +static val_ptr run_lt(val_ptr v[]) { + return fun_cmp(v, islt); +} +static val_ptr run_gt(val_ptr v[]) { + return fun_cmp(v, isgt); +} + +static fun_t fun_eq = {{ "==", run_eq, 2, sig_elem_elem }}; +static fun_t fun_ne = {{ "!=", run_ne, 2, sig_elem_elem }}; +static fun_t fun_le = {{ "<=", run_le, 2, sig_elem_elem }}; +static fun_t fun_ge = {{ ">=", run_ge, 2, sig_elem_elem }}; +static fun_t fun_lt = {{ "<", run_lt, 2, sig_elem_elem }}; +static fun_t fun_gt = {{ ">", run_gt, 2, sig_elem_elem }}; + +static val_ptr eval_elem(tree_ptr t) { + // TODO: Write element_clone(), or at least element_new(). + element_ptr e = pbc_malloc(sizeof(*e)); + element_init_same_as(e, t->elem); + element_set(e, t->elem); + return val_new_element(e); +} + +static val_ptr eval_list(tree_ptr t) { + element_ptr e = NULL; + int n = darray_count(t->child); + int i; + for(i = 0; i < n; i++) { + val_ptr x = tree_eval(darray_at(t->child, i)); + // TODO: Also check x is a multiz. + if (v_error == x->type) { + return x; + } + if (v_elem != x->type) { + return val_new_error("element expected in list"); + } + if (!i) e = multiz_new_list(x->elem); + else multiz_append(e, x->elem); + } + return val_new_element(e); +} + +static val_ptr eval_ternary(tree_ptr t) { + val_ptr x = tree_eval(darray_at(t->child, 0)); + if (v_error == x->type) { + return x; + } + if (x->type != v_elem) { + return val_new_error("element expected in ternary operator"); + } + if (!element_is0(x->elem)) { + return tree_eval(darray_at(t->child, 1)); + } + return tree_eval(darray_at(t->child, 2)); +} + +static val_ptr eval_id(tree_ptr t) { + val_ptr x = symtab_at(reserved, t->id); + if (!x) x = symtab_at(tab, t->id); + if (!x) { + return val_new_error("undefined variable %s", t->id); + } + return x->type->eval(x); +} + +static val_ptr eval_funcall(tree_ptr t) { + val_ptr x = tree_eval(darray_last(t->child)); + return x->type->funcall(x, t); +} + +static val_ptr eval_fun(tree_ptr t) { + return val_new_fun(t->fun); +} + +static val_ptr run_neg(val_ptr v[]) { + element_neg(v[0]->elem, v[0]->elem); + return v[0]; +} +static fun_t fun_neg = {{ "neg", run_neg, 1, sig_elem }}; + +static val_ptr eval_assign(tree_ptr t) { + tree_ptr tid = darray_at(t->child, 0); + val_ptr v = tree_eval(darray_at(t->child, 1)); + if (symtab_at(reserved, tid->id)) { + return val_new_error("%s is reserved", tid->id); + } + symtab_put(tab, v, tid->id); + return v; +} + +static void assign_field(field_ptr f, const char* s) { + symtab_put(tab, val_new_field(f), s); +} + +tree_ptr tree_new(val_ptr (*eval)(tree_ptr)) { + tree_ptr res = pbc_malloc(sizeof(*res)); + res->eval = eval; + return res; +} + +tree_ptr tree_new_z(const char* s) { + element_ptr e = pbc_malloc(sizeof(*e)); + element_init(e, M); + element_set_str(e, s, 0); + tree_ptr t = tree_new(eval_elem); + t->elem = e; + return t; +} + +static val_ptr eval_err(tree_ptr t) { + UNUSED_VAR(t); + pbc_die("BUG: shouldn't reach here!"); +} + +tree_ptr tree_new_empty_stmt_list() { + tree_ptr t = tree_new(eval_err); + t->child = darray_new(); + return t; +} + +tree_ptr tree_new_empty_parms() { + tree_ptr t = tree_new(eval_err); + t->child = darray_new(); + return t; +} + +static val_ptr eval_define(tree_ptr t) { + val_ptr v = pbc_malloc(sizeof(*v)); + v->type = v_def; + v->def = t; + symtab_put(tab, v, ((tree_ptr) darray_at(t->child, 0))->id); + return v; +} + +tree_ptr tree_new_define(tree_ptr id, tree_ptr parm, tree_ptr body) { + tree_ptr t = tree_new(eval_define); + t->child = darray_new(); + darray_append(t->child, id); + darray_append(t->child, parm); + darray_append(t->child, body); + return t; +} + +tree_ptr tree_new_list(tree_ptr first) { + tree_ptr t = tree_new(eval_list); + t->child = darray_new(); + darray_append(t->child, first); + return t; +} + +tree_ptr tree_new_ternary(tree_ptr cond, tree_ptr t1, tree_ptr t2) { + tree_ptr t = tree_new(eval_ternary); + t->child = darray_new(); + darray_append(t->child, cond); + darray_append(t->child, t1); + darray_append(t->child, t2); + return t; +} + +tree_ptr tree_new_id(const char* s) { + tree_ptr t = tree_new(eval_id); + t->id = pbc_strdup(s); + return t; +} + +tree_ptr tree_new_funcall(void) { + tree_ptr t = tree_new(eval_funcall); + t->child = darray_new(); + return t; +} + +static tree_ptr tree_new_fun(fun_ptr fun) { + tree_ptr t = tree_new(eval_fun); + t->fun = fun; + return t; +} + +void tree_set_fun(tree_ptr f, tree_ptr src) { + darray_append(f->child, src); +} + +void tree_append(tree_ptr f, tree_ptr p) { + darray_append(f->child, p); +} + +tree_ptr tree_new_binary(fun_ptr fun, tree_ptr x, tree_ptr y) { + tree_ptr t = tree_new_funcall(); + tree_append(t, x); + tree_append(t, y); + tree_set_fun(t, tree_new_fun(fun)); + return t; +} + +static tree_ptr tree_new_unary(fun_ptr fun, tree_ptr x) { + tree_ptr t = tree_new_funcall(); + tree_append(t, x); + tree_set_fun(t, tree_new_fun(fun)); + return t; +} + +tree_ptr tree_new_neg(tree_ptr t) { + return tree_new_unary(fun_neg, t); +} +tree_ptr tree_new_add(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_add, x, y); +} +tree_ptr tree_new_sub(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_sub, x, y); +} +tree_ptr tree_new_mul(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_mul, x, y); +} +tree_ptr tree_new_div(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_div, x, y); +} +tree_ptr tree_new_pow(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_pow, x, y); +} +tree_ptr tree_new_eq(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_eq, x, y); +} +tree_ptr tree_new_ne(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_ne, x, y); +} +tree_ptr tree_new_le(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_le, x, y); +} +tree_ptr tree_new_ge(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_ge, x, y); +} +tree_ptr tree_new_lt(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_lt, x, y); +} +tree_ptr tree_new_gt(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_gt, x, y); +} + +static val_ptr run_item(val_ptr v[]) { + mpz_t z; + mpz_init(z); + element_to_mpz(z, v[1]->elem); + int i = mpz_get_si(z); + mpz_clear(z); + element_ptr a = element_item(v[0]->elem, i); + element_ptr e = pbc_malloc(sizeof(*e)); + element_init_same_as(e, a); + element_set(e, a); + return val_new_element(e); +} +static fun_t fun_item = {{ "item", run_item, 2, sig_elem_elem }}; +tree_ptr tree_new_item(tree_ptr x, tree_ptr y) { + return tree_new_binary(fun_item, x, y); +} + +tree_ptr tree_new_assign(tree_ptr l, tree_ptr r) { + // TODO: Check l's type. + tree_ptr t = tree_new(eval_assign); + t->child = darray_new(); + darray_append(t->child, l); + darray_append(t->child, r); + return t; +} + +// Evaluate statement. +void tree_eval_stmt(tree_ptr stmt) { + val_ptr v = tree_eval(stmt); + if (v && v_error == v->type) { + v->type->out_str(stdout, v); + putchar('\n'); + } else if (stmt->eval != eval_assign && v) { + v->type->out_str(stdout, v); + putchar('\n'); + } +} + +static val_ptr run_nextprime(val_ptr v[]) { + element_ptr e = v[0]->elem; + mpz_t z; + mpz_init(z); + element_to_mpz(z, e); + mpz_nextprime(z, z); + element_set_mpz(e, z); + return v[0]; +} +static fun_t fun_nextprime = {{ "nextprime", run_nextprime, 1, sig_elem }}; + +static val_ptr run_order(val_ptr v[]) { + field_ptr f = v[0]->field; + element_ptr e = pbc_malloc(sizeof(*e)); + element_init(e, M); + element_set_mpz(e, f->order); + return val_new_element(e); +} +static fun_t fun_ord = {{ "ord", run_order, 1, sig_field }}; +static fun_t fun_order = {{ "order", run_order, 1, sig_field }}; + +static val_ptr run_random(val_ptr v[]) { + element_ptr e = pbc_malloc(sizeof(*e)); + element_init(e, v[0]->field); + element_random(e); + return val_new_element(e); +} +static fun_t fun_rnd = {{ "rnd", run_random, 1, sig_field }}; +static fun_t fun_random = {{ "random", run_random, 1, sig_field }}; + +static val_ptr run_sqrt(val_ptr v[]) { + // TODO: Check v[0] is square. + element_sqrt(v[0]->elem, v[0]->elem); + return v[0]; +} +static fun_t fun_sqrt = {{ "sqrt", run_sqrt, 1, sig_elem }}; + +static val_ptr run_invert(val_ptr v[]) { + // TODO: Check v[0] is invertible. + element_invert(v[0]->elem, v[0]->elem); + return v[0]; +} +static fun_t fun_inv = {{ "inv", run_invert, 1, sig_elem }}; + +static val_ptr run_type(val_ptr v[]) { + puts(v[0]->type->name); + return v[0]; +} +static fun_t fun_type = {{ "type", run_type, 1, sig_any }}; + +static val_ptr run_pairing(val_ptr v[]) { + element_ptr x = v[0]->elem; + element_ptr e = element_new(x->field->pairing->GT); + element_pairing(e, x, v[1]->elem); + return val_new_element(e); +} +static fun_t fun_pairing = {{ "pairing", run_pairing, 2, sig_elem_elem }}; + +static val_ptr run_zmod(val_ptr v[]) { + element_ptr e = v[0]->elem; + mpz_t z; + mpz_init(z); + element_to_mpz(z, e); + field_ptr f = pbc_malloc(sizeof(*f)); + field_init_fp(f, z); + mpz_clear(z); + return val_new_field(f); +} +static fun_t fun_zmod = {{ "zmod", run_zmod, 1, sig_elem }}; + +static val_ptr run_poly(val_ptr v[]) { + field_ptr f = pbc_malloc(sizeof(*f)); + field_init_poly(f, v[0]->field); + return val_new_field(f); +} +static fun_t fun_poly = {{ "poly", run_poly, 1, sig_field }}; + +static val_ptr run_polymod(val_ptr v[]) { + // TODO: Check v[0] is a poly. + field_ptr f = pbc_malloc(sizeof(*f)); + field_init_polymod(f, v[0]->elem); + return val_new_field(f); +} +static fun_t fun_polymod = {{ "polymod", run_polymod, 1, sig_elem }}; + +static val_ptr run_extend(val_ptr v[]) { + // TODO: Check v[1] is multiz poly. + field_ptr fx = pbc_malloc(sizeof(*fx)); + field_init_poly(fx, v[0]->field); + element_ptr poly = element_new(fx); + element_set_multiz(poly, v[1]->elem->data); + field_ptr f = pbc_malloc(sizeof(*f)); + field_init_polymod(f, poly); + element_free(poly); + return val_new_field(f); +} +static fun_t fun_extend = {{ "extend", run_extend, 1, sig_field_elem }}; + +static void init_pairing(const char *s) { + pairing_init_set_str(pairing, s); + assign_field(pairing->G1, "G1"); + assign_field(pairing->G2, "G2"); + assign_field(pairing->GT, "GT"); + assign_field(pairing->Zr, "Zr"); +} + +static val_ptr run_exit(val_ptr v[]) { + mpz_t z; + mpz_init(z); + element_to_mpz(z, v[0]->elem); + exit(mpz_get_si(z)); +} +static fun_t fun_exit = {{ "exit", run_exit, 1, sig_elem }}; + +static val_ptr run_CHECK(val_ptr v[]) { + if (element_is0(v[0]->elem)) { + pbc_die("CHECK failed"); + } + return v[0]; +} +static fun_t fun_CHECK = {{ "CHECK", run_CHECK, 1, sig_elem }}; + +static char *aparam = +"type a\n" +"q 8780710799663312522437781984754049815806883199414208211028653399266475630880222957078625179422662221423155858769582317459277713367317481324925129998224791\n" +"h 12016012264891146079388821366740534204802954401251311822919615131047207289359704531102844802183906537786776\n" +"r 730750818665451621361119245571504901405976559617\n" +"exp2 159\n" +"exp1 107\n" +"sign1 1\n" +"sign0 1\n"; + +static char *dparam = +"type d\n" +"q 625852803282871856053922297323874661378036491717\n" +"n 625852803282871856053923088432465995634661283063\n" +"h 3\n" +"r 208617601094290618684641029477488665211553761021\n" +"a 581595782028432961150765424293919699975513269268\n" +"b 517921465817243828776542439081147840953753552322\n" +"k 6\n" +"nk 60094290356408407130984161127310078516360031868417968262992864809623507269833854678414046779817844853757026858774966331434198257512457993293271849043664655146443229029069463392046837830267994222789160047337432075266619082657640364986415435746294498140589844832666082434658532589211525696\n" +"hk 1380801711862212484403205699005242141541629761433899149236405232528956996854655261075303661691995273080620762287276051361446528504633283152278831183711301329765591450680250000592437612973269056\n" +"coeff0 472731500571015189154958232321864199355792223347\n" +"coeff1 352243926696145937581894994871017455453604730246\n" +"coeff2 289113341693870057212775990719504267185772707305\n" +"nqr 431211441436589568382088865288592347194866189652\n"; + +static char *eparam = +"type e\n" +"q 7245986106510086080714203333362098431608853335867425877960916928496629182991629664903654100214900946450053872786629995869445693724001299041657434948257845644905153122838458864000479326695430719258600053239930483226650953770354174712511646273516974069245462534034085895319225452125649979474047163305307830001\n" +"r 730750862221594424981965739670091261094297337857\n" +"h 13569343110918781839835249021482970252603216587988030044836106948825516930173270978617489032334001006615524543925753725725046733884363846960470444404747241287743773746682188521738728797153760275116924829183670000\n" +"a 7130970454025799000067946137594446075551569949583815943390108723282396973737794273397246892274981883807989525599540630855644968426794929215599380425269625872763801485968007136000471718335185787206876242871042697778608875139078711621836858237429403052273312335081163896980825048123655535355411494046493419999\n" +"b 7169309004853894693616698536183663527570664411678352588247044791687141043489072737232715961588288238022010974661903752526911876859197052490952065266265699130144252031591491045333807587788600764557450846327338626261289568016170532652061787582791926724597362401398804563093625182790987016728290050466098223333\n" +"exp2 159\n" +"exp1 135\n" +"sign1 1\n" +"sign0 1\n"; + +static char *fparam = +"type f\n" +"q 205523667896953300194896352429254920972540065223\n" +"r 205523667896953300194895899082072403858390252929\n" +"b 40218105156867728698573668525883168222119515413\n" +"beta 115334401956802802075595682801335644058796914268\n" +"alpha0 191079354656274778837764015557338301375963168470\n" +"alpha1 71445317903696340296199556072836940741717506375\n"; + +static char *gparam = +"type g\n" +"q 503189899097385532598615948567975432740967203\n" +"n 503189899097385532598571084778608176410973351\n" +"h 1\n" +"r 503189899097385532598571084778608176410973351\n" +"a 465197998498440909244782433627180757481058321\n" +"b 463074517126110479409374670871346701448503064\n" +"k 10\n" +"nk 1040684643531490707494989587381629956832530311976146077888095795458709511789670022388326295177424065807612879371896982185473788988016190582073591316127396374860265835641044035656044524481121528846249501655527462202999638159773731830375673076317719519977183373353791119388388468745670818193868532404392452816602538968163226713846951514831917487400267590451867746120591750902040267826351982737642689423713163967384383105678367875981348397359466338807\n" +"hk 4110127713690841149713310614420858884651261781185442551927080083178682965171097172366598236129731931693425629387502221804555636704708008882811353539555915064049685663790355716130262332064327767695339422323460458479884756000782939428852120522712008037615051139080628734566850259704397643028017435446110322024094259858170303605703280329322675124728639532674407\n" +"coeff0 67343110967802947677845897216565803152319250\n" +"coeff1 115936772834120270862756636148166314916823221\n" +"coeff2 87387877425076080433559927080662339215696505\n" +"coeff3 433223145899090928132052677121692683015058909\n" +"coeff4 405367866213598664862417230702935310328613596\n" +"nqr 22204504160560785687198080413579021865783099\n"; + +static char *iparam = +"type i\n" +"m 97\n" +"t 12\n" +"n 2726865189058261010774960798134976187171462721\n" +"n2 7\n"; + +static val_ptr run_init_pairing_a(val_ptr v[]) { + UNUSED_VAR(v); + init_pairing(aparam); + return NULL; +} +static fun_t fun_init_pairing_a = {{ + "init_pairing_a", run_init_pairing_a, 0, NULL + }}; + +static val_ptr run_init_pairing_d(val_ptr v[]) { + UNUSED_VAR(v); + init_pairing(dparam); + return NULL; +} +static fun_t fun_init_pairing_d = {{ + "init_pairing_d", run_init_pairing_d, 0, NULL + }}; + +static val_ptr run_init_pairing_e(val_ptr v[]) { + UNUSED_VAR(v); + init_pairing(eparam); + return NULL; +} +static fun_t fun_init_pairing_e = {{ + "init_pairing_e", run_init_pairing_e, 0, NULL + }}; + +static val_ptr run_init_pairing_f(val_ptr v[]) { + UNUSED_VAR(v); + init_pairing(fparam); + return NULL; +} +static fun_t fun_init_pairing_f = {{ + "init_pairing_f", run_init_pairing_f, 0, NULL + }}; + +static val_ptr run_init_pairing_g(val_ptr v[]) { + UNUSED_VAR(v); + init_pairing(gparam); + return NULL; +} +static fun_t fun_init_pairing_g = {{ + "init_pairing_g", run_init_pairing_g, 0, NULL + }}; + +static val_ptr run_init_pairing_i(val_ptr v[]) { + UNUSED_VAR(v); + init_pairing(iparam); + return NULL; +} +static fun_t fun_init_pairing_i = {{ + "init_pairing_i", run_init_pairing_i, 0, NULL + }}; + +static void builtin(fun_ptr fun) { + symtab_put(reserved, val_new_fun(fun), fun->name); +} + +int end_of_input; + +int yywrap_return1(void) { return 1; } + +int yywrap_readline(void) { + static char *currentline; + static YY_BUFFER_STATE st; + yy_delete_buffer(st); + free(currentline); + currentline = pbc_getline(option_prompt); + if (!currentline) { + end_of_input = 1; + return 1; + } + int n = strlen(currentline); + currentline = realloc(currentline, n + 2); + currentline[n] = '\n'; + currentline[n + 1] = '\0'; + st = yy_scan_string(currentline); + //if (option_echo) puts(currentline); + return 0; +} + +static int (*yywrapfun)(void); +int yywrap(void) { + return yywrapfun(); +} + +int main(int argc, char **argv) { + for (;;) { + int c = getopt(argc, argv, "y"); + if (c == -1) break; + switch (c) { + case 'y': + option_easy = 1; + option_prompt = "> "; + break; + default: + fprintf(stderr, "unrecognized option: %c\n", c); + break; + } + } + + field_init_z(Z); + field_init_multiz(M); + symtab_init(tab); + + builtin(fun_rnd); + builtin(fun_random); + builtin(fun_ord); + builtin(fun_order); + builtin(fun_nextprime); + builtin(fun_sqrt); + builtin(fun_inv); + builtin(fun_type); + builtin(fun_pairing); + builtin(fun_zmod); + builtin(fun_poly); + builtin(fun_polymod); + builtin(fun_extend); + builtin(fun_exit); + builtin(fun_CHECK); + builtin(fun_init_pairing_a); + builtin(fun_init_pairing_d); + builtin(fun_init_pairing_e); + builtin(fun_init_pairing_f); + builtin(fun_init_pairing_g); + builtin(fun_init_pairing_i); + run_init_pairing_a(NULL); + symtab_put(reserved, val_new_field(M), "M"); + symtab_put(reserved, val_new_field(Z), "Z"); + + if (argc > optind) { + FILE *fp = fopen(argv[optind], "r"); + if (!fp) pbc_die("fopen failed on %s", argv[optind]); + YY_BUFFER_STATE st = yy_create_buffer(fp, YY_BUF_SIZE); + yy_switch_to_buffer(st); + yywrapfun = yywrap_return1; + yyparse(); + yy_delete_buffer(st); + } else { + yywrapfun = yywrap_readline; + yywrap(); + while (!end_of_input) { + if (2 == yyparse()) pbc_die("parser out of memory"); + } + putchar('\n'); + } + + symtab_clear(tab); + field_clear(M); + return 0; +} diff --git a/moon-abe/pbc-0.5.14/pbc/pbc_getline.c b/moon-abe/pbc-0.5.14/pbc/pbc_getline.c new file mode 100644 index 00000000..dc44cc40 --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/pbc_getline.c @@ -0,0 +1,17 @@ +#include +#include + +#include "pbc_memory.h" + +char *pbc_getline(const char *prompt) { + char s[1024]; + if (prompt) fputs(prompt, stdout); + if (!fgets(s, 1024, stdin)) return NULL; + if (feof(stdin)) return NULL; + /* use strdup rather than pbc_strdup. because + * 1. readline version of this function uses malloc. + * 2. pbc_malloc called by pbc_strdup may differ from malloc. + * here we keep consistency. + */ + return strdup(s); +} diff --git a/moon-abe/pbc-0.5.14/pbc/pbc_getline.readline.c b/moon-abe/pbc-0.5.14/pbc/pbc_getline.readline.c new file mode 100644 index 00000000..8d5e8f5a --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/pbc_getline.readline.c @@ -0,0 +1,10 @@ +#include +#include +#include + +char *pbc_getline(const char *prompt) +{ + char *line = readline(prompt); + if (line && *line) add_history(line); + return line; +} diff --git a/moon-abe/pbc-0.5.14/pbc/pbc_tree.h b/moon-abe/pbc-0.5.14/pbc/pbc_tree.h new file mode 100644 index 00000000..2526ab61 --- /dev/null +++ b/moon-abe/pbc-0.5.14/pbc/pbc_tree.h @@ -0,0 +1,30 @@ +// Requires: +// * field.h +struct tree_s; +typedef struct tree_s *tree_ptr; +tree_ptr tree_new_z(const char* s); +tree_ptr tree_new_empty_stmt_list(void); +tree_ptr tree_new_empty_parms(void); +tree_ptr tree_new_define(tree_ptr id, tree_ptr parm, tree_ptr body); +tree_ptr tree_new_list(tree_ptr t); +tree_ptr tree_new_id(const char* s); +tree_ptr tree_new_assign(tree_ptr l, tree_ptr r); +tree_ptr tree_new_funcall(void); +void tree_append(tree_ptr f, tree_ptr p); +void tree_set_fun(tree_ptr dst, tree_ptr src); +void tree_eval_stmt(tree_ptr t); + +tree_ptr tree_new_neg(tree_ptr t); +tree_ptr tree_new_add(tree_ptr x, tree_ptr y); +tree_ptr tree_new_sub(tree_ptr x, tree_ptr y); +tree_ptr tree_new_mul(tree_ptr x, tree_ptr y); +tree_ptr tree_new_div(tree_ptr x, tree_ptr y); +tree_ptr tree_new_pow(tree_ptr x, tree_ptr y); +tree_ptr tree_new_eq(tree_ptr x, tree_ptr y); +tree_ptr tree_new_ne(tree_ptr x, tree_ptr y); +tree_ptr tree_new_le(tree_ptr x, tree_ptr y); +tree_ptr tree_new_ge(tree_ptr x, tree_ptr y); +tree_ptr tree_new_lt(tree_ptr x, tree_ptr y); +tree_ptr tree_new_gt(tree_ptr x, tree_ptr y); +tree_ptr tree_new_ternary(tree_ptr cond, tree_ptr t1, tree_ptr t2); +tree_ptr tree_new_item(tree_ptr x, tree_ptr y); -- cgit 1.2.3-korg