1d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// Copyright (c) 2013 The Chromium Authors. All rights reserved. 2d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// Use of this source code is governed by a BSD-style license that can be 3d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// found in the LICENSE file. 4d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 5d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// This file defines some bit utilities. 6d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 7d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#ifndef BASE_BITS_H_ 8d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#define BASE_BITS_H_ 9d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 10d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#include <stddef.h> 11d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#include <stdint.h> 12d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 13d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#include "third_party/base/compiler_specific.h" 14d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#include "third_party/base/logging.h" 15d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 16d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#if defined(COMPILER_MSVC) 17d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#include <intrin.h> 18d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#endif 19d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 20d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmannnamespace pdfium { 21d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmannnamespace base { 22d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmannnamespace bits { 23d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 24d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// Returns the integer i such as 2^i <= n < 2^(i+1) 25d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmanninline int Log2Floor(uint32_t n) { 26d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann if (n == 0) 27d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return -1; 28d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann int log = 0; 29d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann uint32_t value = n; 30d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann for (int i = 4; i >= 0; --i) { 31d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann int shift = (1 << i); 32d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann uint32_t x = value >> shift; 33d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann if (x != 0) { 34d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann value = x; 35d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann log += shift; 36d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann } 37d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann } 38d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann DCHECK_EQ(value, 1u); 39d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return log; 40d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 41d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 42d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// Returns the integer i such as 2^(i-1) < n <= 2^i 43d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmanninline int Log2Ceiling(uint32_t n) { 44d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann if (n == 0) { 45d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return -1; 46d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann } else { 47d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann // Log2Floor returns -1 for 0, so the following works correctly for n=1. 48d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return 1 + Log2Floor(n - 1); 49d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann } 50d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 51d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 52d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// Round up |size| to a multiple of alignment, which must be a power of two. 53d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmanninline size_t Align(size_t size, size_t alignment) { 54d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann DCHECK_EQ(alignment & (alignment - 1), 0u); 55d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return (size + alignment - 1) & ~(alignment - 1); 56d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 57d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 58d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// These functions count the number of leading zeros in a binary value, starting 59d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// with the most significant bit. C does not have an operator to do this, but 60d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// fortunately the various compilers have built-ins that map to fast underlying 61d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// processor instructions. 62d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#if defined(COMPILER_MSVC) 63d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 64d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. MoltmannALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) { 65d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann unsigned long index; 66d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return LIKELY(_BitScanReverse(&index, x)) ? (31 - index) : 32; 67d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 68d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 69d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#if defined(ARCH_CPU_64_BITS) 70d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 71d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// MSVC only supplies _BitScanForward64 when building for a 64-bit target. 72d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. MoltmannALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) { 73d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann unsigned long index; 74d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return LIKELY(_BitScanReverse64(&index, x)) ? (63 - index) : 64; 75d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 76d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 77d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#endif 78d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 79d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#elif defined(COMPILER_GCC) 80d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 81d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// This is very annoying. __builtin_clz has undefined behaviour for an input of 82d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// 0, even though there's clearly a return value that makes sense, and even 83d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// though some processor clz instructions have defined behaviour for 0. We could 84d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// drop to raw __asm__ to do better, but we'll avoid doing that unless we see 85d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann// proof that we need to. 86d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. MoltmannALWAYS_INLINE uint32_t CountLeadingZeroBits32(uint32_t x) { 87d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return LIKELY(x) ? __builtin_clz(x) : 32; 88d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 89d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 90d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. MoltmannALWAYS_INLINE uint64_t CountLeadingZeroBits64(uint64_t x) { 91d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return LIKELY(x) ? __builtin_clzll(x) : 64; 92d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 93d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 94d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#endif 95d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 96d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#if defined(ARCH_CPU_64_BITS) 97d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 98d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. MoltmannALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) { 99d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return CountLeadingZeroBits64(x); 100d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 101d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 102d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#else 103d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 104d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. MoltmannALWAYS_INLINE size_t CountLeadingZeroBitsSizeT(size_t x) { 105d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann return CountLeadingZeroBits32(x); 106d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} 107d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 108d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#endif 109d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 110d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} // namespace bits 111d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} // namespace base 112d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann} // namespace pdfium 113d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann 114d904c1ec7e8d1d86ed56f0dd252435d12cd345aePhilip P. Moltmann#endif // BASE_BITS_H_ 115