src/core/bitmath_func.cpp

   1 /* $Id$ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   8  */
   9
  10 /** @file bitmath_func.cpp Functions related to bit mathematics. */
  11
  12 #include "../stdafx.h"
  13 #include "bitmath_func.hpp"
  14
  15 const uint8 _ffb_64[64] = {
  16         0,  0,  1,  0,  2,  0,  1,  0,
  17         3,  0,  1,  0,  2,  0,  1,  0,
  18         4,  0,  1,  0,  2,  0,  1,  0,
  19         3,  0,  1,  0,  2,  0,  1,  0,
  20         5,  0,  1,  0,  2,  0,  1,  0,
  21         3,  0,  1,  0,  2,  0,  1,  0,
  22         4,  0,  1,  0,  2,  0,  1,  0,
  23         3,  0,  1,  0,  2,  0,  1,  0,
  24 };
  25
  26 /**
  27  * Search the first set bit in a 32 bit variable.
  28  *
  29  * This algorithm is a static implementation of a log
  30  * congruence search algorithm. It checks the first half
  31  * if there is a bit set search there further. And this
  32  * way further. If no bit is set return 0.
  33  *
  34  * @param x The value to search
  35  * @return The position of the first bit set
  36  */
  37 uint8 FindFirstBit(uint32 x)
  38 {
  39         if (x == 0) return 0;
  40         /* The macro FIND_FIRST_BIT is better to use when your x is
  41           not more than 128. */
  42
  43         uint8 pos = 0;
  44
  45         if ((x & 0x0000ffff) == 0) { x >>= 16; pos += 16; }
  46         if ((x & 0x000000ff) == 0) { x >>= 8;  pos += 8;  }
  47         if ((x & 0x0000000f) == 0) { x >>= 4;  pos += 4;  }
  48         if ((x & 0x00000003) == 0) { x >>= 2;  pos += 2;  }
  49         if ((x & 0x00000001) == 0) { pos += 1; }
  50
  51         return pos;
  52 }
  53
  54 /**
  55  * Search the last set bit in a 64 bit variable.
  56  *
  57  * This algorithm is a static implementation of a log
  58  * congruence search algorithm. It checks the second half
  59  * if there is a bit set search there further. And this
  60  * way further. If no bit is set return 0.
  61  *
  62  * @param x The value to search
  63  * @return The position of the last bit set
  64  */
  65 uint8 FindLastBit(uint64 x)
  66 {
  67         if (x == 0) return 0;
  68
  69         uint8 pos = 0;
  70
  71         if ((x & 0xffffffff00000000ULL) != 0) { x >>= 32; pos += 32; }
  72         if ((x & 0x00000000ffff0000ULL) != 0) { x >>= 16; pos += 16; }
  73         if ((x & 0x000000000000ff00ULL) != 0) { x >>= 8;  pos += 8;  }
  74         if ((x & 0x00000000000000f0ULL) != 0) { x >>= 4;  pos += 4;  }
  75         if ((x & 0x000000000000000cULL) != 0) { x >>= 2;  pos += 2;  }
  76         if ((x & 0x0000000000000002ULL) != 0) { pos += 1; }
  77
  78         return pos;
  79 }