1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/BitArray.cpp Tue Jun 17 09:55:20 2014 +0200
1.3 @@ -0,0 +1,1020 @@
1.4 +/***************************************************************************
1.5 +* Arrays of Arbitrary Bit Length
1.6 +*
1.7 +* File : bitarray.cpp
1.8 +* Purpose : Provides object with methods for creation and manipulation of
1.9 +* arbitrary length arrays of bits.
1.10 +*
1.11 +* Bit arrays are implemented as vectors of unsigned chars. Bit
1.12 +* 0 is the MSB of char 0, and the last bit is the least
1.13 +* significant (non-spare) bit of the last unsigned char.
1.14 +*
1.15 +* Example: array of 20 bits (0 through 19) with 8 bit unsigned
1.16 +* chars requires 3 unsigned chars (0 through 2) to
1.17 +* store all the bits.
1.18 +*
1.19 +* char 0 1 2
1.20 +* +--------+--------+--------+
1.21 +* | | | |
1.22 +* +--------+--------+--------+
1.23 +* bit 01234567 8911111111111XXXX
1.24 +* 012345 6789
1.25 +*
1.26 +* Author : Michael Dipperstein
1.27 +* Date : July 23, 2004
1.28 +*
1.29 +****************************************************************************
1.30 +* HISTORY
1.31 +*
1.32 +* $Id: bitarray.cpp,v 1.7 2010/02/04 03:31:43 michael Exp $
1.33 +* $Log: bitarray.cpp,v $
1.34 +* Revision 1.7 2010/02/04 03:31:43 michael
1.35 +* Replaced vector<unsigned char> with an array of unsigned char.
1.36 +*
1.37 +* Made updates for GCC 4.4.
1.38 +*
1.39 +* Revision 1.5 2007/08/06 05:23:29 michael
1.40 +* Updated for LGPL Version 3.
1.41 +*
1.42 +* All methods that don't modify object have been made
1.43 +* const to increase functionality of const bit_array_c.
1.44 +*
1.45 +* All assignment operators return a reference to the object being assigned a value so that operator chaining will work.
1.46 +*
1.47 +* Added >> and << operators.
1.48 +*
1.49 +* Revision 1.3 2006/04/30 23:34:07 michael
1.50 +* Improved performance by incorporating Benjamin Schindler's
1.51 +* <bschindler@student.ethz.ch> changes to pass arguments as a reference.
1.52 +*
1.53 +* Revision 1.2 2004/08/05 22:16:49 michael
1.54 +* Add overloads for bitwise operators returning values.
1.55 +* Add a more natural looking way to set bit values.
1.56 +*
1.57 +* Revision 1.1.1.1 2004/08/04 13:28:20 michael
1.58 +* bit_array_c
1.59 +*
1.60 +****************************************************************************
1.61 +*
1.62 +* Bitarray: An ANSI C++ class for manipulating arbitrary length bit arrays
1.63 +* Copyright (C) 2004, 2006-2007, 2010 by
1.64 +* Michael Dipperstein (mdipper@alumni.engr.ucsb.edu)
1.65 +*
1.66 +* This file is part of the bit array library.
1.67 +*
1.68 +* The bit array library is free software; you can redistribute it and/or
1.69 +* modify it under the terms of the GNU Lesser General Public License as
1.70 +* published by the Free Software Foundation; either version 3 of the
1.71 +* License, or (at your option) any later version.
1.72 +*
1.73 +* The bit array library is distributed in the hope that it will be useful,
1.74 +* but WITHOUT ANY WARRANTY; without even the implied warranty of
1.75 +* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
1.76 +* General Public License for more details.
1.77 +*
1.78 +* You should have received a copy of the GNU Lesser General Public License
1.79 +* along with this program. If not, see <http://www.gnu.org/licenses/>.
1.80 +*
1.81 +***************************************************************************/
1.82 +
1.83 +/***************************************************************************
1.84 +* INCLUDED FILES
1.85 +***************************************************************************/
1.86 +#include <iostream>
1.87 +#include <climits>
1.88 +#include "bitarray.h"
1.89 +
1.90 +using namespace std;
1.91 +
1.92 +/***************************************************************************
1.93 +* MACROS
1.94 +***************************************************************************/
1.95 +
1.96 +/* make CHAR_BIT 8 if it's not defined in limits.h */
1.97 +#ifndef CHAR_BIT
1.98 +#warning CHAR_BIT not defined. Assuming 8 bits.
1.99 +#define CHAR_BIT 8
1.100 +#endif
1.101 +
1.102 +/* position of bit within character */
1.103 +#define BIT_CHAR(bit) ((bit) / CHAR_BIT)
1.104 +
1.105 +/* array index for character containing bit */
1.106 +//SL: We had to change that macro since bits in our frame buffer are the other way around
1.107 +//TODO: Find a solution to tackle that problem
1.108 +//#define BIT_IN_CHAR(bit) (1 << (CHAR_BIT - 1 - ((bit) % CHAR_BIT)))
1.109 +#define BIT_IN_CHAR(bit) (1 << (((bit) % CHAR_BIT)))
1.110 +
1.111 +/* number of characters required to contain number of bits */
1.112 +#define BITS_TO_CHARS(bits) ((((bits) - 1) / CHAR_BIT) + 1)
1.113 +
1.114 +/* most significant bit in a character */
1.115 +#define MS_BIT (1 << (CHAR_BIT - 1))
1.116 +
1.117 +/***************************************************************************
1.118 +* METHODS
1.119 +***************************************************************************/
1.120 +
1.121 +/***************************************************************************
1.122 +* Method : bit_array_c - constructor
1.123 +* Description: This is the bit_array_c constructor. It reserves memory
1.124 +* for the vector storing the array.
1.125 +* Parameters : numBits - number of bits in the array
1.126 +* Effects : Allocates vectory for array bits
1.127 +* Returned : None
1.128 +***************************************************************************/
1.129 +BitArray::BitArray(const int numBits):
1.130 + m_NumBits(numBits),
1.131 + m_Array(NULL),
1.132 + m_OwnsBuffer(true)
1.133 +{
1.134 + m_SizeInBytes = BITS_TO_CHARS(numBits);
1.135 +
1.136 +
1.137 + /* allocate space for bit array */
1.138 + m_Array = new unsigned char[m_SizeInBytes];
1.139 +
1.140 + /* set all bits to 0 */
1.141 + fill_n(m_Array, m_SizeInBytes, 0);
1.142 +}
1.143 +
1.144 +/***************************************************************************
1.145 +* Method : bit_array_c - constructor
1.146 +* Description: This is the bit_array_c constructor. It copies the
1.147 +* for contents of a vector of unsigned char into the
1.148 +* bitarray.
1.149 +* Parameters : vect - vector to be copied
1.150 +* numBits - number of bits in the array
1.151 +* Effects : Allocates vectory for array bits
1.152 +* Returned : None
1.153 +***************************************************************************/
1.154 +BitArray::BitArray(unsigned char *array, const int numBits,bool aOwnsBuffer):
1.155 + m_NumBits(numBits),
1.156 + m_Array(array),
1.157 + m_OwnsBuffer(aOwnsBuffer)
1.158 +{
1.159 +
1.160 +}
1.161 +
1.162 +/***************************************************************************
1.163 +* Method : ~bit_array_c - destructor
1.164 +* Description: This is the bit_array_c destructor. At this point it's
1.165 +* just a place holder.
1.166 +* Parameters : None
1.167 +* Effects : None
1.168 +* Returned : None
1.169 +***************************************************************************/
1.170 +BitArray::~BitArray(void)
1.171 +{
1.172 + if (m_OwnsBuffer)
1.173 + {
1.174 + delete[] m_Array;
1.175 + m_Array = NULL;
1.176 + }
1.177 +}
1.178 +
1.179 +/***************************************************************************
1.180 +* Method : Dump
1.181 +* Description: This method dumps the conents of a bit array to stdout.
1.182 +* The format of the dump is a series of bytes represented in
1.183 +* hexadecimal.
1.184 +* Parameters : outStream - stream to write to
1.185 +* Effects : Array contents are dumped to stdout
1.186 +* Returned : None
1.187 +***************************************************************************/
1.188 +void BitArray::Dump(std::ostream &outStream)
1.189 +{
1.190 + int size;
1.191 +
1.192 + size = BITS_TO_CHARS(m_NumBits);
1.193 +
1.194 + outStream.width(2);
1.195 + outStream.fill('0');
1.196 + outStream << uppercase << hex << (int)(m_Array[0]); /* first byte */
1.197 +
1.198 + for (int i = 1; i < size; i++)
1.199 + {
1.200 + /* remaining bytes with a leading space */
1.201 + outStream << " ";
1.202 + outStream.width(2);
1.203 + outStream.fill('0');
1.204 + outStream << (int)(m_Array[i]);
1.205 + }
1.206 +
1.207 + outStream << dec;
1.208 +}
1.209 +
1.210 +/***************************************************************************
1.211 +* Method : SetAll
1.212 +* Description: This method sets every bit in the bit array to 1. This
1.213 +* method uses UCHAR_MAX to determine what it means to set
1.214 +* all bits in an unsigned char, so it is crucial that the
1.215 +* machine implementation of unsigned char utilizes all of
1.216 +* the bits in the memory allocated for an unsigned char.
1.217 +* Parameters : None
1.218 +* Effects : Each of the bits used in the bit array are set to 1.
1.219 +* Unused (spare) bits are set to 0.
1.220 +* Returned : None
1.221 +***************************************************************************/
1.222 +void BitArray::SetAll(void)
1.223 +{
1.224 + int bits, size;
1.225 + unsigned char mask;
1.226 +
1.227 + size = BITS_TO_CHARS(m_NumBits);
1.228 +
1.229 + /* set bits in all bytes to 1 */
1.230 + fill_n(m_Array, size, UCHAR_MAX);
1.231 +
1.232 + /* zero any spare bits so increment and decrement are consistent */
1.233 + bits = m_NumBits % CHAR_BIT;
1.234 + if (bits != 0)
1.235 + {
1.236 + mask = UCHAR_MAX << (CHAR_BIT - bits);
1.237 + m_Array[BIT_CHAR(m_NumBits - 1)] = mask;
1.238 + }
1.239 +}
1.240 +
1.241 +/***************************************************************************
1.242 +* Method : ClearAll
1.243 +* Description: This method sets every bit in the bit array to 0.
1.244 +* Parameters : None
1.245 +* Effects : Each of the bits in the bit array are set to 0.
1.246 +* Returned : None
1.247 +***************************************************************************/
1.248 +void BitArray::ClearAll(void)
1.249 +{
1.250 + int size;
1.251 +
1.252 + size = BITS_TO_CHARS(m_NumBits);
1.253 +
1.254 + /* set bits in all bytes to 0 */
1.255 + fill_n(m_Array, size, 0);
1.256 +}
1.257 +
1.258 +/***************************************************************************
1.259 +* Method : SetBit
1.260 +* Description: This method sets a bit in the bit array to 1.
1.261 +* Parameters : bit - the number of the bit to set
1.262 +* Effects : The specified bit will be set to 1.
1.263 +* Returned : None
1.264 +***************************************************************************/
1.265 +void BitArray::SetBit(const unsigned int bit)
1.266 +{
1.267 + if (m_NumBits <= bit)
1.268 + {
1.269 + return; /* bit out of range */
1.270 + }
1.271 +
1.272 + m_Array[BIT_CHAR(bit)] |= BIT_IN_CHAR(bit);
1.273 +}
1.274 +
1.275 +/**
1.276 +*/
1.277 +void BitArray::SetBitValue(const unsigned int bit, bool aValue)
1.278 + {
1.279 + if (aValue)
1.280 + {
1.281 + SetBit(bit);
1.282 + }
1.283 + else
1.284 + {
1.285 + ClearBit(bit);
1.286 + }
1.287 + }
1.288 +
1.289 +/***************************************************************************
1.290 +* Method : ClearBit
1.291 +* Description: This method sets a bit in the bit array to 0.
1.292 +* Parameters : bit - the number of the bit to clear
1.293 +* Effects : The specified bit will be set to 0.
1.294 +* Returned : None
1.295 +***************************************************************************/
1.296 +void BitArray::ClearBit(const unsigned int bit)
1.297 +{
1.298 + unsigned char mask;
1.299 +
1.300 + if (m_NumBits <= bit)
1.301 + {
1.302 + return; /* bit out of range */
1.303 + }
1.304 +
1.305 + /* create a mask to zero out desired bit */
1.306 + mask = BIT_IN_CHAR(bit);
1.307 + mask = ~mask;
1.308 +
1.309 + m_Array[BIT_CHAR(bit)] &= mask;
1.310 +}
1.311 +
1.312 +/***************************************************************************
1.313 +* Method : operator()
1.314 +* Description: Overload of the () operator. This method approximates
1.315 +* array indices used for assignment. It returns a
1.316 +* bit_array_index_c which includes an = method used to
1.317 +* set bit values.
1.318 +* Parameters : bit - index of array bit
1.319 +* Effects : None
1.320 +* Returned : bit_array_index_c (pointer to bit)
1.321 +***************************************************************************/
1.322 +BitArrayIndex BitArray::operator()(const unsigned int bit)
1.323 +{
1.324 + BitArrayIndex result(this, bit);
1.325 +
1.326 + return result;
1.327 +}
1.328 +
1.329 +/***************************************************************************
1.330 +* Method : operator[]
1.331 +* Description: Overload of the [] operator. This method returns the
1.332 +* value of a bit in the bit array.
1.333 +* Parameters : bit - index of array bit
1.334 +* Effects : None
1.335 +* Returned : The value of the specified bit.
1.336 +***************************************************************************/
1.337 +bool BitArray::operator[](const unsigned int bit) const
1.338 +{
1.339 + return((m_Array[BIT_CHAR(bit)] & BIT_IN_CHAR(bit)) != 0);
1.340 +}
1.341 +
1.342 +/***************************************************************************
1.343 +* Method : operator==
1.344 +* Description: overload of the == operator
1.345 +* Parameters : other - bit array to compare
1.346 +* Effects : None
1.347 +* Returned : True if this == other. Otherwise false.
1.348 +***************************************************************************/
1.349 +bool BitArray::operator==(const BitArray &other) const
1.350 +{
1.351 + if (m_NumBits != other.m_NumBits)
1.352 + {
1.353 + /* unequal sizes */
1.354 + return false;
1.355 + }
1.356 +
1.357 + return (this->m_Array == other.m_Array);
1.358 +}
1.359 +
1.360 +/***************************************************************************
1.361 +* Method : operator!=
1.362 +* Description: overload of the != operator
1.363 +* Parameters : other - bit array to compare
1.364 +* Effects : None
1.365 +* Returned : True if this != other. Otherwise false.
1.366 +***************************************************************************/
1.367 +bool BitArray::operator!=(const BitArray &other) const
1.368 +{
1.369 + if (m_NumBits != other.m_NumBits)
1.370 + {
1.371 + /* unequal sizes */
1.372 + return true;
1.373 + }
1.374 +
1.375 + return (this->m_Array != other.m_Array);
1.376 +}
1.377 +
1.378 +/***************************************************************************
1.379 +* Method : operator<
1.380 +* Description: overload of the < operator
1.381 +* Parameters : other - bit array to compare
1.382 +* Effects : None
1.383 +* Returned : True if this < other. Otherwise false.
1.384 +***************************************************************************/
1.385 +bool BitArray::operator<(const BitArray &other) const
1.386 +{
1.387 + if (m_NumBits != other.m_NumBits)
1.388 + {
1.389 + /* unequal sizes */
1.390 + return false;
1.391 + }
1.392 +
1.393 + return (this->m_Array < other.m_Array);
1.394 +}
1.395 +
1.396 +/***************************************************************************
1.397 +* Method : operator<=
1.398 +* Description: overload of the <= operator
1.399 +* Parameters : other - bit array to compare
1.400 +* Effects : None
1.401 +* Returned : True if this <= other. Otherwise false.
1.402 +***************************************************************************/
1.403 +bool BitArray::operator<=(const BitArray &other) const
1.404 +{
1.405 + if (m_NumBits != other.m_NumBits)
1.406 + {
1.407 + /* unequal sizes */
1.408 + return false;
1.409 + }
1.410 +
1.411 + return (this->m_Array <= other.m_Array);
1.412 +}
1.413 +
1.414 +/***************************************************************************
1.415 +* Method : operator>
1.416 +* Description: overload of the > operator
1.417 +* Parameters : other - bit array to compare
1.418 +* Effects : None
1.419 +* Returned : True if this > other. Otherwise false.
1.420 +***************************************************************************/
1.421 +bool BitArray::operator>(const BitArray &other) const
1.422 +{
1.423 + if (m_NumBits != other.m_NumBits)
1.424 + {
1.425 + /* unequal sizes */
1.426 + return false;
1.427 + }
1.428 +
1.429 + return (this->m_Array > other.m_Array);
1.430 +}
1.431 +
1.432 +/***************************************************************************
1.433 +* Method : operator>=
1.434 +* Description: overload of the >= operator
1.435 +* Parameters : other - bit array to compare
1.436 +* Effects : None
1.437 +* Returned : True if this >= other. Otherwise false.
1.438 +***************************************************************************/
1.439 +bool BitArray::operator>=(const BitArray &other) const
1.440 +{
1.441 + if (m_NumBits != other.m_NumBits)
1.442 + {
1.443 + /* unequal sizes */
1.444 + return false;
1.445 + }
1.446 +
1.447 + return (this->m_Array >= other.m_Array);
1.448 +}
1.449 +
1.450 +/***************************************************************************
1.451 +* Method : operator~
1.452 +* Description: overload of the ~ operator. Negates all non-spare bits in
1.453 +* bit array
1.454 +* Parameters : None
1.455 +* Effects : None
1.456 +* Returned : value of this after bitwise not
1.457 +***************************************************************************/
1.458 +BitArray BitArray::operator~(void) const
1.459 +{
1.460 + BitArray result(this->m_NumBits);
1.461 + result = *this;
1.462 + result.Not();
1.463 +
1.464 + return result;
1.465 +}
1.466 +
1.467 +/***************************************************************************
1.468 +* Method : operator&
1.469 +* Description: overload of the & operator. Performs a bitwise and
1.470 +* between the source array and this bit array.
1.471 +* Parameters : other - bit array on righthand side of &
1.472 +* Effects : None
1.473 +* Returned : value of bitwise and of this and other.
1.474 +***************************************************************************/
1.475 +BitArray BitArray::operator&(const BitArray &other) const
1.476 +{
1.477 + BitArray result(this->m_NumBits);
1.478 + result = *this;
1.479 + result &= other;
1.480 +
1.481 + return result;
1.482 +}
1.483 +
1.484 +
1.485 +/***************************************************************************
1.486 +* Method : operator^
1.487 +* Description: overload of the ^ operator. Performs a bitwise xor
1.488 +* between the source array and this bit array.
1.489 +* Parameters : other - bit array on righthand side of ^
1.490 +* Effects : None
1.491 +* Returned : value of bitwise xor of this and other.
1.492 +***************************************************************************/
1.493 +BitArray BitArray::operator^(const BitArray &other) const
1.494 +{
1.495 + BitArray result(this->m_NumBits);
1.496 + result = *this;
1.497 + result ^= other;
1.498 +
1.499 + return result;
1.500 +}
1.501 +
1.502 +/***************************************************************************
1.503 +* Method : operator|
1.504 +* Description: overload of the | operator. Performs a bitwise or
1.505 +* between the source array and this bit array.
1.506 +* Parameters : other - bit array on righthand side of |
1.507 +* Effects : None
1.508 +* Returned : value of bitwise or of this and other.
1.509 +***************************************************************************/
1.510 +BitArray BitArray::operator|(const BitArray &other) const
1.511 +{
1.512 + BitArray result(this->m_NumBits);
1.513 + result = *this;
1.514 + result |= other;
1.515 +
1.516 + return result;
1.517 +}
1.518 +
1.519 +/***************************************************************************
1.520 +* Method : operator<<
1.521 +* Description: overload of the << operator. Performs a bitwise left
1.522 +* shift of this bit array.
1.523 +* Parameters : count - the number of bits to shift left
1.524 +* Effects : None
1.525 +* Returned : result of bitwise left shift
1.526 +***************************************************************************/
1.527 +BitArray BitArray::operator<<(const unsigned int count) const
1.528 +{
1.529 + BitArray result(this->m_NumBits);
1.530 + result = *this;
1.531 + result <<= count;
1.532 +
1.533 + return result;
1.534 +}
1.535 +
1.536 +/***************************************************************************
1.537 +* Method : operator>>
1.538 +* Description: overload of the >> operator. Performs a bitwise right
1.539 +* shift of this bit array.
1.540 +* Parameters : count - the number of bits to shift right
1.541 +* Effects : None
1.542 +* Returned : result of bitwise right shift
1.543 +***************************************************************************/
1.544 +BitArray BitArray::operator>>(const unsigned int count) const
1.545 +{
1.546 + BitArray result(this->m_NumBits);
1.547 + result = *this;
1.548 + result >>= count;
1.549 +
1.550 + return result;
1.551 +}
1.552 +
1.553 +/***************************************************************************
1.554 +* Method : operator++ (prefix)
1.555 +* Description: overload of the ++ operator. Increments the contents of
1.556 +* a bit array. Overflows cause rollover.
1.557 +* Parameters : None
1.558 +* Effects : Bit array contents are incremented
1.559 +* Returned : Reference to this array after increment
1.560 +***************************************************************************/
1.561 +BitArray& BitArray::operator++(void)
1.562 +{
1.563 + int i;
1.564 + unsigned char maxValue; /* maximum value for current char */
1.565 + unsigned char one; /* least significant bit in current char */
1.566 +
1.567 + if (m_NumBits == 0)
1.568 + {
1.569 + return *this; /* nothing to increment */
1.570 + }
1.571 +
1.572 + /* handle arrays that don't use every bit in the last character */
1.573 + i = (m_NumBits % CHAR_BIT);
1.574 + if (i != 0)
1.575 + {
1.576 + maxValue = UCHAR_MAX << (CHAR_BIT - i);
1.577 + one = 1 << (CHAR_BIT - i);
1.578 + }
1.579 + else
1.580 + {
1.581 + maxValue = UCHAR_MAX;
1.582 + one = 1;
1.583 + }
1.584 +
1.585 + for (i = BIT_CHAR(m_NumBits - 1); i >= 0; i--)
1.586 + {
1.587 + if (m_Array[i] != maxValue)
1.588 + {
1.589 + m_Array[i] = m_Array[i] + one;
1.590 + return *this;
1.591 + }
1.592 + else
1.593 + {
1.594 + /* need to carry to next byte */
1.595 + m_Array[i] = 0;
1.596 +
1.597 + /* remaining characters must use all bits */
1.598 + maxValue = UCHAR_MAX;
1.599 + one = 1;
1.600 + }
1.601 + }
1.602 +
1.603 + return *this;
1.604 +}
1.605 +
1.606 +/***************************************************************************
1.607 +* Method : operator++ (postfix)
1.608 +* Description: overload of the ++ operator. Increments the contents of
1.609 +* a bit array. Overflows cause rollover.
1.610 +* Parameters : dumy - needed for postfix increment
1.611 +* Effects : Bit array contents are incremented
1.612 +* Returned : Reference to this array after increment
1.613 +***************************************************************************/
1.614 +BitArray& BitArray::operator++(int dummy)
1.615 +{
1.616 + ++(*this);
1.617 + return *this;
1.618 +}
1.619 +
1.620 +/***************************************************************************
1.621 +* Method : operator-- (prefix)
1.622 +* Description: overload of the -- operator. Decrements the contents of
1.623 +* a bit array. Underflows cause rollover.
1.624 +* Parameters : None
1.625 +* Effects : Bit array contents are decremented
1.626 +* Returned : None
1.627 +***************************************************************************/
1.628 +BitArray& BitArray::operator--(void)
1.629 +{
1.630 + int i;
1.631 + unsigned char maxValue; /* maximum value for current char */
1.632 + unsigned char one; /* least significant bit in current char */
1.633 +
1.634 + if (m_NumBits == 0)
1.635 + {
1.636 + return *this; /* nothing to decrement */
1.637 + }
1.638 +
1.639 + /* handle arrays that don't use every bit in the last character */
1.640 + i = (m_NumBits % CHAR_BIT);
1.641 + if (i != 0)
1.642 + {
1.643 + maxValue = UCHAR_MAX << (CHAR_BIT - i);
1.644 + one = 1 << (CHAR_BIT - i);
1.645 + }
1.646 + else
1.647 + {
1.648 + maxValue = UCHAR_MAX;
1.649 + one = 1;
1.650 + }
1.651 +
1.652 + for (i = BIT_CHAR(m_NumBits - 1); i >= 0; i--)
1.653 + {
1.654 + if (m_Array[i] >= one)
1.655 + {
1.656 + m_Array[i] = m_Array[i] - one;
1.657 + return *this;
1.658 + }
1.659 + else
1.660 + {
1.661 + /* need to borrow from the next byte */
1.662 + m_Array[i] = maxValue;
1.663 +
1.664 + /* remaining characters must use all bits */
1.665 + maxValue = UCHAR_MAX;
1.666 + one = 1;
1.667 + }
1.668 + }
1.669 +
1.670 + return *this;
1.671 +}
1.672 +
1.673 +/***************************************************************************
1.674 +* Method : operator-- (postfix)
1.675 +* Description: overload of the -- operator. Decrements the contents of
1.676 +* a bit array. Underflows cause rollover.
1.677 +* Parameters : dumy - needed for postfix decrement
1.678 +* Effects : Bit array contents are decremented
1.679 +* Returned : None
1.680 +***************************************************************************/
1.681 +BitArray& BitArray::operator--(int dummy)
1.682 +{
1.683 + --(*this);
1.684 + return *this;
1.685 +}
1.686 +
1.687 +/***************************************************************************
1.688 +* Method : operator=
1.689 +* Description: overload of the = operator. Copies source contents into
1.690 +* this bit array.
1.691 +* Parameters : src - Source bit array
1.692 +* Effects : Source bit array contents are copied into this array
1.693 +* Returned : Reference to this array after copy
1.694 +***************************************************************************/
1.695 +BitArray& BitArray::operator=(const BitArray &src)
1.696 +{
1.697 + if (*this == src)
1.698 + {
1.699 + /* don't do anything for a self assignment */
1.700 + return *this;
1.701 + }
1.702 +
1.703 + if (m_NumBits != src.m_NumBits)
1.704 + {
1.705 + /* don't do assignment with different array sizes */
1.706 + return *this;
1.707 + }
1.708 +
1.709 + if ((m_NumBits == 0) || (src.m_NumBits == 0))
1.710 + {
1.711 + /* don't do assignment with unallocated array */
1.712 + return *this;
1.713 + }
1.714 +
1.715 + /* copy bits from source */
1.716 + int size;
1.717 + size = BITS_TO_CHARS(m_NumBits);
1.718 +
1.719 + copy(src.m_Array, &src.m_Array[size], this->m_Array);
1.720 + return *this;
1.721 +}
1.722 +
1.723 +/***************************************************************************
1.724 +* Method : operator&=
1.725 +* Description: overload of the &= operator. Performs a bitwise and
1.726 +* between the source array and this bit array. This bit
1.727 +* array will contain the result.
1.728 +* Parameters : src - Source bit array
1.729 +* Effects : Results of bitwise and are stored in this array
1.730 +* Returned : Reference to this array after and
1.731 +***************************************************************************/
1.732 +BitArray& BitArray::operator&=(const BitArray &src)
1.733 +{
1.734 + int size;
1.735 +
1.736 + size = BITS_TO_CHARS(m_NumBits);
1.737 +
1.738 + if (m_NumBits != src.m_NumBits)
1.739 + {
1.740 + /* don't do assignment with different array sizes */
1.741 + return *this;
1.742 + }
1.743 +
1.744 + /* AND array one unsigned char at a time */
1.745 + for(int i = 0; i < size; i++)
1.746 + {
1.747 + m_Array[i] = m_Array[i] & src.m_Array[i];
1.748 + }
1.749 +
1.750 + return *this;
1.751 +}
1.752 +
1.753 +/***************************************************************************
1.754 +* Method : operator^=
1.755 +* Description: overload of the ^= operator. Performs a bitwise xor
1.756 +* between the source array and this bit array. This bit
1.757 +* array will contain the result.
1.758 +* Parameters : src - Source bit array
1.759 +* Effects : Results of bitwise xor are stored in this array
1.760 +* Returned : Reference to this array after xor
1.761 +***************************************************************************/
1.762 +BitArray& BitArray::operator^=(const BitArray &src)
1.763 +{
1.764 + int size;
1.765 +
1.766 + size = BITS_TO_CHARS(m_NumBits);
1.767 +
1.768 + if (m_NumBits != src.m_NumBits)
1.769 + {
1.770 + /* don't do assignment with different array sizes */
1.771 + return *this;
1.772 + }
1.773 +
1.774 + /* XOR array one unsigned char at a time */
1.775 + for(int i = 0; i < size; i++)
1.776 + {
1.777 + m_Array[i] = m_Array[i] ^ src.m_Array[i];
1.778 + }
1.779 +
1.780 + return *this;
1.781 +}
1.782 +
1.783 +/***************************************************************************
1.784 +* Method : operator|=
1.785 +* Description: overload of the |= operator. Performs a bitwise or
1.786 +* between the source array and this bit array. This bit
1.787 +* array will contain the result.
1.788 +* Parameters : src - Source bit array
1.789 +* Effects : Results of bitwise or are stored in this array
1.790 +* Returned : Reference to this array after or
1.791 +***************************************************************************/
1.792 +BitArray& BitArray::operator|=(const BitArray &src)
1.793 +{
1.794 + int size;
1.795 +
1.796 + size = BITS_TO_CHARS(m_NumBits);
1.797 +
1.798 + if (m_NumBits != src.m_NumBits)
1.799 + {
1.800 + /* don't do assignment with different array sizes */
1.801 + return *this;
1.802 + }
1.803 +
1.804 + /* OR array one unsigned char at a time */
1.805 + for(int i = 0; i < size; i++)
1.806 + {
1.807 + m_Array[i] = m_Array[i] | src.m_Array[i];
1.808 + }
1.809 +
1.810 + return *this;
1.811 +}
1.812 +
1.813 +/***************************************************************************
1.814 +* Method : Not
1.815 +* Description: Negates all non-spare bits in bit array.
1.816 +* Parameters : None
1.817 +* Effects : Contents of bit array are negated. Any spare bits are
1.818 +* left at 0.
1.819 +* Returned : Reference to this array after not
1.820 +***************************************************************************/
1.821 +BitArray& BitArray::Not(void)
1.822 +{
1.823 + int bits;
1.824 + unsigned char mask;
1.825 + int size;
1.826 +
1.827 + size = BITS_TO_CHARS(m_NumBits);
1.828 +
1.829 + if (m_NumBits == 0)
1.830 + {
1.831 + /* don't do not with unallocated array */
1.832 + return *this;
1.833 + }
1.834 +
1.835 + /* NOT array one unsigned char at a time */
1.836 + for(int i = 0; i < size; i++)
1.837 + {
1.838 + m_Array[i] = ~m_Array[i];
1.839 + }
1.840 +
1.841 + /* zero any spare bits so increment and decrement are consistent */
1.842 + bits = m_NumBits % CHAR_BIT;
1.843 + if (bits != 0)
1.844 + {
1.845 + mask = UCHAR_MAX << (CHAR_BIT - bits);
1.846 + m_Array[BIT_CHAR(m_NumBits - 1)] &= mask;
1.847 + }
1.848 +
1.849 + return *this;
1.850 +}
1.851 +
1.852 +/***************************************************************************
1.853 +* Method : operator<<=
1.854 +* Description: overload of the <<= operator. Performs a left shift on
1.855 +* this bit array. This bit array will contain the result.
1.856 +* Parameters : shifts - number of bit positions to shift
1.857 +* Effects : Results of the shifts are stored in this array
1.858 +* Returned : Reference to this array after shift
1.859 +***************************************************************************/
1.860 +BitArray& BitArray::operator<<=(const unsigned int shifts)
1.861 +{
1.862 + int i;
1.863 + int chars = shifts / CHAR_BIT; /* number of whole byte shifts */
1.864 +
1.865 + if (shifts >= m_NumBits)
1.866 + {
1.867 + /* all bits have been shifted off */
1.868 + this->ClearAll();
1.869 + return *this;
1.870 + }
1.871 +
1.872 + /* first handle big jumps of bytes */
1.873 + if (chars > 0)
1.874 + {
1.875 + int size;
1.876 +
1.877 + size = BITS_TO_CHARS(m_NumBits);
1.878 +
1.879 + for (i = 0; (i + chars) < size; i++)
1.880 + {
1.881 + m_Array[i] = m_Array[i + chars];
1.882 + }
1.883 +
1.884 + /* now zero out new bytes on the right */
1.885 + for (i = size; chars > 0; chars--)
1.886 + {
1.887 + m_Array[i - chars] = 0;
1.888 + }
1.889 + }
1.890 +
1.891 + /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
1.892 + for (i = 0; i < (int)(shifts % CHAR_BIT); i++)
1.893 + {
1.894 + for (unsigned int j = 0; j < BIT_CHAR(m_NumBits - 1); j++)
1.895 + {
1.896 + m_Array[j] <<= 1;
1.897 +
1.898 + /* handle shifts across byte bounds */
1.899 + if (m_Array[j + 1] & MS_BIT)
1.900 + {
1.901 + m_Array[j] |= 0x01;
1.902 + }
1.903 + }
1.904 +
1.905 + m_Array[BIT_CHAR(m_NumBits - 1)] <<= 1;
1.906 + }
1.907 +
1.908 + return *this;
1.909 +}
1.910 +
1.911 +/***************************************************************************
1.912 +* Method : operator>>=
1.913 +* Description: overload of the >>= operator. Performs a right shift on
1.914 +* this bit array. This bit array will contain the result.
1.915 +* Parameters : shifts - number of bit positions to shift
1.916 +* Effects : Results of the shifts are stored in this array
1.917 +* Returned : Reference to this array after shift
1.918 +***************************************************************************/
1.919 +BitArray& BitArray::operator>>=(const unsigned int shifts)
1.920 +{
1.921 + int i;
1.922 + char mask;
1.923 + int chars = shifts / CHAR_BIT; /* number of whole byte shifts */
1.924 +
1.925 + if (shifts >= m_NumBits)
1.926 + {
1.927 + /* all bits have been shifted off */
1.928 + this->ClearAll();
1.929 + return *this;
1.930 + }
1.931 +
1.932 + /* first handle big jumps of bytes */
1.933 + if (chars > 0)
1.934 + {
1.935 + for (i = BIT_CHAR(m_NumBits - 1); (i - chars) >= 0; i--)
1.936 + {
1.937 + m_Array[i] = m_Array[i - chars];
1.938 + }
1.939 +
1.940 + /* now zero out new bytes on the right */
1.941 + for (; chars > 0; chars--)
1.942 + {
1.943 + m_Array[chars - 1] = 0;
1.944 + }
1.945 + }
1.946 +
1.947 + /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
1.948 + for (i = 0; i < (int)(shifts % CHAR_BIT); i++)
1.949 + {
1.950 + for (unsigned int j = BIT_CHAR(m_NumBits - 1); j > 0; j--)
1.951 + {
1.952 + m_Array[j] >>= 1;
1.953 +
1.954 + /* handle shifts across byte bounds */
1.955 + if (m_Array[j - 1] & 0x01)
1.956 + {
1.957 + m_Array[j] |= MS_BIT;
1.958 + }
1.959 + }
1.960 +
1.961 + m_Array[0] >>= 1;
1.962 + }
1.963 +
1.964 + /***********************************************************************
1.965 + * zero any spare bits that are shifted beyond the end of the bit array
1.966 + * so that increment and decrement are consistent.
1.967 + ***********************************************************************/
1.968 + i = m_NumBits % CHAR_BIT;
1.969 + if (i != 0)
1.970 + {
1.971 + mask = UCHAR_MAX << (CHAR_BIT - i);
1.972 + m_Array[BIT_CHAR(m_NumBits - 1)] &= mask;
1.973 + }
1.974 +
1.975 + return *this;
1.976 +}
1.977 +
1.978 +/***************************************************************************
1.979 +* Method : bit_array_index_c - constructor
1.980 +* Description: This is the bit_array_index_c constructor. It stores a
1.981 +* pointer to the bit array and the bit index.
1.982 +* Parameters : array - pointer to bit array
1.983 +* index - index of bit in array
1.984 +* Effects : Pointer to bit array and bit index are stored.
1.985 +* Returned : None
1.986 +***************************************************************************/
1.987 +BitArrayIndex::BitArrayIndex(BitArray *array,
1.988 + const unsigned int index)
1.989 +{
1.990 + m_BitArray = array;
1.991 + m_Index = index;
1.992 +}
1.993 +
1.994 +/***************************************************************************
1.995 +* Method : operator=
1.996 +* Description: overload of the = operator. Sets the bit array bit to
1.997 +* the value of src.
1.998 +* Parameters : src - bit value
1.999 +* Effects : Bit pointed to by this object is set to the value of
1.1000 +* source.
1.1001 +* Returned : None
1.1002 +***************************************************************************/
1.1003 +void BitArrayIndex::operator=(const bool src)
1.1004 +{
1.1005 + if (m_BitArray == NULL)
1.1006 + {
1.1007 + return; /* no array */
1.1008 + }
1.1009 +
1.1010 + if (m_BitArray->SizeInBits() <= m_Index)
1.1011 + {
1.1012 + return; /* index is out of bounds */
1.1013 + }
1.1014 +
1.1015 + if (src)
1.1016 + {
1.1017 + m_BitArray->SetBit(m_Index);
1.1018 + }
1.1019 + else
1.1020 + {
1.1021 + m_BitArray->ClearBit(m_Index);
1.1022 + }
1.1023 +}