1 module qrcode.common.bitarray;
2 
3 import qrcode.common.bitutils;
4 
5 alias BitArrayBitType = long;
6 
7 /**
8 * A simple, fast array of bits.
9 */
10 class BitArray
11 {
12     /**
13 	* Bits represented as an array of integers.
14 	*
15 	* @var SplFixedArray
16 	*/
17     protected BitArrayBitType[] bits;
18     /**
19 	* Size of the bit array in bits.
20 	*
21 	* @var integer
22 	*/
23     protected BitArrayBitType size;
24     /**
25 	* Creates a new bit array with a given size.
26 	*
27 	* @param integer size
28 	*/
29     this(int size = 0)
30     {
31         this.size = size;
32         this.bits = new BitArrayBitType[(this.size + 31) >> 3];
33     }
34     /**
35 	* Gets the size in bits.
36 	*
37 	* @return integer
38 	*/
39     public BitArrayBitType getSize()
40     {
41         return this.size;
42     }
43     /**
44 	* Gets the size in bytes.
45 	*
46 	* @return integer
47 	*/
48     public BitArrayBitType getSizeInBytes()
49     {
50         return (this.size + 7) >> 3;
51     }
52     /**
53 	* Ensures that the array has a minimum capacity.
54 	*
55 	* @param  integer size
56 	* @return void
57 	*/
58     public void ensureCapacity(BitArrayBitType size)
59     {
60         if (size > bits.length << 5)
61         {
62             this.bits.length = (size + 31) >> 5;
63         }
64     }
65     /**
66 	* Gets a specific bit.
67 	*
68 	* @param  integer i
69 	* @return boolean
70 	*/
71     public bool get(long i)
72     {
73         return (this.bits[i >> 5L] & (1L << (i & 0x1f))) != 0;
74     }
75     /**
76 	* Sets a specific bit.
77 	*
78 	* @param  integer i
79 	* @return void
80 	*/
81     public void set(int i)
82     {
83         this.bits[i >> 5] = this.bits[i >> 5] | 1L << (i & 0x1f);
84     }
85     /**
86 	* Flips a specific bit.
87 	*
88 	* @param  integer i
89 	* @return void
90 	*/
91     public void flip(int i)
92     {
93         this.bits[i >> 5] ^= 1L << (i & 0x1f);
94     }
95     /**
96 	* Gets the next set bit position from a given position.
97 	*
98 	* @param  integer from
99 	* @return integer
100 	*/
101     public long getNextSet(long from)
102     {
103         if (from >= this.size)
104         {
105             return this.size;
106         }
107         auto bitsOffset = from >> 5;
108         auto currentBits = this.bits[bitsOffset];
109         auto bitsLength = this.bits.length;
110         currentBits &= ~((1L << (from & 0x1f)) - 1);
111         while (currentBits == 0)
112         {
113             if (++bitsOffset == bitsLength)
114             {
115                 return this.size;
116             }
117             currentBits = this.bits[bitsOffset];
118         }
119         auto result = (bitsOffset << 5) + BitUtils.numberOfTrailingZeros(currentBits);
120         return result > this.size ? this.size : result;
121     }
122     /**
123 	* Gets the next unset bit position from a given position.
124 	*
125 	* @param  integer from
126 	* @return integer
127 	*/
128     public ulong getNextUnset(int from)
129     {
130         if (from >= this.size)
131         {
132             return this.size;
133         }
134         auto bitsOffset = from >> 5;
135         auto currentBits =  ~this.bits[bitsOffset];
136         auto bitsLength = this.bits.length;
137         currentBits &= ~((1L << (from & 0x1f)) - 1);
138         while (currentBits == 0)
139         {
140             if (++bitsOffset == bitsLength)
141             {
142                 return this.size;
143             }
144             currentBits =  ~this.bits[bitsOffset];
145         }
146         auto result = (bitsOffset << 5) + BitUtils.numberOfTrailingZeros(currentBits);
147         return result > this.size ? this.size : result;
148     }
149     /**
150 	* Sets a bulk of bits.
151 	*
152 	* @param  integer i
153 	* @param  integer newBits
154 	* @return void
155 	*/
156     public void setBulk(int i, BitArrayBitType newBits)
157     {
158         this.bits[i >> 5] = newBits;
159     }
160     /**
161 	* Sets a range of bits.
162 	*
163 	* @param  integer start
164 	* @param  integer end
165 	* @return void
166 	* @throws Exception\InvalidArgumentException
167 	*/
168     public void setRange(int start, int end)
169     {
170         if (end < start)
171         {
172             throw new Exception("End must be greater or equal to start");
173         }
174         if (end == start)
175         {
176             return;
177         }
178         end--;
179         auto firstInt = start >> 5;
180         auto lastInt = end >> 5;
181         auto mask = 0;
182         for (auto i = firstInt; i <= lastInt; i++)
183         {
184             auto firstBit = i > firstInt ? 0 : start & 0x1f;
185             auto lastBit = i < lastInt ? 31 : end & 0x1f;
186             if (firstBit == 0 && lastBit == 31)
187             {
188                 mask = 0x7fffffff;
189             }
190             else
191             {
192                 mask = 0;
193                 for (auto j = firstBit; j < lastBit; j++)
194                 {
195                     mask |= 1L << j;
196                 }
197             }
198             this.bits[i] = this.bits[i] | mask;
199         }
200     }
201     /**
202 	* Clears the bit array, unsetting every bit.
203 	*
204 	* @return void
205 	*/
206     public void clear()
207     {
208         this.bits[] = 0;
209     }
210     /**
211 	* Checks if a range of bits is set or not set.
212 	*
213 	* @param  integer start
214 	* @param  integer end
215 	* @param  integer value
216 	* @return boolean
217 	* @throws Exception\InvalidArgumentException
218 	*/
219     public bool isRange(int start, int end, int value)
220     {
221         if (end < start)
222         {
223             throw new Exception("End must be greater or equal to start");
224         }
225         if (end == start)
226         {
227             return false;
228         }
229         end--;
230         auto firstInt = start >> 5;
231         auto lastInt = end >> 5;
232         auto mask = 0;
233         for (auto i = firstInt; i <= lastInt; i++)
234         {
235             auto firstBit = i > firstInt ? 0 : start & 0x1f;
236             auto lastBit = i < lastInt ? 31 : end & 0x1f;
237             if (firstBit == 0 && lastBit == 31)
238             {
239                 mask = 0x7fffffff;
240             }
241             else
242             {
243                 mask = 0;
244                 for (auto j = firstBit; j <= lastBit; j++)
245                 {
246                     mask |= 1L << j;
247                 }
248             }
249             if ((this.bits[i] & mask) != (value ? mask : 0))
250             {
251                 return false;
252             }
253         }
254         return true;
255     }
256     /**
257 	* Appends a bit to the array.
258 	*
259 	* @param  boolean bit
260 	* @return void
261 	*/
262     public void appendBit(bool bit, bool test = false)
263     {
264         this.ensureCapacity(this.size + 1);
265         if (bit)
266         {
267             if (test)
268             {
269                 import std.stdio;
270 
271                 //writeln("---",this.bits, " size:", this.size);
272             }
273             this.bits[this.size >> 5] = this.bits[this.size >> 5] | (1L << (this.size & 0x1f));
274             if (test)
275             {
276                 import std.stdio;
277 
278                 //writeln(this.bits);
279             }
280         }
281         this.size++;
282     }
283     /**
284 	* Appends a number of bits (up to 32) to the array.
285 	*
286 	* @param  integer value
287 	* @param  integer numBits
288 	* @return void
289 	* @throws Exception\InvalidArgumentException
290 	*/
291     public void appendBits(int value, int numBits, bool test = false)
292     {
293         if (numBits < 0 || numBits > 32)
294         {
295             throw new Exception("Num bits must be between 0 and 32");
296         }
297         this.ensureCapacity(this.size + numBits);
298         for (auto numBitsLeft = numBits; numBitsLeft > 0; numBitsLeft--)
299         {
300             if (test)
301             {
302                 import std.stdio;
303 
304                 //writeln("value:", value , " xxx:", ((value >> (numBitsLeft - 1)) & 0x01));
305             }
306             this.appendBit(((value >> (numBitsLeft - 1)) & 0x01) == 1, test);
307         }
308     }
309     /**
310 	* Appends another bit array to this array.
311 	*
312 	* @param  BitArray other
313 	* @return void
314 	*/
315     public void appendBitArray(BitArray other)
316     {
317         this.ensureCapacity(this.size + other.getSize());
318         for (auto i = 0; i < other.getSize(); i++)
319         {
320             this.appendBit(other.get(i));
321         }
322     }
323     /**
324 	* Makes an exclusive-or comparision on the current bit array.
325 	*
326 	* @param  BitArray other
327 	* @return void
328 	* @throws Exception\InvalidArgumentException
329 	*/
330     public void xorBits(BitArray other)
331     {
332         auto bitsLength = this.bits.length;
333         auto otherBits = other.getBitArray();
334         if (bitsLength != otherBits.length)
335         {
336             throw new Exception("Sizes don\'t match");
337         }
338         for (auto i = 0; i < bitsLength; i++)
339         {
340             this.bits[i] = this.bits[i] ^ otherBits[i];
341         }
342     }
343     /**
344 	* Converts the bit array to a byte array.
345 	*
346 	* @param  integer bitOffset
347 	* @param  integer numBytes
348 	* @return SplFixedArray
349 	*/
350     public int[] toBytes(int bitOffset, int numBytes)
351     {
352         auto bytes = new int[numBytes];
353         for (auto i = 0; i < numBytes; i++)
354         {
355             auto _byte = 0;
356             for (auto j = 0; j < 8; j++)
357             {
358                 if (this.get(bitOffset))
359                 {
360                     _byte |= 1L << (7 - j);
361                 }
362                 bitOffset++;
363             }
364             bytes[i] = _byte;
365         }
366         return bytes;
367     }
368     /**
369 	* Gets the internal bit array.
370 	*
371 	* @return SplFixedArray
372 	*/
373     public BitArrayBitType[] getBitArray()
374     {
375         return this.bits;
376     }
377     /**
378 	* Reverses the array.
379 	*
380 	* @return void
381 	*/
382     public void reverse()
383     {
384         auto newBits = new BitArrayBitType[this.bits.length];
385         for (auto i = 0; i < this.size; i++)
386         {
387             if (this.get(this.size - i - 1))
388             {
389                 newBits[i >> 5] = newBits[i >> 5] | (1L << (i & 0x1f));
390             }
391         }
392         this.bits = newBits;
393     }
394     /**
395 	* Returns a string representation of the bit array.
396 	*
397 	* @return string
398 	*/
399     public override string toString()
400     {
401         import std.array;
402 
403         Appender!string result = appender!string();
404         for (auto i = 0; i < this.size; i++)
405         {
406             if ((i & 0x07) == 0)
407             {
408                 result.put(" ");
409             }
410             result.put(this.get(i) ? 'X' : '.');
411         }
412         return result.data;
413     }
414 }