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 static const uint64_t de_bruijn_c = 0x07EDD5E59A4E28C2ULL;
  20
  21 static const int de_bruijn_index[64] = {
  22         63,  0, 58,  1, 59, 47, 53,  2,
  23         60, 39, 48, 27, 54, 33, 42,  3,
  24         61, 51, 37, 40, 49, 18, 28, 20,
  25         55, 30, 34, 11, 43, 14, 22,  4,
  26         62, 57, 46, 52, 38, 26, 32, 41,
  27         50, 36, 17, 19, 29, 10, 13, 21,
  28         56, 45, 25, 31, 35, 16,  9, 12,
  29         44, 24, 15,  8, 23,  7,  6,  5
  30 };
  31
  32 int
  33 bit_scan(uint64_t b)
  34 {
  35         return de_bruijn_index[((b & -b) * de_bruijn_c) >> 58];
  36 }
  37
  38 int
  39 bit_scan_clear(uint64_t *b)
  40 {
  41         uint64_t bb;
  42
  43         bb = *b;
  44         *b &= *b - 1;
  45
  46         return de_bruijn_index[((bb & -bb) * de_bruijn_c) >> 58];
  47 }
  48
  49 int
  50 bit_scan_rev(uint64_t b)
  51 {
  52         if (b >> 48) return (lzArray[b >> 48]) ^ 63;
  53         if (b >> 32) return (lzArray[b >> 32] + 16) ^ 63;
  54         if (b >> 16) return (lzArray[b >> 16] + 32) ^ 63;
  55
  56         return (lzArray[b] + 48) ^ 63;
  57 }