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