ZPW7JFL5ZR4T77O5Y4CRLCJTCKHYKEERP2JT2OIYZO5A7PIJSSBAC
assert_is_true(&a, "5 + x + 2 == 7 + x");
assert_is_true(&a, "3 + x + 5 + x == 8 + 2 * x");
assert_is_true(&a, "x + y + z + x + y + z == 2*x + 2*y + 2*z");
assert_is_true(&a, "10 - x == 10 + x * -1");
assert_is_true(&a, "10 + x == 10 + x * -1 * -1");
assert_is_true(&a, "10 + x == 10 + x * -1 * -1");
assert_is_true(&a, "10 == 100 / 10");
}
// n • x + x => (n + 1) • x
if(is_product(lhs) && get_list_count(lhs) == 2) {
uint64_t num = get_index(a, lhs, 0);
if(is_number(num)) {
uint64_t var = get_index(a, lhs, 1);
if(is_variable(var) && is_variable(rhs) && alias_str_same(unpack_variable(var), unpack_variable(rhs))) {
uint64_t product_values[2];
product_values[0] = number_add(a, num, LITERAL_ONE);
product_values[1] = rhs;
*merged = embed_product(a, 2, product_values);
return true;
}
}
}
// x + n • x => (n + 1) • x
if(is_product(rhs) && get_list_count(rhs) == 2) {
uint64_t num = get_index(a, rhs, 0);
if(is_number(num)) {
uint64_t var = get_index(a, rhs, 1);
if(is_variable(var) && is_variable(lhs) && alias_str_same(unpack_variable(var), unpack_variable(lhs))) {
uint64_t product_values[2];
product_values[0] = number_add(a, num, LITERAL_ONE);
product_values[1] = lhs;
*merged = embed_product(a, 2, product_values);
return true;
}
}
static bool product_merge_single_term(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs, uint64_t *merged) {
if(is_number(lhs) && is_number(rhs)) {
*merged = number_multiply(a, lhs, rhs);
return true;
}
if(is_number(lhs) && lhs == LITERAL_ZERO) {
*merged = LITERAL_ZERO;
return true;
}
if(is_number(rhs) && rhs == LITERAL_ZERO) {
*merged = LITERAL_ZERO;
return true;
}
if(is_number(lhs) && lhs == LITERAL_ONE) {
*merged = rhs;
return true;
}
if(is_number(rhs) && rhs == LITERAL_ONE) {
*merged = lhs;
return true;
}
return false;
}
if(is_number(values[0]) && is_number(values[1])) {
return number_multiply(a, values[0], values[1]);
if(product_merge_single_term(a, values[0], values[1], &merged)) {
return merged;
}
}
uint32_t new_count = 0;
uint64_t * new_values = alias_stack_allocation(sizeof(*new_values) * count, alignof(*new_values));
for(uint32_t i = 0; i < count; i++) {
uint32_t k;
for(k = 0; k < new_count; k++) {
if(product_merge_single_term(a, new_values[k], values[i], &merged)) {
if(merged == LITERAL_ZERO) return LITERAL_ZERO;
new_values[k] = merged;
break;
}
}
if(k == new_count) {
if(values[i] == LITERAL_ZERO) return LITERAL_ZERO;
new_values[new_count++] = values[i];
}
}
if(new_count == 0) return LITERAL_ZERO;
if(new_count == 1) return new_values[0];
if(new_count == 2) {
if(product_merge_single_term(a, new_values[0], new_values[1], &merged)) {
return merged;
uint64_t solver_Algebra_power(struct solver_Algebra *a, uint64_t base, uint64_t exponent) {
static uint64_t embed_power(struct solver_Algebra *a, uint64_t base, uint64_t exponent) {
if(is_number(base) && is_number(exponent)) {
return number_power(a, base, exponent);
}
if(is_number(base) && base == LITERAL_ZERO) return LITERAL_ZERO;
if(is_number(base) && base == LITERAL_ONE) return LITERAL_ONE;
if(is_number(exponent) && exponent == LITERAL_ZERO) return LITERAL_ONE;
if(is_number(exponent) && exponent == LITERAL_ONE) return base;
uint64_t solver_Algebra_power(struct solver_Algebra *a, uint64_t base, uint64_t exponent) {
return embed_power(a, base, exponent);
}
primary(O) ::= fraction(F). { O = F; }
//primary(O) ::= fraction(F). { O = F; }
%type unary { uint64_t }
unary(O) ::= MACRON unary(A). { O = solver_Algebra_negate(extra.a, A); }
unary(O) ::= HYPHEN_MINUS unary(B). { O = solver_Algebra_negate(extra.a, B); }
unary(O) ::= primary(C). { O = C; }
static uint64_t integer_integer_add(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return pack_integer(unpack_integer(lhs) + unpack_integer(rhs));
static uint64_t number_add__smallint__smallint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
int64_t l = unpack_smallint(lhs);
int64_t r = unpack_smallint(rhs);
int64_t c = l + r;
return pack_smallint(c);
static uint64_t integer_integer_multiply(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
// TODO big integer upgrade
return pack_integer(unpack_integer(lhs) * unpack_integer(rhs));
static uint64_t number_multiply__smallint__smallint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return pack_smallint(unpack_smallint(lhs) * unpack_smallint(rhs));
static uint64_t integer_multiply(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
static uint64_t number_multiply__smallint__fraction(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
uint64_t n = get_car(a, rhs);
uint64_t d = get_cdr(a, rhs);
return solver_Algebra_fraction(a, number_multiply(a, lhs, n), d);
}
static uint64_t number_multiply__smallint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
static int integer_integer_compare(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
// TODO big integer upgrade
return unpack_integer(rhs) - unpack_integer(lhs);
static uint64_t number_power__smallint__smallint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
int64_t base = unpack_smallint(lhs);
int64_t exp = unpack_smallint(rhs);
bool n = exp < 0;
if(exp) {
exp = -exp;
}
int32_t result = 1;
for(;;) {
if(exp & 1) {
result *= base;
}
exp >>= 1;
if(exp == 0) {
break;
}
base *= base;
}
if(n) {
return solver_Algebra_fraction(a, LITERAL_ONE, pack_smallint(result));
} else {
return pack_smallint(result);
}
case Tag_Integer:
return integer_compare(a, lhs, rhs);
case Tag_SmallInt:
return number_power__smallint(a, lhs, rhs);
default:
return pack_undefined();
}
}
static int number_compare__smallint__smallint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return unpack_smallint(rhs) - unpack_smallint(lhs);
}
static int number_compare__smallint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
assert(is_number(rhs));
switch(get_tag(rhs)) {
case Tag_SmallInt:
return number_compare__smallint__smallint(a, lhs, rhs);
static uint64_t embed_fraction(struct solver_Algebra *a, uint64_t numerator, uint64_t denominator) {
uint64_t values[2] = {numerator, denominator};
uint32_t index = embed_values(a, 2, values);
return pack_fraction(index);
static int number_compare(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
assert(is_number(lhs));
assert(is_number(rhs));
switch(get_tag(lhs)) {
case Tag_SmallInt:
return number_compare__smallint(a, lhs, rhs);
default:
return 0;
}
#define PAIR_INDEX_MASK 0x0000000000FFFFFFull
#define LIST_COUNT_MASK 0x00007FFFFF000000ull
#define LIST_INDEX_MASK 0x0000000000FFFFFFull
#define PAIR_INDEX_MASK 0x0000000000FFFFFFull // 24-bits
#define LIST_COUNT_MASK 0x00007FFFFF000000ull // 23-bits
#define LIST_INDEX_MASK 0x0000000000FFFFFFull // 24-bits
#define INTEGER_MASK 0xFFFE000000000000ull // mask ignores small or large integer descriminating bit
#define INTEGER_BITS 0x7FF2000000000000ull
#define INTEGER_NEG_FLAG_BIT 0x0000800000000000ull
#define INTEGER_COUNT_MASK 0x00007FFFFF000000ull // 23-bits
#define INTEGER_INDEX_MASK 0x0000000000FFFFFFull // 24-bits
#define INTEGER_SMALL_MASK 0x00007FFFFFFFFFFFull // 47-bits
#define LITERAL_FALSE (TAG_ATOM_BITS | 0)
#define LITERAL_TRUE (TAG_ATOM_BITS | 1)
#define LITERAL_UNDEFINED (TAG_ATOM_BITS | 2)
#define LITERAL_ZERO (TAG_SMALLINT_BITS | 0)
#define LITERAL_ONE (TAG_SMALLINT_BITS | 1)
#define LITERAL_TWO (TAG_SMALLINT_BITS | 2)
#define LITERAL_NEGATIVE_ONE (TAG_SMALLINT_BITS | INTEGER_NEG_FLAG_BIT | 1)
static uint32_t get_integer_count(uint64_t expr) {
assert((expr & TAG_MASK) == TAG_LARGEINT_BITS);
return (expr & INTEGER_COUNT_MASK) >> 24;
}
static uint32_t get_integer_index(uint64_t expr) {
assert((expr & TAG_MASK) == TAG_LARGEINT_BITS);
return (expr & INTEGER_INDEX_MASK);
}
struct EncodedList {
uint32_t count;
uint32_t index;
};
DEFINE_ENCODING(
integer, int32_t,
{ return (packed & TAG_MASK) == TAG_INTEGER_BITS; },
{
union Int32x2 _;
_.i[0] = unpacked;
_.i[1] = unpacked;
return TAG_INTEGER_BITS | (_.u & PAYLOAD_MASK);
},
{
union Int32x2 _;
_.u = packed & PAYLOAD_MASK;
return _.i[0] | _.i[1];
static inline bool is_smallint(uint64_t packed) {
return (packed & TAG_MASK) == TAG_SMALLINT_BITS;
}
static inline uint64_t pack_smallint(int64_t value) {
uint64_t result = TAG_SMALLINT_BITS;
if(value < 0) {
result |= INTEGER_NEG_FLAG_BIT;
value *= -1;
)
assert((value & ~INTEGER_SMALL_MASK) == 0);
return result | value;
}
static inline int64_t unpack_smallint(uint64_t expr) {
assert(is_smallint(expr));
return (((expr & INTEGER_NEG_FLAG_BIT) == INTEGER_NEG_FLAG_BIT) ? -1 : 1) * ((int64_t)(expr & INTEGER_SMALL_MASK));
}
struct BigInteger {
int64_t big;
};
DEFINE_ENCODING(
big_integer, struct BigInteger *,
{ return (packed & TAG_MASK) == TAG_BIGINT_BITS; },
{ return TAG_BIGINT_BITS | ((uint64_t)unpacked & PAYLOAD_MASK); },
{ return (struct BigInteger *)(packed & PAYLOAD_MASK); }
)
static inline bool is_largeint(uint64_t packed) {
return (packed & TAG_MASK) == TAG_LARGEINT_BITS;
}
static inline uint64_t pack_largeint(uint64_t flags, uint32_t count, uint32_t index) {
return TAG_LARGEINT_BITS | flags | (count << 24) | index;
}
static inline struct EncodedList unpack_largeint(uint64_t packed) {
struct EncodedList _;
_.count = (packed & INTEGER_COUNT_MASK) >> 24;
_.index = (packed & INTEGER_INDEX_MASK);
return _;
}
static bool equals__integer_integer(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return unpack_integer(lhs) == unpack_integer(rhs);
static bool equals__smallint__smallint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return unpack_smallint(lhs) == unpack_smallint(rhs);
static bool equals__big_integer_big_integer(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) { return false; }
static bool equals__big_integer(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
static bool equals__largeint__largeint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) { return false; }
static bool equals__largeint(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
static bool equals__equals_equals(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return equals(a, get_car(a, lhs), get_car(a, rhs)) && equals(a, get_cdr(a, lhs), get_cdr(a, rhs));
static bool equals__equals__equals(struct solver_Algebra *a, uint64_t lhs, uint64_t rhs) {
return equals(a, get_car(a, lhs), get_car(a, rhs)) &&
equals(a, get_cdr(a, lhs), get_cdr(a, rhs));
case Tag_Integer:
return equals__integer(a, lhs, rhs);
case Tag_BigInteger:
return equals__big_integer(a, lhs, rhs);
case Tag_SmallInt:
return equals__smallint(a, lhs, rhs);
case Tag_LargeInt:
return equals__largeint(a, lhs, rhs);