src/core/bitmath_func.cpp

   1 /* $Id: bitmath_func.cpp 24900 2013-01-08 22:46:42Z planetmaker $ */
   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 #include "../safeguards.h"
  16
  17 const uint8 _ffb_64[64] = {
  18         0,  0,  1,  0,  2,  0,  1,  0,
  19         3,  0,  1,  0,  2,  0,  1,  0,
  20         4,  0,  1,  0,  2,  0,  1,  0,
  21         3,  0,  1,  0,  2,  0,  1,  0,
  22         5,  0,  1,  0,  2,  0,  1,  0,
  23         3,  0,  1,  0,  2,  0,  1,  0,
  24         4,  0,  1,  0,  2,  0,  1,  0,
  25         3,  0,  1,  0,  2,  0,  1,  0,
  26 };
  27
  28 /**
  29  * Search the first set bit in a 32 bit variable.
  30  *
  31  * This algorithm is a static implementation of a log
  32  * congruence search algorithm. It checks the first half
  33  * if there is a bit set search there further. And this
  34  * way further. If no bit is set return 0.
  35  *
  36  * @param x The value to search
  37  * @return The position of the first bit set
  38  */
  39 uint8 FindFirstBit(uint32 x)
  40 {
  41         if (x == 0) return 0;
  42         /* The macro FIND_FIRST_BIT is better to use when your x is
  43           not more than 128. */
  44
  45         uint8 pos = 0;
  46
  47         if ((x & 0x0000ffff) == 0) { x >>= 16; pos += 16; }
  48         if ((x & 0x000000ff) == 0) { x >>= 8;  pos += 8;  }
  49         if ((x & 0x0000000f) == 0) { x >>= 4;  pos += 4;  }
  50         if ((x & 0x00000003) == 0) { x >>= 2;  pos += 2;  }
  51         if ((x & 0x00000001) == 0) { pos += 1; }
  52
  53         return pos;
  54 }
  55
  56 /**
  57  * Search the last set bit in a 64 bit variable.
  58  *
  59  * This algorithm is a static implementation of a log
  60  * congruence search algorithm. It checks the second half
  61  * if there is a bit set search there further. And this
  62  * way further. If no bit is set return 0.
  63  *
  64  * @param x The value to search
  65  * @return The position of the last bit set
  66  */
  67 uint8 FindLastBit(uint64 x)
  68 {
  69         if (x == 0) return 0;
  70
  71         uint8 pos = 0;
  72
  73         if ((x & 0xffffffff00000000ULL) != 0) { x >>= 32; pos += 32; }
  74         if ((x & 0x00000000ffff0000ULL) != 0) { x >>= 16; pos += 16; }
  75         if ((x & 0x000000000000ff00ULL) != 0) { x >>= 8;  pos += 8;  }
  76         if ((x & 0x00000000000000f0ULL) != 0) { x >>= 4;  pos += 4;  }
  77         if ((x & 0x000000000000000cULL) != 0) { x >>= 2;  pos += 2;  }
  78         if ((x & 0x0000000000000002ULL) != 0) { pos += 1; }
  79
  80         return pos;
  81 }