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