From 8618172276fae088f311923a61bbf26c3d4d8941 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Sat, 9 Jul 2016 10:01:25 -0500 Subject: [PATCH] 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'. --- include/wimlib/bitops.h | 50 ++++++++++++++++++++++---------------- include/wimlib/compiler.h | 8 +++--- include/wimlib/lz_extend.h | 4 +-- src/lzx_common.c | 2 +- src/resource.c | 2 +- src/xpress_compress.c | 10 ++++---- 6 files changed, 42 insertions(+), 34 deletions(-) diff --git a/include/wimlib/bitops.h b/include/wimlib/bitops.h index d964374d..2c905057 100644 --- a/include/wimlib/bitops.h +++ b/include/wimlib/bitops.h @@ -24,13 +24,17 @@ #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 */ diff --git a/include/wimlib/compiler.h b/include/wimlib/compiler.h index 9f53e192..6bce5d01 100644 --- 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. */ -#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__ diff --git a/include/wimlib/lz_extend.h b/include/wimlib/lz_extend.h index c4547e2b..cbbe88fd 100644 --- 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) - 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; diff --git a/src/lzx_common.c b/src/lzx_common.c index 194e8162..fe201a42 100644 --- 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)) { - unsigned bit = ffs32(e8_mask); + unsigned bit = bsf32(e8_mask); (*process_target)(p + bit + 1, p + bit - data); valid_mask &= ~((u64)0x1F << bit); } diff --git a/src/resource.c b/src/resource.c index c3e6927c..385f9f65 100644 --- 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; diff --git a/src/xpress_compress.c b/src/xpress_compress.c index d8cb7697..99a4b46a 100644 --- 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; - 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; -- 2.43.0