1 /*
2 * Copyright 2013 Haiku, Inc. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 * Paweł Dziepak, pdziepak@quarnos.org
7 */
8 #ifndef KERNEL_UTIL_BITUTIL_H
9 #define KERNEL_UTIL_BITUTIL_H
10
11
12 #include <string.h>
13
14 #include <SupportDefs.h>
15
16
17 // http://graphics.stanford.edu/~seander/bithacks.html
18 static inline uint32
next_power_of_2(uint32 v)19 next_power_of_2(uint32 v)
20 {
21 v--;
22 v |= v >> 1;
23 v |= v >> 2;
24 v |= v >> 4;
25 v |= v >> 8;
26 v |= v >> 16;
27 v++;
28
29 return v;
30 }
31
32
33 // http://graphics.stanford.edu/~seander/bithacks.html
34 static inline uint32
count_set_bits(uint32 v)35 count_set_bits(uint32 v)
36 {
37 v = v - ((v >> 1) & 0x55555555);
38 v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
39 return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
40 }
41
42
43 static inline uint32
fls(uint32 value)44 fls(uint32 value)
45 {
46 if (value == 0)
47 return 0;
48
49 #if __has_builtin(__builtin_clz)
50 return ((sizeof(value) * 8) - __builtin_clz(value));
51 #else
52 // https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
53 static const uint32 masks[] = {
54 0xaaaaaaaa,
55 0xcccccccc,
56 0xf0f0f0f0,
57 0xff00ff00,
58 0xffff0000
59 };
60 uint32 result = (value & masks[0]) != 0;
61 for (int i = 4; i > 0; i--)
62 result |= ((value & masks[i]) != 0) << i;
63 return result + 1;
64 #endif
65 }
66
67
68 static inline uint32
log2(uint32 v)69 log2(uint32 v)
70 {
71 static const int MultiplyDeBruijnBitPosition[32] = {
72 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
73 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
74 };
75
76 v |= v >> 1;
77 v |= v >> 2;
78 v |= v >> 4;
79 v |= v >> 8;
80 v |= v >> 16;
81
82 return MultiplyDeBruijnBitPosition[(uint32)(v * 0x07C4ACDDU) >> 27];
83 }
84
85
86 template<typename T>
87 void
bitmap_shift(T * bits,size_t bitCount,ssize_t shift)88 bitmap_shift(T* bits, size_t bitCount, ssize_t shift)
89 {
90 if (shift == 0)
91 return;
92
93 const size_t bitsPerElement = sizeof(T) * 8;
94 const size_t elementsCount = (bitCount + bitsPerElement - 1) / bitsPerElement;
95 const size_t absoluteShift = (shift > 0) ? shift : -shift;
96 const size_t nElements = absoluteShift / bitsPerElement;
97 const size_t nBits = absoluteShift % bitsPerElement;
98 if (nElements != 0) {
99 if (shift > 0) {
100 // "Left" shift.
101 memmove(&bits[nElements], bits, sizeof(T) * (elementsCount - nElements));
102 memset(bits, 0, sizeof(T) * nElements);
103 } else if (shift < 0) {
104 // "Right" shift.
105 memmove(bits, &bits[nElements], sizeof(T) * (elementsCount - nElements));
106 memset(&bits[elementsCount - nElements], 0, sizeof(T) * nElements);
107 }
108 }
109
110 // If the shift was by a multiple of the element size, nothing more to do.
111 if (nBits == 0)
112 return;
113
114 // One set of bits comes from the "current" element and are shifted in the
115 // direction of the shift; the other set comes from the next-processed
116 // element and are shifted in the opposite direction.
117 if (shift > 0) {
118 // "Left" shift.
119 for (ssize_t i = elementsCount - 1; i >= 0; i--) {
120 T low = 0;
121 if (i != 0)
122 low = bits[i - 1] >> (bitsPerElement - nBits);
123 const T high = bits[i] << nBits;
124 bits[i] = low | high;
125 }
126 } else if (shift < 0) {
127 // "Right" shift.
128 for (size_t i = 0; i < elementsCount; i++) {
129 const T low = bits[i] >> nBits;
130 T high = 0;
131 if (i != (elementsCount - 1))
132 high = bits[i + 1] << (bitsPerElement - nBits);
133 bits[i] = low | high;
134 }
135 }
136 }
137
138
139 #endif // KERNEL_UTIL_BITUTIL_H
140
141