From fac10ea799fe9b6158d74f66d6ad46536d38a545 Mon Sep 17 00:00:00 2001 From: Patrick McHardy Date: Wed, 18 Mar 2009 04:55:00 +0100 Subject: Initial commit --- src/expression.c | 622 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 622 insertions(+) create mode 100644 src/expression.c (limited to 'src/expression.c') diff --git a/src/expression.c b/src/expression.c new file mode 100644 index 00000000..66a8793f --- /dev/null +++ b/src/expression.c @@ -0,0 +1,622 @@ +/* + * Copyright (c) 2008 Patrick McHardy + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + * + * Development of this code funded by Astaro AG (http://www.astaro.com/) + */ + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +struct expr *expr_alloc(const struct location *loc, const struct expr_ops *ops, + const struct datatype *dtype, enum byteorder byteorder, + unsigned int len) +{ + struct expr *expr; + + expr = xzalloc(sizeof(*expr)); + expr->location = *loc; + expr->ops = ops; + expr->dtype = dtype; + expr->byteorder = byteorder; + expr->len = len; + expr->refcnt = 1; + init_list_head(&expr->list); + return expr; +} + +struct expr *expr_get(struct expr *expr) +{ + expr->refcnt++; + return expr; +} + +void expr_free(struct expr *expr) +{ + if (expr == NULL) + return; + if (--expr->refcnt > 0) + return; + if (expr->ops->destroy) + expr->ops->destroy(expr); + xfree(expr); +} + +void expr_print(const struct expr *expr) +{ + expr->ops->print(expr); +} + +void expr_describe(const struct expr *expr) +{ + const struct datatype *dtype = expr->dtype; + const char *delim = ""; + + printf("%s expression, datatype %s", expr->ops->name, dtype->name); + if (dtype->basetype != NULL) { + printf(" (basetype "); + for (dtype = dtype->basetype; dtype != NULL; + dtype = dtype->basetype) { + printf("%s%s", delim, dtype->name); + delim = ", "; + } + printf(")"); + } + + if (expr_basetype(expr)->type == TYPE_STRING) { + if (expr->len) + printf(", %u characters", expr->len / BITS_PER_BYTE); + else + printf(", dynamic length"); + } else + printf(", %u bits", expr->len); + + printf("\n"); + + if (expr->dtype->sym_tbl != NULL) { + printf("\npre-defined symbolic constants:\n"); + symbol_table_print(expr->dtype->sym_tbl); + } +} + +void expr_set_type(struct expr *expr, const struct datatype *dtype, + enum byteorder byteorder) +{ + if (expr->ops->set_type) + expr->ops->set_type(expr, dtype, byteorder); + else { + expr->dtype = dtype; + expr->byteorder = byteorder; + } +} + +const struct datatype *expr_basetype(const struct expr *expr) +{ + const struct datatype *type = expr->dtype; + + while (type->basetype != NULL) + type = type->basetype; + return type; +} + +int __fmtstring(4, 5) expr_binary_error(struct eval_ctx *ctx, + const struct expr *e1, const struct expr *e2, + const char *fmt, ...) +{ + struct error_record *erec; + va_list ap; + + va_start(ap, fmt); + erec = erec_vcreate(EREC_ERROR, &e1->location, fmt, ap); + if (e2 != NULL) + erec_add_location(erec, &e2->location); + va_end(ap); + erec_queue(erec, ctx->msgs); + return -1; +} + +static void verdict_expr_print(const struct expr *expr) +{ + datatype_print(expr); +} + +static void verdict_expr_destroy(struct expr *expr) +{ + xfree(expr->chain); +} + +static const struct expr_ops verdict_expr_ops = { + .type = EXPR_VERDICT, + .name = "verdict", + .print = verdict_expr_print, + .destroy = verdict_expr_destroy, +}; + +struct expr *verdict_expr_alloc(const struct location *loc, + int verdict, const char *chain) +{ + struct expr *expr; + + expr = expr_alloc(loc, &verdict_expr_ops, &verdict_type, + BYTEORDER_INVALID, 0); + expr->verdict = verdict; + if (chain != NULL) + expr->chain = chain; + expr->flags = EXPR_F_CONSTANT | EXPR_F_SINGLETON; + return expr; +} + +static void symbol_expr_print(const struct expr *expr) +{ + printf("%s", expr->identifier); +} + +static void symbol_expr_destroy(struct expr *expr) +{ + xfree(expr->identifier); +} + +static const struct expr_ops symbol_expr_ops = { + .type = EXPR_SYMBOL, + .name = "symbol", + .print = symbol_expr_print, + .destroy = symbol_expr_destroy, +}; + +struct expr *symbol_expr_alloc(const struct location *loc, + const char *identifier) +{ + struct expr *expr; + + expr = expr_alloc(loc, &symbol_expr_ops, &invalid_type, + BYTEORDER_INVALID, 0); + expr->identifier = xstrdup(identifier); + return expr; +} + +static void constant_expr_print(const struct expr *expr) +{ + datatype_print(expr); +} + +static void constant_expr_destroy(struct expr *expr) +{ + mpz_clear(expr->value); +} + +static const struct expr_ops constant_expr_ops = { + .type = EXPR_VALUE, + .name = "value", + .print = constant_expr_print, + .destroy = constant_expr_destroy, +}; + +struct expr *constant_expr_alloc(const struct location *loc, + const struct datatype *dtype, + enum byteorder byteorder, + unsigned int len, const void *data) +{ + struct expr *expr; + + expr = expr_alloc(loc, &constant_expr_ops, dtype, byteorder, len); + expr->flags = EXPR_F_CONSTANT | EXPR_F_SINGLETON; + + mpz_init2(expr->value, len); + if (data != NULL) + mpz_import_data(expr->value, data, byteorder, + div_round_up(len, BITS_PER_BYTE)); + + return expr; +} + +struct expr *constant_expr_join(const struct expr *e1, const struct expr *e2) +{ + unsigned int len = (e1->len + e2->len) / BITS_PER_BYTE, tmp; + unsigned char data[len]; + + assert(e1->ops->type == EXPR_VALUE); + assert(e2->ops->type == EXPR_VALUE); + + tmp = e1->len / BITS_PER_BYTE; + mpz_export_data(data, e1->value, e1->byteorder, tmp); + mpz_export_data(data + tmp, e2->value, e2->byteorder, + e2->len / BITS_PER_BYTE); + + return constant_expr_alloc(&e1->location, &invalid_type, + BYTEORDER_INVALID, len * BITS_PER_BYTE, + data); +} + +struct expr *constant_expr_splice(struct expr *expr, unsigned int len) +{ + struct expr *slice; + mpz_t mask; + + assert(expr->ops->type == EXPR_VALUE); + assert(len <= expr->len); + + slice = constant_expr_alloc(&expr->location, &invalid_type, + BYTEORDER_INVALID, len, NULL); + mpz_init2(mask, len); + mpz_bitmask(mask, len); + mpz_set(slice->value, expr->value); + mpz_and(slice->value, slice->value, mask); + mpz_clear(mask); + + mpz_rshift_ui(expr->value, len); + expr->len -= len; + return slice; +} + +static void prefix_expr_print(const struct expr *expr) +{ + expr_print(expr->expr); + printf("/%u", expr->prefix_len); +} + +static void prefix_expr_set_type(const struct expr *expr, + const struct datatype *type, + enum byteorder byteorder) +{ + expr_set_type(expr->expr, type, byteorder); +} + +static const struct expr_ops prefix_expr_ops = { + .type = EXPR_PREFIX, + .name = "prefix", + .print = prefix_expr_print, + .set_type = prefix_expr_set_type, +}; + +struct expr *prefix_expr_alloc(const struct location *loc, + struct expr *expr, unsigned int prefix_len) +{ + struct expr *prefix; + + prefix = expr_alloc(loc, &prefix_expr_ops, &invalid_type, + BYTEORDER_INVALID, 0); + prefix->expr = expr; + prefix->prefix_len = prefix_len; + return prefix; +} + +const char *expr_op_symbols[] = { + [OP_INVALID] = "invalid", + [OP_HTON] = "hton", + [OP_NTOH] = "ntoh", + [OP_AND] = "&", + [OP_OR] = "|", + [OP_XOR] = "^", + [OP_LSHIFT] = "<<", + [OP_RSHIFT] = ">>", + [OP_EQ] = NULL, + [OP_NEQ] = "!=", + [OP_LT] = "<", + [OP_GT] = ">", + [OP_LTE] = "<=", + [OP_GTE] = ">=", + [OP_RANGE] = "within range", + [OP_LOOKUP] = NULL, +}; + +static void unary_expr_print(const struct expr *expr) +{ + if (expr_op_symbols[expr->op] != NULL) + printf("%s(", expr_op_symbols[expr->op]); + expr_print(expr->arg); + printf(")"); +} + +static void unary_expr_destroy(struct expr *expr) +{ + expr_free(expr->arg); +} + +static const struct expr_ops unary_expr_ops = { + .type = EXPR_UNARY, + .name = "unary", + .print = unary_expr_print, + .destroy = unary_expr_destroy, +}; + +struct expr *unary_expr_alloc(const struct location *loc, + enum ops op, struct expr *arg) +{ + struct expr *expr; + + expr = expr_alloc(loc, &unary_expr_ops, &invalid_type, + BYTEORDER_INVALID, 0); + expr->op = op; + expr->arg = arg; + return expr; +} + +static void binop_expr_print(const struct expr *expr) +{ + expr_print(expr->left); + if (expr_op_symbols[expr->op] != NULL) + printf(" %s ", expr_op_symbols[expr->op]); + else + printf(" "); + expr_print(expr->right); +} + +static void binop_expr_destroy(struct expr *expr) +{ + expr_free(expr->left); + expr_free(expr->right); +} + +static const struct expr_ops binop_expr_ops = { + .type = EXPR_BINOP, + .name = "binop", + .print = binop_expr_print, + .destroy = binop_expr_destroy, +}; + +struct expr *binop_expr_alloc(const struct location *loc, enum ops op, + struct expr *left, struct expr *right) +{ + struct expr *expr; + + expr = expr_alloc(loc, &binop_expr_ops, &invalid_type, + BYTEORDER_INVALID, 0); + expr->left = left; + expr->op = op; + expr->right = right; + return expr; +} + +static const struct expr_ops relational_expr_ops = { + .type = EXPR_RELATIONAL, + .name = "relational", + .print = binop_expr_print, + .destroy = binop_expr_destroy, +}; + +struct expr *relational_expr_alloc(const struct location *loc, enum ops op, + struct expr *left, struct expr *right) +{ + struct expr *expr; + + expr = expr_alloc(loc, &relational_expr_ops, &verdict_type, + BYTEORDER_INVALID, 0); + expr->left = left; + expr->op = op; + expr->right = right; + return expr; +} + +static void range_expr_print(const struct expr *expr) +{ + expr_print(expr->left); + printf("-"); + expr_print(expr->right); +} + +static void range_expr_destroy(struct expr *expr) +{ + expr_free(expr->left); + expr_free(expr->right); +} + +static void range_expr_set_type(const struct expr *expr, + const struct datatype *type, + enum byteorder byteorder) +{ + expr_set_type(expr->left, type, byteorder); + expr_set_type(expr->right, type, byteorder); +} + +static const struct expr_ops range_expr_ops = { + .type = EXPR_RANGE, + .name = "range", + .print = range_expr_print, + .destroy = range_expr_destroy, + .set_type = range_expr_set_type, +}; + +struct expr *range_expr_alloc(const struct location *loc, + struct expr *left, struct expr *right) +{ + struct expr *expr; + + expr = expr_alloc(loc, &range_expr_ops, &invalid_type, + BYTEORDER_INVALID, 0); + expr->left = left; + expr->right = right; + return expr; +} + +static struct expr *compound_expr_alloc(const struct location *loc, + const struct expr_ops *ops) +{ + struct expr *expr; + + expr = expr_alloc(loc, ops, &invalid_type, BYTEORDER_INVALID, 0); + init_list_head(&expr->expressions); + return expr; +} + +static void compound_expr_destroy(struct expr *expr) +{ + struct expr *i, *next; + + list_for_each_entry_safe(i, next, &expr->expressions, list) + expr_free(i); +} + +static void compound_expr_print(const struct expr *expr, const char *delim) +{ + const struct expr *i; + const char *d = ""; + + list_for_each_entry(i, &expr->expressions, list) { + printf("%s", d); + expr_print(i); + d = delim; + } +} + +void compound_expr_add(struct expr *compound, struct expr *expr) +{ + list_add_tail(&expr->list, &compound->expressions); + compound->size++; +} + +void compound_expr_remove(struct expr *compound, struct expr *expr) +{ + compound->size--; + list_del(&expr->list); +} + +static void concat_expr_print(const struct expr *expr) +{ + compound_expr_print(expr, " . "); +} + +static const struct expr_ops concat_expr_ops = { + .type = EXPR_CONCAT, + .name = "concat", + .print = concat_expr_print, + .destroy = compound_expr_destroy, +}; + +struct expr *concat_expr_alloc(const struct location *loc) +{ + return compound_expr_alloc(loc, &concat_expr_ops); +} + +static void list_expr_print(const struct expr *expr) +{ + compound_expr_print(expr, ","); +} + +static const struct expr_ops list_expr_ops = { + .type = EXPR_LIST, + .name = "list", + .print = list_expr_print, + .destroy = compound_expr_destroy, +}; + +struct expr *list_expr_alloc(const struct location *loc) +{ + return compound_expr_alloc(loc, &list_expr_ops); +} + +static void set_expr_print(const struct expr *expr) +{ + printf("{ "); + compound_expr_print(expr, ", "); + printf("}"); +} + +static void set_expr_set_type(const struct expr *expr, + const struct datatype *dtype, + enum byteorder byteorder) +{ + struct expr *i; + + list_for_each_entry(i, &expr->expressions, list) + expr_set_type(i, dtype, byteorder); +} + +static const struct expr_ops set_expr_ops = { + .type = EXPR_SET, + .name = "set", + .print = set_expr_print, + .set_type = set_expr_set_type, + .destroy = compound_expr_destroy, +}; + +struct expr *set_expr_alloc(const struct location *loc) +{ + return compound_expr_alloc(loc, &set_expr_ops); +} + +static void mapping_expr_print(const struct expr *expr) +{ + expr_print(expr->left); + printf(" => "); + expr_print(expr->right); +} + +static void mapping_expr_set_type(const struct expr *expr, + const struct datatype *dtype, + enum byteorder byteorder) +{ + expr_set_type(expr->left, dtype, byteorder); +} + +static void mapping_expr_destroy(struct expr *expr) +{ + expr_free(expr->left); + expr_free(expr->right); +} + +static const struct expr_ops mapping_expr_ops = { + .type = EXPR_MAPPING, + .name = "mapping", + .print = mapping_expr_print, + .set_type = mapping_expr_set_type, + .destroy = mapping_expr_destroy, +}; + +struct expr *mapping_expr_alloc(const struct location *loc, + struct expr *from, struct expr *to) +{ + struct expr *expr; + + expr = expr_alloc(loc, &mapping_expr_ops, from->dtype, + from->byteorder, 0); + expr->left = from; + expr->right = to; + return expr; +} + +static void map_expr_print(const struct expr *expr) +{ + expr_print(expr->expr); + printf(" map "); + expr_print(expr->mappings); +} + +static void map_expr_destroy(struct expr *expr) +{ + expr_free(expr->expr); + expr_free(expr->mappings); +} + +static const struct expr_ops map_expr_ops = { + .type = EXPR_MAP, + .name = "map", + .print = map_expr_print, + .destroy = map_expr_destroy, +}; + +struct expr *map_expr_alloc(const struct location *loc, struct expr *arg, + struct expr *list) +{ + struct expr *expr; + + assert(list->ops->type == EXPR_SET); + expr = expr_alloc(loc, &map_expr_ops, list->dtype, + list->byteorder, list->len); + expr->expr = arg; + expr->mappings = list; + return expr; +} -- cgit v1.2.3