[Avida-SVN] r3302 - development/source/tools
blwalker at myxo.css.msu.edu
blwalker at myxo.css.msu.edu
Tue Jun 9 12:30:35 PDT 2009
Author: blwalker
Date: 2009-06-09 15:30:35 -0400 (Tue, 09 Jun 2009)
New Revision: 3302
Modified:
development/source/tools/cBitArray.cc
development/source/tools/cBitArray.h
Log:
Adds left shift and right shift to cBitArray, including <<, >>, <<=, and >>=. Changes cRawBitArray to use unsigned ints for fields rather than ints, preventing right shift from shifting in the sign bit.
Left shift includes masking to zero out bits that have "shifted out" of the bit array's specified size but not out of the actual backing bit field, allowing CountBits and CountBits2 to count correctly.
Unit tests have been added to cBitArray.cc's main() function. main() function remains #ifdef'd out; to compile tests you must #define UNITTEST_CBITARRAY.
Modified: development/source/tools/cBitArray.cc
===================================================================
--- development/source/tools/cBitArray.cc 2009-06-09 17:31:45 UTC (rev 3301)
+++ development/source/tools/cBitArray.cc 2009-06-09 19:30:35 UTC (rev 3302)
@@ -6,7 +6,7 @@
if (bit_fields != NULL) {
delete [] bit_fields;
}
- bit_fields = new int[num_fields];
+ bit_fields = new unsigned int[num_fields];
for (int i = 0; i < num_fields; i++) {
bit_fields[i] = in_array.bit_fields[i];
}
@@ -29,9 +29,9 @@
const int num_new_fields = GetNumFields(new_bits);
if (num_old_fields == num_new_fields) {
// Clear all bits past the new end and stop.
- int & last_field = bit_fields[num_new_fields - 1];
+ unsigned int & last_field = bit_fields[num_new_fields - 1];
for (int i = new_bits; i < old_bits; i++) {
- const int clear_bit = i & 31;
+ const unsigned int clear_bit = i & 31;
last_field &= ~(1 << clear_bit);
}
return;
@@ -39,7 +39,7 @@
// If we made it this far, we have to change the number of fields.
// Create the new bit array and copy the old one into it.
- int * new_bit_fields = new int[ num_new_fields ];
+ unsigned int * new_bit_fields = new unsigned int[ num_new_fields ];
for (int i = 0; i < num_new_fields && i < num_old_fields; i++) {
new_bit_fields[i] = bit_fields[i];
}
@@ -47,7 +47,7 @@
// If the old bits are longer, we need to clear the end of the last
// bit field.
if (num_old_fields > num_new_fields) {
- int & last_field = new_bit_fields[num_new_fields - 1];
+ unsigned int & last_field = new_bit_fields[num_new_fields - 1];
for (int clear_bit=GetFieldPos(new_bits); clear_bit < 32; clear_bit++) {
last_field &= ~(1 << clear_bit);
}
@@ -72,7 +72,7 @@
if (bit_fields != NULL) {
delete [] bit_fields;
}
- bit_fields = new int[ new_fields ];
+ bit_fields = new unsigned int[ new_fields ];
}
void cRawBitArray::ResizeClear(const int new_bits)
@@ -137,7 +137,66 @@
return out_array;
}
+void cRawBitArray::ShiftLeft(const int num_bits, const int shift_size)
+{
+ assert(shift_size > 0);
+ int num_fields = GetNumFields(num_bits);
+ int field_shift = shift_size / 32;
+ int bit_shift = shift_size % 32;
+
+ // acount for field_shift
+ if(field_shift) {
+ for (int i = num_fields - 1; i >= field_shift; i--) {
+ bit_fields[i] = bit_fields[i - field_shift];
+ }
+ for (int i = field_shift - 1; i >= 0; i--) {
+ bit_fields[i] = 0;
+ }
+ }
+
+ // account for bit_shift
+ int temp = 0;
+ for (int i = 0; i < num_fields; i++) {
+ temp = bit_fields[i] >> (32 - bit_shift);
+ bit_fields[i] <<= bit_shift;
+ bit_fields[i - 1] |= temp; // same as += in this case since lower bit_shift bits of bit_fields[i - 1] are all 0 at this point -- any advantage?
+ //could also check for temp != 0 here before assignment -- would that save any time for sparse arrays, or is it always going to be useless?
+ }
+
+ // mask out any bits that have left-shifted away, allowing CountBits and CountBits2 to work
+ // blw: if CountBits/CountBits2 are fixed, this code should be removed as it will be redundant
+ unsigned int shift_mask = 0xffffffff >> 32 - (num_bits % 32);
+ bit_fields[num_fields - 1] &= shift_mask;
+}
+// ALWAYS shifts in zeroes, irrespective of sign bit (since fields are unsigned)
+void cRawBitArray::ShiftRight(const int num_bits, const int shift_size)
+{
+ assert(shift_size > 0);
+ int num_fields = GetNumFields(num_bits);
+ int field_shift = shift_size / 32;
+ int bit_shift = shift_size % 32;
+
+ // account for field_shift
+ if (field_shift) {
+ for (int i = 0; i < num_fields - field_shift; i++) {
+ bit_fields[i] = bit_fields[i + field_shift];
+ }
+ for(int i = num_fields - field_shift; i < num_fields; i++) {
+ bit_fields[i] = 0;
+ }
+ }
+
+ // account for bit_shift
+ bit_fields[num_fields - 1] >>= bit_shift; // drops off right end, may shift in ones if sign bit was set
+ int temp = 0;
+ for (int i = num_fields - 2; i >= 0; i--) {
+ temp = bit_fields[i] << (32 - bit_shift);
+ bit_fields[i] >>= bit_shift;
+ bit_fields[i + 1] |= temp;
+ }
+}
+
void cRawBitArray::NOT(const int num_bits)
{
const int num_fields = GetNumFields(num_bits);
@@ -215,10 +274,18 @@
}
}
+void cRawBitArray::SHIFT(const int num_bits, const int shift_size)
+{
+ if (shift_size == 0) return;
+ if (shift_size > 0) { ShiftLeft(num_bits, shift_size); return; }
+ if (shift_size < 0) { ShiftRight(num_bits, -shift_size); return; }
+ assert(false); // Should never get here.
+}
+
void cRawBitArray::NOT(const cRawBitArray & array1, const int num_bits)
{
ResizeSloppy(num_bits);
@@ -315,7 +382,17 @@
}
}
+void cRawBitArray::SHIFT(const cRawBitArray & array1, const int num_bits, const int shift_size)
+{
+ if (shift_size == 0) return;
+
+ Copy(array1, num_bits);
+
+ SHIFT(num_bits, shift_size);
+}
+
+
std::ostream & operator << (std::ostream & out, const cBitArray & bit_array)
{
bit_array.Print(out);
@@ -499,7 +576,81 @@
passed = false;
cerr << "ERROR in EQU operation!" << endl;
}
+
+ // LEFT AND RIGHT SHIFT
+
+ cRawBitArray bit_array7(32);
+ bit_array7.SetBit(0, true);
+
+ bit_array7.SHIFT(32, 0);
+ if (bit_array7.GetBit(0) != true || bit_array7.CountBits(32) != 1) {
+ passed = false;
+ cerr << "ERROR when Shifting by zero bits!" << endl;
+ }
+
+ bit_array7.SHIFT(32, 31);
+ if (bit_array7.GetBit(31) != true || bit_array7.CountBits(32) != 1) {
+ passed = false;
+ cerr << "ERROR in ShiftLeft!" << endl;
+ }
+
+ bit_array7.SHIFT(32, -31);
+ if (bit_array7.GetBit(0) != true || bit_array7.CountBits(32) != 1) {
+ passed = false;
+ cerr << "ERROR in ShiftRight with sign bit!" << endl;
+ }
+
+ bit_array7.SHIFT(32, 30);
+ bit_array7.SHIFT(32, -30);
+ if (bit_array7.GetBit(0) != true || bit_array7.CountBits(32) != 1) {
+ passed = false;
+ cerr << "ERROR in ShiftRight without sign bit!" << endl;
+ }
+ bit_array7.SHIFT(32, 32);
+ if (bit_array7.CountBits(32) != 0) {
+ passed = false;
+ cerr << "ERROR in ShiftLeft dropping!" << endl;
+ }
+
+ bit_array7.SetBit(31, true);
+ bit_array7.SHIFT(32, -32);
+ if(bit_array7.CountBits(32) != 0) {
+ passed = false;
+ cerr << "ERROR in ShiftRight dropping!" << endl;
+ }
+
+ cRawBitArray bit_array8(34);
+ bit_array8.SetBit(0, true);
+
+ bit_array8.SHIFT(34, 33);
+ if (bit_array8.GetBit(33) != true || bit_array8.CountBits(34) != 1) {
+ passed = false;
+ cerr << "ERROR in ShiftLeft across bit fields!" << endl;
+ }
+
+ bit_array8.SHIFT(34, -33);
+ if (bit_array8.GetBit(0) != true || bit_array8.CountBits(34) != 1) {
+ passed = false;
+ cerr << "ERROR in ShiftRight accross bit fields!" << endl;
+ }
+
+ cRawBitArray bit_array9(66);
+ bit_array9.SetBit(0, true);
+ bit_array9.SetBit(32, true);
+
+ bit_array9.SHIFT(66, 65);
+ if(bit_array9.GetBit(65) != true || bit_array9.CountBits(66) != 1) {
+ passed = false;
+ cerr << "ERROR in ShiftLeft across multiple fields!" << endl;
+ }
+
+ bit_array9.SHIFT(66, -65);
+ if(bit_array9.GetBit(0) != true || bit_array9.CountBits(66) != 1) {
+ passed = false;
+ cerr << "ERROR in ShiftRight across multiple fields!" << endl;
+ }
+
// bit_array4.Print(70);
// bit_array5.Print(70);
// bit_array6.Print(70);
@@ -532,6 +683,16 @@
passed = false;
cerr << "ERROR: operator~ failed for cBitArray" << endl;
}
+
+ if ((ba << 65).CountBits() != 2) {
+ passed = false;
+ cerr << "ERROR: operator<< (leftshift) failed for cBitArray" << endl;
+ }
+
+ if ((ba >> 65).CountBits() != 2) {
+ passed = false;
+ cerr << "ERROR: operator>> (rightshift) failed for cBitArray" << endl;
+ }
if ((~ba & ~ba2).CountBits() != 31) {
passed = false;
Modified: development/source/tools/cBitArray.h
===================================================================
--- development/source/tools/cBitArray.h 2009-06-09 17:31:45 UTC (rev 3301)
+++ development/source/tools/cBitArray.h 2009-06-09 19:30:35 UTC (rev 3302)
@@ -53,6 +53,7 @@
// cBitArray NOR(const cBitArray & array2) const
// cBitArray XOR(const cBitArray & array2) const
// cBitArray EQU(const cBitArray & array2) const
+// cBitArray SHIFT(const int shift_size) const -- positive for left shift, negative for right shift
// const cBitArray & NOTSELF()
// const cBitArray & ANDSELF(const cBitArray & array2)
@@ -61,15 +62,20 @@
// const cBitArray & NORSELF(const cBitArray & array2)
// const cBitArray & XORSELF(const cBitArray & array2)
// const cBitArray & EQUSELF(const cBitArray & array2)
+// const cBitArray & SHIFTSELF(const int shift_size) const
// Operator overloads:
// cBitArray operator~() const
// cBitArray operator&(const cBitArray & ar2) const
// cBitArray operator|(const cBitArray & ar2) const
// cBitArray operator^(const cBitArray & ar2) const
+// cBitArray operator>>(const int) const
+// cBitArray operator<<(const int) const
// const cBitArray & operator&=(const cBitArray & ar2)
// const cBitArray & operator|=(const cBitArray & ar2)
// const cBitArray & operator^=(const cBitArray & ar2)
+// const cBitArray & operator>>=(const int)
+// const cBitArray & operator<<=(const int)
@@ -80,7 +86,7 @@
class cRawBitArray {
private:
- int * bit_fields;
+ unsigned int * bit_fields;
// Disallow default copy constructor and operator=
// (we need to know the number of bits we're working with!)
@@ -120,7 +126,7 @@
cRawBitArray(const int num_bits) {
const int num_fields = GetNumFields(num_bits);
- bit_fields = new int[ num_fields ];
+ bit_fields = new unsigned int[ num_fields ];
Zero(num_bits);
}
@@ -168,12 +174,21 @@
// Other bit-play
int FindBit1(const int num_bits, const int start_pos) const;
tArray<int> GetOnes(const int num_bits) const;
+ void ShiftLeft(const int num_bits, const int shift_size); // Helper: call SHIFT with positive number instead
+ void ShiftRight(const int num_bits, const int shift_size); // Helper: call SHIFT with negative number instead
void Print(const int num_bits, ostream & out=cout) const {
for (int i = 0; i < num_bits; i++) {
out << GetBit(i);
}
}
+
+ // prints in the accepted human readable low-to-hight = right-to-left format, taking bit 0 as low bit
+ void PrintRightToLeft(const int num_bits, ostream & out=cout) const {
+ for (int i = num_bits - 1; i >= 0; i--) {
+ out << GetBit(i);
+ }
+ }
void PrintOneIDs(const int num_bits, ostream & out=cout) const {
for (int i = 0; i < num_bits; i++) {
@@ -192,6 +207,7 @@
void NOR(const cRawBitArray & array2, const int num_bits);
void XOR(const cRawBitArray & array2, const int num_bits);
void EQU(const cRawBitArray & array2, const int num_bits);
+ void SHIFT(const int num_bits, const int shift_size); // positive numbers for left and negative for right (0 does nothing)
// Fast bool operators where we load all of the inputs and store the
// results here.
@@ -208,6 +224,7 @@
const int num_bits);
void EQU(const cRawBitArray & array1, const cRawBitArray & array2,
const int num_bits);
+ void SHIFT(const cRawBitArray & array1, const int num_bits, const int shift_size);
};
class cBitArray {
@@ -268,6 +285,7 @@
void Print(ostream & out=cout) const { bit_array.Print(array_size, out); }
+ void PrintRightToLeft(ostream & out=cout) const { bit_array.PrintRightToLeft(array_size, out); }
void PrintOneIDs(ostream & out=cout) const
{ bit_array.PrintOneIDs(array_size, out); }
void Resize(const int new_size) {
@@ -340,6 +358,13 @@
out_array.array_size = array_size;
return out_array;
}
+
+ cBitArray SHIFT(const int shift_size) const {
+ cBitArray out_array;
+ out_array.bit_array.SHIFT(bit_array, array_size, shift_size);
+ out_array.array_size = array_size;
+ return out_array;
+ }
const cBitArray & NOTSELF() {
bit_array.NOT(array_size);
@@ -381,15 +406,25 @@
bit_array.EQU(array2.bit_array, array_size);
return *this;
}
+
+ const cBitArray & SHIFTSELF(const int shift_size) {
+ bit_array.SHIFT(array_size, shift_size);
+ return *this;
+ }
+
// Operator overloads...
cBitArray operator~() const { return NOT(); }
cBitArray operator&(const cBitArray & ar2) const { return AND(ar2); }
cBitArray operator|(const cBitArray & ar2) const { return OR(ar2); }
cBitArray operator^(const cBitArray & ar2) const { return XOR(ar2); }
+ cBitArray operator<<(const int shift_size) const { return SHIFT(shift_size); }
+ cBitArray operator>>(const int shift_size) const { return SHIFT(-shift_size); }
const cBitArray & operator&=(const cBitArray & ar2) { return ANDSELF(ar2); }
const cBitArray & operator|=(const cBitArray & ar2) { return ORSELF(ar2); }
const cBitArray & operator^=(const cBitArray & ar2) { return XORSELF(ar2); }
+ const cBitArray & operator<<=(const int shift_size) { return SHIFTSELF(shift_size); }
+ const cBitArray & operator>>=(const int shift_size) { return SHIFTSELF(-shift_size); }
};
More information about the Avida-cvs
mailing list