Decoded: OpenTTD (2003) v1.8 (2018)
Source file: bitmath_func.cpp
Line-by-line code walkthrough by MaiZure

bitmath_func.cpp defines bit searching algorithms

Original code:
https://github.com/MaiZure/OpenTTD-1.8/blob/master/src/core/bitmath_func.cpp





1     COMMENT (*)
2     BLANK (-)
3     *
4     *
5     *
6     *
7     *
8     *
9     -
10    *
11    -
12    Includes the OpenTTD platform-specific header
13    Includes the OpenTTD bitmath function header
14    -
15    Includes the OpenTTD safeguards header
16    -
17    BLOCK START - _ffb_64 lookup table for 6 bit variable to find the first
      asserted least-significant bit
18    Table entries 0-7
19    Table entries 8-15
20    Table entries 16-23
21    Table entries 24-31
22    Table entries 32-39
23    Table entries 40-47
24    Table entries 48-55
25    Table entries 56-63
26    BLOCK END - _ffb_64 lookup table
27    -
28    *
29    *
30    *
31    *
32    *
33    *
34    *
35    *
36    *
37    *
38    *
39    Defines FindFirstBit with one argument: The input integer to check
40    BLOCK START - FindFirstBit, Finds the position of the first asserted,
      least-significant bit
41    If the input value is zero, then there is no asserted bit
42    *
43    *
44    -
45    Start at the first position
46    -
47    If the first 16 bits are clear, move to the 17th bit.
48    Check the next 8 bits and move again (0-8 or 17-24)
49    Check the next 4 bits and move again (0-4, 9-12, 17-20, 25-28)
50    Check the next 2 bits and move or stay
51    Check the last bit. Pos should now contain the first asserted bit position
52    -
53    Return the position
54    BLOCK END - FindFirstBit
55    -
56    *
57    *
58    *
59    *
60    *
61    *
62    *
63    *
64    *
65    *
66    *
67    Defines FindLastBit with one argument: A 64-bit input to check
68    BLOCK START - FindLastBit, returns the position of the most significant
      asserted bit
69    No input means return the first position
70    -
71    Start at the beginning
72    -
73    Check the most significant 32 bits. Shift if needed
74    Check the next 16 bits. Shift if needed
75    Check the next 8 bits. Shift if needed
76    Check the next 4 bits. Shift if needed
77    Check the next 2 bits. Shift if needed
78    Check the last bit. Shift if needed
79    -
80    Return the position
81    BLOCK END - FindLastBit