bitutils.c

   1 /*
   2  *      This program is free software; you can redistribute it and/or modify
   3  *      it under the terms of the GNU General Public License as published by
   4  *      the Free Software Foundation; either version 2 of the License, or
   5  *      (at your option) any later version.
   6  *
   7  *      This program is distributed in the hope that it will be useful,
   8  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  *      GNU General Public License for more details.
  11  *
  12  *      You should have received a copy of the GNU General Public License
  13  *      along with this program; if not, write to the Free Software
  14  *      Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  15  */
  16 #include "common.h"
  17 #include "board.h"
  18
  19 #ifdef X86
  20 static const int lsb_64_table[64] = {
  21         63, 30,  3, 32, 59, 14, 11, 33,
  22         60, 24, 50,  9, 55, 19, 21, 34,
  23         61, 29,  2, 53, 51, 23, 41, 18,
  24         56, 28,  1, 43, 46, 27,  0, 35,
  25         62, 31, 58,  4,  5, 49, 54,  6,
  26         15, 52, 12, 40,  7, 42, 45, 16,
  27         25, 57, 48, 13, 10, 39,  8, 44,
  28         20, 47, 38, 22, 17, 37, 36, 26
  29 };
  30
  31 int
  32 bit_scan(uint64_t b)
  33 {
  34         uint32_t folded;
  35
  36         b ^= (b - 1);
  37         folded = (int) b ^ (b >> 32);
  38
  39         return lsb_64_table[folded * 0x78291ACF >> 26];
  40 }
  41
  42 int
  43 bit_scan_clear(uint64_t *b)
  44 {
  45         uint32_t folded;
  46         uint64_t bb;
  47
  48         bb = *b;
  49         bb ^= (bb - 1);
  50         folded = (int) bb ^ (bb >> 32);
  51
  52         *b &= *b - 1;
  53
  54         return lsb_64_table[folded * 0x78291ACF >> 26];
  55 }
  56
  57 int
  58 bit_scan_rev(uint64_t b)
  59 {
  60         if (b >> 48) return (lzArray[b >> 48]) ^ 63;
  61         if (b >> 32) return (lzArray[b >> 32] + 16) ^ 63;
  62         if (b >> 16) return (lzArray[b >> 16] + 32) ^ 63;
  63
  64         return (lzArray[b] + 48) ^ 63;
  65 }
  66 #elif X86_64
  67 static const uint64_t de_bruijn_c = 0x07EDD5E59A4E28C2ULL;
  68
  69 static const int de_bruijn_index[64] = {
  70         63,  0, 58,  1, 59, 47, 53,  2,
  71         60, 39, 48, 27, 54, 33, 42,  3,
  72         61, 51, 37, 40, 49, 18, 28, 20,
  73         55, 30, 34, 11, 43, 14, 22,  4,
  74         62, 57, 46, 52, 38, 26, 32, 41,
  75         50, 36, 17, 19, 29, 10, 13, 21,
  76         56, 45, 25, 31, 35, 16,  9, 12,
  77         44, 24, 15,  8, 23,  7,  6,  5
  78 };
  79
  80 int
  81 bit_scan(uint64_t b)
  82 {
  83         return de_bruijn_index[((b & -b) * de_bruijn_c) >> 58];
  84 }
  85
  86 int
  87 bit_scan_clear(uint64_t *b)
  88 {
  89         uint64_t bb;
  90
  91         bb = *b;
  92         *b &= *b - 1;
  93
  94         return de_bruijn_index[((bb & -bb) * de_bruijn_c) >> 58];
  95 }
  96
  97 int
  98 bit_scan_rev(uint64_t b)
  99 {
 100         if (b >> 48) return (lzArray[b >> 48]) ^ 63;
 101         if (b >> 32) return (lzArray[b >> 32] + 16) ^ 63;
 102         if (b >> 16) return (lzArray[b >> 16] + 32) ^ 63;
 103
 104         return (lzArray[b] + 48) ^ 63;
 105 }
 106 #endif