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 log2(uint32 v) 45 { 46 static const int MultiplyDeBruijnBitPosition[32] = { 47 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 48 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 49 }; 50 51 v |= v >> 1; 52 v |= v >> 2; 53 v |= v >> 4; 54 v |= v >> 8; 55 v |= v >> 16; 56 57 return MultiplyDeBruijnBitPosition[(uint32)(v * 0x07C4ACDDU) >> 27]; 58 } 59 60 61 template<typename T> 62 void 63 bitmap_shift(T* bits, size_t bitCount, ssize_t shift) 64 { 65 if (shift == 0) 66 return; 67 68 const size_t bitsPerElement = sizeof(T) * 8; 69 const size_t elementsCount = (bitCount + bitsPerElement - 1) / bitsPerElement; 70 const size_t absoluteShift = (shift > 0) ? shift : -shift; 71 const size_t nElements = absoluteShift / bitsPerElement; 72 const size_t nBits = absoluteShift % bitsPerElement; 73 if (nElements != 0) { 74 if (shift > 0) { 75 // "Left" shift. 76 memmove(&bits[nElements], bits, sizeof(T) * (elementsCount - nElements)); 77 memset(bits, 0, sizeof(T) * nElements); 78 } else if (shift < 0) { 79 // "Right" shift. 80 memmove(bits, &bits[nElements], sizeof(T) * (elementsCount - nElements)); 81 memset(&bits[elementsCount - nElements], 0, sizeof(T) * nElements); 82 } 83 } 84 85 // If the shift was by a multiple of the element size, nothing more to do. 86 if (nBits == 0) 87 return; 88 89 // One set of bits comes from the "current" element and are shifted in the 90 // direction of the shift; the other set comes from the next-processed 91 // element and are shifted in the opposite direction. 92 if (shift > 0) { 93 // "Left" shift. 94 for (ssize_t i = elementsCount - 1; i >= 0; i--) { 95 T low = 0; 96 if (i != 0) 97 low = bits[i - 1] >> (bitsPerElement - nBits); 98 const T high = bits[i] << nBits; 99 bits[i] = low | high; 100 } 101 } else if (shift < 0) { 102 // "Right" shift. 103 for (size_t i = 0; i < elementsCount; i++) { 104 const T low = bits[i] >> nBits; 105 T high = 0; 106 if (i != (elementsCount - 1)) 107 high = bits[i + 1] << (bitsPerElement - nBits); 108 bits[i] = low | high; 109 } 110 } 111 } 112 113 114 #endif // KERNEL_UTIL_BITUTIL_H 115 116