bit.c

Go to the documentation of this file.

 
#include "bit.h"
#include "util.h"
 
const unsigned long long X_TO_BIT[] = {
        0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
        0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL, 0x0000000000000080ULL,
        0x0000000000000100ULL, 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL,
        0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, 0x0000000000008000ULL,
        0x0000000000010000ULL, 0x0000000000020000ULL, 0x0000000000040000ULL, 0x0000000000080000ULL,
        0x0000000000100000ULL, 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL,
        0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, 0x0000000008000000ULL,
        0x0000000010000000ULL, 0x0000000020000000ULL, 0x0000000040000000ULL, 0x0000000080000000ULL,
        0x0000000100000000ULL, 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL,
        0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, 0x0000008000000000ULL,
        0x0000010000000000ULL, 0x0000020000000000ULL, 0x0000040000000000ULL, 0x0000080000000000ULL,
        0x0000100000000000ULL, 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL,
        0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, 0x0008000000000000ULL,
        0x0010000000000000ULL, 0x0020000000000000ULL, 0x0040000000000000ULL, 0x0080000000000000ULL,
        0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL,
        0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, 0x8000000000000000ULL,
        0, 0 // <- hack for passing move & nomove
};
 
const unsigned long long NEIGHBOUR[] = {
        0x0000000000000302ULL, 0x0000000000000705ULL, 0x0000000000000e0aULL, 0x0000000000001c14ULL,
        0x0000000000003828ULL, 0x0000000000007050ULL, 0x000000000000e0a0ULL, 0x000000000000c040ULL,
        0x0000000000030203ULL, 0x0000000000070507ULL, 0x00000000000e0a0eULL, 0x00000000001c141cULL,
        0x0000000000382838ULL, 0x0000000000705070ULL, 0x0000000000e0a0e0ULL, 0x0000000000c040c0ULL,
        0x0000000003020300ULL, 0x0000000007050700ULL, 0x000000000e0a0e00ULL, 0x000000001c141c00ULL,
        0x0000000038283800ULL, 0x0000000070507000ULL, 0x00000000e0a0e000ULL, 0x00000000c040c000ULL,
        0x0000000302030000ULL, 0x0000000705070000ULL, 0x0000000e0a0e0000ULL, 0x0000001c141c0000ULL,
        0x0000003828380000ULL, 0x0000007050700000ULL, 0x000000e0a0e00000ULL, 0x000000c040c00000ULL,
        0x0000030203000000ULL, 0x0000070507000000ULL, 0x00000e0a0e000000ULL, 0x00001c141c000000ULL,
        0x0000382838000000ULL, 0x0000705070000000ULL, 0x0000e0a0e0000000ULL, 0x0000c040c0000000ULL,
        0x0003020300000000ULL, 0x0007050700000000ULL, 0x000e0a0e00000000ULL, 0x001c141c00000000ULL,
        0x0038283800000000ULL, 0x0070507000000000ULL, 0x00e0a0e000000000ULL, 0x00c040c000000000ULL,
        0x0302030000000000ULL, 0x0705070000000000ULL, 0x0e0a0e0000000000ULL, 0x1c141c0000000000ULL,
        0x3828380000000000ULL, 0x7050700000000000ULL, 0xe0a0e00000000000ULL, 0xc040c00000000000ULL,
        0x0203000000000000ULL, 0x0507000000000000ULL, 0x0a0e000000000000ULL, 0x141c000000000000ULL,
        0x2838000000000000ULL, 0x5070000000000000ULL, 0xa0e0000000000000ULL, 0x40c0000000000000ULL,
        0, 0 // <- hack for passing move & nomove
};
 
DLL_API int bit_count(unsigned long long b)
{
#if defined(POPCOUNT)
 
        #if defined(USE_GAS_X64)
                __asm__("popcntq %1,%0" :"=r" (b) :"rm" (b));
                return (int) b;
        #elif defined(USE_MSVC_X64)
                return __popcnt64(b);
        #elif defined(USE_GCC_X64)
                return __builtin_popcountll(b);
        #endif
 
// MMX does not help much here :-(
#elif defined (USE_GAS_MMX)
 
        const unsigned long long M55 = 0x5555555555555555ULL;
        const unsigned long long M33 = 0x3333333333333333ULL;
        const unsigned long long M0F = 0x0F0F0F0F0F0F0F0FULL;
        int count;
 
        __asm__ volatile(
                "movq  %1, %%mm1\n\t"
                "pxor  %%mm2, %%mm2\n\t"
 
                "movq  %%mm1, %%mm0\n\t"
                "psrlq $1, %%mm1\n\t"
                "pand  %2, %%mm1\n\t"
                "psubd %%mm1, %%mm0\n\t"
 
                "movq  %%mm0, %%mm1\n\t"
                "psrlq $2, %%mm0\n\t"
                "pand  %3, %%mm1\n\t"
                "pand  %3, %%mm0\n\t"
                "paddd %%mm1, %%mm0\n\t"
 
                "movq  %%mm0, %%mm1\n\t"
                "psrlq $4, %%mm0\n\t"
                "paddd %%mm1, %%mm0\n\t"
                "pand  %4, %%mm0\n\t"
 
                "psadbw %%mm2, %%mm0\n\t"
                "movd   %%mm0, %0\n\t"
                "emms\n\t"
                : "=a" (count) : "m" (b), "m" (M55), "m" (M33), "m" (M0F));
 
        return count;
 
#else
 
        register unsigned long long c = b
                - ((b >> 1) & 0x7777777777777777ULL)
                - ((b >> 2) & 0x3333333333333333ULL)
                - ((b >> 3) & 0x1111111111111111ULL);
        c = ((c + (c >> 4)) & 0x0F0F0F0F0F0F0F0FULL) * 0x0101010101010101ULL;
 
        return  (int)(c >> 56);
 
#endif
}
 
 
int bit_weighted_count(const unsigned long long v)
{
#if defined(POPCOUNT)
 
        return bit_count(v) + bit_count(v & 0x8100000000000081ULL);
 
#else
 
        register unsigned long long b;
        b  = v - ((v >> 1) & 0x1555555555555515ULL) + (v & 0x0100000000000001ULL);
        b  = ((b >> 2) & 0x3333333333333333ULL) + (b & 0x3333333333333333ULL);
        b  = ((b >> 4) + b) & 0x0f0f0f0f0f0f0f0fULL;
        b *= 0x0101010101010101ULL;
 
        return  (int)(b >> 56);
 
#endif
}
 
DLL_API int first_bit(unsigned long long b)
{
#if defined(USE_GAS_X64)
 
        __asm__("bsfq %1,%0" : "=r" (b) : "rm" (b));
        return (int) b;
 
#elif defined(USE_GAS_X86)
 
  int x1, x2;
        __asm__ ("bsf %0,%0\n"
                 "jnz 1f\n"
                 "bsf %1,%0\n"
                 "jz 1f\n"
                 "addl $32,%0\n"
                     "1:": "=&q" (x1), "=&q" (x2):"1" ((int) (b >> 32)), "0" ((int) b));
        return x1;
 
#elif defined(USE_MSVC_X64)
 
        unsigned long index;
        _BitScanForward64(&index, b);
        return (int) index;
 
#elif defined(USE_GCC_X64)
 
        return __builtin_ctzll(b);
 
#elif defined(USE_MASM_X86)
        __asm {
                xor eax, eax
                bsf edx, dword ptr b
                jnz l1
                bsf edx, dword ptr b+4
                mov eax, 32
                jnz l1
                mov edx, -32
        l1:     add eax, edx
        }
 
#elif defined(USE_GCC_ARM)
        const unsigned int lb = (unsigned int)b;
        if (lb) {
                return  __builtin_clz(lb & -lb) ^ 31;
        } else {
                const unsigned int hb = b >> 32;
                return 32 + (__builtin_clz(hb & -hb) ^ 31);
        }
 
#else
 
        const int magic[64] = {
                63, 0, 58, 1, 59, 47, 53, 2,
                60, 39, 48, 27, 54, 33, 42, 3,
                61, 51, 37, 40, 49, 18, 28, 20,
                55, 30, 34, 11, 43, 14, 22, 4,
                62, 57, 46, 52, 38, 26, 32, 41,
                50, 36, 17, 19, 29, 10, 13, 21,
                56, 45, 25, 31, 35, 16, 9, 12,
                44, 24, 15, 8, 23, 7, 6, 5
        };
 
        return magic[((b & (-b)) * 0x07EDD5E59A4E28C2ULL) >> 58];
 
#endif
}
 
int next_bit(unsigned long long *b)
{
        *b &= *b - 1;
        return first_bit(*b);
}
 
DLL_API int last_bit(unsigned long long b)
{
#if defined(USE_GAS_X64)
 
        __asm__("bsrq %1,%0" :"=r" (b) :"rm" (b));
        return b;
 
#elif defined(USE_MSVC_X64)
 
        unsigned long index;
        _BitScanReverse64(&index, b);
        return (int) index;
 
#elif defined(USE_GCC_X64)
 
        return 63 - __builtin_clzll(b);
        
#elif defined(USE_GAS_X86)
 
  int x1, x2;
        __asm__ ("bsr %1,%0\n"
                 "jnz 1f\n"
                 "bsr %0,%0\n"
                 "subl $32,%0\n"
             "1: addl $32,%0\n" : "=&q" (x1), "=&q" (x2) : "1" ((int) (b >> 32)), "0" ((int) b));
  return x1;
 
        
#elif defined(USE_GCC_ARM)
        const unsigned int hb = b >> 32;
        if (hb) {
                return 63 - __builtin_clz(hb);
        } else {
                return 31 - __builtin_clz((int) b);
        }
 
 
#elif defined(USE_MASM_X86)
        __asm {
                xor eax, eax
                bsr edx, dword ptr b+4
                jnz l1
                bsr edx, dword ptr b
                mov eax, 32
                jnz l1
                mov edx, -32
        l1:     add eax, edx
        }
 
        
#else
 
        const int magic[64] = {
                63, 0, 58, 1, 59, 47, 53, 2,
                60, 39, 48, 27, 54, 33, 42, 3,
                61, 51, 37, 40, 49, 18, 28, 20,
                55, 30, 34, 11, 43, 14, 22, 4,
                62, 57, 46, 52, 38, 26, 32, 41,
                50, 36, 17, 19, 29, 10, 13, 21,
                56, 45, 25, 31, 35, 16, 9, 12,
                44, 24, 15, 8, 23, 7, 6, 5
        };
 
        b |= b >> 1;
        b |= b >> 2;
        b |= b >> 4;
        b |= b >> 8;
        b |= b >> 16;
        b |= b >> 32;
        b = (b >> 1) + 1;
 
        return magic[(b * 0x07EDD5E59A4E28C2ULL) >> 58];
 
#endif
}
 
unsigned long long transpose(unsigned long long b)
{
        unsigned long long t;
 
        t = (b ^ (b >> 7)) & 0x00aa00aa00aa00aaULL;
        b = b ^ t ^ (t << 7);
        t = (b ^ (b >> 14)) & 0x0000cccc0000ccccULL;
        b = b ^ t ^ (t << 14);
        t = (b ^ (b >> 28)) & 0x00000000f0f0f0f0ULL;
        b = b ^ t ^ (t << 28);
 
        return b;
}
 
unsigned long long vertical_mirror(unsigned long long b)
{
        b = ((b >>  8) & 0x00FF00FF00FF00FFULL) | ((b <<  8) & 0xFF00FF00FF00FF00ULL);
        b = ((b >> 16) & 0x0000FFFF0000FFFFULL) | ((b << 16) & 0xFFFF0000FFFF0000ULL);
        b = ((b >> 32) & 0x00000000FFFFFFFFULL) | ((b << 32) & 0xFFFFFFFF00000000ULL);
        return b;
}
 
unsigned long long horizontal_mirror(unsigned long long b)
{
  b = ((b >> 1) & 0x5555555555555555ULL) | ((b << 1) & 0xAAAAAAAAAAAAAAAAULL);
  b = ((b >> 2) & 0x3333333333333333ULL) | ((b << 2) & 0xCCCCCCCCCCCCCCCCULL);
  b = ((b >> 4) & 0x0F0F0F0F0F0F0F0FULL) | ((b << 4) & 0xF0F0F0F0F0F0F0F0ULL);
 
  return b;
}
 
unsigned short bswap_short(unsigned short s)
{
        return (unsigned short) ((s >> 8) & 0x00FF) | ((s <<  8) & 0xFF00);
}
 
unsigned int bswap_int(unsigned int i)
{
        i = ((i >>  8) & 0x00FF00FFU) | ((i <<  8) & 0xFF00FF00U);
        i = ((i >> 16) & 0x0000FFFFU) | ((i << 16) & 0xFFFF0000U);
        return i;
}
 
int get_rand_bit(unsigned long long b, Random *r)
{
        int n = bit_count(b), x;
 
        if (n == 0) return -1;
 
        n = random_get(r) % n;
        foreach_bit(x, b) if (n-- == 0) return x;
 
        return -2; // impossible.
}
 
void bitboard_write(const unsigned long long b, FILE *f)
{
        int i, j, x;
        const char *color = ".X";
 
        fputs("  A B C D E F G H\n", f);
        for (i = 0; i < 8; ++i) {
                fputc(i + '1', f);
                fputc(' ', f);
                for (j = 0; j < 8; ++j) {
                        x = i * 8 + j;
                        fputc(color[((b >> (unsigned)x) & 1)], f);
                        fputc(' ', f);
                }
                fputc(i + '1', f);
                fputc('\n', f);
        }
        fputs("  A B C D E F G H\n", f);
}