Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 1 | // Copyright (c) 2013 The Chromium Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| 5 | // This file defines some bit utilities. |
| 6 | |
Lei Zhang | 158b571 | 2018-10-01 17:42:19 +0000 | [diff] [blame] | 7 | #ifndef THIRD_PARTY_BASE_BITS_H_ |
| 8 | #define THIRD_PARTY_BASE_BITS_H_ |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 9 | |
| 10 | #include <stddef.h> |
| 11 | #include <stdint.h> |
| 12 | |
Lei Zhang | ce34218 | 2018-10-01 18:00:10 +0000 | [diff] [blame] | 13 | #include <type_traits> |
| 14 | |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 15 | #include "third_party/base/compiler_specific.h" |
| 16 | #include "third_party/base/logging.h" |
| 17 | |
| 18 | #if defined(COMPILER_MSVC) |
| 19 | #include <intrin.h> |
| 20 | #endif |
| 21 | |
| 22 | namespace pdfium { |
| 23 | namespace base { |
| 24 | namespace bits { |
| 25 | |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 26 | // Round up |size| to a multiple of alignment, which must be a power of two. |
| 27 | inline size_t Align(size_t size, size_t alignment) { |
| 28 | DCHECK_EQ(alignment & (alignment - 1), 0u); |
| 29 | return (size + alignment - 1) & ~(alignment - 1); |
| 30 | } |
| 31 | |
Lei Zhang | cda8e00 | 2018-05-16 19:18:42 +0000 | [diff] [blame] | 32 | // CountLeadingZeroBits(value) returns the number of zero bits following the |
| 33 | // most significant 1 bit in |value| if |value| is non-zero, otherwise it |
| 34 | // returns {sizeof(T) * 8}. |
| 35 | // Example: 00100010 -> 2 |
| 36 | // |
| 37 | // CountTrailingZeroBits(value) returns the number of zero bits preceding the |
| 38 | // least significant 1 bit in |value| if |value| is non-zero, otherwise it |
| 39 | // returns {sizeof(T) * 8}. |
| 40 | // Example: 00100010 -> 1 |
| 41 | // |
| 42 | // C does not have an operator to do this, but fortunately the various |
| 43 | // compilers have built-ins that map to fast underlying processor instructions. |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 44 | #if defined(COMPILER_MSVC) |
| 45 | |
Lei Zhang | cda8e00 | 2018-05-16 19:18:42 +0000 | [diff] [blame] | 46 | template <typename T, unsigned bits = sizeof(T) * 8> |
| 47 | ALWAYS_INLINE |
| 48 | typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 4, |
| 49 | unsigned>::type |
| 50 | CountLeadingZeroBits(T x) { |
| 51 | static_assert(bits > 0, "invalid instantiation"); |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 52 | unsigned long index; |
Lei Zhang | cda8e00 | 2018-05-16 19:18:42 +0000 | [diff] [blame] | 53 | return LIKELY(_BitScanReverse(&index, static_cast<uint32_t>(x))) |
| 54 | ? (31 - index - (32 - bits)) |
| 55 | : bits; |
| 56 | } |
| 57 | |
| 58 | template <typename T, unsigned bits = sizeof(T) * 8> |
| 59 | ALWAYS_INLINE |
| 60 | typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) == 8, |
| 61 | unsigned>::type |
| 62 | CountLeadingZeroBits(T x) { |
| 63 | static_assert(bits > 0, "invalid instantiation"); |
| 64 | unsigned long index; |
| 65 | return LIKELY(_BitScanReverse64(&index, static_cast<uint64_t>(x))) |
| 66 | ? (63 - index) |
| 67 | : 64; |
| 68 | } |
| 69 | |
| 70 | template <typename T, unsigned bits = sizeof(T) * 8> |
| 71 | ALWAYS_INLINE |
| 72 | typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 4, |
| 73 | unsigned>::type |
| 74 | CountTrailingZeroBits(T x) { |
| 75 | static_assert(bits > 0, "invalid instantiation"); |
| 76 | unsigned long index; |
| 77 | return LIKELY(_BitScanForward(&index, static_cast<uint32_t>(x))) ? index |
| 78 | : bits; |
| 79 | } |
| 80 | |
| 81 | template <typename T, unsigned bits = sizeof(T) * 8> |
| 82 | ALWAYS_INLINE |
| 83 | typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) == 8, |
| 84 | unsigned>::type |
| 85 | CountTrailingZeroBits(T x) { |
| 86 | static_assert(bits > 0, "invalid instantiation"); |
| 87 | unsigned long index; |
| 88 | return LIKELY(_BitScanForward64(&index, static_cast<uint64_t>(x))) ? index |
| 89 | : 64; |
| 90 | } |
| 91 | |
| 92 | ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) { |
| 93 | return CountLeadingZeroBits(x); |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | #if defined(ARCH_CPU_64_BITS) |
| 97 | |
| 98 | // MSVC only supplies _BitScanForward64 when building for a 64-bit target. |
| 99 | ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) { |
Lei Zhang | cda8e00 | 2018-05-16 19:18:42 +0000 | [diff] [blame] | 100 | return CountLeadingZeroBits(x); |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 101 | } |
| 102 | |
| 103 | #endif |
| 104 | |
| 105 | #elif defined(COMPILER_GCC) |
| 106 | |
Lei Zhang | cda8e00 | 2018-05-16 19:18:42 +0000 | [diff] [blame] | 107 | // __builtin_clz has undefined behaviour for an input of 0, even though there's |
| 108 | // clearly a return value that makes sense, and even though some processor clz |
| 109 | // instructions have defined behaviour for 0. We could drop to raw __asm__ to |
| 110 | // do better, but we'll avoid doing that unless we see proof that we need to. |
| 111 | template <typename T, unsigned bits = sizeof(T) * 8> |
| 112 | ALWAYS_INLINE |
| 113 | typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8, |
| 114 | unsigned>::type |
| 115 | CountLeadingZeroBits(T value) { |
| 116 | static_assert(bits > 0, "invalid instantiation"); |
| 117 | return LIKELY(value) |
| 118 | ? bits == 64 |
| 119 | ? __builtin_clzll(static_cast<uint64_t>(value)) |
| 120 | : __builtin_clz(static_cast<uint32_t>(value)) - (32 - bits) |
| 121 | : bits; |
| 122 | } |
| 123 | |
| 124 | template <typename T, unsigned bits = sizeof(T) * 8> |
| 125 | ALWAYS_INLINE |
| 126 | typename std::enable_if<std::is_unsigned<T>::value && sizeof(T) <= 8, |
| 127 | unsigned>::type |
| 128 | CountTrailingZeroBits(T value) { |
| 129 | return LIKELY(value) ? bits == 64 |
| 130 | ? __builtin_ctzll(static_cast<uint64_t>(value)) |
| 131 | : __builtin_ctz(static_cast<uint32_t>(value)) |
| 132 | : bits; |
| 133 | } |
| 134 | |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 135 | ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) { |
Lei Zhang | cda8e00 | 2018-05-16 19:18:42 +0000 | [diff] [blame] | 136 | return CountLeadingZeroBits(x); |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 137 | } |
| 138 | |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 139 | #if defined(ARCH_CPU_64_BITS) |
| 140 | |
Lei Zhang | cda8e00 | 2018-05-16 19:18:42 +0000 | [diff] [blame] | 141 | ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) { |
| 142 | return CountLeadingZeroBits(x); |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 143 | } |
| 144 | |
| 145 | #endif |
| 146 | |
Lei Zhang | cda8e00 | 2018-05-16 19:18:42 +0000 | [diff] [blame] | 147 | #endif |
| 148 | |
| 149 | ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) { |
| 150 | return CountLeadingZeroBits(x); |
| 151 | } |
| 152 | |
| 153 | ALWAYS_INLINE size_t CountTrailingZeroBitsSizeT(size_t x) { |
| 154 | return CountTrailingZeroBits(x); |
| 155 | } |
| 156 | |
| 157 | // Returns the integer i such as 2^i <= n < 2^(i+1) |
| 158 | inline int Log2Floor(uint32_t n) { |
| 159 | return 31 - CountLeadingZeroBits(n); |
| 160 | } |
| 161 | |
| 162 | // Returns the integer i such as 2^(i-1) < n <= 2^i |
| 163 | inline int Log2Ceiling(uint32_t n) { |
| 164 | // When n == 0, we want the function to return -1. |
| 165 | // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is |
| 166 | // why the statement below starts with (n ? 32 : -1). |
| 167 | return (n ? 32 : -1) - CountLeadingZeroBits(n - 1); |
| 168 | } |
| 169 | |
Chris Palmer | 79e548e | 2017-03-16 11:39:48 -0700 | [diff] [blame] | 170 | } // namespace bits |
| 171 | } // namespace base |
| 172 | } // namespace pdfium |
| 173 | |
Lei Zhang | 158b571 | 2018-10-01 17:42:19 +0000 | [diff] [blame] | 174 | #endif // THIRD_PARTY_BASE_BITS_H_ |