blob: 75f81be8ae3a26b856ee094b3b57662b140819fc [file] [log] [blame]
 // Copyright (c) 2013 The Chromium Authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. // This file defines some bit utilities. #ifndef THIRD_PARTY_BASE_BITS_H_ #define THIRD_PARTY_BASE_BITS_H_ #include #include #include #include "third_party/base/check.h" #include "third_party/base/compiler_specific.h" #if defined(COMPILER_MSVC) #include #endif namespace pdfium { namespace base { namespace bits { // Returns true iff |value| is a power of 2. template ::value>> constexpr inline bool IsPowerOfTwo(T value) { // From "Hacker's Delight": Section 2.1 Manipulating Rightmost Bits. // // Only positive integers with a single bit set are powers of two. If only one // bit is set in x (e.g. 0b00000100000000) then |x-1| will have that bit set // to zero and all bits to its right set to 1 (e.g. 0b00000011111111). Hence // |x & (x-1)| is 0 iff x is a power of two. return value > 0 && (value & (value - 1)) == 0; } // Round up |size| to a multiple of alignment, which must be a power of two. inline size_t Align(size_t size, size_t alignment) { DCHECK(IsPowerOfTwo(alignment)); return (size + alignment - 1) & ~(alignment - 1); } // CountLeadingZeroBits(value) returns the number of zero bits following the // most significant 1 bit in |value| if |value| is non-zero, otherwise it // returns {sizeof(T) * 8}. // Example: 00100010 -> 2 // // CountTrailingZeroBits(value) returns the number of zero bits preceding the // least significant 1 bit in |value| if |value| is non-zero, otherwise it // returns {sizeof(T) * 8}. // Example: 00100010 -> 1 // // C does not have an operator to do this, but fortunately the various // compilers have built-ins that map to fast underlying processor instructions. #if defined(COMPILER_MSVC) template ALWAYS_INLINE typename std::enable_if::value && sizeof(T) <= 4, unsigned>::type CountLeadingZeroBits(T x) { static_assert(bits > 0, "invalid instantiation"); unsigned long index; return LIKELY(_BitScanReverse(&index, static_cast(x))) ? (31 - index - (32 - bits)) : bits; } template ALWAYS_INLINE typename std::enable_if::value && sizeof(T) == 8, unsigned>::type CountLeadingZeroBits(T x) { static_assert(bits > 0, "invalid instantiation"); unsigned long index; return LIKELY(_BitScanReverse64(&index, static_cast(x))) ? (63 - index) : 64; } template ALWAYS_INLINE typename std::enable_if::value && sizeof(T) <= 4, unsigned>::type CountTrailingZeroBits(T x) { static_assert(bits > 0, "invalid instantiation"); unsigned long index; return LIKELY(_BitScanForward(&index, static_cast(x))) ? index : bits; } template ALWAYS_INLINE typename std::enable_if::value && sizeof(T) == 8, unsigned>::type CountTrailingZeroBits(T x) { static_assert(bits > 0, "invalid instantiation"); unsigned long index; return LIKELY(_BitScanForward64(&index, static_cast(x))) ? index : 64; } ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) { return CountLeadingZeroBits(x); } #if defined(ARCH_CPU_64_BITS) // MSVC only supplies _BitScanForward64 when building for a 64-bit target. ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) { return CountLeadingZeroBits(x); } #endif #elif defined(COMPILER_GCC) // __builtin_clz has undefined behaviour for an input of 0, even though there's // clearly a return value that makes sense, and even though some processor clz // instructions have defined behaviour for 0. We could drop to raw __asm__ to // do better, but we'll avoid doing that unless we see proof that we need to. template ALWAYS_INLINE typename std::enable_if::value && sizeof(T) <= 8, unsigned>::type CountLeadingZeroBits(T value) { static_assert(bits > 0, "invalid instantiation"); return LIKELY(value) ? bits == 64 ? __builtin_clzll(static_cast(value)) : __builtin_clz(static_cast(value)) - (32 - bits) : bits; } template ALWAYS_INLINE typename std::enable_if::value && sizeof(T) <= 8, unsigned>::type CountTrailingZeroBits(T value) { return LIKELY(value) ? bits == 64 ? __builtin_ctzll(static_cast(value)) : __builtin_ctz(static_cast(value)) : bits; } ALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) { return CountLeadingZeroBits(x); } #if defined(ARCH_CPU_64_BITS) ALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) { return CountLeadingZeroBits(x); } #endif #endif ALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) { return CountLeadingZeroBits(x); } ALWAYS_INLINE size_t CountTrailingZeroBitsSizeT(size_t x) { return CountTrailingZeroBits(x); } // Returns the integer i such as 2^i <= n < 2^(i+1) inline int Log2Floor(uint32_t n) { return 31 - CountLeadingZeroBits(n); } // Returns the integer i such as 2^(i-1) < n <= 2^i inline int Log2Ceiling(uint32_t n) { // When n == 0, we want the function to return -1. // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is // why the statement below starts with (n ? 32 : -1). return (n ? 32 : -1) - CountLeadingZeroBits(n - 1); } } // namespace bits } // namespace base } // namespace pdfium #endif // THIRD_PARTY_BASE_BITS_H_