author | rubidium |
Sat, 26 Apr 2008 20:54:56 +0000 | |
branch | 0.6 |
changeset 10366 | 960aae8c20e2 |
parent 8551 | a7c546f4cf86 |
child 10429 | 1b99254f9607 |
permissions | -rw-r--r-- |
8467
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
1 |
/* $Id$ */ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
2 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
3 |
/** @file bitmath_func.cpp */ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
4 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
5 |
#include "../stdafx.h" |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
6 |
#include "bitmath_func.hpp" |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
7 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
8 |
const uint8 _ffb_64[64] = { |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
9 |
0, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
10 |
3, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
11 |
4, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
12 |
3, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
13 |
5, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
14 |
3, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
15 |
4, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
16 |
3, 0, 1, 0, 2, 0, 1, 0, |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
17 |
}; |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
18 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
19 |
/** |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
20 |
* Search the first set bit in a 32 bit variable. |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
21 |
* |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
22 |
* This algorithm is a static implementation of a log |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
23 |
* conguence search algorithm. It checks the first half |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
24 |
* if there is a bit set search there further. And this |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
25 |
* way further. If no bit is set return 0. |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
26 |
* |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
27 |
* @param x The value to search |
8496
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
28 |
* @return The position of the first bit set |
8467
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
29 |
*/ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
30 |
uint8 FindFirstBit(uint32 x) |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
31 |
{ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
32 |
if (x == 0) return 0; |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
33 |
/* The macro FIND_FIRST_BIT is better to use when your x is |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
34 |
not more than 128. */ |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
35 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
36 |
uint8 pos = 0; |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
37 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
38 |
if ((x & 0x0000ffff) == 0) { x >>= 16; pos += 16; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
39 |
if ((x & 0x000000ff) == 0) { x >>= 8; pos += 8; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
40 |
if ((x & 0x0000000f) == 0) { x >>= 4; pos += 4; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
41 |
if ((x & 0x00000003) == 0) { x >>= 2; pos += 2; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
42 |
if ((x & 0x00000001) == 0) { pos += 1; } |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
43 |
|
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
44 |
return pos; |
2f293250afac
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
45 |
} |
8496
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
46 |
|
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
47 |
/** |
8551
a7c546f4cf86
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8501
diff
changeset
|
48 |
* Search the last set bit in a 64 bit variable. |
8496
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
49 |
* |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
50 |
* This algorithm is a static implementation of a log |
8501
66d88113ba24
(svn r11564) -Codechange: Increase the usage of the for_each_bit macro and rename it fitting to the naming style
skidd13
parents:
8496
diff
changeset
|
51 |
* conguence search algorithm. It checks the second half |
8496
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
52 |
* if there is a bit set search there further. And this |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
53 |
* way further. If no bit is set return 0. |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
54 |
* |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
55 |
* @param x The value to search |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
56 |
* @return The position of the last bit set |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
57 |
*/ |
8551
a7c546f4cf86
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8501
diff
changeset
|
58 |
uint8 FindLastBit(uint64 x) |
8496
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
59 |
{ |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
60 |
if (x == 0) return 0; |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
61 |
|
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
62 |
uint8 pos = 0; |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
63 |
|
8551
a7c546f4cf86
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8501
diff
changeset
|
64 |
if ((x & 0xffffffff00000000ULL) != 0) { x >>= 32; pos += 32; } |
a7c546f4cf86
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8501
diff
changeset
|
65 |
if ((x & 0x00000000ffff0000ULL) != 0) { x >>= 16; pos += 16; } |
a7c546f4cf86
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8501
diff
changeset
|
66 |
if ((x & 0x000000000000ff00ULL) != 0) { x >>= 8; pos += 8; } |
a7c546f4cf86
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8501
diff
changeset
|
67 |
if ((x & 0x00000000000000f0ULL) != 0) { x >>= 4; pos += 4; } |
a7c546f4cf86
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8501
diff
changeset
|
68 |
if ((x & 0x000000000000000cULL) != 0) { x >>= 2; pos += 2; } |
a7c546f4cf86
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8501
diff
changeset
|
69 |
if ((x & 0x0000000000000002ULL) != 0) { pos += 1; } |
8496
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
70 |
|
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
71 |
return pos; |
8a4bdf20acb7
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
8467
diff
changeset
|
72 |
} |