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