Frame diff algo now working nicely and providing twice the frame rate.
1 /***************************************************************************
2 * Arrays of Arbitrary Bit Length
5 * Purpose : Provides object with methods for creation and manipulation of
6 * arbitrary length arrays of bits.
8 * Bit arrays are implemented as vectors of unsigned chars. Bit
9 * 0 is the MSB of char 0, and the last bit is the least
10 * significant (non-spare) bit of the last unsigned char.
12 * Example: array of 20 bits (0 through 19) with 8 bit unsigned
13 * chars requires 3 unsigned chars (0 through 2) to
17 * +--------+--------+--------+
19 * +--------+--------+--------+
20 * bit 01234567 8911111111111XXXX
23 * Author : Michael Dipperstein
24 * Date : July 23, 2004
26 ****************************************************************************
29 * $Id: bitarray.cpp,v 1.7 2010/02/04 03:31:43 michael Exp $
30 * $Log: bitarray.cpp,v $
31 * Revision 1.7 2010/02/04 03:31:43 michael
32 * Replaced vector<unsigned char> with an array of unsigned char.
34 * Made updates for GCC 4.4.
36 * Revision 1.5 2007/08/06 05:23:29 michael
37 * Updated for LGPL Version 3.
39 * All methods that don't modify object have been made
40 * const to increase functionality of const bit_array_c.
42 * All assignment operators return a reference to the object being assigned a value so that operator chaining will work.
44 * Added >> and << operators.
46 * Revision 1.3 2006/04/30 23:34:07 michael
47 * Improved performance by incorporating Benjamin Schindler's
48 * <bschindler@student.ethz.ch> changes to pass arguments as a reference.
50 * Revision 1.2 2004/08/05 22:16:49 michael
51 * Add overloads for bitwise operators returning values.
52 * Add a more natural looking way to set bit values.
54 * Revision 1.1.1.1 2004/08/04 13:28:20 michael
57 ****************************************************************************
59 * Bitarray: An ANSI C++ class for manipulating arbitrary length bit arrays
60 * Copyright (C) 2004, 2006-2007, 2010 by
61 * Michael Dipperstein (mdipper@alumni.engr.ucsb.edu)
63 * This file is part of the bit array library.
65 * The bit array library is free software; you can redistribute it and/or
66 * modify it under the terms of the GNU Lesser General Public License as
67 * published by the Free Software Foundation; either version 3 of the
68 * License, or (at your option) any later version.
70 * The bit array library is distributed in the hope that it will be useful,
71 * but WITHOUT ANY WARRANTY; without even the implied warranty of
72 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
73 * General Public License for more details.
75 * You should have received a copy of the GNU Lesser General Public License
76 * along with this program. If not, see <http://www.gnu.org/licenses/>.
78 ***************************************************************************/
80 /***************************************************************************
82 ***************************************************************************/
89 /***************************************************************************
91 ***************************************************************************/
93 /* make CHAR_BIT 8 if it's not defined in limits.h */
95 #warning CHAR_BIT not defined. Assuming 8 bits.
99 /* position of bit within character */
100 #define BIT_CHAR(bit) ((bit) / CHAR_BIT)
102 /* array index for character containing bit */
103 //SL: We had to change that macro since bits in our frame buffer are the other way around
104 //TODO: Find a solution to tackle that problem
105 //#define BIT_IN_CHAR(bit) (1 << (CHAR_BIT - 1 - ((bit) % CHAR_BIT)))
106 #define BIT_IN_CHAR(bit) (1 << (((bit) % CHAR_BIT)))
108 /* number of characters required to contain number of bits */
109 #define BITS_TO_CHARS(bits) ((((bits) - 1) / CHAR_BIT) + 1)
111 /* most significant bit in a character */
112 #define MS_BIT (1 << (CHAR_BIT - 1))
114 /***************************************************************************
116 ***************************************************************************/
118 /***************************************************************************
119 * Method : bit_array_c - constructor
120 * Description: This is the bit_array_c constructor. It reserves memory
121 * for the vector storing the array.
122 * Parameters : numBits - number of bits in the array
123 * Effects : Allocates vectory for array bits
125 ***************************************************************************/
126 BitArray::BitArray(const int numBits):
131 m_SizeInBytes = BITS_TO_CHARS(numBits);
134 /* allocate space for bit array */
135 m_Array = new unsigned char[m_SizeInBytes];
137 /* set all bits to 0 */
138 fill_n(m_Array, m_SizeInBytes, 0);
141 /***************************************************************************
142 * Method : bit_array_c - constructor
143 * Description: This is the bit_array_c constructor. It copies the
144 * for contents of a vector of unsigned char into the
146 * Parameters : vect - vector to be copied
147 * numBits - number of bits in the array
148 * Effects : Allocates vectory for array bits
150 ***************************************************************************/
151 BitArray::BitArray(unsigned char *array, const int numBits,bool aOwnsBuffer):
154 m_OwnsBuffer(aOwnsBuffer)
159 /***************************************************************************
160 * Method : ~bit_array_c - destructor
161 * Description: This is the bit_array_c destructor. At this point it's
162 * just a place holder.
166 ***************************************************************************/
167 BitArray::~BitArray(void)
176 /***************************************************************************
178 * Description: This method dumps the conents of a bit array to stdout.
179 * The format of the dump is a series of bytes represented in
181 * Parameters : outStream - stream to write to
182 * Effects : Array contents are dumped to stdout
184 ***************************************************************************/
185 void BitArray::Dump(std::ostream &outStream)
189 size = BITS_TO_CHARS(m_NumBits);
193 outStream << uppercase << hex << (int)(m_Array[0]); /* first byte */
195 for (int i = 1; i < size; i++)
197 /* remaining bytes with a leading space */
201 outStream << (int)(m_Array[i]);
207 /***************************************************************************
209 * Description: This method sets every bit in the bit array to 1. This
210 * method uses UCHAR_MAX to determine what it means to set
211 * all bits in an unsigned char, so it is crucial that the
212 * machine implementation of unsigned char utilizes all of
213 * the bits in the memory allocated for an unsigned char.
215 * Effects : Each of the bits used in the bit array are set to 1.
216 * Unused (spare) bits are set to 0.
218 ***************************************************************************/
219 void BitArray::SetAll(void)
224 size = BITS_TO_CHARS(m_NumBits);
226 /* set bits in all bytes to 1 */
227 fill_n(m_Array, size, UCHAR_MAX);
229 /* zero any spare bits so increment and decrement are consistent */
230 bits = m_NumBits % CHAR_BIT;
233 mask = UCHAR_MAX << (CHAR_BIT - bits);
234 m_Array[BIT_CHAR(m_NumBits - 1)] = mask;
238 /***************************************************************************
240 * Description: This method sets every bit in the bit array to 0.
242 * Effects : Each of the bits in the bit array are set to 0.
244 ***************************************************************************/
245 void BitArray::ClearAll(void)
249 size = BITS_TO_CHARS(m_NumBits);
251 /* set bits in all bytes to 0 */
252 fill_n(m_Array, size, 0);
255 /***************************************************************************
257 * Description: This method sets a bit in the bit array to 1.
258 * Parameters : bit - the number of the bit to set
259 * Effects : The specified bit will be set to 1.
261 ***************************************************************************/
262 void BitArray::SetBit(const unsigned int bit)
264 if (m_NumBits <= bit)
266 return; /* bit out of range */
269 m_Array[BIT_CHAR(bit)] |= BIT_IN_CHAR(bit);
274 void BitArray::SetBitValue(const unsigned int bit, bool aValue)
286 /***************************************************************************
288 * Description: This method sets a bit in the bit array to 0.
289 * Parameters : bit - the number of the bit to clear
290 * Effects : The specified bit will be set to 0.
292 ***************************************************************************/
293 void BitArray::ClearBit(const unsigned int bit)
297 if (m_NumBits <= bit)
299 return; /* bit out of range */
302 /* create a mask to zero out desired bit */
303 mask = BIT_IN_CHAR(bit);
306 m_Array[BIT_CHAR(bit)] &= mask;
309 /***************************************************************************
310 * Method : operator()
311 * Description: Overload of the () operator. This method approximates
312 * array indices used for assignment. It returns a
313 * bit_array_index_c which includes an = method used to
315 * Parameters : bit - index of array bit
317 * Returned : bit_array_index_c (pointer to bit)
318 ***************************************************************************/
319 BitArrayIndex BitArray::operator()(const unsigned int bit)
321 BitArrayIndex result(this, bit);
326 /***************************************************************************
327 * Method : operator[]
328 * Description: Overload of the [] operator. This method returns the
329 * value of a bit in the bit array.
330 * Parameters : bit - index of array bit
332 * Returned : The value of the specified bit.
333 ***************************************************************************/
334 bool BitArray::operator[](const unsigned int bit) const
336 return((m_Array[BIT_CHAR(bit)] & BIT_IN_CHAR(bit)) != 0);
339 /***************************************************************************
340 * Method : operator==
341 * Description: overload of the == operator
342 * Parameters : other - bit array to compare
344 * Returned : True if this == other. Otherwise false.
345 ***************************************************************************/
346 bool BitArray::operator==(const BitArray &other) const
348 if (m_NumBits != other.m_NumBits)
354 return (this->m_Array == other.m_Array);
357 /***************************************************************************
358 * Method : operator!=
359 * Description: overload of the != operator
360 * Parameters : other - bit array to compare
362 * Returned : True if this != other. Otherwise false.
363 ***************************************************************************/
364 bool BitArray::operator!=(const BitArray &other) const
366 if (m_NumBits != other.m_NumBits)
372 return (this->m_Array != other.m_Array);
375 /***************************************************************************
377 * Description: overload of the < operator
378 * Parameters : other - bit array to compare
380 * Returned : True if this < other. Otherwise false.
381 ***************************************************************************/
382 bool BitArray::operator<(const BitArray &other) const
384 if (m_NumBits != other.m_NumBits)
390 return (this->m_Array < other.m_Array);
393 /***************************************************************************
394 * Method : operator<=
395 * Description: overload of the <= operator
396 * Parameters : other - bit array to compare
398 * Returned : True if this <= other. Otherwise false.
399 ***************************************************************************/
400 bool BitArray::operator<=(const BitArray &other) const
402 if (m_NumBits != other.m_NumBits)
408 return (this->m_Array <= other.m_Array);
411 /***************************************************************************
413 * Description: overload of the > operator
414 * Parameters : other - bit array to compare
416 * Returned : True if this > other. Otherwise false.
417 ***************************************************************************/
418 bool BitArray::operator>(const BitArray &other) const
420 if (m_NumBits != other.m_NumBits)
426 return (this->m_Array > other.m_Array);
429 /***************************************************************************
430 * Method : operator>=
431 * Description: overload of the >= operator
432 * Parameters : other - bit array to compare
434 * Returned : True if this >= other. Otherwise false.
435 ***************************************************************************/
436 bool BitArray::operator>=(const BitArray &other) const
438 if (m_NumBits != other.m_NumBits)
444 return (this->m_Array >= other.m_Array);
447 /***************************************************************************
449 * Description: overload of the ~ operator. Negates all non-spare bits in
453 * Returned : value of this after bitwise not
454 ***************************************************************************/
455 BitArray BitArray::operator~(void) const
457 BitArray result(this->m_NumBits);
464 /***************************************************************************
466 * Description: overload of the & operator. Performs a bitwise and
467 * between the source array and this bit array.
468 * Parameters : other - bit array on righthand side of &
470 * Returned : value of bitwise and of this and other.
471 ***************************************************************************/
472 BitArray BitArray::operator&(const BitArray &other) const
474 BitArray result(this->m_NumBits);
482 /***************************************************************************
484 * Description: overload of the ^ operator. Performs a bitwise xor
485 * between the source array and this bit array.
486 * Parameters : other - bit array on righthand side of ^
488 * Returned : value of bitwise xor of this and other.
489 ***************************************************************************/
490 BitArray BitArray::operator^(const BitArray &other) const
492 BitArray result(this->m_NumBits);
499 /***************************************************************************
501 * Description: overload of the | operator. Performs a bitwise or
502 * between the source array and this bit array.
503 * Parameters : other - bit array on righthand side of |
505 * Returned : value of bitwise or of this and other.
506 ***************************************************************************/
507 BitArray BitArray::operator|(const BitArray &other) const
509 BitArray result(this->m_NumBits);
516 /***************************************************************************
517 * Method : operator<<
518 * Description: overload of the << operator. Performs a bitwise left
519 * shift of this bit array.
520 * Parameters : count - the number of bits to shift left
522 * Returned : result of bitwise left shift
523 ***************************************************************************/
524 BitArray BitArray::operator<<(const unsigned int count) const
526 BitArray result(this->m_NumBits);
533 /***************************************************************************
534 * Method : operator>>
535 * Description: overload of the >> operator. Performs a bitwise right
536 * shift of this bit array.
537 * Parameters : count - the number of bits to shift right
539 * Returned : result of bitwise right shift
540 ***************************************************************************/
541 BitArray BitArray::operator>>(const unsigned int count) const
543 BitArray result(this->m_NumBits);
550 /***************************************************************************
551 * Method : operator++ (prefix)
552 * Description: overload of the ++ operator. Increments the contents of
553 * a bit array. Overflows cause rollover.
555 * Effects : Bit array contents are incremented
556 * Returned : Reference to this array after increment
557 ***************************************************************************/
558 BitArray& BitArray::operator++(void)
561 unsigned char maxValue; /* maximum value for current char */
562 unsigned char one; /* least significant bit in current char */
566 return *this; /* nothing to increment */
569 /* handle arrays that don't use every bit in the last character */
570 i = (m_NumBits % CHAR_BIT);
573 maxValue = UCHAR_MAX << (CHAR_BIT - i);
574 one = 1 << (CHAR_BIT - i);
578 maxValue = UCHAR_MAX;
582 for (i = BIT_CHAR(m_NumBits - 1); i >= 0; i--)
584 if (m_Array[i] != maxValue)
586 m_Array[i] = m_Array[i] + one;
591 /* need to carry to next byte */
594 /* remaining characters must use all bits */
595 maxValue = UCHAR_MAX;
603 /***************************************************************************
604 * Method : operator++ (postfix)
605 * Description: overload of the ++ operator. Increments the contents of
606 * a bit array. Overflows cause rollover.
607 * Parameters : dumy - needed for postfix increment
608 * Effects : Bit array contents are incremented
609 * Returned : Reference to this array after increment
610 ***************************************************************************/
611 BitArray& BitArray::operator++(int dummy)
617 /***************************************************************************
618 * Method : operator-- (prefix)
619 * Description: overload of the -- operator. Decrements the contents of
620 * a bit array. Underflows cause rollover.
622 * Effects : Bit array contents are decremented
624 ***************************************************************************/
625 BitArray& BitArray::operator--(void)
628 unsigned char maxValue; /* maximum value for current char */
629 unsigned char one; /* least significant bit in current char */
633 return *this; /* nothing to decrement */
636 /* handle arrays that don't use every bit in the last character */
637 i = (m_NumBits % CHAR_BIT);
640 maxValue = UCHAR_MAX << (CHAR_BIT - i);
641 one = 1 << (CHAR_BIT - i);
645 maxValue = UCHAR_MAX;
649 for (i = BIT_CHAR(m_NumBits - 1); i >= 0; i--)
651 if (m_Array[i] >= one)
653 m_Array[i] = m_Array[i] - one;
658 /* need to borrow from the next byte */
659 m_Array[i] = maxValue;
661 /* remaining characters must use all bits */
662 maxValue = UCHAR_MAX;
670 /***************************************************************************
671 * Method : operator-- (postfix)
672 * Description: overload of the -- operator. Decrements the contents of
673 * a bit array. Underflows cause rollover.
674 * Parameters : dumy - needed for postfix decrement
675 * Effects : Bit array contents are decremented
677 ***************************************************************************/
678 BitArray& BitArray::operator--(int dummy)
684 /***************************************************************************
686 * Description: overload of the = operator. Copies source contents into
688 * Parameters : src - Source bit array
689 * Effects : Source bit array contents are copied into this array
690 * Returned : Reference to this array after copy
691 ***************************************************************************/
692 BitArray& BitArray::operator=(const BitArray &src)
696 /* don't do anything for a self assignment */
700 if (m_NumBits != src.m_NumBits)
702 /* don't do assignment with different array sizes */
706 if ((m_NumBits == 0) || (src.m_NumBits == 0))
708 /* don't do assignment with unallocated array */
712 /* copy bits from source */
714 size = BITS_TO_CHARS(m_NumBits);
716 copy(src.m_Array, &src.m_Array[size], this->m_Array);
720 /***************************************************************************
721 * Method : operator&=
722 * Description: overload of the &= operator. Performs a bitwise and
723 * between the source array and this bit array. This bit
724 * array will contain the result.
725 * Parameters : src - Source bit array
726 * Effects : Results of bitwise and are stored in this array
727 * Returned : Reference to this array after and
728 ***************************************************************************/
729 BitArray& BitArray::operator&=(const BitArray &src)
733 size = BITS_TO_CHARS(m_NumBits);
735 if (m_NumBits != src.m_NumBits)
737 /* don't do assignment with different array sizes */
741 /* AND array one unsigned char at a time */
742 for(int i = 0; i < size; i++)
744 m_Array[i] = m_Array[i] & src.m_Array[i];
750 /***************************************************************************
751 * Method : operator^=
752 * Description: overload of the ^= operator. Performs a bitwise xor
753 * between the source array and this bit array. This bit
754 * array will contain the result.
755 * Parameters : src - Source bit array
756 * Effects : Results of bitwise xor are stored in this array
757 * Returned : Reference to this array after xor
758 ***************************************************************************/
759 BitArray& BitArray::operator^=(const BitArray &src)
763 size = BITS_TO_CHARS(m_NumBits);
765 if (m_NumBits != src.m_NumBits)
767 /* don't do assignment with different array sizes */
771 /* XOR array one unsigned char at a time */
772 for(int i = 0; i < size; i++)
774 m_Array[i] = m_Array[i] ^ src.m_Array[i];
780 /***************************************************************************
781 * Method : operator|=
782 * Description: overload of the |= operator. Performs a bitwise or
783 * between the source array and this bit array. This bit
784 * array will contain the result.
785 * Parameters : src - Source bit array
786 * Effects : Results of bitwise or are stored in this array
787 * Returned : Reference to this array after or
788 ***************************************************************************/
789 BitArray& BitArray::operator|=(const BitArray &src)
793 size = BITS_TO_CHARS(m_NumBits);
795 if (m_NumBits != src.m_NumBits)
797 /* don't do assignment with different array sizes */
801 /* OR array one unsigned char at a time */
802 for(int i = 0; i < size; i++)
804 m_Array[i] = m_Array[i] | src.m_Array[i];
810 /***************************************************************************
812 * Description: Negates all non-spare bits in bit array.
814 * Effects : Contents of bit array are negated. Any spare bits are
816 * Returned : Reference to this array after not
817 ***************************************************************************/
818 BitArray& BitArray::Not(void)
824 size = BITS_TO_CHARS(m_NumBits);
828 /* don't do not with unallocated array */
832 /* NOT array one unsigned char at a time */
833 for(int i = 0; i < size; i++)
835 m_Array[i] = ~m_Array[i];
838 /* zero any spare bits so increment and decrement are consistent */
839 bits = m_NumBits % CHAR_BIT;
842 mask = UCHAR_MAX << (CHAR_BIT - bits);
843 m_Array[BIT_CHAR(m_NumBits - 1)] &= mask;
849 /***************************************************************************
850 * Method : operator<<=
851 * Description: overload of the <<= operator. Performs a left shift on
852 * this bit array. This bit array will contain the result.
853 * Parameters : shifts - number of bit positions to shift
854 * Effects : Results of the shifts are stored in this array
855 * Returned : Reference to this array after shift
856 ***************************************************************************/
857 BitArray& BitArray::operator<<=(const unsigned int shifts)
860 int chars = shifts / CHAR_BIT; /* number of whole byte shifts */
862 if (shifts >= m_NumBits)
864 /* all bits have been shifted off */
869 /* first handle big jumps of bytes */
874 size = BITS_TO_CHARS(m_NumBits);
876 for (i = 0; (i + chars) < size; i++)
878 m_Array[i] = m_Array[i + chars];
881 /* now zero out new bytes on the right */
882 for (i = size; chars > 0; chars--)
884 m_Array[i - chars] = 0;
888 /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
889 for (i = 0; i < (int)(shifts % CHAR_BIT); i++)
891 for (unsigned int j = 0; j < BIT_CHAR(m_NumBits - 1); j++)
895 /* handle shifts across byte bounds */
896 if (m_Array[j + 1] & MS_BIT)
902 m_Array[BIT_CHAR(m_NumBits - 1)] <<= 1;
908 /***************************************************************************
909 * Method : operator>>=
910 * Description: overload of the >>= operator. Performs a right shift on
911 * this bit array. This bit array will contain the result.
912 * Parameters : shifts - number of bit positions to shift
913 * Effects : Results of the shifts are stored in this array
914 * Returned : Reference to this array after shift
915 ***************************************************************************/
916 BitArray& BitArray::operator>>=(const unsigned int shifts)
920 int chars = shifts / CHAR_BIT; /* number of whole byte shifts */
922 if (shifts >= m_NumBits)
924 /* all bits have been shifted off */
929 /* first handle big jumps of bytes */
932 for (i = BIT_CHAR(m_NumBits - 1); (i - chars) >= 0; i--)
934 m_Array[i] = m_Array[i - chars];
937 /* now zero out new bytes on the right */
938 for (; chars > 0; chars--)
940 m_Array[chars - 1] = 0;
944 /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
945 for (i = 0; i < (int)(shifts % CHAR_BIT); i++)
947 for (unsigned int j = BIT_CHAR(m_NumBits - 1); j > 0; j--)
951 /* handle shifts across byte bounds */
952 if (m_Array[j - 1] & 0x01)
954 m_Array[j] |= MS_BIT;
961 /***********************************************************************
962 * zero any spare bits that are shifted beyond the end of the bit array
963 * so that increment and decrement are consistent.
964 ***********************************************************************/
965 i = m_NumBits % CHAR_BIT;
968 mask = UCHAR_MAX << (CHAR_BIT - i);
969 m_Array[BIT_CHAR(m_NumBits - 1)] &= mask;
975 /***************************************************************************
976 * Method : bit_array_index_c - constructor
977 * Description: This is the bit_array_index_c constructor. It stores a
978 * pointer to the bit array and the bit index.
979 * Parameters : array - pointer to bit array
980 * index - index of bit in array
981 * Effects : Pointer to bit array and bit index are stored.
983 ***************************************************************************/
984 BitArrayIndex::BitArrayIndex(BitArray *array,
985 const unsigned int index)
991 /***************************************************************************
993 * Description: overload of the = operator. Sets the bit array bit to
995 * Parameters : src - bit value
996 * Effects : Bit pointed to by this object is set to the value of
999 ***************************************************************************/
1000 void BitArrayIndex::operator=(const bool src)
1002 if (m_BitArray == NULL)
1004 return; /* no array */
1007 if (m_BitArray->SizeInBits() <= m_Index)
1009 return; /* index is out of bounds */
1014 m_BitArray->SetBit(m_Index);
1018 m_BitArray->ClearBit(m_Index);