1 // Copyright 2013 The Chromium Authors
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
7 #ifndef BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_PARTITION_ALLOC_BASE_BITS_H_
8 #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_PARTITION_ALLOC_BASE_BITS_H_
9
10 #include <stddef.h>
11 #include <stdint.h>
12
13 #include <bit>
14 #include <concepts>
15
16 #include "partition_alloc/partition_alloc_base/check.h"
17
18 namespace partition_alloc::internal::base::bits {
19
20 // Bit functions in <bit> are restricted to a specific set of types of unsigned
21 // integer; restrict functions in this file that are related to those in that
22 // header to match for consistency.
23 template <typename T>
24 concept UnsignedInteger =
25 std::unsigned_integral<T> && !std::same_as<T, bool> &&
26 !std::same_as<T, char> && !std::same_as<T, char8_t> &&
27 !std::same_as<T, char16_t> && !std::same_as<T, char32_t> &&
28 !std::same_as<T, wchar_t>;
29
30 // Round down |size| to a multiple of alignment, which must be a power of two.
31 template <typename T>
32 requires UnsignedInteger<T>
AlignDown(T size,T alignment)33 inline constexpr T AlignDown(T size, T alignment) {
34 PA_BASE_DCHECK(std::has_single_bit(alignment));
35 return size & ~(alignment - 1);
36 }
37
38 // Move |ptr| back to the previous multiple of alignment, which must be a power
39 // of two. Defined for types where sizeof(T) is one byte.
40 template <typename T>
41 requires(sizeof(T) == 1)
AlignDown(T * ptr,size_t alignment)42 inline T* AlignDown(T* ptr, size_t alignment) {
43 return reinterpret_cast<T*>(
44 AlignDown(reinterpret_cast<uintptr_t>(ptr), alignment));
45 }
46
47 // Round up |size| to a multiple of alignment, which must be a power of two.
48 template <typename T>
49 requires UnsignedInteger<T>
AlignUp(T size,T alignment)50 inline constexpr T AlignUp(T size, T alignment) {
51 PA_BASE_DCHECK(std::has_single_bit(alignment));
52 return (size + alignment - 1) & ~(alignment - 1);
53 }
54
55 // Advance |ptr| to the next multiple of alignment, which must be a power of
56 // two. Defined for types where sizeof(T) is one byte.
57 template <typename T>
58 requires(sizeof(T) == 1)
AlignUp(T * ptr,size_t alignment)59 inline T* AlignUp(T* ptr, size_t alignment) {
60 return reinterpret_cast<T*>(
61 AlignUp(reinterpret_cast<size_t>(ptr), alignment));
62 }
63
64 // Returns the integer i such as 2^i <= n < 2^(i+1).
65 //
66 // A common use for this function is to measure the number of bits required to
67 // contain a value; for that case use std::bit_width().
68 //
69 // A common use for this function is to take its result and use it to left-shift
70 // a bit; instead of doing so, use std::bit_floor().
Log2Floor(uint32_t n)71 constexpr int Log2Floor(uint32_t n) {
72 return 31 - std::countl_zero(n);
73 }
74
75 // Returns the integer i such as 2^(i-1) < n <= 2^i.
76 //
77 // A common use for this function is to measure the number of bits required to
78 // contain a value; for that case use std::bit_width().
79 //
80 // A common use for this function is to take its result and use it to left-shift
81 // a bit; instead of doing so, use std::bit_ceil().
Log2Ceiling(uint32_t n)82 constexpr int Log2Ceiling(uint32_t n) {
83 // When n == 0, we want the function to return -1.
84 // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is
85 // why the statement below starts with (n ? 32 : -1).
86 return (n ? 32 : -1) - std::countl_zero(n - 1);
87 }
88
89 // Returns a value of type T with a single bit set in the left-most position.
90 // Can be used instead of manually shifting a 1 to the left. Unlike the other
91 // functions in this file, usable for any integral type.
92 template <typename T>
93 requires std::integral<T>
LeftmostBit()94 constexpr T LeftmostBit() {
95 T one(1u);
96 return one << (8 * sizeof(T) - 1);
97 }
98
99 } // namespace partition_alloc::internal::base::bits
100
101 #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_SRC_PARTITION_ALLOC_PARTITION_ALLOC_BASE_BITS_H_
102