src/core/bitmath_func.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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/>.
   6  */
   7
   8 /** @file bitmath_func.cpp Functions related to bit mathematics. */
   9
  10 #include "../stdafx.h"
  11 #include "bitmath_func.hpp"
  12
  13 #include "../safeguards.h"
  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 64 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(uint64 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 & 0xffffffffULL) == 0) { x >>= 32; pos += 32; }
  46         if ((x & 0x0000ffffULL) == 0) { x >>= 16; pos += 16; }
  47         if ((x & 0x000000ffULL) == 0) { x >>= 8;  pos += 8;  }
  48         if ((x & 0x0000000fULL) == 0) { x >>= 4;  pos += 4;  }
  49         if ((x & 0x00000003ULL) == 0) { x >>= 2;  pos += 2;  }
  50         if ((x & 0x00000001ULL) == 0) { pos += 1; }
  51
  52         return pos;
  53 }
  54
  55 /**
  56  * Search the last set bit in a 64 bit variable.
  57  *
  58  * This algorithm is a static implementation of a log
  59  * congruence search algorithm. It checks the second half
  60  * if there is a bit set search there further. And this
  61  * way further. If no bit is set return 0.
  62  *
  63  * @param x The value to search
  64  * @return The position of the last bit set
  65  */
  66 uint8 FindLastBit(uint64 x)
  67 {
  68         if (x == 0) return 0;
  69
  70         uint8 pos = 0;
  71
  72         if ((x & 0xffffffff00000000ULL) != 0) { x >>= 32; pos += 32; }
  73         if ((x & 0x00000000ffff0000ULL) != 0) { x >>= 16; pos += 16; }
  74         if ((x & 0x000000000000ff00ULL) != 0) { x >>= 8;  pos += 8;  }
  75         if ((x & 0x00000000000000f0ULL) != 0) { x >>= 4;  pos += 4;  }
  76         if ((x & 0x000000000000000cULL) != 0) { x >>= 2;  pos += 2;  }
  77         if ((x & 0x0000000000000002ULL) != 0) { pos += 1; }
  78
  79         return pos;
  80 }