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 unsigned clz64(uint64_t bits) {
 57#if defined(__GNUC__) || __clang__
 58	if (!bits) {
 59		return 64;
 60	}
 61	return __builtin_clzll(bits);
 62#else
 63	static const int table[256] = {
 64		8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
 65		3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 66		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 67		2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 68		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 69		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 70		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 71		1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 72		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 73		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 74		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 75		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 76		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 77		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 78		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 79		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 80	};
 81
 82	if (bits & 0xFF00000000000000) {
 83		return table[bits >> 56];
 84	} else if (bits & 0x00FF000000000000) {
 85		return table[bits >> 48] + 8;
 86	} else if (bits & 0x0000FF0000000000) {
 87		return table[bits >> 40] + 16;
 88	} else if (bits & 0x000000FF00000000) {
 89		return table[bits >> 32] + 24;
 90	} else if (bits & 0x00000000FF000000) {
 91		return table[bits >> 24] + 32;
 92	} else if (bits & 0x0000000000FF0000) {
 93		return table[bits >> 16] + 40;
 94	} else if (bits & 0x000000000000FF00) {
 95		return table[bits >> 8] + 48;
 96	}
 97	return table[bits] + 56;
 98#endif
 99}
100
101static inline uint32_t toPow2(uint32_t bits) {
102	if (!bits) {
103		return 0;
104	}
105	unsigned lz = clz32(bits - 1);
106	return 1 << (32 - lz);
107}
108
109static inline int reduceFraction(int* num, int* den) {
110	int n = *num;
111	int d = *den;
112	while (d != 0) {
113		int temp = n % d;
114		n = d;
115		d = temp;
116	}
117	*num /= n;
118	*den /= n;
119	return n;
120}
121
122CXX_GUARD_END
123
124#endif