skidd13@7971: /* $Id$ */
skidd13@7971: 
rubidium@9111: /** @file bitmath_func.cpp Functions related to bit mathematics. */
skidd13@7971: 
skidd13@7971: #include "../stdafx.h"
skidd13@7971: #include "bitmath_func.hpp"
skidd13@7971: 
skidd13@7971: const uint8 _ffb_64[64] = {
skidd13@7971:  0,  0,  1,  0,  2,  0,  1,  0,
skidd13@7971:  3,  0,  1,  0,  2,  0,  1,  0,
skidd13@7971:  4,  0,  1,  0,  2,  0,  1,  0,
skidd13@7971:  3,  0,  1,  0,  2,  0,  1,  0,
skidd13@7971:  5,  0,  1,  0,  2,  0,  1,  0,
skidd13@7971:  3,  0,  1,  0,  2,  0,  1,  0,
skidd13@7971:  4,  0,  1,  0,  2,  0,  1,  0,
skidd13@7971:  3,  0,  1,  0,  2,  0,  1,  0,
skidd13@7971: };
skidd13@7971: 
skidd13@7971: /**
skidd13@7971:  * Search the first set bit in a 32 bit variable.
skidd13@7971:  *
skidd13@7971:  * This algorithm is a static implementation of a log
skidd13@7971:  * conguence search algorithm. It checks the first half
skidd13@7971:  * if there is a bit set search there further. And this
skidd13@7971:  * way further. If no bit is set return 0.
skidd13@7971:  *
skidd13@7971:  * @param x The value to search
rubidium@8000:  * @return The position of the first bit set
skidd13@7971:  */
skidd13@7971: uint8 FindFirstBit(uint32 x)
skidd13@7971: {
skidd13@7971: 	if (x == 0) return 0;
skidd13@7971: 	/* The macro FIND_FIRST_BIT is better to use when your x is
skidd13@7971: 	  not more than 128. */
skidd13@7971: 
skidd13@7971: 	uint8 pos = 0;
skidd13@7971: 
skidd13@7971: 	if ((x & 0x0000ffff) == 0) { x >>= 16; pos += 16; }
skidd13@7971: 	if ((x & 0x000000ff) == 0) { x >>= 8;  pos += 8;  }
skidd13@7971: 	if ((x & 0x0000000f) == 0) { x >>= 4;  pos += 4;  }
skidd13@7971: 	if ((x & 0x00000003) == 0) { x >>= 2;  pos += 2;  }
skidd13@7971: 	if ((x & 0x00000001) == 0) { pos += 1; }
skidd13@7971: 
skidd13@7971: 	return pos;
skidd13@7971: }
rubidium@8000: 
rubidium@8000: /**
rubidium@8055:  * Search the last set bit in a 64 bit variable.
rubidium@8000:  *
rubidium@8000:  * This algorithm is a static implementation of a log
skidd13@8005:  * conguence search algorithm. It checks the second half
rubidium@8000:  * if there is a bit set search there further. And this
rubidium@8000:  * way further. If no bit is set return 0.
rubidium@8000:  *
rubidium@8000:  * @param x The value to search
rubidium@8000:  * @return The position of the last bit set
rubidium@8000:  */
rubidium@8055: uint8 FindLastBit(uint64 x)
rubidium@8000: {
rubidium@8000: 	if (x == 0) return 0;
rubidium@8000: 
rubidium@8000: 	uint8 pos = 0;
rubidium@8000: 
rubidium@8055: 	if ((x & 0xffffffff00000000ULL) != 0) { x >>= 32; pos += 32; }
rubidium@8055: 	if ((x & 0x00000000ffff0000ULL) != 0) { x >>= 16; pos += 16; }
rubidium@8055: 	if ((x & 0x000000000000ff00ULL) != 0) { x >>= 8;  pos += 8;  }
rubidium@8055: 	if ((x & 0x00000000000000f0ULL) != 0) { x >>= 4;  pos += 4;  }
rubidium@8055: 	if ((x & 0x000000000000000cULL) != 0) { x >>= 2;  pos += 2;  }
rubidium@8055: 	if ((x & 0x0000000000000002ULL) != 0) { pos += 1; }
rubidium@8000: 
rubidium@8000: 	return pos;
rubidium@8000: }