X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=include%2Fwimlib%2Fbitops.h;h=7cca2f22debb0cff8bd4aa096df2a6ba2e8e6c64;hb=41a9a2a95bd357a344be95d2ac3c370aadac3846;hp=14c73593521b8bbba6a5646058d7f21500b534af;hpb=d04a25a537201b46832cac28725a45bf559dc318;p=wimlib

diff --git a/include/wimlib/bitops.h b/include/wimlib/bitops.h
index 14c73593..7cca2f22 100644
--- a/include/wimlib/bitops.h
+++ b/include/wimlib/bitops.h
@@ -1,10 +1,28 @@
 /*
- * bitops.h
+ * bitops.h - inline functions for bit manipulation
  *
- * Inline functions for bit manipulation.
+ * Copyright 2022 Eric Biggers
  *
- * The author dedicates this file to the public domain.
- * You can do whatever you want with this file.
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
  */
 
 #ifndef _WIMLIB_BITOPS_H
@@ -13,13 +31,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)
+static forceinline unsigned
+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)
@@ -28,11 +50,11 @@ fls32(u32 v)
 #endif
 }
 
-static inline unsigned
-fls64(u64 v)
+static forceinline unsigned
+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)
@@ -41,23 +63,27 @@ fls64(u64 v)
 #endif
 }
 
-static inline unsigned
-flsw(machine_word_t v)
+static forceinline unsigned
+bsrw(machine_word_t v)
 {
-	STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8);
-	if (WORDSIZE == 4)
-		return fls32(v);
+	STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
+	if (WORDBITS == 32)
+		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)
+static forceinline unsigned
+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)
@@ -66,11 +92,11 @@ ffs32(u32 v)
 #endif
 }
 
-static inline unsigned
-ffs64(u64 v)
+static forceinline unsigned
+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)
@@ -79,24 +105,30 @@ ffs64(u64 v)
 #endif
 }
 
-static inline unsigned
-ffsw(machine_word_t v)
+static forceinline unsigned
+bsfw(machine_word_t v)
 {
-	STATIC_ASSERT(WORDSIZE == 4 || WORDSIZE == 8);
-	if (WORDSIZE == 4)
-		return ffs32(v);
+	STATIC_ASSERT(WORDBITS == 32 || WORDBITS == 64);
+	if (WORDBITS == 32)
+		return bsf32(v);
 	else
-		return ffs64(v);
+		return bsf64(v);
 }
 
-/* Round up to nearest power of 2  */
+/* Return the log base 2 of 'n', rounded up to the nearest integer. */
+static forceinline unsigned
+ilog2_ceil(size_t n)
+{
+        if (n <= 1)
+                return 0;
+        return 1 + bsrw(n - 1);
+}
 
-static inline size_t
+/* Round 'n' up to the nearest power of 2 */
+static forceinline size_t
 roundup_pow_of_2(size_t n)
 {
-	if (n <= 1)
-		return 1;
-	return (size_t)1 << (1 + flsw(n - 1));
+	return (size_t)1 << ilog2_ceil(n);
 }
 
 #endif /* _WIMLIB_BITOPS_H */