hare

commit fba7b1d030eeedf1b75a26a2f838ace246287142
parent 7d4d5d5fea3dc6dbdca119d3d0e341fce8fe3268
Author: Pierre Curto <pierre.curto@gmail.com>
Date:   Tue,  9 Aug 2022 13:26:15 +0200

math: add trailing_zeros_u*

Match the existing leading_zeros_u* functions.

Signed-off-by: Pierre Curto <pierre.curto@gmail.com>

Diffstat:
M
math/uints.ha
 | 
111
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 111 insertions(+), 0 deletions(-)
diff --git a/math/uints.ha b/math/uints.ha
@@ -61,6 +61,48 @@ const LEN8TAB: [256]u8 = [
 	0x08, 0x08, 0x08, 0x08,
 ];
 
+const NTZ8TAB: [256]u8 = [
+	0x08, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x07, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x06, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x05, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00,
+	0x04, 0x00, 0x01, 0x00, 0x02, 0x00, 0x01, 0x00, 0x03, 0x00, 0x01, 0x00,
+	0x02, 0x00, 0x01, 0x00,
+];
+
+// See http://supertech.csail.mit.edu/papers/debruijn.pdf
+def DEBRUIJN32: u32 = 0x077CB531;
+
+const DEBRUIJN32TAB: [32]u8 = [
+	0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+	31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
+];
+
+def DEBRUIJN64: u64 = 0x03f79d71b4ca8b09;
+
+const DEBRUIJN64TAB: [64]u8 = [
+	0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
+	62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
+	63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
+	54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
+];
+
 // The size of an unsigned int: 32 or 64
 def UINT_SIZE: u8 = (size(uint): u8) * 8;
 
@@ -167,6 +209,75 @@ export fn leading_zeros_u64(x: u64) u8 = 64 - bit_size_u64(x);
 	assert(leading_zeros_u64(1) == 64 - 1);
 };
 
+// Returns the number of trailing zero bits in x
+// The result is UINT_SIZE for x == 0.
+export fn trailing_zeros_u(x: uint) u8 = {
+	if (UINT_SIZE == 32) {
+		return trailing_zeros_u32(x: u32);
+	};
+	return trailing_zeros_u64(x: u64);
+};
+
+// Returns the number of trailing zero bits in x
+// The result is 8 for x == 0.
+export fn trailing_zeros_u8(x: u8) u8 = NTZ8TAB[x];
+
+// Returns the number of trailing zero bits in x
+// The result is 16 for x == 0.
+export fn trailing_zeros_u16(x: u16) u8 = {
+	if (x == 0) {
+		return 16;
+	};
+	return DEBRUIJN32TAB[(x & -x): u32 * DEBRUIJN32 >> (32 - 5)];
+};
+
+// Returns the number of trailing zero bits in x
+// The result is 32 for x == 0.
+export fn trailing_zeros_u32(x: u32) u8 = {
+	if (x == 0) {
+		return 32;
+	};
+	return DEBRUIJN32TAB[(x & -x) * DEBRUIJN32 >> (32 - 5)];
+};
+
+// Returns the number of trailing zero bits in x
+// The result is 64 for x == 0.
+export fn trailing_zeros_u64(x: u64) u8 = {
+	if (x == 0) {
+		return 64;
+	};
+	return DEBRUIJN64TAB[(x & -x) * DEBRUIJN64 >> (64 - 6)];
+};
+
+@test fn trailing_zeros_u() void = {
+	assert(trailing_zeros_u8(0) == 8);
+	for (let x: u8 = 1 << 7, i = 7u8; x > 0; x >>= 1) {
+		assert(trailing_zeros_u8(x) == i);
+		i -= 1;
+	};
+
+	assert(trailing_zeros_u16(0) == 16);
+	for (let x: u16 = 1 << 15, i = 15u8; x > 0; x >>= 1) {
+		assert(trailing_zeros_u16(x) == i);
+		i -= 1;
+	};
+
+	assert(trailing_zeros_u32(0) == 32);
+	for (let x: u32 = 1 << 31, i = 31u8; x > 0; x >>= 1) {
+		assert(trailing_zeros_u32(x) == i);
+		i -= 1;
+	};
+
+	assert(trailing_zeros_u64(0) == 64);
+	for (let x: u64 = 1 << 63, i = 63u8; x > 0; x >>= 1) {
+		assert(trailing_zeros_u64(x) == i);
+		i -= 1;
+	};
+
+	assert(trailing_zeros_u(0) == UINT_SIZE);
+	assert(trailing_zeros_u(1) == 0);
+};
+
 // Returns the sum with carry of x, y and carry: sum = x + y + carry.
 // The carry input must be 0 or 1, otherwise the behavior is undefined.
 // The carry_out output is guaranteed to be 0 or 1.