#include <solver/algebra.h>
// for show
#include <stdio.h>
#include <assert.h>
// 0x7 f f 8 | 7
// <01111111 1111 12-bit nan header> <1-bit silent flag, 0 on most cpus> <3-bit tag> <48-bit payload>
// 000 - variable - pointer to variable name
// 001 - atom
// 010 - integer - 32-bit integer
// 011 - integer - pointer to big integer implementation
// 100 - pair - <3-bit type> <21-bit unused> <24-bit index to first>
// 000 - fraction
// 001 - power
// 010 - unused
// 011 - unused
// 100 - equals
// 101 - not equals
// 110 - less than
// 111 - greater than
// 101 - list - <1-bit type> <23-bit count> <24-bit index to first>
// 0 - sum
// 1 - product
// 110 - unused
// 111 - unused
#define NAN_MASK 0xFFF0000000000000ull
#define NAN_BITS 0x7FF0000000000000ull
#define QUEIT_BITS 0x7FF0000000000000ull
#define SIGNALING_BITS 0x7FF8000000000000ull
#define TAG_MASK 0xFFF7000000000000ull
#define TAG_VARIABLE_BITS 0x7FF0000000000000ull
#define TAG_ATOM_BITS 0x7FF1000000000000ull
#define TAG_INTEGER_BITS 0x7FF2000000000000ull
#define TAG_BIGINT_BITS 0x7FF3000000000000ull
#define TAG_PAIR_BITS 0x7FF4000000000000ull
#define TAG_LIST_BITS 0x7FF5000000000000ull
#define TAG_UNUSED1_BITS 0x7FF6000000000000ull
#define TAG_UNUSED2_BITS 0x7FF7000000000000ull
#define PAIR_MASK 0xFFF7e00000000000ull
#define PAIR_FRACTION_BITS 0x7FF4000000000000ull
#define PAIR_POWER_BITS 0x7FF4200000000000ull
#define PAIR_UNUSED1_BITS 0x7FF4400000000000ull
#define PAIR_UNUSED2_BITS 0x7FF4600000000000ull
#define PAIR_EQUAL_BITS 0x7FF4800000000000ull
#define PAIR_NOT_EQUAL_BITS 0x7FF4a00000000000ull
#define PAIR_LESS_THAN_BITS 0x7FF4c00000000000ull
#define PAIR_GREATER_THAN_BITS 0x7FF4e00000000000ull
#define LIST_MASK 0xFFF7800000000000ull
#define LIST_SUM_BITS 0x7FF5000000000000ull
#define LIST_PRODUCT_BITS 0x7FF5800000000000ull
#define PAYLOAD_MASK 0x0000FFFFFFFFFFFFull
#define PAIR_INDEX_MASK 0x0000000000FFFFFFull
#define LIST_COUNT_MASK 0x00007FFFFF000000ull
#define LIST_INDEX_MASK 0x0000000000FFFFFFull
struct Unpacked {
enum {
Unpacked_Real,
Unpacked_Variable,
Unpacked_Boolean, // atom 0 and 1
Unpacked_Undefined, // atom 2
Unpacked_Integer,
Unpacked_BigInteger,
Unpacked_Fraction,
Unpacked_Power,
Unpacked_Sum,
Unpacked_Product,
Unpacked_Equals,
Unpacked_NotEquals,
Unpacked_LessThan,
Unpacked_GreaterThan,
Unpacked_Invalid
} tag;
union {
double real;
const char *variable;
bool boolean;
int64_t integer;
void * big_integer;
struct {
uint32_t index;
} pair, fraction, power, equals, not_equals, less_than, greater_than;
struct {
uint32_t count;
uint32_t index;
} list, sum, product;
};
};
static inline uint64_t pack_real(double real) {
union {
uint64_t u;
double d;
} _;
_.d = real;
return _.u;
}
static inline uint64_t pack_variable(const char *name) {
return TAG_VARIABLE_BITS | ((uint64_t)name & PAYLOAD_MASK);
}
static inline uint64_t pack_boolean(bool value) {
return TAG_ATOM_BITS | !!value; // assumes ! returns either 0 or 1
}
static inline uint64_t pack_undefined(void) {
return TAG_ATOM_BITS | 2;
}
static inline uint64_t pack_integer(int32_t integer) {
union {
uint64_t u;
int32_t i[2];
} _;
_.i[1] = integer;
return TAG_INTEGER_BITS | (_.u & PAYLOAD_MASK);
}
static inline uint64_t pack_big_integer(void * ptr) {
return TAG_BIGINT_BITS | ((uint64_t)ptr & PAYLOAD_MASK);
}
static inline uint64_t pack_fraction(uint32_t index) {
return PAIR_FRACTION_BITS | index;
}
static inline uint64_t pack_power(uint32_t index) {
return PAIR_POWER_BITS | index;
}
static inline uint64_t pack_sum(uint32_t count, uint32_t index) {
return LIST_SUM_BITS | ((uint64_t)count << 24) | index;
}
static inline uint64_t pack_product(uint32_t count, uint32_t index) {
return LIST_PRODUCT_BITS | ((uint64_t)count << 24) | index;
}
static inline uint64_t pack_equals(uint32_t index) {
return PAIR_EQUAL_BITS | index;
}
static inline uint64_t pack_not_equals(uint32_t index) {
return PAIR_NOT_EQUAL_BITS | index;
}
static inline uint64_t pack_less_than(uint32_t index) {
return PAIR_LESS_THAN_BITS | index;
}
static inline uint64_t pack_greater_than(uint32_t index) {
return PAIR_GREATER_THAN_BITS | index;
}
static inline uint64_t pack(struct Unpacked unpacked) {
switch(unpacked.tag) {
case Unpacked_Real:
return pack_real(unpacked.real);
case Unpacked_Variable:
return pack_variable(unpacked.variable);
case Unpacked_Boolean:
return pack_boolean(unpacked.boolean);
case Unpacked_Undefined:
return pack_undefined();
case Unpacked_Integer:
return pack_integer(unpacked.integer);
case Unpacked_BigInteger:
return pack_big_integer(unpacked.big_integer);
case Unpacked_Fraction:
return pack_fraction(unpacked.fraction.index);
case Unpacked_Power:
return pack_power(unpacked.power.index);
case Unpacked_Sum:
return pack_sum(unpacked.sum.count, unpacked.sum.index);
case Unpacked_Product:
return pack_product(unpacked.product.count, unpacked.product.index);
case Unpacked_Equals:
return pack_equals(unpacked.equals.index);
case Unpacked_NotEquals:
return pack_not_equals(unpacked.not_equals.index);
case Unpacked_LessThan:
return pack_not_equals(unpacked.less_than.index);
case Unpacked_GreaterThan:
return pack_not_equals(unpacked.greater_than.index);
case Unpacked_Invalid:
return SIGNALING_BITS;
}
}
static inline bool is_real(uint64_t bits) {
return (bits & NAN_MASK) != NAN_BITS;
}
static inline bool is_variable(uint64_t bits) {
return (bits & TAG_MASK) == TAG_VARIABLE_BITS;
}
static inline bool is_boolean(uint64_t bits) {
return (bits & TAG_MASK) == TAG_ATOM_BITS && (bits & (PAYLOAD_MASK ^ 1)) == 0;
}
static inline bool is_undefined(uint64_t bits) {
return bits == TAG_ATOM_BITS | 2;
}
static inline bool is_integer(uint64_t bits) {
return (bits & TAG_MASK) == TAG_INTEGER_BITS;
}
static inline bool is_big_integer(uint64_t bits) {
return (bits & TAG_MASK) == TAG_BIGINT_BITS;
}
static inline bool is_fraction(uint64_t bits) {
return (bits & PAIR_MASK) == PAIR_FRACTION_BITS;
}
static inline bool is_power(uint64_t bits) {
return (bits & PAIR_MASK) == PAIR_POWER_BITS;
}
static inline bool is_sum(uint64_t bits) {
return (bits & LIST_MASK) == LIST_SUM_BITS;
}
static inline bool is_product(uint64_t bits) {
return (bits & LIST_MASK) == LIST_PRODUCT_BITS;
}
static inline bool is_equals(uint64_t bits) {
return (bits & PAIR_MASK) == PAIR_EQUAL_BITS;
}
static inline bool is_not_equals(uint64_t bits) {
return (bits & PAIR_MASK) == PAIR_NOT_EQUAL_BITS;
}
static inline bool is_less_than(uint64_t bits) {
return (bits & PAIR_MASK) == PAIR_LESS_THAN_BITS;
}
static inline bool is_greater_than(uint64_t bits) {
return (bits & PAIR_MASK) == PAIR_GREATER_THAN_BITS;
}
static inline double unpack_real(uint64_t bits) {
union {
uint64_t u;
double d;
} _;
assert(is_real(bits));
_.u = bits;
return _.d;
}
static inline const char * unpack_variable(uint64_t bits) {
assert(is_variable(bits));
return (const char *)(bits & PAYLOAD_MASK);
}
static inline bool unpack_boolean(uint64_t bits) {
assert(is_boolean(bits));
return !!(bits & 1);
}
static inline void unpack_undefined(uint64_t bits) {
assert(is_undefined(bits));
}
static inline int32_t unpack_integer(uint64_t bits) {
union {
uint64_t u;
int32_t i[2];
} _;
assert(is_integer(bits));
_.u = bits & PAYLOAD_MASK;
return _.i[1];
}
static inline void * unpack_big_integer(uint64_t bits) {
assert(is_big_integer(bits));
return (void *)(bits & PAYLOAD_MASK);
}
static inline uint32_t unpack_fraction(uint64_t bits) {
assert(is_fraction(bits));
return bits & PAIR_INDEX_MASK;
}
static inline uint32_t unpack_power(uint64_t bits) {
assert(is_power(bits));
return bits & PAIR_INDEX_MASK;
}
static inline void unpack_sum(uint64_t bits, uint32_t *count, uint32_t *index) {
assert(is_sum(bits));
*count = (bits & LIST_COUNT_MASK) >> 24;
*index = bits & LIST_INDEX_MASK;
}
static inline void unpack_product(uint64_t bits, uint32_t *count, uint32_t *index) {
assert(is_product(bits));
*count = (bits & LIST_COUNT_MASK) >> 24;
*index = bits & LIST_INDEX_MASK;
}
static inline uint32_t unpack_equals(uint64_t bits) {
assert(is_equals(bits));
return bits & PAIR_INDEX_MASK;
}
static inline uint32_t unpack_not_equals(uint64_t bits) {
assert(is_not_equals(bits));
return bits & PAIR_INDEX_MASK;
}
static inline uint32_t unpack_less_than(uint64_t bits) {
assert(is_less_than(bits));
return bits & PAIR_INDEX_MASK;
}
static inline uint32_t unpack_greater_than(uint64_t bits) {
assert(is_greater_than(bits));
return bits & PAIR_INDEX_MASK;
}
static int unpack_tag(uint64_t bits) {
if(is_real(bits)) {
return Unpacked_Real;
} else if(is_variable(bits)) {
return Unpacked_Variable;
} else if(is_boolean(bits)) {
return Unpacked_Boolean;
} else if(is_undefined(bits)) {
return Unpacked_Undefined;
} else if(is_integer(bits)) {
return Unpacked_Integer;
} else if(is_big_integer(bits)) {
return Unpacked_BigInteger;
} else if(is_fraction(bits)) {
return Unpacked_Fraction;
} else if(is_power(bits)) {
return Unpacked_Power;
} else if(is_equals(bits)) {
return Unpacked_Equals;
} else if(is_not_equals(bits)) {
return Unpacked_NotEquals;
} else if(is_less_than(bits)) {
return Unpacked_LessThan;
} else if(is_greater_than(bits)) {
return Unpacked_GreaterThan;
} else if(is_sum(bits)) {
return Unpacked_Sum;
} else if(is_product(bits)) {
return Unpacked_Product;
} else {
return Unpacked_Invalid;
}
}
static inline struct Unpacked unpack(uint64_t bits) {
struct Unpacked result;
switch(result.tag = unpack_tag(bits)) {
case Unpacked_Real:
result.real = unpack_real(bits);
break;
case Unpacked_Variable:
result.variable = unpack_variable(bits);
break;
case Unpacked_Boolean:
result.boolean = unpack_boolean(bits);
break;
case Unpacked_Undefined:
unpack_undefined(bits);
break;
case Unpacked_Integer:
result.integer = unpack_integer(bits);
break;
case Unpacked_BigInteger:
result.big_integer = unpack_big_integer(bits);
break;
case Unpacked_Fraction:
result.fraction.index = (bits & PAIR_INDEX_MASK);
break;
case Unpacked_Power:
result.power.index = (bits & PAIR_INDEX_MASK);
break;
case Unpacked_Sum:
unpack_sum(bits, &result.sum.count, &result.sum.index);
break;
case Unpacked_Product:
unpack_product(bits, &result.product.count, &result.product.index);
break;
case Unpacked_Equals:
result.equals.index = unpack_equals(bits);
break;
case Unpacked_NotEquals:
result.not_equals.index = unpack_not_equals(bits);
break;
case Unpacked_LessThan:
result.less_than.index = unpack_less_than(bits);
break;
case Unpacked_GreaterThan:
result.greater_than.index = unpack_greater_than(bits);
break;
case Unpacked_Invalid:
break;
}
return result;
}
// --------------------------------------------------------------------------------------------------------------------
// numerics
static inline bool is_number(uint64_t bits) {
return is_real(bits) || is_integer(bits) || is_big_integer(bits) || is_fraction(bits);
}
static inline bool is_exact(uint64_t bits) {
return is_integer(bits) || is_big_integer(bits) || is_fraction(bits);
}
static inline bool is_inexact(uint64_t bits) {
return is_real(bits);
}
// --------------------------------------------------------------------------------------------------------------------
// lifetime
void solver_Algebra_init(struct solver_Algebra *a) {
alias_Vector_init(&a->values);
}
void solver_Algebra_free(struct solver_Algebra *a) {
alias_Vector_free(&a->values, NULL);
}
// --------------------------------------------------------------------------------------------------------------------
// creation entry points , most go through simplification before being committed to memory
static uint64_t simplify_real(struct solver_Algebra *a, double real);
static uint64_t simplify_fraction(struct solver_Algebra *a, uint64_t numerator, uint64_t denominator);
uint64_t solver_Algebra_boolean(struct solver_Algebra *a, bool value) {
return pack_boolean(value);
}
uint64_t solver_Algebra_integer(struct solver_Algebra *a, int64_t value) {
return pack_integer(value);
}
uint64_t solver_Algebra_fraction(struct solver_Algebra *a, int64_t numerator, int64_t denominator) {
return simplify_fraction(numerator, denominator);
}
uint64_t solver_Algebra_real(struct solver_Algebra *a, double value) {
return simplify_real(a, real);
}
uint64_t solver_Algebra_variable(struct solver_Algebra *a, const char * name) {
return pack_variable(name);
}
uint64_t solver_Algebra_sum(struct solver_Algebra *a, uint32_t num_operands, const uint64_t *operands) {
uint32_t index = embed(a, num_operands, operands);
return pack_sum(num_operands, index);
}
uint64_t solver_Algebra_product(struct solver_Algebra *a, uint32_t num_operands, const uint64_t *operands) {
uint32_t index = embed(a, num_operands, operands);
return pack_product(num_operands, index);
}
uint64_t solver_Algebra_add(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
uint64_t operands[2] = {lhs, rhs};
return solver_Algebra_sum(a, 2, operands);
}
uint64_t solver_Algebra_multiply(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
uint64_t operands[2] = {lhs, rhs};
return solver_Algebra_product(a, 2, operands);
}
uint64_t solver_Algebra_negate(struct solver_Algebra *a, uint64_t expr) {
if(is_number(expr)) {
return number_negate(a, expr);
}
return solver_Algebra_multiply(a, solver_Algebra_integer(a, -1), expr);
}
uint64_t solver_Algebra_subtract(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return solver_Algebra_add(a, lhs, solver_Algebra_negate(a, rhs));
}
uint64_t solver_Algebra_divide(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return solver_Algebra_multiply(a, lhs, solver_Algebra_power(a, rhs, solver_Algebra_integer(a, -1)));
}
uint64_t solver_Algebra_power(struct solver_Algebra *a, uint64_t base, uint64_t exponent) {
uint64_t values[2];
values[0] = base;
values[1] = exponent;
uint32_t index = embed(a, 2, values);
return pack_power(index);
}
uint64_t solver_Algebra_equals(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
uint64_t values[2];
values[0] = lhs;
values[1] = rhs;
uint32_t index = embed(a, 2, values);
return pack_equals(index);
}
uint64_t solver_Algebra_not_equals(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
uint64_t values[2];
values[0] = lhs;
values[1] = rhs;
uint32_t index = embed(a, 2, values);
return pack_not_equals(index);
}
uint64_t solver_Algebra_less_than(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
uint64_t values[2];
values[0] = lhs;
values[1] = rhs;
uint32_t index = embed(a, 2, values);
return pack_less_than(index);
}
uint64_t solver_Algebra_greater_than(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
uint64_t values[2];
values[0] = lhs;
values[1] = rhs;
uint32_t index = embed(a, 2, values);
return pack_greater_than(index);
}
// --------------------------------------------------------------------------------------------------------------------
// solver_Algebra_show
#define PRECEDENCE_NUMBER 1000
#define PRECEDENCE_SUM 110
#define PRECEDENCE_PRODUCT 120
#define PRECEDENCE_POWER 130
static int precedence(uint64_t bits) {
struct Unpacked unpacked = unpack(bits);
switch(unpacked.tag) {
case Unpacked_Real:
case Unpacked_Variable:
case Unpacked_Integer:
case Unpacked_BigInteger:
case Unpacked_Fraction:
return PRECEDENCE_NUMBER;
case Unpacked_Power:
return PRECEDENCE_POWER;
case Unpacked_Sum:
return PRECEDENCE_SUM;
case Unpacked_Product:
return PRECEDENCE_PRODUCT;
default:
return 0;
}
}
static void show(struct solver_Algebra *a, uint64_t bits, bool parens);
static void show_real(struct solver_Algebra *a, uint64_t bits) {
printf("%f", unpack_real(bits));
}
static void show_variable(struct solver_Algebra *a, uint64_t bits) {
printf("%s", unpack_variable(bits));
}
static void show_boolean(struct solver_Algebra *a, uint64_t bits) {
bool v = unpack_boolean(bits);
printf("%s", v ? "true" : "false");
}
static void show_undefined(struct solver_Algebra *a, uint64_t bits) {
unpack_undefined(bits);
printf("undefined");
}
static void show_integer(struct solver_Algebra *a, uint64_t bits) {
printf("%lu", unpack_integer(bits));
}
static void show_big_integer(struct solver_Algebra *a, uint64_t bits) {
printf("%p", unpack_big_integer(bits));
}
static void show_fraction(struct solver_Algebra *a, uint64_t bits) {
uint32_t index = unpack_fraction(bits);
uint64_t car = a->values.data[index + 0];
uint64_t cdr = a->values.data[index + 1];
show(a, car, false);
printf("/");
show(a, cdr, false);
}
static void show_power(struct solver_Algebra *a, uint64_t bits) {
uint32_t index = unpack_power(bits);
uint64_t car = a->values.data[index + 0];
uint64_t cdr = a->values.data[index + 1];
show(a, car, precedence(car) < PRECEDENCE_POWER);
printf("/");
show(a, cdr, precedence(cdr) < PRECEDENCE_POWER);
}
static void show_sum(struct solver_Algebra *a, uint64_t bits) {
uint32_t count;
uint32_t index;
unpack_sum(bits, &count, &index);
for(uint32_t i = 0; i < count; i++) {
uint64_t operand = a->values.data[index + i];
if(i > 0) {
printf(" + ");
}
show(a, operand, precedence(operand) < PRECEDENCE_SUM);
}
}
static void show_product(struct solver_Algebra *a, uint64_t bits) {
uint32_t count;
uint32_t index;
unpack_sum(bits, &count, &index);
for(uint32_t i = 0; i < count; i++) {
uint64_t operand = a->values.data[index + i];
show(a, operand, precedence(operand) < PRECEDENCE_PRODUCT);
if(i > 0) {
printf(" * ");
}
}
}
static void show_equals(struct solver_Algebra *a, uint64_t bits) {
uint32_t index = unpack_equals(bits);
uint64_t car = a->values.data[index + 0];
uint64_t cdr = a->values.data[index + 1];
show(a, car, false);
printf(" == ");
show(a, cdr, false);
}
static void show_not_equals(struct solver_Algebra *a, uint64_t bits) {
uint32_t index = unpack_not_equals(bits);
uint64_t car = a->values.data[index + 0];
uint64_t cdr = a->values.data[index + 1];
show(a, car, false);
printf(" != ");
show(a, cdr, false);
}
static void show_less_than(struct solver_Algebra *a, uint64_t bits) {
uint32_t index = unpack_less_than(bits);
uint64_t car = a->values.data[index + 0];
uint64_t cdr = a->values.data[index + 1];
show(a, car, false);
printf(" < ");
show(a, cdr, false);
}
static void show_greater_than(struct solver_Algebra *a, uint64_t bits) {
uint32_t index = unpack_greater_than(bits);
uint64_t car = a->values.data[index + 0];
uint64_t cdr = a->values.data[index + 1];
show(a, car, false);
printf(" > ");
show(a, cdr, false);
}
static void show(struct solver_Algebra *a, uint64_t bits, bool parens) {
if(parens) printf("(");
switch(unpack_tag(bits)) {
case Unpacked_Real:
show_real(a, bits);
break;
case Unpacked_Variable:
show_variable(a, bits);
break;
case Unpacked_Boolean:
show_boolean(a, bits);
break;
case Unpacked_Undefined:
show_undefined(a, bits);
break;
case Unpacked_Integer:
show_integer(a, bits);
break;
case Unpacked_BigInteger:
show_big_integer(a, bits);
break;
case Unpacked_Fraction:
show_fraction(a, bits);
break;
case Unpacked_Power:
show_power(a, bits);
break;
case Unpacked_Sum:
show_sum(a, bits);
break;
case Unpacked_Product:
show_product(a, bits);
break;
case Unpacked_Equals:
show_equals(a, bits);
break;
case Unpacked_NotEquals:
show_not_equals(a, bits);
break;
case Unpacked_LessThan:
show_less_than(a, bits);
break;
case Unpacked_GreaterThan:
show_greater_than(a, bits);
break;
case Unpacked_Invalid:
break;
}
if(parens) printf(")");
}
void solver_Algebra_show(struct solver_Algebra *a, uint64_t bits) {
show(a, bits, false);
printf("\n");
}
// --------------------------------------------------------------------------------------------------------------------
// boolean_not
static uint64_t boolean_not(struct solver_Algebra *a, uint64_t expr_) {
if(expr_ == TAG_ATOM_BITS | 0) return TAG_ATOM_BITS | 1;
if(expr_ == TAG_ATOM_BITS | 1) return TAG_ATOM_BITS | 0;
return TAG_ATOM_BITS | 2;
}
// --------------------------------------------------------------------------------------------------------------------
// == !=
static uint64_t equals(struct solver_Algebra *a, uint64_t lhs_, uint64_t rhs_);
static uint64_t integer_integer_equals(struct solver_Algebra *a, uint64_t lhs_, uint64_t rhs_) {
int64_t lhs = unpack_integer(lhs_);
int64_t rhs = unpack_integer(rhs_);
return pack_boolean(lhs == rhs);
}
// TODO
static uint64_t equals(struct solver_Algebra *a, uint64_t lhs_, uint64_t rhs_) {
int lhs_tag = unpack_tag(lhs_);
int rhs_tag = unpack_tag(rhs_);
if(lhs_tag == Unpacked_Integer && rhs_tag == Unpacked_Integer) {
return integer_integer_equals(a, lhs_, rhs_);
}
if(lhs_tag != rhs_tag) {
return pack_boolean(false);
}
return pack_undefined();
}
static uint64_t not_equals(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return boolean_not(a, equals(lhs, rhs));
}
// --------------------------------------------------------------------------------------------------------------------
// < >
static uint64_t integer_integer_less_than(struct solver_Algebra *a, uint64_t lhs_, uint64_t rhs_) {
int64_t lhs = unpack_integer(lhs_);
int64_t rhs = unpack_integer(rhs_);
return pack_boolean(lhs < rhs);
}
// TODO
static uint64_t less_than(struct solver_Algebra *a, uint64_t lhs_, uint64_t rhs_) {
int lhs_tag = unpack_tag(lhs_);
int rhs_tag = unpack_tag(rhs_);
if(lhs_tag == Unpacked_Integer && rhs_tag == Unpacked_Integer) {
return integer_integer_less_than(a, lhs_, rhs_);
}
return pack_undefined();
}
static uint64_t greater_than(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return boolean_not(a, less_than(lhs, rhs));
}
// --------------------------------------------------------------------------------------------------------------------
// solver_Algebra_to_boolean
uint64_t solver_Algebra_to_boolean(struct solver_Algebra *a, uint64_t expr_) {
struct Unpacked expr = unpack(expr_);
if(expr.tag == Unpacked_Boolean) {
return expr_;
}
if(expr.tag == Unpacked_Equals || expr.tag == Unpacked_NotEquals || expr.tag == Unpacked_LessThan || expr.tag == Unpacked_GreaterThan) {
uint64_t car, cdr;
car = a->values.data[expr.pair.index + 0];
cdr = a->values.data[expr.pair.index + 1];
return expr.tag == Unpacked_Equals ? equals(a, car, cdr) :
expr.tag == Unpacked_NotEquals ? not_equals(a, car, cdr) :
expr.tag == Unpacked_LessThan ? less_than(a, car, cdr) :
expr.tag == Unpacked_GreaterThan ? greater_than(a, car, cdr) :
pack_undefined() ;
} else {
return pack_undefined();
}
}
// --------------------------------------------------------------------------------------------------------------------
// solver_Algebra_simplify
// these actually create values into the algebra
static uint64_t simplify(struct solver_Algebra *a, uint64_t expr);
static uint32_t embed(struct solver_Algebra *a, uint32_t count, const uint64_t *values) {
uint32_t index = a->values.length;
alias_Vector_space_for(&a->values, NULL, count);
alias_memory_copy(a->values.data + index, sizeof(*a->values.data) * (a->values.capacity - index), values, sizeof(*values) * count);
a->values.length += count;
return index;
}
static uint64_t simplify_real(struct solver_Algebra *a, double real) {
if(real == floor(real)) return pack_integer((int64_t)real);
return pack_real(real);
}
static uint64_t simplify_big_integer(struct solver_Algebra *a, void * big_integer) {
return pack_big_integer(big_integer);
}
static uint64_t simplify_fraction(struct solver_Algebra *a, uint64_t numerator, uint64_t denominator) {
uint64_t values[2];
values[0] = numberator;
values[1] = denominator;
uint32_t index = embed(a, 2, values);
return pack_fraction(index);
}
static uint64_t simplify_power(struct solver_Algebra *a, uint64_t base, uint64_t exponent) {
uint64_t values[2];
values[0] = simplify(a, base);
values[1] = simplify(a, exponent);
if(is_number(values[0]) && is_number(values[1])) {
return number_pow(values[0], values[1]);
}
uint32_t index = embed(a, 2, values);
return pack_fraction(index);
}
static uint64_t simplify_sum(struct solver_Algebra *a, uint32_t num_operands, const uint64_t * operands) {
struct {
uint32_t num_operands;
const uint64_t * operands;
} stack[3], *top = stack + 3;
if(num_operands == 0) {
return pack_integer(a, 0);
}
if(num_operands == 1) {
return operands[0];
}
if(num_operands == 2) {
if(is_number(operands[0]) && is_number(operands[1])) {
return number_add(a, operands[0], operands[1]);
}
if(is_sum(operands[0])) || is_sum(operands[1])) {
--top;
if(is_sum(operands[0])) {
uint32_t index;
unpack_sum(operands[0], &top->num_operands, &index);
top->operands = a->values.data + index;
} else {
top->num_operands = 1;
top->operands = &operands[0];
}
--top;
if(is_sum(operands[1])) {
uint32_t index;
unpack_sum(operands[1], &top->num_operands, &index);
top->operands = a->values.data + index;
} else {
top->num_operands = 1;
top->operands = &operands[1];
}
}
}
}
static uint64_t simplify(struct solver_Algebra *a, uint64_t expr) {
struct Unpacked unpacked = unpack(expr);
switch(unpacked.tag) {
case Unpacked_Real:
return simplify_real(a, unpacked.real);
case Unpacked_Variable:
return expr;
case Unpacked_Boolean:
return expr;
case Unpacked_Undefined:
return expr;
case Unpacked_Integer:
return expr;
case Unpacked_BigInteger:
return simplify_big_integer(a, unpacked.big_integer);
case Unpacked_Fraction:
return simplify_fraction(a, a->values.data[unpacked.fraction.index + 0], a->values.data[unpacked.fraction.index + 1]);
case Unpacked_Power:
return simplify_power(a, a->values.data[unpacked.power.index + 0], a->values.data[unpacked.power.index + 1]);
case Unpacked_Sum:
return simplify_sum(a, unpacked.sum.count, a->values.data + unpacked.sum.index);
case Unpacked_Product:
return simplify_product(a, unpacked.sum.count, a->values.data + unpacked.sum.index);
case Unpacked_Equals:
return simplify_equals(a, a->values.data[unpacked.power.index + 0], a->values.data[unpacked.power.index + 1]);
case Unpacked_NotEquals:
return simplify_not_equals(a, a->values.data[unpacked.power.index + 0], a->values.data[unpacked.power.index + 1]);
case Unpacked_LessThan:
return simplify_less_than(a, a->values.data[unpacked.power.index + 0], a->values.data[unpacked.power.index + 1]);
case Unpacked_GreaterThan:
return simplify_greater_than(a, a->values.data[unpacked.power.index + 0], a->values.data[unpacked.power.index + 1]);
case Unpacked_Invalid:
break;
}
}
uint64_t solver_Algebra_simplify(struct solver_Algebra *a, uint64_t expr) {
return simplify(a, expr);
}
#if 0
// -- numerator
double solver_Algebra_numerator(struct solver_Algebra *a, double expr) {
uint64_t payload;
switch(_decode(expr, &payload)) {
case FRACTION:
return first(a, expr);
default:
return expr;
}
}
// -- denominator
double solver_Algebra_denominator(struct solver_Algebra *a, double expr) {
uint64_t payload;
switch(_decode(expr, &payload)) {
case FRACTION:
return second(a, expr);
default:
return one(a);
}
}
// -- simplify
static double _simplify_power(struct solver_Algebra *a, double base, double exponent) {
base = solver_Algebra_simplify(base);
exponent = solver_Algebra_simplify(exponent);
if(is_integer(base, 0)) return integer(0);
if(is_integer(base, 1)) return integer(1);
if(is_integer(exponent, 0)) return integer(1);
if(is_integer(exponent, 1)) return base;
uint64_t base_payload;
uint64_t exponent_payload;
int base_tag = _decode(base, &base_payload);
int exponent_tag = _decode(exponent, &exponent_payload);
if(base_tag == INTEGER) {
if(exponent_tag == INTEGER) {
} else if(exponent_tag == BIG_INTEGER) {
} else if(exponent_tag == FRACTION) {
} else if(exponent_tag == REAL) {
}
} else if(base_tag == BIG_INTEGER) {
if(exponent_tag == INTEGER) {
} else if(exponent_tag == BIG_INTEGER) {
} else if(exponent_tag == FRACTION) {
} else if(exponent_tag == REAL) {
}
} else if(base_tag == FRACTION) {
if(exponent_tag == INTEGER) {
} else if(exponent_tag == BIG_INTEGER) {
} else if(exponent_tag == FRACTION) {
} else if(exponent_tag == REAL) {
}
} else if(base_tag == REAL) {
if(exponent_tag == INTEGER) {
} else if(exponent_tag == BIG_INTEGER) {
} else if(exponent_tag == FRACTION) {
} else if(exponent_tag == REAL) {
return pow(base, exponent);
}
}
return solver_Algebra_power(a, base, exponent);
}
// numbers
static double _number_gcd(struct solver_Algebra *a, double lhs, double rhs);
static double _number_add(struct solver_Algebra *a, double lhs, double rhs);
static double _number_multiply(struct solver_Algebra *a, double lhs, double rhs);
static double _integer_integer_add(struct solver_Algebra *a, double lhs, double rhs) {
}
static double _number_add(struct solver_Algebra *a, double lhs, double rhs) {
uint64_t lhs_payload;
int lhs_tag = _decode(lhs, &lhs_payload);
uint64_t rhs_payload;
int rhs_tag = _decode(rhs, &rhs_payload);
if(lhs_tag == INTEGER) {
int64_t lhs_value = _decode_integer(lhs);
if(rhs_tag == INTEGER) {
int64_t rhs_value = _decode_integer(rhs);
return solver_Algebra_integer(a, lhs + rhs);
} else if(rhs_tag == BIG_INTEGER) {
// TODO
} else if(rhs_tag == FRACTION) {
double numerator = first(a, rhs);
double denominator = second(a, rhs);
lhs = _number_multiply(a, lhs, denominator);
numerator = _number_add(a, lhs, numerator);
return solver_Algebra_fraction(a, numerator, denominator);
} else if(rhs_tag == REAL) {
return lhs_value * rhs;
}
} else if(lhs_tag == BIG_INTEGER) {
// TODO
if(rhs_tag == INTEGER) {
} else if(rhs_tag == BIG_INTEGER) {
} else if(rhs_tag == FRACTION) {
} else if(rhs_tag == REAL) {
}
} else if(lhs_tag == FRACTION) {
double lhs_numerator = first(a, lhs);
double lhs_denominator = second(a, lhs);
if(rhs_tag == INTEGER) {
int64_t rhs_value = _decode_integer(rhs);
rhs = _number_multiply(a, rhs, lhs_denominator);
lhs_numerator = _number_add(a, rhs, lhs_numerator);
return solver_Algebra_fraction(a, lhs_numerator, lhs_denominator);
} else if(rhs_tag == BIG_INTEGER) {
// TODO
} else if(rhs_tag == FRACTION) {
double rhs_numerator = first(a, rhs);
double rhs_denominator = second(a, rhs);
double denominator = _number_gcd(a, lhs_denominator, rhs_denominator);
} else if(rhs_tag == REAL) {
}
} else if(lhs_tag == REAL) {
if(rhs_tag == INTEGER) {
} else if(rhs_tag == BIG_INTEGER) {
// TODO
} else if(rhs_tag == FRACTION) {
} else if(rhs_tag == REAL) {
return rhs + lhs;
}
}
}
static double _number_multiply(struct solver_Algebra *a, double lhs, double rhs) {
uint64_t lhs_payload;
int lhs_tag = _decode(lhs, &lhs_payload);
uint64_t rhs_payload;
int rhs_tag = _decode(rhs, &rhs_payload);
if(lhs_tag == INTEGER) {
if(rhs_tag == INTEGER) {
} else if(rhs_tag == BIG_INTEGER) {
} else if(rhs_tag == FRACTION) {
} else if(rhs_tag == REAL) {
}
} else if(lhs_tag == BIG_INTEGER) {
if(rhs_tag == INTEGER) {
} else if(rhs_tag == BIG_INTEGER) {
} else if(rhs_tag == FRACTION) {
} else if(rhs_tag == REAL) {
}
} else if(lhs_tag == FRACTION) {
if(rhs_tag == INTEGER) {
} else if(rhs_tag == BIG_INTEGER) {
} else if(rhs_tag == FRACTION) {
} else if(rhs_tag == REAL) {
}
} else if(lhs_tag == REAL) {
if(rhs_tag == INTEGER) {
} else if(rhs_tag == BIG_INTEGER) {
} else if(rhs_tag == FRACTION) {
} else if(rhs_tag == REAL) {
return lhs * rhs;
}
}
}
static void _simplify_sum_recursive(struct solver_Algebra *a, uint32_t num_operands, const double *operands, uint32_t *result_num_operands, double ** result_operands) {
if(num_operands == 2) {
uint64_t lhs_payload, rhs_payload;
int lhs_tag = _decode(operands[0], &lhs_payload);
int rhs_tag = _decode(operands[1], &rhs_payload);
if(lhs_tag == SUM && rhs_tag == SUM) {
_simplify_sum_merge(a,
(lhs_payload >> 24) & 0x07FFull, a->values.data + (lhs_payload & 0x0FFFull),
(rhs_payload >> 24) & 0x07FFull, a->values.data + (rhs_payload & 0x0FFFull),
result_num_operands, result_operands
);
return;
}
if(lhs_tag == SUM) {
_simplify_sum_merge(a,
(lhs_payload >> 24) & 0x07FFull, a->values.data + (lhs_payload & 0x0FFFull),
1, &operands[1],
result_num_operands, result_operands
);
return;
}
if(rhs_tag == SUM) {
_simplify_sum_merge(a,
1, &operands[0],
(rhs_payload >> 24) & 0x07FFull, a->values.data + (rhs_payload & 0x0FFFull),
result_num_operands, result_operands
);
return;
}
if(_precedence(operands[0]) == PRECEDENCE_NUMBER && _precedence(operands[1]) == PRECEDENCE_NUMBER) {
}
}
}
static double _simplify_sum(struct solver_Algebra *a, uint32_t num_operands, const double *operands) {
if(num_operands == 1) {
return operands[0];
}
uint32_t result_num_operands;
double * result_operands;
double result;
_simplify_sum_recursive(a, num_operands, operands, &result_num_operands, &result_operands);
if(result_num_operands == 0) {
return integer(0);
}
if(result_num_operands == 1) {
result = result_operands[1];
} else {
result = solver_Algebra_sum(a, result_num_operands, result_operands);
}
free(result_operands);
return result;
}
double solver_Algebra_simplify(struct solver_Algebra *a, double expr) {
uint64_t payload;
switch(_decode(expr, &payload)) {
case REAL: return expr;
case VARIABLE: return expr;
case UNDEFINED: return expr;
case INTEGER: return expr;
case BIG_INTEGER: return expr;
case FRACTION: return expr;
case POWER: return _simplify_power(a, a->values.data[(payload & 0x0FFFull) + 0], a->values.data[(payload & 0x0FFFull) + 1]);
case SUM: return _simplify_sum(a, (payload >> 24) & 0x07FFull, a->values.data + (payload & 0x0FFFull));
case PRODUCT: return _simplify_product(a, (payload >> 24) & 0x07FFull, a->values.data + (payload & 0x0FFFull));
case INVALID: return expr;
}
}
#endif