source: trunk/lib/bitblock_iterator.hpp @ 3189

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

Add optimized BitBlockScanner?

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