blob: 3a92b4c8ed815da48c34ac3df93418a4e448a45e [file] [log] [blame]
Chris Palmer79e548e2017-03-16 11:39:48 -07001// 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 Zhang158b5712018-10-01 17:42:19 +00007#ifndef THIRD_PARTY_BASE_BITS_H_
8#define THIRD_PARTY_BASE_BITS_H_
Chris Palmer79e548e2017-03-16 11:39:48 -07009
10#include <stddef.h>
11#include <stdint.h>
12
Lei Zhangce342182018-10-01 18:00:10 +000013#include <type_traits>
14
Chris Palmer79e548e2017-03-16 11:39:48 -070015#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
22namespace pdfium {
23namespace base {
24namespace bits {
25
Chris Palmer79e548e2017-03-16 11:39:48 -070026// Round up |size| to a multiple of alignment, which must be a power of two.
27inline 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 Zhangcda8e002018-05-16 19:18:42 +000032// 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 Palmer79e548e2017-03-16 11:39:48 -070044#if defined(COMPILER_MSVC)
45
Lei Zhangcda8e002018-05-16 19:18:42 +000046template <typename T, unsigned bits = sizeof(T) * 8>
47ALWAYS_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 Palmer79e548e2017-03-16 11:39:48 -070052 unsigned long index;
Lei Zhangcda8e002018-05-16 19:18:42 +000053 return LIKELY(_BitScanReverse(&index, static_cast<uint32_t>(x)))
54 ? (31 - index - (32 - bits))
55 : bits;
56}
57
58template <typename T, unsigned bits = sizeof(T) * 8>
59ALWAYS_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
70template <typename T, unsigned bits = sizeof(T) * 8>
71ALWAYS_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
81template <typename T, unsigned bits = sizeof(T) * 8>
82ALWAYS_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
92ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
93 return CountLeadingZeroBits(x);
Chris Palmer79e548e2017-03-16 11:39:48 -070094}
95
96#if defined(ARCH_CPU_64_BITS)
97
98// MSVC only supplies _BitScanForward64 when building for a 64-bit target.
99ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) {
Lei Zhangcda8e002018-05-16 19:18:42 +0000100 return CountLeadingZeroBits(x);
Chris Palmer79e548e2017-03-16 11:39:48 -0700101}
102
103#endif
104
105#elif defined(COMPILER_GCC)
106
Lei Zhangcda8e002018-05-16 19:18:42 +0000107// __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.
111template <typename T, unsigned bits = sizeof(T) * 8>
112ALWAYS_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
124template <typename T, unsigned bits = sizeof(T) * 8>
125ALWAYS_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 Palmer79e548e2017-03-16 11:39:48 -0700135ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) {
Lei Zhangcda8e002018-05-16 19:18:42 +0000136 return CountLeadingZeroBits(x);
Chris Palmer79e548e2017-03-16 11:39:48 -0700137}
138
Chris Palmer79e548e2017-03-16 11:39:48 -0700139#if defined(ARCH_CPU_64_BITS)
140
Lei Zhangcda8e002018-05-16 19:18:42 +0000141ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) {
142 return CountLeadingZeroBits(x);
Chris Palmer79e548e2017-03-16 11:39:48 -0700143}
144
145#endif
146
Lei Zhangcda8e002018-05-16 19:18:42 +0000147#endif
148
149ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) {
150 return CountLeadingZeroBits(x);
151}
152
153ALWAYS_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)
158inline 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
163inline 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 Palmer79e548e2017-03-16 11:39:48 -0700170} // namespace bits
171} // namespace base
172} // namespace pdfium
173
Lei Zhang158b5712018-10-01 17:42:19 +0000174#endif // THIRD_PARTY_BASE_BITS_H_