first one code question

[Uri Blass]

I see that different open source bitboard programs have different functions
for first one and my question is:

1)Which way is better for speed?
2)I do not understand how the code works and the question is if programmers are allowed to do copy and paste for these functions that are not about chess and their meaning is clear(I give code of sloppy and glaurung and I hope that this is the code that they use for these functions because I did not look at the code of these programs enough to be sure about it).

3)In movei I prefered to use something that I wrote and understood so I also give the code that I use.

4)I do not know if strelka assembler code is original or copied from some source so I do not post it because I am not sure if I am allowed to do it.

Sloppy code

Code: Select all

#if defined(__GNUC__) && (defined(__LP64__) || defined(__powerpc64__))

/* Locates the first (least significant) "one" bit in a bitboard.
   Optimized for x86-64.  */
int
get_lsb(U64 b)
{
   U64 ret;
   __asm__
   (
        "bsfq %[b], %[ret]"
        :[ret] "=r" (ret)
        :[b] "mr" (b)
   );
   return (int)ret;
}

#else /* not 64-bit GNUC */

/* Locates the first (least significant) "one" bit in a bitboard.
   Optimized for x86.  */
int
get_lsb(U64 b)
{
   unsigned a;
   /* Based on code by Lasse Hansen.  */
   static const int lsb_table[32] = {
      31,  0,  9,  1, 10, 20, 13,  2,
       7, 11, 21, 23, 17, 14,  3, 25,
      30,  8, 19, 12,  6, 22, 16, 24,
      29, 18,  5, 15, 28,  4, 27, 26
   };

   ASSERT(2, b != 0);

   a = (unsigned)b;
   if (a != 0)
      return lsb_table[((a & -(int)a) * 0xe89b2be) >> 27];
   a  =  (unsigned)(b >> 32);

   return lsb_table[((a & -(int)a) * 0xe89b2be) >> 27]  +  32;
}

#endif /* not 64-bit GNUC */

Glaurung code

Code: Select all

#if defined(USE_FOLDED_BITSCAN)

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

Square first_1(Bitboard b) {
  uint32 fold;
  b ^= (b - 1);
  fold = int(b) ^ int(b >> 32);
  return Square(BitTable[(fold * 0x783a9b23) >> 26]);
}

Square pop_1st_bit(Bitboard* b) {
  Bitboard bb = *b ^ (*b - 1);
  uint32 fold = int(bb) ^ int(bb >> 32);
  *b &= (*b - 1);
  return Square(BitTable[(fold * 0x783a9b23) >> 26]);
}

#else

static const int BitTable[64] = {
  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
};

Square first_1(Bitboard b) {
  return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
}

Square pop_1st_bit(Bitboard* b) {
  Bitboard bb = *b;
  *b &= (*b - 1);
  return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
}

#endif



Note that in Movei I have the following functions

Code: Select all

static void initializepowers(void)
{
  int maskl,i;
  char j;
  biggest_power[0]=-1;
  smallest_power[0]=-1;
  for (i=1;i<65536;i++)
  {
   biggest_power[i]=-1;
   smallest_power[i]=-1;
    maskl=1;
    for(j=0;j<16;j++)
   {
      if ((maskl & i))
     {
        biggest_power[i]=j;
      if (smallest_power[i]==-1)
         smallest_power[i]=j;
      }
      maskl=maskl<<1;
    }
  }
}

int smallest_pow(BitBoard arg1)
{
    if (arg1&65535)
      return (smallest_power[arg1&65535]);
       
    if ((arg1>>16)&65535)
      return (smallest_power[(arg1>>16)&65535]+16);
 
    if ((arg1>>32)&65535)
     return (smallest_power[(arg1>>32)&65535]+32);
    return (smallest_power[(arg1>>48)]+48);
}

int biggest_pow(BitBoard arg1)
{
   if (arg1>>48)
      return biggest_power[(arg1>>48)]+48;
   if (arg1>>32)
         return biggest_power[(arg1>>32)]+32;
   if (arg1>>16)
      return biggest_power[(arg1>>16)]+16;
   return biggest_power[arg1];
}


[Ilari Pihlajisto]

I can't give a definitive answer to 1) because the speed depends on the processor architecture. Sloppy's get_lsb() for 64-bit GNUC is probably as fast as it gets. On 32-bit I just tried Glaurung's bitscans in Sloppy, and they were both slightly slower on my pc (Core 2 Duo, Linux OS) than what I'm currently using. They may be faster on some other machines.

As for question 2, I feel that it's enough that I understand exactly what these functions do, not how they do it. Sloppy's popcount and get_lsb functions are from these forums. I think Gerd Isenberg has posted several bit-twiddling functions here. So it seems to me that they were released for public domain.

[bob]

I see that different open source bitboard programs have different functions
for first one and my question is:

1)Which way is better for speed?

I believe that what I do is as good as can be done, using the inline BSF/BSR instructions...

2)I do not understand how the code works and the question is if programmers are allowed to do copy and paste for these functions that are not about chess and their meaning is clear(I give code of sloppy and glaurung and I hope that this is the code that they use for these functions because I did not look at the code of these programs enough to be sure about it).

I don't see why not. I took my Lock/Unlock functions from the linux kernel, and many have copied that code directly from Crafty.

3)In movei I prefered to use something that I wrote and understood so I also give the code that I use.

4)I do not know if strelka assembler code is original or copied from some source so I do not post it because I am not sure if I am allowed to do it. [/quote

looks just like what I do using bsf/bsr...

Sloppy code

Code: Select all

#if defined(__GNUC__) && (defined(__LP64__) || defined(__powerpc64__))

/* Locates the first (least significant) "one" bit in a bitboard.
   Optimized for x86-64.  */
int
get_lsb(U64 b)
{
   U64 ret;
   __asm__
   (
        "bsfq %[b], %[ret]"
        :[ret] "=r" (ret)
        :[b] "mr" (b)
   );
   return (int)ret;
}

#else /* not 64-bit GNUC */

/* Locates the first (least significant) "one" bit in a bitboard.
   Optimized for x86.  */
int
get_lsb(U64 b)
{
   unsigned a;
   /* Based on code by Lasse Hansen.  */
   static const int lsb_table[32] = {
      31,  0,  9,  1, 10, 20, 13,  2,
       7, 11, 21, 23, 17, 14,  3, 25,
      30,  8, 19, 12,  6, 22, 16, 24,
      29, 18,  5, 15, 28,  4, 27, 26
   };

   ASSERT(2, b != 0);

   a = (unsigned)b;
   if (a != 0)
      return lsb_table[((a & -(int)a) * 0xe89b2be) >> 27];
   a  =  (unsigned)(b >> 32);

   return lsb_table[((a & -(int)a) * 0xe89b2be) >> 27]  +  32;
}

#endif /* not 64-bit GNUC */

Glaurung code

Code: Select all

#if defined(USE_FOLDED_BITSCAN)

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

Square first_1(Bitboard b) {
  uint32 fold;
  b ^= (b - 1);
  fold = int(b) ^ int(b >> 32);
  return Square(BitTable[(fold * 0x783a9b23) >> 26]);
}

Square pop_1st_bit(Bitboard* b) {
  Bitboard bb = *b ^ (*b - 1);
  uint32 fold = int(bb) ^ int(bb >> 32);
  *b &= (*b - 1);
  return Square(BitTable[(fold * 0x783a9b23) >> 26]);
}

#else

static const int BitTable[64] = {
  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
};

Square first_1(Bitboard b) {
  return Square(BitTable[((b & -b) * 0x218a392cd3d5dbfULL) >> 58]);
}

Square pop_1st_bit(Bitboard* b) {
  Bitboard bb = *b;
  *b &= (*b - 1);
  return Square(BitTable[((bb & -bb) * 0x218a392cd3d5dbfULL) >> 58]);
}

#endif



Note that in Movei I have the following functions

Code: Select all

static void initializepowers(void)
{
  int maskl,i;
  char j;
  biggest_power[0]=-1;
  smallest_power[0]=-1;
  for (i=1;i<65536;i++)
  {
   biggest_power[i]=-1;
   smallest_power[i]=-1;
    maskl=1;
    for(j=0;j<16;j++)
   {
      if ((maskl & i))
     {
        biggest_power[i]=j;
      if (smallest_power[i]==-1)
         smallest_power[i]=j;
      }
      maskl=maskl<<1;
    }
  }
}

int smallest_pow(BitBoard arg1)
{
    if (arg1&65535)
      return (smallest_power[arg1&65535]);
       
    if ((arg1>>16)&65535)
      return (smallest_power[(arg1>>16)&65535]+16);
 
    if ((arg1>>32)&65535)
     return (smallest_power[(arg1>>32)&65535]+32);
    return (smallest_power[(arg1>>48)]+48);
}

int biggest_pow(BitBoard arg1)
{
   if (arg1>>48)
      return biggest_power[(arg1>>48)]+48;
   if (arg1>>32)
         return biggest_power[(arg1>>32)]+32;
   if (arg1>>16)
      return biggest_power[(arg1>>16)]+16;
   return biggest_power[arg1];
}


[Uri Blass]

I see that different open source bitboard programs have different functions
for first one and my question is:

1)Which way is better for speed?

I believe that what I do is as good as can be done, using the inline BSF/BSR instructions...

I see that Crafty has the following code in boolean.c:

Code: Select all

int LSB(BITBOARD arg1)
{
  unsigned long index;

  if (_BitScanForward64(&index, arg1))
    return index;
  else
    return 64;
}

It has if else and my question is if it is good to have branches in code like this.

Uri

[bob]

I see that different open source bitboard programs have different functions
for first one and my question is:

1)Which way is better for speed?

I believe that what I do is as good as can be done, using the inline BSF/BSR instructions...

I see that Crafty has the following code in boolean.c:

Code: Select all

int LSB(BITBOARD arg1)
{
  unsigned long index;

  if (_BitScanForward64(&index, arg1))
    return index;
  else
    return 64;
}

It has if else and my question is if it is good to have branches in code like this.

Uri

It is safe because the branch is never taken. I never call the thing with a non-zero value in the first place, it is only there to catch the debugging errors that creep in when testing new things. But normally, the value is always non-zero so the return 64 never happens.

[Tord Romstad]

1)Which way is better for speed?

For speed, the assembly language instructions are probably difficult to beat on modern x86 CPUs. I use a de Bruijn bitscan instead, because I dislike using assembly language, and because Glaurung's doesn't call its bitscanning functions quite as often as other bitboard programs anyway (mainly because I use piece lists in addition to bitboards).

Tord