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