1/* Copyright (c) 2013-2015 Jeffrey Pfau
 2 *
 3 * This Source Code Form is subject to the terms of the Mozilla Public
 4 * License, v. 2.0. If a copy of the MPL was not distributed with this
 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 6#ifndef UTIL_MATH_H
 7#define UTIL_MATH_H
 8
 9#include "util/common.h"
10
11static inline uint32_t popcount32(unsigned bits) {
12	bits = bits - ((bits >> 1) & 0x55555555);
13	bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
14	return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
15}
16
17static inline unsigned clz32(uint32_t bits) {
18#if defined(__GNUC__) || __clang__
19	return __builtin_clz(bits);
20#else
21	static const int table[256] = {
22		8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
23		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
24		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
25		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
26		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
27		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
28		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
29		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
30		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
31		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
32		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
33		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
34		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
35		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
36		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
37		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
38	};
39
40	if (bits & 0xFF000000) {
41		return table[bits >> 24];
42	} else if (bits & 0x00FF0000) {
43		return table[bits >> 16] + 8;
44	} else if (bits & 0x0000FF00) {
45		return table[bits >> 8] + 16;
46	}
47	return table[bits] + 24;
48#endif
49}
50
51static inline uint32_t toPow2(uint32_t bits) {
52	if (!bits) {
53		return 0;
54	}
55	unsigned lz = clz32(bits - 1);
56	return 1 << (32 - lz);
57}
58
59#endif