1 /*
2 Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved.
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
24 C_MODE_START
25
26 extern const char _my_bits_nbits[256];
27 extern const uchar _my_bits_reverse_table[256];
28
29 /*
30 Find smallest X in 2^X >= value
31 This can be used to divide a number with value by doing a shift instead
32 */
33
my_bit_log2(ulong value)34 static inline uint my_bit_log2(ulong value)
35 {
36 uint bit;
37 for (bit=0 ; value > 1 ; value>>=1, bit++) ;
38 return bit;
39 }
40
my_count_bits(ulonglong v)41 static inline uint my_count_bits(ulonglong v)
42 {
43 #if SIZEOF_LONG_LONG > 4
44 /* The following code is a bit faster on 16 bit machines than if we would
45 only shift v */
46 ulong v2=(ulong) (v >> 32);
47 return (uint) (uchar) (_my_bits_nbits[(uchar) v] +
48 _my_bits_nbits[(uchar) (v >> 8)] +
49 _my_bits_nbits[(uchar) (v >> 16)] +
50 _my_bits_nbits[(uchar) (v >> 24)] +
51 _my_bits_nbits[(uchar) (v2)] +
52 _my_bits_nbits[(uchar) (v2 >> 8)] +
53 _my_bits_nbits[(uchar) (v2 >> 16)] +
54 _my_bits_nbits[(uchar) (v2 >> 24)]);
55 #else
56 return (uint) (uchar) (_my_bits_nbits[(uchar) v] +
57 _my_bits_nbits[(uchar) (v >> 8)] +
58 _my_bits_nbits[(uchar) (v >> 16)] +
59 _my_bits_nbits[(uchar) (v >> 24)]);
60 #endif
61 }
62
my_count_bits_uint32(uint32 v)63 static inline uint my_count_bits_uint32(uint32 v)
64 {
65 return (uint) (uchar) (_my_bits_nbits[(uchar) v] +
66 _my_bits_nbits[(uchar) (v >> 8)] +
67 _my_bits_nbits[(uchar) (v >> 16)] +
68 _my_bits_nbits[(uchar) (v >> 24)]);
69 }
70
71
72 /*
73 Next highest power of two
74
75 SYNOPSIS
76 my_round_up_to_next_power()
77 v Value to check
78
79 RETURN
80 Next or equal power of 2
81 Note: 0 will return 0
82
83 NOTES
84 Algorithm by Sean Anderson, according to:
85 http://graphics.stanford.edu/~seander/bithacks.html
86 (Orignal code public domain)
87
88 Comments shows how this works with 01100000000000000000000000001011
89 */
90
my_round_up_to_next_power(uint32 v)91 static inline uint32 my_round_up_to_next_power(uint32 v)
92 {
93 v--; /* 01100000000000000000000000001010 */
94 v|= v >> 1; /* 01110000000000000000000000001111 */
95 v|= v >> 2; /* 01111100000000000000000000001111 */
96 v|= v >> 4; /* 01111111110000000000000000001111 */
97 v|= v >> 8; /* 01111111111111111100000000001111 */
98 v|= v >> 16; /* 01111111111111111111111111111111 */
99 return v+1; /* 10000000000000000000000000000000 */
100 }
101
my_clear_highest_bit(uint32 v)102 static inline uint32 my_clear_highest_bit(uint32 v)
103 {
104 uint32 w=v >> 1;
105 w|= w >> 1;
106 w|= w >> 2;
107 w|= w >> 4;
108 w|= w >> 8;
109 w|= w >> 16;
110 return v & w;
111 }
112
my_reverse_bits(uint32 key)113 static inline uint32 my_reverse_bits(uint32 key)
114 {
115 return
116 (_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) |
119 _my_bits_reverse_table[(key>>24) ];
120 }
121
122 C_MODE_END
123
124 #endif /* MY_BIT_INCLUDED */
125