From dd4af9ab4aa5e39ff3db44466b07b0c119b8aa21 Mon Sep 17 00:00:00 2001
From: Pavel Charvat <pchar@ucw.cz>
Date: Sat, 17 Nov 2012 18:40:13 +0100
Subject: [PATCH] Bitarray: Counting of bits and other fixes

  o  Added bit_array_count_bits().
  o  Padding after the last significant bit is guaranteed to be 0.
  o  BIT_ARRAY_FISH_BITS_... is not destructive any longer.
---
 ucw/Makefile    |  4 ++--
 ucw/bit-count.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 ucw/bitarray.h  | 25 ++++++++++++++++---------
 ucw/bitops.t    | 10 ++++++++++
 4 files changed, 74 insertions(+), 11 deletions(-)
 create mode 100644 ucw/bit-count.c

diff --git a/ucw/Makefile b/ucw/Makefile
index 35a1cc2b..d4a055ce 100644
--- a/ucw/Makefile
+++ b/ucw/Makefile
@@ -21,7 +21,7 @@ LIBUCW_MODS= \
 	wildmatch regex \
 	prime primetable random \
 	time-stamp time-timer time-conf \
-	bit-ffs bit-fls \
+	bit-ffs bit-fls bit-count \
 	url \
 	mainloop main-block main-rec \
 	proctitle exitstatus runcmd \
@@ -124,7 +124,7 @@ $(o)/ucw/unicode.test: $(o)/ucw/unicode-t
 $(o)/ucw/hash-test.test: $(o)/ucw/hash-test
 $(o)/ucw/mempool.test: $(o)/ucw/mempool-t $(o)/ucw/mempool-fmt-t $(o)/ucw/mempool-str-t
 $(o)/ucw/stkstring.test: $(o)/ucw/stkstring-t
-$(o)/ucw/bitops.test: $(o)/ucw/bit-ffs-t $(o)/ucw/bit-fls-t
+$(o)/ucw/bitops.test: $(o)/ucw/bit-ffs-t $(o)/ucw/bit-fls-t $(o)/ucw/bit-count-t
 $(o)/ucw/slists.test: $(o)/ucw/slists-t
 $(o)/ucw/kmp-test.test: $(o)/ucw/kmp-test
 $(o)/ucw/bbuf.test: $(o)/ucw/bbuf-t
diff --git a/ucw/bit-count.c b/ucw/bit-count.c
new file mode 100644
index 00000000..a84a6b7c
--- /dev/null
+++ b/ucw/bit-count.c
@@ -0,0 +1,46 @@
+/*
+ *	UCW Library -- Counting bits in bitarray
+ *
+ *	(c) 2012 Pavel Charvat <pchar@ucw.cz>
+ *
+ *	This software may be freely distributed and used according to the terms
+ *	of the GNU Lesser General Public License.
+ */
+
+#include <ucw/lib.h>
+#include <ucw/bitops.h>
+#include <ucw/bitarray.h>
+
+uns bit_array_count_bits(bitarray_t a, uns n)
+{
+  uns m = 0;
+  n = BIT_ARRAY_WORDS(n);
+  while (n--)
+    m += bit_count(*a++);
+  return m;
+}
+
+#ifdef TEST
+
+#include <stdio.h>
+#include <alloca.h>
+
+int main(void)
+{
+  char buf[1024];
+  bitarray_t a = alloca(BIT_ARRAY_BYTES(sizeof(buf)));
+  while (1)
+    {
+      if (!fgets(buf, sizeof(buf), stdin))
+	return 0;
+      uns n;
+      for (n = 0; buf[n] == '0' || buf[n] == '1'; n++);
+      bit_array_zero(a, n);
+      for (uns i = 0; i < n; i++)
+	if (buf[i] == '1')
+	  bit_array_set(a, i);
+      printf("%u\n", bit_array_count_bits(a, n));
+    }
+}
+
+#endif
diff --git a/ucw/bitarray.h b/ucw/bitarray.h
index 72480415..e2994c64 100644
--- a/ucw/bitarray.h
+++ b/ucw/bitarray.h
@@ -2,6 +2,7 @@
  *	UCW Library -- Bit Array Operations
  *
  *	(c) 2003--2006 Martin Mares <mj@ucw.cz>
+ *	(c) 2012 Pavel Charvat <pchar@ucw.cz>
  *
  *	This software may be freely distributed and used according to the terms
  *	of the GNU Lesser General Public License.
@@ -12,7 +13,8 @@
 
 #include <string.h>
 
-typedef u32 *bitarray_t;
+typedef u32 *bitarray_t; // Must be initialized by bit_array_xmalloc(), bit_array_zero() or bit_array_set_all()
+
 #define BIT_ARRAY_WORDS(n) (((n)+31)/32)
 #define BIT_ARRAY_BYTES(n) (4*BIT_ARRAY_WORDS(n))
 #define BIT_ARRAY(name,size) u32 name[BIT_ARRAY_WORDS(size)]
@@ -38,7 +40,11 @@ bit_array_zero(bitarray_t a, uns n)
 static inline void
 bit_array_set_all(bitarray_t a, uns n)
 {
-  memset(a, 255, BIT_ARRAY_BYTES(n));
+  uns w = n / 32;
+  memset(a, 255, w * 4);
+  uns m = n & 31;
+  if (m)
+    a[w] = (1U << m) - 1;
 }
 
 static inline void
@@ -90,18 +96,19 @@ bit_array_test_and_clear(bitarray_t a, uns i)
   return t;
 }
 
-/* Iterate over all set bits, possibly destructively */
+uns bit_array_count_bits(bitarray_t a, uns n);
+
+/* Iterate over all set bits */
 #define BIT_ARRAY_FISH_BITS_BEGIN(var,ary,size)					\
   for (uns var##_hi=0; var##_hi < BIT_ARRAY_WORDS(size); var##_hi++)		\
-    for (uns var##_lo=0; ary[var##_hi]; var##_lo++)				\
-      if (ary[var##_hi] & (1 << var##_lo))					\
-        {									\
-	  uns var = 32*var##_hi + var##_lo;					\
-	  ary[var##_hi] &= ~(1 << var##_lo);					\
+    {										\
+      u32 var##_cur = ary[var##_hi];						\
+      for (uns var = 32 * var##_hi; var##_cur; var++, var##_cur >>= 1)		\
+        if (var##_cur & 1)							\
 	  do
 
 #define BIT_ARRAY_FISH_BITS_END							\
 	  while (0);								\
-	}
+    }
 
 #endif
diff --git a/ucw/bitops.t b/ucw/bitops.t
index 42240665..69fb4f0d 100644
--- a/ucw/bitops.t
+++ b/ucw/bitops.t
@@ -51,3 +51,13 @@ Out:	0
 	17
 	9
 	27
+
+Run:	../obj/ucw/bit-count-t
+In:	11111111111111111
+	000000000000
+	0001010000
+	1001010101010000010111100011100001110010101010000111000011100000001001010101000101010
+Out:	17
+	0
+	2
+	35
-- 
2.39.2