/*
* bitops.h - inline functions for bit manipulation
*
- * The following copying information applies to this specific source code file:
+ * Copyright 2022 Eric Biggers
*
- * Written in 2014-2016 by Eric Biggers <ebiggers3@gmail.com>
+ * 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:
*
- * To the extent possible under law, the author(s) have dedicated all copyright
- * and related and neighboring rights to this software to the public domain
- * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
- * Dedication (the "CC0").
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
*
- * This software is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
- * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
- *
- * You should have received a copy of the CC0 along with this software; if not
- * see <http://creativecommons.org/publicdomain/zero/1.0/>.
+ * 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
#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);
-#else
- unsigned bit = 0;
- while ((v >>= 1) != 0)
- bit++;
- return bit;
-#endif
+ return 31 - __builtin_clz(v);
}
-static inline unsigned
-fls64(u64 v)
+static forceinline unsigned
+bsr64(u64 v)
{
-#ifdef compiler_fls64
- return compiler_fls64(v);
-#else
- unsigned bit = 0;
- while ((v >>= 1) != 0)
- bit++;
- return bit;
-#endif
+ return 63 - __builtin_clzll(v);
}
-static inline unsigned
-flsw(machine_word_t v)
+static forceinline unsigned
+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)
+static forceinline unsigned
+bsf32(u32 v)
{
-#ifdef compiler_ffs32
- return compiler_ffs32(v);
-#else
- unsigned bit;
- for (bit = 0; !(v & 1); bit++, v >>= 1)
- ;
- return bit;
-#endif
+ return __builtin_ctz(v);
}
-static inline unsigned
-ffs64(u64 v)
+static forceinline unsigned
+bsf64(u64 v)
{
-#ifdef compiler_ffs64
- return compiler_ffs64(v);
-#else
- unsigned bit;
- for (bit = 0; !(v & 1); bit++, v >>= 1)
- ;
- return bit;
-#endif
+ return __builtin_ctzll(v);
}
-static inline unsigned
-ffsw(machine_word_t v)
+static forceinline unsigned
+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);
}
-/* 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 */
git://wimlib.net / wimlib / blobdiff