First One

[Jose Carlos]

Hi. Sorry if this has already been answered before.
I'm trying to compile an old engine of mine in 64 bits. I have some old asm code for FirstOne() (left and right, I mean, MSB and LSB) which won't compile for X64.
Is there some C code out there I can use for the tasks?
I don't care much for speed. I just want it to be problem-free.

Thanks in advance.

[Sven]

Hi. Sorry if this has already been answered before.
I'm trying to compile an old engine of mine in 64 bits. I have some old asm code for FirstOne() (left and right, I mean, MSB and LSB) which won't compile for X64.
Is there some C code out there I can use for the tasks?
I don't care much for speed. I just want it to be problem-free.

Thanks in advance.

Hi José,

have you already taken a look into the chess programming wiki? In case you haven't: go to the BitScan page and search for bitScanForward and bitScanReverse, there are several variants for both.

Sven

[Jim Ablett]

I use these a lot >

Code: Select all

#include <assert.h>

const uint64_t magic = 0x03f79d71b4cb0a89;


const unsigned int magictable[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 int bitscan_forward(uint64_t bb) {
assert (bb != 0);
return magictable[((bb&-bb)*magic) >> 58];
}


static inline int bitscan_reverse(uint64_t bb) {
    union {
    double d;
    struct {
    unsigned int mantissal : 32;     
    unsigned int mantissah : 20;     
    unsigned int exponent : 11;     
    unsigned int sign : 1;     
    };
    } ud;
    ud.d = (double)(uint64_t)(bb & ~(bb >> 32));
    int idx = (ud.exponent - 1023) | (63*ud.sign);
    return idx;
    }

Jim.

[Jose Carlos]

Thanks a lot to both. Really useful

[bob]

Hi. Sorry if this has already been answered before.
I'm trying to compile an old engine of mine in 64 bits. I have some old asm code for FirstOne() (left and right, I mean, MSB and LSB) which won't compile for X64.
Is there some C code out there I can use for the tasks?
I don't care much for speed. I just want it to be problem-free.

Thanks in advance.

Look in the crafty source. You can find two inline functions for LSB and MSB, which will use the BSF/BSR instructions... Trivial piece of code...

[jdart]

There are intrinsics for this in most compilers.

Here is some code I have (returns InvalidSquare if 'data' is 0, the first bit otherwise, using intrinsics):

Code: Select all

#elif defined(_WIN64) && defined(_MSC_VER) && defined(USE_INTRINSICS)
      DWORD index;
      if (_BitScanForward64(&index,data))
        return (Square)index;
      else 
        return InvalidSquare;
#elif defined(USE_INTRINSICS) && defined(__INTEL_COMPILER)
      if (lovalue()) {
         return _bit_scan_forward(lovalue());
      else if (hivalue()) {
         return _bit_scan_forward(hivalue())+32;
      } else {
         return InvalidSquare;
      }  
#elif defined(USE_INTRINSICS) && defined(__GNUC__)
      int tmp = __builtin_ffsll(data);
      if (tmp == 0) return InvalidSquare;
      else return tmp-1;

[Ron Murawski]

There are intrinsics for this in most compilers.

Here is some code I have (returns InvalidSquare if 'data' is 0, the first bit otherwise, using intrinsics):

Code: Select all

#elif defined(_WIN64) && defined(_MSC_VER) && defined(USE_INTRINSICS)
      DWORD index;
      if (_BitScanForward64(&index,data))
        return (Square)index;
      else 
        return InvalidSquare;
#elif defined(USE_INTRINSICS) && defined(__INTEL_COMPILER)
      if (lovalue()) {
         return _bit_scan_forward(lovalue());
      else if (hivalue()) {
         return _bit_scan_forward(hivalue())+32;
      } else {
         return InvalidSquare;
      }  
#elif defined(USE_INTRINSICS) && defined(__GNUC__)
      int tmp = __builtin_ffsll(data);
      if (tmp == 0) return InvalidSquare;
      else return tmp-1;

Hi Jon,

for GCC you can use this instead:

Code: Select all

#elif defined(USE_INTRINSICS) && defined(__GNUC__)
      int tmp = __builtin_ctzll(data);
      if (tmp == 0) return InvalidSquare;
      else return tmp;

it will save you the subtraction

[lucasart]

Hi. Sorry if this has already been answered before.
I'm trying to compile an old engine of mine in 64 bits. I have some old asm code for FirstOne() (left and right, I mean, MSB and LSB) which won't compile for X64.
Is there some C code out there I can use for the tasks?
I don't care much for speed. I just want it to be problem-free.

Thanks in advance.

From Stockfish. fast and portable

Code: Select all

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

unsigned first_bit(uint64_t b)
/* From Stockfish */
{
	return BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58];
}