diff options
| -rw-r--r--[l---------] | src/pbg.c | 1401 | ||||
| -rw-r--r--[l---------] | src/pbg.h | 240 | ||||
| -rw-r--r--[l---------] | src/teeny-sha1.c | 207 |
3 files changed, 1845 insertions, 3 deletions
diff --git a/src/pbg.c b/src/pbg.c index c707a6b..f002339 120000..100644 --- a/src/pbg.c +++ b/src/pbg.c @@ -1 +1,1400 @@ -../pbg/pbg.c
\ No newline at end of file +/** + * Cloned from https://github.com/coderthetyler/pbg.git + * in commit 5b61964c84c56c3ad824b240ca078eba98bc9ca7 + * + * A small patch was applied to fix some memory leaks + * To see it: + * git clone https://github.com/coderthetyler/pbg.git && cd pbg + * git checkout 5b61964c84c56c3ad824b240ca078eba98bc9ca7 + * diff <this file> <pbg.c from repo> + */ + +#include "pbg.h" +#include <stdlib.h> +#include <stdio.h> +#include <string.h> + +/***************************** + * * + * LOCAL STRUCTURE DIRECTORY * + * * + *****************************/ + +/* LITERAL REPRESENTATIONS */ +typedef struct { + double _val; +} pbg_lt_number; /* PBG_LT_NUMBER */ + +typedef struct { + unsigned int _YYYY; /* year */ + unsigned int _MM; /* month */ + unsigned int _DD; /* day */ +} pbg_lt_date; /* PBG_LT_DATE */ + +typedef char pbg_lt_string; /* PBG_LT_STRING */ + +/* ERROR REPRESENTATIONS */ +typedef struct { + int _arity; /* Number of arguments given to operator. */ + pbg_field_type _type; /* Type of operator involved in error. */ +} pbg_op_arity_err; /* PBG_ERR_OP_ARITY. */ + +typedef struct { + char* _msg; /* Description of syntax error. */ + char* _str; /* String in which error occurred. */ + int _i; /* Index of error in string. */ +} pbg_syntax_err; /* PBG_ERR_SYNTAX */ + +typedef struct { + char* _field; /* String representing the unknown type. */ + int _n; /* Length of field. */ +} pbg_unknown_type_err; /* PBG_ERR_UNKNOWN_TYPE */ + + +/**************************** + * * + * LOCAL FUNCTION DIRECTORY * + * * + ****************************/ + +/* ERROR MANAGEMENT */ +void pbg_err_init(pbg_error* err, pbg_error_type type, int line, char* file, int size, void* data); +void pbg_err_alloc(pbg_error* err, int line, char* file); +void pbg_err_unknown_type(pbg_error* err, int line, char* file, char* field, int n); +void pbg_err_syntax(pbg_error* err, int line, char* file, char* str, int i, char* msg); +void pbg_err_op_arity(pbg_error* err, int line, char* file, pbg_field_type type, int arity); +void pbg_err_state(pbg_error* err, int line, char* file, char* msg); +void pbg_err_op_arg_type(pbg_error* err, int line, char* file, char* msg); +char* pbg_error_str(pbg_error_type type); +char* pbg_field_type_str(pbg_field_type type); + +/* FIELD MANAGEMENT */ +pbg_field* pbg_field_get(pbg_expr* e, int index); +void pbg_field_free(pbg_field* field); +int pbg_store_constant(pbg_expr* e, pbg_field field); +int pbg_store_variable(pbg_expr* e, pbg_field field); + +/* FIELD CREATION TOOLKIT */ +pbg_field pbg_field_init(pbg_field_type type, int size, void* data); +pbg_field pbg_parse_op(pbg_error* err, pbg_field_type type, int numchildren); +pbg_field pbg_parse_var(pbg_error* err, char* str, int n); +pbg_field pbg_parse_date(pbg_error* err, char* str, int n); +pbg_field pbg_parse_number(pbg_error* err, char* str, int n); +pbg_field pbg_parse_string(pbg_error* err, char* str, int n); + +/* FIELD PARSING TOOLKIT */ +int pbg_check_op_arity(pbg_field_type type, int numargs); + +/* FIELD EVALUATION TOOLKIT */ +int pbg_evaluate_r(pbg_expr* e, pbg_error* err, pbg_field* field); +int pbg_evaluate_op_not(pbg_expr* e, pbg_error* err, pbg_field* field); +int pbg_evaluate_op_and(pbg_expr* e, pbg_error* err, pbg_field* field); +int pbg_evaluate_op_or(pbg_expr* e, pbg_error* err, pbg_field* field); +int pbg_evaluate_op_exst(pbg_expr* e, pbg_error* err, pbg_field* field); +int pbg_evaluate_op_eq(pbg_expr* e, pbg_error* err, pbg_field* field); +int pbg_evaluate_op_neq(pbg_expr* e, pbg_error* err, pbg_field* field); +int pbg_evaluate_op_order(pbg_expr* e, pbg_error* err, pbg_field* field); +int pbg_evaluate_op_type(pbg_expr* e, pbg_error* err, pbg_field* field); + +/* JANITORIAL FUNCTIONS */ +/* No local functions. */ + +/* CONVERSION & CHECKING TOOLKIT */ +pbg_field_type pbg_gettype(char* str, int n); +int pbg_istypedate(char* str, int n); +int pbg_istypenumber(char* str, int n); +int pbg_istypebool(char* str, int n); +int pbg_istypestring(char* str, int n); +int pbg_istrue(char* str, int n); +int pbg_isfalse(char* str, int n); +int pbg_isvar(char* str, int n); +int pbg_isnumber(char* str, int n); +int pbg_isstring(char* str, int n); +int pbg_isdate(char* str, int n); + +void pbg_tonumber(pbg_lt_number* ptr, char* str, int n); +void pbg_todate(pbg_lt_date* ptr, char* str, int n); + +int pbg_cmpnumber(pbg_lt_number* n1, pbg_lt_number* n2); +int pbg_cmpdate(pbg_lt_date* d1, pbg_lt_date* d2); +int pbg_cmpstring(pbg_lt_string* s1, pbg_lt_string* s2, int n); + +int pbg_type_isbool(pbg_field_type type); +int pbg_type_isop(pbg_field_type type); + +/* HELPER FUNCTIONS */ +int pbg_isdigit(char c); +int pbg_iswhitespace(char c); + + +/********************** + * * + * ERROR CONSTRUCTION * + * * + **********************/ + +void pbg_error_print(pbg_error* err) +{ + pbg_op_arity_err* arity; + pbg_syntax_err* syntax; + pbg_unknown_type_err* utype; + if(err->_type == PBG_ERR_NONE) + return; + printf("error %s at %s:%d", + pbg_error_str(err->_type), err->_file, err->_line); + switch(err->_type) { + case PBG_ERR_OP_ARG_TYPE: + case PBG_ERR_STATE: + printf(": %s", (char*) err->_data); + break; + case PBG_ERR_OP_ARITY: + arity = (pbg_op_arity_err*) err->_data; + printf(": operator %s cannot take %d arguments!", + pbg_field_type_str(arity->_type), arity->_arity); + break; + case PBG_ERR_SYNTAX: + syntax = (pbg_syntax_err*) err->_data; + printf(": %s -> %s", (char*) syntax->_msg, syntax->_str+syntax->_i); + break; + case PBG_ERR_UNKNOWN_TYPE: + utype = (pbg_unknown_type_err*) err->_data; + printf(": failed to recognize %s (%d bytes)\n", (char*)utype->_field, utype->_n); + break; + default: + break; + } + printf("\n"); +} + +void pbg_err_init(pbg_error* err, pbg_error_type type, int line, char* file, + int size, void* data) +{ + err->_type = type; + err->_line = line; + err->_file = file; + err->_int = size; + err->_data = data; +} + +void pbg_err_alloc(pbg_error* err, int line, char* file) { + pbg_err_init(err, PBG_ERR_ALLOC, line, file, 0, NULL); +} + +void pbg_err_unknown_type(pbg_error* err, int line, char* file, + char* field, int n) +{ + pbg_unknown_type_err* data; + data = malloc(n * sizeof(char)); + if(data == NULL) { + pbg_err_alloc(err, __LINE__, __FILE__); /* gah. */ + return; + } + data->_field = field; + data->_n = n; + pbg_err_init(err, PBG_ERR_UNKNOWN_TYPE, line, file, n, data); +} + +void pbg_err_syntax(pbg_error* err, int line, char* file, + char* str, int i, char* msg) +{ + pbg_syntax_err* data; + int size; + data = malloc(size = sizeof(pbg_syntax_err)); + if(data == NULL) { + pbg_err_alloc(err, __LINE__, __FILE__); /* unfortunate. */ + return; + } + data->_msg = msg; + data->_str = str; + data->_i = i; + pbg_err_init(err, PBG_ERR_SYNTAX, line, file, size, data); +} + +void pbg_err_op_arity(pbg_error* err, int line, char* file, + pbg_field_type type, int arity) +{ + pbg_op_arity_err* data; + int size; + data = malloc(size = sizeof(pbg_op_arity_err)); + if(data == NULL) { + pbg_err_alloc(err, __LINE__, __FILE__); /* unfortunate. */ + return; + } + data->_arity = arity; + data->_type = type; + pbg_err_init(err, PBG_ERR_OP_ARITY, line, file, size, data); +} + +void pbg_err_state(pbg_error* err, int line, char* file, char* msg) { + pbg_err_init(err, PBG_ERR_STATE, line, file, 0, msg); +} + +void pbg_err_op_arg_type(pbg_error* err, int line, char* file, char* msg) { + pbg_err_init(err, PBG_ERR_OP_ARG_TYPE, line, file, 0, msg); +} + +void pbg_error_free(pbg_error* err) { + if(err->_int != 0) free(err->_data); +} + + +/******************** + * * + * FIELD MANAGEMENT * + * * + ********************/ + +/** + * This function returns the field identified by the given index. Constant fields + * are identified by positive indices starting at 1. Variable fields are + * identified by negative indices starting at -1. + * @param e PBG expression to get field from. + * @param index Index of the field to get. + * @return Pointer to the pbg_field in e specified by the index, + * NULL if index is 0. + */ +pbg_field* pbg_field_get(pbg_expr* e, int index) +{ + if(index < 0) return e->_variables - (index+1); + if(index > 0) return e->_constants + (index-1); + return NULL; +} + +/** + * Free's the single pbg_field pointed to by the specified pointer. + * @param field pbg_field to free. + */ +void pbg_field_free(pbg_field* field) { + if(field->_data != NULL) free(field->_data); +} + +/** + * This function stores the given constant field in the AST. Constant fields are + * indexed using positive values starting at 1. + * @param e Abstract expression tree to store field in. + * @param field Field to store. + * @return a positive index if successful, + * 0 otherwise. + */ +int pbg_store_constant(pbg_expr* e, pbg_field field) +{ + int fieldi; + if(field._type == PBG_NULL) + return 0; + fieldi = 1 + e->_numconst++; + *pbg_field_get(e, fieldi) = field; + return fieldi; +} + +/** + * This function stores the given variable field in the AST. Variable fields are + * indexed using negative values starting at -1. + * @param e Abstract expression tree to store field in. + * @param field Field to store. + * @return a negative index if successful, + * 0 otherwise. + */ +int pbg_store_variable(pbg_expr* e, pbg_field field) +{ + int fieldi; + fieldi = -(1 + e->_numvars++); + *pbg_field_get(e, fieldi) = field; + return fieldi; +} + + +/************************** + * * + * FIELD CREATION TOOLKIT * + * * + **************************/ + +pbg_field pbg_make_date(int year, int month, int day) +{ + int size; + pbg_lt_date* data; + data = malloc(size = sizeof(pbg_lt_date)); + data->_YYYY = year; + data->_MM = month; + data->_DD = day; + return pbg_field_init(PBG_LT_DATE, size, data); +} + +pbg_field pbg_make_bool(int truth) { + return pbg_field_init(truth ? PBG_LT_TRUE : PBG_LT_FALSE, 0, NULL); +} + +pbg_field pbg_make_number(double value) +{ + int size; + pbg_lt_number* data; + data = malloc(size = sizeof(pbg_lt_number)); + data->_val = value; + return pbg_field_init(PBG_LT_NUMBER, size, data); +} + +pbg_field pbg_make_string(char* str) +{ + int size, n; + pbg_lt_string* data; + n = strlen(str); + data = malloc(size = n * sizeof(pbg_lt_string)); + memcpy(data, str, n); + return pbg_field_init(PBG_LT_STRING, size, data); +} + +pbg_field pbg_make_null(void) { + return pbg_field_init(PBG_NULL, 0, NULL); +} + +/** + * Create a new pbg_field with the given arguments. + * @param type Type of the field. + * @param size Size of the field, however that is measured. + * @param data Data to store in the field. + * @return the new pbg_field. + */ +pbg_field pbg_field_init(pbg_field_type type, int size, void* data) +{ + pbg_field field; + field._type = type; + field._int = size; + field._data = data; + return field; +} + +/** + * Makes a pbg_field representing the given operator type with the specified + * number of child fields. + * @param err Used to store error, if any. + * @param type Type of the operator. + * @param argc Number of arguments. + * @return the new pbg_field. + */ +pbg_field pbg_parse_op(pbg_error* err, pbg_field_type type, int argc) +{ + void* data; + data = malloc(argc * sizeof(int)); + if(data == NULL) + pbg_err_alloc(err, __LINE__, __FILE__); + return pbg_field_init(type, argc, data); +} + +/** + * Makes a field representing a VAR. Attempts to parse the given string as a + * VAR. If an error occurs during conversion, then err will be initialized with + * the relevant error. + * @param err Used to store error, if any. + * @param str String to parse as a VAR. + * @param n Length of str. + * @return a VAR field if successful, a NULL field otherwise. + */ +pbg_field pbg_parse_var(pbg_error* err, char* str, int n) +{ + int size; + void* data; + data = malloc(size = (n-2) * sizeof(char)); + if(data == NULL) + pbg_err_alloc(err, __LINE__, __FILE__); + else + memcpy(data, str+1, n-2); + return pbg_field_init(PBG_LT_VAR, size, data); +} + +/** + * Makes a field representing a DATE. Attempts to parse the given string as a + * DATE. If an error occurs during conversion, then err will be initialized with + * the relevant error. + * @param err Used to store error, if any. + * @param str String to parse as a DATE. + * @param n Length of str. + * @return a DATE field if successful, a NULL field otherwise. + */ +pbg_field pbg_parse_date(pbg_error* err, char* str, int n) +{ + int size; + pbg_lt_date* data; + data = malloc(size = sizeof(pbg_lt_date)); + if(data == NULL) + pbg_err_alloc(err, __LINE__, __FILE__); + else + pbg_todate(data, str, n); + return pbg_field_init(PBG_LT_DATE, size, data); +} + +/** + * Makes a field representing a NUMBER. Attempts to parse the given string as a + * NUMBER. If an error occurs during conversion, then err will be initialized + * with the relevant error. + * @param err Used to store error, if any. + * @param str String to parse as a NUMBER. + * @param n Length of str. + * @return a NUMBER field if successful, a NULL field otherwise. + */ +pbg_field pbg_parse_number(pbg_error* err, char* str, int n) +{ + int size; + pbg_lt_number* data; + data = malloc(size = sizeof(pbg_lt_number)); + if(data == NULL) + pbg_err_alloc(err, __LINE__, __FILE__); + else + pbg_tonumber(data, str, n); + return pbg_field_init(PBG_LT_NUMBER, size, data); +} + +/** + * Makes a field representing a STRING. Attempts to parse the given string as a + * STRING. If an error occurs during conversion, then err will be initialized + * with the relevant error. + * @param err Used to store error, if any. + * @param str String to parse as a STRING. + * @param n Length of str. + * @return a STRING field if successful, a NULL field otherwise. + */ +pbg_field pbg_parse_string(pbg_error* err, char* str, int n) +{ + int size; + pbg_lt_string* data; + data = malloc(size = (n-2) * sizeof(pbg_lt_string)); + if(data == NULL) + pbg_err_alloc(err, __LINE__, __FILE__); + else + memcpy(data, str+1, n-2); + return pbg_field_init(PBG_LT_STRING, size, data); +} + + +/************************* + * * + * FIELD PARSING TOOLKIT * + * * + *************************/ + +/** + * Checks if the operator can legally take the specified number of arguments. + * This function encodes the rules for operator arity and should be modified if + * a new operator is added. + * @param type Type of operator. + * @param numargs Number of arguments to operator. + * @return 1 if the number of arguments can be legally given to the operator, + * 0 if not or if type does not refer to an operator. + */ +int pbg_check_op_arity(pbg_field_type type, int numargs) +{ + int arity = 0; + /* Positive arity specifies "exact arity," i.e. the number of arguments + * must be exact. Negative arity specifies a "minimum arity," i.e. the + * minimum number of arguments needed. */ + switch(type) { + case PBG_OP_NOT: arity = 1; break; + case PBG_OP_AND: arity = -2; break; + case PBG_OP_OR: arity = -2; break; + case PBG_OP_EQ: arity = -2; break; + case PBG_OP_LT: arity = 2; break; + case PBG_OP_GT: arity = 2; break; + case PBG_OP_EXST: arity = -1; break; + case PBG_OP_NEQ: arity = 2; break; + case PBG_OP_LTE: arity = 2; break; + case PBG_OP_GTE: arity = 2; break; + case PBG_OP_TYPE: arity = -2; break; + default: + return 0; + } + if((arity > 0 && numargs != arity) || + (-arity > 0 && numargs < -arity)) + return 0; + return 1; +} + +void pbg_parse(pbg_expr* e, pbg_error* err, char* str) { + pbg_parse_n(e, err, str, strlen(str)); +} + +void pbg_parse_n(pbg_expr* e, pbg_error* err, char* str, int n) +{ + int i; + + int numfields, numvars, numclosings; + int depth, maxdepth, reachedend; + int instring, invar; + + int* stack, stacksz; + int* groupsz, groupi; + int opened; + + int* fields, *lengths, fieldi; + int* closings, closingi; + + int numconstant, numvariable; + + pbg_field_type type; + int* children; + int id = 0; + int start, len; + + /* Always start with a clean error! */ + pbg_err_init(err, PBG_ERR_NONE, 0, NULL, 0, NULL); + + /* Set to NULL to allow for pbg_free to check if needing free. */ + e->_constants = NULL; + e->_variables = NULL; + + /* These are initialized to 0 as they are used as counters for the number + * of each type of field created. In the end they should be equal to the + * associated local variables here. */ + e->_numconst = 0; + e->_numvars = 0; + + /******************************************************************* + * FIRST PASS * + * 1 Count number of groups, fields, and variables. * + * 2 Identify depth of the tree. * + * 3 Ensure group, string, and variable formatting are correct. * + *******************************************************************/ + + numfields = numvars = numclosings = 0; + depth = reachedend = maxdepth = 0; + instring = invar = 0; + for(i = 0; i < n; i++) { + /* Ignore whitespaces. */ + if(pbg_iswhitespace(str[i])) continue; + /* Open a new group. */ + if(str[i] == '(') { + depth++, maxdepth++; + /* Close current group. */ + }else if(str[i] == ')') { + numclosings++, depth--; + if(depth < 0 || (depth == 0 && reachedend)) break; + if(depth == 0 && !reachedend) reachedend = i; + /* Process a new field. */ + }else{ + /* It's a string! */ + if(str[i] == '\'') { + instring = 1; + do i++; while(i != n && !(str[i] == '\'' && str[i-1] != '\\')); + if(i != n) instring = 0; + /* It's a variable! */ + }else if(str[i] == '[') { + invar = 1, numvars++; + do i++; while(i != n && !(str[i] == ']' && str[i-1] != '\\')); + if(i != n) invar = 0; + /* It's literally anything else! */ + }else + while(i != n-1 && !pbg_iswhitespace(str[i+1]) && str[i+1] != '[' && + str[i+1] != '(' && str[i+1] != ')') i++; + numfields++; + } + } + /* Check if there aren't any fields. */ + if(numfields == 0) { + pbg_err_syntax(err, __LINE__, __FILE__, str, 0, + "No fields in expression."); + return; + } + /* Check if there are too many closing parentheses. */ + if(depth < 0) { + pbg_err_syntax(err, __LINE__, __FILE__, str, i, + "Too many closing parentheses."); + return; + } + /* Check if there are not enough closing parentheses. */ + if(depth != 0) { + pbg_err_syntax(err, __LINE__, __FILE__, str, 0, + "Too few closing parentheses."); + return; + } + /* Check if there are multiple (possible) expressions. */ + if(depth == 0 && reachedend && i != n) { + pbg_err_syntax(err, __LINE__, __FILE__, str, reachedend, + "Too many opening parentheses yield multiple expressions."); + return; + } + /* Check if string is left unclosed. */ + if(instring) { + pbg_err_syntax(err, __LINE__, __FILE__, str, instring, + "Unclosed string."); + return; + } + /* Check if variable is left unclosed. */ + if(invar) { + pbg_err_syntax(err, __LINE__, __FILE__, str, invar, + "Unclosed variable."); + return; + } + + /******************************************************************* + * SECOND PASS * + * 1 Compute size of each group. * + * 2 Identify starting index & length of each group. * + * 3 Identify index of each group closing. * + *******************************************************************/ + + /* Ensure we have a stack for TRUE/FALSE standalone literals. */ + if(maxdepth == 0) maxdepth = 1; + /* Use a stack to identify number of fields in each group. */ + stack = malloc(2*maxdepth * sizeof(int)); + + /* Use to record number of fields in each group. Notice that the number of + * groups is equal to the number of closings. */ + groupsz = calloc(numclosings+1, sizeof(int)); + + /* Allocate space to record field starting positions & lengths as well as + * the positions of group closings. */ + fields = (int*) malloc(numfields * sizeof(int)); + lengths = (int*) malloc(numfields * sizeof(int)); + closings = (int*) malloc((numclosings+1) * sizeof(int)); + + /* Compute sizes of constant and variable arrays. */ + numconstant = numfields - numvars; + numvariable = numvars; + + /* Allocate space for constant and variable field arrays. */ + e->_constants = (pbg_field*) malloc(numconstant * sizeof(pbg_field)); + e->_variables = (pbg_field*) malloc(numvariable * sizeof(pbg_field)); + + /* Ensure we got all of the memory we need. */ + if(stack == NULL || groupsz == NULL || fields == NULL || lengths == NULL || + closings == NULL || e->_constants == NULL || e->_variables == NULL) { + free(stack); free(groupsz); + free(fields); free(lengths); free(closings); + pbg_err_alloc(err, __LINE__, __FILE__); + pbg_free(e); + return; + } + + /* Do the work! */ + opened = stacksz = groupi = closingi = fieldi = 0; + stacksz = 1; + stack[0] = 0; + for(i = 0; i < n; i++) { + /* Ignore whitespaces. */ + if(pbg_iswhitespace(str[i])) continue; + /* Open a new group. Push it onto the stack. */ + if(str[i] == '(') { + opened = 1; + if(groupi != 0) { + groupsz[stack[stacksz-1]]++; + stack[stacksz++] = groupi; + } + groupi++; + /* Close current group. Pop group it off of the stack. */ + }else if(str[i] == ')') { + closings[closingi++] = i; + stacksz--; + /* Process a new field. */ + }else{ + /* Save index of the field. */ + fields[fieldi] = i; + /* It's a string! */ + if(str[i] == '\'') { + do i++; while(i != n && !(str[i] == '\'' && str[i-1] != '\\')); + /* It's a variable! */ + }else if(str[i] == '[') { + do i++; while(i != n && !(str[i] == ']' && str[i-1] != '\\')); + /* It's literally anything else! */ + }else + while(i != n-1 && !pbg_iswhitespace(str[i+1]) && str[i+1] != '[' && + str[i+1] != '(' && str[i+1] != ')') i++; + /* Compute length of the field. */ + lengths[fieldi] = i - fields[fieldi] + 1; + /* Identify type of field. */ + type = pbg_gettype(str+fields[fieldi], lengths[fieldi]); + /* Ensure opener is operator, and no other field is an operator. */ + if(opened != pbg_type_isop(type) || (opened = 0)) { + pbg_err_syntax(err, __LINE__, __FILE__, str, fields[fieldi], + "Field ordering not respected."); + free(stack); free(groupsz); + free(fields); free(lengths); free(closings); + pbg_free(e); + return; + } + /* Add field to current group. */ + groupsz[stack[stacksz-1]]++, fieldi++; + } + } + closings[closingi] = n; + + /****************************** + * THIRD PASS * + * 1 Build the final tree. * + ******************************/ + + /* Alias simple stack operations for more readable code. */ + #define pbg_stack_inputcnt stack[2*(stacksz-1)+1] + #define pbg_stack_fieldid stack[2*(stacksz-1)] + + children = NULL; + stacksz = groupi = closingi = 0; + for(fieldi = 0; fieldi < numfields; fieldi++) { + /* Alias field start and field length for easier use. */ + start = fields[fieldi]; + len = lengths[fieldi]; + /* Parsed all inputs to current operator. Pop it from the stack. */ + if(start > closings[closingi]) { + closingi++; + /* Pop from the stack. */ + stacksz--; + id = pbg_stack_fieldid; + /* Restore list of children from parent operator. */ + children = pbg_field_get(e, id)->_data; + } + /* Identify type of field. */ + type = pbg_gettype(str+start, len); + /* It's an operator! Push it onto the stack. */ + if(pbg_type_isop(type)) { + /* Add operator to the tree. */ + id = pbg_store_constant(e, + pbg_parse_op(err, type, groupsz[groupi]-1)); + /* Enforce operator arity. */ + if(pbg_check_op_arity(type, groupsz[groupi]-1) == 0) { + pbg_err_op_arity(err, __LINE__, __FILE__, type, groupsz[groupi]-1); + id = 0; + } + groupi++; + /* Check for errors when adding operator to tree. */ + if(id == 0) break; + /* Add this operator as a child of the parent operator, if any. */ + if(children != NULL) + children[pbg_stack_inputcnt++] = id; + /* Push the operator onto the stack. */ + stacksz++; + pbg_stack_fieldid = id; + pbg_stack_inputcnt = 0; + /* Replace children list with that of the new operator. */ + children = pbg_field_get(e, id)->_data; + /* It's a literal! */ + }else{ + /* It's a variable. */ + if(type == PBG_LT_VAR) + id = pbg_store_variable(e, + pbg_parse_var(err, str+start, len)); + /* It's a date. */ + else if(type == PBG_LT_DATE) + id = pbg_store_constant(e, + pbg_parse_date(err, str+start, len)); + /* It's a number. */ + else if(type == PBG_LT_NUMBER) + id = pbg_store_constant(e, + pbg_parse_number(err, str+start, len)); + /* It's a string. */ + else if(type == PBG_LT_STRING) + id = pbg_store_constant(e, + pbg_parse_string(err, str+start, len)); + /* It's a simple field. */ + else if(type == PBG_LT_TRUE || + type == PBG_LT_FALSE || + type == PBG_LT_TP_DATE || + type == PBG_LT_TP_BOOL || + type == PBG_LT_TP_NUMBER || + type == PBG_LT_TP_STRING) + id = pbg_store_constant(e, + pbg_field_init(type, 0, NULL)); + /* It's an error... */ + else { + pbg_err_unknown_type(err, __LINE__, __FILE__, str+start, n); + id = 0; + } + /* Check for errors when adding literal to tree. */ + if(id == 0) break; + /* Add this literal as a child of the parent operator, if any. */ + if(children != NULL) + children[pbg_stack_inputcnt++] = id; + } + } + /* Free expression if a parse error occurred. */ + if(id == 0) pbg_free(e); + + /* Clean up! */ + free(stack), free(groupsz); + free(fields), free(lengths), free(closings); + + /* Do not perform sanity checks if an error occurred. */ + if(pbg_iserror(err)) + return; + + /* Sanity check: verify we parsed everything we expected. */ + if(e->_numconst != numconstant || e->_numvars != numvariable) { + pbg_err_state(err, __LINE__, __FILE__, + "Not all fields were parsed?"); + return; + } +} + + +/**************************** + * * + * FIELD EVALUATION TOOLKIT * + * * + ****************************/ + +int pbg_evaluate_op_not(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + int child0, result; + child0 = ((int*)field->_data)[0]; + result = pbg_evaluate_r(e, err, pbg_field_get(e, child0)); + if(result == PBG_ERROR) return PBG_ERROR; /* Pass error through. */ + return result == PBG_TRUE ? PBG_FALSE : PBG_TRUE; +} + +int pbg_evaluate_op_and(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + int i, size, childi, result; + size = field->_int; + for(i = 0; i < size; i++) { + childi = ((int*)field->_data)[i]; + result = pbg_evaluate_r(e, err, pbg_field_get(e, childi)); + if(result == PBG_ERROR) return PBG_ERROR; /* Pass error through. */ + if(result == PBG_FALSE) return PBG_FALSE; + } + return PBG_TRUE; +} + +int pbg_evaluate_op_or(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + int i, childi, result; + for(i = 0; i < field->_int; i++) { + childi = ((int*)field->_data)[i]; + result = pbg_evaluate_r(e, err, pbg_field_get(e, childi)); + if(result == PBG_ERROR) return PBG_ERROR; /* Pass error through. */ + if(result == PBG_TRUE) return PBG_TRUE; + } + return PBG_FALSE; +} + +int pbg_evaluate_op_exst(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + int i, childi; + PBG_UNUSED(err); + for(i = 0; i < field->_int; i++) { + childi = ((int*)field->_data)[i]; + if(pbg_field_get(e, childi)->_type == PBG_NULL) + return PBG_FALSE; + } + return PBG_TRUE; +} + +int pbg_evaluate_op_eq(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + int i, child0, childi, result; + pbg_field* c0, *ci; + PBG_UNUSED(err); + /* Ensure type and size of all children are identical. */ + child0 = ((int*)field->_data)[0]; + c0 = pbg_field_get(e, child0); + if(c0->_type == PBG_NULL) { + pbg_err_op_arg_type(err, __LINE__, __FILE__, + "NULL input given to EQ operator."); + return PBG_ERROR; + } + /* We have a bunch of BOOLs! Evaluate them. */ + if(pbg_type_isbool(c0->_type)) { + result = pbg_evaluate_r(e, err, c0); + for(i = 1; i < field->_int; i++) { + childi = ((int*)field->_data)[i]; + ci = pbg_field_get(e, childi); + if(ci->_type == PBG_NULL) { + pbg_err_op_arg_type(err, __LINE__, __FILE__, + "NULL input given to EQ operator."); + return PBG_ERROR; + } + if(result != pbg_evaluate_r(e, err, ci)) + return PBG_FALSE; + } + return PBG_TRUE; + /* We don't have a bunch of BOOLs! Do standard equality test. */ + }else{ + for(i = 1; i < field->_int; i++) { + childi = ((int*)field->_data)[i]; + ci = pbg_field_get(e, childi); + if(ci->_type == PBG_NULL) { + pbg_err_op_arg_type(err, __LINE__, __FILE__, + "NULL input given to EQ operator."); + return PBG_ERROR; + } + if(ci->_int != c0->_int || + ci->_type != c0->_type) + return PBG_FALSE; + /* Ensure each data byte is identical. */ + if(memcmp(ci->_data, c0->_data, c0->_int) != 0) + return PBG_FALSE; + } + return PBG_TRUE; + } +} + +int pbg_evaluate_op_neq(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + int child0, child1; + pbg_field* c0, *c1; + PBG_UNUSED(err); + child0 = ((int*)field->_data)[0], child1 = ((int*)field->_data)[1]; + c0 = pbg_field_get(e, child0), c1 = pbg_field_get(e, child1); + if(c0->_type == PBG_NULL || c1->_type == PBG_NULL) { + pbg_err_op_arg_type(err, __LINE__, __FILE__, + "NULL input given to NEQ operator."); + return PBG_ERROR; + } + /* We have two BOOLs! Evaluate them, and check if they are different. */ + if(pbg_type_isbool(c0->_type) && pbg_type_isbool(c1->_type)) + return (pbg_evaluate_r(e, err, c0) != pbg_evaluate_r(e, err, c1)) ? + PBG_TRUE : PBG_FALSE; + /* We don't have a bunch of BOOLs! Do standard difference check. */ + else return (c1->_type != c0->_type || c1->_int != c0->_int || + memcmp(c1->_data, c0->_data, c0->_int)) ? PBG_TRUE : PBG_FALSE; +} + +int pbg_evaluate_op_order(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + int result; + int child0, child1; + pbg_field* c0, *c1; + child0 = ((int*)field->_data)[0], child1 = ((int*)field->_data)[1]; + c0 = pbg_field_get(e, child0), c1 = pbg_field_get(e, child1); + if(c0->_type == PBG_NULL || c1->_type == PBG_NULL) { + pbg_err_op_arg_type(err, __LINE__, __FILE__, + "NULL input given to comparison operator."); + return PBG_ERROR; + } + result = -2; + /* Both are NUMBERs. */ + if(c0->_type == PBG_LT_NUMBER && + c1->_type == PBG_LT_NUMBER) + result = pbg_cmpnumber(c0->_data, c1->_data); + /* Both are DATEs. */ + if(c0->_type == PBG_LT_DATE && + c1->_type == PBG_LT_DATE) + result = pbg_cmpdate(c0->_data, c1->_data); + /* Both are STRINGs. */ + if(c0->_type == PBG_LT_STRING && + c1->_type == PBG_LT_STRING) + result = pbg_cmpstring(c0->_data, c1->_data, c0->_int); + /* Both are BOOLs. */ + if(pbg_type_isbool(c0->_type) && pbg_type_isbool(c1->_type)) + result = pbg_evaluate_r(e, err, c0) - pbg_evaluate_r(e, err, c1); + /* Check if mismatched or invalid types. */ + if(result == -2) { + pbg_err_op_arg_type(err, __LINE__, __FILE__, + "Unknown input type to comparison operator"); + return PBG_ERROR; + /* Compare results according to type of comparison operator. */ + }else{ + if(field->_type == PBG_OP_LT) return result < 0 ? PBG_TRUE : PBG_FALSE; + if(field->_type == PBG_OP_GT) return result > 0 ? PBG_TRUE : PBG_FALSE; + if(field->_type == PBG_OP_LTE) return result <= 0 ? PBG_TRUE : PBG_FALSE; + if(field->_type == PBG_OP_GTE) return result >= 0 ? PBG_TRUE : PBG_FALSE; + pbg_err_state(err, __LINE__, __FILE__, + "Unknown result from select comparison function."); + return PBG_ERROR; + } +} + +int pbg_evaluate_op_type(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + int i, child0, childi; + pbg_field* c0, *ci; + pbg_field_type type; + child0 = ((int*)field->_data)[0]; + c0 = pbg_field_get(e, child0); + type = c0->_type; + /* Ensure the first argument is a type literal. */ + if(type < PBG_MIN_LT_TP || type > PBG_MAX_LT_TP) { + pbg_err_op_arg_type(err, __LINE__, __FILE__, + "First input to TYPE operator must be a type literal."); + return PBG_ERROR; + } + /* Verify types of all trailing arguments. */ + for(i = 1; i < field->_int; i++) { + childi = ((int*)field->_data)[i]; + ci = pbg_field_get(e, childi); + if(type == PBG_LT_TP_BOOL && !pbg_type_isbool(ci->_type)) + return PBG_FALSE; + if(type == PBG_LT_TP_DATE && ci->_type != PBG_LT_DATE) + return PBG_FALSE; + if(type == PBG_LT_TP_NUMBER && ci->_type != PBG_LT_NUMBER) + return PBG_FALSE; + if(type == PBG_LT_TP_STRING && ci->_type != PBG_LT_STRING) + return PBG_FALSE; + } + return PBG_TRUE; +} + +int pbg_evaluate_r(pbg_expr* e, pbg_error* err, pbg_field* field) +{ + if(pbg_type_isbool(field->_type)) { + switch(field->_type) { + case PBG_OP_NOT: return pbg_evaluate_op_not(e, err, field); + case PBG_OP_AND: return pbg_evaluate_op_and(e, err, field); + case PBG_OP_OR: return pbg_evaluate_op_or(e, err, field); + case PBG_OP_EXST: return pbg_evaluate_op_exst(e, err, field); + case PBG_OP_EQ: return pbg_evaluate_op_eq(e, err, field); + case PBG_OP_NEQ: return pbg_evaluate_op_neq(e, err, field); + case PBG_OP_LT: + case PBG_OP_GT: + case PBG_OP_LTE: + case PBG_OP_GTE: return pbg_evaluate_op_order(e, err, field); + case PBG_OP_TYPE: return pbg_evaluate_op_type(e, err, field); + case PBG_LT_TRUE: return PBG_TRUE; + case PBG_LT_FALSE: return PBG_FALSE; + default: pbg_err_state(err, __LINE__, __FILE__, + "Unsupported operation."); + } + } + pbg_err_state(err, __LINE__, __FILE__, + "Cannot evaluate a non-BOOL value."); + return PBG_ERROR; +} + +int pbg_evaluate(pbg_expr* e, pbg_error* err, pbg_field (*dict)(char*, int)) +{ + int i, result; + pbg_field* newvars, *var, *oldvars; + + /* Always start with a clean error! */ + pbg_err_init(err, PBG_ERR_NONE, 0, NULL, 0, NULL); + + /* Variable resolution. Lookup every variable in provided dictionary. */ + newvars = (pbg_field*) malloc(e->_numvars * sizeof(pbg_field)); + if(newvars == NULL) { + pbg_err_alloc(err, __LINE__, __FILE__); + return PBG_ERROR; + } + for(i = 0; i < e->_numvars; i++) { + var = e->_variables+i; + newvars[i] = dict((char*)(var->_data), var->_int); + } + + /* Swap out variable literals with dictionary equivalents. */ + oldvars = e->_variables; + e->_variables = newvars; + + /* Evaluate expression! */ + result = pbg_evaluate_r(e, err, e->_constants); + + /* Restore old variable literal array. */ + e->_variables = oldvars; + + /* Clean up malloc'd memory. */ + for(i = 0; i < e->_numvars; i++) + pbg_field_free(newvars+i); + free(newvars); + + /* Done! */ + return result; +} + + +/************************ + * * + * JANITORIAL FUNCTIONS * + * * + ************************/ + +void pbg_free(pbg_expr* e) +{ + int i; + + /* Free individual constant fields. Some do not have _data malloc'd. */ + for(i = e->_numconst-1; i >= 0; i--) + pbg_field_free(e->_constants+i); + + /* Free individual variable fields. All have _data malloc'd. */ + for(i = 0; i < e->_numvars; i++) + pbg_field_free(e->_variables+i); + + /* Free internal field arrays. */ + if(e->_constants != NULL) { + free(e->_constants); + e->_constants = NULL; + } + if(e->_variables != NULL) { + free(e->_variables); + e->_variables = NULL; + } +} + + +/********************************* + * * + * CONVERSION & CHECKING TOOLKIT * + * * + *********************************/ + +/** + * Translates the given pbg_field_type to a human-readable string. + * @param type PBG field type to translate. + * @return String representation of the given field type. + */ +char* pbg_field_type_str(pbg_field_type type) +{ + switch(type) { + case PBG_LT_TRUE: return "PBG_LT_TRUE"; + case PBG_LT_FALSE: return "PBG_LT_FALSE"; + case PBG_LT_NUMBER: return "PBG_LT_NUMBER"; + case PBG_LT_STRING: return "PBG_LT_STRING"; + case PBG_LT_DATE: return "PBG_LT_DATE"; + case PBG_LT_VAR: return "PBG_LT_VAR"; + case PBG_OP_NOT: return "PBG_OP_NOT"; + case PBG_OP_AND: return "PBG_OP_AND"; + case PBG_OP_OR: return "PBG_OP_OR"; + case PBG_OP_EQ: return "PBG_OP_EQ"; + case PBG_OP_LT: return "PBG_OP_LT"; + case PBG_OP_GT: return "PBG_OP_GT"; + case PBG_OP_EXST: return "PBG_OP_EXST"; + case PBG_OP_NEQ: return "PBG_OP_NEQ"; + case PBG_OP_LTE: return "PBG_OP_LTE"; + case PBG_OP_GTE: return "PBG_OP_GTE"; + case PBG_LT_TP_DATE: return "PBG_LT_TP_DATE"; + case PBG_LT_TP_BOOL: return "PBG_LT_TP_BOOL"; + case PBG_LT_TP_NUMBER: return "PBG_LT_TP_NUMBER"; + case PBG_LT_TP_STRING: return "PBG_LT_TP_STRING"; + default: return "PBG_NULL"; + } +} + +/** + * Translates the given pbg_error_type to a human-readable string. + * @param type PBG error type to translate. + * @return String representation of the given error type. + */ +char* pbg_error_str(pbg_error_type type) +{ + switch(type) { + case PBG_ERR_NONE: return "PBG_ERR_NONE"; + case PBG_ERR_ALLOC: return "PBG_ERR_ALLOC"; + case PBG_ERR_STATE: return "PBG_ERR_STATE"; + case PBG_ERR_SYNTAX: return "PBG_ERR_SYNTAX"; + case PBG_ERR_UNKNOWN_TYPE: return "PBG_ERR_UNKNOWN_TYPE"; + case PBG_ERR_OP_ARITY: return "PBG_ERR_OP_ARITY"; + case PBG_ERR_OP_ARG_TYPE: return "PBG_ERR_OP_ARG_TYPE"; + } + return "PBG_ERR_???"; +} + +int pbg_iserror(pbg_error* err) { + return err->_type != PBG_ERR_NONE; +} + +pbg_field_type pbg_gettype(char* str, int n) +{ + /* Is it a literal? */ + if(pbg_istrue(str, n)) return PBG_LT_TRUE; + if(pbg_isfalse(str, n)) return PBG_LT_FALSE; + if(pbg_isnumber(str, n)) return PBG_LT_NUMBER; + if(pbg_isstring(str, n)) return PBG_LT_STRING; + if(pbg_isdate(str, n)) return PBG_LT_DATE; + if(pbg_isvar(str, n)) return PBG_LT_VAR; + if(pbg_istypedate(str, n)) return PBG_LT_TP_DATE; + if(pbg_istypebool(str, n)) return PBG_LT_TP_BOOL; + if(pbg_istypenumber(str, n)) return PBG_LT_TP_NUMBER; + if(pbg_istypestring(str, n)) return PBG_LT_TP_STRING; + + /* Is it an operator? */ + if(n == 1) { + if(str[0] == '!') return PBG_OP_NOT; + if(str[0] == '&') return PBG_OP_AND; + if(str[0] == '|') return PBG_OP_OR; + if(str[0] == '=') return PBG_OP_EQ; + if(str[0] == '<') return PBG_OP_LT; + if(str[0] == '>') return PBG_OP_GT; + if(str[0] == '?') return PBG_OP_EXST; + if(str[0] == '@') return PBG_OP_TYPE; + } + if(n == 2) { + if(str[0] == '!' && str[1] == '=') return PBG_OP_NEQ; + if(str[0] == '<' && str[1] == '=') return PBG_OP_LTE; + if(str[0] == '>' && str[1] == '=') return PBG_OP_GTE; + } + + /* It isn't anything! */ + return PBG_NULL; +} + +int pbg_istypedate(char* str, int n) { + return n == 4 && + str[0]=='D' && + str[1]=='A' && + str[2]=='T' && + str[3]=='E'; +} + +int pbg_istypenumber(char* str, int n) { + return n == 6 && + str[0]=='N' && + str[1]=='U' && + str[2]=='M' && + str[3]=='B' && + str[4]=='E' && + str[5]=='R'; +} + +int pbg_istypebool(char* str, int n) { + return n == 4 && + str[0]=='B' && + str[1]=='O' && + str[2]=='O' && + str[3]=='L'; +} + +int pbg_istypestring(char* str, int n) { + return n == 6 && + str[0]=='S' && + str[1]=='T' && + str[2]=='R' && + str[3]=='I' && + str[4]=='N' && + str[5]=='G'; +} + +int pbg_istrue(char* str, int n) { + return n == 4 && + str[0]=='T' && + str[1]=='R' && + str[2]=='U' && + str[3]=='E'; +} + +int pbg_isfalse(char* str, int n) { + return n == 5 && + str[0]=='F' && + str[1]=='A' && + str[2]=='L' && + str[3]=='S' && + str[4]=='E'; +} + +int pbg_isnumber(char* str, int n) +{ + int i; + + /* Start at the beginning of the string. */ + i = 0; + + /* Check if negative or positive */ + if(str[i] == '-' || str[i] == '+') i++; + /* Otherwise, ensure first character is a digit. */ + else if(!pbg_isdigit(str[i])) + return 0; + + /* Parse everything before the dot. */ + if(str[i] != '0' && pbg_isdigit(str[i])) { + while(i != n && pbg_isdigit(str[i])) i++; + if(i != n && !pbg_isdigit(str[i]) && str[i] != '.') return 0; + }else if(str[i] == '0') { + if(++i != n && !(str[i] == '.' || str[i] == 'e' || str[i] == 'E')) return 0; + } + + /* Parse everything after the dot. */ + if(str[i] == '.') { + /* Last character must be a digit. */ + if(i++ == n-1) return 0; + /* Exhaust all digits. */ + while(i != n && pbg_isdigit(str[i])) i++; + if(i != n && !pbg_isdigit(str[i]) && str[i] != 'e' && str[i] != 'E') return 0; + } + + /* Parse everything after the exponent. */ + if(str[i] == 'e' || str[i] == 'E') { + /* Last character must be a digit. */ + if(i++ == n-1) return 0; + /* Parse positive or negative sign. */ + if(str[i] == '-' || str[i] == '+') i++; + /* Exhaust all digits. */ + while(i != n && pbg_isdigit(str[i])) i++; + if(i != n && !pbg_isdigit(str[i])) return 0; + } + + /* Probably a number! */ + return 1; +} + +void pbg_tonumber(pbg_lt_number* ptr, char* str, int n) { + PBG_UNUSED(n); + ptr->_val = atof(str); +} + +int pbg_cmpnumber(pbg_lt_number* n1, pbg_lt_number* n2) { + if(n1->_val < n2->_val) return -1; + if(n1->_val > n2->_val) return 1; + return 0; +} + +int pbg_cmpdate(pbg_lt_date* n1, pbg_lt_date* n2) { + if(n1->_YYYY < n2->_YYYY) return -1; + if(n1->_YYYY > n2->_YYYY) return 1; + if(n1->_MM < n2->_MM) return -1; + if(n1->_MM > n2->_MM) return 1; + if(n1->_DD < n2->_DD) return -1; + if(n1->_DD > n2->_DD) return 1; + return 0; +} + +int pbg_cmpstring(pbg_lt_string* s1, pbg_lt_string* s2, int n) { + return strncmp(s1, s2, n); +} + +int pbg_isvar(char* str, int n) { + return str[0] == '[' && str[n-1] == ']'; +} + +int pbg_isstring(char* str, int n) { + return str[0] == '\'' && str[n-1] == '\''; +} + +int pbg_isdate(char* str, int n) { + return n == 10 && + pbg_isdigit(str[0]) && pbg_isdigit(str[1]) && + pbg_isdigit(str[2]) && pbg_isdigit(str[3]) && + str[4] == '-' && + pbg_isdigit(str[5]) && pbg_isdigit(str[6]) && + str[7] == '-' && + pbg_isdigit(str[8]) && pbg_isdigit(str[9]); +} + +void pbg_todate(pbg_lt_date* ptr, char* str, int n) { + if(n != 10) return; + ptr->_YYYY = (str[0]-'0')*1000 + (str[1]-'0')*100 + (str[2]-'0')*10 + (str[3]-'0'); + ptr->_MM = (str[5]-'0')*10 + (str[6]-'0'); + ptr->_DD = (str[8]-'0')*10 + (str[9]-'0'); +} + +/** + * Checks if the given type is an operator, TRUE, or FALSE. Useful for checking + * if both arguments will have a valid return value from pbg_evaluate_r. + * @param type Type to check. + * @return 1 if the given type is TRUE, FALSE, or an operator, + * 0 otherwise. + */ +int pbg_type_isbool(pbg_field_type type) { + return type == PBG_LT_TRUE || type == PBG_LT_FALSE || + (type < PBG_MAX_OP && type > PBG_MIN_OP); +} + +/** + * Checks if the given type is an operator. + * @param type Type to check. + * @return 1 if the given type is an operator, + * 0 otherwise. + */ +int pbg_type_isop(pbg_field_type type) { + return type > PBG_MIN_OP && type < PBG_MAX_OP; +} + + +/******************** + * * + * HELPER FUNCTIONS * + * * + ********************/ + +/** + * Checks if the given character is a digit. + * @param c Character to check. + */ +int pbg_isdigit(char c) { return c >= '0' && c <= '9'; } + +/** + * Checks if the given character is whitespace. + * @param c Character to check. + */ +int pbg_iswhitespace(char c) { return c==' ' || c=='\t' || c=='\n'; } diff --git a/src/pbg.h b/src/pbg.h index 36a1da6..98a3370 120000..100644 --- a/src/pbg.h +++ b/src/pbg.h @@ -1 +1,239 @@ -../pbg/pbg.h
\ No newline at end of file +#ifndef __PBG_H__ +#define __PBG_H__ + +/********************************************************* + * * + * Prefix Boolean Grammar (PBG), a lightweight C library * + * By Tyler J. Daddio, November 2018 * + * * + *********************************************************/ + +/* Used to suppress compiler warnings for intentionally unused arguments. This + * isn't as foolproof as GCC's unused attribute, but it is not compiler- + * dependent, which is just dandy. */ +#define PBG_UNUSED(x) (void)(x) + +/* Used to represent the result of an expression evaluation. */ +#define PBG_FALSE 0 +#define PBG_TRUE 1 +#define PBG_ERROR -1 + +/***************************** + * * + * EXPRESSION REPRESENTATION * + * * + *****************************/ + +/** + * Types of PBG fields. + */ +typedef enum { + PBG_NULL, /* NULL: Unknown field type */ + + /* Type literals. */ + PBG_MIN_LT_TP, + PBG_LT_TP_DATE, /* DATE TYPE literal */ + PBG_LT_TP_BOOL, /* TRUE/FALSE TYPE literal */ + PBG_LT_TP_NUMBER, /* NUMBER TYPE literal */ + PBG_LT_TP_STRING, /* STRING TYPE literal */ + /* Add more TYPE literals here. */ + PBG_MAX_LT_TP, + + /* Literals. */ + PBG_MIN_LT, + PBG_LT_TRUE, /* TRUE literal */ + PBG_LT_FALSE, /* FALSE literal */ + PBG_LT_NUMBER, /* NUMBER literal */ + PBG_LT_STRING, /* STRING literal */ + PBG_LT_DATE, /* DATE literal */ + PBG_LT_VAR, /* VARiable literal */ + /* Add more literals here. */ + PBG_MAX_LT, + + /* Operators. */ + PBG_MIN_OP, + PBG_OP_NOT, /* ! NOT */ + PBG_OP_AND, /* & AND */ + PBG_OP_OR, /* | OR */ + PBG_OP_EQ, /* = EQUAL */ + PBG_OP_LT, /* < LESS THAN */ + PBG_OP_GT, /* > GREATER THAN */ + PBG_OP_EXST, /* ? EXISTS */ + PBG_OP_NEQ, /* != NOT EQUAL */ + PBG_OP_LTE, /* <= LESS THAN OR EQUAL TO */ + PBG_OP_GTE, /* >= GREATER THAN OR EQUAL TO */ + PBG_OP_TYPE, /* @ TYPE OF */ + /* Add more operators here. */ + PBG_MAX_OP +} pbg_field_type; + +/** + * This struct represents a PBG field. A field can be either a literal or an + * operator. This is determined by its type. For operators, the data pointer + * describes a list of pointers to other fields in the abstract syntax tree. + * For constants, it describes data relevant to the field type. + */ +typedef struct { + pbg_field_type _type; /* Node type, determines the type/size of data. */ + int _int; /* Type determines what this is used for! */ + void* _data; /* Arbitrary data! */ +} pbg_field; + +/** + * This struct represents a PBG expression. There are two arrays in this + * representation: one for constants, and one for variables. Both types are + * represented by fields. + */ +typedef struct { + pbg_field* _constants; /* Constants. */ + pbg_field* _variables; /* Variables. */ + int _numconst; /* Number of constants. */ + int _numvars; /* Number of variables. */ +} pbg_expr; + + +/************************ + * * + * ERROR REPRESENTATION * + * * + ************************/ + +/** + * Type specifiers for all possible PBG errors. + */ +typedef enum { + PBG_ERR_NONE, + PBG_ERR_ALLOC, + PBG_ERR_STATE, + PBG_ERR_SYNTAX, + PBG_ERR_UNKNOWN_TYPE, + PBG_ERR_OP_ARITY, + PBG_ERR_OP_ARG_TYPE +} pbg_error_type; + +/** + * Represents a PBG error. Errors may be generated during parsing and + * evaluation and should be checked by the caller. + */ +typedef struct { + pbg_error_type _type; /* Error type. */ + int _line; /* Line of file where error occurred. */ + char* _file; /* File in which error occurred. */ + int _int; /* Type determines what this is used for! */ + void* _data; /* Data to be included with error report. */ +} pbg_error; + + +/*************** + * * + * EXPRESSIONS * + * * + ***************/ + +/** + * Parses the string as a boolean expression in Prefix Boolean Grammar. + * @param e PBG expression instance to initialize. + * @param err Container to store error, if any occurs. + * @param str String to parse. This must be terminated with '\0'. + */ +void pbg_parse(pbg_expr* e, pbg_error* err, char* str); + +/** + * Parses the string as a boolean expression in Prefix Boolean Grammar. + * @param e PBG expression instance to initialize. + * @param err Container to store error, if any occurs. + * @param str String to parse. + * @param n Length of the string. + */ +void pbg_parse_n(pbg_expr* e, pbg_error* err, char* str, int n); + +/** + * Evaluates the PBG expression with the provided assignments. + * @param e PBG expression to evaluate. + * @param err Container to store error, if any occurs. + * @param dict Dictionary used to resolve VAR names. + * @return 1 if the PBG expression evaluates to true with the given dictionary. + * 0 otherwise. + */ +int pbg_evaluate(pbg_expr* e, pbg_error* err, pbg_field (*dict)(char*, int)); + +/** + * Destroys the PBG expression instance and frees all associated resources. + * This function does not free the provided pointer. + * @param e PBG expression to destroy. + */ +void pbg_free(pbg_expr* e); + + +/************** + * * + * FIELDS * + * * + **************/ + +/** + * Makes a field representing a DATE. + * @param year Year of the date. + * @param month Month of the date. + * @param day Day of the date. + * @return a new DATE field. + */ +pbg_field pbg_make_date(int year, int month, int day); + +/** + * Makes a field representing a BOOL. + * @param truth Truth value of the new BOOL. + * @return a new BOOL field. + */ +pbg_field pbg_make_bool(int truth); + +/** + * Makes a field representing a NUMBER. + * @param value Numeric value of the NUMBER. + * @return a new NUMBER field. + */ +pbg_field pbg_make_number(double value); + +/** + * Makes a field representing a STRING. + * @param value Value of the STRING. + * @return a new STRING field. + */ +pbg_field pbg_make_string(char* str); + +/** + * Makes a field representing NULL. + * @return a new NULL field. + */ +pbg_field pbg_make_null(void); + + +/*************** + * * + * ERRORS * + * * + ***************/ + +/** + * Checks if the given error has been initialized with error data. + * @param err Error to check. + * @return 1 if the given error has been initialized, 0 otherwise. + */ +int pbg_iserror(pbg_error* err); + +/** + * Prints a human-readable representation of the given pbg_error to the + * standard output. + * @param err Error to print. + */ +void pbg_error_print(pbg_error* err); + +/** + * Frees resources being used by the given error, if any. This function does + * not free the provided pointer. + * @param e PBG error to clean up. + */ +void pbg_error_free(pbg_error* e); + + +#endif /* __PBG_H__ */ diff --git a/src/teeny-sha1.c b/src/teeny-sha1.c index 4208eb3..69e5cc9 120000..100644 --- a/src/teeny-sha1.c +++ b/src/teeny-sha1.c @@ -1 +1,206 @@ -../teeny-sha1/teeny-sha1.c
\ No newline at end of file +/** + * Cloned from https://github.com/CTrabant/teeny-sha1 + * in commit f05a2d0019e12850bb482274c1a21ae7a4fb84bd + */ + +/******************************************************************************* + * Teeny SHA-1 + * + * The below sha1digest() calculates a SHA-1 hash value for a + * specified data buffer and generates a hex representation of the + * result. This implementation is a re-forming of the SHA-1 code at + * https://github.com/jinqiangshou/EncryptionLibrary. + * + * Copyright (c) 2017 CTrabant + * + * License: MIT, see included LICENSE file for details. + * + * To use the sha1digest() function either copy it into an existing + * project source code file or include this file in a project and put + * the declaration (example below) in the sources files where needed. + ******************************************************************************/ + +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +/* Declaration: +extern int sha1digest(uint8_t *digest, char *hexdigest, const uint8_t *data, size_t databytes); +*/ + +/******************************************************************************* + * sha1digest: https://github.com/CTrabant/teeny-sha1 + * + * Calculate the SHA-1 value for supplied data buffer and generate a + * text representation in hexadecimal. + * + * Based on https://github.com/jinqiangshou/EncryptionLibrary, credit + * goes to @jinqiangshou, all new bugs are mine. + * + * @input: + * data -- data to be hashed + * databytes -- bytes in data buffer to be hashed + * + * @output: + * digest -- the result, MUST be at least 20 bytes + * hexdigest -- the result in hex, MUST be at least 41 bytes + * + * At least one of the output buffers must be supplied. The other, if not + * desired, may be set to NULL. + * + * @return: 0 on success and non-zero on error. + ******************************************************************************/ +int +sha1digest(uint8_t *digest, char *hexdigest, const uint8_t *data, size_t databytes) +{ +#define SHA1ROTATELEFT(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits)))) + + uint32_t W[80]; + uint32_t H[] = {0x67452301, + 0xEFCDAB89, + 0x98BADCFE, + 0x10325476, + 0xC3D2E1F0}; + uint32_t a; + uint32_t b; + uint32_t c; + uint32_t d; + uint32_t e; + uint32_t f = 0; + uint32_t k = 0; + + uint32_t idx; + uint32_t lidx; + uint32_t widx; + uint32_t didx = 0; + + int32_t wcount; + uint32_t temp; + uint64_t databits = ((uint64_t)databytes) * 8; + uint32_t loopcount = (databytes + 8) / 64 + 1; + uint32_t tailbytes = 64 * loopcount - databytes; + uint8_t datatail[128] = {0}; + + if (!digest && !hexdigest) + return -1; + + if (!data) + return -1; + + /* Pre-processing of data tail (includes padding to fill out 512-bit chunk): + Add bit '1' to end of message (big-endian) + Add 64-bit message length in bits at very end (big-endian) */ + datatail[0] = 0x80; + datatail[tailbytes - 8] = (uint8_t) (databits >> 56 & 0xFF); + datatail[tailbytes - 7] = (uint8_t) (databits >> 48 & 0xFF); + datatail[tailbytes - 6] = (uint8_t) (databits >> 40 & 0xFF); + datatail[tailbytes - 5] = (uint8_t) (databits >> 32 & 0xFF); + datatail[tailbytes - 4] = (uint8_t) (databits >> 24 & 0xFF); + datatail[tailbytes - 3] = (uint8_t) (databits >> 16 & 0xFF); + datatail[tailbytes - 2] = (uint8_t) (databits >> 8 & 0xFF); + datatail[tailbytes - 1] = (uint8_t) (databits >> 0 & 0xFF); + + /* Process each 512-bit chunk */ + for (lidx = 0; lidx < loopcount; lidx++) + { + /* Compute all elements in W */ + memset (W, 0, 80 * sizeof (uint32_t)); + + /* Break 512-bit chunk into sixteen 32-bit, big endian words */ + for (widx = 0; widx <= 15; widx++) + { + wcount = 24; + + /* Copy byte-per byte from specified buffer */ + while (didx < databytes && wcount >= 0) + { + W[widx] += (((uint32_t)data[didx]) << wcount); + didx++; + wcount -= 8; + } + /* Fill out W with padding as needed */ + while (wcount >= 0) + { + W[widx] += (((uint32_t)datatail[didx - databytes]) << wcount); + didx++; + wcount -= 8; + } + } + + /* Extend the sixteen 32-bit words into eighty 32-bit words, with potential optimization from: + "Improving the Performance of the Secure Hash Algorithm (SHA-1)" by Max Locktyukhin */ + for (widx = 16; widx <= 31; widx++) + { + W[widx] = SHA1ROTATELEFT ((W[widx - 3] ^ W[widx - 8] ^ W[widx - 14] ^ W[widx - 16]), 1); + } + for (widx = 32; widx <= 79; widx++) + { + W[widx] = SHA1ROTATELEFT ((W[widx - 6] ^ W[widx - 16] ^ W[widx - 28] ^ W[widx - 32]), 2); + } + + /* Main loop */ + a = H[0]; + b = H[1]; + c = H[2]; + d = H[3]; + e = H[4]; + + for (idx = 0; idx <= 79; idx++) + { + if (idx <= 19) + { + f = (b & c) | ((~b) & d); + k = 0x5A827999; + } + else if (idx >= 20 && idx <= 39) + { + f = b ^ c ^ d; + k = 0x6ED9EBA1; + } + else if (idx >= 40 && idx <= 59) + { + f = (b & c) | (b & d) | (c & d); + k = 0x8F1BBCDC; + } + else if (idx >= 60 && idx <= 79) + { + f = b ^ c ^ d; + k = 0xCA62C1D6; + } + temp = SHA1ROTATELEFT (a, 5) + f + e + k + W[idx]; + e = d; + d = c; + c = SHA1ROTATELEFT (b, 30); + b = a; + a = temp; + } + + H[0] += a; + H[1] += b; + H[2] += c; + H[3] += d; + H[4] += e; + } + + /* Store binary digest in supplied buffer */ + if (digest) + { + for (idx = 0; idx < 5; idx++) + { + digest[idx * 4 + 0] = (uint8_t) (H[idx] >> 24); + digest[idx * 4 + 1] = (uint8_t) (H[idx] >> 16); + digest[idx * 4 + 2] = (uint8_t) (H[idx] >> 8); + digest[idx * 4 + 3] = (uint8_t) (H[idx]); + } + } + + /* Store hex version of digest in supplied buffer */ + if (hexdigest) + { + snprintf (hexdigest, 41, "%08x%08x%08x%08x%08x", + H[0],H[1],H[2],H[3],H[4]); + } + + return 0; +} /* End of sha1digest() */ |