aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2008-07-23 05:27:30 +0000
committerMike Buland <eichlan@xagasoft.com>2008-07-23 05:27:30 +0000
commit0047991313fd7c67b45c59d58e3fde0236bf3872 (patch)
treeb2b0abbc67f7c276a71583270e57c1da46293f4d
parent57046f7fcbc6cd50105bd926b8f34732e302988a (diff)
downloadlibbu++-0047991313fd7c67b45c59d58e3fde0236bf3872.tar.gz
libbu++-0047991313fd7c67b45c59d58e3fde0236bf3872.tar.bz2
libbu++-0047991313fd7c67b45c59d58e3fde0236bf3872.tar.xz
libbu++-0047991313fd7c67b45c59d58e3fde0236bf3872.zip
Added BitString, it was used in a few projects. It needs a few functions to
be corrected, they were using standard library features, that shouldn't be hard to fix though.
Diffstat (limited to '')
-rw-r--r--src/bitstring.cpp440
-rw-r--r--src/bitstring.h251
2 files changed, 691 insertions, 0 deletions
diff --git a/src/bitstring.cpp b/src/bitstring.cpp
new file mode 100644
index 0000000..8d99992
--- /dev/null
+++ b/src/bitstring.cpp
@@ -0,0 +1,440 @@
1#include "bitstring.h"
2#include <stdlib.h>
3#include <stdio.h>
4#include <string.h>
5
6#ifdef _WIN32
7#define random() rand()
8#endif
9
10#define bitsToBytes( nBits ) (((nBits/8)+((nBits%8)?(1):(0))));
11
12Bu::BitString::BitString()
13{
14 caData = NULL;
15 cTopByteMask = 0;
16 nBits = nBytes = 0;
17}
18
19Bu::BitString::BitString( const Bu::BitString &xSrc )
20{
21 nBits = xSrc.nBits;
22 nBytes = xSrc.nBytes;
23 cTopByteMask = xSrc.cTopByteMask;
24 caData = new unsigned char[nBytes];
25 memcpy( caData, xSrc.caData, nBytes );
26
27 fixup();
28}
29
30Bu::BitString::BitString( long nNewBits, bool bFillRandomly )
31{
32 long j;
33 nBits = nNewBits;
34 nBytes = bitsToBytes( nNewBits );//(nNewBits/8)+((nNewBits%8)?(1):(0));
35 caData = new unsigned char[nBytes];
36
37 // This can either mean that there are a multiple of eight bits or zero, if there are zero you're an idiot
38 // (zero can't happen, because we would allocate an extra byte and never use it)
39 if( (nBits%8 == 0) )
40 {
41 cTopByteMask = 0xFF;
42 }
43 else
44 {
45 cTopByteMask = 0;
46 for( j = 0; j < (nBits%8); j++ )
47 {
48 cTopByteMask |= (1<<j);
49 }
50 }
51
52 if( bFillRandomly )
53 {
54 // rand() only returns a value up to RAND_MAX (0x7FFF on my system) so I'll just use the low order byte)
55 for( j = 0; j < nBytes; j++ )
56 {
57 caData[j] = (unsigned char)(random() & 0xFF);
58 }
59 }
60 else
61 {
62 clearString();
63 }
64
65 fixup();
66}
67
68Bu::BitString::~BitString()
69{
70 if( caData != NULL ) delete[] caData;
71}
72
73Bu::BitString &Bu::BitString::operator=( const Bu::BitString &xSrc )
74{
75 if( caData != NULL )
76 {
77 delete[] caData;
78 }
79 nBits = xSrc.nBits;
80 nBytes = xSrc.nBytes;
81 cTopByteMask = xSrc.cTopByteMask;
82 caData = new unsigned char[nBytes];
83 memcpy( caData, xSrc.caData, nBytes );
84
85 fixup();
86
87 return *this;
88}
89
90Bu::BitString Bu::BitString::operator~()
91{
92 Bu::BitString xRet( *this );
93
94 for( int j = 0; j < xRet.nBytes; j++ )
95 {
96 xRet.caData[j] = ~xRet.caData[j];
97 }
98
99 xRet.fixup();
100
101 return xRet;
102}
103
104Bu::BitString Bu::BitString::operator<<( const long nAmt )
105{
106 if( nAmt == 0 )
107 {
108 return (*this);
109 }
110 //int nByteShift = nAmt/8;
111
112 Bu::BitString xSub( getBitLength() );
113
114 long shft = (nAmt%8);
115 long base = (nAmt/8);
116 unsigned char lowmask=0;
117 for( long j = 0; j < 8-shft; j++ )
118 {
119 lowmask |= (1<<j);
120 }
121 for( long j = 0; j < xSub.nBytes; j++ )
122 {
123 xSub.caData[base+j] = ((caData[j]>>shft)&(lowmask)) | ((caData[j+1]<<(8-shft))&(~lowmask));
124 }
125 xSub.fixup();
126
127 return xSub;
128}
129
130Bu::BitString Bu::BitString::operator>>( const long nAmt )
131{
132 if( nAmt == 0 )
133 {
134 return (*this);
135 }
136 return (*this);
137}
138
139void Bu::BitString::shiftLeft( long nAmt )
140{
141 if( nAmt == 0 )
142 {
143 return;
144 }
145 else if( nAmt < 0 )
146 {
147 shiftRight( -nAmt );
148 return;
149 }
150
151 long nByteShift = nAmt/8;
152 long nBitShift = nAmt%8;
153
154 long j;
155 for( j = nBytes-1; j >= 0; j-- )
156 {
157 caData[j] = (((j-nByteShift)<0)?(0):((caData[j-nByteShift]<<nBitShift))) | (((j-nByteShift-1)<0)?(0):((caData[j-nByteShift-1]>>(8-nBitShift))));
158 }
159
160 fixup();
161}
162
163void Bu::BitString::shiftRight( long nAmt )
164{
165 if( nAmt == 0 )
166 {
167 return;
168 }
169 else if( nAmt < 0 )
170 {
171 shiftLeft( -nAmt );
172 return;
173 }
174
175 long nByteShift = nAmt/8;
176 long nBitShift = nAmt%8;
177
178 long j;
179 for( j = 0; j < nBytes; j++ )
180 {
181 caData[j] = (((j+nByteShift)>nBytes)?(0):((caData[j+nByteShift]>>nBitShift))) | (((j+nByteShift+1)>nBytes)?(0):((caData[j+nByteShift+1]<<(8-nBitShift))));
182 }
183
184 fixup();
185}
186/*
187long Bu::BitString::bitsToBytes( long nBits )
188{
189 return (nBits/8)+((nBits%8)?(1):(0));
190}
191*/
192void Bu::BitString::fixup()
193{
194 if( caData != NULL )
195 {
196 caData[nBytes-1] &= cTopByteMask;
197 }
198}
199
200void Bu::BitString::setBit( long nBit, bool bBitState )
201{
202 if( bBitState )
203 {
204 caData[nBit/8] |= (1<<(nBit%8));
205 }
206 else
207 {
208 caData[nBit/8] &= ~(1<<(nBit%8));
209 }
210}
211
212void Bu::BitString::flipBit( long nBit )
213{
214 caData[nBit/8] ^= (1<<(nBit%8));
215}
216
217bool Bu::BitString::getBit( long nBit )
218{
219 if( nBit >= nBits || nBit < 0 ) return false;
220 if( (caData[nBit/8] & (1<<(nBit%8))) == 0 )
221 {
222 return false;
223 }
224 return true;
225}
226
227long Bu::BitString::getBitLength()
228{
229 return nBits;
230}
231
232class Bu::BitString Bu::BitString::getSubString( long nLower, long nUpper )
233{
234 if( nUpper == 0 || nUpper < nLower ) nUpper = nBits;
235
236 Bu::BitString xSub( nUpper-nLower+1 );
237
238 long shft = (nLower%8);
239 long base = (nLower/8);
240 unsigned char lowmask=0;
241 for( long j = 0; j < 8-shft; j++ )
242 {
243 lowmask |= (1<<j);
244 }
245 for( long j = 0; j < xSub.nBytes; j++ )
246 {
247 xSub.caData[j] = ((caData[base+j]>>shft)&(lowmask)) | ((caData[base+j+1]<<(8-shft))&(~lowmask));
248 }
249 xSub.fixup();
250
251 return xSub;
252}
253
254long Bu::BitString::toLong( long nStart, long nSize )
255{
256 if( nSize < 1 ) nSize = 1;
257 if( nSize > 32 ) nSize = 32;
258 if( nStart < 0 ) return 0;
259 if( nStart+nSize > getBitLength() ) return 0;
260
261 Bu::BitString tmpo;
262 tmpo = getSubString( nStart, nStart+nSize-1 );
263 long x = *((long *)tmpo.caData);
264
265 return x;
266}
267/*
268std::string Bu::BitString::toString( bool bAddSpacers )
269{
270 long nSz = nBits;
271 if( bAddSpacers )
272 {
273 nSz += (nBits/8);
274 if( nBits%8 == 0 ) nSz--;
275 }
276 std::string xStr;
277
278 int bw=0;
279 int of=0;
280 for( int j = nBits-1; j >= 0; j-- )
281 {
282 if( getBit( j ) )
283 {
284 xStr += '1';
285 }
286 else
287 {
288 xStr += '0';
289 }
290
291 if( bAddSpacers )
292 {
293 bw++;
294 if( bw >= 8 && j < nBits-1 )
295 {
296 bw = 0;
297 of++;
298 xStr += ' ';
299 }
300 }
301 }
302
303 return xStr;
304}
305*/
306void Bu::BitString::clearString()
307{
308 if( caData != NULL )
309 {
310 memset( caData, 0, nBytes );
311 }
312}
313
314bool Bu::BitString::setBitLength( long nLength, bool bClear )
315{
316 if( nBits != nLength )
317 {
318 if( bClear || caData == NULL )
319 {
320 //long j;
321 nBits = nLength;
322 nBytes = bitsToBytes( nLength );//(nNewBits/8)+((nNewBits%8)?(1):(0));
323 if( caData != NULL ) delete[] caData;
324 caData = new unsigned char[nBytes];
325 memset( caData, 0, nBytes );
326 }
327 else
328 {
329 //long j;
330 nBits = nLength;
331 long nNewBytes = bitsToBytes( nLength );//(nNewBits/8)+((nNewBits%8)?(1):(0));
332 unsigned char *tmp = caData;
333 caData = new unsigned char[nBytes];
334 if( nNewBytes < nBytes )
335 {
336 memcpy( caData, tmp, nNewBytes );
337 }
338 else
339 {
340 memcpy( caData, tmp, nBytes );
341 }
342 delete[] tmp;
343 nBytes = nNewBytes;
344 }
345
346 // This can either mean that there are a multiple of eight bits or zero, if there are zero you're an idiot
347 // (zero can't happen, because we would allocate an extra byte and never use it)
348 if( (nBits%8 == 0) )
349 {
350 cTopByteMask = 0xFF;
351 }
352 else
353 {
354 cTopByteMask = 0;
355 for( long j = 0; j < (nBits%8); j++ )
356 {
357 cTopByteMask |= (1<<j);
358 }
359 }
360 }
361 else if( bClear )
362 {
363 clearString();
364 }
365
366 return true;
367}
368
369void Bu::BitString::randomize()
370{
371 if( caData != NULL )
372 {
373 for( int j = 0; j < nBytes; j++ )
374 {
375 caData[j] = (unsigned char)(random() & 0xFF);
376 }
377 fixup();
378 }
379}
380
381void Bu::BitString::invert()
382{
383 if( caData != NULL )
384 {
385 for( long j = 0; j < nBytes; j++ )
386 {
387 caData[j] = ~caData[j];
388 }
389 fixup();
390 }
391}
392
393long Bu::BitString::getHighestOrderBitPos()
394{
395 for( long j = nBits-1; j >= 0; j-- )
396 {
397 if( getBit( j ) )
398 {
399 return j;
400 }
401 }
402
403 return -1;
404}
405/*
406bool Bu::BitString::writeToFile( FILE *fh )
407{
408 fwrite( &nBits, sizeof(long), 1, fh );
409 fwrite( caData, sizeof(char), nBytes, fh );
410
411 return true;
412}
413
414bool Bu::BitString::readFromFile( FILE *fh )
415{
416 fread( &nBits, sizeof(long), 1, fh );
417
418 nBytes = bitsToBytes( nBits );
419 if( caData ) delete[] caData;
420 caData = new unsigned char[nBytes];
421
422 fread( caData, sizeof(char), nBytes, fh );
423
424 if( (nBits%8 == 0) )
425 {
426 cTopByteMask = 0xFF;
427 }
428 else
429 {
430 cTopByteMask = 0;
431 for( int j = 0; j < (nBits%8); j++ )
432 {
433 cTopByteMask |= (1<<j);
434 }
435 }
436
437 fixup();
438
439 return true;
440}*/
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