Debian Codegraph @

lib/jxl/base/bits.h

raw
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_