Google Git
Sign in
chromium / chromium / src / lkgr / . / base / bits.h
blob: 5f93183d034b7d3b448e5616bfa4fb08a23dddcd [file] [log] [blame]
Avi Drissmane4622aa2022-09-08 20:36:06[diff] [blame]1// Copyright 2013 The Chromium Authors
[email protected]6d1729ee2009-11-18 23:08:39[diff] [blame]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_BITS_H_
8#define BASE_BITS_H_
[email protected]6d1729ee2009-11-18 23:08:39[diff] [blame]9
avi9b6f42932015-12-26 22:15:14[diff] [blame]10#include <stddef.h>
11#include <stdint.h>
12
Avi Drissman6f303a542023-11-17 15:09:58[diff] [blame]13#include <bit>
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]14#include <concepts>
Takuto Ikuta4d4c6852024-12-09 11:16:02[diff] [blame]15#include <type_traits>
Lei Zhangd93f7ed2018-09-28 13:40:03[diff] [blame]16
Hans Wennborg7b533712020-06-22 20:52:27[diff] [blame]17#include "base/check.h"
[email protected]6d1729ee2009-11-18 23:08:39[diff] [blame]18
Avi Drissman6f303a542023-11-17 15:09:58[diff] [blame]19namespace base::bits {
[email protected]6d1729ee2009-11-18 23:08:39[diff] [blame]20
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]21// Bit functions in <bit> are restricted to a specific set of types of unsigned
22// integer; restrict functions in this file that are related to those in that
23// header to match for consistency.
24template <typename T>
25concept UnsignedInteger =
26 std::unsigned_integral<T> && !std::same_as<T, bool> &&
27 !std::same_as<T, char> && !std::same_as<T, char8_t> &&
28 !std::same_as<T, char16_t> && !std::same_as<T, char32_t> &&
29 !std::same_as<T, wchar_t>;
30
31// We want to migrate all users of these functions to use the unsigned type
32// versions of the functions, but until they are all moved over, create a
33// concept that captures all the types that must be supported for compatibility
34// but that we want to remove.
Avi Drissmanc73aa5d22023-12-07 17:24:22[diff] [blame]35//
Alison Galed965ba02024-04-26 21:50:54[diff] [blame]36// TODO(crbug.com/40256225): Switch uses to supported functions and
Avi Drissmanc73aa5d22023-12-07 17:24:22[diff] [blame]37// remove.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]38template <typename T>
39concept SignedIntegerDeprecatedDoNotUse =
40 std::integral<T> && !UnsignedInteger<T>;
41
Lei Zhang0c010262018-12-11 18:56:09[diff] [blame]42// Round down |size| to a multiple of alignment, which must be a power of two.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]43template <typename T>
44 requires UnsignedInteger<T>
45inline constexpr T AlignDown(T size, T alignment) {
Avi Drissmanc73aa5d22023-12-07 17:24:22[diff] [blame]46 DCHECK(std::has_single_bit(alignment));
Lei Zhang0c010262018-12-11 18:56:09[diff] [blame]47 return size & ~(alignment - 1);
48}
49
Avi Drissmanc73aa5d22023-12-07 17:24:22[diff] [blame]50// Round down |size| to a multiple of alignment, which must be a power of two.
51// DEPRECATED; use the UnsignedInteger version.
52//
Alison Galed965ba02024-04-26 21:50:54[diff] [blame]53// TODO(crbug.com/40256225): Switch uses and remove.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]54template <typename T>
Alex Attar764f7462024-12-05 14:46:15[diff] [blame]55inline constexpr auto AlignDownDeprecatedDoNotUse(T size, T alignment) {
56 using U = std::make_unsigned_t<T>;
57 DCHECK(std::has_single_bit(static_cast<U>(alignment)));
58 return static_cast<U>(size) & ~static_cast<U>(alignment - 1);
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]59}
60
Mike Wittman668debf82020-07-28 03:10:30[diff] [blame]61// Move |ptr| back to the previous multiple of alignment, which must be a power
62// of two. Defined for types where sizeof(T) is one byte.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]63template <typename T>
64 requires(sizeof(T) == 1)
Peter Kasting6a4bf14c2022-07-13 14:53:33[diff] [blame]65inline T* AlignDown(T* ptr, uintptr_t alignment) {
Mike Wittman668debf82020-07-28 03:10:30[diff] [blame]66 return reinterpret_cast<T*>(
Peter Kasting6a4bf14c2022-07-13 14:53:33[diff] [blame]67 AlignDown(reinterpret_cast<uintptr_t>(ptr), alignment));
Mike Wittman668debf82020-07-28 03:10:30[diff] [blame]68}
69
Benoit Lizec90419f62021-02-02 18:04:25[diff] [blame]70// Round up |size| to a multiple of alignment, which must be a power of two.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]71template <typename T>
72 requires UnsignedInteger<T>
73inline constexpr T AlignUp(T size, T alignment) {
Avi Drissmanc73aa5d22023-12-07 17:24:22[diff] [blame]74 DCHECK(std::has_single_bit(alignment));
Benoit Lizec90419f62021-02-02 18:04:25[diff] [blame]75 return (size + alignment - 1) & ~(alignment - 1);
76}
77
Avi Drissmanc73aa5d22023-12-07 17:24:22[diff] [blame]78// Round up |size| to a multiple of alignment, which must be a power of two.
79// DEPRECATED; use the UnsignedInteger version.
80//
Alison Galed965ba02024-04-26 21:50:54[diff] [blame]81// TODO(crbug.com/40256225): Switch uses and remove.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]82template <typename T>
83 requires SignedIntegerDeprecatedDoNotUse<T>
84inline constexpr T AlignUpDeprecatedDoNotUse(T size, T alignment) {
Alex Attar764f7462024-12-05 14:46:15[diff] [blame]85 using U = std::make_unsigned_t<T>;
86 DCHECK(std::has_single_bit(static_cast<U>(alignment)));
87 return static_cast<U>(size + alignment - 1) & ~static_cast<U>(alignment - 1);
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]88}
89
Benoit Lizec90419f62021-02-02 18:04:25[diff] [blame]90// Advance |ptr| to the next multiple of alignment, which must be a power of
91// two. Defined for types where sizeof(T) is one byte.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]92template <typename T>
93 requires(sizeof(T) == 1)
Peter Kasting6a4bf14c2022-07-13 14:53:33[diff] [blame]94inline T* AlignUp(T* ptr, uintptr_t alignment) {
Benoit Lizec90419f62021-02-02 18:04:25[diff] [blame]95 return reinterpret_cast<T*>(
Peter Kasting6a4bf14c2022-07-13 14:53:33[diff] [blame]96 AlignUp(reinterpret_cast<uintptr_t>(ptr), alignment));
Benoit Lizec90419f62021-02-02 18:04:25[diff] [blame]97}
98
Avi Drissmanf2905bf62021-11-17 19:16:23[diff] [blame]99// Returns the integer i such as 2^i <= n < 2^(i+1).
100//
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]101// A common use for this function is to measure the number of bits required to
102// contain a value; for that case use std::bit_width().
Peter Kasting64c67dd2022-05-12 18:11:51[diff] [blame]103//
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]104// A common use for this function is to take its result and use it to left-shift
105// a bit; instead of doing so, use std::bit_floor().
Anton Bikineeve033cdf2020-11-26 03:40:40[diff] [blame]106constexpr int Log2Floor(uint32_t n) {
Avi Drissman6f303a542023-11-17 15:09:58[diff] [blame]107 return 31 - std::countl_zero(n);
Brian Anderson6aab84c2018-03-14 00:43:31[diff] [blame]108}
109
Avi Drissmanf2905bf62021-11-17 19:16:23[diff] [blame]110// Returns the integer i such as 2^(i-1) < n <= 2^i.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]111//
112// A common use for this function is to measure the number of bits required to
113// contain a value; for that case use std::bit_width().
114//
115// A common use for this function is to take its result and use it to left-shift
116// a bit; instead of doing so, use std::bit_ceil().
Anton Bikineeve033cdf2020-11-26 03:40:40[diff] [blame]117constexpr int Log2Ceiling(uint32_t n) {
Brian Anderson6aab84c2018-03-14 00:43:31[diff] [blame]118 // When n == 0, we want the function to return -1.
119 // When n == 0, (n - 1) will underflow to 0xFFFFFFFF, which is
120 // why the statement below starts with (n ? 32 : -1).
Avi Drissman6f303a542023-11-17 15:09:58[diff] [blame]121 return (n ? 32 : -1) - std::countl_zero(n - 1);
Brian Anderson6aab84c2018-03-14 00:43:31[diff] [blame]122}
123
OlivierLi02b94c52020-05-29 21:30:56[diff] [blame]124// Returns a value of type T with a single bit set in the left-most position.
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]125// Can be used instead of manually shifting a 1 to the left. Unlike the other
126// functions in this file, usable for any integral type.
OlivierLi02b94c52020-05-29 21:30:56[diff] [blame]127template <typename T>
Avi Drissmandb766e52023-11-28 22:40:29[diff] [blame]128 requires std::integral<T>
OlivierLi02b94c52020-05-29 21:30:56[diff] [blame]129constexpr T LeftmostBit() {
OlivierLi02b94c52020-05-29 21:30:56[diff] [blame]130 T one(1u);
Lei Zhangce16fc02023-06-27 17:11:29[diff] [blame]131 return one << (8 * sizeof(T) - 1);
OlivierLi02b94c52020-05-29 21:30:56[diff] [blame]132}
133
Avi Drissman6f303a542023-11-17 15:09:58[diff] [blame]134} // namespace base::bits
[email protected]6d1729ee2009-11-18 23:08:39[diff] [blame]135
136#endif // BASE_BITS_H_