source: trunk/lib/bitblock_iterator.hpp @ 3833

Last change on this file since 3833 was 3670, checked in by ksherdy, 5 years ago

Added static contant member to the BitStreamScanner?. Clean up.

File size: 17.3 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]));
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
185/*=============================================================================
186
187Classes Descriptions:
188
189    * BitBlock Scanners
190
191    Scanner - Scanner base class.
192    ForwardScanner - Scans a BitBlock of ScanWords in the forward direction.
193    ReverseScanner - Scans a bitblock of ScanWords in the reverse direction.
194
195    Deprecated (BitBlock iterators only)
196
197    * BitBlock Iterators
198
199    BitBlock iterator classes provide Standard Template Library (STL)
200    Input iterator 'like' interface implementations as a programmer
201    convenience and allow iterator classes to be used
202    with STL Algorithms.
203
204    Forward iterators can only step forward (++) marker-bit by marker-bit.
205    Reverse iterators can only step backwards (--) marker-bit by marker-bit.
206
207
208    ForwardIterator template class wraps ForwardScanner.
209
210    - Implements STL Input iterator interface.
211    - Reads elements only once.
212    - '->' - Not implemented.
213
214    ReverseIterator template class wraps ReverseScanner.
215
216        - An STL 'like' iterator that implements prefix and postfix decrement operators.
217    Under STL, a reverse iterator implementation necessitates the implementation of
218    the STL bidirectional interface and hence scanning in both directions.
219    This functionality is not yet required and hence not implemented.
220        - Reads elements only once.
221    - '->' - Not implemented.
222
223        BitBlockForwardIterator - ForwardIterator derived specialization of ForwardIterator<BitBlock, Scanword>
224        BitBlockReverseIterator - ForwardIterator derived specialization of ReverseIterator<BitBlock, Scanword>
225
226        * BitStreamIterators
227
228    BitStreamIterator class wraps ForwardScanner.
229        - Scans an array (stream) of scanwords in contiguous memory.
230        - Implements STL Input iterator interface.
231        - Reads elements only once.     
232    - '->' - Not implemented.
233        - May be more appropriately named ForwardBitStreamIterator.
234
235=============================================================================*/
236
237//
238// Scanner Classes
239//
240#define has_bit(x) (x != 0)
241#define EOS -1
242
243template <class bitblock_t, class scanblock_t>
244class Scanner {
245
246protected:
247        Scanner(): strm(NULL), pos(EOS), blk(-1), scan_blk(-1) {}
248        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) {}
249
250        const bitblock_t * strm;
251        int32_t pos;
252        int32_t blk;
253        scanblock_t scan_blk;
254};
255
256template <class bitblock_t, class scanblock_t>
257class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {
258
259public:
260
261        ForwardScanner(){}
262        ForwardScanner(const bitblock_t * s) {
263                init(s);
264        }
265
266        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
267                this->strm = s;
268                this->pos = 0;
269                this->blk = 0;
270                this->scan_blk = *(scanblock_t *)s;
271        }
272
273        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
274                while (this->blk < BLOCK_COUNT){
275                        if(has_bit(this->scan_blk)){
276                                this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
277                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
278
279                                return (this->pos);
280                        }
281
282                        this->blk++;
283                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
284                };
285
286                this->pos = EOS;
287                return (this->pos);
288        }
289
290        /* Set or reset the iterator to position new_pos. */
291        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {           
292                const scanblock_t one_bit = 1;
293                this->blk = new_pos / (sizeof(scanblock_t)*8);
294                this->pos = new_pos % (sizeof(scanblock_t)*8);
295                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
296                // clear bit at pos and all positions to the right.
297                scanblock_t marker = one_bit << this->pos;
298                this->scan_blk = this->scan_blk &~((marker-1)|marker); 
299        }
300
301        IDISA_ALWAYS_INLINE bool is_done() const {return (EOS==this->pos);}
302        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
303        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
304        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
305        IDISA_ALWAYS_INLINE void set_pos(int32_t pos) {(this->pos = pos);}
306        static const int32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
307
308};
309
310class BitBlockForwardScanner: public ForwardScanner<BitBlock, ScanWord> {
311public:
312        BitBlockForwardScanner(){}
313        BitBlockForwardScanner(BitBlock * s): ForwardScanner<BitBlock, ScanWord>(s){}
314};
315
316template <class bitblock_t, class scanblock_t>
317class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
318
319public:
320        ReverseScanner(){}
321        ReverseScanner(const bitblock_t * s) {
322                init(s);
323        }
324        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
325                this->strm = s;
326                this->pos = 0;
327                this->blk = BLOCK_COUNT-1;
328                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
329        }
330
331        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
332                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
333                while (this->blk > -1){
334                        if(has_bit(this->scan_blk)){
335                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk) * sizeof(scanblock_t)*8 );
336                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
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 left.
355                scanblock_t marker = one_bit << this->pos;
356                this->scan_blk = this->scan_blk & (marker-1);
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 uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
365
366};
367
368//
369// BitBlock Iterator Classses
370//
371template<class bitblock_t, class scanblock_t>
372class ForwardIterator : public std::iterator<std::input_iterator_tag, int>
373{
374public:
375
376        ForwardIterator(bitblock_t * s): scanner(s)
377        {
378                scanner.scan_to_next();
379        }
380
381        // set scanner to first pos of
382        void init(bitblock_t * s)
383        {
384                scanner.init(s);
385                scanner.scan_to_next();
386        }
387
388        // equal position and stream
389        bool operator==(const ForwardIterator& iter)
390        {
391                return ((scanner.get_strm() == iter.scanner.get_strm()) && 
392                        (scanner.get_pos() == iter.scanner.get_pos()));
393        }
394
395        // not equal position and stream
396        bool operator!=(const ForwardIterator& iter)
397        {
398                return ((scanner.get_strm() != iter.scanner.get_strm()) && 
399                        (scanner.get_pos() != iter.scanner.get_pos()));
400        }
401
402        // Returns absolute position.
403        IDISA_ALWAYS_INLINE int32_t operator*()
404        {
405                return scanner.get_pos();
406        }
407
408        // prefix increment
409        IDISA_ALWAYS_INLINE ForwardIterator& operator++()
410        {
411                scanner.scan_to_next();
412                return(*this);
413        }
414
415        // postfix increment
416        ForwardIterator operator++(int)
417        {
418                ForwardIterator temp(*this);
419                ++(*this);
420                return(temp);
421        }
422
423        IDISA_ALWAYS_INLINE bool isDone() const
424        {
425                return scanner.is_done();
426        }
427
428protected:
429        ForwardIterator() {}
430
431private:
432        ForwardScanner<bitblock_t, scanblock_t> scanner;
433};
434
435class BitBlockForwardIterator: public ForwardIterator<BitBlock, ScanWord> {
436public:
437        BitBlockForwardIterator(){}
438        BitBlockForwardIterator(BitBlock * s): ForwardIterator<BitBlock, ScanWord>(s){}
439};
440
441template<class bitblock_t, class scanblock_t>
442class ReverseIterator 
443{
444public:
445        ReverseIterator(BitBlock * s): scanner(s)
446        {
447                scanner.scan_to_next();
448        }
449
450        void init(bitblock_t * s)
451        {
452                scanner.init(s);
453                scanner.scan_to_next();
454        }
455
456        // equal position and stream
457        bool operator==(const ReverseIterator& iter)
458        {
459                return ((scanner.get_strm() == iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos));
460        }
461
462        // not equal position and stream
463        bool operator!=(const ReverseIterator& iter)
464        {
465                return ((scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos()));
466        }
467
468        // Returns absolute position.
469        IDISA_ALWAYS_INLINE int32_t operator*()
470        {
471                return scanner.get_pos();
472        }
473
474        // prefix decrement
475        IDISA_ALWAYS_INLINE ReverseIterator& operator--()
476        {
477                scanner.scan_to_next();
478                return(*this);
479        }
480
481        // postfix decrement
482        ReverseIterator operator--(int)
483        {
484                ReverseIterator temp(*this);
485                --(*this);
486                return(temp);
487        }
488
489        IDISA_ALWAYS_INLINE bool isDone() const
490        {
491                return scanner.is_done();
492        }
493
494protected:
495        ReverseIterator() {}
496        ReverseScanner<bitblock_t, scanblock_t> scanner;
497};
498
499class BitBlockReverseIterator: public ReverseIterator<BitBlock, ScanWord> 
500{
501public:
502        BitBlockReverseIterator(BitBlock * s): ReverseIterator<BitBlock, ScanWord>(s){}
503private:
504        BitBlockReverseIterator(){}
505};
506
507//
508// BitStream Iterator classes
509//
510class BitStreamIterator: public std::iterator<std::input_iterator_tag, int>
511{
512public:
513        BitStreamIterator():pos(EOS), blk(-1), blk_pos(-1), strm(NULL), scan_blk(-1), scan_blk_cnt(0)
514        {
515                // default constructor defines past-the-end of bit stream semantics, pos == EOS
516        }
517
518        BitStreamIterator(const BitBlock * s, int cnt):pos(0), 
519                                                                                         blk(0),
520                                                                                         blk_pos(0),
521                                                                                         strm((ScanWord *)s),
522                                                                                         scan_blk(*((ScanWord *)s)),
523                                                                                         scan_blk_cnt(cnt)
524        {
525                scan_to_next();
526        }
527
528        virtual ~BitStreamIterator() {};
529
530        // shallow copy, bit stream iterators refer to shared data
531        BitStreamIterator& operator=(const BitStreamIterator& iter)
532        {
533                pos = iter.pos;
534                blk = iter.blk;
535                blk_pos = iter.blk_pos;
536                strm = iter.strm;                       // No copy, both
537                scan_blk =  iter.scan_blk;
538                scan_blk_cnt = iter.scan_blk_cnt;
539                return(*this);
540        }
541
542        // equal position and stream
543        bool operator==(const BitStreamIterator& iter)
544        {
545                return((strm == iter.strm) && (pos == iter.pos));
546        }
547
548        // not equal position and stream
549        bool operator!=(const BitStreamIterator& iter)
550        {
551                return((strm != iter.strm) || (pos != iter.pos));
552        }
553
554        // prefix
555        inline BitStreamIterator& operator++()
556        {
557                scan_to_next();
558                return(*this);
559        }
560
561        // postfix
562        BitStreamIterator operator++(int)
563        {
564                BitStreamIterator temp(*this);
565                ++(*this);
566                return(temp);
567        }
568
569        // Returns absolute position.
570        inline int32_t operator*()
571        {
572                return pos;
573        }
574
575        /*
576        int operator->()
577        {
578                return(&*(BitStreamIterator)*this);
579        }
580        */
581
582        IDISA_ALWAYS_INLINE bool isDone() const
583        {
584                return (EOS == pos);
585        }
586
587        void debug() {
588        std::cout << "pos: " << pos << std::endl;
589        std::cout << "blk: " << blk << std::endl;
590        std::cout << "blk_pos: " << blk_pos << std::endl;
591        }
592
593private:
594        int32_t pos;
595        uint32_t blk;
596        int32_t blk_pos;
597        const ScanWord * strm;
598        ScanWord scan_blk;
599        uint32_t scan_blk_cnt;
600
601        // Helpers
602        inline void scan_to_next() {
603                while (blk<scan_blk_cnt) {
604                        if(scan_blk > 0){
605                                pos = scan_forward_zeroes(scan_blk) + blk_pos;
606                                scan_blk = scan_blk & (scan_blk-1);  // clear rightmost bit
607                                return;
608                        }
609
610                        blk_pos += (sizeof(ScanWord)*8);
611                        blk++;
612                        scan_blk = strm[blk];
613                };
614
615                pos = EOS;
616                return;
617        }
618};
619
620#undef has_bit
621
622#endif // BITBLOCK_ITERATOR_H_
623
Note: See TracBrowser for help on using the repository browser.