1/* Copyright (c) 2007, 2011, Oracle and/or its affiliates.
2 Copyright (c) 2009, 2017, MariaDB Corporation.
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 as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
17#ifndef MY_BIT_INCLUDED
18#define MY_BIT_INCLUDED
19
20/*
21 Some useful bit functions
22*/
23
24C_MODE_START
25
26extern const uchar _my_bits_reverse_table[256];
27
28/*
29 Find smallest X in 2^X >= value
30 This can be used to divide a number with value by doing a shift instead
31*/
32
33static inline uint my_bit_log2(ulong value)
34{
35 uint bit;
36 for (bit=0 ; value > 1 ; value>>=1, bit++) ;
37 return bit;
38}
39
40
41/*
42Count bits in 32bit integer
43
44 Algorithm by Sean Anderson, according to:
45 http://graphics.stanford.edu/~seander/bithacks.html
46 under "Counting bits set, in parallel"
47
48 (Original code public domain).
49*/
50static inline uint my_count_bits_uint32(uint32 v)
51{
52 v = v - ((v >> 1) & 0x55555555);
53 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
54 return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
55}
56
57
58static inline uint my_count_bits(ulonglong x)
59{
60 return my_count_bits_uint32((uint32)x) + my_count_bits_uint32((uint32)(x >> 32));
61}
62
63
64
65
66/*
67 Next highest power of two
68
69 SYNOPSIS
70 my_round_up_to_next_power()
71 v Value to check
72
73 RETURN
74 Next or equal power of 2
75 Note: 0 will return 0
76
77 NOTES
78 Algorithm by Sean Anderson, according to:
79 http://graphics.stanford.edu/~seander/bithacks.html
80 (Original code public domain)
81
82 Comments shows how this works with 01100000000000000000000000001011
83*/
84
85static inline uint32 my_round_up_to_next_power(uint32 v)
86{
87 v--; /* 01100000000000000000000000001010 */
88 v|= v >> 1; /* 01110000000000000000000000001111 */
89 v|= v >> 2; /* 01111100000000000000000000001111 */
90 v|= v >> 4; /* 01111111110000000000000000001111 */
91 v|= v >> 8; /* 01111111111111111100000000001111 */
92 v|= v >> 16; /* 01111111111111111111111111111111 */
93 return v+1; /* 10000000000000000000000000000000 */
94}
95
96static inline uint32 my_clear_highest_bit(uint32 v)
97{
98 uint32 w=v >> 1;
99 w|= w >> 1;
100 w|= w >> 2;
101 w|= w >> 4;
102 w|= w >> 8;
103 w|= w >> 16;
104 return v & w;
105}
106
107static inline uint32 my_reverse_bits(uint32 key)
108{
109 return (uint32)
110 (_my_bits_reverse_table[ key & 255] << 24) |
111 (_my_bits_reverse_table[(key>> 8) & 255] << 16) |
112 (_my_bits_reverse_table[(key>>16) & 255] << 8) |
113 _my_bits_reverse_table[(key>>24) ];
114}
115
116/*
117 a number with the n lowest bits set
118 an overflow-safe version of (1 << n) - 1
119*/
120static inline uint64 my_set_bits(int n)
121{
122 return (((1ULL << (n - 1)) - 1) << 1) | 1;
123}
124
125C_MODE_END
126
127#endif /* MY_BIT_INCLUDED */
128