bitops: rename bit scan functions
authorEric Biggers <ebiggers3@gmail.com>
Sat, 9 Jul 2016 15:01:25 +0000 (10:01 -0500)
committerEric Biggers <ebiggers3@gmail.com>
Sat, 9 Jul 2016 15:11:00 +0000 (10:11 -0500)
Our bit scan functions use 0-based indices and do not allow zero inputs.
Rename them to 'bsr' and 'bsf' to match the x86 instructions and avoid
confusion with another common convention for 'fls' and 'ffs'.

include/wimlib/bitops.h
include/wimlib/compiler.h
include/wimlib/lz_extend.h
src/lzx_common.c
src/resource.c
src/xpress_compress.c

index d964374..2c90505 100644 (file)
 #include "wimlib/compiler.h"
 #include "wimlib/types.h"
 
-/* Find Last Set bit   */
+/*
+ * Bit Scan Reverse (BSR) - find the 0-based index (relative to the least
+ * significant bit) of the *most* significant 1 bit in the input value.  The
+ * input value must be nonzero!
+ */
 
 static inline unsigned
-fls32(u32 v)
+bsr32(u32 v)
 {
-#ifdef compiler_fls32
-       return compiler_fls32(v);
+#ifdef compiler_bsr32
+       return compiler_bsr32(v);
 #else
        unsigned bit = 0;
        while ((v >>= 1) != 0)
@@ -40,10 +44,10 @@ fls32(u32 v)
 }
 
 static inline unsigned
-fls64(u64 v)
+bsr64(u64 v)
 {
-#ifdef compiler_fls64
-       return compiler_fls64(v);
+#ifdef compiler_bsr64
+       return compiler_bsr64(v);
 #else
        unsigned bit = 0;
        while ((v >>= 1) != 0)
@@ -53,22 +57,26 @@ fls64(u64 v)
 }
 
 static inline unsigned
-flsw(machine_word_t v)
+bsrw(machine_word_t v)
 {
        STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
        if (WORDBITS == 32)
-               return fls32(v);
+               return bsr32(v);
        else
-               return fls64(v);
+               return bsr64(v);
 }
 
-/* Find First Set bit   */
+/*
+ * Bit Scan Forward (BSF) - find the 0-based index (relative to the least
+ * significant bit) of the *least* significant 1 bit in the input value.  The
+ * input value must be nonzero!
+ */
 
 static inline unsigned
-ffs32(u32 v)
+bsf32(u32 v)
 {
-#ifdef compiler_ffs32
-       return compiler_ffs32(v);
+#ifdef compiler_bsf32
+       return compiler_bsf32(v);
 #else
        unsigned bit;
        for (bit = 0; !(v & 1); bit++, v >>= 1)
@@ -78,10 +86,10 @@ ffs32(u32 v)
 }
 
 static inline unsigned
-ffs64(u64 v)
+bsf64(u64 v)
 {
-#ifdef compiler_ffs64
-       return compiler_ffs64(v);
+#ifdef compiler_bsf64
+       return compiler_bsf64(v);
 #else
        unsigned bit;
        for (bit = 0; !(v & 1); bit++, v >>= 1)
@@ -91,13 +99,13 @@ ffs64(u64 v)
 }
 
 static inline unsigned
-ffsw(machine_word_t v)
+bsfw(machine_word_t v)
 {
        STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
        if (WORDBITS == 32)
-               return ffs32(v);
+               return bsf32(v);
        else
-               return ffs64(v);
+               return bsf64(v);
 }
 
 /* Return the log base 2 of 'n', rounded up to the nearest integer. */
@@ -106,7 +114,7 @@ ilog2_ceil(size_t n)
 {
         if (n <= 1)
                 return 0;
-        return 1 + flsw(n - 1);
+        return 1 + bsrw(n - 1);
 }
 
 /* Round 'n' up to the nearest power of 2 */
index 9f53e19..6bce5d0 100644 (file)
 #endif
 
 /* (Optional) Find Last Set bit and Find First Set bit macros.  */
-#define compiler_fls32(n)      (31 - __builtin_clz(n))
-#define compiler_fls64(n)      (63 - __builtin_clzll(n))
-#define compiler_ffs32(n)      __builtin_ctz(n)
-#define compiler_ffs64(n)      __builtin_ctzll(n)
+#define compiler_bsr32(n)      (31 - __builtin_clz(n))
+#define compiler_bsr64(n)      (63 - __builtin_clzll(n))
+#define compiler_bsf32(n)      __builtin_ctz(n)
+#define compiler_bsf64(n)      __builtin_ctzll(n)
 
 /* Optional definitions for checking with 'sparse'.  */
 #ifdef __CHECKER__
index c4547e2..cbbe88f 100644 (file)
@@ -37,9 +37,9 @@ lz_extend(const u8 * const strptr, const u8 * const matchptr,
                                   load_word_unaligned(strptr + len);
                if (v != 0) {
                        if (CPU_IS_LITTLE_ENDIAN)
-                               len += ffsw(v) >> 3;
+                               len += bsfw(v) >> 3;
                        else
-                               len += (WORDBITS - 1 - flsw(v)) >> 3;
+                               len += (WORDBITS - 1 - bsrw(v)) >> 3;
                        return len;
                }
                len += WORDBYTES;
index 194e816..fe201a4 100644 (file)
@@ -288,7 +288,7 @@ lzx_e8_filter(u8 *data, u32 size, void (*process_target)(void *, s32))
                         * 'valid_mask' ensures we never process an E8 byte that
                         * was itself part of a translation target.  */
                        while ((e8_mask &= valid_mask)) {
-                               unsigned bit = ffs32(e8_mask);
+                               unsigned bit = bsf32(e8_mask);
                                (*process_target)(p + bit + 1, p + bit - data);
                                valid_mask &= ~((u64)0x1F << bit);
                        }
index c3e6927..385f9f6 100644 (file)
@@ -188,7 +188,7 @@ read_compressed_wim_resource(const struct wim_resource_descriptor * const rdesc,
                }
        }
 
-       const u32 chunk_order = fls32(chunk_size);
+       const u32 chunk_order = bsr32(chunk_size);
 
        /* Calculate the total number of chunks the resource is divided into.  */
        const u64 num_chunks = (rdesc->uncompressed_size + chunk_size - 1) >> chunk_order;
index d8cb769..99a4b46 100644 (file)
@@ -413,7 +413,7 @@ xpress_write_item_list(struct xpress_output_bitstream *os,
                        unsigned sym;
 
                        adjusted_len = length - XPRESS_MIN_MATCH_LEN;
-                       log2_offset = fls32(offset);
+                       log2_offset = bsr32(offset);
                        len_hdr = min(0xF, adjusted_len);
                        sym = XPRESS_NUM_CHARS + ((log2_offset << 4) | len_hdr);
 
@@ -501,7 +501,7 @@ xpress_record_match(struct xpress_compressor *c, unsigned length, unsigned offse
 {
        unsigned adjusted_len = length - XPRESS_MIN_MATCH_LEN;
        unsigned len_hdr = min(adjusted_len, 0xF);
-       unsigned log2_offset = fls32(offset);
+       unsigned log2_offset = bsr32(offset);
        unsigned sym = XPRESS_NUM_CHARS + ((log2_offset << 4) | len_hdr);
 
        c->freqs[sym]++;
@@ -755,7 +755,7 @@ xpress_tally_item_list(struct xpress_compressor *c,
                        unsigned sym;
 
                        adjusted_len = length - XPRESS_MIN_MATCH_LEN;
-                       log2_offset = fls32(offset);
+                       log2_offset = bsr32(offset);
                        len_hdr = min(0xF, adjusted_len);
                        sym = XPRESS_NUM_CHARS + ((log2_offset << 4) | len_hdr);
 
@@ -831,7 +831,7 @@ xpress_find_min_cost_path(struct xpress_compressor *c, size_t in_nbytes,
                                u32 offset_cost;
 
                                offset = match->offset;
-                               log2_offset = fls32(offset);
+                               log2_offset = bsr32(offset);
                                offset_cost = log2_offset;
                                do {
                                        unsigned len_hdr;
@@ -860,7 +860,7 @@ xpress_find_min_cost_path(struct xpress_compressor *c, size_t in_nbytes,
                                u32 offset_cost;
 
                                offset = match->offset;
-                               log2_offset = fls32(offset);
+                               log2_offset = bsr32(offset);
                                offset_cost = log2_offset;
                                do {
                                        unsigned adjusted_len;