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
18static inline uint32
19next_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
34static inline uint32
35count_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
43static inline uint32
44log2(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
61template<typename T>
62void
63bitmap_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