aboutsummaryrefslogtreecommitdiff
path: root/src/unstable/bitstring.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/unstable/bitstring.h')
-rw-r--r--src/unstable/bitstring.h224
1 files changed, 224 insertions, 0 deletions
diff --git a/src/unstable/bitstring.h b/src/unstable/bitstring.h
new file mode 100644
index 0000000..7a8fc48
--- /dev/null
+++ b/src/unstable/bitstring.h
@@ -0,0 +1,224 @@
1/*
2 * Copyright (C) 2007-2011 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#ifndef BU_BITSTRING_H
9#define BU_BITSTRING_H
10
11#include "bu/util.h"
12#include "bu/string.h"
13
14namespace Bu
15{
16 /**
17 * Manages an arbitrarily sized string of bits, and allows basic interaction
18 * with them. This includes basic non-mathematical bitwise operations such
19 * as setting and testing bits, shifting the string, inversion and a few
20 * extras like randomization. On linux systems this takes advantage of long
21 * longs giving you a maximum size of about 2tb per string.
22 *
23 * For more general and mathematical type interaction see BitStringInt.
24 *
25 */
26 class BitString
27 {
28 public:
29 /**
30 * Constructs a blank and basic BitString. This is actually useful
31 * since you can resize BitStrings at will, and even retain the data
32 * that was in them.
33 */
34 BitString();
35
36 /**
37 * Constructs a BitString object as a copy of another BitString. This
38 * is a standard copy constructor and produces an exact duplicate of
39 * the original BitString object.
40 *@param xSrc Source BitString to copy data from.
41 */
42 BitString( const BitString &xSrc );
43
44 /**
45 * Constructs a BitString with length iBits and optionally fills it with
46 * random data. The default setting, to not fill randomly, will produce
47 * a blank (all zeros) string of the specified size.
48 *@param iBits The length of the new BitString in bits.
49 *@param bFillRandomly Wether or not to randomize this BitString.
50 */
51 BitString( long iBits, bool bFillRandomly=false );
52
53 /**
54 * Virtual deconstructor for the BitString. Takes care of cleanup for
55 * you. What more do you really want to know?
56 */
57 virtual ~BitString();
58
59 // basic interaction
60 /**
61 * Sets a bit in the BitString. In it's normal mode it will always turn
62 * the given bit on, to clear a bit set bBitState to false instead of
63 * true. This operation runs in O(1).
64 *@param iBit The zero-based index of the bit to modify.
65 *@param bBitState Set to true to set the bit to 1, set to false to set
66 * the bit to 0.
67 */
68 void setBit( long iBit, bool bBitState=true );
69
70 /**
71 * Reverses the state of the given bit. This will set the given bit
72 * to a 1 if it was 0, and to 0 if it was 1. This operation runs in
73 * O(1), and it should be noted that using this is marginally faster
74 * than doing the test and flip yourself with getBit and setBit since
75 * it uses a bitwise not operation and doesn't actually test the bit
76 * itself.
77 *@param iBit The index of the bit to flip.
78 */
79 void flipBit( long iBit );
80
81 /**
82 * Gets the state of the given bit. This follows the standard
83 * convention used so far, a returned value of true means the bit in
84 * question is 1, and a value of flase means the bit is 0. All bits
85 * out of range of the BitString are treated as off, but are
86 * "accessable" in that this does not produce any kind of error
87 * message. This is intentional. This operation runs in O(1).
88 *@param iBit The index of the bit to test.
89 *@returns True for a 1, false for a 0.
90 */
91 bool getBit( long iBit );
92
93 /**
94 * Inverts the entire BitString, in effect this calls flipBit on every
95 * bit in the string but is faster since it can operate on whole bytes
96 * at a time instead of individual bits. This operation runs in O(N).
97 */
98 void invert();
99
100 /**
101 * Returns the number of bits allocated in this BitString. This
102 * operation runs in O(1) time since this value is cached and not
103 * computed.
104 *@returns The number of bits allocated in this BitString.
105 */
106 DEPRECATED
107 long getBitLength();
108
109 long getSize();
110
111 /**
112 * Sets the entire BitString to zeros, but it does it very quickly.
113 * This operation runs in O(N).
114 */
115 void clear();
116
117 /**
118 * Gets another BitString that is autonomous of the current one
119 * (contains a copy of the memory, not a pointer) and contains a subset
120 * of the data in the current BitString. This is an inclusive
121 * operation, so grabbing bits 0-5 will give you 6 bits. This is based
122 * on a very tricky bit-shifting algorithm and runs very quickly, in
123 * O(N) time. Passing in a value of zero for iUpper, or any value for
124 * iUpper that is less than iLower will set iUpper equal to the number
125 * of bits in the BitString.
126 *@param iLower The first bit in the current string, will be the first
127 * bit (0 index) in the new sub string.
128 *@param iUpper The last bit in the current string, will be the last
129 * bit in the new sub string. iUpper is included in the sub string.
130 *@returns A new BitString object ready to be used. Please note that
131 * managing this new object is up to whomever calls this function.
132 */
133 class BitString getSubString( long iLower, long iUpper );
134
135 /**
136 * Sets the number of bits in the BitString, allocating more memory if
137 * necesarry, or freeing extra if able. The default operation of this
138 * function clears all data in the BitString while resizing it. If you
139 * would like to keep as much of the data that you had in your BitString
140 * as possible, then set bClear to false, and any data that will fit
141 * into the new BitString length will be retained. If increasing the
142 * number of bits, the new bits will come into existance cleared (set
143 * to 0).
144 *@param iLength The number of bits to set the BitString to.
145 *@param bClear When true, all data is eradicated and zeroed, when set
146 * to false an effort is made to retain the existing data.
147 *@returns true on success, false on failure.
148 */
149 DEPRECATED
150 bool setBitLength( long iLength, bool bClear=true );
151 bool setSize( long iLength, bool bClear=true );
152
153 /**
154 * Randomize the entire BitString, one bit at a time. This is actually
155 * the function called by the constructor when the user selects initial
156 * randomization. This function uses the system random() function, so
157 * srandom may be used to effect this process at will.
158 */
159 void randomize();
160
161 /**
162 * Operates exactly like <<. All data in the BitString is shifted to
163 * the left by some number of bits, any data pushed off the edge of the
164 * BitString is lost, and all new data coming in will be zeroed.
165 * Using a negative value in the shiftLeft function will turn it into
166 * the shiftRight function.
167 *@param iAmt The number of bit positions to shift all data.
168 */
169 void shiftLeft( long iAmt ); // just like <<
170
171 /**
172 * Operates exactly like >>. All data in the BitString is shifted to
173 * the right by some number of bits, any data pushed off the edge of the
174 * BitString is lost, and all new data coming in will be zeroed.
175 * Using a negative value in the shiftRight function will turn it into
176 * the shiftLeft function.
177 *@param iAmt The number of bit positions to shift all data.
178 */
179 void shiftRight( long iAmt ); // just like >>
180
181 /**
182 * Searches through the BitString and returns the index of the highest
183 * order bit position (the highest index) with an on bit (a bit set to
184 * 1). This is a handy helper function and rather faster than calling
185 * getBit() over and over again.
186 *@returns The index of the highest indexed on bit.
187 */
188 long getHighestOrderBitPos();
189
190 // Conversion
191 /**
192 * Convert a block of data (no more than 32 bits) to a primitive long
193 * type.
194 * This is done in a little bit interesting way, so it may not always be
195 * the fastest way to access the data that you want, although it will
196 * always ensure that the long that is written makes numerical sense, as
197 * we write numbers, regaurdless of platform.
198 *@param iStart The first bit in the BitString to include in the long
199 *@param iSize THe number of bits to include, if this value is set over
200 * 32 it will be automatically truncated to, or however many bits there
201 * are in a long in your system.
202 *@returns A long converted from your raw BitString data.
203 */
204 long toLong( long iStart = 0, long iSize = 32 );
205
206 Bu::String toString();
207
208 //operators
209 BitString &operator=( const BitString &xSrc );
210 BitString operator~();
211 BitString operator<<( const long iAmt );
212 BitString operator>>( const long iAmt );
213
214 private:
215 void fixup();
216 void setMask();
217 unsigned char *caData;
218 long iBits;
219 long iBytes;
220 unsigned char cTopByteMask;
221 };
222};
223
224#endif