source: trunk/lib/bitblock_iterator.hpp @ 4063

Last change on this file since 4063 was 4045, checked in by ksherdy, 5 years ago

Added a scanner to scan a stream of bitblocks.

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