rcx

commit 4095b9d1ea56b41cf7a2ee544b56d8084ae14298
parent c7f3417b06d4b75ba61f7f1d8e37c7d519c405fa
Author: Robert Russell <robertrussell.72001@gmail.com>
Date:   Mon, 29 May 2023 13:32:50 -0700

Add rightmost zero byte search functions

Diffstat:
M
inc/all.h
 | 
1
+
M
inc/bits.h
 | 
29
+++++++++++++++++++++++++++++

2 files changed, 30 insertions(+), 0 deletions(-)
diff --git a/inc/all.h b/inc/all.h
@@ -7,6 +7,7 @@
 #include "error.h"
 #include "log.h"
 #include "opt.h"
+#include "rand.h"
 #include "rcx.h"
 #include "str.h"
 #include "string.h"
diff --git a/inc/bits.h b/inc/bits.h
@@ -160,6 +160,35 @@ r_ctz64(u64 n) {
 }
 
 
+/* ----- Rightmost zero byte searching ----- */
+
+/* See Warren, "Hacker's Delight", 2 ed., sec. 6.1. The basic idea is to map
+ * the rightmost 0x00 byte to 0x80 and all bytes right of the rightmost 0x00 to
+ * 0x00, and then use ctz. When the argument n has no zero byte, r8search
+ * returns sizeof n. By first XORing with a suitable value, these functions can
+ * be used to find arbitrary bytes. Also, by replacing the masks within the
+ * definition, this method adapts to searching for arbitrary length sequences
+ * of 0 bits aligned in a particular way. */
+
+static inline int
+r_r8search16(u16 n) {
+	n = (n - U16_C(0x0101)) & ~n & U16_C(0x8080);
+	return r_ctz16(n) / 8u;
+}
+
+static inline int
+r_r8search32(u32 n) {
+	n = (n - U32_C(0x01010101)) & ~n & U32_C(0x80808080);
+	return r_ctz32(n) / 8u;
+}
+
+static inline int
+r_r8search64(u64 n) {
+	n = (n - U64_C(0x0101010101010101)) & ~n & U64_C(0x8080808080808080);
+	return r_ctz64(n) / 8u;
+}
+
+
 /* ----- Full width multiply ----- */
 
 static inline void