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 <mgba-util/common.h>
10
11CXX_GUARD_START
12
13static inline uint32_t popcount32(unsigned bits) {
14	bits = bits - ((bits >> 1) & 0x55555555);
15	bits = (bits & 0x33333333) + ((bits >> 2) & 0x33333333);
16	return (((bits + (bits >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
17}
18
19static inline unsigned clz32(uint32_t bits) {
20#if defined(__GNUC__) || __clang__
21	if (!bits) {
22		return 32;
23	}
24	return __builtin_clz(bits);
25#else
26	static const int table[256] = {
27		8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
28		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
29		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
30		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
31		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
32		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
33		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
34		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
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		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
39		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
40		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
41		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
42		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
43	};
44
45	if (bits & 0xFF000000) {
46		return table[bits >> 24];
47	} else if (bits & 0x00FF0000) {
48		return table[bits >> 16] + 8;
49	} else if (bits & 0x0000FF00) {
50		return table[bits >> 8] + 16;
51	}
52	return table[bits] + 24;
53#endif
54}
55
56static inline uint32_t toPow2(uint32_t bits) {
57	if (!bits) {
58		return 0;
59	}
60	unsigned lz = clz32(bits - 1);
61	return 1 << (32 - lz);
62}
63
64static inline int reduceFraction(int* num, int* den) {
65	int n = *num;
66	int d = *den;
67	while (d != 0) {
68		int temp = n % d;
69		n = d;
70		d = temp;
71	}
72	*num /= n;
73	*den /= n;
74	return n;
75}
76
77CXX_GUARD_END
78
79#endif