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 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 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 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 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 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