From d96b8c7d12fc61ec609d6138627b9d6d18139a9a Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sat, 28 Oct 2023 00:00:21 +0300 Subject: move to monorepo + Will probably have to make some changes to dir layout to make things make more sense --- core/t9.inc | 729 +++++++++++++++++++++++++++++++++++++++++++++++++++ core/tests/add.c | 23 ++ core/tests/comp.c | 6 + core/tests/diop.c | 21 ++ core/tests/div.c | 22 ++ core/tests/from_to.c | 10 + core/tests/mul.c | 28 ++ core/tests/sub.c | 22 ++ core/tests/unop.c | 24 ++ core/tri.h | 711 +++++++++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 1596 insertions(+) create mode 100644 core/t9.inc create mode 100644 core/tests/add.c create mode 100644 core/tests/comp.c create mode 100644 core/tests/diop.c create mode 100644 core/tests/div.c create mode 100644 core/tests/from_to.c create mode 100644 core/tests/mul.c create mode 100644 core/tests/sub.c create mode 100644 core/tests/unop.c create mode 100644 core/tri.h (limited to 'core') diff --git a/core/t9.inc b/core/t9.inc new file mode 100644 index 0000000..4d922ae --- /dev/null +++ b/core/t9.inc @@ -0,0 +1,729 @@ +0, +1, +6, +4, +5, +26, +24, +25, +18, +16, +17, +22, +20, +21, +106, +104, +105, +98, +96, +97, +102, +100, +101, +74, +72, +73, +66, +64, +65, +70, +68, +69, +90, +88, +89, +82, +80, +81, +86, +84, +85, +426, +424, +425, +418, +416, +417, +422, +420, +421, +394, +392, +393, +386, +384, +385, +390, +388, +389, +410, +408, +409, +402, +400, +401, +406, +404, +405, +298, +296, +297, +290, +288, +289, +294, +292, +293, +266, +264, +265, +258, +256, +257, +262, +260, +261, +282, +280, +281, +274, +272, +273, +278, +276, +277, +362, +360, +361, +354, +352, +353, +358, +356, +357, +330, +328, +329, +322, +320, +321, +326, +324, +325, +346, +344, +345, +338, +336, +337, +342, +340, +341, +1706, +1704, +1705, +1698, +1696, +1697, +1702, +1700, +1701, +1674, +1672, +1673, +1666, +1664, +1665, +1670, +1668, +1669, +1690, +1688, +1689, +1682, +1680, +1681, +1686, +1684, +1685, +1578, +1576, +1577, +1570, +1568, +1569, +1574, +1572, +1573, +1546, +1544, +1545, +1538, +1536, +1537, +1542, +1540, +1541, +1562, +1560, +1561, +1554, +1552, +1553, +1558, +1556, +1557, +1642, +1640, +1641, +1634, +1632, +1633, +1638, +1636, +1637, +1610, +1608, +1609, +1602, +1600, +1601, +1606, +1604, +1605, +1626, +1624, +1625, +1618, +1616, +1617, +1622, +1620, +1621, +1194, +1192, +1193, +1186, +1184, +1185, +1190, +1188, +1189, +1162, +1160, +1161, +1154, +1152, +1153, +1158, +1156, +1157, +1178, +1176, +1177, +1170, +1168, +1169, +1174, +1172, +1173, +1066, +1064, +1065, +1058, +1056, +1057, +1062, +1060, +1061, +1034, +1032, +1033, +1026, +1024, +1025, +1030, +1028, +1029, +1050, +1048, +1049, +1042, +1040, +1041, +1046, +1044, +1045, +1130, +1128, +1129, +1122, +1120, +1121, +1126, +1124, +1125, +1098, +1096, +1097, +1090, +1088, +1089, +1094, +1092, +1093, +1114, +1112, +1113, +1106, +1104, +1105, +1110, +1108, +1109, +1450, +1448, +1449, +1442, +1440, +1441, +1446, +1444, +1445, +1418, +1416, +1417, +1410, +1408, +1409, +1414, +1412, +1413, +1434, +1432, +1433, +1426, +1424, +1425, +1430, +1428, +1429, +1322, +1320, +1321, +1314, +1312, +1313, +1318, +1316, +1317, +1290, +1288, +1289, +1282, +1280, +1281, +1286, +1284, +1285, +1306, +1304, +1305, +1298, +1296, +1297, +1302, +1300, +1301, +1386, +1384, +1385, +1378, +1376, +1377, +1382, +1380, +1381, +1354, +1352, +1353, +1346, +1344, +1345, +1350, +1348, +1349, +1370, +1368, +1369, +1362, +1360, +1361, +1366, +1364, +1365, +6826, +6824, +6825, +6818, +6816, +6817, +6822, +6820, +6821, +6794, +6792, +6793, +6786, +6784, +6785, +6790, +6788, +6789, +6810, +6808, +6809, +6802, +6800, +6801, +6806, +6804, +6805, +6698, +6696, +6697, +6690, +6688, +6689, +6694, +6692, +6693, +6666, +6664, +6665, +6658, +6656, +6657, +6662, +6660, +6661, +6682, +6680, +6681, +6674, +6672, +6673, +6678, +6676, +6677, +6762, +6760, +6761, +6754, +6752, +6753, +6758, +6756, +6757, +6730, +6728, +6729, +6722, +6720, +6721, +6726, +6724, +6725, +6746, +6744, +6745, +6738, +6736, +6737, +6742, +6740, +6741, +6314, +6312, +6313, +6306, +6304, +6305, +6310, +6308, +6309, +6282, +6280, +6281, +6274, +6272, +6273, +6278, +6276, +6277, +6298, +6296, +6297, +6290, +6288, +6289, +6294, +6292, +6293, +6186, +6184, +6185, +6178, +6176, +6177, +6182, +6180, +6181, +6154, +6152, +6153, +6146, +6144, +6145, +6150, +6148, +6149, +6170, +6168, +6169, +6162, +6160, +6161, +6166, +6164, +6165, +6250, +6248, +6249, +6242, +6240, +6241, +6246, +6244, +6245, +6218, +6216, +6217, +6210, +6208, +6209, +6214, +6212, +6213, +6234, +6232, +6233, +6226, +6224, +6225, +6230, +6228, +6229, +6570, +6568, +6569, +6562, +6560, +6561, +6566, +6564, +6565, +6538, +6536, +6537, +6530, +6528, +6529, +6534, +6532, +6533, +6554, +6552, +6553, +6546, +6544, +6545, +6550, +6548, +6549, +6442, +6440, +6441, +6434, +6432, +6433, +6438, +6436, +6437, +6410, +6408, +6409, +6402, +6400, +6401, +6406, +6404, +6405, +6426, +6424, +6425, +6418, +6416, +6417, +6422, +6420, +6421, +6506, +6504, +6505, +6498, +6496, +6497, +6502, +6500, +6501, +6474, +6472, +6473, +6466, +6464, +6465, +6470, +6468, +6469, +6490, +6488, +6489, +6482, +6480, +6481, +6486, +6484, +6485, +4778, +4776, +4777, +4770, +4768, +4769, +4774, +4772, +4773, +4746, +4744, +4745, +4738, +4736, +4737, +4742, +4740, +4741, +4762, +4760, +4761, +4754, +4752, +4753, +4758, +4756, +4757, +4650, +4648, +4649, +4642, +4640, +4641, +4646, +4644, +4645, +4618, +4616, +4617, +4610, +4608, +4609, +4614, +4612, +4613, +4634, +4632, +4633, +4626, +4624, +4625, +4630, +4628, +4629, +4714, +4712, +4713, +4706, +4704, +4705, +4710, +4708, +4709, +4682, +4680, +4681, +4674, +4672, +4673, +4678, +4676, +4677, +4698, +4696, +4697, +4690, +4688, +4689, +4694, +4692, +4693, +4266, +4264, +4265, +4258, +4256, +4257, +4262, +4260, +4261, +4234, +4232, +4233, +4226, +4224, +4225, +4230, +4228, +4229, +4250, +4248, +4249, +4242, +4240, +4241, +4246, +4244, +4245, +4138, +4136, +4137, +4130, +4128, +4129, +4134, +4132, +4133, +4106, +4104, +4105, +4098, diff --git a/core/tests/add.c b/core/tests/add.c new file mode 100644 index 0000000..3d733ce --- /dev/null +++ b/core/tests/add.c @@ -0,0 +1,23 @@ +#include +#include + +int main(int argc, char *argv[]) +{ + assert(argc == 2); + char *s = argv[1]; + tri_t a = tri_parse_default(s, strlen(s)); + tri_t one = tri_from(1); + + int64_t ba = tri_to(a); + + for (size_t i = 0; i < 1000000000; ++i) { + a = tri_add(a, one); + } + + assert(ba + 1000000000 == tri_to(a)); + + char r[32]; + size_t l = tri_fmt_default(r, 32, a); + r[l] = '\0'; + printf("%s\n", r); +} diff --git a/core/tests/comp.c b/core/tests/comp.c new file mode 100644 index 0000000..b4ac94d --- /dev/null +++ b/core/tests/comp.c @@ -0,0 +1,6 @@ +#include + +int main() +{ + /* test comparisons */ +} diff --git a/core/tests/diop.c b/core/tests/diop.c new file mode 100644 index 0000000..1f9aea4 --- /dev/null +++ b/core/tests/diop.c @@ -0,0 +1,21 @@ +#include + +static tri_t f; + +static tri_t filter(tri_t t) +{ + tri_t r = tri_diop(OON, OOO, OOP, t, f); + return r; +} + +int main() +{ + /* very much not enough testing */ + f = tri_parse_default("111111111", 9); + + tri_t a = tri_parse_default("iii000111", 9); + tri_t b = tri_parse_default("i01i01i01", 9); + + tri_t r = tri_diop(NNN, NNN, NNN, a, b); + assert(tri_eq(filter(r), tri_parse_default("iiiiiiiii", 9))); +} diff --git a/core/tests/div.c b/core/tests/div.c new file mode 100644 index 0000000..07e429d --- /dev/null +++ b/core/tests/div.c @@ -0,0 +1,22 @@ +#include +#include + +int main(int argc, char *argv[]) +{ + assert(argc == 2); + char *s = argv[1]; + tri_t a = tri_parse_default(s, strlen(s)); + tri_t one = tri_from(1); + + trival_t ba = tri_to(a); + + for (size_t i = 0; i < 1000000000; ++i) + a = tri_div(a, one); + + assert(ba == tri_to(a)); + + char r[32]; + size_t l = tri_fmt_default(r, 32, a); + r[l] = '\0'; + printf("%s\n", r); +} diff --git a/core/tests/from_to.c b/core/tests/from_to.c new file mode 100644 index 0000000..d6a392d --- /dev/null +++ b/core/tests/from_to.c @@ -0,0 +1,10 @@ +#include + +int main() +{ + /* increment by prime to hopefully somewhat randomly test patterns */ + for (int64_t i = TRI_MIN; i < TRI_MAX; i += 1048009) { + tri_t t = tri_from(i); + assert(tri_to(t) == i); + } +} diff --git a/core/tests/mul.c b/core/tests/mul.c new file mode 100644 index 0000000..55d3af6 --- /dev/null +++ b/core/tests/mul.c @@ -0,0 +1,28 @@ +#include +#include + +int main(int argc, char *argv[]) +{ + assert(argc == 2); + char *s = argv[1]; + tri_t a = tri_parse_default(s, strlen(s)); + tri_t one = tri_from(1); + + for (int64_t i = -13; i <= 13; ++i) { + tri_t b = tri_from(i); + b = tri_mul(b, one); + assert(tri_to(b) == i); + } + + int64_t ba = tri_to(a); + + for (size_t i = 0; i < 1000000000; ++i) + a = tri_mul(a, one); + + assert(ba == tri_to(a)); + + char r[32]; + size_t l = tri_fmt_default(r, 32, a); + r[l] = '\0'; + printf("%s\n", r); +} diff --git a/core/tests/sub.c b/core/tests/sub.c new file mode 100644 index 0000000..41c4037 --- /dev/null +++ b/core/tests/sub.c @@ -0,0 +1,22 @@ +#include +#include + +int main(int argc, char *argv[]) +{ + assert(argc == 2); + char *s = argv[1]; + tri_t a = tri_parse_default(s, strlen(s)); + tri_t one = tri_from(1); + + int64_t ba = tri_to(a); + + for (size_t i = 0; i < 1000000000; ++i) + a = tri_sub(a, one); + + assert(ba - 1000000000 == tri_to(a)); + + char r[32]; + size_t l = tri_fmt_default(r, 32, a); + r[l] = '\0'; + printf("%s\n", r); +} diff --git a/core/tests/unop.c b/core/tests/unop.c new file mode 100644 index 0000000..a63e420 --- /dev/null +++ b/core/tests/unop.c @@ -0,0 +1,24 @@ +#include + +int main() +{ + /* technically speaking there are only 27 cases to test, and they could + * potentially all checked for manually, but this is good enough for now + */ + tri_t t = tri_parse_default("i01", 3); + + tri_t r = tri_unop(NOP, t); + assert(tri_eq(r, t)); + + r = tri_unop(NNN, t); + assert(tri_eq(r, tri_from(TRI_MIN))); + + r = tri_unop(OOO, t); + assert(tri_eq(r, tri_from(0))); + + r = tri_unop(PPP, t); + assert(tri_eq(r, tri_from(TRI_MAX))); + + r = tri_unop(PON, t); + assert(tri_eq(r, tri_parse_default("10i", 3))); +} diff --git a/core/tri.h b/core/tri.h new file mode 100644 index 0000000..e4336ec --- /dev/null +++ b/core/tri.h @@ -0,0 +1,711 @@ +#ifndef CORE_TRI_H +#define CORE_TRI_H + +#include +#include +#include +#include +#include +#include +#include +#include + +/* type that can contain the binary value of a tri */ +typedef uint64_t tri_t; + +#define TRI_WIDTH 27 + +/* (3^(27) - 1) / 2 */ +#define TRI_MAX 3812798742493LL +#define TRI_MIN -TRI_MAX + +/* 54 bits */ +#define TRI_BMASK 0x7fffffffffffff +/* alternating ...0101 */ +#define TRI_PMASK 0x15555555555555 +/* alternating ...1010 */ +#define TRI_NMASK 0x2aaaaaaaaaaaaa + +/** + * fairly trivial mapping, + * where operations are mapped as N/O/P, where + * N means that negative values are mapped, + * O means neutral and P means positive. + * + * So for example NOP means N is mapped to N, + * O is mapped to O, P is mapped to P. + */ +enum triop { + N = 1, + O = 2, + P = 3, +}; +typedef enum triop triop_t; + +/* syntactic sugar around passing arguments to TRIOP3 and TRIOP9 */ +#define NNN N, N, N +#define NNO N, N, O +#define NNP N, N, P +#define NON N, O, N +#define NOO N, O, O +#define NOP N, O, P +#define NPN N, P, N +#define NPO N, P, O +#define NPP N, P, P + +#define ONN O, N, N +#define ONO O, N, O +#define ONP O, N, P +#define OON O, O, N +#define OOO O, O, O +#define OOP O, O, P +#define OPN O, P, N +#define OPO O, P, O +#define OPP O, P, P + +#define PNN P, N, N +#define PNO P, N, O +#define PNP P, N, P +#define PON P, O, N +#define POO P, O, O +#define POP P, O, P +#define PPN P, P, N +#define PPO P, P, O +#define PPP P, P, P + +#define GET_TRIOP(t, x)\ + (((t) >> ((x) * 2)) & 0x3) + +#define _SET_TRIOP(t, x)\ + ((t) << ((x) * 2)) + +#define _TRIOP3(a, b, c, i) \ + (_SET_TRIOP((a), (i) + 0) | _SET_TRIOP((b), (i) + 1) | _SET_TRIOP((c), (i) + 2)) + +#define TRIOP3(a) \ + _TRIOP3(a, 0) + +#define _TRIOP9(a, b, c, d, e, f, g, h, i) \ + (_TRIOP3(a, b, c, 0) | _TRIOP3(d, e, f, 3) | _TRIOP3(g, h, i, 6)) + +#define TRIOP9(a, b, c) \ + _TRIOP9(a, b, c) + +static inline int tri_get_trit(tri_t t, size_t i) +{ + bool p = (t >> ((2 * i) + 0)) & 1; + bool n = (t >> ((2 * i) + 1)) & 1; + + /* assume normalized */ + if (!p && !n) + return 0; + + if (p) + return 1; + + if (n) + return -1; + + /* shouldn't be possible */ + return 0; +} + +static inline tri_t tri_set_trit(tri_t t, size_t i, int f) +{ + /* preclear area */ + t &= ~(0x3ULL << (i * 2)); + if (f == 0) + return t; + + if (f < 0) + return t | (0x2ULL << (i * 2)); + + return t | (0x1ULL << (i * 2)); +} + +/* keep n lowest trits */ +static inline tri_t tri_mask(tri_t t, size_t n) +{ + return t & ((1ULL << (n * 2)) - 1); +} + +/* discard n lowest trits */ +static inline tri_t tri_discard(tri_t t, size_t n) +{ + return t & ~((1ULL << (n * 2)) - 1); +} + +static inline tri_t tri_ns(tri_t t) +{ + tri_t n = ( t & TRI_NMASK) >> 1; + tri_t p = (~t & TRI_PMASK) >> 0; + + tri_t ns = (n & p); + ns |= ns << 1; + + return ns; +} + +static inline tri_t tri_ps(tri_t t) +{ + tri_t n = (~t & TRI_NMASK) >> 1; + tri_t p = ( t & TRI_PMASK) >> 0; + + tri_t ps = (n & p); + ps |= ps << 1; + + return ps; +} + +static inline tri_t tri_zs(tri_t t) +{ + tri_t n = (~t & TRI_NMASK) >> 1; + tri_t p = (~t & TRI_PMASK) >> 0; + + tri_t z = (n & p); + z |= z << 1; + + return z; +} + +static inline tri_t tri_us(tri_t t) +{ + tri_t n = ( t & TRI_NMASK) >> 1; + tri_t p = ( t & TRI_PMASK) >> 0; + + tri_t u = (n & p); + u |= u << 1; + + return u; +} + +static inline tri_t tri_normalize(tri_t t) +{ + /* convert binary ones in both positive and negative trits to zero */ + tri_t t0 = ((t & TRI_PMASK) << 1) & t; + t0 |= t0 << 1; + return (t & ~t0) & TRI_BMASK; +} + +static inline tri_t tri_bias(tri_t a) +{ + tri_t z = tri_zs(a); + tri_t p = tri_ps(a); + return (TRI_PMASK & z) | (TRI_NMASK & p); +} + +static inline tri_t tri_unbias(tri_t a) +{ + tri_t n = tri_ns(a); + tri_t z = tri_zs(a); + return (TRI_PMASK & n) | (TRI_NMASK & z); +} + +static inline tri_t tri_neg(tri_t t) +{ + tri_t p = t & TRI_PMASK; + tri_t n = t & TRI_NMASK; + return (p << 1) | (n >> 1); +} + +static inline tri_t tri_from(int64_t v) +{ + static const uint16_t tbl[] = { +#include "t9.inc" + }; + + bool neg = false; + if (v < 0) { + neg = true; + v = - v; + } + + tri_t s = 0; + for (size_t i = 0; i < 5; ++i) { + int64_t d = v / 729; + int64_t r = v - (d * 729); + + tri_t t = tbl[r]; + s |= (t & 0xfff) << (i * 12); + + v = d; + + tri_t c = t >> 12; + if (c == 1) v += 1; + else if (c == 2) v -= 1; + } + + if (neg) + s = tri_neg(s); + + return s & TRI_BMASK; +} + +static inline int64_t tri_to(tri_t t) +{ + /* apparently an algorithm that a superoptimizer found so I'm not even + * going to try to understand what's going on */ + tri_t acc = tri_bias(t); + + acc = acc - (((acc >> 2) & 0x3333333333333333) * ( 4 - 3)); + acc = acc - (((acc >> 4) & 0x0F0F0F0F0F0F0F0F) * ( 16 - 9)); + acc = acc - (((acc >> 8) & 0x00FF00FF00FF00FF) * ( 256 - 81)); + acc = acc - (((acc >> 16) & 0x0000FFFF0000FFFF) * ( 65536 - 6561)); + acc = acc - (((acc >> 32) & 0x00000000FFFFFFFF) * (4294967296 - 43046721)); + + return (int64_t)acc - TRI_MAX; +} + +static inline tri_t tri_parse(const char *s, size_t len, char n, char o, char p) +{ + int64_t r = 1; + int64_t sum = 0; + size_t l = len < TRI_WIDTH ? len : TRI_WIDTH; + for (size_t i = 0; i < l; r *= 3, ++i) { + char t = s[len - 1 - i]; + if (t == n) { sum -= r; continue; } + if (t == p) { sum += r; continue; } + if (t == o) continue; + + /* not pretty but good enough for now */ + fprintf(stderr, "invalid trinary digit: %c\n", t); + abort(); + } + + return tri_from(sum); +} + +static inline tri_t tri_parse_default(const char *s, size_t len) +{ + return tri_parse(s, len, 'i', '0', '1'); +} + +/* does not append trailing NULL */ +/* could be useful to add how many zeroes to print out? */ +static inline size_t tri_fmt(char *s, size_t len, tri_t t, char n, char o, char p) +{ + int64_t v = tri_to(t); + if (v == 0) { + s[0] = '0'; + return 1; + } + + /* naive conversion to trinary is pretty nifty as it automatically stops + * once we reach zero, but I still need to add padding and possibly base + * as well */ + size_t i = 0; + while (v) { + if (i >= len) + break; + + int d = v % 3; + + switch (d) { + case +2: + case -1: s[i] = n; v += 1; break; + + case -2: + case +1: s[i] = p; v -= 1; break; + + default: s[i] = o; + } + + v /= 3; + i++; + } + + /* reverse string */ + for (size_t j = 0; j < i / 2; ++j) { + size_t k = i - j - 1; + char tmp = s[j]; + s[j] = s[k]; + s[k] = tmp; + } + return i; +} + +static inline size_t tri_fmt_default(char *s, size_t len, tri_t t) +{ + return tri_fmt(s, len, t, 'i', '0', '1'); +} + +static inline tri_t tri_sl(tri_t t, size_t i) +{ + return t << (i * 2); +} + +static inline tri_t tri_sr(tri_t t, size_t i) +{ + return t >> (i * 2); +} + +/* bias happends to be used in several places */ +#define BIAS 0x5555555555555555ULL +static inline tri_t tri_bsum(tri_t a, tri_t b) +{ + /* directly lifted from libter27, + * http://homepage.cs.uiowa.edu/~dwjones/ternary/libtern.shtml + * added comments to help myself understand what's going on */ + + /* Really cool algorithm, first `a` is mapped to another number system, + * where 00 is invalid, and the trinary values look like + * 00 "0" => 01 + * 01 "1" => 10 + * 10 "2" => 11 + * + * This is so our hardware addition functions according to + * + * c+b | 00 | 01 | 10 + * ----+----+----+--- + * 01 | 01 | 10 | 11 + * 10 | 10 | 11 |+00 + * 11 | 11 |+00 |+01 + * + * + means carry. Note how similar the above table is to unbalanced + * trinary: + * + * a+b | 0 | 1 | 2 + * ----+---+---+-- + * 0 | 0 | 1 | 2 + * 1 | 1 | 2 |+0 + * 2 | 2 |+0 |+1 + * + * Ignoring carries for the moment, we can map 01 => 0, 10 => 1 and + * 11 => 2. To get back to our normal number system, we can subtract the + * bias again, except for where carries happen. However, notice that the + * number that is left behind IS the number we want! So we just need to + * detect when a carry has occured, and we don't have to fix up that + * location. + * + * Getting the carry occurences is done with b ^ c ^ d. + * b^c is the standard way to compute the sum of two bits and discarding + * the carry. Therefore, if (b^c) is different from d, we know that the + * previous stage must have sent us a carry! + */ + + /* add bias to make binary addition in hardware more closely + * match unbalanced trinary addition */ + tri_t c = a + BIAS; + + /* caclulate biased sum with errors */ + tri_t d = b + c; + + /* detect if a carry happened in the previous stage, if one is detected + * then that region shouldn't be subtracted in the final step */ + tri_t e = (~(b ^ c ^ d) & BIAS) >> 2; + + /* subtract to counter adding bias in first step and fix errors that + * show up in second stage */ + return (d - e) & TRI_BMASK; +} + +static inline tri_t tri_bneg(tri_t a) +{ + return 0x2aaaaaaaaaaaaaaaULL - a; +} + +#define TRI_B0 0x1540000000000000ULL +static inline tri_t tri_bsl(tri_t a, int i) +{ + return (a << (2 * i)) | (TRI_B0 >> (2 * (31 - i))); +} + +static inline tri_t tri_bsr(tri_t a, int i) +{ + return (a >> (2 * i)) | (TRI_B0 << (2 * (31 - i))); +} + +static inline tri_t tri_badd(tri_t a, tri_t b) +{ + /* do some biased number magic for partial sum */ + tri_t bsum = tri_bsum(a, b); + + /* subtract bias for full sum. note that bias + 1 is the same as -bias */ + tri_t sum = tri_bsum(bsum, BIAS + 1); + return sum; +} + +static inline tri_t tri_bsub(tri_t a, tri_t b) +{ + return tri_badd(a, tri_bneg(b)); +} + +static inline tri_t tri_add(tri_t a, tri_t b) +{ + /* convert to biased numbers */ + tri_t ab = tri_bias(a); + tri_t bb = tri_bias(b); + + /* internal helper */ + tri_t sum = tri_badd(ab, bb); + + /* convert back to balanced numbers */ + tri_t r = tri_unbias(sum); + return r; +} +#undef BIAS + +static inline tri_t tri_sub(tri_t a, tri_t b) +{ + return tri_add(a, tri_neg(b)); +} + +#define TRI_N13 0b101010 +#define TRI_N12 0b101000 +#define TRI_N11 0b101001 +#define TRI_N10 0b100010 +#define TRI_N9 0b100000 +#define TRI_N8 0b100001 +#define TRI_N7 0b100110 +#define TRI_N6 0b100100 +#define TRI_N5 0b100101 +#define TRI_N4 0b001010 +#define TRI_N3 0b001000 +#define TRI_N2 0b001001 +#define TRI_N1 0b000010 +#define TRI_0 0b000000 +#define TRI_P1 0b000001 +#define TRI_P2 0b000110 +#define TRI_P3 0b000100 +#define TRI_P4 0b000101 +#define TRI_P5 0b011010 +#define TRI_P6 0b011000 +#define TRI_P7 0b011001 +#define TRI_P8 0b010010 +#define TRI_P9 0b010000 +#define TRI_P10 0b010001 +#define TRI_P11 0b010110 +#define TRI_P12 0b010100 +#define TRI_P13 0b010101 + +static inline tri_t tri_mul(tri_t a, tri_t b) +{ + /* probably needs a little bit more testing */ + tri_t pa = tri_bias(a); + tri_t na = tri_bneg(a); + tri_t p = tri_bias(0); + + for (int i = 0; i < 9; ++i) { + tri_t m = b & 0x3f; + b >>= 6; + + switch (m) { + case TRI_N2: p = tri_badd(p, na); /* fallthru */ + case TRI_N1: p = tri_badd(p, na); + break; + + case TRI_N5: p = tri_badd(p, na); /* fallthru */ + case TRI_N4: p = tri_badd(p, na); /* fallthru */ + case TRI_N3: p = tri_badd(p, tri_bsl(na, 1)); + break; + + case TRI_N8: p = tri_badd(p, na); /* fallthru */ + case TRI_N7: p = tri_badd(p, na); /* fallthru */ + case TRI_N6: p = tri_badd(p, tri_bsl(na, 1)); + p = tri_badd(p, tri_bsl(na, 1)); + break; + + case TRI_N11: p = tri_badd(p, na); /* fallthru */ + case TRI_N10: p = tri_badd(p, na); /* fallthru */ + case TRI_N9: p = tri_badd(p, tri_bsl(na, 2)); + break; + + case TRI_N13: p = tri_badd(p, na); /* fallthru */ + case TRI_N12: p = tri_badd(p, tri_bsl(na, 2)); + p = tri_badd(p, tri_bsl(na, 1)); + break; + + case TRI_0: break; + case TRI_P2: p = tri_badd(p, pa); /* fallthru */ + case TRI_P1: p = tri_badd(p, pa); + break; + + case TRI_P5: p = tri_badd(p, pa); /* fallthru */ + case TRI_P4: p = tri_badd(p, pa); /* fallthru */ + case TRI_P3: p = tri_badd(p, tri_bsl(pa, 1)); + break; + + case TRI_P8: p = tri_badd(p, pa); /* fallthru */ + case TRI_P7: p = tri_badd(p, pa); /* fallthru */ + case TRI_P6: p = tri_badd(p, tri_bsl(pa, 1)); + p = tri_badd(p, tri_bsl(pa, 1)); + break; + + case TRI_P11: p = tri_badd(p, pa); /* fallthru */ + case TRI_P10: p = tri_badd(p, pa); /* fallthru */ + case TRI_P9: p = tri_badd(p, tri_bsl(pa, 2)); + break; + + case TRI_P13: p = tri_badd(p, pa); /* fallthru */ + case TRI_P12: p = tri_badd(p, tri_bsl(pa, 2)); + p = tri_badd(p, tri_bsl(pa, 1)); + break; + + default: printf("misshandled 0x%lx\n", m); + abort(); + } + } + + return tri_unbias(p); +} + +#if 0 +/* I'll deal with division later, turns out hardware and software division + * differs */ +static inline tri_t tri_div(tri_t a, tri_t b) +{ + /* ditto */ + trival_t ba = tri_to(a); + trival_t bb = tri_to(b); + return tri_from(ba / bb); +} + +static inline tri_t tri_rem(tri_t a, tri_t b) +{ + trival_t ba = tri_to(a); + trival_t bb = tri_to(b); + return tri_from(ba % bb); +} +#endif + +/* return sign of whole tri, -1 for negative, 0 for zero, 1 for positive */ +static inline int tri_sign(tri_t t) +{ + if (t == 0) + return 0; + + int lz = __builtin_clzll(t); + if (lz % 2 == 0) + return 1; + + return -1; +} + +static inline bool tri_eq(tri_t a, tri_t b) +{ + return a == b; +} + +static inline bool tri_lt(tri_t a, tri_t b) +{ + tri_t r = tri_sub(a, b); + int s = tri_sign(r); + if (s >= 0) + return false; + + return true; +} + +static inline bool tri_le(tri_t a, tri_t b) +{ + return tri_eq(a, b) || tri_lt(a, b); +} + +static inline bool tri_gt(tri_t a, tri_t b) +{ + return tri_le(b, a); +} + +static inline bool tri_ge(tri_t a, tri_t b) +{ + return tri_lt(b, a); +} + +#define tri_illegal_op()\ + do { fprintf(stderr, "illegal op, aborting\n"); abort(); } while (0) + +#define tri_unop(o, a)\ + tri_unop_do(_TRIOP3(o, 0), a) + +static inline tri_t tri_unop_do(triop_t op, tri_t a) +{ + + tri_t n = 0; + tri_t p = 0; + + tri_t an = tri_ns(a); + tri_t ap = tri_ps(a); + tri_t az = tri_zs(a); + + /* handle mapping n */ + switch (GET_TRIOP(op, 0)) { + case N: n |= an; break; + case P: p |= an; break; + case O: /* noop */ break; + default: tri_illegal_op(); + } + + /* map o */ + switch (GET_TRIOP(op, 1)) { + case N: n |= az; break; + case P: p |= az; break; + case O: /* noop */ break; + default: tri_illegal_op(); + } + + /* map p */ + switch (GET_TRIOP(op, 2)) { + case N: n |= ap; break; + case P: p |= ap; break; + case O: /* noop */ break; + default: tri_illegal_op(); + } + + return (TRI_PMASK & p) | (TRI_NMASK & n); +} + +#define tri_diop(o0, o1, o2, a, b)\ + tri_diop_do(_TRIOP9(o0, o1, o2), a, b) + +static inline tri_t tri_diop_do(triop_t op, tri_t a, tri_t b) +{ + tri_t n = 0; + tri_t p = 0; + + tri_t an = tri_ns(a); + tri_t ap = tri_ps(a); + tri_t az = tri_zs(a); + + tri_t bn = tri_ns(b); + tri_t bp = tri_ps(b); + tri_t bz = tri_zs(b); + + for (int i = 0; i < 9; i += 3) { + /* select map */ + tri_t r = 0; + switch (i) { + case 0: r = an; break; + case 3: r = az; break; + case 6: r = ap; break; + } + + /* map n */ + switch (GET_TRIOP(op, i + 0)) { + case N: n |= r & bn; break; + case P: p |= r & bn; break; + case O: /* noop */ break; + default: tri_illegal_op(); + } + + /* map o */ + switch (GET_TRIOP(op, i + 1)) { + case N: n |= r & bz; break; + case P: p |= r & bz; break; + case O: /* noop */ break; + default: tri_illegal_op(); + } + + /* map p */ + switch (GET_TRIOP(op, i + 2)) { + case N: n |= r & bp; break; + case P: p |= r & bp; break; + case O: /* noop */ break; + default: tri_illegal_op(); + } + } + + return (TRI_PMASK & p) | (TRI_NMASK & n); +} + +#undef tri_illegal_op +#endif -- cgit v1.3