aboutsummaryrefslogtreecommitdiff
path: root/src/bitstring.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/bitstring.h')
-rw-r--r--src/bitstring.h251
1 files changed, 251 insertions, 0 deletions
diff --git a/src/bitstring.h b/src/bitstring.h
new file mode 100644
index 0000000..8052691
--- /dev/null
+++ b/src/bitstring.h
@@ -0,0 +1,251 @@
1#ifndef BU_BITSTRING_H
2#define BU_BITSTRING_H
3
4namespace Bu
5{
6 /**
7 * Manages an arbitrarily sized string of bits, and allows basic interaction
8 * with them. This includes basic non-mathematical bitwise operations such
9 * as setting and testing bits, shifting the string, inversion and a few
10 * extras like randomization. On linux systems this takes advantage of long
11 * longs giving you a maximum size of about 2tb per string.
12 *
13 * For more general and mathematical type interaction see BitStringInt.
14 *
15 *@author Mike Buland
16 */
17 class BitString
18 {
19 public:
20 /**
21 * Constructs a blank and basic BitString. This is actually useful since
22 * you can resize BitStrings at will, and even retain the data that was
23 * in them.
24 */
25 BitString();
26
27 /**
28 * Constructs a BitString object as a copy of another BitString. This is
29 * a standard copy constructor and produces an exact duplicate of the
30 * original BitString object.
31 *@param xSrc Source BitString to copy data from.
32 */
33 BitString( const BitString &xSrc );
34
35 /**
36 * Constructs a BitString with length nBits and optionally fills it with
37 * random data. The default setting, to not fill randomly, will produce
38 * a blank (all zeros) string of the specified size.
39 *@param nBits The length of the new BitString in bits.
40 *@param bFillRandomly Wether or not to randomize this BitString.
41 */
42 BitString( long nBits, bool bFillRandomly=false );
43
44 /**
45 * Virtual deconstructor for the BitString. Takes care of cleanup for you.
46 * What more do you really want to know?
47 */
48 virtual ~BitString();
49
50 // basic interaction
51 /**
52 * Sets a bit in the BitString. In it's normal mode it will always turn
53 * the given bit on, to clear a bit set bBitState to false instead of
54 * true. This operation runs in O(1).
55 *@param nBit The zero-based index of the bit to modify.
56 *@param bBitState Set to true to set the bit to 1, set to false to set
57 * the bit to 0.
58 */
59 void setBit( long nBit, bool bBitState=true );
60
61 /**
62 * Reverses the state of the given bit. This will set the given bit to a
63 * 1 if it was 0, and to 0 if it was 1. This operation runs in O(1), and
64 * it should be noted that using this is marginally faster than doing the
65 * test and flip yourself with getBit and setBit since it uses a bitwise
66 * not operation and doesn't actually test the bit itself.
67 *@param nBit The index of the bit to flip.
68 */
69 void flipBit( long nBit );
70
71 /**
72 * Gets the state of the given bit. This follows the standard convention
73 * used so far, a returned value of true means the bit in question is 1,
74 * and a value of flase means the bit is 0. All bits out of range of the
75 * BitString are treated as off, but are "accessable" in that this does not
76 * produce any kind of error message. This is intentional. This operation
77 * runs in O(1).
78 *@param nBit The index of the bit to test.
79 *@returns True for a 1, false for a 0.
80 */
81 bool getBit( long nBit );
82
83 /**
84 * Inverts the entire BitString, in effect this calls flipBit on every bit
85 * in the string but is faster since it can operate on whole bytes at a
86 * time instead of individual bits. This operation runs in O(N).
87 */
88 void invert();
89
90 /**
91 * Returns the number of bits allocated in this BitString. This operation
92 * runs in O(N) time since this value is cached and not computed.
93 *@returns The number of bits allocated in this BitString.
94 */
95 long getBitLength();
96
97 /**
98 * Sets the entire BitString to zeros, but it does it very quickly. This
99 * operation runs in O(N).
100 */
101 void clearString();
102
103 /**
104 * Gets another BitString that is autonomous of the current one (contains
105 * a copy of the memory, not a pointer) and contains a subset of the data
106 * in the current BitString. This is an inclusive operation, so grabbing
107 * bits 0-5 will give you 6 bits. This is based on a very tricky
108 * bit-shifting algorithm and runs very quickly, in O(N) time.
109 * Passing in a value of zero for nUpper, or any value for nUpper that is
110 * less than nLower will set nUpper equal to the number of bits in the
111 * BitString.
112 *@param nLower The first bit in the current string, will be the first bit
113 * (0 index) in the new sub string.
114 *@param nUpper The last bit in the current string, will be the last bit in
115 * the new sub string. nUpper is included in the sub string.
116 *@returns A new BitString object ready to be used. Please note that
117 * managing this new object is up to whomever calls this function.
118 */
119 class BitString getSubString( long nLower, long nUpper );
120
121 /**
122 * Sets the number of bits in the BitString, allocating more memory if
123 * necesarry, or freeing extra if able. The default operation of this
124 * function clears all data in the BitString while resizing it. If you
125 * would like to keep as much of the data that you had in your BitString
126 * as possible, then set bClear to false, and any data that will fit into
127 * the new BitString length will be retained. If increasing the number of
128 * bits, the new bits will come into existance cleared (set to 0).
129 *@param nLength The number of bits to set the BitString to.
130 *@param bClear When true, all data is eradicated and zeroed, when set to
131 * false an effort is made to retain the existing data.
132 *@returns true on success, false on failure.
133 */
134 bool setBitLength( long nLength, bool bClear=true );
135
136 /**
137 * Randomize the entire BitString, one bit at a time. This is actually
138 * the function called by the constructor when the user selects initial
139 * randomization. This function uses the system random() function, so
140 * srandom may be used to effect this process at will.
141 */
142 void randomize();
143
144 /**
145 * Operates exactly like <<. All data in the BitString is shifted to
146 * the left by some number of bits, any data pushed off the edge of the
147 * BitString is lost, and all new data coming in will be zeroed.
148 * Using a negative value in the shiftLeft function will turn it into the
149 * shiftRight function.
150 *@param nAmt The number of bit positions to shift all data.
151 */
152 void shiftLeft( long nAmt ); // just like <<
153
154 /**
155 * Operates exactly like >>. All data in the BitString is shifted to
156 * the right by some number of bits, any data pushed off the edge of the
157 * BitString is lost, and all new data coming in will be zeroed.
158 * Using a negative value in the shiftRight function will turn it into the
159 * shiftLeft function.
160 *@param nAmt The number of bit positions to shift all data.
161 */
162 void shiftRight( long nAmt ); // just like >>
163
164 /**
165 * Searches through the BitString and returns the index of the highest
166 * order bit position (the highest index) with an on bit (a bit set to 1).
167 * This is a handy helper function and rather faster than calling getBit()
168 * over and over again.
169 *@returns The index of the highest indexed on bit.
170 */
171 long getHighestOrderBitPos();
172
173 // Conversion
174 /**
175 * Convert a block of data (no more than 32 bits) to a primitive long type.
176 * This is done in a little bit interesting way, so it may not always be
177 * the fastest way to access the data that you want, although it will
178 * always ensure that the long that is written makes numerical sense, as
179 * we write numbers, regaurdless of platform.
180 *@param nStart The first bit in the BitString to include in the long
181 *@param nSize THe number of bits to include, if this value is set over
182 * 32 it will be automatically truncated to, or however many bits there
183 * are in a long in your system.
184 *@returns A long converted from your raw BitString data.
185 */
186 long toLong( long nStart = 0, long nSize = 32 );
187
188 /**
189 * Converts the data into a human-readable SString object. SString is
190 * used to make transport of the string and management very simple. Since
191 * BitStrings will generally be longer than your average strip of ints a
192 * faculty is included and turned on by default that will insert spacers
193 * into the output text every 8 places. For debugging work, this is
194 * definately reccomended.
195 *@param bAddSpacers Leave set to true in order to have the output broken
196 * into logical groupings of 8 bits per block. Set to off to have a harder
197 * to read solid block of bits.
198 *@returns A SString object containing the produced string.
199 */
200 //std::string toString( bool bAddSpacers = true );
201
202 // Utility
203 /**
204 * Converts the given number of bits into the smallest allocatable unit,
205 * which is bytes in C and on most systems nowadays. This is the minimum
206 * number of bytes needed to contain the given number of bits, so there is
207 * generally some slop if they are not evenly divisible.
208 *@param nBits The number of bits you wish to use.
209 *@returns The number of bytes you will need to contain the given number
210 * of bits.
211 */
212 //static long bitsToBytes( long nBits );
213
214 /**
215 * Writes all data in the BitString, including a small header block
216 * describing the number of bits in the BitString to the file described
217 * by the given file descriptor. The data writen is purely sequential and
218 * probably not too easy to read by other mechanisms, although the
219 * readFromFile function should always be able to do it. This function
220 * does not open nor close the file pointed to by fh.
221 *@param fh The file descriptor of the file to write the data to.
222 *@returns true if the operation completed without error, false otherwise.
223 */
224 //bool writeToFile( FILE *fh );
225
226 /**
227 * Reads data formatted by writeToFile and clears out any data that may
228 * have been in the BitString. This function preserves nothing in the
229 * original BitString that it may be replacing. This function does not
230 * open nor close the file pointed to by fh.
231 *@param fh The file descriptor to try to read the data from.
232 *@returns true if the operation completed without error, false otherwise.
233 */
234 //bool readFromFile( FILE *fh );
235
236 //operators
237 BitString &operator=( const BitString &xSrc );
238 BitString operator~();
239 BitString operator<<( const long nAmt );
240 BitString operator>>( const long nAmt );
241
242 private:
243 void fixup();
244 unsigned char *caData;
245 long nBits;
246 long nBytes;
247 unsigned char cTopByteMask;
248 };
249};
250
251#endif