summary |
shortlog |
log |
commit | commitdiff |
tree
raw |
patch |
inline | side by side (from parent 1:
3ceffe5)
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/compiler.h"
#include "wimlib/types.h"
#include "wimlib/compiler.h"
#include "wimlib/types.h"
+/*
+ * 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!
+ */
-#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)
-#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)
{
STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
if (WORDBITS == 32)
{
STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
if (WORDBITS == 32)
-/* 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!
+ */
-#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)
-#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)
{
STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
if (WORDBITS == 32)
{
STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
if (WORDBITS == 32)
}
/* 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. */
- 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 */
#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__
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 += (WORDBITS - 1 - flsw(v)) >> 3;
+ len += (WORDBITS - 1 - bsrw(v)) >> 3;
return len;
}
len += WORDBYTES;
return len;
}
len += WORDBYTES;
* '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);
}
- 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;
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);
{
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]++;
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);
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;
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;