source: trunk/lib/bitblock_iterator.hpp @ 3334

Last change on this file since 3334 was 3334, checked in by cameron, 6 years ago

Enable static assert checking (requires -std=gnu++0x compiler flag)

File size: 16.6 KB
Line 
1#ifndef BITBLOCK_ITERATOR_H_
2#define BITBLOCK_ITERATOR_H_
3
4#include <iterator>
5#include <iostream>
6#include "bitblock.hpp"
7
8/*=============================================================================
9  bitblock_iterator.hpp
10
11  Created on: Sept 2011, revised May 2013
12  Authors: Ken Herdy and Rob Cameron
13
14  Description:
15
16        Scanner classes implement the low level methods to scan through
17        the 'scanwords' of a 'bitblock'. Scanner classes are templated
18        on bitblock type and scanword type.
19
20*/
21
22
23//
24// The following implementation of BitBlockScanner is optimized
25// to eliminate branch mispredictions during scanning.  Only the
26// essential methods are included.   RDC May 2013.
27//
28// Usage:
29//   (1) declare:  BitBlockScanner myscanner;
30//   (2) initialize:  myscanner.init(&mybitblock);
31//   (3) iterate:  while (myscanner.has_next()) { pos = myscanner.scan_to_next();  ...}
32//
33
34//
35// Could also use FW 32.
36#define FW 8
37#define _FW _8
38template <class bitblock_t, class scanblock_t>
39class BitBlockScanner {
40public:
41        BitBlockScanner() {}
42
43        IDISA_ALWAYS_INLINE int init(const BitBlock *s) {
44                remaining._bitblock = *s;
45                mask = hsimd<FW>::signmask(simd_not(simd<FW>::eq(simd<1>::constant<0>(), remaining._bitblock)));
46        }
47
48        IDISA_ALWAYS_INLINE int has_next() {
49               
50                     return mask != 0;
51        }
52
53        IDISA_ALWAYS_INLINE int scan_to_next() {
54               
55                     int item_pos = scan_forward_zeroes(mask);
56                     uint32_t scan_item = remaining._FW[item_pos];
57                     int bitpos = scan_forward_zeroes(scan_item);
58                     scan_item = scan_item & (scan_item - 1);
59                     remaining._FW[item_pos] = scan_item;
60                     // We could recalculate the mask, but updating it is faster.
61                     // Note that this update code compiles to a SETcc instruction.
62                     mask = mask & (mask - ((scan_item == 0) ? 1 : 0));
63                     int pos = item_pos * FW + bitpos;
64                     return pos;
65        }
66        // It slows things down to store the position.
67        //IDISA_ALWAYS_INLINE int32_t get_pos() { return pos;}
68private:
69        union {bitblock_t _bitblock;
70               uint8_t _8[sizeof(bitblock_t)];
71               uint32_t _32[sizeof(bitblock_t)/sizeof(uint32_t)];} remaining;
72        scanblock_t mask;                       
73};
74#undef _FW
75#undef FW
76
77
78/*
79    A scanner to successively generate the positions marked by 1 bits
80    in a bit stream segment of bitblock_count bit blocks.
81
82    Usage:
83
84    (1) declaration, e.g.
85        BitStreamScanner<BitBlock, uint32_t, u8int_t, 8> s;
86        (There is considerable flexibility for using different
87         scanblock sizes for the main mask, as well as the
88         scan field sizes within each block.)
89
90    (2) initialization/reinitialization
91        s.init();
92
93    (3) load the blocks;
94        for (i = 0; i++; i < n) {mybitblock = ...; s.load_block(mybitblock, i);}
95
96    (4) Iterative scan loop (generates each position exactly once.)
97        while (s.has_next()) { pos = s.scan_to_next(); ...   };
98*/
99
100template <class bitblock_t, class scanblock_t, class scanfield_t, int bitblock_count>
101class BitStreamScanner {
102public:
103        /* Make sure that the number of bits in the mask at least equals
104           the number of scanblocks. */
105        /* Requires flag -std=gnu++0x */ 
106        static_assert(sizeof(scanblock_t) * 8 >= bitblock_count * sizeof(bitblock_t)/sizeof(scanfield_t),
107                      "Too many bitblocks for a single scanword mask");
108
109
110        BitStreamScanner() {}
111
112        IDISA_ALWAYS_INLINE void init() { mask = 0;}
113
114        IDISA_ALWAYS_INLINE void load_block(BitBlock b, int i) {
115                remaining._bitblock[i] = b;
116                BitBlock mask_i = simd_not(simd<sizeof(scanfield_t)*8>::eq(simd<1>::constant<0>(), b));
117                mask |= ((scanblock_t) hsimd<sizeof(scanfield_t)*8>::signmask(mask_i)) << (i * sizeof(bitblock_t)/sizeof(scanfield_t));
118        }
119
120        IDISA_ALWAYS_INLINE bool has_next() {
121                     return mask != 0;
122        }
123
124        IDISA_ALWAYS_INLINE int scan_to_next() {
125                     int item_pos = scan_forward_zeroes(mask);
126                     scanfield_t scan_item = remaining._scanfield[item_pos];
127                     int bitpos = scan_forward_zeroes(scan_item);
128                     scan_item = scan_item & (scan_item - 1);
129                     remaining._scanfield[item_pos] = scan_item;
130                     mask = mask & (mask - ((scan_item == 0) ? 1 : 0));
131                     int pos = item_pos * sizeof(scanfield_t) * 8 + bitpos;
132                     return pos;
133        }
134
135        IDISA_ALWAYS_INLINE int get_final_pos() {
136                     int item_pos = sizeof(scanblock_t) * 8 - scan_backward_zeroes((scanblock_t) mask) - 1;
137                     scanfield_t scan_item = remaining._scanfield[item_pos];
138                     int bitpos = sizeof(scanblock_t)  * 8 - scan_backward_zeroes((scanblock_t) scan_item) - 1;
139                     int pos = item_pos * sizeof(scanfield_t) * 8 + bitpos;
140                     return pos;
141        }
142
143        IDISA_ALWAYS_INLINE void clear_from(int pos) {
144                     int item_pos = pos / (sizeof(scanfield_t) * 8);
145                     int bitpos = pos % (sizeof(scanfield_t) * 8);
146                     remaining._scanfield[item_pos] &= (1 << bitpos) - 1;
147                     item_pos += remaining._scanfield[item_pos] == 0 ? 0 : 1;
148                     mask = mask & (((scanblock_t) 1) << item_pos) - 1;
149        }
150private:
151        union {bitblock_t _bitblock[bitblock_count];
152               scanfield_t _scanfield[bitblock_count * sizeof(bitblock_t)/sizeof(scanfield_t)];} remaining;
153        scanblock_t mask;                       
154};
155
156
157
158/*=============================================================================
159
160   Deprecated:
161
162        BitBlock iterator classes provide Standard Template Library (STL)
163        Input iterator 'like' interface implementations as a programmer
164        convenience and allow iterator classes to be used
165        with STL Algorithms.
166        Forward iterators can only step forward (++) marker-bit by marker-bit.
167        Reverse iterators can only step backwards (--) marker-bit by marker-bit.
168
169        BitStream iterator class provide an STL Input iterator interface to scan
170        through an array of scanwords (stream) in the forward direction.
171
172
173  Classes Descriptions:
174
175        *       BitBlock Scanners
176
177        Scanner - Scanner base class.
178        ForwardScanner - Scans a bitblock of scanwords in the forward direction.
179        ReverseScanner - Scans a bitblock of scanwords in the reverse direction.
180
181        * BitBlock Iterators
182
183  ForwardIterator template class wraps ForwardScanner.
184       
185        - Implements STL Input iterator interface.
186        - Reads elements only once.     
187  - '->' - Not implemented.
188
189  ReverseIterator template class wraps ReverseScanner.
190
191        - An STL 'like' iterator that implements prefix and postfix decrement operators.
192    Under STL, a reverse iterator implementation necessitates the implementation of
193                the STL bidirectional interface and hence scanning in both directions.
194                This functionality is not yet required and hence not implemented.
195        - Reads elements only once.
196  - '->' - Not implemented.
197
198        BitBlockForwardIterator - ForwardIterator derived specialization of ForwardIterator<BitBlock, Scanword>
199
200        BitBlockReverseIterator - ForwardIterator derived specialization of ReverseIterator<BitBlock, Scanword>
201
202        * BitStreamIterators
203
204  BitStreamIterator class wraps ForwardScanner.
205        - Scans an array (stream) of scanwords in contiguous memory.
206        - Implements STL Input iterator interface.
207        - Reads elements only once.     
208  - '->' - Not implemented.
209        - May be more appropriately named ForwardBitStreamIterator.
210
211=============================================================================*/
212//
213// Scanner Classes
214//
215#define has_bit(x) (x != 0)
216#define EOS -1
217
218template <class bitblock_t, class scanblock_t>
219class Scanner {
220
221protected:
222        Scanner(): strm(NULL), pos(EOS), blk(-1), scan_blk(-1) {}
223        Scanner(const bitblock_t * s, uint32_t start_pos, uint32_t start_blk, scanblock_t start_scan_blk): strm(s), pos(start_pos), blk(start_blk), scan_blk(start_scan_blk) {}
224
225        const bitblock_t * strm;
226        int32_t pos;
227        int32_t blk;
228        scanblock_t scan_blk;
229};
230
231template <class bitblock_t, class scanblock_t>
232class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {
233
234public:
235
236        ForwardScanner(){}
237        ForwardScanner(const bitblock_t * s) {
238                init(s);
239        }
240
241        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
242                this->strm = s;
243                this->pos = 0;
244                this->blk = 0;
245                this->scan_blk = *(scanblock_t *)s;
246        }
247
248        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
249                while (this->blk < BLOCK_COUNT){
250                        if(has_bit(this->scan_blk)){
251                                this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
252                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
253
254                                return (this->pos);
255                        }
256
257                        this->blk++;
258                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
259                };
260
261                this->pos = EOS;
262                return (this->pos);
263        }
264
265        /* Set or reset the iterator to position new_pos. */
266        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {           
267                const scanblock_t one_bit = 1;
268                this->blk = new_pos / (sizeof(scanblock_t)*8);
269                this->pos = new_pos % (sizeof(scanblock_t)*8);
270                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
271                // clear bit at pos and all positions to the right.
272                scanblock_t marker = one_bit << this->pos;
273                this->scan_blk = this->scan_blk &~((marker-1)|marker); 
274        }
275
276        IDISA_ALWAYS_INLINE bool is_done() const {return (EOS==this->pos);}
277        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
278        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
279        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
280        IDISA_ALWAYS_INLINE void set_pos(int32_t pos) {(this->pos = pos);}
281        static const int32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
282
283};
284
285class BitBlockForwardScanner: public ForwardScanner<BitBlock, ScanWord> {
286public:
287        BitBlockForwardScanner(){}
288        BitBlockForwardScanner(BitBlock * s): ForwardScanner<BitBlock, ScanWord>(s){}
289};
290
291
292template <class bitblock_t, class scanblock_t>
293class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
294
295public:
296        ReverseScanner(){}
297        ReverseScanner(const bitblock_t * s) {
298                init(s);
299        }
300        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
301                this->strm = s;
302                this->pos = 0;
303                this->blk = BLOCK_COUNT-1;
304                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
305        }
306
307        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
308                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
309                while (this->blk > -1){
310                        if(has_bit(this->scan_blk)){
311                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk) * sizeof(scanblock_t)*8 );
312                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
313                                return (this->pos);
314                        }
315
316                        this->blk--;
317                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
318                };
319
320                this->pos = EOS;
321                return (this->pos);
322        }
323
324        /* Set or reset the iterator to position new_pos. */
325        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {
326                const scanblock_t one_bit = 1;
327                this->blk = (new_pos / (sizeof(scanblock_t)*8));
328                this->pos = new_pos % (sizeof(scanblock_t)*8);
329                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
330                // clear bit at pos and all positions to the left.
331                scanblock_t marker = one_bit << this->pos;
332                this->scan_blk = this->scan_blk & (marker-1);
333        }
334
335        IDISA_ALWAYS_INLINE bool is_done() const {return (EOS==this->pos);}
336        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
337        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
338        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
339        IDISA_ALWAYS_INLINE void set_pos(int32_t pos) {(this->pos = pos);}
340        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
341
342};
343
344
345//
346// BitBlock Iterator Classses
347//
348template<class bitblock_t, class scanblock_t>
349class ForwardIterator : public std::iterator<std::input_iterator_tag, int>
350{
351public:
352
353        ForwardIterator(bitblock_t * s): scanner(s)
354        {
355                scanner.scan_to_next();
356        }
357
358        // set scanner to first pos of
359        void init(bitblock_t * s)
360        {
361                scanner.init(s);
362                scanner.scan_to_next();
363        }
364
365        // equal position and stream
366        bool operator==(const ForwardIterator& iter)
367        {
368                return ((scanner.get_strm() == iter.scanner.get_strm()) && 
369                        (scanner.get_pos() == iter.scanner.get_pos()));
370        }
371
372        // not equal position and stream
373        bool operator!=(const ForwardIterator& iter)
374        {
375                return ((scanner.get_strm() != iter.scanner.get_strm()) && 
376                        (scanner.get_pos() != iter.scanner.get_pos()));
377        }
378
379        // Returns absolute position.
380        IDISA_ALWAYS_INLINE int32_t operator*()
381        {
382                return scanner.get_pos();
383        }
384
385        // prefix increment
386        IDISA_ALWAYS_INLINE ForwardIterator& operator++()
387        {
388                scanner.scan_to_next();
389                return(*this);
390        }
391
392        // postfix increment
393        ForwardIterator operator++(int)
394        {
395                ForwardIterator temp(*this);
396                ++(*this);
397                return(temp);
398        }
399
400        IDISA_ALWAYS_INLINE bool isDone() const
401        {
402                return scanner.is_done();
403        }
404
405protected:
406        ForwardIterator() {}
407
408private:
409        ForwardScanner<bitblock_t, scanblock_t> scanner;
410};
411
412class BitBlockForwardIterator: public ForwardIterator<BitBlock, ScanWord> {
413public:
414        BitBlockForwardIterator(){}
415        BitBlockForwardIterator(BitBlock * s): ForwardIterator<BitBlock, ScanWord>(s){}
416};
417
418
419template<class bitblock_t, class scanblock_t>
420class ReverseIterator 
421{
422public:
423        ReverseIterator(BitBlock * s): scanner(s)
424        {
425                scanner.scan_to_next();
426        }
427
428        void init(bitblock_t * s)
429        {
430                scanner.init(s);
431                scanner.scan_to_next();
432        }
433
434        // equal position and stream
435        bool operator==(const ReverseIterator& iter)
436        {
437                return ((scanner.get_strm() == iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos));
438        }
439
440        // not equal position and stream
441        bool operator!=(const ReverseIterator& iter)
442        {
443                return ((scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos()));
444        }
445
446        // Returns absolute position.
447        IDISA_ALWAYS_INLINE int32_t operator*()
448        {
449                return scanner.get_pos();
450        }
451
452        // prefix decrement
453        IDISA_ALWAYS_INLINE ReverseIterator& operator--()
454        {
455                scanner.scan_to_next();
456                return(*this);
457        }
458
459        // postfix decrement
460        ReverseIterator operator--(int)
461        {
462                ReverseIterator temp(*this);
463                --(*this);
464                return(temp);
465        }
466
467        IDISA_ALWAYS_INLINE bool isDone() const
468        {
469                return scanner.is_done();
470        }
471
472protected:
473        ReverseIterator() {}
474        ReverseScanner<bitblock_t, scanblock_t> scanner;
475};
476
477class BitBlockReverseIterator: public ReverseIterator<BitBlock, ScanWord> 
478{
479public:
480        BitBlockReverseIterator(BitBlock * s): ReverseIterator<BitBlock, ScanWord>(s){}
481private:
482        BitBlockReverseIterator(){}
483};
484
485//
486// BitStream Iterator classes
487//
488class BitStreamIterator: public std::iterator<std::input_iterator_tag, int>
489{
490public:
491        BitStreamIterator():pos(EOS), blk(-1), blk_pos(-1), strm(NULL), scan_blk(-1), scan_blk_cnt(0)
492        {
493                // default constructor defines past-the-end of bit stream semantics, pos == EOS
494        }
495
496        BitStreamIterator(const BitBlock * s, int cnt):pos(0), 
497                                                                                         blk(0),
498                                                                                         blk_pos(0),
499                                                                                         strm((ScanWord *)s),
500                                                                                         scan_blk(*((ScanWord *)s)),
501                                                                                         scan_blk_cnt(cnt)
502        {
503                scan_to_next();
504        }
505
506        virtual ~BitStreamIterator() {};
507
508        // shallow copy, bit stream iterators refer to shared data
509        BitStreamIterator& operator=(const BitStreamIterator& iter)
510        {
511                pos = iter.pos;
512                blk = iter.blk;
513                blk_pos = iter.blk_pos;
514                strm = iter.strm;                       // No copy, both
515                scan_blk =  iter.scan_blk;
516                scan_blk_cnt = iter.scan_blk_cnt;
517                return(*this);
518        }
519
520        // equal position and stream
521        bool operator==(const BitStreamIterator& iter)
522        {
523                return((strm == iter.strm) && (pos == iter.pos));
524        }
525
526        // not equal position and stream
527        bool operator!=(const BitStreamIterator& iter)
528        {
529                return((strm != iter.strm) || (pos != iter.pos));
530        }
531
532        // prefix
533        inline BitStreamIterator& operator++()
534        {
535                scan_to_next();
536                return(*this);
537        }
538
539        // postfix
540        BitStreamIterator operator++(int)
541        {
542                BitStreamIterator temp(*this);
543                ++(*this);
544                return(temp);
545        }
546
547        // Returns absolute position.
548        inline int32_t operator*()
549        {
550                return pos;
551        }
552
553        /*
554        int operator->()
555        {
556                return(&*(BitStreamIterator)*this);
557        }
558        */
559
560        IDISA_ALWAYS_INLINE bool isDone() const
561        {
562                return (EOS == pos);
563        }
564
565        void debug() {
566        std::cout << "pos: " << pos << std::endl;
567        std::cout << "blk: " << blk << std::endl;
568        std::cout << "blk_pos: " << blk_pos << std::endl;
569        }
570
571private:
572        int32_t pos;
573        uint32_t blk;
574        int32_t blk_pos;
575        const ScanWord * strm;
576        ScanWord scan_blk;
577        uint32_t scan_blk_cnt;
578
579        // Helpers
580        inline void scan_to_next() {
581                while (blk<scan_blk_cnt) {
582                        if(scan_blk > 0){
583                                pos = scan_forward_zeroes(scan_blk) + blk_pos;
584                                scan_blk = scan_blk & (scan_blk-1);  // clear rightmost bit
585                                return;
586                        }
587
588                        blk_pos += (sizeof(ScanWord)*8);
589                        blk++;
590                        scan_blk = strm[blk];
591                };
592
593                pos = EOS;
594                return;
595        }
596};
597
598
599
600#undef has_bit
601
602
603#endif // BITBLOCK_ITERATOR_H_
604
Note: See TracBrowser for help on using the repository browser.