Debian Codegraph @

protolib/src/common/protoBitmask.cpp

raw
1 /**
2 * @file protoBitmask.cpp
3 *
4 * @brief This class also provides space-efficient binary storage
5 */
6
7 #include "protoBitmask.h"
8 #include "protoDebug.h"
9 /**
10 * @file protoBitmask.cpp
11 *
12 * @brief This class provides space-efficient binary storage.
13 */
14
15 // Hamming weights for given one-byte bit masks
16 const unsigned char ProtoBitmask::WEIGHT[256] =
17 {
18 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
19 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
20 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
21 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
22 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
23 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
24 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
25 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
26 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
27 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
28 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
29 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
30 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
31 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
32 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
33 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
34 };
35
36 // Bit location vectors for given one-byte bit masks
37 const unsigned char ProtoBitmask::BITLOCS[256][8] =
38 {
39 {0, 0, 0, 0, 0, 0, 0, 0}, {7, 0, 0, 0, 0, 0, 0, 0},
40 {6, 0, 0, 0, 0, 0, 0, 0}, {6, 7, 0, 0, 0, 0, 0, 0},
41 {5, 0, 0, 0, 0, 0, 0, 0}, {5, 7, 0, 0, 0, 0, 0, 0},
42 {5, 6, 0, 0, 0, 0, 0, 0}, {5, 6, 7, 0, 0, 0, 0, 0},
43 {4, 0, 0, 0, 0, 0, 0, 0}, {4, 7, 0, 0, 0, 0, 0, 0},
44 {4, 6, 0, 0, 0, 0, 0, 0}, {4, 6, 7, 0, 0, 0, 0, 0},
45 {4, 5, 0, 0, 0, 0, 0, 0}, {4, 5, 7, 0, 0, 0, 0, 0},
46 {4, 5, 6, 0, 0, 0, 0, 0}, {4, 5, 6, 7, 0, 0, 0, 0},
47 {3, 0, 0, 0, 0, 0, 0, 0}, {3, 7, 0, 0, 0, 0, 0, 0},
48 {3, 6, 0, 0, 0, 0, 0, 0}, {3, 6, 7, 0, 0, 0, 0, 0},
49 {3, 5, 0, 0, 0, 0, 0, 0}, {3, 5, 7, 0, 0, 0, 0, 0},
50 {3, 5, 6, 0, 0, 0, 0, 0}, {3, 5, 6, 7, 0, 0, 0, 0},
51 {3, 4, 0, 0, 0, 0, 0, 0}, {3, 4, 7, 0, 0, 0, 0, 0},
52 {3, 4, 6, 0, 0, 0, 0, 0}, {3, 4, 6, 7, 0, 0, 0, 0},
53 {3, 4, 5, 0, 0, 0, 0, 0}, {3, 4, 5, 7, 0, 0, 0, 0},
54 {3, 4, 5, 6, 0, 0, 0, 0}, {3, 4, 5, 6, 7, 0, 0, 0},
55 {2, 0, 0, 0, 0, 0, 0, 0}, {2, 7, 0, 0, 0, 0, 0, 0},
56 {2, 6, 0, 0, 0, 0, 0, 0}, {2, 6, 7, 0, 0, 0, 0, 0},
57 {2, 5, 0, 0, 0, 0, 0, 0}, {2, 5, 7, 0, 0, 0, 0, 0},
58 {2, 5, 6, 0, 0, 0, 0, 0}, {2, 5, 6, 7, 0, 0, 0, 0},
59 {2, 4, 0, 0, 0, 0, 0, 0}, {2, 4, 7, 0, 0, 0, 0, 0},
60 {2, 4, 6, 0, 0, 0, 0, 0}, {2, 4, 6, 7, 0, 0, 0, 0},
61 {2, 4, 5, 0, 0, 0, 0, 0}, {2, 4, 5, 7, 0, 0, 0, 0},
62 {2, 4, 5, 6, 0, 0, 0, 0}, {2, 4, 5, 6, 7, 0, 0, 0},
63 {2, 3, 0, 0, 0, 0, 0, 0}, {2, 3, 7, 0, 0, 0, 0, 0},
64 {2, 3, 6, 0, 0, 0, 0, 0}, {2, 3, 6, 7, 0, 0, 0, 0},
65 {2, 3, 5, 0, 0, 0, 0, 0}, {2, 3, 5, 7, 0, 0, 0, 0},
66 {2, 3, 5, 6, 0, 0, 0, 0}, {2, 3, 5, 6, 7, 0, 0, 0},
67 {2, 3, 4, 0, 0, 0, 0, 0}, {2, 3, 4, 7, 0, 0, 0, 0},
68 {2, 3, 4, 6, 0, 0, 0, 0}, {2, 3, 4, 6, 7, 0, 0, 0},
69 {2, 3, 4, 5, 0, 0, 0, 0}, {2, 3, 4, 5, 7, 0, 0, 0},
70 {2, 3, 4, 5, 6, 0, 0, 0}, {2, 3, 4, 5, 6, 7, 0, 0},
71 {1, 0, 0, 0, 0, 0, 0, 0}, {1, 7, 0, 0, 0, 0, 0, 0},
72 {1, 6, 0, 0, 0, 0, 0, 0}, {1, 6, 7, 0, 0, 0, 0, 0},
73 {1, 5, 0, 0, 0, 0, 0, 0}, {1, 5, 7, 0, 0, 0, 0, 0},
74 {1, 5, 6, 0, 0, 0, 0, 0}, {1, 5, 6, 7, 0, 0, 0, 0},
75 {1, 4, 0, 0, 0, 0, 0, 0}, {1, 4, 7, 0, 0, 0, 0, 0},
76 {1, 4, 6, 0, 0, 0, 0, 0}, {1, 4, 6, 7, 0, 0, 0, 0},
77 {1, 4, 5, 0, 0, 0, 0, 0}, {1, 4, 5, 7, 0, 0, 0, 0},
78 {1, 4, 5, 6, 0, 0, 0, 0}, {1, 4, 5, 6, 7, 0, 0, 0},
79 {1, 3, 0, 0, 0, 0, 0, 0}, {1, 3, 7, 0, 0, 0, 0, 0},
80 {1, 3, 6, 0, 0, 0, 0, 0}, {1, 3, 6, 7, 0, 0, 0, 0},
81 {1, 3, 5, 0, 0, 0, 0, 0}, {1, 3, 5, 7, 0, 0, 0, 0},
82 {1, 3, 5, 6, 0, 0, 0, 0}, {1, 3, 5, 6, 7, 0, 0, 0},
83 {1, 3, 4, 0, 0, 0, 0, 0}, {1, 3, 4, 7, 0, 0, 0, 0},
84 {1, 3, 4, 6, 0, 0, 0, 0}, {1, 3, 4, 6, 7, 0, 0, 0},
85 {1, 3, 4, 5, 0, 0, 0, 0}, {1, 3, 4, 5, 7, 0, 0, 0},
86 {1, 3, 4, 5, 6, 0, 0, 0}, {1, 3, 4, 5, 6, 7, 0, 0},
87 {1, 2, 0, 0, 0, 0, 0, 0}, {1, 2, 7, 0, 0, 0, 0, 0},
88 {1, 2, 6, 0, 0, 0, 0, 0}, {1, 2, 6, 7, 0, 0, 0, 0},
89 {1, 2, 5, 0, 0, 0, 0, 0}, {1, 2, 5, 7, 0, 0, 0, 0},
90 {1, 2, 5, 6, 0, 0, 0, 0}, {1, 2, 5, 6, 7, 0, 0, 0},
91 {1, 2, 4, 0, 0, 0, 0, 0}, {1, 2, 4, 7, 0, 0, 0, 0},
92 {1, 2, 4, 6, 0, 0, 0, 0}, {1, 2, 4, 6, 7, 0, 0, 0},
93 {1, 2, 4, 5, 0, 0, 0, 0}, {1, 2, 4, 5, 7, 0, 0, 0},
94 {1, 2, 4, 5, 6, 0, 0, 0}, {1, 2, 4, 5, 6, 7, 0, 0},
95 {1, 2, 3, 0, 0, 0, 0, 0}, {1, 2, 3, 7, 0, 0, 0, 0},
96 {1, 2, 3, 6, 0, 0, 0, 0}, {1, 2, 3, 6, 7, 0, 0, 0},
97 {1, 2, 3, 5, 0, 0, 0, 0}, {1, 2, 3, 5, 7, 0, 0, 0},
98 {1, 2, 3, 5, 6, 0, 0, 0}, {1, 2, 3, 5, 6, 7, 0, 0},
99 {1, 2, 3, 4, 0, 0, 0, 0}, {1, 2, 3, 4, 7, 0, 0, 0},
100 {1, 2, 3, 4, 6, 0, 0, 0}, {1, 2, 3, 4, 6, 7, 0, 0},
101 {1, 2, 3, 4, 5, 0, 0, 0}, {1, 2, 3, 4, 5, 7, 0, 0},
102 {1, 2, 3, 4, 5, 6, 0, 0}, {1, 2, 3, 4, 5, 6, 7, 0},
103 {0, 0, 0, 0, 0, 0, 0, 0}, {0, 7, 0, 0, 0, 0, 0, 0},
104 {0, 6, 0, 0, 0, 0, 0, 0}, {0, 6, 7, 0, 0, 0, 0, 0},
105 {0, 5, 0, 0, 0, 0, 0, 0}, {0, 5, 7, 0, 0, 0, 0, 0},
106 {0, 5, 6, 0, 0, 0, 0, 0}, {0, 5, 6, 7, 0, 0, 0, 0},
107 {0, 4, 0, 0, 0, 0, 0, 0}, {0, 4, 7, 0, 0, 0, 0, 0},
108 {0, 4, 6, 0, 0, 0, 0, 0}, {0, 4, 6, 7, 0, 0, 0, 0},
109 {0, 4, 5, 0, 0, 0, 0, 0}, {0, 4, 5, 7, 0, 0, 0, 0},
110 {0, 4, 5, 6, 0, 0, 0, 0}, {0, 4, 5, 6, 7, 0, 0, 0},
111 {0, 3, 0, 0, 0, 0, 0, 0}, {0, 3, 7, 0, 0, 0, 0, 0},
112 {0, 3, 6, 0, 0, 0, 0, 0}, {0, 3, 6, 7, 0, 0, 0, 0},
113 {0, 3, 5, 0, 0, 0, 0, 0}, {0, 3, 5, 7, 0, 0, 0, 0},
114 {0, 3, 5, 6, 0, 0, 0, 0}, {0, 3, 5, 6, 7, 0, 0, 0},
115 {0, 3, 4, 0, 0, 0, 0, 0}, {0, 3, 4, 7, 0, 0, 0, 0},
116 {0, 3, 4, 6, 0, 0, 0, 0}, {0, 3, 4, 6, 7, 0, 0, 0},
117 {0, 3, 4, 5, 0, 0, 0, 0}, {0, 3, 4, 5, 7, 0, 0, 0},
118 {0, 3, 4, 5, 6, 0, 0, 0}, {0, 3, 4, 5, 6, 7, 0, 0},
119 {0, 2, 0, 0, 0, 0, 0, 0}, {0, 2, 7, 0, 0, 0, 0, 0},
120 {0, 2, 6, 0, 0, 0, 0, 0}, {0, 2, 6, 7, 0, 0, 0, 0},
121 {0, 2, 5, 0, 0, 0, 0, 0}, {0, 2, 5, 7, 0, 0, 0, 0},
122 {0, 2, 5, 6, 0, 0, 0, 0}, {0, 2, 5, 6, 7, 0, 0, 0},
123 {0, 2, 4, 0, 0, 0, 0, 0}, {0, 2, 4, 7, 0, 0, 0, 0},
124 {0, 2, 4, 6, 0, 0, 0, 0}, {0, 2, 4, 6, 7, 0, 0, 0},
125 {0, 2, 4, 5, 0, 0, 0, 0}, {0, 2, 4, 5, 7, 0, 0, 0},
126 {0, 2, 4, 5, 6, 0, 0, 0}, {0, 2, 4, 5, 6, 7, 0, 0},
127 {0, 2, 3, 0, 0, 0, 0, 0}, {0, 2, 3, 7, 0, 0, 0, 0},
128 {0, 2, 3, 6, 0, 0, 0, 0}, {0, 2, 3, 6, 7, 0, 0, 0},
129 {0, 2, 3, 5, 0, 0, 0, 0}, {0, 2, 3, 5, 7, 0, 0, 0},
130 {0, 2, 3, 5, 6, 0, 0, 0}, {0, 2, 3, 5, 6, 7, 0, 0},
131 {0, 2, 3, 4, 0, 0, 0, 0}, {0, 2, 3, 4, 7, 0, 0, 0},
132 {0, 2, 3, 4, 6, 0, 0, 0}, {0, 2, 3, 4, 6, 7, 0, 0},
133 {0, 2, 3, 4, 5, 0, 0, 0}, {0, 2, 3, 4, 5, 7, 0, 0},
134 {0, 2, 3, 4, 5, 6, 0, 0}, {0, 2, 3, 4, 5, 6, 7, 0},
135 {0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 7, 0, 0, 0, 0, 0},
136 {0, 1, 6, 0, 0, 0, 0, 0}, {0, 1, 6, 7, 0, 0, 0, 0},
137 {0, 1, 5, 0, 0, 0, 0, 0}, {0, 1, 5, 7, 0, 0, 0, 0},
138 {0, 1, 5, 6, 0, 0, 0, 0}, {0, 1, 5, 6, 7, 0, 0, 0},
139 {0, 1, 4, 0, 0, 0, 0, 0}, {0, 1, 4, 7, 0, 0, 0, 0},
140 {0, 1, 4, 6, 0, 0, 0, 0}, {0, 1, 4, 6, 7, 0, 0, 0},
141 {0, 1, 4, 5, 0, 0, 0, 0}, {0, 1, 4, 5, 7, 0, 0, 0},
142 {0, 1, 4, 5, 6, 0, 0, 0}, {0, 1, 4, 5, 6, 7, 0, 0},
143 {0, 1, 3, 0, 0, 0, 0, 0}, {0, 1, 3, 7, 0, 0, 0, 0},
144 {0, 1, 3, 6, 0, 0, 0, 0}, {0, 1, 3, 6, 7, 0, 0, 0},
145 {0, 1, 3, 5, 0, 0, 0, 0}, {0, 1, 3, 5, 7, 0, 0, 0},
146 {0, 1, 3, 5, 6, 0, 0, 0}, {0, 1, 3, 5, 6, 7, 0, 0},
147 {0, 1, 3, 4, 0, 0, 0, 0}, {0, 1, 3, 4, 7, 0, 0, 0},
148 {0, 1, 3, 4, 6, 0, 0, 0}, {0, 1, 3, 4, 6, 7, 0, 0},
149 {0, 1, 3, 4, 5, 0, 0, 0}, {0, 1, 3, 4, 5, 7, 0, 0},
150 {0, 1, 3, 4, 5, 6, 0, 0}, {0, 1, 3, 4, 5, 6, 7, 0},
151 {0, 1, 2, 0, 0, 0, 0, 0}, {0, 1, 2, 7, 0, 0, 0, 0},
152 {0, 1, 2, 6, 0, 0, 0, 0}, {0, 1, 2, 6, 7, 0, 0, 0},
153 {0, 1, 2, 5, 0, 0, 0, 0}, {0, 1, 2, 5, 7, 0, 0, 0},
154 {0, 1, 2, 5, 6, 0, 0, 0}, {0, 1, 2, 5, 6, 7, 0, 0},
155 {0, 1, 2, 4, 0, 0, 0, 0}, {0, 1, 2, 4, 7, 0, 0, 0},
156 {0, 1, 2, 4, 6, 0, 0, 0}, {0, 1, 2, 4, 6, 7, 0, 0},
157 {0, 1, 2, 4, 5, 0, 0, 0}, {0, 1, 2, 4, 5, 7, 0, 0},
158 {0, 1, 2, 4, 5, 6, 0, 0}, {0, 1, 2, 4, 5, 6, 7, 0},
159 {0, 1, 2, 3, 0, 0, 0, 0}, {0, 1, 2, 3, 7, 0, 0, 0},
160 {0, 1, 2, 3, 6, 0, 0, 0}, {0, 1, 2, 3, 6, 7, 0, 0},
161 {0, 1, 2, 3, 5, 0, 0, 0}, {0, 1, 2, 3, 5, 7, 0, 0},
162 {0, 1, 2, 3, 5, 6, 0, 0}, {0, 1, 2, 3, 5, 6, 7, 0},
163 {0, 1, 2, 3, 4, 0, 0, 0}, {0, 1, 2, 3, 4, 7, 0, 0},
164 {0, 1, 2, 3, 4, 6, 0, 0}, {0, 1, 2, 3, 4, 6, 7, 0},
165 {0, 1, 2, 3, 4, 5, 0, 0}, {0, 1, 2, 3, 4, 5, 7, 0},
166 {0, 1, 2, 3, 4, 5, 6, 0}, {0, 1, 2, 3, 4, 5, 6, 7}
167 };
168
169 // TBD - We can reimplement ProtoBitmask to used "unsigned int"
170 // words instead of "unsigned char" for its "mask" array.
171 // Instead of the BITLOCS[][] lookup, we can use the
172 // approach where the least signficant set bit for 'x' can
173 // be determined with "leastSetBit = (x & -x);"
174 //
175 // Here's code to set bits and get the next set bit for a given "index"
176 // (Note index zero is the least significant bit of word[0] here)
177 //
178 // void SetBit(unsigned int* mask, unsigned int index)
179 // {
180 // const unsigned int BITS_PER_WORD = 8*sizeof(unsigned int);
181 // const unsigned int BSHIFT = log2(BITS_PER_WORD);
182 // const unsigned int BMASK = (BITS_PER_WORD - 1);
183 // mask[(index >> BSHIFT)] |= (0x00000001 << (index & BMASK));
184 // }
185 //
186 // // Returns index of next set bit >= index
187 // bool GetNextSetBit(unsigned int* mask, unsigned int maskWords, unsigned int &index)
188 // {
189 // const unsigned int BONES = ((unsigned int)-1); // all ones
190 // const unsigned int BITS_PER_WORD = 8*sizeof(unsigned int);
191 // const unsigned int BSHIFT = log2(BITS_PER_WORD);
192 // const unsigned int BMASK = (BITS_PER_WORD - 1);
193 //
194 // unsigned int maskIndex = index >> BSHIFT;
195 // unsigned int word = mask[maskIndex];
196 // if (0 != word)
197 // {
198 // unsigned int bitIndex = index & BMASK;
199 // word &= BONES << bitIndex ; // mask bits < bitIndex
200 // if (0 != word)
201 // {
202 // unsigned int nextSet = (word & -word);
203 // if (0 != nextSet)
204 // {
205 // unsigned int bitOffset = 0;
206 // while (0 != (nextSet >>= 1)) bitOffset++;
207 // index = (maskIndex << BSHIFT) + bitOffset;
208 // return true;
209 // }
210 // }
211 // }
212 // while (++maskIndex < maskWords)
213 // {
214 // word = mask[maskIndex];
215 // if (0 != word)
216 // {
217 // unsigned int nextSet = (word & -word);
218 // if (0 != nextSet)
219 // {
220 // unsigned int bitOffset = 0;
221 // while (0 != (nextSet >>= 1)) bitOffset++;
222 // index = (maskIndex << BSHIFT) + bitOffset;
223 // return true;
224 // }
225 // }
226 // }
227 // return false; // nothing was set
228 // } // end GetNextSetBit()
229
230
231 ProtoBitmask::ProtoBitmask()
232 : mask(NULL), mask_len(0),
233 num_bits(0), first_set(0)
234 {
235 }
236
237 ProtoBitmask::~ProtoBitmask()
238 {
239 Destroy();
240 }
241
242 bool ProtoBitmask::Init(UINT32 numBits)
243 {
244 if (mask) Destroy();
245 // Allocate memory for mask
246 unsigned int len = (numBits + 7) >> 3;
247 if ((mask = new unsigned char[len]))
248 {
249 num_bits = numBits;
250 mask_len = len;
251 Clear();
252 return true;
253 }
254 else
255 {
256 return false;
257 }
258
259 } // end ProtoBitmask::Init()
260
261 void ProtoBitmask::Destroy()
262 {
263 if (mask)
264 {
265 delete[] mask;
266 mask = (unsigned char*)NULL;
267 num_bits = first_set = 0;
268 }
269 } // end ProtoBitmask::Destroy()
270
271
272 bool ProtoBitmask::GetNextSet(UINT32& index) const
273 {
274 if (index >= num_bits) return false;
275 if (index < first_set) return GetFirstSet(index);
276 UINT32 maskIndex = index >> 3;
277 if (mask[maskIndex])
278 {
279 int w = WEIGHT[mask[maskIndex]];
280 int remainder = index & 0x07;
281 for (int i = 0; i < w; i++)
282 {
283 int loc = BITLOCS[mask[maskIndex]][i];
284 if (loc >= remainder)
285 {
286 index = (maskIndex << 3) + loc;
287 return true;
288 }
289 }
290 }
291 while(++maskIndex < mask_len)
292 {
293 if (mask[maskIndex])
294 {
295 index = (maskIndex << 3) + BITLOCS[mask[maskIndex]][0];
296 return true;
297 }
298 }
299 return false;
300 } // end ProtoBitmask::NextSet()
301
302 bool ProtoBitmask::GetPrevSet(UINT32& index) const
303 {
304 if (index >= num_bits) index = num_bits - 1;
305 if (index < first_set) return false;
306 UINT32 maskIndex = index >> 3;
307 if (mask[maskIndex])
308 {
309 int w = WEIGHT[mask[maskIndex]] - 1;
310 int remainder = index & 0x07;
311 for (int i = w; i >= 0; i--)
312 {
313 int loc = BITLOCS[mask[maskIndex]][i];
314 if (loc <= remainder)
315 {
316 index = ((maskIndex << 3) + loc);
317 return true;
318 }
319 }
320 }
321 maskIndex--;
322 UINT32 startIndex = first_set >> 3;
323 for (; maskIndex >= startIndex; maskIndex--)
324 {
325 if (0 != mask[maskIndex])
326 {
327 int w = WEIGHT[mask[maskIndex]] - 1;
328 index = ((maskIndex << 3) + BITLOCS[mask[maskIndex]][w]);
329 return true;
330 }
331 }
332 return false; // (nothing prior was set)
333 } // end ProtoBitmask::GetPrevSet()
334
335 bool ProtoBitmask::GetNextUnset(UINT32& index) const
336 {
337 if (index >= num_bits) return false;
338 UINT32 next = index;
339 UINT32 maskIndex = next >> 3;
340 unsigned char bit = 0x80 >> (next & 0x07);
341 while (next < num_bits)
342 {
343 unsigned char val = mask[maskIndex];
344 if (val)
345 {
346 while (bit && (next < num_bits))
347 {
348 if (0 == (val & bit))
349 {
350 index = next;
351 return true;
352 }
353 next++;
354 bit >>= 0x01;
355 }
356 bit = 0x80;
357 maskIndex++;
358 }
359 else
360 {
361 index = next;
362 return true;
363 }
364 }
365 return false;
366 } // end ProtoBitmask::GetNextUnset()
367
368
369 bool ProtoBitmask::SetBits(UINT32 index, UINT32 count)
370 {
371 if (0 == count) return true;
372 if ((index+count) > num_bits) return false;
373 UINT32 maskIndex = index >> 3;
374 // To set appropriate bits in first byte
375 unsigned int bitIndex = index & 0x07;
376 unsigned int bitRemainder = 8 - bitIndex;
377 if (count <= bitRemainder)
378 {
379 mask[maskIndex] |= (0x00ff >> bitIndex) &
380 (0x00ff << (bitRemainder - count));
381 }
382 else
383 {
384 mask[maskIndex] |= 0x00ff >> bitIndex;
385 count -= bitRemainder;
386 UINT32 nbytes = count >> 3;
387 memset(&mask[++maskIndex], 0xff, nbytes);
388 count &= 0x07;
389 if (count)
390 mask[maskIndex+nbytes] |= 0xff << (8-count);
391 }
392 if (index < first_set) first_set = index;
393 return true;
394 } // end ProtoBitmask::SetBits()
395
396
397 bool ProtoBitmask::UnsetBits(UINT32 index, UINT32 count)
398 {
399 if ((index >= num_bits)|| (0 == count)) return true;
400 UINT32 end = index + count;
401 if (end > num_bits)
402 {
403 end = num_bits;
404 count = end - index;
405 }
406 UINT32 maskIndex = index >> 3;
407 // To unset appropriate bits in first byte
408 unsigned int bitIndex = index & 0x07;
409 unsigned int bitRemainder = 8 - bitIndex;
410 if (count <= bitRemainder)
411 {
412 mask[maskIndex] &= (0x00ff << bitRemainder) |
413 (0x00ff >> (bitIndex + count));
414 }
415 else
416 {
417 mask[maskIndex] &= 0x00ff << bitRemainder;
418 count -= bitRemainder;
419 UINT32 nbytes = count >> 3;
420 memset(&mask[++maskIndex], 0, nbytes);
421 count &= 0x07;
422 if (count) mask[maskIndex+nbytes] &= 0xff >> count;
423 }
424 if ((first_set >= index) && (end > first_set))
425 {
426 first_set = end;
427 if (!GetNextSet(first_set)) first_set = num_bits;
428 }
429 return true;
430 } // end ProtoBitmask::UnsetBits()
431
432 // this = b
433 bool ProtoBitmask::Copy(const ProtoBitmask &b)
434 {
435 if (b.num_bits > num_bits) return false;
436 memcpy(mask, b.mask, b.mask_len);
437 (mask_len > b.mask_len) ?
438 memset(mask+b.mask_len, 0, mask_len - b.mask_len) : 0;
439 first_set = (b.first_set < b.num_bits) ? b.first_set : num_bits;
440 return true;
441 } // end ProtoBitmask::Copy()
442
443 // this = this | b
444 bool ProtoBitmask::Add(const ProtoBitmask& b)
445 {
446 if (b.num_bits > num_bits) return false;
447 for(unsigned int i = 0; i < b.mask_len; i++)
448 mask[i] |= b.mask[i];
449 if ((b.first_set < first_set) &&
450 (b.first_set < b.num_bits))
451 first_set = b.first_set;
452 return true;
453 } // end ProtoBitmask::Add()
454
455 // this = this & ~b
456 bool ProtoBitmask::Subtract(const ProtoBitmask& b)
457 {
458 UINT32 len = (mask_len < b.mask_len) ? mask_len : b.mask_len;
459 for(UINT32 i = 0; i < len; i++)
460 mask[i] &= ~b.mask[i];
461 if (first_set >= b.first_set)
462 {
463 if (!GetNextSet(first_set)) first_set = num_bits;
464 }
465 return true;
466 } // end ProtoBitmask::Subtract()
467
468
469 // this = ~this & b (this = b - this)
470 // (i.e., this is set to the bits uniquely set in 'b')
471 bool ProtoBitmask::XCopy(const ProtoBitmask& b)
472 {
473 if (!b.IsSet())
474 {
475 Clear();
476 return true;
477 }
478 if (b.num_bits > num_bits) return false;
479 unsigned int len = b.mask_len;
480 unsigned int begin = b.first_set >> 3;
481 if (begin) memset(mask, 0, begin);
482 for (unsigned int i = begin; i < len; i++)
483 mask[i] = b.mask[i] & ~mask[i];
484 if (len < mask_len) memset(&mask[len], 0, mask_len - len);
485 UINT32 theFirst = (b.first_set < b.num_bits) ? b.first_set : num_bits;
486 if (theFirst < first_set)
487 {
488 first_set = b.first_set;
489 }
490 else
491 {
492 first_set = theFirst;
493 if (!GetNextSet(first_set)) first_set = num_bits;
494 }
495 return true;
496 } // end ProtoBitmask::XCopy()
497
498 // this = this & b
499 bool ProtoBitmask::Multiply(const ProtoBitmask& b)
500 {
501 UINT32 len = (mask_len < b.mask_len) ? mask_len : b.mask_len;
502 for(unsigned int i = 0; i < len; i++)
503 mask[i] |= b.mask[i];
504 if (len < mask_len) memset(&mask[len], 0, mask_len - len);
505
506 if (b.first_set > first_set)
507 {
508 first_set = b.first_set;
509 if (!GetNextSet(first_set)) first_set = num_bits;
510 }
511 else if (first_set > b.first_set)
512 {
513 if (!GetNextSet(first_set)) first_set = num_bits;
514 }
515 return true;
516 } // end ProtoBitmask::Multiply()
517
518 // this = this ^ b
519 bool ProtoBitmask::Xor(const ProtoBitmask& b)
520 {
521 // Does "b" have any bits set?
522 if (!b.IsSet()) return true;
523 if (b.num_bits > num_bits) return false;
524 for(unsigned int i = 0; i < b.mask_len; i++)
525 mask[i] ^= b.mask[i];
526 if (b.first_set == first_set)
527 {
528 if (!GetNextSet(first_set)) first_set = num_bits;
529 }
530 else if (b.first_set < first_set)
531 {
532 first_set = b.first_set;
533 }
534 return true;
535 } // end ProtoBitmask::Xor()
536
537 void ProtoBitmask::Display(FILE* stream)
538 {
539 UINT32 index = 0;
540 for (UINT32 i = 0; i < num_bits; i++)
541 {
542 if (Test(index++)) fprintf(stream, "1"); else fprintf(stream, "0");
543 if (0x07 == (i & 0x07)) fprintf(stream, " ");
544 if (0x3f == (i & 0x3f)) fprintf(stream, "\n");
545 }
546 } // end ProtoBitmask::Display()
547
548
549 ProtoSlidingMask::ProtoSlidingMask()
550 : mask((unsigned char*)NULL), mask_len(0), num_bits(0),
551 start(0), end(0), offset(0)
552 {
553 }
554
555
556 ProtoSlidingMask::~ProtoSlidingMask()
557 {
558 Destroy();
559 }
560
561 bool ProtoSlidingMask::Init(UINT32 numBits, UINT32 rangeMask)
562 {
563 if (mask) Destroy();
564 if ((0 != rangeMask) && (numBits > ((rangeMask>>1)+1)))
565 return false;
566 UINT32 len = (numBits + 7) >> 3;
567 if ((mask = new unsigned char[len]))
568 {
569 range_mask = rangeMask;
570 range_sign = rangeMask ? (rangeMask ^ (rangeMask >> 1)) : 0;
571 mask_len = len;
572 num_bits = numBits;
573 Clear();
574 return true;
575 }
576 else
577 {
578 return false;
579 }
580 } // end ProtoSlidingMask::Init()
581
582 bool ProtoSlidingMask::Resize(UINT32 numBits)
583 {
584 // 1) Backup the current state
585 ProtoSlidingMask tempMask = *this;
586 // 2) Prune if needed.
587 if (numBits < num_bits)
588 {
589 UINT32 endex = offset + numBits;
590 if (range_mask) endex &= range_mask;
591 tempMask.UnsetBits(endex, num_bits-numBits);
592 }
593 // 3) Re-init w/ new "numBits"
594 mask = NULL;
595 bool result = Init(numBits, range_mask);
596 if (result)
597 {
598 // 4) Copy old mask content
599 result = Copy(tempMask);
600 ASSERT(result);
601 }
602 else
603 {
604 *this = tempMask;
605 tempMask.mask = NULL;
606 }
607 tempMask.Destroy();
608 return result;
609 } // end ProtoSlidingMask::Resize()
610
611 void ProtoSlidingMask::Destroy()
612 {
613 if (NULL != mask)
614 {
615 delete[] mask;
616 mask = NULL;
617 mask_len = num_bits = start = end = offset = 0;
618 }
619 } // end ProtoSlidingMask::Destroy()
620
621 bool ProtoSlidingMask::CanSet(UINT32 index) const
622 {
623 ASSERT((0 == range_mask) || (index <= range_mask));
624 if (IsSet())
625 {
626 // Determine position with respect to current start
627 // and end, given the "offset" of the current start
628 if (Compare(index, offset) < 0)
629 {
630 // Precedes start.
631 INT32 deltaPos = start + Difference(index, offset);;
632 if (deltaPos < 0) deltaPos += num_bits;
633 if (deltaPos < 0)
634 {
635 // out of range
636 return false;
637 }
638 else
639 {
640 // Is pos between end & start?
641 UINT32 pos = (UINT32)deltaPos;
642 if (end < start)
643 {
644 if ((pos <= end) || (pos >= start)) return false;
645 }
646 else
647 {
648 if ((pos <= end) && (pos >= start)) return false;
649 }
650 return true;
651 }
652 }
653 else if ((UINT32)Difference(index, offset) < num_bits)
654 {
655 return true;
656 }
657 else
658 {
659 return false; // out of range
660 }
661 }
662 else
663 {
664 return true; // empty mask can be set in any fashion
665 }
666 } // end ProtoSlidingMask::CanSet()
667
668 bool ProtoSlidingMask::Set(UINT32 index)
669 {
670 ASSERT((0 == range_mask) || (index <= range_mask));
671 if (IsSet())
672 {
673 // Determine position with respect to current start
674 // and end, given the "offset" of the current start
675 UINT32 pos;
676 if (Compare(index, offset) < 0)
677 {
678 // Precedes start.
679 INT32 deltaPos = start + Difference(index, offset);
680 if (deltaPos < 0) deltaPos += num_bits;
681 if (deltaPos < 0)
682 {
683 // out of range
684 return false;
685 }
686 else
687 {
688 pos = (UINT32)deltaPos;
689 // Is pos between end & start?
690 if (end < start)
691 {
692 if ((pos <= end) || (pos >= start)) return false; // Brian fix 14 Mar 2011 >= start
693 }
694 else
695 {
696 if ((pos <= end) && (pos >= start)) return false; // Brian fix 17 JUL 2007 >= start
697 }
698 // Ok for new "start" && "offset"
699 start = pos;
700 offset = index;
701 }
702 }
703 else
704 {
705 pos = Difference(index, offset);
706 if (pos < num_bits)
707 {
708 pos += start;
709 if (pos >= num_bits) pos -= num_bits;
710 if (end < start)
711 {
712 if ((pos < start) && (pos > end)) end = pos;
713 }
714 else
715 {
716 if ((pos > end) || (pos < start)) end = pos;
717 }
718 }
719 else
720 {
721 return false; // out of range
722 }
723 }
724 ASSERT((pos >> 3) >= 0);
725 ASSERT((pos >> 3) < mask_len);
726 mask[(pos >> 3)] |= (0x80 >> (pos & 0x07));
727 }
728 else
729 {
730 start = end = 0;
731 offset = index;
732 mask[0] = 0x80;
733 }
734 return true;
735 } // end ProtoSlidingMask::Set()
736
737 bool ProtoSlidingMask::Unset(UINT32 index)
738 {
739 ASSERT((0 == range_mask) || (index <= range_mask));
740 if (IsSet())
741 {
742 if (Compare(index, offset) < 0)
743 {
744 return true; // out-of-range
745 }
746 else
747 {
748 UINT32 pos = Difference(index, offset);
749 if (pos < num_bits)
750 {
751 // Is it in current range of set bits?
752 pos += start;
753 if (pos >= num_bits) pos -= num_bits;
754 if (end < start)
755 {
756 if ((pos > end) && (pos < start)) return true;
757 }
758 else
759 {
760 if ((pos < start) || (pos > end)) return true;
761 }
762 // Yes, it was in range.
763 // Unset the corresponding bit
764 ASSERT((pos >> 3) >= 0);
765 ASSERT((pos >> 3) < mask_len);
766 mask[(pos >> 3)] &= ~(0x80 >> (pos & 0x07));
767 if (start == end)
768 {
769 ASSERT(pos == start);
770 start = end = num_bits;
771 return true;
772 }
773 if (start == pos)
774 {
775 UINT32 next = index;
776 if (!GetNextSet(next))
777 ASSERT(0);
778 ASSERT(Compare(next, offset) >= 0);
779 UINT32 delta = Difference(next, offset);
780 start += delta;
781 if (start >= num_bits) start -= num_bits;
782 offset = next;
783 }
784 if (pos == end)
785 {
786 UINT32 prev = index;
787 if (!GetPrevSet(prev))
788 ASSERT(0);
789 ASSERT(Compare(prev, offset) >= 0);
790 UINT32 delta = Difference(prev, offset);
791 end = start + delta;
792 if (end >= num_bits) end -= num_bits;
793 }
794 }
795 else
796 {
797 return true; // out-of-range
798 }
799 }
800 }
801 return true;
802 } // end ProtoSlidingMask::Unset()
803
804 bool ProtoSlidingMask::SetBits(UINT32 index, UINT32 count)
805 {
806 ASSERT((0 == range_mask) || (index <= range_mask));
807 if (0 == count) return true;
808 UINT32 firstPos, lastPos;
809 if (IsSet())
810 {
811 UINT32 last = (index + count - 1);
812 if (range_mask) last &= range_mask;
813 if (!CanSet(index)) return false;
814 if (!CanSet(last)) return false;
815 // Calculate first set bit position
816 if (Compare(index, offset) < 0)
817 {
818 // precedes start
819 INT32 deltaPos = start + Difference(index, offset);
820 if (deltaPos < 0) deltaPos += num_bits;
821 // The "CanSet()" checks above guarantee positive "deltaPos" here
822 start = firstPos = (UINT32)deltaPos;
823 offset = index;
824 }
825 else
826 {
827 firstPos = start + Difference(index, offset);
828 if (firstPos >= num_bits) firstPos -= num_bits;
829 }
830 // Calculate last set bit position
831 if (Compare(last, offset) > 0)
832 {
833 // Is post start, post end?
834 lastPos = start + Difference(last, offset);
835 if (lastPos >= num_bits) lastPos -= num_bits;
836 if (end < start)
837 {
838 if ((lastPos < start) && (lastPos > end)) end = lastPos;
839 }
840 else
841 {
842 if ((lastPos > end) || (lastPos < start)) end = lastPos;
843 }
844 }
845 else
846 {
847 INT32 deltaPos = start + Difference(last, offset);
848 if (deltaPos < 0) deltaPos += num_bits;
849 // The "CanSet()" checks above guarantee positive "deltaPos" here
850 lastPos = (UINT32)deltaPos;
851 }
852 if (lastPos < firstPos)
853 {
854 // Set bits from firstPos to num_bits
855 count = num_bits - firstPos;
856 UINT32 maskIndex = firstPos >> 3;
857 UINT32 bitIndex = firstPos & 0x07;
858 UINT32 bitRemainder = 8 - bitIndex;
859 ASSERT(maskIndex < mask_len);
860 if (count <= bitRemainder)
861 {
862 mask[maskIndex] |= (0x00ff >> bitIndex) &
863 (0x00ff << (bitRemainder - count));
864 }
865 else
866 {
867 mask[maskIndex] |= 0x00ff >> bitIndex;
868 count -= bitRemainder;
869 UINT32 nbytes = count >> 3;
870 ASSERT((maskIndex+1+nbytes) <= mask_len);
871 memset(&mask[++maskIndex], 0xff, nbytes);
872 count &= 0x07;
873 if (count)
874 {
875 ASSERT((maskIndex+nbytes) < mask_len);
876 mask[maskIndex+nbytes] |= 0xff << (8-count);
877 }
878 }
879 firstPos = 0;
880 }
881 }
882 else
883 {
884 if (count > num_bits) return false;
885 start = firstPos = 0;
886 end = lastPos = (count - 1);
887 offset = index;
888 }
889 // Set bits from firstPos to lastPos
890 count = lastPos - firstPos + 1;
891 UINT32 maskIndex = firstPos >> 3;
892 UINT32 bitIndex = firstPos & 0x07;
893 UINT32 bitRemainder = 8 - bitIndex;
894 ASSERT(maskIndex < mask_len);
895 if (count <= bitRemainder)
896 {
897 mask[maskIndex] |= (0x00ff >> bitIndex) &
898 (0x00ff << (bitRemainder - count));
899 }
900 else
901 {
902 mask[maskIndex] |= 0x00ff >> bitIndex;
903 count -= bitRemainder;
904 UINT32 nbytes = count >> 3;
905 ASSERT((maskIndex+1+nbytes) <= mask_len);
906 memset(&mask[++maskIndex], 0xff, nbytes);
907 count &= 0x07;
908 if (count)
909 {
910 ASSERT((maskIndex+nbytes) < mask_len);
911 mask[maskIndex+nbytes] |= 0xff << (8-count);
912 }
913 }
914 return true;
915 } // end ProtoSlidingMask::SetBits()
916
917 bool ProtoSlidingMask::UnsetBits(UINT32 index, UINT32 count)
918 {
919 ASSERT((0 == range_mask) || (index <= range_mask));
920 if (IsSet())
921 {
922 // Trim to fit as needed.
923 UINT32 firstPos;
924 if (0 == count) return true;
925 if (count > num_bits) count = num_bits;
926 if (Compare(index, offset) < 0)
927 {
928 // index precedes offset
929 firstPos = start;
930 UINT32 diff = Difference(offset, index);
931 if (diff >= count)
932 {
933 count = 0;
934 return true;
935 }
936 count -= diff;
937 }
938 else
939 {
940 UINT32 diff = Difference(index, offset);
941 if (diff >= num_bits)
942 return true; //beyond range
943 firstPos = start + diff;
944 if (firstPos >= num_bits) firstPos -= num_bits;
945 }
946 UINT32 lastSet;
947 if (!GetLastSet(lastSet))
948 ASSERT(0);
949 UINT32 endex = index + count - 1;
950 if (range_mask) endex &= range_mask;
951 UINT32 lastPos;
952 if (Compare(endex, lastSet) < 0)
953 {
954 lastPos = firstPos + count - 1;
955 if (lastPos >= num_bits) lastPos -= num_bits;
956 }
957 else
958 {
959 lastPos = end;
960 }
961 UINT32 startPos;
962 if (lastPos < firstPos)
963 {
964 // Clear bits from firstPos to num_bits
965 count = num_bits - firstPos;
966 UINT32 maskIndex = firstPos >> 3;
967 UINT32 bitIndex = firstPos & 0x07;
968 UINT32 bitRemainder = 8 - bitIndex;
969 ASSERT(maskIndex < mask_len);
970 if (count <= bitRemainder)
971 {
972 mask[maskIndex] &= (0x00ff << bitRemainder) |
973 (0x00ff >> (bitIndex + count));
974 }
975 else
976 {
977 mask[maskIndex] &= 0x00ff << bitRemainder;
978 count -= bitRemainder;
979 UINT32 nbytes = count >> 3;
980 ASSERT((maskIndex+1+nbytes) <= mask_len);
981 memset(&mask[++maskIndex], 0, nbytes);
982 count &= 0x07;
983 if (count)
984 {
985 ASSERT((maskIndex+nbytes) < mask_len);
986 mask[maskIndex+nbytes] &= 0xff >> count;
987 }
988 }
989 startPos = 0;
990 }
991 else
992 {
993 startPos = firstPos;
994 }
995 // Unset bits from firstPos to lastPos
996 count = lastPos - startPos + 1;
997 UINT32 maskIndex = startPos >> 3;
998 UINT32 bitIndex = startPos & 0x07;
999 UINT32 bitRemainder = 8 - bitIndex;
1000 ASSERT(maskIndex < mask_len);
1001 if (count <= bitRemainder)
1002 {
1003 mask[maskIndex] &= (0x00ff << bitRemainder) |
1004 (0x00ff >> (bitIndex + count));
1005 }
1006 else
1007 {
1008 mask[maskIndex] &= 0x00ff << bitRemainder;
1009 count -= bitRemainder;
1010 UINT32 nbytes = count >> 3;
1011 ASSERT((maskIndex+1+nbytes) <= mask_len);
1012 memset(&mask[++maskIndex], 0, nbytes);
1013 count &= 0x07;
1014 if (count)
1015 {
1016 ASSERT((maskIndex+nbytes) < mask_len);
1017 mask[maskIndex+nbytes] &= 0xff >> count;
1018 }
1019 }
1020 // Calling these will properly update the offset/start/end state
1021 if (start == firstPos)
1022 {
1023 if (end == lastPos)
1024 {
1025 start = end = num_bits;
1026 }
1027 else
1028 {
1029 Unset(offset);
1030 }
1031 }
1032 else if (end == lastPos)
1033 {
1034 UINT32 lastSet;
1035 GetLastSet(lastSet);
1036 Unset(lastSet);
1037 }
1038 }
1039 return true;
1040 } // end ProtoSlidingMask::UnsetBits()
1041
1042 bool ProtoSlidingMask::Test(UINT32 index) const
1043 {
1044 ASSERT((0 == range_mask) || (index <= range_mask));
1045 if (IsSet())
1046 {
1047 if (Compare(index, offset) >= 0)
1048 {
1049 UINT32 pos = Difference(index, offset);
1050 // Is it in range?
1051 if (pos >= num_bits) return false;
1052 pos += start;
1053 if (pos >= num_bits) pos -= num_bits;
1054 if (end < start)
1055 {
1056 if ((pos > end) && (pos < start)) return false;
1057 }
1058 else
1059 {
1060 if ((pos < start) || (pos > end)) return false;
1061 }
1062 // Test the corresponding bit
1063 if (0 != (mask[(pos >> 3)] & (0x80 >> (pos & 0x07))))
1064 return true;
1065 }
1066 }
1067 return false;
1068 } // end ProtoSlidingMask::Test()
1069
1070 bool ProtoSlidingMask::GetNextSet(UINT32& index) const
1071 {
1072 ASSERT((0 == range_mask) || (index <= range_mask));
1073 if (IsSet())
1074 {
1075 UINT32 next = index;
1076 if (Compare(next, offset) >= 0)
1077 {
1078 UINT32 pos = Difference(next, offset);
1079 // Is it in range?
1080 if (pos >= num_bits) return false;
1081 pos += start;
1082 if (pos >= num_bits) pos -= num_bits;
1083
1084 if (end < start)
1085 {
1086 if ((pos > end) && (pos < start)) return false;
1087 }
1088 else
1089 {
1090 if ((pos < start) || (pos > end)) return false;
1091 }
1092 // Seek next set bit
1093 UINT32 maskIndex = pos >> 3;
1094 if (mask[maskIndex])
1095 {
1096 int w = ProtoBitmask::WEIGHT[mask[maskIndex]];
1097 int remainder = pos & 0x07;
1098 for (int i = 0; i < w; i++)
1099 {
1100 int loc = ProtoBitmask::BITLOCS[mask[maskIndex]][i];
1101 if (loc >= remainder)
1102 {
1103 pos = (maskIndex << 3) + loc;
1104 if (pos >= start)
1105 pos -= start;
1106 else
1107 pos = num_bits - (start - pos);
1108 index = offset + pos;
1109 if (range_mask) index &= range_mask;
1110 return true;
1111 }
1112 }
1113 }
1114 maskIndex++;
1115 if (end < pos)
1116 {
1117 for (; maskIndex < mask_len; maskIndex++)
1118 {
1119 if (mask[maskIndex])
1120 {
1121 pos = (maskIndex << 3) + ProtoBitmask::BITLOCS[mask[maskIndex]][0];
1122 if (pos >= start)
1123 pos -= start;
1124 else
1125 pos = num_bits - (start - pos);
1126 index = offset + pos;
1127 if (range_mask) index &= range_mask;
1128 return true;
1129 }
1130 }
1131 maskIndex = 0;
1132 }
1133 UINT32 endIndex = end >> 3;
1134 for (; maskIndex <= endIndex; maskIndex++)
1135 {
1136 if (mask[maskIndex])
1137 {
1138 pos = (maskIndex << 3) + ProtoBitmask::BITLOCS[mask[maskIndex]][0];
1139 if (pos >= start)
1140 pos -= start;
1141 else
1142 pos = num_bits - (start - pos);
1143 index = offset + pos;
1144 if (range_mask) index &= range_mask;
1145 return true;
1146 }
1147 }
1148 }
1149 else
1150 {
1151 index = offset;
1152 return true;
1153 } // end if/else (pos >= 0)
1154 }
1155 return false; // indicates nothing was set
1156 } // end ProtoSlidingMask::GetNextSet()
1157
1158 bool ProtoSlidingMask::GetPrevSet(UINT32& index) const
1159 {
1160 ASSERT((0 == range_mask) || (index <= range_mask));
1161 if (IsSet())
1162 {
1163 UINT32 prev = index;
1164 if (Compare(prev, offset) >= 0)
1165 {
1166 UINT32 pos = Difference(prev, offset);
1167 // Is it in range?
1168 if (pos >= num_bits)
1169 {
1170 GetLastSet(index);
1171 return true;
1172 }
1173 pos += start;
1174 if (pos >= num_bits) pos -= num_bits;
1175 if (end < start)
1176 {
1177 if ((pos > end) && (pos < start))
1178 {
1179 GetLastSet(index);
1180 return true;
1181 }
1182 }
1183 else
1184 {
1185 if ((pos < start) || (pos > end))
1186 {
1187 GetLastSet(index);
1188 return true;
1189 }
1190 }
1191 // Seek prev set bits, starting with index
1192 UINT32 maskIndex = pos >> 3;
1193 if (mask[maskIndex])
1194 {
1195 int w = ProtoBitmask::WEIGHT[mask[maskIndex]] - 1;
1196 int remainder = pos & 0x07;
1197 for (int i = w; i >= 0; i--)
1198 {
1199 int loc = ProtoBitmask::BITLOCS[mask[maskIndex]][i];
1200 if (loc <= remainder)
1201 {
1202 pos = (maskIndex << 3) + loc;
1203 if (pos >= start)
1204 pos -= start;
1205 else
1206 pos = num_bits - (start - pos);
1207 index = offset + pos;
1208 if (range_mask) index &= range_mask;
1209 return true;
1210 }
1211 }
1212 }
1213 maskIndex--;
1214 if (pos < start)
1215 {
1216 //for(; maskIndex >= 0; maskIndex--)
1217 for(; maskIndex != 0xffffffff; maskIndex--)
1218 {
1219 if (mask[maskIndex])
1220 {
1221
1222 int w = ProtoBitmask::WEIGHT[mask[maskIndex]] - 1;
1223 pos = (maskIndex << 3) + ProtoBitmask::BITLOCS[mask[maskIndex]][w];
1224 if (pos >= start)
1225 pos -= start;
1226 else
1227 pos = num_bits - (start - pos);
1228 index = offset + pos;
1229 if (range_mask) index &= range_mask;
1230 return true;
1231 }
1232 }
1233 maskIndex = mask_len - 1;
1234 }
1235 UINT32 startIndex = start >> 3;
1236 for (; maskIndex >= startIndex; maskIndex--)
1237 {
1238 if (mask[maskIndex])
1239 {
1240 int w = ProtoBitmask::WEIGHT[mask[maskIndex]] - 1;
1241 pos = (maskIndex << 3) + ProtoBitmask::BITLOCS[mask[maskIndex]][w];
1242 if (pos >= start)
1243 pos -= start;
1244 else
1245 pos = num_bits - (start - pos);
1246 index = offset + pos;
1247 if (range_mask) index &= range_mask;
1248 return true;
1249 }
1250 }
1251 }
1252 }
1253 return false; // indicates nothing prior was set
1254 } // end ProtoSlidingMask::GetPrevSet()
1255
1256 bool ProtoSlidingMask::Copy(const ProtoSlidingMask& b)
1257 {
1258 if (b.IsSet())
1259 {
1260 UINT32 range = (b.end >= b.start) ?
1261 (b.end - b.start) :
1262 (b.num_bits - (b.start - b.end));
1263 if (range <= num_bits)
1264 {
1265 start = b.start & 0x07;
1266 UINT32 bLastSet;
1267 b.GetLastSet(bLastSet);
1268 UINT32 bFirstSet;
1269 b.GetFirstSet(bFirstSet);
1270 end = Difference(bLastSet, bFirstSet) + start;
1271 offset = b.offset;
1272 // Copy start to mask_len
1273 UINT32 startIndex = b.start >> 3;
1274 UINT32 endIndex = b.end >> 3;
1275 if (b.end < b.start)
1276 {
1277 ASSERT((b.mask_len - startIndex) <= mask_len);
1278 memcpy(mask, b.mask+startIndex, b.mask_len - startIndex);
1279 ASSERT((b.mask_len - startIndex + endIndex) <= mask_len);
1280 //memcpy(mask+b.mask_len-startIndex, b.mask, endIndex+1); // old
1281 memcpy(mask+b.mask_len-startIndex, b.mask, endIndex); // new
1282 // Clear any possible start/end overlap
1283 if (mask_len > b.mask_len)
1284 {
1285 unsigned int remainder = start & 0x07;
1286 if (remainder) mask[0] &= 0xff >> remainder;
1287 remainder = end & 0x7;
1288 if (remainder)
1289 {
1290 ASSERT((startIndex+endIndex) < mask_len);
1291 mask[startIndex+endIndex] &= 0xff << (8 - remainder);
1292 }
1293 }
1294 }
1295 else
1296 {
1297 ASSERT((endIndex-startIndex+1) <= mask_len);
1298 memcpy(mask, b.mask+startIndex, endIndex-startIndex+1);
1299 }
1300 return true;
1301 }
1302 else
1303 {
1304 return false;
1305 }
1306 }
1307 else
1308 {
1309 Clear();
1310 return true;
1311 }
1312 } // end ProtoSlidingMask::Copy()
1313
1314 // Logically OR two bit mask such that "this = (this | b)"
1315 bool ProtoSlidingMask::Add(const ProtoSlidingMask& b)
1316 {
1317 if (b.IsSet())
1318 {
1319 if (IsSet())
1320 {
1321 UINT32 bFirstSet;
1322 b.GetFirstSet(bFirstSet);
1323 if (!CanSet(bFirstSet)) return false;
1324 UINT32 bLastSet;
1325 b.GetFirstSet(bLastSet);
1326 if (!CanSet(bLastSet)) return false;
1327
1328 UINT32 range = (b.end >= b.start) ?
1329 (b.end - b.start) :
1330 (b.num_bits - (b.start - b.end));
1331 UINT32 index;
1332 b.GetFirstSet(index);
1333 for (UINT32 i = 0; i <= range; i++)
1334 {
1335 // (TBD) Improve performance by getting/setting
1336 // ranges of set bits.
1337 if (b.Test(index)) Set(index);
1338 index++;
1339 if (range_mask) index &= range_mask;
1340 }
1341 return true;
1342 }
1343 else
1344 {
1345 return Copy(b);
1346 }
1347 }
1348 return true;
1349 } // end ProtoSlidingMask::Add()
1350
1351 // A sort of logical subtraction "this = (this & ~b)"
1352 // This leaves us with bits uniquely set in "this"
1353 bool ProtoSlidingMask::Subtract(const ProtoSlidingMask& b)
1354 {
1355 if (IsSet() && b.IsSet())
1356 {
1357 UINT32 index = offset;
1358 UINT32 range = (end >= start) ?
1359 (end - start) :
1360 (num_bits - (start - end));
1361 for (UINT32 i = 0; i <= range; i++)
1362 {
1363 if (Test(index) && b.Test(index)) Unset(index);
1364 index++;
1365 if (range_mask) index &= range_mask;
1366 }
1367 }
1368 return true;
1369 } // end ProtoSlidingMask::Subtract()
1370
1371 // A sort of logical subtraction "this = (~this & b)"
1372 // This leaves us with bits uniquely set in "b"
1373 bool ProtoSlidingMask::XCopy(const ProtoSlidingMask& b)
1374 {
1375 if (b.IsSet())
1376 {
1377 if (IsSet())
1378 {
1379 // Make sure b's range is compatible
1380 UINT32 bFirstSet;
1381 b.GetFirstSet(bFirstSet);
1382 if (!CanSet(bFirstSet)) return false;
1383 UINT32 bLastSet;
1384 b.GetFirstSet(bLastSet);
1385 if (!CanSet(bLastSet)) return false;
1386 UINT32 firstSet;
1387 GetFirstSet(firstSet);
1388 UINT32 lastSet;
1389 GetLastSet(lastSet);
1390 // Clear any bits prior to 'bFirstSet'
1391 if (Compare(firstSet, bFirstSet) < 0)
1392 {
1393 UINT32 numBits = Difference(bFirstSet, firstSet);
1394 UnsetBits(firstSet, numBits);
1395 }
1396 // Clear any bits after 'bLastSet'
1397 if (Compare(lastSet, bLastSet) > 0)
1398 {
1399 UINT32 numBits = Difference(lastSet, bLastSet);
1400 UnsetBits(bLastSet, numBits);
1401 }
1402 // Perform XCopy() operation on the common range
1403 UINT32 range = (b.end >= b.start) ?
1404 (b.end - b.start) :
1405 (b.num_bits - (b.start - b.end));
1406 UINT32 index = bFirstSet;
1407 for (UINT32 i = 0; i <= range; i++)
1408 {
1409 if (Test(index))
1410 Unset(index);
1411 else if (b.Test(index))
1412 Set(index);
1413 index++;
1414 if (b.range_mask) index &= range_mask;
1415 }
1416 }
1417 else
1418 {
1419 return Copy(b);
1420 }
1421 }
1422 else
1423 {
1424 Clear();
1425 }
1426 return true;
1427 } // end ProtoSlidingMask::XCopy()
1428
1429 // Logically AND two bit mask such that "this = (this & b)"
1430 bool ProtoSlidingMask::Multiply(const ProtoSlidingMask& b)
1431 {
1432 if (b.IsSet())
1433 {
1434 if (IsSet())
1435 {
1436 UINT32 index = offset;
1437 UINT32 range = (end >= start) ?
1438 (end - start) :
1439 (num_bits - (start - end));
1440 for (UINT32 i = 0; i <= range; i++)
1441 {
1442 if (Test(index) && !b.Test(index)) Unset(index);
1443 index++;
1444 if (range_mask) index &= range_mask;
1445 }
1446 }
1447 }
1448 else
1449 {
1450 Clear();
1451 }
1452 return true;
1453 } // end ProtoSlidingMask::Multiply()
1454
1455 // Logically XOR two bit mask such that "this = (this ^ b)"
1456 // (TBD) rewrite for byte-based operation for better efficiency
1457 bool ProtoSlidingMask::Xor(const ProtoSlidingMask& b)
1458 {
1459 if (b.IsSet())
1460 {
1461 UINT32 bFirstSet;
1462 b.GetFirstSet(bFirstSet);
1463 if (!CanSet(bFirstSet)) return false;
1464 UINT32 bLastSet;
1465 b.GetFirstSet(bLastSet);
1466 if (!CanSet(bLastSet)) return false;
1467 UINT32 index;
1468 b.GetFirstSet(index);
1469 UINT32 range = (b.end >= b.start) ?
1470 (b.end - b.start) :
1471 (b.num_bits - (b.start - b.end));
1472 for (UINT32 i = 0; i <= range; i++)
1473 {
1474 if (b.Test(index)) Invert(index);
1475 index++;
1476 if (range_mask) index &= range_mask;
1477 }
1478 }
1479 return true;
1480 } // end ProtoSlidingMask::Xor()
1481
1482 void ProtoSlidingMask::Display(FILE* stream)
1483 {
1484 UINT32 index = offset;
1485 for (UINT32 i = 0; i < num_bits; i++)
1486 {
1487 if (Test(index)) fprintf(stream, "1"); else fprintf(stream, "0");
1488 if (0x07 == (i & 0x07)) fprintf(stream, " ");
1489 if (0x3f == (i & 0x3f)) fprintf(stream, "\n");
1490 index++;
1491 if (range_mask) index &= range_mask;
1492 }
1493 } // end ProtoSlidingMask::Display()
1494
1495 void ProtoSlidingMask::Debug(UINT32 theCount)
1496 {
1497 UINT32 index = offset;
1498 theCount = MIN(theCount, num_bits);
1499 PLOG(PL_ERROR, "ProtoSlidingMask::Debug() offset:%lu\n ", (unsigned long)index);
1500 UINT32 i;
1501 for (i = 0; i < theCount; i++)
1502 {
1503 if (Test(index)) PLOG(PL_ERROR, "1"); else PLOG(PL_ERROR, "0");
1504 if (0x07 == (i & 0x07)) PLOG(PL_ERROR, " ");
1505 if (0x3f == (i & 0x3f)) PLOG(PL_ERROR, "\n ");
1506 index++;
1507 if (range_mask) index &= range_mask;
1508 }
1509 if (0x3f != (i & 0x3f)) PLOG(PL_ERROR, "\n");
1510 } // end ProtoSlidingMask::Debug()