a series of fast, integer-based logarithms

int_log.inc

#if defined _int_log_included
	#endinput
#endif
#define _int_log_included

#include <sourcemod>


stock int BitScanReverse(int n) {
	int bit_index = 0;
	for( int i = n >>> 1; i > 0; i >>>= 1 ) {
		bit_index++;
	}
	return bit_index;
	//CountLeadingZeroes(n) ^ 31;
}
stock int CountLeadingZeroes(int n) {
	if( n==0 ) {
		return 32;
	}
	//return BitScanReverse(n) ^ 31;
	int count = 0;
	while( !(n & (1 << (31-count))) ) {
		count++;
	}
	return count;
}
stock int BitwiseCeil(int x) {
	x |= x >>> 1;
	x |= x >>> 2;
	x |= x >>> 4;
	x |= x >>> 8;
	x |= x >>> 16;
	return x;
}

/// Credit to Eric Cole.
/// uses a De Bruijn sequence as well as a bitwise rounding algorithm.
/// better explanation here:
/// https://cstheory.stackexchange.com/questions/19524/using-the-de-bruijn-sequence-to-find-the-lceil-log-2-v-rceil-of-an-integer
stock int IntLog2(int x) {
	static int de_bruijn_tab[] = {
		 0,  9,  1, 10, 13, 21,  2, 29,
		11, 14, 16, 18, 22, 25,  3, 30,
		 8, 12, 20, 28, 15, 17, 24,  7,
		19, 27, 23,  6, 26,  5,  4, 31
	};
	enum { DeBruijnLog2Magic = 0x07C4ACDD };
	return de_bruijn_tab[(BitwiseCeil(x) * DeBruijnLog2Magic) >>> 27];
}

/**
/// where log10_tab[i] = logN(exp(2, i)) = logN(1 << i) = logA(1 << i) / logA(N)
stock int log10(int x) {
	const int log10_tab[32] = {
		0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
		3, 3, 3, 3, 4, 4, 4, 5, 5, 5,
		6, 6, 6, 6, 7, 7, 7, 8, 8, 8,
		9, 9
	};
	const int powers_of_10[] = {
		1, 10, 100, 1000, 10000, 100000, 1000000,
		10000000, 100000000, 1000000000, 0
	};
	int y = log10_tab[ IntLog2(x) ];
	return y + (x >= powers_of_10[y + 1]);
}
*/

/// https://lemire.me/blog/2021/05/28/computing-the-number-of-digits-of-an-integer-quickly/
/// log10(x) = log2(x) / log2(10)
stock int IntLog10(int x) {
	if( x < 0 ) {
		return -1;
	}
	static int log10_tab[] = {
		9,      99,      999, 9999, 99999,
		999999, 9999999, 99999999, 999999999
	};
	int y = (9 * IntLog2(x)) >> 5;
	y += view_as< int >(x > log10_tab[y]);
	return y;
}

stock int IntLog(int x, const int[] logN_table, const int[] powers_of_N) {
	int y = logN_table[ IntLog2(x) ];
	return y + view_as< int >(x >= powers_of_N[y + 1]);
}

enum {
	MAX_LOG_TABLE_SIZE = 32,
	MAX_LOG_POWER_SIZE = 21,
};
stock int InitIntLogarithmTables(int logN_table[MAX_LOG_TABLE_SIZE], int powers[MAX_LOG_POWER_SIZE], int base=10) {
	if( base < 3 ) {
		return 0;
	}
	/// Generate our powers of the base.
	powers[0] = 1;
	int n = 1;
	for( int i=1; i < sizeof(powers); i++ ) {
		int prev_pow = powers[i-1];
		int next_pow = prev_pow * base;
		if( IntLog2(next_pow) <= IntLog2(prev_pow) ) {
			break;
		}
		powers[i] = next_pow;
		n++;
	}
	
	/// generate guesses table.
	float fbase = base + 0.0;
	for( int i; i < sizeof(logN_table); i++ ) {
		int r = 1 << i;
		float fr = float(r);
		if( fr < 0 ) {
			fr = -fr;
		}
		logN_table[i] = RoundToFloor(Logarithm(fr, fbase));
	}
	return n;
}