source: icXML/icXML-devel/src/simd-lib/bitblock_iterator.hpp @ 3567

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

simd-lib updates

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