source: trunk/lib_c/cpp2c/expected_output/bitblock_iterator.hpp @ 3396

Last change on this file since 3396 was 3396, checked in by linmengl, 6 years ago

handle bitblock_iterator.hpp correctly now

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