source: trunk/lib/bitblock_scan.hpp @ 1933

Last change on this file since 1933 was 1932, checked in by ksherdy, 8 years ago

Update uint32_t to int32_t since negative positions indicate 'not
found'.

File size: 2.8 KB
Line 
1/*
2 * bitblock_scan.hpp
3 */
4
5#ifndef BITBLOCK_SCAN_H_
6#define BITBLOCK_SCAN_H_
7
8#include <iterator>
9#include <iostream>
10using namespace std;
11
12#include "bitblock.hpp"
13
14/*
15 * Templated scanner forward and reverse scanner classes on biblock_t, scanblock_t.
16 */ 
17 
18// Base
19template <class bitblock_t, class scanblock_t>
20class Scanner {
21
22protected:
23        Scanner(): strm(NULL), pos(-1), blk(-1), scan_blk(-1) {}
24        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) {}
25
26        const bitblock_t * strm;
27        int32_t pos;
28        uint32_t blk;
29        scanblock_t scan_blk;
30        /* The test here needs to be != 0, not > 0, in case scanblock_t is signed.*/
31        IDISA_ALWAYS_INLINE bool has_bit(scanblock_t x) const {return x != 0;};
32};
33
34// Forward
35template <class bitblock_t, class scanblock_t>
36class ForwardScanner: public Scanner<bitblock_t, scanblock_t> {
37
38public:
39
40        ForwardScanner(){}
41        ForwardScanner(const bitblock_t * s) {
42                init(s);
43        }
44
45        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
46                this->strm = s;
47                this->pos = 0;
48                this->blk = 0;
49                this->scan_blk = *(scanblock_t *)s;
50        }
51
52        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
53                while (this->blk < (sizeof(bitblock_t)/sizeof(scanblock_t))){
54                        if(has_bit(this->scan_blk)){
55                                this->pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
56                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
57
58                                return (this->pos);
59                        }
60
61                        this->blk++;
62                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
63                };
64
65                this->pos = -1;
66                return (this->pos);
67        }
68
69        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
70        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
71
72};
73
74// Reverse
75template <class bitblock_t, class scanblock_t>
76class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
77
78public:
79        ReverseScanner(){}
80        ReverseScanner(const bitblock_t * s) {
81                init(s);
82        }
83        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
84                this->strm = s;
85                this->pos = 0;
86                this->blk = BLOCK_COUNT;
87                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
88        }
89
90        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
91                while (this->blk > 0){
92                        if(has_bit(this->scan_blk)){
93                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk-1) * sizeof(scanblock_t)*8 );
94                                this->scan_blk = this->scan_blk ^ (1 << this->pos); // clear leftmost bit
95                                return (this->pos);
96                        }
97
98                        this->blk--;
99                        this->scan_blk = *((scanblock_t *)this->strm + this->blk-1);
100                };
101
102                this->pos = -1;
103                return (this->pos);
104        }
105
106        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
107        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
108
109        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
110
111};
112
113
114#endif /* BITBLOCK_SCAN_H_ */
115
Note: See TracBrowser for help on using the repository browser.