Debian Codegraph @

protolib/include/protoBitmask.h

raw
1 #ifndef _PROTO_BITMASK_
2 #define _PROTO_BITMASK_
3
4 #include "protoDefs.h"
5 #include "protoDebug.h"
6
7 #include <string.h> // for memset()
8 #include <stdio.h> // for fprintf()
9
10
11 /**
12 * @class ProtoBitmask
13 *
14 * @brief This class also provides space-efficient binary storage.
15 *
16 * It's pretty much just a flat-indexed array of bits, but
17 * keeps some state to be relatively efficient for various
18 * operations.
19 */
20
21 class ProtoBitmask
22 {
23 // Methods
24 public:
25 ProtoBitmask();
26 ~ProtoBitmask();
27
28 bool Init(UINT32 numBits);
29 void Destroy();
30 UINT32 Size() {return num_bits;} // (TBD) change to "GetSize()"
31 void Clear() // set to all zero's
32 {
33 memset(mask, 0, mask_len);
34 first_set = num_bits;
35 };
36 void Reset() // set to all one's
37 {
38 memset(mask, 0xff, (mask_len-1));
39 mask[mask_len-1] = 0x00ff << ((8 - (num_bits & 0x07)) & 0x07);
40 first_set = 0;
41 }
42
43 bool IsSet() const {return (first_set < num_bits);}
44 bool GetFirstSet(UINT32& index) const
45 {
46 index = first_set;
47 return IsSet();
48 }
49
50 bool GetLastSet(UINT32& index) const
51 {
52 index = num_bits - 1;
53 return GetPrevSet(index);
54 }
55 bool Test(UINT32 index) const
56 {
57 return ((index < num_bits) ?
58 (0 != (mask[(index >> 3)] & (0x80 >> (index & 0x07)))) :
59 false);
60 }
61 bool CanSet(UINT32 index) const
62 {return (index < num_bits);}
63
64 bool Set(UINT32 index)
65 {
66 if (index < num_bits)
67 {
68 mask[(index >> 3)] |= (0x80 >> (index & 0x07));
69 (index < first_set) ? (first_set = index) : 0;
70 return true;
71 }
72 else
73 {
74 return false;
75 }
76 }
77 bool Unset(UINT32 index)
78 {
79 if (index < num_bits)
80 {
81 mask[(index >> 3)] &= ~(0x80 >> (index & 0x07));
82 (index == first_set) ? first_set = GetNextSet(first_set) ? first_set : num_bits : 0;
83 }
84 return true;
85 }
86 bool Invert(UINT32 index)
87 {return (Test(index) ? Unset(index) : Set(index));}
88
89 bool SetBits(UINT32 baseIndex, UINT32 count);
90 bool UnsetBits(UINT32 baseIndex, UINT32 count);
91
92 bool GetNextSet(UINT32& index) const;
93 bool GetPrevSet(UINT32& index) const;
94 bool GetNextUnset(UINT32& index) const;
95
96 bool Copy(const ProtoBitmask &b); // this = b
97 bool Add(const ProtoBitmask & b); // this = this | b
98 bool Subtract(const ProtoBitmask & b); // this = this & ~b
99 bool XCopy(const ProtoBitmask & b); // this = ~this & b
100 bool Multiply(const ProtoBitmask & b); // this = this & b
101 bool Xor(const ProtoBitmask & b); // this = this ^ b
102
103
104 static unsigned char GetWeight(unsigned char c)
105 {return WEIGHT[c];}
106
107 static const unsigned char WEIGHT[256];
108 static const unsigned char BITLOCS[256][8];
109
110 void Display(FILE* stream);
111
112 // Members
113 //private:
114 unsigned char* mask;
115 UINT32 mask_len;
116 UINT32 num_bits;
117 UINT32 first_set; // index of lowest _set_ bit
118 }; // end class ProtoBitmask
119
120
121
122 /**
123 * @class ProtoSlidingMask
124 *
125 * @brief This class also provides space-efficient binary storage.
126 *
127 * More than just a flat-indexed array of bits, this
128 * class can also automatically act as a sliding
129 * window buffer as long as the range of _set_ bit
130 * indices fall within the number of storage bits
131 * for which the class initialized.
132 */
133 // (TBD) This class could be improved if we byte-aligned the offset?
134
135 class ProtoSlidingMask
136 {
137 public:
138 ProtoSlidingMask();
139 ~ProtoSlidingMask();
140
141 const char* GetMask() const {return (const char*)mask;}
142
143 bool Init(UINT32 numBits, UINT32 rangeMask);
144 bool Resize(UINT32 numBits);
145 void Destroy();
146 UINT32 GetSize() const {return num_bits;}
147 void Clear()
148 {
149 memset(mask, 0, mask_len);
150 start = end = num_bits;
151 offset = 0;
152 }
153 void Reset(UINT32 index = 0)
154 {
155 ASSERT(0 != num_bits);
156 memset(mask, 0xff, mask_len);
157 mask[mask_len-1] = 0x00ff << ((8 - (num_bits & 0x07)) & 0x07);
158 start = 0;
159 end = num_bits - 1;
160 offset = index;
161 if (range_mask) offset &= range_mask;
162 }
163 bool IsSet() const {return (start < num_bits);}
164 bool GetFirstSet(UINT32& index) const
165 {
166 index = offset;
167 return IsSet();
168 }
169 bool GetLastSet(UINT32& index) const
170 {
171 UINT32 n = (end < start) ?
172 (num_bits - (start - end)) :
173 (end - start);
174 index = offset + n;
175 if (range_mask) index &= range_mask;
176 return IsSet();
177 }
178 bool Test(UINT32 index) const;
179 bool CanSet(UINT32 index) const;
180
181 bool Set(UINT32 index);
182 bool Unset(UINT32 index);
183 bool Invert(UINT32 index)
184 {return (Test(index) ? Unset(index): Set(index));}
185
186 bool SetBits(UINT32 index, UINT32 count);
187 bool UnsetBits(UINT32 index, UINT32 count);
188
189 UINT32 GetRangeMask() const {return range_mask;}
190 UINT32 GetRangeSign() const {return range_sign;}
191
192 // These return "false" when finding nothing
193 bool GetNextSet(UINT32& index) const;
194 bool GetPrevSet(UINT32& index) const;
195
196 bool Copy(const ProtoSlidingMask& b); // this = b
197 bool Add(const ProtoSlidingMask & b); // this = this | b
198 bool Subtract(const ProtoSlidingMask & b); // this = this & ~b
199 bool XCopy(const ProtoSlidingMask & b); // this = ~this & b
200 bool Multiply(const ProtoSlidingMask & b); // this = this & b
201 bool Xor(const ProtoSlidingMask & b); // this = this ^ b
202
203 void Display(FILE* stream);
204 void Debug(UINT32 theCount);
205
206 // Calculate "circular" delta between two indices
207 // (If (0 == range_mask) it is an absolute 32-bit delta
208 INT32 Difference(UINT32 a, UINT32 b) const
209 {
210 UINT32 result = a - b;
211 if (0 != range_mask)
212 {
213 return ((0 == (result & range_sign)) ?
214 (result & range_mask) :
215 (((result != range_sign) || (a < b)) ?
216 (INT32)(result | ~range_mask) : (INT32)result));
217 }
218 else
219 {
220 return (INT32)result;
221 }
222 }
223
224 // Compare values. If a non-zero bit "mask" is given, the comparison
225 // is a "sliding window" (signed) over the bit space. Otherwise, it is
226 // simply and unsigned value comparison.
227 // Returns -1, 0, +1 for (a < b), (a == b), and (a > b), respectively
228 int Compare(UINT32 a, UINT32 b) const
229 {
230 if (0 != range_mask)
231 {
232 // "Sliding window" comparison
233 INT32 delta = Difference(a, b);
234 if (delta < 0)
235 return -1;
236 else if (0 == delta)
237 return 0;
238 else // if delta > 0
239 return 1;
240 }
241 else if (a < b)
242 {
243 return -1;
244 }
245 else if (a == b)
246 {
247 return 0;
248 }
249 else //if (a > b)
250 {
251 return 1;
252 }
253 }
254
255 private:
256 unsigned char* mask;
257 UINT32 mask_len;
258 UINT32 range_mask;
259 UINT32 range_sign;
260 UINT32 num_bits;
261 UINT32 start;
262 UINT32 end;
263 UINT32 offset;
264 }; // end class ProtoSlidingMask
265
266 #endif // _PROTO_BITMASK_