source: trunk/lib/bitblock_iterator.hpp @ 3274

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

get_last_pos, clear_from scanner operations

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