rcx

commit 781d20dc7406d20bc84da01fec1a723b7e308e5a
parent c0ac5a44102417bc091976e713435e92550034c3
Author: Robert Russell <robertrussell.72001@gmail.com>
Date:   Wed,  1 Feb 2023 17:28:54 -0800

Add bit manipulation library

Just popcnt for now. Extend with more functions as needed.

Diffstat:
M
Makefile
 | 
4
+++-
A
inc/rcx/bits.h
 | 
8
++++++++
A
src/bits.c
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
M
src/unix.c
 | 
1
+

4 files changed, 55 insertions(+), 1 deletion(-)
diff --git a/Makefile b/Makefile
@@ -5,6 +5,7 @@ include config.mk
 SRC =\
 	src/alloc.c\
 	src/bench.c\
+	src/bits.c\
 	src/log.c\
 	src/str.c\
 	src/unicode.c\
@@ -20,11 +21,12 @@ librcx.a: $(SRC:.c=.o)
 
 src/alloc.o: src/alloc.c inc/rcx/alloc.h inc/rcx/def.h inc/rcx/log.h inc/rcx/rcx.h inc/rcx/internal/util.h config.mk
 src/bench.o: src/bench.c inc/rcx/bench.h inc/rcx/def.h inc/rcx/log.h inc/rcx/rcx.h config.mk
+src/bits.o: src/bits.c inc/rcx/bits.h inc/rcx/def.h inc/rcx/rcx.h config.mk
 src/log.o: src/log.c inc/rcx/def.h inc/rcx/log.h inc/rcx/rcx.h config.mk
 src/opt.o: src/opt.c inc/rcx/def.h inc/rcx/opt.h inc/rcx/rcx.h config.mk
 src/str.o: src/str.c inc/rcx/alloc.h inc/rcx/def.h inc/rcx/log.h inc/rcx/rcx.h inc/rcx/str.h config.mk
 src/unicode.o: src/unicode.c inc/rcx/def.h inc/rcx/rcx.h gen/ucattab.inc config.mk
-src/unix.o: src/unix.c inc/rcx/def.h inc/rcx/rcx.h config.mk
+src/unix.o: src/unix.c inc/rcx/def.h inc/rcx/rcx.h inc/rcx/unix.h config.mk
 src/utf8.o: src/utf8.c inc/rcx/def.h inc/rcx/rcx.h inc/rcx/utf8.h config.mk
 
 gen/ucattab.inc: gen tool/ucattab gen/UnicodeData.txt
diff --git a/inc/rcx/bits.h b/inc/rcx/bits.h
@@ -0,0 +1,8 @@
+#pragma once
+
+#include "rcx/def.h"
+
+int r_popcnt_8(u8 n);
+int r_popcnt_16(u16 n);
+int r_popcnt_32(u32 n);
+int r_popcnt_64(u64 n);
diff --git a/src/bits.c b/src/bits.c
@@ -0,0 +1,43 @@
+#include "rcx/bits.h"
+#include "rcx/rcx.h"
+
+/* popcnt functions are implemented with a divide and conquer strategy.
+ * See Henry Warren, Hacker's Delight, 2 ed., sec. 5.1. */
+
+int
+r_popcnt_8(u8 n) {
+	n = (n & U8_C(0x55)) + ((n>>1) & U8_C(0x55));
+	n = (n & U8_C(0x33)) + ((n>>2) & U8_C(0x33));
+	n = (n & U8_C(0x0f)) + ((n>>4) & U8_C(0x0f));
+	return n;
+}
+
+int
+r_popcnt_16(u16 n) {
+	n = (n & U16_C(0x5555)) + ((n>>1) & U16_C(0x5555));
+	n = (n & U16_C(0x3333)) + ((n>>2) & U16_C(0x3333));
+	n = (n & U16_C(0x0f0f)) + ((n>>4) & U16_C(0x0f0f));
+	n = (n & U16_C(0x00ff)) + ((n>>8) & U16_C(0x00ff));
+	return n;
+}
+
+int
+r_popcnt_32(u32 n) {
+	n = (n & U32_C(0x55555555)) + ((n>>1)  & U32_C(0x55555555));
+	n = (n & U32_C(0x33333333)) + ((n>>2)  & U32_C(0x33333333));
+	n = (n & U32_C(0x0f0f0f0f)) + ((n>>4)  & U32_C(0x0f0f0f0f));
+	n = (n & U32_C(0x00ff00ff)) + ((n>>8)  & U32_C(0x00ff00ff));
+	n = (n & U32_C(0x0000ffff)) + ((n>>16) & U32_C(0x0000ffff));
+	return n;
+}
+
+int
+r_popcnt_64(u64 n) {
+	n = (n & U64_C(0x5555555555555555)) + ((n>>1)  & U64_C(0x5555555555555555));
+	n = (n & U64_C(0x3333333333333333)) + ((n>>2)  & U64_C(0x3333333333333333));
+	n = (n & U64_C(0x0f0f0f0f0f0f0f0f)) + ((n>>4)  & U64_C(0x0f0f0f0f0f0f0f0f));
+	n = (n & U64_C(0x00ff00ff00ff00ff)) + ((n>>8)  & U64_C(0x00ff00ff00ff00ff));
+	n = (n & U64_C(0x0000ffff0000ffff)) + ((n>>16) & U64_C(0x0000ffff0000ffff));
+	n = (n & U64_C(0x00000000ffffffff)) + ((n>>32) & U64_C(0x00000000ffffffff));
+	return n;
+}
diff --git a/src/unix.c b/src/unix.c
@@ -5,6 +5,7 @@
 #include <unistd.h>
 
 #include "rcx/rcx.h"
+#include "rcx/unix.h"
 
 typedef isize (*IoOp)(int, void *, usize);