source: trunk/lib/bitblock_scan.hpp @ 1977

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

Added 'is_done' method to bit block scanner.

File size: 3.4 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        IDISA_ALWAYS_INLINE bool is_done() {return (-1==pos);}
72        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {return this->strm = strm;}
73        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
74        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
75
76};
77
78// Reverse
79template <class bitblock_t, class scanblock_t>
80class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
81
82public:
83        ReverseScanner(){}
84        ReverseScanner(const bitblock_t * s) {
85                init(s);
86        }
87        IDISA_ALWAYS_INLINE void init(const bitblock_t * s) {
88                this->strm = s;
89                this->pos = 0;
90                this->blk = BLOCK_COUNT;
91                this->scan_blk = *((scanblock_t *)s + (BLOCK_COUNT-1));
92        }
93
94        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
95                const scanblock_t one_bit = 1;  /* ensure enough bits for shift: one_bit << this->pos */
96                while (this->blk > 0){
97                        if(has_bit(this->scan_blk)){
98                                this->pos = (sizeof(scanblock_t)*8 - scan_backward_zeroes(this->scan_blk) -1) + ( (this->blk-1) * sizeof(scanblock_t)*8 );
99                                this->scan_blk = this->scan_blk ^ (one_bit << this->pos); // clear leftmost bit
100                                return (this->pos);
101                        }
102
103                        this->blk--;
104                        this->scan_blk = *((scanblock_t *)this->strm + this->blk-1);
105                };
106
107                this->pos = -1;
108                return (this->pos);
109        }
110
111        IDISA_ALWAYS_INLINE bool is_done() {return (-1==pos);}
112        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {return this->strm = strm;}
113        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
114        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
115
116        static const uint32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
117
118};
119
120
121#endif // BITBLOCK_SCAN_H_
122
Note: See TracBrowser for help on using the repository browser.