-
Notifications
You must be signed in to change notification settings - Fork 1
/
bit.h
140 lines (124 loc) · 2.98 KB
/
bit.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/*
* (c) Copyright 2001, 2004 - 2006 -- Anders Torger
*
* This program is open source. For license terms, see the LICENSE file.
*
*/
#ifndef _BIT_H_
#define _BIT_H_
#include <inttypes.h>
#include "defs.h"
static inline bool_t
bit_isset(const uint32_t bitset[],
int pos)
{
int n = pos >> 5;
return bitset[n] & 1 << (pos - (n << 5));
}
static inline void
bit_set(uint32_t bitset[],
int pos)
{
int n = pos >> 5;
bitset[n] = bitset[n] | 1 << (pos - (n << 5));
}
static inline void
bit_clr(uint32_t bitset[],
int pos)
{
int n = pos >> 5;
bitset[n] = bitset[n] & ~(1 << (pos - (n << 5)));
}
static inline bool_t
bit_isset_volatile(volatile const uint32_t bitset[],
int pos)
{
int n = pos >> 5;
return bitset[n] & 1 << (pos - (n << 5));
}
static inline void
bit_set_volatile(volatile uint32_t bitset[],
int pos)
{
int n = pos >> 5;
bitset[n] = bitset[n] | 1 << (pos - (n << 5));
}
static inline void
bit_clr_volatile(volatile uint32_t bitset[],
int pos)
{
int n = pos >> 5;
bitset[n] = bitset[n] & ~(1 << (pos - (n << 5)));
}
#if defined(__ARCH_IA32__)
static inline int
bit_bsf(uint32_t n)
{
int r;
__asm__ volatile ("bsfl %1,%0\n\t" : "=r" (r) : "g" (n));
return r;
}
#else
static inline int
bit_bsf(uint32_t n)
{
static const int tab[256] = {
0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
if ((n & 0x0000FFFF) != 0) {
if ((n & 0x000000FF) != 0) {
return tab[n & 0x000000FF];
} else {
return 8 + tab[(n & 0x0000FF00) >> 8];
}
} else {
if ((n & 0x00FF0000) != 0) {
return 16 + tab[(n & 0x00FF0000) >> 16];
} else {
return 24 + tab[(n & 0xFF000000) >> 24];
}
}
}
#endif
static inline int
bit_find(const uint32_t bitset[],
int start,
int end)
{
uint32_t b;
int n;
if (end < start) {
return -1;
}
if ((b = bitset[start >> 5] >> (start & 0x1F)) != 0) {
if ((n = bit_bsf(b) + start) > end) {
return -1;
}
return n;
}
for (n = (start >> 5) + 1; n <= end >> 5; n++) {
if (bitset[n] != 0) {
if ((n = bit_bsf(bitset[n]) + (n << 5)) > end) {
return -1;
}
return n;
}
}
return -1;
}
#endif