author | rubidium |
Mon, 03 Dec 2007 23:39:38 +0000 | |
branch | NewGRF_ports |
changeset 6871 | 5a9dc001e1ad |
child 6872 | 1c4a4a609f85 |
permissions | -rw-r--r-- |
6871
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
1 |
/* $Id$ */ |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
2 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
3 |
/** @file bitmath_func.cpp */ |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
4 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
5 |
#include "../stdafx.h" |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
6 |
#include "bitmath_func.hpp" |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
7 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
8 |
const uint8 _ffb_64[64] = { |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
9 |
0, 0, 1, 0, 2, 0, 1, 0, |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
10 |
3, 0, 1, 0, 2, 0, 1, 0, |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
11 |
4, 0, 1, 0, 2, 0, 1, 0, |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
12 |
3, 0, 1, 0, 2, 0, 1, 0, |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
13 |
5, 0, 1, 0, 2, 0, 1, 0, |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
14 |
3, 0, 1, 0, 2, 0, 1, 0, |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
15 |
4, 0, 1, 0, 2, 0, 1, 0, |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
16 |
3, 0, 1, 0, 2, 0, 1, 0, |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
17 |
}; |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
18 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
19 |
/** |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
20 |
* Search the first set bit in a 32 bit variable. |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
21 |
* |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
22 |
* This algorithm is a static implementation of a log |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
23 |
* conguence search algorithm. It checks the first half |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
24 |
* if there is a bit set search there further. And this |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
25 |
* way further. If no bit is set return 0. |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
26 |
* |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
27 |
* @param x The value to search |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
28 |
* @return The position of the first bit set |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
29 |
*/ |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
30 |
uint8 FindFirstBit(uint32 x) |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
31 |
{ |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
32 |
if (x == 0) return 0; |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
33 |
/* The macro FIND_FIRST_BIT is better to use when your x is |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
34 |
not more than 128. */ |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
35 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
36 |
uint8 pos = 0; |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
37 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
38 |
if ((x & 0x0000ffff) == 0) { x >>= 16; pos += 16; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
39 |
if ((x & 0x000000ff) == 0) { x >>= 8; pos += 8; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
40 |
if ((x & 0x0000000f) == 0) { x >>= 4; pos += 4; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
41 |
if ((x & 0x00000003) == 0) { x >>= 2; pos += 2; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
42 |
if ((x & 0x00000001) == 0) { pos += 1; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
43 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
44 |
return pos; |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
45 |
} |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
46 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
47 |
/** |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
48 |
* Search the last set bit in a 32 bit variable. |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
49 |
* |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
50 |
* This algorithm is a static implementation of a log |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
51 |
* conguence search algorithm. It checks the second half |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
52 |
* if there is a bit set search there further. And this |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
53 |
* way further. If no bit is set return 0. |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
54 |
* |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
55 |
* @param x The value to search |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
56 |
* @return The position of the last bit set |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
57 |
*/ |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
58 |
uint8 FindLastBit(uint32 x) |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
59 |
{ |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
60 |
if (x == 0) return 0; |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
61 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
62 |
uint8 pos = 0; |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
63 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
64 |
if ((x & 0xffff0000) != 0) { x >>= 16; pos += 16; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
65 |
if ((x & 0x0000ff00) != 0) { x >>= 8; pos += 8; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
66 |
if ((x & 0x000000f0) != 0) { x >>= 4; pos += 4; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
67 |
if ((x & 0x0000000c) != 0) { x >>= 2; pos += 2; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
68 |
if ((x & 0x00000002) != 0) { pos += 1; } |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
69 |
|
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
70 |
return pos; |
5a9dc001e1ad
(svn r11566) [NewGRF_ports] -Sync: with trunk r11218:r11565.
rubidium
parents:
diff
changeset
|
71 |
} |