source: trunk/lib/bitblock_scan.hpp @ 2006

Last change on this file since 2006 was 1994, checked in by cameron, 7 years ago

move_to methods for scanners

File size: 4.3 KB
Line 
1#ifndef BITBLOCK_SCAN_H_
2#define BITBLOCK_SCAN_H_
3
4/*=============================================================================
5  bitblock_scan.hpp
6  Created on:
7  Author: Ken Herdy
8=============================================================================*/
9
10#include <iterator>
11#include <iostream>
12using namespace std;
13
14#include "bitblock.hpp"
15
16/*
17 * Templated scanner forward and reverse scanner classes on biblock_t, scanblock_t.
18 */ 
19 
20// Base
21template <class bitblock_t, class scanblock_t>
22class Scanner {
23
24protected:
25        Scanner(): strm(NULL), pos(-1), blk(-1), scan_blk(-1) {}
26        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) {}
27
28        const bitblock_t * strm;
29        int32_t pos;
30        uint32_t blk;
31        scanblock_t scan_blk;
32        /* The test here needs to be != 0, not > 0, in case scanblock_t is signed.*/
33        IDISA_ALWAYS_INLINE bool has_bit(scanblock_t x) const {return x != 0;};
34};
35
36// Forward
37template <class bitblock_t, class scanblock_t>
38class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {
39
40public:
41
42        ForwardScanner(){}
43        ForwardScanner(const bitblock_t * s) {
44                init(s);
45        }
46
47        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
48                this->strm = s;
49                this->pos = 0;
50                this->blk = 0;
51                this->scan_blk = *(scanblock_t *)s;
52        }
53
54        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
55                while (this->blk < (sizeof(bitblock_t)/sizeof(scanblock_t))){
56                        if(has_bit(this->scan_blk)){
57                                this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
58                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
59
60                                return (this->pos);
61                        }
62
63                        this->blk++;
64                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
65                };
66
67                this->pos = -1;
68                return (this->pos);
69        }
70
71        /* Set or reset the iterator to position new_pos. */
72        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {
73                const scanblock_t one_bit = 1;
74                this->blk = new_pos / (sizeof(scanblock_t)*8);
75                this->pos = new_pos % (sizeof(scanblock_t)*8);
76                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
77                // clear bit at pos and all positions to the right.
78                scanblock_t marker = one_bit << this->pos;
79                this->scan_blk = this->scan_blk &~((marker-1)|marker); 
80        }
81
82        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
83        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
84        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
85        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
86
87};
88
89// Reverse
90template <class bitblock_t, class scanblock_t>
91class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
92
93public:
94        ReverseScanner(){}
95        ReverseScanner(const bitblock_t * s) {
96                init(s);
97        }
98        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
99                this->strm = s;
100                this->pos = 0;
101                this->blk = BLOCK_COUNT;
102                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
103        }
104
105        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
106                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
107                while (this->blk > 0){
108                        if(has_bit(this->scan_blk)){
109                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk-1) * sizeof(scanblock_t)*8 );
110                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
111                                return (this->pos);
112                        }
113
114                        this->blk--;
115                        this->scan_blk = *((scanblock_t *)this->strm + this->blk-1);
116                };
117
118                this->pos = -1;
119                return (this->pos);
120        }
121
122        /* Set or reset the iterator to position new_pos. */
123        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {
124                const scanblock_t one_bit = 1;
125                this->blk = new_pos / (sizeof(scanblock_t)*8);
126                this->pos = new_pos % (sizeof(scanblock_t)*8);
127                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
128                // clear bit at pos and all positions to the left.
129                scanblock_t marker = one_bit << this->pos;
130                this->scan_blk = this->scan_blk &(marker-1); 
131        }
132
133        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
134        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
135        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
136        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
137
138        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
139
140};
141
142
143#endif // BITBLOCK_SCAN_H_
144
Note: See TracBrowser for help on using the repository browser.