source: trunk/lib/bitblock_iterator.hpp @ 2347

Last change on this file since 2347 was 2347, checked in by ksherdy, 7 years ago

Documented and consolidated bitstream scanner and iterator classes.

File size: 10.8 KB
Line 
1#ifndef BITBLOCK_ITERATOR_H_
2#define BITBLOCK_ITERATOR_H_
3
4/*=============================================================================
5  bitblock_iterator.hpp
6
7  Created on: Sept 2011
8  Author: Ken Herdy
9
10  Description:
11
12        Scanner classes implement the low level methods to scan through
13        the 'scanwords' of a 'bitblock'. Scanner classes are templated
14        on bitblock type and scanword type.
15
16        BitBlock iterator classes provide Standard Template Library (STL)
17        Input iterator 'like' interface implementations as a programmer
18        convenience and allow iterator classes to be used
19        with STL Algorithms.
20        Forward iterators can only step forward (++) marker-bit by marker-bit.
21        Reverse iterators can only step backwards (--) marker-bit by marker-bit.
22
23        BitStream iterator class provide an STL Input iterator interface to scan
24        through an array of scanwords (stream) in the forward direction.
25
26
27  Classes Descriptions:
28
29        *       BitBlock Scanners
30
31        Scanner - Scanner base class.
32        ForwardScanner - Scans a bitblock of scanwords in the forward direction.
33        ReverseScanner - Scans a bitblock of scanwords in the reverse direction.
34
35        * BitBlock Iterators
36
37  ForwardIterator template class wraps ForwardScanner.
38       
39        - Implements STL Input iterator interface.
40        - Reads elements only once.     
41  - '->' - Not implemented.
42
43  ReverseIterator template class wraps ReverseScanner.
44
45        - An STL 'like' iterator that implements prefix and postfix decrement operators.
46    Under STL, a reverse iterator implementation necessitates the implementation of
47                the STL bidirectional interface and hence scanning in both directions.
48                This functionality is not yet required and hence not implemented.
49        - Reads elements only once.
50  - '->' - Not implemented.
51
52        BitBlockForwardIterator - ForwardIterator derived specialization of ForwardIterator<BitBlock, scanword_t>
53
54        BitBlockReverseIterator - ForwardIterator derived specialization of ReverseIterator<BitBlock, scanword_t>
55
56        * BitStreamIterators
57
58  BitStreamIterator class wraps ForwardScanner.
59        - Scans an array (stream) of scanwords in contiguous memory.
60        - Implements STL Input iterator interface.
61        - Reads elements only once.     
62  - '->' - Not implemented.
63        - May be more appropriately named ForwardBitStreamIterator.
64
65=============================================================================*/
66
67#include <iterator>
68#include <iostream>
69
70#include "bitblock.hpp"
71#include "bitblock_scan.hpp"
72
73//
74// Scanner Classes
75//
76#define has_bit(x) (x != 0)
77
78template <class bitblock_t, class scanblock_t>
79class Scanner {
80
81protected:
82        Scanner(): strm(NULL), pos(-1), blk(-1), scan_blk(-1) {}
83        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) {}
84
85        const bitblock_t * strm;
86        int32_t pos;
87        int32_t blk;
88        scanblock_t scan_blk;
89};
90
91template <class bitblock_t, class scanblock_t>
92class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {
93
94public:
95
96        ForwardScanner(){}
97        ForwardScanner(const bitblock_t * s) {
98                init(s);
99        }
100
101        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
102                this->strm = s;
103                this->pos = 0;
104                this->blk = 0;
105                this->scan_blk = *(scanblock_t *)s;
106        }
107
108        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
109                while (this->blk < BLOCK_COUNT){
110                        if(has_bit(this->scan_blk)){
111                                this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
112                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
113
114                                return (this->pos);
115                        }
116
117                        this->blk++;
118                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
119                };
120
121                this->pos = -1;
122                return (this->pos);
123        }
124
125        /* Set or reset the iterator to position new_pos. */
126        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {           
127                const scanblock_t one_bit = 1;
128                this->blk = new_pos / (sizeof(scanblock_t)*8);
129                this->pos = new_pos % (sizeof(scanblock_t)*8);
130                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
131                // clear bit at pos and all positions to the right.
132                scanblock_t marker = one_bit << this->pos;
133                this->scan_blk = this->scan_blk &~((marker-1)|marker); 
134        }
135
136        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
137        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
138        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
139        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
140
141        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
142
143};
144
145template <class bitblock_t, class scanblock_t>
146class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
147
148public:
149        ReverseScanner(){}
150        ReverseScanner(const bitblock_t * s) {
151                init(s);
152        }
153        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
154                this->strm = s;
155                this->pos = 0;
156                this->blk = BLOCK_COUNT-1;
157                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
158        }
159
160        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
161                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
162                while (this->blk > -1){
163                        if(has_bit(this->scan_blk)){
164                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk) * sizeof(scanblock_t)*8 );
165                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
166                                return (this->pos);
167                        }
168
169                        this->blk--;
170                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
171                };
172
173                this->pos = -1;
174                return (this->pos);
175        }
176
177        /* Set or reset the iterator to position new_pos. */
178        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {
179                const scanblock_t one_bit = 1;
180                this->blk = (new_pos / (sizeof(scanblock_t)*8));
181                this->pos = new_pos % (sizeof(scanblock_t)*8);
182                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
183                // clear bit at pos and all positions to the left.
184                scanblock_t marker = one_bit << this->pos;
185                this->scan_blk = this->scan_blk & (marker-1);
186        }
187
188        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
189        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
190        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
191        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
192
193        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
194
195};
196
197#undef has_bit
198
199//
200// BitBlock Iterator Classses
201//
202template<class bitblock_t, class scanblock_t>
203class ForwardIterator : public std::iterator<std::input_iterator_tag, int>
204{
205public:
206        ForwardIterator() {}
207
208        ForwardIterator(bitblock_t * s): scanner(s)
209        {
210                scanner.scan_to_next();
211        }
212
213        void init(bitblock_t * s)
214        {
215                scanner.init(s);
216                scanner.scan_to_next();
217        }
218
219        // equal position and stream
220        bool operator==(const ForwardIterator& iter)
221        {
222                return ((scanner.get_strm() = iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos));
223        }
224
225        // not equal .get_pos()ition and stream
226        bool operator!=(const ForwardIterator& iter)
227        {
228                return ( (scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos()));
229        }
230
231        // Returns absolute position.
232        IDISA_ALWAYS_INLINE int32_t operator*()
233        {
234                return scanner.get_pos();
235        }
236
237        // prefix increment
238        IDISA_ALWAYS_INLINE ForwardIterator& operator++()
239        {
240                scanner.scan_to_next();
241                return(*this);
242        }
243
244        // postfix increment
245        ForwardIterator operator++(int)
246        {
247                ForwardIterator temp(*this);
248                ++(*this);
249                return(temp);
250        }
251
252private:
253        ForwardScanner<bitblock_t, scanblock_t> scanner;
254};
255
256class BitBlockForwardIterator: public ForwardIterator<BitBlock, scanword_t> {
257public:
258        BitBlockForwardIterator(){}
259        BitBlockForwardIterator(BitBlock * s): ForwardIterator<BitBlock, scanword_t>(s){}
260};
261
262template<class bitblock_t, class scanblock_t>
263class ReverseIterator 
264{
265public:
266        ReverseIterator() {}
267        ReverseIterator(BitBlock * s): scanner(s)
268        {
269                scanner.scan_to_next();
270        }
271
272        void init(bitblock_t * s)
273        {
274                scanner.init(s);
275                scanner.scan_to_next();
276        }
277
278        // equal position and stream
279        bool operator==(const ReverseIterator& iter)
280        {
281                return ((scanner.get_strm() = iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos));
282        }
283
284        // not equal .get_pos()ition and stream
285        bool operator!=(const ReverseIterator& iter)
286        {
287                return ((scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos()));
288        }
289
290        // Returns absolute position.
291        IDISA_ALWAYS_INLINE int32_t operator*()
292        {
293                return scanner.get_pos();
294        }
295
296        // prefix decrement
297        IDISA_ALWAYS_INLINE ReverseIterator& operator--()
298        {
299                scanner.scan_to_next();
300                return(*this);
301        }
302
303        // postfix decrement
304        ReverseIterator operator--(int)
305        {
306                ReverseIterator temp(*this);
307                --(*this);
308                return(temp);
309        }
310
311private:
312        ReverseScanner<bitblock_t, scanblock_t> scanner;
313};
314
315class BitBlockReverseIterator: public ReverseIterator<BitBlock, scanword_t> {
316public:
317        BitBlockReverseIterator(){}
318        BitBlockReverseIterator(BitBlock * s): ReverseIterator<BitBlock, scanword_t>(s){}
319};
320
321//
322// BitStream Iterator classes
323//
324class BitStreamIterator: public std::iterator<std::input_iterator_tag, int>
325{
326public:
327        BitStreamIterator():pos(-1), blk(-1), blk_pos(-1), strm(NULL), scan_blk(-1), scan_blk_cnt(0)
328        {
329                // default constructor defines past-the-end of bit stream semantics, pos == -1
330        }
331
332        BitStreamIterator(const BitBlock * s, int cnt):pos(0), 
333                                                                                         blk(0),
334                                                                                         blk_pos(0),
335                                                                                         strm((scanword_t *)s),
336                                                                                         scan_blk(*((scanword_t *)s)),
337                                                                                         scan_blk_cnt(cnt)
338        {
339                scan_to_next();
340        }
341
342        virtual ~BitStreamIterator() {};
343
344        // shallow copy, bit stream iterators refer to shared data
345        BitStreamIterator& operator=(const BitStreamIterator& iter)
346        {
347                pos = iter.pos;
348                blk = iter.blk;
349                blk_pos = iter.blk_pos;
350                strm = iter.strm;                       // No copy, both
351                scan_blk =  iter.scan_blk;
352                scan_blk_cnt = iter.scan_blk_cnt;
353                return(*this);
354        }
355
356        // equal position and stream
357        bool operator==(const BitStreamIterator& iter)
358        {
359                return((strm = iter.strm) && (pos == iter.pos));
360        }
361
362        // not equal position and stream
363        bool operator!=(const BitStreamIterator& iter)
364        {
365                return((strm != iter.strm) || (pos != iter.pos));
366        }
367
368        // prefix
369        inline BitStreamIterator& operator++()
370        {
371                scan_to_next();
372                return(*this);
373        }
374
375        // postfix
376        BitStreamIterator operator++(int)
377        {
378                BitStreamIterator temp(*this);
379                ++(*this);
380                return(temp);
381        }
382
383        // Returns absolute position.
384        inline int32_t operator*()
385        {
386                return pos;
387        }
388
389        /*
390        int operator->()
391        {
392                return(&*(BitStreamIterator)*this);
393        }
394        */
395
396        void debug() {
397        std::cout << "pos: " << pos << std::endl;
398        std::cout << "blk: " << blk << std::endl;
399        std::cout << "blk_pos: " << blk_pos << std::endl;
400        }
401
402private:
403        int32_t pos;
404        uint32_t blk;
405        int32_t blk_pos;
406        const scanword_t * strm;
407        scanword_t scan_blk;
408        uint32_t scan_blk_cnt;
409
410        // Helpers
411        inline void scan_to_next() {
412                while (blk<scan_blk_cnt) {
413                        if(scan_blk > 0){
414                                pos = scan_forward_zeroes(scan_blk) + blk_pos;
415                                scan_blk = scan_blk & (scan_blk-1);  // clear rightmost bit
416                                return;
417                        }
418
419                        blk_pos += (sizeof(scanword_t)*8);
420                        blk++;
421                        scan_blk = strm[blk];
422                };
423
424                pos = -1;
425                return;
426        }
427};
428
429#endif // BITBLOCK_ITERATOR_H_
430
Note: See TracBrowser for help on using the repository browser.