author | peter1138 |
Tue, 22 Jan 2008 07:27:06 +0000 | |
changeset 8374 | 7a1b6c89cb89 |
parent 8055 | 49cf1521d591 |
child 9111 | 48ce04029fe4 |
permissions | -rw-r--r-- |
7971
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
1 |
/* $Id$ */ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
2 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
3 |
/** @file bitmath_func.cpp */ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
4 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
5 |
#include "../stdafx.h" |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
6 |
#include "bitmath_func.hpp" |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
7 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
8 |
const uint8 _ffb_64[64] = { |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(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, |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
17 |
}; |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
18 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
19 |
/** |
8509d595142a
(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. |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
21 |
* |
8509d595142a
(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 |
8509d595142a
(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 |
8509d595142a
(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 |
8509d595142a
(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. |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
26 |
* |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
27 |
* @param x The value to search |
8000
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
28 |
* @return The position of the first bit set |
7971
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
29 |
*/ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
30 |
uint8 FindFirstBit(uint32 x) |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
31 |
{ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
32 |
if (x == 0) return 0; |
8509d595142a
(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 |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
34 |
not more than 128. */ |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
35 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
36 |
uint8 pos = 0; |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
37 |
|
8509d595142a
(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; } |
8509d595142a
(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; } |
8509d595142a
(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; } |
8509d595142a
(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; } |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
42 |
if ((x & 0x00000001) == 0) { pos += 1; } |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
43 |
|
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
44 |
return pos; |
8509d595142a
(svn r11527) -Codechange: Split the bitmath functions of to their own files
skidd13
parents:
diff
changeset
|
45 |
} |
8000
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
46 |
|
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
47 |
/** |
8055
49cf1521d591
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8005
diff
changeset
|
48 |
* Search the last set bit in a 64 bit variable. |
8000
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
49 |
* |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
50 |
* This algorithm is a static implementation of a log |
8005
2318a0547719
(svn r11564) -Codechange: Increase the usage of the for_each_bit macro and rename it fitting to the naming style
skidd13
parents:
8000
diff
changeset
|
51 |
* conguence search algorithm. It checks the second half |
8000
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
52 |
* if there is a bit set search there further. And this |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
53 |
* way further. If no bit is set return 0. |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
54 |
* |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
55 |
* @param x The value to search |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
56 |
* @return The position of the last bit set |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
57 |
*/ |
8055
49cf1521d591
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8005
diff
changeset
|
58 |
uint8 FindLastBit(uint64 x) |
8000
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
59 |
{ |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
60 |
if (x == 0) return 0; |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
61 |
|
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
62 |
uint8 pos = 0; |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
63 |
|
8055
49cf1521d591
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8005
diff
changeset
|
64 |
if ((x & 0xffffffff00000000ULL) != 0) { x >>= 32; pos += 32; } |
49cf1521d591
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8005
diff
changeset
|
65 |
if ((x & 0x00000000ffff0000ULL) != 0) { x >>= 16; pos += 16; } |
49cf1521d591
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8005
diff
changeset
|
66 |
if ((x & 0x000000000000ff00ULL) != 0) { x >>= 8; pos += 8; } |
49cf1521d591
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8005
diff
changeset
|
67 |
if ((x & 0x00000000000000f0ULL) != 0) { x >>= 4; pos += 4; } |
49cf1521d591
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8005
diff
changeset
|
68 |
if ((x & 0x000000000000000cULL) != 0) { x >>= 2; pos += 2; } |
49cf1521d591
(svn r11616) -Fix [FS#1526]: sometimes large values could go off the chart.
rubidium
parents:
8005
diff
changeset
|
69 |
if ((x & 0x0000000000000002ULL) != 0) { pos += 1; } |
8000
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
70 |
|
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
71 |
return pos; |
2ba28bc428f1
(svn r11559) -Fix [FS#1505]: overflow when drawing graphics with high company values.
rubidium
parents:
7971
diff
changeset
|
72 |
} |