source: trunk/lib/bitblock_scan.hpp @ 2196

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

Fixed reverse scanner logic impose strict inequality test on blk count.

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
21// Base
22template <class bitblock_t, class scanblock_t>
23class Scanner {
24
25protected:
26        Scanner(): strm(NULL), pos(-1), blk(-1), scan_blk(-1) {}
27        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) {}
28
29        const bitblock_t * strm;
30        int32_t pos;
31        int32_t blk;
32        scanblock_t scan_blk;
33        /* The test here needs to be != 0, not > 0, in case scanblock_t is signed.*/
34        IDISA_ALWAYS_INLINE bool has_bit(scanblock_t x) const {return x != 0;};
35};
36
37// Forward
38template <class bitblock_t, class scanblock_t>
39class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {
40
41public:
42
43        ForwardScanner(){}
44        ForwardScanner(const bitblock_t * s) {
45                init(s);
46        }
47
48        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
49                this->strm = s;
50                this->pos = 0;
51                this->blk = 0;
52                this->scan_blk = *(scanblock_t *)s;
53        }
54
55        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
56                while (this->blk < BLOCK_COUNT){
57                        if(has_bit(this->scan_blk)){
58                                this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
59                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
60
61                                return (this->pos);
62                        }
63
64                        this->blk++;
65                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
66                };
67
68                this->pos = -1;
69                return (this->pos);
70        }
71
72        /* Set or reset the iterator to position new_pos. */
73        IDISA_ALWAYS_INLINE void move_to(uint32_t new_pos) {           
74                const scanblock_t one_bit = 1;
75                this->blk = new_pos / (sizeof(scanblock_t)*8);
76                this->pos = new_pos % (sizeof(scanblock_t)*8);
77                this->scan_blk = ((scanblock_t *)this->strm)[this->blk];
78                // clear bit at pos and all positions to the right.
79                scanblock_t marker = one_bit << this->pos;
80                this->scan_blk = this->scan_blk &~((marker-1)|marker); 
81        }
82
83        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
84        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
85        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
86        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
87
88        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
89
90};
91
92// Reverse
93template <class bitblock_t, class scanblock_t>
94class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
95
96public:
97        ReverseScanner(){}
98        ReverseScanner(const bitblock_t * s) {
99                init(s);
100        }
101        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
102                this->strm = s;
103                this->pos = 0;
104                this->blk = BLOCK_COUNT-1;
105                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
106        }
107
108        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
109                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
110                while (this->blk > -1){
111                        if(has_bit(this->scan_blk)){
112                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk) * sizeof(scanblock_t)*8 );
113                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
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 left.
132                scanblock_t marker = one_bit << this->pos;
133                this->scan_blk = this->scan_blk & (marker-1);
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
145
146#endif // BITBLOCK_SCAN_H_
147
Note: See TracBrowser for help on using the repository browser.