pbc.c

这是一个C的源代码

// Pairing-Based Calculator
// mainly for demonstration purposes
//
// It's times like these I wish C had garbage collection

#include <string.h>
#include <ctype.h>
#include <stdarg.h>
#include <unistd.h> //for getopt
#include "pbc.h"
#include "pbc_fieldmpz.h"
#include "pbc_fp.h"
#include "pbc_utils.h"

#include "config.h"

char *pbc_getline(void);

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;
}

void tree_delete(tree_ptr t)
{
    void delete_child(void *p) { tree_delete(p); }
    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();
		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; i<t->child->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; i<n; i++) {
	int t = va_arg(ap, int);
	val_ptr vp = arg->item[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;