stego.git

/* stego - chess engine
 * Copyright (C) 2025 ArcNyxx <me@arcnyxx.net>
 * see LICENCE file for licensing information */

#include <assert.h>

#include "bits.h"
#include "stego.h"

#ifndef __GNUC__
static const int forward[64] = {
	0,  1,  48, 2,  57, 49, 28, 3,
	61, 58, 50, 42, 38, 29, 17, 4,
	62, 55, 59, 36, 53, 51, 43, 22,
	45, 39, 33, 30, 24, 18, 12, 5,
	63, 47, 56, 27, 60, 41, 37, 16,
	54, 35, 52, 21, 44, 32, 23, 11,
	46, 26, 40, 15, 34, 20, 31, 10,
	25, 14, 19, 9,  13, 8,  7,  6
};
static const int reverse[64] = {
	0,  47, 1,  56, 48, 27, 2,  60,
	57, 49, 41, 37, 28, 16, 3,  61,
	54, 58, 35, 52, 50, 42, 21, 44,
	38, 32, 29, 23, 17, 11, 4,  62,
	46, 55, 26, 59, 40, 36, 15, 53,
	34, 51, 20, 43, 31, 22, 10, 45,
	25, 39, 14, 33, 19, 30, 9,  24,
	13, 18,  8, 12, 7,  6,  5,  63
};
static const u64 debruijn64 = 0x03f79d71b4cb0a89;
#endif /* __GNUC__ */

int
lsb(u64 bb)
{
	assert(bb != 0);
#ifdef __GNUC__
	return __builtin_ctzg(bb);
#else /* __GNUC__ */
	return forward[((bb ^ (bb - 1)) * debruijn64) >> 58];
#endif /* __GNUC__ */
}

int
msb(u64 bb)
{
	assert(bb != 0);
#ifdef __GNUC__
	return 63 - __builtin_clzg(bb);
#else /* __GNUC__ */
	bb |= bb >> 1; 
	bb |= bb >> 2;
	bb |= bb >> 4;
	bb |= bb >> 8;
	bb |= bb >> 16;
	bb |= bb >> 32;
	return reverse[(bb * debruijn64) >> 58];
#endif /* __GNUC__ */
}

int
popcount(u64 bb)
{
#ifdef __GNUC__
	return __builtin_popcountg(bb);
#else /* __GNUC__ */
	/* there are much faster ways to do this with only c operations */
	int ret;
	for (ret = 0; bb != 0; bb >>= 1)
		ret += bb & 1;
	return ret;
#endif /* __GNUC__ */
}