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