Changeset 2347 for trunk/lib

Timestamp:

Sep 1, 2012, 2:36:05 PM (6 years ago)

Author:

ksherdy

Message:

Documented and consolidated bitstream scanner and iterator classes.

Location:

trunk/lib

Files:

• bitblock_iterator.hpp (modified) (4 diffs)
• bitblock_scan.hpp (deleted)
• bitstream_iterator.hpp (deleted)

trunk/lib/bitblock_iterator.hpp

@@ -4 +4 @@
 /*=============================================================================
   bitblock_iterator.hpp
-  Created on:
+
+  Created on: Sept 2011
   Author: Ken Herdy
+
+  Description:
+
+        Scanner classes implement the low level methods to scan through 
+        the 'scanwords' of a 'bitblock'. Scanner classes are templated 
+        on bitblock type and scanword type. 
+
+        BitBlock iterator classes provide Standard Template Library (STL) 
+        Input iterator 'like' interface implementations as a programmer
+        convenience and allow iterator classes to be used 
+        with STL Algorithms. 
+        Forward iterators can only step forward (++) marker-bit by marker-bit. 
+        Reverse iterators can only step backwards (--) marker-bit by marker-bit.
+
+        BitStream iterator class provide an STL Input iterator interface to scan 
+        through an array of scanwords (stream) in the forward direction. 
+
+
+  Classes Descriptions:
+
+        *       BitBlock Scanners
+
+        Scanner - Scanner base class.
+        ForwardScanner - Scans a bitblock of scanwords in the forward direction.
+        ReverseScanner - Scans a bitblock of scanwords in the reverse direction.
+
+        * BitBlock Iterators
+
+  ForwardIterator template class wraps ForwardScanner. 
+        
+        - Implements STL Input iterator interface.
+        - Reads elements only once.     
+  - '->' - Not implemented.
+
+  ReverseIterator template class wraps ReverseScanner.
+
+        - An STL 'like' iterator that implements prefix and postfix decrement operators.
+    Under STL, a reverse iterator implementation necessitates the implementation of
+                the STL bidirectional interface and hence scanning in both directions. 
+                This functionality is not yet required and hence not implemented.
+        - Reads elements only once. 
+  - '->' - Not implemented.
+
+        BitBlockForwardIterator - ForwardIterator derived specialization of ForwardIterator<BitBlock, scanword_t>
+
+        BitBlockReverseIterator - ForwardIterator derived specialization of ReverseIterator<BitBlock, scanword_t>
+
+        * BitStreamIterators
+
+  BitStreamIterator class wraps ForwardScanner. 
+        - Scans an array (stream) of scanwords in contiguous memory. 
+        - Implements STL Input iterator interface.
+        - Reads elements only once.     
+  - '->' - Not implemented.
+        - May be more appropriately named ForwardBitStreamIterator.
+
 =============================================================================*/
 
@@ -14 +71 @@
 #include "bitblock_scan.hpp"
 
+//
+// Scanner Classes
+//
+#define has_bit(x) (x != 0)
+
+template <class bitblock_t, class scanblock_t>
+class Scanner {
+
+protected:
+        Scanner(): strm(NULL), pos(-1), blk(-1), scan_blk(-1) {}
+        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) {}
+
+        const bitblock_t * strm;
+        int32_t pos;
+        int32_t blk;
+        scanblock_t scan_blk;
+};
+
+template <class bitblock_t, class scanblock_t>
+class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {
+
+public:
+
+        ForwardScanner(){}
+        ForwardScanner(const bitblock_t * s) {
+                init(s);
+        }
+
+        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
+                this->strm = s;
+                this->pos = 0;
+                this->blk = 0;
+                this->scan_blk = *(scanblock_t *)s;
+        }
+
+        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
+                while (this->blk < BLOCK_COUNT){
+                        if(has_bit(this->scan_blk)){
+                                this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
+                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
+
+                                return (this->pos);
+                        }
+
+                        this->blk++;
+                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
+                };
+
+                this->pos = -1;
+                return (this->pos);
+        }
+
+        /* Set or reset the iterator to position new_pos. */
+        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {            
+                const scanblock_t one_bit = 1;
+                this->blk = new_pos / (sizeof(scanblock_t)*8);
+                this->pos = new_pos % (sizeof(scanblock_t)*8);
+                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
+                // clear bit at pos and all positions to the right.
+                scanblock_t marker = one_bit << this->pos;
+                this->scan_blk = this->scan_blk &~((marker-1)|marker); 
+        }
+
+        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
+        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
+        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
+        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
+
+        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
+
+};
+
+template <class bitblock_t, class scanblock_t>
+class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
+
+public:
+        ReverseScanner(){}
+        ReverseScanner(const bitblock_t * s) {
+                init(s);
+        }
+        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
+                this->strm = s;
+                this->pos = 0;
+                this->blk = BLOCK_COUNT-1;
+                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
+        }
+
+        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
+                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
+                while (this->blk > -1){
+                        if(has_bit(this->scan_blk)){
+                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk) * sizeof(scanblock_t)*8 );
+                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
+                                return (this->pos);
+                        }
+
+                        this->blk--;
+                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
+                };
+
+                this->pos = -1;
+                return (this->pos);
+        }
+
+        /* Set or reset the iterator to position new_pos. */
+        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {
+                const scanblock_t one_bit = 1;
+                this->blk = (new_pos / (sizeof(scanblock_t)*8));
+                this->pos = new_pos % (sizeof(scanblock_t)*8);
+                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
+                // clear bit at pos and all positions to the left.
+                scanblock_t marker = one_bit << this->pos;
+                this->scan_blk = this->scan_blk & (marker-1);
+        }
+
+        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
+        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
+        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
+        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
+
+        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
+
+};
+
+#undef has_bit
+
+//
+// BitBlock Iterator Classses
+//
 template<class bitblock_t, class scanblock_t>
 class ForwardIterator : public std::iterator<std::input_iterator_tag, int>
@@ -75 +261 @@
 
 template<class bitblock_t, class scanblock_t>
-class ReverseIterator : public std::iterator<std::input_iterator_tag, int>
+class ReverseIterator 
 {
 public:
@@ -133 +319 @@
 };
 
+//
+// BitStream Iterator classes
+//
+class BitStreamIterator: public std::iterator<std::input_iterator_tag, int>
+{
+public:
+        BitStreamIterator():pos(-1), blk(-1), blk_pos(-1), strm(NULL), scan_blk(-1), scan_blk_cnt(0)
+        {
+                // default constructor defines past-the-end of bit stream semantics, pos == -1
+        }
+
+        BitStreamIterator(const BitBlock * s, int cnt):pos(0),  
+                                                                                         blk(0),
+                                                                                         blk_pos(0),
+                                                                                         strm((scanword_t *)s),
+                                                                                         scan_blk(*((scanword_t *)s)),
+                                                                                         scan_blk_cnt(cnt)
+        {
+                scan_to_next();
+        }
+
+        virtual ~BitStreamIterator() {};
+
+        // shallow copy, bit stream iterators refer to shared data
+        BitStreamIterator& operator=(const BitStreamIterator& iter)
+        {
+                pos = iter.pos;
+                blk = iter.blk;
+                blk_pos = iter.blk_pos;
+                strm = iter.strm;                       // No copy, both
+                scan_blk =  iter.scan_blk;
+                scan_blk_cnt = iter.scan_blk_cnt;
+                return(*this);
+        }
+
+        // equal position and stream
+        bool operator==(const BitStreamIterator& iter)
+        {
+                return((strm = iter.strm) && (pos == iter.pos));
+        }
+
+        // not equal position and stream
+        bool operator!=(const BitStreamIterator& iter)
+        {
+                return((strm != iter.strm) || (pos != iter.pos));
+        }
+
+        // prefix
+        inline BitStreamIterator& operator++()
+        {
+                scan_to_next();
+                return(*this);
+        }
+
+        // postfix
+        BitStreamIterator operator++(int)
+        {
+                BitStreamIterator temp(*this);
+                ++(*this);
+                return(temp);
+        }
+
+        // Returns absolute position.
+        inline int32_t operator*()
+        {
+                return pos;
+        }
+
+        /*
+        int operator->()
+        {
+                return(&*(BitStreamIterator)*this);
+        }
+        */
+
+        void debug() {
+        std::cout << "pos: " << pos << std::endl;
+        std::cout << "blk: " << blk << std::endl;
+        std::cout << "blk_pos: " << blk_pos << std::endl;
+        }
+
+private:
+        int32_t pos;
+        uint32_t blk;
+        int32_t blk_pos;
+        const scanword_t * strm;
+        scanword_t scan_blk;
+        uint32_t scan_blk_cnt;
+
+        // Helpers
+        inline void scan_to_next() {
+                while (blk<scan_blk_cnt) {
+                        if(scan_blk > 0){
+                                pos = scan_forward_zeroes(scan_blk) + blk_pos;
+                                scan_blk = scan_blk & (scan_blk-1);  // clear rightmost bit
+                                return;
+                        }
+
+                        blk_pos += (sizeof(scanword_t)*8);
+                        blk++;
+                        scan_blk = strm[blk];
+                };
+
+                pos = -1;
+                return;
+        }
+};
 
 #endif // BITBLOCK_ITERATOR_H_