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