bits.h (4123B)
1 // Copyright (c) the JPEG XL Project Authors. All rights reserved. 2 // 3 // Use of this source code is governed by a BSD-style 4 // license that can be found in the LICENSE file. 5 6 #ifndef LIB_JXL_BASE_BITS_H_ 7 #define LIB_JXL_BASE_BITS_H_ 8 9 // Specialized instructions for processing register-sized bit arrays. 10 11 #include "lib/jxl/base/compiler_specific.h" 12 #include "lib/jxl/base/status.h" 13 14 #if JXL_COMPILER_MSVC 15 #include <intrin.h> 16 #endif 17 18 #include <stddef.h> 19 #include <stdint.h> 20 21 namespace jxl { 22 23 // Empty struct used as a size tag type. 24 template <size_t N> 25 struct SizeTag {}; 26 27 template <typename T> 28 constexpr bool IsSigned() { 29 // TODO(eustas): remove dupes 30 return static_cast<T>(0) > static_cast<T>(-1); 31 } 32 33 // Undefined results for x == 0. 34 static JXL_INLINE JXL_MAYBE_UNUSED size_t 35 Num0BitsAboveMS1Bit_Nonzero(SizeTag<4> /* tag */, const uint32_t x) { 36 JXL_DASSERT(x != 0); 37 #if JXL_COMPILER_MSVC 38 unsigned long index; 39 _BitScanReverse(&index, x); 40 return 31 - index; 41 #else 42 return static_cast<size_t>(__builtin_clz(x)); 43 #endif 44 } 45 static JXL_INLINE JXL_MAYBE_UNUSED size_t 46 Num0BitsAboveMS1Bit_Nonzero(SizeTag<8> /* tag */, const uint64_t x) { 47 JXL_DASSERT(x != 0); 48 #if JXL_COMPILER_MSVC 49 #if JXL_ARCH_X64 50 unsigned long index; 51 _BitScanReverse64(&index, x); 52 return 63 - index; 53 #else // JXL_ARCH_X64 54 // _BitScanReverse64 not available 55 uint32_t msb = static_cast<uint32_t>(x >> 32u); 56 unsigned long index; 57 if (msb == 0) { 58 uint32_t lsb = static_cast<uint32_t>(x & 0xFFFFFFFF); 59 _BitScanReverse(&index, lsb); 60 return 63 - index; 61 } else { 62 _BitScanReverse(&index, msb); 63 return 31 - index; 64 } 65 #endif // JXL_ARCH_X64 66 #else 67 return static_cast<size_t>(__builtin_clzll(x)); 68 #endif 69 } 70 template <typename T> 71 static JXL_INLINE JXL_MAYBE_UNUSED size_t 72 Num0BitsAboveMS1Bit_Nonzero(const T x) { 73 static_assert(!IsSigned<T>(), "Num0BitsAboveMS1Bit_Nonzero: use unsigned"); 74 return Num0BitsAboveMS1Bit_Nonzero(SizeTag<sizeof(T)>(), x); 75 } 76 77 // Undefined results for x == 0. 78 static JXL_INLINE JXL_MAYBE_UNUSED size_t 79 Num0BitsBelowLS1Bit_Nonzero(SizeTag<4> /* tag */, const uint32_t x) { 80 JXL_DASSERT(x != 0); 81 #if JXL_COMPILER_MSVC 82 unsigned long index; 83 _BitScanForward(&index, x); 84 return index; 85 #else 86 return static_cast<size_t>(__builtin_ctz(x)); 87 #endif 88 } 89 static JXL_INLINE JXL_MAYBE_UNUSED size_t 90 Num0BitsBelowLS1Bit_Nonzero(SizeTag<8> /* tag */, const uint64_t x) { 91 JXL_DASSERT(x != 0); 92 #if JXL_COMPILER_MSVC 93 #if JXL_ARCH_X64 94 unsigned long index; 95 _BitScanForward64(&index, x); 96 return index; 97 #else // JXL_ARCH_64 98 // _BitScanForward64 not available 99 uint32_t lsb = static_cast<uint32_t>(x & 0xFFFFFFFF); 100 unsigned long index; 101 if (lsb == 0) { 102 uint32_t msb = static_cast<uint32_t>(x >> 32u); 103 _BitScanForward(&index, msb); 104 return 32 + index; 105 } else { 106 _BitScanForward(&index, lsb); 107 return index; 108 } 109 #endif // JXL_ARCH_X64 110 #else 111 return static_cast<size_t>(__builtin_ctzll(x)); 112 #endif 113 } 114 template <typename T> 115 static JXL_INLINE JXL_MAYBE_UNUSED size_t Num0BitsBelowLS1Bit_Nonzero(T x) { 116 static_assert(!IsSigned<T>(), "Num0BitsBelowLS1Bit_Nonzero: use unsigned"); 117 return Num0BitsBelowLS1Bit_Nonzero(SizeTag<sizeof(T)>(), x); 118 } 119 120 // Returns bit width for x == 0. 121 template <typename T> 122 static JXL_INLINE JXL_MAYBE_UNUSED size_t Num0BitsAboveMS1Bit(const T x) { 123 return (x == 0) ? sizeof(T) * 8 : Num0BitsAboveMS1Bit_Nonzero(x); 124 } 125 126 // Returns bit width for x == 0. 127 template <typename T> 128 static JXL_INLINE JXL_MAYBE_UNUSED size_t Num0BitsBelowLS1Bit(const T x) { 129 return (x == 0) ? sizeof(T) * 8 : Num0BitsBelowLS1Bit_Nonzero(x); 130 } 131 132 // Returns base-2 logarithm, rounded down. 133 template <typename T> 134 static JXL_INLINE JXL_MAYBE_UNUSED size_t FloorLog2Nonzero(const T x) { 135 return (sizeof(T) * 8 - 1) ^ Num0BitsAboveMS1Bit_Nonzero(x); 136 } 137 138 // Returns base-2 logarithm, rounded up. 139 template <typename T> 140 static JXL_INLINE JXL_MAYBE_UNUSED size_t CeilLog2Nonzero(const T x) { 141 const size_t floor_log2 = FloorLog2Nonzero(x); 142 if ((x & (x - 1)) == 0) return floor_log2; // power of two 143 return floor_log2 + 1; 144 } 145 146 } // namespace jxl 147 148 #endif // LIB_JXL_BASE_BITS_H_