Ignore:
Timestamp:
Sep 1, 2012, 2:36:05 PM (7 years ago)
Author:
ksherdy
Message:

Documented and consolidated bitstream scanner and iterator classes.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/bitblock_iterator.hpp

    r2286 r2347  
    44/*=============================================================================
    55  bitblock_iterator.hpp
    6   Created on:
     6
     7  Created on: Sept 2011
    78  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
    865=============================================================================*/
    966
     
    1471#include "bitblock_scan.hpp"
    1572
     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//
    16202template<class bitblock_t, class scanblock_t>
    17203class ForwardIterator : public std::iterator<std::input_iterator_tag, int>
     
    75261
    76262template<class bitblock_t, class scanblock_t>
    77 class ReverseIterator : public std::iterator<std::input_iterator_tag, int>
     263class ReverseIterator
    78264{
    79265public:
     
    133319};
    134320
     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};
    135428
    136429#endif // BITBLOCK_ITERATOR_H_
Note: See TracChangeset for help on using the changeset viewer.