bitops: rename bit scan functions

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'.

diff --git a/include/wimlib/bitops.h b/include/wimlib/bitops.h
index d964374d63e0def7112e83ea5532d7d1d7f91832..2c90505715af988a19c88094dc08ed045c1df329 100644 (file)
--- a/include/wimlib/bitops.h
+++ b/include/wimlib/bitops.h
@@ -24,13 +24,17 @@
 #include "wimlib/compiler.h"
 #include "wimlib/types.h"
 
 #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
 
 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)
 #else
        unsigned bit = 0;
        while ((v >>= 1) != 0)


@@ -40,10 +44,10 @@ fls32(u32 v)
 }
 
 static inline unsigned
 }
 
 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)
 #else
        unsigned bit = 0;
        while ((v >>= 1) != 0)


@@ -53,22 +57,26 @@ fls64(u64 v)
 }
 
 static inline unsigned
 }
 
 static inline unsigned

-flsw(machine_word_t v)
+bsrw(machine_word_t v)

 {
        STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
        if (WORDBITS == 32)
 {
        STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
        if (WORDBITS == 32)

-               return fls32(v);
+               return bsr32(v);

        else
        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
 
 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)
 #else
        unsigned bit;
        for (bit = 0; !(v & 1); bit++, v >>= 1)


@@ -78,10 +86,10 @@ ffs32(u32 v)
 }
 
 static inline unsigned
 }
 
 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)
 #else
        unsigned bit;
        for (bit = 0; !(v & 1); bit++, v >>= 1)


@@ -91,13 +99,13 @@ ffs64(u64 v)
 }
 
 static inline unsigned
 }
 
 static inline unsigned

-ffsw(machine_word_t v)
+bsfw(machine_word_t v)

 {
        STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
        if (WORDBITS == 32)
 {
        STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
        if (WORDBITS == 32)

-               return ffs32(v);
+               return bsf32(v);

        else
        else

-               return ffs64(v);
+               return bsf64(v);

 }
 
 /* Return the log base 2 of 'n', rounded up to the nearest integer. */
 }
 
 /* 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;
 {
         if (n <= 1)
                 return 0;

-        return 1 + flsw(n - 1);
+        return 1 + bsrw(n - 1);

 }
 
 /* Round 'n' up to the nearest power of 2 */
 }
 
 /* Round 'n' up to the nearest power of 2 */

diff --git a/include/wimlib/compiler.h b/include/wimlib/compiler.h
index 9f53e192fc52796e2837c016a2f20b479e05d1cf..6bce5d0152e11742905461df5d1b6fcc1b71411d 100644 (file)
--- a/include/wimlib/compiler.h
+++ b/include/wimlib/compiler.h
@@ -171,10 +171,10 @@
 #endif
 
 /* (Optional) Find Last Set bit and Find First Set bit macros.  */
 #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__
 
 /* Optional definitions for checking with 'sparse'.  */
 #ifdef __CHECKER__

diff --git a/include/wimlib/lz_extend.h b/include/wimlib/lz_extend.h
index c4547e2bc6d9d046e7aebc35ee765eae40db9342..cbbe88fdf09c246ad0c3ea79c9a55c1b6f475fc1 100644 (file)
--- a/include/wimlib/lz_extend.h
+++ b/include/wimlib/lz_extend.h
@@ -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)
                                   load_word_unaligned(strptr + len);
                if (v != 0) {
                        if (CPU_IS_LITTLE_ENDIAN)

-                               len += ffsw(v) >> 3;
+                               len += bsfw(v) >> 3;

                        else
                        else

-                               len += (WORDBITS - 1 - flsw(v)) >> 3;
+                               len += (WORDBITS - 1 - bsrw(v)) >> 3;

                        return len;
                }
                len += WORDBYTES;
                        return len;
                }
                len += WORDBYTES;

diff --git a/src/lzx_common.c b/src/lzx_common.c
index 194e8162da2e4bc67eb91fc213b8c4a8b78ab3e2..fe201a42e5ab4ab67ca6f6f6367aa4cbdafb491b 100644 (file)
--- a/src/lzx_common.c
+++ b/src/lzx_common.c
@@ -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)) {
                         * '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);
                        }
                                (*process_target)(p + bit + 1, p + bit - data);
                                valid_mask &= ~((u64)0x1F << bit);
                        }

diff --git a/src/resource.c b/src/resource.c
index c3e6927c147d50a25dd4e4c0d0f694737e652edc..385f9f65ba6836aa594c5bb34e9b4823eabff79c 100644 (file)
--- a/src/resource.c
+++ b/src/resource.c
@@ -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;
 
        /* Calculate the total number of chunks the resource is divided into.  */
        const u64 num_chunks = (rdesc->uncompressed_size + chunk_size - 1) >> chunk_order;

diff --git a/src/xpress_compress.c b/src/xpress_compress.c
index d8cb7697deb9732eeab7a4e33c1d6093abb618fc..99a4b46a3b3f37285644a0ebe9525579ccd68ee2 100644 (file)
--- a/src/xpress_compress.c
+++ b/src/xpress_compress.c
@@ -413,7 +413,7 @@ xpress_write_item_list(struct xpress_output_bitstream *os,
                        unsigned sym;
 
                        adjusted_len = length - XPRESS_MIN_MATCH_LEN;
                        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);
 
                        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 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]++;
        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;
                        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);
 
                        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;
                                u32 offset_cost;
 
                                offset = match->offset;

-                               log2_offset = fls32(offset);
+                               log2_offset = bsr32(offset);

                                offset_cost = log2_offset;
                                do {
                                        unsigned len_hdr;
                                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;
                                u32 offset_cost;
 
                                offset = match->offset;

-                               log2_offset = fls32(offset);
+                               log2_offset = bsr32(offset);

                                offset_cost = log2_offset;
                                do {
                                        unsigned adjusted_len;
                                offset_cost = log2_offset;
                                do {
                                        unsigned adjusted_len;