45 #define DEBUG DEBUG_NONE 55 #ifndef LVM_MAX_NAME_LENGTH 56 #define LVM_MAX_NAME_LENGTH 16 59 #ifndef LVM_MAX_VARIABLE_ID 60 #define LVM_MAX_VARIABLE_ID 8 63 #ifndef LVM_USE_FLOATS 64 #define LVM_USE_FLOATS 0 67 #define IS_CONNECTIVE(op) ((op) & LVM_CONNECTIVE) 71 operand_value_t value;
72 char name[LVM_MAX_NAME_LENGTH + 1];
74 typedef struct variable variable_t;
81 typedef struct derivation derivation_t;
85 static variable_t variables[LVM_MAX_VARIABLE_ID];
88 static derivation_t derivations[LVM_MAX_VARIABLE_ID];
92 print_derivations(derivation_t *d)
96 for(i = 0; i < LVM_MAX_VARIABLE_ID; i++) {
98 printf(
"%s is constrained to (%ld,%ld)\n", variables[i].name,
99 d[i].min.l, d[i].max.l);
110 for(var = variables; var <= &variables[LVM_MAX_VARIABLE_ID - 1] && var->name[0] !=
'\0'; var++) {
111 if(strcmp(var->name, name) == 0) {
116 return (variable_id_t)(var - &variables[0]);
120 get_operator(lvm_instance_t *p)
122 operator_t *
operator;
124 operator = (operator_t *)&p->code[p->ip];
125 p->ip +=
sizeof(operator_t);
130 get_operand(lvm_instance_t *p, operand_t *operand)
132 memcpy(operand, &p->code[p->ip],
sizeof(*operand));
133 p->ip +=
sizeof(*operand);
137 get_type(lvm_instance_t *p)
139 node_type_t node_type;
141 node_type = *(node_type_t *)(p->code + p->ip);
142 p->ip +=
sizeof(node_type);
148 operand_to_long(operand_t *operand)
150 switch(operand->type) {
152 return operand->value.l;
155 return (
long)operand->value.f;
159 return variables[operand->value.id].value.l;
166 eval_expr(lvm_instance_t *p, operator_t op, operand_t *result)
170 operator_t *
operator;
171 operand_t operand[2];
176 for(i = 0; i < 2; i++) {
180 operator = get_operator(p);
181 r = eval_expr(p, *
operator, &operand[i]);
187 get_operand(p, &operand[i]);
190 return LVM_SEMANTIC_ERROR;
192 value[i] = operand_to_long(&operand[i]);
197 result_value = value[0] + value[1];
200 result_value = value[0] - value[1];
203 result_value = value[0] * value[1];
207 return LVM_MATH_ERROR;
209 result_value = value[0] / value[1];
212 return LVM_EXECUTION_ERROR;
215 result->type = LVM_LONG;
216 result->value.l = result_value;
222 eval_logic(lvm_instance_t *p, operator_t *op)
229 operator_t *
operator;
234 if(IS_CONNECTIVE(*op)) {
235 arguments = *op == LVM_NOT ? 1 : 2;
236 for(i = 0; i < arguments; i++) {
238 if(type != LVM_CMP_OP) {
239 return LVM_SEMANTIC_ERROR;
241 operator = get_operator(p);
242 logic_result[i] = eval_logic(p,
operator);
243 if(LVM_ERROR(logic_result[i])) {
244 return logic_result[i];
249 return !logic_result[0];
250 }
else if(*op == LVM_AND) {
251 return logic_result[0] == LVM_TRUE && logic_result[1] == LVM_TRUE;
253 return logic_result[0] == LVM_TRUE || logic_result[1] == LVM_TRUE;
257 for(i = 0; i < 2; i++) {
261 operator = get_operator(p);
262 r = eval_expr(p, *
operator, &operand);
268 get_operand(p, &operand);
271 return LVM_SEMANTIC_ERROR;
273 result[i] = operand_to_long(&operand);
278 PRINTF(
"Result1: %ld\nResult2: %ld\n", l1, l2);
297 return LVM_EXECUTION_ERROR;
301 lvm_reset(lvm_instance_t *p,
unsigned char *code, lvm_ip_t size)
303 memset(code, 0, size);
310 memset(variables, 0,
sizeof(variables));
311 memset(derivations, 0,
sizeof(derivations));
315 lvm_jump_to_operand(lvm_instance_t *p)
320 p->end +=
sizeof(operator_t) +
sizeof(node_type_t);
321 if(p->end >= p->size) {
330 lvm_shift_for_operator(lvm_instance_t *p, lvm_ip_t end)
337 if(p->end +
sizeof(operator_t) +
sizeof(node_type_t) > p->size ||
345 memmove(ptr +
sizeof(operator_t) +
sizeof(node_type_t), ptr, old_end - end);
348 return old_end +
sizeof(operator_t) +
sizeof(node_type_t);
352 lvm_get_end(lvm_instance_t *p)
358 lvm_set_end(lvm_instance_t *p, lvm_ip_t end)
374 lvm_execute(lvm_instance_t *p)
377 operator_t *
operator;
381 status = LVM_EXECUTION_ERROR;
385 operator = get_operator(p);
386 status = eval_logic(p,
operator);
387 if(!LVM_ERROR(status)) {
388 PRINTF(
"The statement is %s\n", status == LVM_TRUE ?
"true" :
"false");
390 PRINTF(
"Execution error: %d\n", (
int)status);
394 PRINTF(
"Error: The code must start with a relational operator\n");
401 lvm_set_type(lvm_instance_t *p, node_type_t type)
403 if(p->end +
sizeof(node_type_t) >= DB_VM_BYTECODE_SIZE) {
404 PRINTF(
"Error: overflow in lvm_set_type\n");
405 return LVM_STACK_OVERFLOW;
408 *(node_type_t *)(p->code + p->end) = type;
409 p->end +=
sizeof(type);
414 lvm_set_op(lvm_instance_t *p, operator_t op)
418 status = lvm_set_type(p, LVM_ARITH_OP);
419 if(status != LVM_TRUE) {
423 if(p->end +
sizeof(op) >= DB_VM_BYTECODE_SIZE) {
424 PRINTF(
"Error: overflow in lvm_set_op\n");
425 return LVM_STACK_OVERFLOW;
428 memcpy(&p->code[p->end], &op,
sizeof(op));
429 p->end +=
sizeof(op);
434 lvm_set_relation(lvm_instance_t *p, operator_t op)
438 status = lvm_set_type(p, LVM_CMP_OP);
439 if(status != LVM_TRUE) {
443 if(p->end +
sizeof(op) >= DB_VM_BYTECODE_SIZE) {
444 PRINTF(
"Error: overflow in lvm_set_relation\n");
445 return LVM_STACK_OVERFLOW;
448 memcpy(&p->code[p->end], &op,
sizeof(op));
449 p->end +=
sizeof(op);
454 lvm_set_operand(lvm_instance_t *p, operand_t *op)
458 status = lvm_set_type(p, LVM_OPERAND);
459 if(status != LVM_TRUE) {
463 if(p->end +
sizeof(*op) >= DB_VM_BYTECODE_SIZE) {
464 PRINTF(
"Error: overflow in lvm_set_operand\n");
465 return LVM_STACK_OVERFLOW;
468 memcpy(&p->code[p->end], op,
sizeof(*op));
469 p->end +=
sizeof(*op);
474 lvm_set_long(lvm_instance_t *p,
long l)
481 return lvm_set_operand(p, &op);
485 lvm_register_variable(
char *name, operand_type_t type)
491 if(
id == LVM_MAX_VARIABLE_ID) {
492 return LVM_VARIABLE_LIMIT_REACHED;
495 var = &variables[id];
496 if(var->name[0] ==
'\0') {
497 strncpy(var->name, name,
sizeof(var->name) - 1);
498 var->name[
sizeof(var->name) - 1] =
'\0';
506 lvm_set_variable_value(
char *name, operand_value_t value)
511 if(
id == LVM_MAX_VARIABLE_ID) {
512 return LVM_INVALID_IDENTIFIER;
515 variables[id].value = value;
520 lvm_set_variable(lvm_instance_t *p,
char *name)
526 if(
id == LVM_MAX_VARIABLE_ID) {
527 return LVM_INVALID_IDENTIFIER;
530 PRINTF(
"var id = %d\n",
id);
531 op.type = LVM_VARIABLE;
533 return lvm_set_operand(p, &op);
537 lvm_clone(lvm_instance_t *dst, lvm_instance_t *src)
539 memcpy(dst, src,
sizeof(*dst));
543 create_intersection(derivation_t *result, derivation_t *d1, derivation_t *d2)
547 for(i = 0; i < LVM_MAX_VARIABLE_ID; i++) {
548 if(!d1[i].derived && !d2[i].derived) {
550 }
else if(d1[i].derived && !d2[i].derived) {
551 result[i].min.l = d1[i].min.l;
552 result[i].max.l = d1[i].max.l;
553 }
else if(!d1[i].derived && d2[i].derived) {
554 result[i].min.l = d2[i].min.l;
555 result[i].max.l = d2[i].max.l;
559 if(d1[i].min.l > d2[i].min.l) {
560 result[i].min.l = d1[i].min.l;
562 result[i].min.l = d2[i].min.l;
565 if(d1[i].max.l < d2[i].max.l) {
566 result[i].max.l = d1[i].max.l;
568 result[i].max.l = d2[i].max.l;
571 result[i].derived = 1;
575 PRINTF(
"Created an intersection of D1 and D2\n");
577 print_derivations(d1);
579 print_derivations(d2);
580 PRINTF(
"Result: \n");
581 print_derivations(result);
586 create_union(derivation_t *result, derivation_t *d1, derivation_t *d2)
590 for(i = 0; i < LVM_MAX_VARIABLE_ID; i++) {
591 if(!d1[i].derived && !d2[i].derived) {
593 }
else if(d1[i].derived && !d2[i].derived) {
594 result[i].min.l = d1[i].min.l;
595 result[i].max.l = d1[i].max.l;
596 }
else if(!d1[i].derived && d2[i].derived) {
597 result[i].min.l = d2[i].min.l;
598 result[i].max.l = d2[i].max.l;
602 if(d1[i].min.l > d2[i].min.l) {
603 result[i].min.l = d2[i].min.l;
605 result[i].min.l = d1[i].min.l;
608 if(d1[i].max.l < d2[i].max.l) {
609 result[i].max.l = d2[i].max.l;
611 result[i].max.l = d1[i].max.l;
614 result[i].derived = 1;
618 PRINTF(
"Created a union of D1 and D2\n");
620 print_derivations(d1);
622 print_derivations(d2);
623 PRINTF(
"Result: \n");
624 print_derivations(result);
629 derive_relation(lvm_instance_t *p, derivation_t *local_derivations)
631 operator_t *
operator;
633 operand_t operand[2];
636 operand_value_t *value;
637 derivation_t *derivation;
640 operator = get_operator(p);
642 if(IS_CONNECTIVE(*
operator)) {
643 derivation_t d1[LVM_MAX_VARIABLE_ID];
644 derivation_t d2[LVM_MAX_VARIABLE_ID];
646 if(*
operator != LVM_AND && *
operator != LVM_OR) {
647 return LVM_DERIVATION_ERROR;
650 PRINTF(
"Attempting to infer ranges from a logical connective\n");
652 memset(d1, 0,
sizeof(d1));
653 memset(d2, 0,
sizeof(d2));
655 if(LVM_ERROR(derive_relation(p, d1)) ||
656 LVM_ERROR(derive_relation(p, d2))) {
657 return LVM_DERIVATION_ERROR;
660 if(*
operator == LVM_AND) {
661 create_intersection(local_derivations, d1, d2);
662 }
else if(*
operator == LVM_OR) {
663 create_union(local_derivations, d1, d2);
668 for(i = 0; i < 2; i++) {
672 get_operand(p, &operand[i]);
675 return LVM_DERIVATION_ERROR;
679 if(operand[0].type == LVM_VARIABLE && operand[1].type == LVM_VARIABLE) {
680 return LVM_DERIVATION_ERROR;
684 if(operand[0].type == LVM_VARIABLE) {
685 if(operand[1].type == LVM_VARIABLE) {
686 return LVM_DERIVATION_ERROR;
688 variable_id = operand[0].value.id;
689 value = &operand[1].value;
691 variable_id = operand[1].value.id;
692 value = &operand[0].value;
695 if(variable_id >= LVM_MAX_VARIABLE_ID) {
696 return LVM_DERIVATION_ERROR;
699 PRINTF(
"variable id %d, value %ld\n", variable_id, *(
long *)value);
701 derivation = local_derivations + variable_id;
703 derivation->max.l = LONG_MAX;
704 derivation->min.l = LONG_MIN;
708 derivation->max = *value;
709 derivation->min = *value;
712 derivation->min.l = value->l + 1;
715 derivation->min.l = value->l;
718 derivation->max.l = value->l - 1;
721 derivation->max.l = value->l;
724 return LVM_DERIVATION_ERROR;
727 derivation->derived = 1;
733 lvm_derive(lvm_instance_t *p)
735 return derive_relation(p, derivations);
739 lvm_get_derived_range(lvm_instance_t *p,
char *name,
740 operand_value_t *min, operand_value_t *max)
744 for(i = 0; i < LVM_MAX_VARIABLE_ID; i++) {
745 if(strcmp(name, variables[i].name) == 0) {
746 if(derivations[i].derived) {
747 *min = derivations[i].min;
748 *max = derivations[i].max;
751 return LVM_DERIVATION_ERROR;
754 return LVM_INVALID_IDENTIFIER;
759 print_operator(lvm_instance_t *p, lvm_ip_t index)
762 struct operator_map {
764 char *representation;
766 struct operator_map operator_map[] = {
783 memcpy(&
operator, p->code + index,
sizeof(
operator));
785 for(i = 0; i <
sizeof(operator_map) /
sizeof(operator_map[0]); i++) {
786 if(operator_map[i].op ==
operator) {
787 PRINTF(
"%s ", operator_map[i].representation);
792 return index +
sizeof(operator_t);
796 print_operand(lvm_instance_t *p, lvm_ip_t index)
800 memcpy(&operand, p->code + index,
sizeof(operand));
802 switch(operand.type) {
804 if(operand.value.id >= LVM_MAX_VARIABLE_ID ||
805 variables[operand.value.id].name == NULL) {
806 PRINTF(
"var(id:%d):?? ", operand.value.id);
808 PRINTF(
"var(%s):%ld ", variables[operand.value.id].name,
809 variables[operand.value.id].value.l);
813 PRINTF(
"long:%ld ", operand.value.l);
820 return index +
sizeof(operand_t);
824 print_relation(lvm_instance_t *p, lvm_ip_t index)
827 return print_operator(p, index);
832 lvm_print_code(lvm_instance_t *p)
839 for(ip = 0; ip < p->end;) {
840 switch(*(node_type_t *)(p->code + ip)) {
842 ip = print_relation(p, ip +
sizeof(node_type_t));
845 ip = print_operator(p, ip +
sizeof(node_type_t));
848 ip = print_operand(p, ip +
sizeof(node_type_t));
851 PRINTF(
"Invalid opcode: 0x%x ", p->code[ip]);
861 lvm_print_derivations(lvm_instance_t *p)
864 print_derivations(derivations);
873 unsigned char code[256];
875 lvm_reset(&p, code,
sizeof(code));
877 lvm_register_variable(
"z", LVM_LONG);
878 lvm_set_variable_value(
"z", (operand_value_t)15L);
880 lvm_register_variable(
"y", LVM_LONG);
881 lvm_set_variable_value(
"y", (operand_value_t)109L);
884 lvm_set_relation(&p, LVM_AND);
885 lvm_set_relation(&p, LVM_EQ);
886 lvm_set_long(&p, 109);
887 lvm_set_variable(&p,
"y");
888 lvm_set_relation(&p, LVM_GE);
889 lvm_set_long(&p, 20);
890 lvm_set_op(&p, LVM_SUB);
891 lvm_set_long(&p, 70);
892 lvm_set_op(&p, LVM_ADD);
894 lvm_set_op(&p, LVM_MUL);
895 lvm_set_variable(&p,
"z");
903 lvm_reset(&p, code,
sizeof(code));
904 lvm_set_relation(&p, LVM_NOT);
905 lvm_set_relation(&p, LVM_LE);
906 lvm_set_op(&p, LVM_ADD);
907 lvm_set_long(&p, 9999);
909 lvm_set_op(&p, LVM_ADD);
910 lvm_set_long(&p, -1);
911 lvm_set_long(&p, 10001);
920 lvm_reset(&p, code,
sizeof(code));
921 lvm_register_variable(
"a", LVM_LONG);
922 lvm_set_relation(&p, LVM_EQ);
923 lvm_set_variable(&p,
"a");
927 lvm_print_derivations(&p);
930 lvm_reset(&p, code,
sizeof(code));
931 lvm_register_variable(
"a", LVM_LONG);
932 lvm_set_relation(&p, LVM_LE);
933 lvm_set_variable(&p,
"a");
934 lvm_set_long(&p, 10);
937 lvm_print_derivations(&p);
940 lvm_reset(&p, code,
sizeof(code));
941 lvm_register_variable(
"a", LVM_LONG);
942 lvm_set_relation(&p, LVM_AND);
943 lvm_set_relation(&p, LVM_LE);
944 lvm_set_variable(&p,
"a");
945 lvm_set_long(&p, 100);
946 lvm_set_relation(&p, LVM_GE);
947 lvm_set_long(&p, 10);
948 lvm_set_variable(&p,
"a");
951 lvm_print_derivations(&p);
954 lvm_reset(&p, code,
sizeof(code));
955 lvm_register_variable(
"a", LVM_LONG);
956 lvm_register_variable(
"b", LVM_LONG);
957 lvm_set_relation(&p, LVM_AND);
958 lvm_set_relation(&p, LVM_LE);
959 lvm_set_variable(&p,
"a");
960 lvm_set_long(&p, 100);
961 lvm_set_relation(&p, LVM_GE);
962 lvm_set_variable(&p,
"b");
963 lvm_set_long(&p, 100);
966 lvm_print_derivations(&p);
969 lvm_reset(&p, code,
sizeof(code));
970 lvm_register_variable(
"a", LVM_LONG);
971 lvm_set_relation(&p, LVM_OR);
972 lvm_set_relation(&p, LVM_LE);
973 lvm_set_variable(&p,
"a");
974 lvm_set_long(&p, 100);
975 lvm_set_relation(&p, LVM_OR);
976 lvm_set_relation(&p, LVM_LE);
977 lvm_set_long(&p, 1000);
978 lvm_set_variable(&p,
"a");
979 lvm_set_relation(&p, LVM_LE);
980 lvm_set_variable(&p,
"a");
981 lvm_set_long(&p, 1902);
984 lvm_print_derivations(&p);
988 lvm_reset(&p, code,
sizeof(code));
989 lvm_register_variable(
"a", LVM_LONG);
990 lvm_register_variable(
"b", LVM_LONG);
992 lvm_set_relation(&p, LVM_OR);
993 lvm_set_relation(&p, LVM_GE);
994 lvm_set_variable(&p,
"b");
995 lvm_set_long(&p, 10000);
997 lvm_set_relation(&p, LVM_AND);
998 lvm_set_relation(&p, LVM_LE);
999 lvm_set_variable(&p,
"a");
1000 lvm_set_long(&p, 100);
1001 lvm_set_relation(&p, LVM_AND);
1002 lvm_set_relation(&p, LVM_LE);
1003 lvm_set_variable(&p,
"a");
1004 lvm_set_long(&p, 90);
1005 lvm_set_relation(&p, LVM_AND);
1006 lvm_set_relation(&p, LVM_GE);
1007 lvm_set_variable(&p,
"a");
1008 lvm_set_long(&p, 80);
1009 lvm_set_relation(&p, LVM_LE);
1010 lvm_set_variable(&p,
"a");
1011 lvm_set_long(&p, 105);
1014 lvm_print_derivations(&p);
A set of debugging macros.
Definitions and declarations for AQL, the Antelope Query Language.
Definitions and declarations for the Propositional Logic Engine.