MySQL 8.2.0
Source Code Documentation
my_bit.h
Go to the documentation of this file.
1/*
2 Copyright (c) 2007, 2023, Oracle and/or its affiliates.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License, version 2.0,
6 as published by the Free Software Foundation.
7
8 This program is also distributed with certain software (including
9 but not limited to OpenSSL) that is licensed under separate terms,
10 as designated in a particular file or component or in included license
11 documentation. The authors of MySQL hereby grant you an additional
12 permission to link the program and your derivative works with the
13 separately licensed software that they have included with MySQL.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef MY_BIT_INCLUDED
25#define MY_BIT_INCLUDED
26
27/**
28 @file include/my_bit.h
29 Some useful bit functions.
30*/
31
32#include <sys/types.h>
33
34#include "my_config.h"
35#include "my_inttypes.h"
36#include "my_macros.h"
37
38extern const char _my_bits_nbits[256];
39extern const uchar _my_bits_reverse_table[256];
40
41/*
42 Find smallest X in 2^X >= value
43 This can be used to divide a number with value by doing a shift instead
44*/
45
46static inline uint my_bit_log2(ulong value) {
47 uint bit;
48 for (bit = 0; value > 1; value >>= 1, bit++)
49 ;
50 return bit;
51}
52
53static inline uint my_count_bits(ulonglong v) {
54#if SIZEOF_LONG_LONG > 4
55 /* The following code is a bit faster on 16 bit machines than if we would
56 only shift v */
57 const ulong v2 = (ulong)(v >> 32);
58 return (uint)(uchar)(
59 _my_bits_nbits[(uchar)v] + _my_bits_nbits[(uchar)(v >> 8)] +
60 _my_bits_nbits[(uchar)(v >> 16)] + _my_bits_nbits[(uchar)(v >> 24)] +
61 _my_bits_nbits[(uchar)(v2)] + _my_bits_nbits[(uchar)(v2 >> 8)] +
62 _my_bits_nbits[(uchar)(v2 >> 16)] + _my_bits_nbits[(uchar)(v2 >> 24)]);
63#else
64 return (uint)(uchar)(
65 _my_bits_nbits[(uchar)v] + _my_bits_nbits[(uchar)(v >> 8)] +
66 _my_bits_nbits[(uchar)(v >> 16)] + _my_bits_nbits[(uchar)(v >> 24)]);
67#endif
68}
69
70static inline uint my_count_bits_uint32(uint32 v) {
71 return (uint)(uchar)(
72 _my_bits_nbits[(uchar)v] + _my_bits_nbits[(uchar)(v >> 8)] +
73 _my_bits_nbits[(uchar)(v >> 16)] + _my_bits_nbits[(uchar)(v >> 24)]);
74}
75
76/*
77 Next highest power of two
78
79 SYNOPSIS
80 my_round_up_to_next_power()
81 v Value to check
82
83 RETURN
84 Next or equal power of 2
85 Note: 0 will return 0
86
87 NOTES
88 Algorithm by Sean Anderson, according to:
89 http://graphics.stanford.edu/~seander/bithacks.html
90 (Original code public domain)
91
92 Comments shows how this works with 01100000000000000000000000001011
93*/
94
96 v--; /* 01100000000000000000000000001010 */
97 v |= v >> 1; /* 01110000000000000000000000001111 */
98 v |= v >> 2; /* 01111100000000000000000000001111 */
99 v |= v >> 4; /* 01111111110000000000000000001111 */
100 v |= v >> 8; /* 01111111111111111100000000001111 */
101 v |= v >> 16; /* 01111111111111111111111111111111 */
102 return v + 1; /* 10000000000000000000000000000000 */
103}
104
106 uint32 w = v >> 1;
107 w |= w >> 1;
108 w |= w >> 2;
109 w |= w >> 4;
110 w |= w >> 8;
111 w |= w >> 16;
112 return v & w;
113}
114
116 return (_my_bits_reverse_table[key & 255] << 24) |
117 (_my_bits_reverse_table[(key >> 8) & 255] << 16) |
118 (_my_bits_reverse_table[(key >> 16) & 255] << 8) |
120}
121
122/**
123 Determine if a single bit is set among some bits.
124 @tparam IntType an integer type
125 @param bits the bits to examine
126 @retval true if bits equals to a power of 2
127 @retval false otherwise
128*/
129
130template <typename IntType>
131constexpr bool is_single_bit(IntType bits) {
132 /*
133 Proof of correctness:
134 (1) is_single_bit(0)==false is left as an exercise to the reader.
135 (2) is_single_bit(1)==true is left as an exercise to the reader.
136 (3) is_single_bit(1<<(N+1))==true because the most significant set bit
137 in (bits - 1) would be 1<<N, and obviously (bits & (bits - 1)) == 0.
138 (4) In all other cases, is_single_bit(bits)==false.
139 In these cases, we must have multiple bits set, that is,
140 bits==m|1<<N such that N>=0 and m!=0 and the least significant
141 bit that is set in m is greater than 1<<N. In this case,
142 (bits-1)==m|((1<<N)-1), and (bits&(bits-1))==m, which we defined to be
143 nonzero. So, m==0 will not hold.
144
145 Note: The above proof (3),(4) is applicable also to the case where
146 IntType is signed using two's complement arithmetic, and the most
147 significant bit is set, or in other words, bits<0.
148 */
149 return bits != 0 && (bits & (bits - 1)) == 0;
150}
151
152#endif /* MY_BIT_INCLUDED */
static uint32 my_round_up_to_next_power(uint32 v)
Definition: my_bit.h:95
static uint my_bit_log2(ulong value)
Definition: my_bit.h:46
static uint my_count_bits(ulonglong v)
Definition: my_bit.h:53
static uint32 my_reverse_bits(uint32 key)
Definition: my_bit.h:115
const uchar _my_bits_reverse_table[256]
Definition: my_bit.cc:51
static uint my_count_bits_uint32(uint32 v)
Definition: my_bit.h:70
const char _my_bits_nbits[256]
Definition: my_bit.cc:34
constexpr bool is_single_bit(IntType bits)
Determine if a single bit is set among some bits.
Definition: my_bit.h:131
static uint32 my_clear_highest_bit(uint32 v)
Definition: my_bit.h:105
Some integer typedefs for easier portability.
unsigned long long int ulonglong
Definition: my_inttypes.h:55
unsigned char uchar
Definition: my_inttypes.h:51
uint32_t uint32
Definition: my_inttypes.h:66
Some common macros.
required string key
Definition: replication_asynchronous_connection_failover.proto:59