Changeset ed4cf588b31c5ebb50b4d502802d243fec2cb338

Timestamp:

04/30/08 12:45:38 (8 months ago)

Author:

krayouva <krayouva@…>

Parents:

3516e7ae3f4df445e780bee77b2a9a7f6ce7ddb8

Children:

1c4d613e749d9e677b5d4a13214e93bfee485937

git-committer:

krayouva <krayouva@gmail.com> / 2008-04-29T22:45:38Z-0400

Message:

* Optimized bitvector

- Wrapped bitvector.h descriptions to fit 80 char width
- Added malloc/inline/const/pure attributes where possible to improve

compiler optimizations

- Inlined most important functions [at least, the ones that are benched]
- Refactored bv_set/unset by having a set_value they call to
- Implemented optimized bicount routines that use gcc builtins where

possible

- Improved bv_recount to count by word

Location:

c

Files:

• include/bitvector.h (modified) (8 diffs)
• include/global.h (modified) (2 diffs)
• src/bitvector.c (modified) (11 diffs)

c/include/bitvector.h

@@ -21 +21 @@
     int capa;
 
-    /** count is the running count of bits set. This is kept up to date by
-     *frt_bv_set and frt_bv_unset. You can reset this value by calling frt_bv_recount */
+    /** count is the running count of bits set. This is kept up to
+     * date by frt_bv_set and frt_bv_unset. You can reset this value
+     * by calling frt_bv_recount */
     int count;
 
@@ -33 +34 @@
 
 /**
- * Create a new FrtBitVector with a capacity of +FRT_BV_INIT_CAPA+. Note that the
- * FrtBitVector is growable and will adjust it's capacity when you use frt_bv_set.
+ * Create a new FrtBitVector with a capacity of
+ * +FRT_BV_INIT_CAPA+. Note that the FrtBitVector is growable and will
+ * adjust it's capacity when you use frt_bv_set.
  *
  * @return FrtBitVector with a capacity of +FRT_BV_INIT_CAPA+.
  */
-extern FrtBitVector *frt_bv_new();
-
-/**
- * Create a new FrtBitVector with a capacity of +capa+. Note that the FrtBitVector
- * is growable and will adjust it's capacity when you use frt_bv_set.
+extern FRT_ATTR_MALLOC
+FrtBitVector *frt_bv_new();
+
+/**
+ * Create a new FrtBitVector with a capacity of +capa+. Note that the
+ * FrtBitVector is growable and will adjust it's capacity when you use
+ * frt_bv_set.
  *
  * @param capa the initial capacity of the FrtBitVector
  * @return FrtBitVector with a capacity of +capa+.
  */
-extern FrtBitVector *frt_bv_new_capa(int capa);
-
-/**
- * Destroy a FrtBitVector, freeing all memory allocated to that FrtBitVector
+extern FRT_ATTR_MALLOC
+FrtBitVector *frt_bv_new_capa(int capa);
+
+/**
+ * Destroy a FrtBitVector, freeing all memory allocated to that
+ * FrtBitVector
  *
  * @param bv FrtBitVector to destroy
@@ -57 +63 @@
 
 /**
- * Set the bit at position +index+. If +index+ is outside of the range of the
- * FrtBitVector, that is >= FrtBitVector.size, FrtBitVector.size will be set to +index+
- * + 1. If it is greater than the capacity of the FrtBitVector, the capacity will
- * be expanded to accomodate.
+ * Set the bit at position +index+ with +value+. If +index+ is outside
+ * of the range of the FrtBitVector, that is >= FrtBitVector.size,
+ * FrtBitVector.size will be set to +index+ + 1. If it is greater than
+ * the capacity of the FrtBitVector, the capacity will be expanded to
+ * accomodate.
  *
  * @param bv the FrtBitVector to set the bit in
  * @param index the index of the bit to set
- */
-extern void frt_bv_set(FrtBitVector *bv, int index);
+ * @param value the boolean value
+ */
+
+/*
+ * FIXME: if the top set bit is unset, size is not adjusted. This will not
+ * cause any bugs in this code but could cause problems if users are relying
+ * on the fact that size is accurate.
+ */
+extern FRT_ATTR_ALWAYS_INLINE
+void frt_bv_set_value(FrtBitVector *bv, int bit, bool value)
+{
+    frt_u32 *word_p;
+    int word = bit >> 5;
+    frt_u32 bitmask = 1 << (bit & 31);
+
+    /* Check to see if we need to grow the BitVector */
+    if (unlikely(bit >= bv->size)) {
+        bv->size = bit + 1; /* size is max range of bits set */
+        if (word >= bv->capa) {
+            int capa = bv->capa << 1;
+            while (capa <= word) {
+                capa <<= 1;
+            }
+            FRT_REALLOC_N(bv->bits, frt_u32, capa);
+            memset(bv->bits + bv->capa, (bv->extends_as_ones ? 0xFF : 0),
+                   sizeof(frt_u32) * (capa - bv->capa));
+            bv->capa = capa;
+        }
+    }
+
+    /* Set the required bit */
+    word_p = &(bv->bits[word]);
+    if ((!!(bitmask & *word_p)) != value) {
+        if (value) {
+            bv->count++;
+            *word_p |= bitmask;
+        }
+        else {
+            bv->count--;
+            *word_p &= ~bitmask;
+        }
+    }
+}
+
+/**
+ * Set the bit at position +index+. If +index+ is outside of the range
+ * of the FrtBitVector, that is >= FrtBitVector.size,
+ * FrtBitVector.size will be set to +index+ + 1. If it is greater than
+ * the capacity of the FrtBitVector, the capacity will be expanded to
+ * accomodate.
+ *
+ * @param bv the FrtBitVector to set the bit in
+ * @param index the index of the bit to set
+ */
+extern FRT_ATTR_ALWAYS_INLINE
+void frt_bv_set(FrtBitVector *bv, int bit)
+{
+    frt_bv_set_value(bv, bit, 1);
+}
 
 /**
  * Unsafely set the bit at position +index+. If you choose to use this
- * function you must create the FrtBitVector with a large enough capacity to
- * accomodate all of the frt_bv_set_fast operations. You must also set bits in
- * order and only one time per bit. Otherwise, use the safe frt_bv_set function.
+ * function you must create the FrtBitVector with a large enough
+ * capacity to accomodate all of the frt_bv_set_fast operations. You
+ * must also set bits in order and only one time per bit. Otherwise,
+ * use the safe frt_bv_set function.
  *
  * So this is ok;
@@ -93 +158 @@
  * @param index the index of the bit to set
  */
-extern FRT_INLINE void frt_bv_set_fast(FrtBitVector *bv, int bit);
-
-/**
- * Return 1 if the bit at +index+ was set or 0 otherwise. If +index+ is out of
- * range, that is greater then the BitVectors capacity, it will also return 0.
+extern FRT_ATTR_ALWAYS_INLINE
+void frt_bv_set_fast(FrtBitVector *bv, int bit)
+{
+    bv->count++;
+    bv->size = bit + 1;
+    bv->bits[bit >> 5] |= (1 << (bit & 31));
+}
+
+/**
+ * Return 1 if the bit at +index+ was set or 0 otherwise. If +index+
+ * is out of range, that is greater then the BitVectors capacity, it
+ * will also return 0.
  *
  * @param bv the FrtBitVector to check in
@@ -103 +175 @@
  * @return 1 if the bit was set, 0 otherwise
  */
-extern int frt_bv_get(FrtBitVector *bv, int index);
-
-/**
- * Unset the bit at position +index+. If the +index+ was out of range, that is
- * greater than the BitVectors capacity then do nothing. (frt_bv_get will return 0
- * in this case anyway).
+extern FRT_ATTR_ALWAYS_INLINE
+int frt_bv_get(FrtBitVector *bv, int bit)
+{
+    /* out of range so return 0 because it can't have been set */
+    if (unlikely(bit >= bv->size)) {
+        return bv->extends_as_ones;
+    }
+    return (bv->bits[bit >> 5] >> (bit & 31)) & 0x01;
+}
+
+/**
+ * Unset the bit at position +index+. If the +index+ was out of range,
+ * that is greater than the BitVectors capacity then do
+ * nothing. (frt_bv_get will return 0 in this case anyway).
  *
  * @param bv the FrtBitVector to unset the bit in
  * @param index the index of the bit to unset
  */
-extern void frt_bv_unset(FrtBitVector *bv, int bit);
+extern FRT_ATTR_ALWAYS_INLINE
+void frt_bv_unset(FrtBitVector *bv, int bit)
+{
+    frt_bv_set_value(bv, bit, 0);
+}
 
 /**
@@ -123 +207 @@
 
 /**
- * Resets the set bit count by running through the whole FrtBitVector and
- * counting all set bits. A running count of the bits is kept by frt_bv_set,
- *frt_bv_get and frt_bv_set_fast so this function is only necessary if the count could
- * have been corrupted somehow or if the FrtBitVector has been constructed in a
- * different way (for example being read from the file_system).
+ * Resets the set bit count by running through the whole FrtBitVector
+ * and counting all set bits. A running count of the bits is kept by
+ * frt_bv_set, *frt_bv_get and frt_bv_set_fast so this function is
+ * only necessary if the count could have been corrupted somehow or if
+ * the FrtBitVector has been constructed in a different way (for
+ * example being read from the file_system).
  *
  * @param bv the FrtBitVector to count the bits in
@@ -136 +221 @@
 
 /**
- * Reset the FrtBitVector for scanning. This function should be called before
- * using frt_bv_scan_next to scan through all set bits in the FrtBitVector. This is
- * not necessary when using frt_bv_scan_next_from.
+ * Reset the FrtBitVector for scanning. This function should be called
+ * before using frt_bv_scan_next to scan through all set bits in the
+ * FrtBitVector. This is not necessary when using
+ * frt_bv_scan_next_from.
  *
  * @param bv the FrtBitVector to reset for scanning
@@ -145 +231 @@
 
 /**
- * Scan the FrtBitVector for the next set bit. Before using this function you
- * should reset the FrtBitVector for scanning using +frt_bv_scan_reset+. You can the
- * repeated call frt_bv_scan_next to get each set bit until it finally returns
- * -1.
+ * Scan the FrtBitVector for the next set bit after +from+. If no more
+ * bits are set then return -1, otherwise return the index of teh next
+ * set bit.
+ *
+ * @param bv the FrtBitVector to scan
+ * @return the next set bit's index or -1 if no more bits are set
+ */
+extern FRT_ATTR_ALWAYS_INLINE
+int frt_bv_scan_next_from(FrtBitVector *bv, const int bit)
+{
+    frt_u32 pos  = bit >> 5;
+    frt_u32 word = bv->bits[pos];
+
+    if (bit >= bv->size)
+        return -1;
+
+    /* Keep only the bits above this position */
+    word &= ~0 << (bit & 31);
+    if (word)
+        goto done;
+
+    for (pos++; pos < (frt_u32)bv->size; ++pos)
+    {
+        if ( (word = bv->bits[pos]) )
+            goto done;
+    }
+    return -1;
+ done:
+    return bv->curr_bit = (pos << 5) + frt_count_trailing_zeros(word);
+}
+
+/**
+ * Scan the FrtBitVector for the next set bit. Before using this
+ * function you should reset the FrtBitVector for scanning using
+ * +frt_bv_scan_reset+. You can the repeatedly call frt_bv_scan_next
+ * to get each set bit until it finally returns -1.
  *
  * @param bv the FrtBitVector to scan
  * @return the next set bits index or -1 if no more bits are set
  */
-extern int frt_bv_scan_next(FrtBitVector *bv);
-
-/**
- * Scan the FrtBitVector for the next set bit after +from+. If no more bits are
- * set then return -1, otherwise return the index of teh next set bit.
+extern FRT_ATTR_ALWAYS_INLINE
+int frt_bv_scan_next(FrtBitVector *bv)
+{
+    return frt_bv_scan_next_from(bv, bv->curr_bit + 1);
+}
+
+/**
+ * Scan the FrtBitVector for the next unset bit after +from+. If no
+ * more bits are unset then return -1, otherwise return the index of
+ * teh next unset bit.
  *
  * @param bv the FrtBitVector to scan
- * @return the next set bit's index or -1 if no more bits are set
- */
-
-extern int frt_bv_scan_next_from(FrtBitVector *bv, register const int from);
-/**
- * Scan the FrtBitVector for the next unset bit. Before using this function you
- * should reset the FrtBitVector for scanning using +frt_bv_scan_reset+. You can the
- * repeated call frt_bv_scan_next to get each unset bit until it finally returns
- * -1.
+ * @return the next unset bit's index or -1 if no more bits are unset
+ */
+extern FRT_ATTR_ALWAYS_INLINE
+int frt_bv_scan_next_unset_from(FrtBitVector *bv, const int bit)
+{
+    frt_u32 pos  = bit >> 5;
+    frt_u32 word = bv->bits[pos];
+
+    if (bit >= bv->size)
+        return -1;
+
+    /* Set all of the bits below this position */
+    word |= (1 << (bit & 31)) - 1;
+    if (~word)
+        goto done;
+
+    for (pos++; pos < (frt_u32)bv->size; ++pos)
+    {
+        if ( ~(word = bv->bits[pos]) )
+            goto done;
+    }
+    return -1;
+ done:
+    return bv->curr_bit = (pos << 5) + frt_count_trailing_ones(word);
+}
+
+/**
+ * Scan the FrtBitVector for the next unset bit. Before using this
+ * function you should reset the FrtBitVector for scanning using
+ * +frt_bv_scan_reset+. You can the repeated call frt_bv_scan_next to
+ * get each unset bit until it finally returns -1.
  *
  * @param bv the FrtBitVector to scan
  * @return the next unset bits index or -1 if no more bits are unset
  */
-extern int frt_bv_scan_next_unset(FrtBitVector *bv);
-
-/**
- * Scan the FrtBitVector for the next unset bit after +from+. If no more bits are
- * unset then return -1, otherwise return the index of teh next unset bit.
- *
- * @param bv the FrtBitVector to scan
- * @return the next unset bit's index or -1 if no more bits are unset
- */
-extern int frt_bv_scan_next_unset_from(FrtBitVector *bv, register const int from);
+extern FRT_ATTR_ALWAYS_INLINE
+int frt_bv_scan_next_unset(FrtBitVector *bv)
+{
+    return frt_bv_scan_next_unset_from(bv, bv->curr_bit + 1);
+}
 
 /**

c/include/global.h

@@ -26 +26 @@
 
 #if __GNUC__ >= 3
-#  define FRT_ALWAYS_INLINE inline __attribute__ ((always_inline))
+#  define FRT_ATTR_ALWAYS_INLINE inline __attribute__ ((always_inline))
+#  define FRT_ATTR_MALLOC               __attribute__ ((malloc))
+#  define FRT_ATTR_PURE                 __attribute__ ((pure))
+#  define FRT_ATTR_CONST                __attribute__ ((const))
 #  define likely(x)   __builtin_expect(!!(x), 1)
 #  define unlikely(x) __builtin_expect(!!(x), 0)
 #else
-#  define FRT_ALWAYS_INLINE
+#  define FRT_ATTR_ALWAYS_INLINE
+#  define FRT_ATTR_MALLOC
+#  define FRT_ATTR_PURE
+#  define FRT_ATTR_CONST
 #  define likely(x)   (x)
 #  define unlikely(x) (x)
@@ -127 +133 @@
 
 /**
+ * Return the count of trailing [LSB] 0 bits in +word+.
+ */
+
+extern FRT_ATTR_ALWAYS_INLINE FRT_ATTR_CONST
+int frt_count_trailing_zeros(frt_u32 word)
+{
+#ifdef __GNUC__
+    return __builtin_ctz(word);
+#else
+    static const int count_trailing_zeros[] = {
+        8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
+        4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
+    };
+                if (word & 0xff) return count_trailing_zeros[word & 0xff];
+    word >>= 8; if (word & 0xff) return count_trailing_zeros[word & 0xff] + 8;
+    word >>= 8; if (word & 0xff) return count_trailing_zeros[word & 0xff] + 16;
+    word >>= 8;                  return count_trailing_zeros[word & 0xff] + 24;
+#endif
+}
+
+extern FRT_ATTR_ALWAYS_INLINE FRT_ATTR_CONST
+int frt_count_trailing_ones(frt_u32 word)
+{
+    return frt_count_trailing_zeros(~word);
+}
+
+extern FRT_ATTR_ALWAYS_INLINE FRT_ATTR_CONST
+int frt_count_ones(frt_u32 word)
+{
+#ifdef __GNUC__
+    return __builtin_popcount(word);
+#else
+    static const frt_uchar count_ones[] = {
+        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
+    };
+    return count_ones[(word      ) & 0xff]
+        +  count_ones[(word >> 8 ) & 0xff]
+        +  count_ones[(word >> 16) & 0xff]
+        +  count_ones[(word >> 24) & 0xff];
+#endif
+}
+
+extern FRT_ATTR_ALWAYS_INLINE FRT_ATTR_CONST
+int frt_count_zeros(frt_u32 word)
+{
+    return frt_count_ones(~word);
+}
+
+/**
  * For coverage, we don't want FRT_XEXIT to actually exit on uncaught
  * exceptions.  +frt_x_abort_on_exception+ is +true+ by default, set it to

c/src/bitvector.c

@@ -5 +5 @@
 BitVector *bv_new_capa(int capa)
 {
-    BitVector *bv = ALLOC(BitVector);
+    BitVector *bv = ALLOC_AND_ZERO(BitVector);
 
     /* The capacity passed by the user is number of bits allowed, however we
@@ -11 +11 @@
     bv->capa = (capa >> 5) + 1;
     bv->bits = ALLOC_AND_ZERO_N(u32, bv->capa);
-
-    bv->size = 0;
-    bv->count = 0;
     bv->curr_bit = -1;
-    bv->extends_as_ones = 0;
     bv->ref_cnt = 1;
     return bv;
@@ -33 +29 @@
 }
 
-void bv_set(BitVector *bv, int bit)
-{
-    u32 *word_p;
+void bv_clear(BitVector *bv)
+{
+    memset(bv->bits, 0, bv->capa * sizeof(u32));
+    bv->extends_as_ones = 0;
+    bv->count = 0;
+    bv->size = 0;
+}
+
+void bv_unset(BitVector *bv, int bit)
+{
+    frt_u32 *word_p;
     int word = bit >> 5;
-    u32 bitmask = 1 << (bit & 31);
-    
+    frt_u32 bitmask = 1 << (bit & 31);
+
     /* Check to see if we need to grow the BitVector */
-    if (bit >= bv->size) {
+    if (unlikely(bit >= bv->size)) {
         bv->size = bit + 1; /* size is max range of bits set */
         if (word >= bv->capa) {
@@ -47 +51 @@
                 capa <<= 1;
             }
-            REALLOC_N(bv->bits, u32, capa);
+            FRT_REALLOC_N(bv->bits, frt_u32, capa);
             memset(bv->bits + bv->capa, (bv->extends_as_ones ? 0xFF : 0),
-                   sizeof(u32) * (capa - bv->capa));
+                   sizeof(frt_u32) * (capa - bv->capa));
             bv->capa = capa;
         }
     }
-    
+
     /* Set the required bit */
     word_p = &(bv->bits[word]);
-    if ((bitmask & *word_p) == 0) {
-        bv->count++; /* update count */
-        *word_p |= bitmask;
-    }
-}
-
-/*
- * This method relies on the fact that enough space has been allocated for the
- * bits to be set. You need to create the BitVector using bv_new_capa(capa)
- * with a capacity larger than any bit being set.
- */
-INLINE void bv_set_fast(BitVector *bv, int bit)
-{
-    bv->count++;
-    bv->size = bit + 1;
-    bv->bits[bit >> 5] |= 1 << (bit & 31);
-}
-
-int bv_get(BitVector *bv, int bit)
-{
-    /* out of range so return 0 because it can't have been set */
-    if (bit >= bv->size) {
-        return bv->extends_as_ones;
-    }
-    return (bv->bits[bit >> 5] >> (bit & 31)) & 0x01;
-}
-
-void bv_clear(BitVector *bv)
-{
-    memset(bv->bits, 0, bv->capa * sizeof(u32));
-    bv->extends_as_ones = 0;
-    bv->count = 0;
-    bv->size = 0;
-}
-
-/*
- * FIXME: if the top set bit is unset, size is not adjusted. This will not
- * cause any bugs in this code but could cause problems if users are relying
- * on the fact that size is accurate.
- */
-void bv_unset(BitVector *bv, int bit)
-{
-    u32 *word_p;
-    u32 bitmask;
-    int word = bit >> 5;
-
-    if (bit >= bv->size) {
-        bv->size = bit + 1; /* size is max range of bits set */
-        if (word >= bv->capa) {
-            int capa = bv->capa << 1;
-
-            while (capa <= word) {
-                capa <<= 1;
-            }
-            REALLOC_N(bv->bits, u32, capa);
-            memset(bv->bits + bv->capa, (bv->extends_as_ones ? 0xFF : 0),
-                   sizeof(u32) * (capa - bv->capa));
-            bv->capa = capa;
-        }
-    }
-    
-    word_p = &(bv->bits[word]);
-    bitmask = 1 << (bit & 31);
-    if ((bitmask & *word_p) > 0) {
+    if ((bitmask & *word_p) != 0) {
         bv->count--; /* update count */
         *word_p &= ~bitmask;
@@ -125 +66 @@
 }
 
-/* Table of bits per char. This table is used by the bv_recount method to
- * optimize the counting of bits */
-static const uchar BYTE_COUNTS[] = {
-    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
-    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
-    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
-    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
-};
-
 int bv_recount(BitVector *bv)
 {
-    /* if the vector has been modified */
-    int i, c = 0;
-    uchar *bytes = (uchar *)bv->bits; /* count by character */
-    const int num_bytes = (((bv->size >> 5) + 1) << 2);
+    unsigned int extra = ((bv->size & 31) >> 3) + 1;
+    unsigned int len   = bv->size >> 5;
+    unsigned int idx, count = 0;
+
     if (bv->extends_as_ones) {
-        for (i = 0; i < num_bytes; i++) {
-            c += BYTE_COUNTS[~(bytes[i]) & 0xFF];  /* sum bits per char */
-        }
-    }
-    else {
-        for (i = 0; i < num_bytes; i++) {
-            c += BYTE_COUNTS[bytes[i]];     /* sum bits per char */
-        }
-    }
-    bv->count = c;
-    return c;
+        for (idx = 0; idx < len; ++idx) {
+            count += frt_count_zeros(bv->bits[idx]);
+        }
+        switch (extra) {
+            case 4: count += frt_count_zeros(bv->bits[idx] | 0x00ffffff);
+            case 3: count += frt_count_zeros(bv->bits[idx] | 0xff00ffff);
+            case 2: count += frt_count_zeros(bv->bits[idx] | 0xffff00ff);
+            case 1: count += frt_count_zeros(bv->bits[idx] | 0xffffff00);
+        }
+    }
+    else {
+        for (idx = 0; idx < len; ++idx) {
+            count += frt_count_ones(bv->bits[idx]);
+        }
+        switch (extra) {
+            case 4: count += frt_count_ones(bv->bits[idx] & 0xff000000);
+            case 3: count += frt_count_ones(bv->bits[idx] & 0x00ff0000);
+            case 2: count += frt_count_ones(bv->bits[idx] & 0x0000ff00);
+            case 1: count += frt_count_ones(bv->bits[idx] & 0x000000ff);
+        }
+    }
+    return bv->count = count;
 }
 
@@ -169 +100 @@
 {
     bv->curr_bit = -1;
-}
-
-/* Table showing the number of trailing 0s in a char. This is used to optimize
- * the bv_scan_next method.  */
-static const int NUM_TRAILING_ZEROS[] = {
-    8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 
-    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
-    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
-};
-
-/*
- * This method is highly optimized, hence the loop unrolling
- */
-static INLINE int bv_get_1_offset(u32 word)
-{
-    if (word & 0xff) {
-        return NUM_TRAILING_ZEROS[word & 0xff];
-    }
-    else {
-        word >>= 8;
-        if (word & 0xff) {
-            return NUM_TRAILING_ZEROS[word & 0xff] + 8;
-        }
-        else {
-            word >>= 8;
-            if (word & 0xff) {
-                return NUM_TRAILING_ZEROS[word & 0xff] + 16;
-            }
-            else {
-                word >>= 8;
-                return NUM_TRAILING_ZEROS[word & 0xff] + 24;
-            }
-        }
-    }
-}
-    /*
-     * second fastest;
-     *
-     *   while ((inc = NUM_TRA