1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/MiniDisplay/BitArray.cpp Tue May 27 19:50:28 2014 +0200
1.3 @@ -0,0 +1,1012 @@
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 +{
1.132 + m_SizeInBytes = BITS_TO_CHARS(numBits);
1.133 +
1.134 +
1.135 + /* allocate space for bit array */
1.136 + m_Array = new unsigned char[m_SizeInBytes];
1.137 +
1.138 + /* set all bits to 0 */
1.139 + fill_n(m_Array, m_SizeInBytes, 0);
1.140 +}
1.141 +
1.142 +/***************************************************************************
1.143 +* Method : bit_array_c - constructor
1.144 +* Description: This is the bit_array_c constructor. It copies the
1.145 +* for contents of a vector of unsigned char into the
1.146 +* bitarray.
1.147 +* Parameters : vect - vector to be copied
1.148 +* numBits - number of bits in the array
1.149 +* Effects : Allocates vectory for array bits
1.150 +* Returned : None
1.151 +***************************************************************************/
1.152 +BitArray::BitArray(unsigned char *array, const int numBits):
1.153 + m_NumBits(numBits),
1.154 + m_Array(array)
1.155 +{
1.156 +}
1.157 +
1.158 +/***************************************************************************
1.159 +* Method : ~bit_array_c - destructor
1.160 +* Description: This is the bit_array_c destructor. At this point it's
1.161 +* just a place holder.
1.162 +* Parameters : None
1.163 +* Effects : None
1.164 +* Returned : None
1.165 +***************************************************************************/
1.166 +BitArray::~BitArray(void)
1.167 +{
1.168 + delete[] m_Array;
1.169 +}
1.170 +
1.171 +/***************************************************************************
1.172 +* Method : Dump
1.173 +* Description: This method dumps the conents of a bit array to stdout.
1.174 +* The format of the dump is a series of bytes represented in
1.175 +* hexadecimal.
1.176 +* Parameters : outStream - stream to write to
1.177 +* Effects : Array contents are dumped to stdout
1.178 +* Returned : None
1.179 +***************************************************************************/
1.180 +void BitArray::Dump(std::ostream &outStream)
1.181 +{
1.182 + int size;
1.183 +
1.184 + size = BITS_TO_CHARS(m_NumBits);
1.185 +
1.186 + outStream.width(2);
1.187 + outStream.fill('0');
1.188 + outStream << uppercase << hex << (int)(m_Array[0]); /* first byte */
1.189 +
1.190 + for (int i = 1; i < size; i++)
1.191 + {
1.192 + /* remaining bytes with a leading space */
1.193 + outStream << " ";
1.194 + outStream.width(2);
1.195 + outStream.fill('0');
1.196 + outStream << (int)(m_Array[i]);
1.197 + }
1.198 +
1.199 + outStream << dec;
1.200 +}
1.201 +
1.202 +/***************************************************************************
1.203 +* Method : SetAll
1.204 +* Description: This method sets every bit in the bit array to 1. This
1.205 +* method uses UCHAR_MAX to determine what it means to set
1.206 +* all bits in an unsigned char, so it is crucial that the
1.207 +* machine implementation of unsigned char utilizes all of
1.208 +* the bits in the memory allocated for an unsigned char.
1.209 +* Parameters : None
1.210 +* Effects : Each of the bits used in the bit array are set to 1.
1.211 +* Unused (spare) bits are set to 0.
1.212 +* Returned : None
1.213 +***************************************************************************/
1.214 +void BitArray::SetAll(void)
1.215 +{
1.216 + int bits, size;
1.217 + unsigned char mask;
1.218 +
1.219 + size = BITS_TO_CHARS(m_NumBits);
1.220 +
1.221 + /* set bits in all bytes to 1 */
1.222 + fill_n(m_Array, size, UCHAR_MAX);
1.223 +
1.224 + /* zero any spare bits so increment and decrement are consistent */
1.225 + bits = m_NumBits % CHAR_BIT;
1.226 + if (bits != 0)
1.227 + {
1.228 + mask = UCHAR_MAX << (CHAR_BIT - bits);
1.229 + m_Array[BIT_CHAR(m_NumBits - 1)] = mask;
1.230 + }
1.231 +}
1.232 +
1.233 +/***************************************************************************
1.234 +* Method : ClearAll
1.235 +* Description: This method sets every bit in the bit array to 0.
1.236 +* Parameters : None
1.237 +* Effects : Each of the bits in the bit array are set to 0.
1.238 +* Returned : None
1.239 +***************************************************************************/
1.240 +void BitArray::ClearAll(void)
1.241 +{
1.242 + int size;
1.243 +
1.244 + size = BITS_TO_CHARS(m_NumBits);
1.245 +
1.246 + /* set bits in all bytes to 0 */
1.247 + fill_n(m_Array, size, 0);
1.248 +}
1.249 +
1.250 +/***************************************************************************
1.251 +* Method : SetBit
1.252 +* Description: This method sets a bit in the bit array to 1.
1.253 +* Parameters : bit - the number of the bit to set
1.254 +* Effects : The specified bit will be set to 1.
1.255 +* Returned : None
1.256 +***************************************************************************/
1.257 +void BitArray::SetBit(const unsigned int bit)
1.258 +{
1.259 + if (m_NumBits <= bit)
1.260 + {
1.261 + return; /* bit out of range */
1.262 + }
1.263 +
1.264 + m_Array[BIT_CHAR(bit)] |= BIT_IN_CHAR(bit);
1.265 +}
1.266 +
1.267 +/**
1.268 +*/
1.269 +void BitArray::SetBitValue(const unsigned int bit, bool aValue)
1.270 + {
1.271 + if (aValue)
1.272 + {
1.273 + SetBit(bit);
1.274 + }
1.275 + else
1.276 + {
1.277 + ClearBit(bit);
1.278 + }
1.279 + }
1.280 +
1.281 +/***************************************************************************
1.282 +* Method : ClearBit
1.283 +* Description: This method sets a bit in the bit array to 0.
1.284 +* Parameters : bit - the number of the bit to clear
1.285 +* Effects : The specified bit will be set to 0.
1.286 +* Returned : None
1.287 +***************************************************************************/
1.288 +void BitArray::ClearBit(const unsigned int bit)
1.289 +{
1.290 + unsigned char mask;
1.291 +
1.292 + if (m_NumBits <= bit)
1.293 + {
1.294 + return; /* bit out of range */
1.295 + }
1.296 +
1.297 + /* create a mask to zero out desired bit */
1.298 + mask = BIT_IN_CHAR(bit);
1.299 + mask = ~mask;
1.300 +
1.301 + m_Array[BIT_CHAR(bit)] &= mask;
1.302 +}
1.303 +
1.304 +/***************************************************************************
1.305 +* Method : operator()
1.306 +* Description: Overload of the () operator. This method approximates
1.307 +* array indices used for assignment. It returns a
1.308 +* bit_array_index_c which includes an = method used to
1.309 +* set bit values.
1.310 +* Parameters : bit - index of array bit
1.311 +* Effects : None
1.312 +* Returned : bit_array_index_c (pointer to bit)
1.313 +***************************************************************************/
1.314 +BitArrayIndex BitArray::operator()(const unsigned int bit)
1.315 +{
1.316 + BitArrayIndex result(this, bit);
1.317 +
1.318 + return result;
1.319 +}
1.320 +
1.321 +/***************************************************************************
1.322 +* Method : operator[]
1.323 +* Description: Overload of the [] operator. This method returns the
1.324 +* value of a bit in the bit array.
1.325 +* Parameters : bit - index of array bit
1.326 +* Effects : None
1.327 +* Returned : The value of the specified bit.
1.328 +***************************************************************************/
1.329 +bool BitArray::operator[](const unsigned int bit) const
1.330 +{
1.331 + return((m_Array[BIT_CHAR(bit)] & BIT_IN_CHAR(bit)) != 0);
1.332 +}
1.333 +
1.334 +/***************************************************************************
1.335 +* Method : operator==
1.336 +* Description: overload of the == operator
1.337 +* Parameters : other - bit array to compare
1.338 +* Effects : None
1.339 +* Returned : True if this == other. Otherwise false.
1.340 +***************************************************************************/
1.341 +bool BitArray::operator==(const BitArray &other) const
1.342 +{
1.343 + if (m_NumBits != other.m_NumBits)
1.344 + {
1.345 + /* unequal sizes */
1.346 + return false;
1.347 + }
1.348 +
1.349 + return (this->m_Array == other.m_Array);
1.350 +}
1.351 +
1.352 +/***************************************************************************
1.353 +* Method : operator!=
1.354 +* Description: overload of the != operator
1.355 +* Parameters : other - bit array to compare
1.356 +* Effects : None
1.357 +* Returned : True if this != other. Otherwise false.
1.358 +***************************************************************************/
1.359 +bool BitArray::operator!=(const BitArray &other) const
1.360 +{
1.361 + if (m_NumBits != other.m_NumBits)
1.362 + {
1.363 + /* unequal sizes */
1.364 + return true;
1.365 + }
1.366 +
1.367 + return (this->m_Array != other.m_Array);
1.368 +}
1.369 +
1.370 +/***************************************************************************
1.371 +* Method : operator<
1.372 +* Description: overload of the < operator
1.373 +* Parameters : other - bit array to compare
1.374 +* Effects : None
1.375 +* Returned : True if this < other. Otherwise false.
1.376 +***************************************************************************/
1.377 +bool BitArray::operator<(const BitArray &other) const
1.378 +{
1.379 + if (m_NumBits != other.m_NumBits)
1.380 + {
1.381 + /* unequal sizes */
1.382 + return false;
1.383 + }
1.384 +
1.385 + return (this->m_Array < other.m_Array);
1.386 +}
1.387 +
1.388 +/***************************************************************************
1.389 +* Method : operator<=
1.390 +* Description: overload of the <= operator
1.391 +* Parameters : other - bit array to compare
1.392 +* Effects : None
1.393 +* Returned : True if this <= other. Otherwise false.
1.394 +***************************************************************************/
1.395 +bool BitArray::operator<=(const BitArray &other) const
1.396 +{
1.397 + if (m_NumBits != other.m_NumBits)
1.398 + {
1.399 + /* unequal sizes */
1.400 + return false;
1.401 + }
1.402 +
1.403 + return (this->m_Array <= other.m_Array);
1.404 +}
1.405 +
1.406 +/***************************************************************************
1.407 +* Method : operator>
1.408 +* Description: overload of the > operator
1.409 +* Parameters : other - bit array to compare
1.410 +* Effects : None
1.411 +* Returned : True if this > other. Otherwise false.
1.412 +***************************************************************************/
1.413 +bool BitArray::operator>(const BitArray &other) const
1.414 +{
1.415 + if (m_NumBits != other.m_NumBits)
1.416 + {
1.417 + /* unequal sizes */
1.418 + return false;
1.419 + }
1.420 +
1.421 + return (this->m_Array > other.m_Array);
1.422 +}
1.423 +
1.424 +/***************************************************************************
1.425 +* Method : operator>=
1.426 +* Description: overload of the >= operator
1.427 +* Parameters : other - bit array to compare
1.428 +* Effects : None
1.429 +* Returned : True if this >= other. Otherwise false.
1.430 +***************************************************************************/
1.431 +bool BitArray::operator>=(const BitArray &other) const
1.432 +{
1.433 + if (m_NumBits != other.m_NumBits)
1.434 + {
1.435 + /* unequal sizes */
1.436 + return false;
1.437 + }
1.438 +
1.439 + return (this->m_Array >= other.m_Array);
1.440 +}
1.441 +
1.442 +/***************************************************************************
1.443 +* Method : operator~
1.444 +* Description: overload of the ~ operator. Negates all non-spare bits in
1.445 +* bit array
1.446 +* Parameters : None
1.447 +* Effects : None
1.448 +* Returned : value of this after bitwise not
1.449 +***************************************************************************/
1.450 +BitArray BitArray::operator~(void) const
1.451 +{
1.452 + BitArray result(this->m_NumBits);
1.453 + result = *this;
1.454 + result.Not();
1.455 +
1.456 + return result;
1.457 +}
1.458 +
1.459 +/***************************************************************************
1.460 +* Method : operator&
1.461 +* Description: overload of the & operator. Performs a bitwise and
1.462 +* between the source array and this bit array.
1.463 +* Parameters : other - bit array on righthand side of &
1.464 +* Effects : None
1.465 +* Returned : value of bitwise and of this and other.
1.466 +***************************************************************************/
1.467 +BitArray BitArray::operator&(const BitArray &other) const
1.468 +{
1.469 + BitArray result(this->m_NumBits);
1.470 + result = *this;
1.471 + result &= other;
1.472 +
1.473 + return result;
1.474 +}
1.475 +
1.476 +
1.477 +/***************************************************************************
1.478 +* Method : operator^
1.479 +* Description: overload of the ^ operator. Performs a bitwise xor
1.480 +* between the source array and this bit array.
1.481 +* Parameters : other - bit array on righthand side of ^
1.482 +* Effects : None
1.483 +* Returned : value of bitwise xor of this and other.
1.484 +***************************************************************************/
1.485 +BitArray BitArray::operator^(const BitArray &other) const
1.486 +{
1.487 + BitArray result(this->m_NumBits);
1.488 + result = *this;
1.489 + result ^= other;
1.490 +
1.491 + return result;
1.492 +}
1.493 +
1.494 +/***************************************************************************
1.495 +* Method : operator|
1.496 +* Description: overload of the | operator. Performs a bitwise or
1.497 +* between the source array and this bit array.
1.498 +* Parameters : other - bit array on righthand side of |
1.499 +* Effects : None
1.500 +* Returned : value of bitwise or of this and other.
1.501 +***************************************************************************/
1.502 +BitArray BitArray::operator|(const BitArray &other) const
1.503 +{
1.504 + BitArray result(this->m_NumBits);
1.505 + result = *this;
1.506 + result |= other;
1.507 +
1.508 + return result;
1.509 +}
1.510 +
1.511 +/***************************************************************************
1.512 +* Method : operator<<
1.513 +* Description: overload of the << operator. Performs a bitwise left
1.514 +* shift of this bit array.
1.515 +* Parameters : count - the number of bits to shift left
1.516 +* Effects : None
1.517 +* Returned : result of bitwise left shift
1.518 +***************************************************************************/
1.519 +BitArray BitArray::operator<<(const unsigned int count) const
1.520 +{
1.521 + BitArray result(this->m_NumBits);
1.522 + result = *this;
1.523 + result <<= count;
1.524 +
1.525 + return result;
1.526 +}
1.527 +
1.528 +/***************************************************************************
1.529 +* Method : operator>>
1.530 +* Description: overload of the >> operator. Performs a bitwise right
1.531 +* shift of this bit array.
1.532 +* Parameters : count - the number of bits to shift right
1.533 +* Effects : None
1.534 +* Returned : result of bitwise right shift
1.535 +***************************************************************************/
1.536 +BitArray BitArray::operator>>(const unsigned int count) const
1.537 +{
1.538 + BitArray result(this->m_NumBits);
1.539 + result = *this;
1.540 + result >>= count;
1.541 +
1.542 + return result;
1.543 +}
1.544 +
1.545 +/***************************************************************************
1.546 +* Method : operator++ (prefix)
1.547 +* Description: overload of the ++ operator. Increments the contents of
1.548 +* a bit array. Overflows cause rollover.
1.549 +* Parameters : None
1.550 +* Effects : Bit array contents are incremented
1.551 +* Returned : Reference to this array after increment
1.552 +***************************************************************************/
1.553 +BitArray& BitArray::operator++(void)
1.554 +{
1.555 + int i;
1.556 + unsigned char maxValue; /* maximum value for current char */
1.557 + unsigned char one; /* least significant bit in current char */
1.558 +
1.559 + if (m_NumBits == 0)
1.560 + {
1.561 + return *this; /* nothing to increment */
1.562 + }
1.563 +
1.564 + /* handle arrays that don't use every bit in the last character */
1.565 + i = (m_NumBits % CHAR_BIT);
1.566 + if (i != 0)
1.567 + {
1.568 + maxValue = UCHAR_MAX << (CHAR_BIT - i);
1.569 + one = 1 << (CHAR_BIT - i);
1.570 + }
1.571 + else
1.572 + {
1.573 + maxValue = UCHAR_MAX;
1.574 + one = 1;
1.575 + }
1.576 +
1.577 + for (i = BIT_CHAR(m_NumBits - 1); i >= 0; i--)
1.578 + {
1.579 + if (m_Array[i] != maxValue)
1.580 + {
1.581 + m_Array[i] = m_Array[i] + one;
1.582 + return *this;
1.583 + }
1.584 + else
1.585 + {
1.586 + /* need to carry to next byte */
1.587 + m_Array[i] = 0;
1.588 +
1.589 + /* remaining characters must use all bits */
1.590 + maxValue = UCHAR_MAX;
1.591 + one = 1;
1.592 + }
1.593 + }
1.594 +
1.595 + return *this;
1.596 +}
1.597 +
1.598 +/***************************************************************************
1.599 +* Method : operator++ (postfix)
1.600 +* Description: overload of the ++ operator. Increments the contents of
1.601 +* a bit array. Overflows cause rollover.
1.602 +* Parameters : dumy - needed for postfix increment
1.603 +* Effects : Bit array contents are incremented
1.604 +* Returned : Reference to this array after increment
1.605 +***************************************************************************/
1.606 +BitArray& BitArray::operator++(int dummy)
1.607 +{
1.608 + ++(*this);
1.609 + return *this;
1.610 +}
1.611 +
1.612 +/***************************************************************************
1.613 +* Method : operator-- (prefix)
1.614 +* Description: overload of the -- operator. Decrements the contents of
1.615 +* a bit array. Underflows cause rollover.
1.616 +* Parameters : None
1.617 +* Effects : Bit array contents are decremented
1.618 +* Returned : None
1.619 +***************************************************************************/
1.620 +BitArray& BitArray::operator--(void)
1.621 +{
1.622 + int i;
1.623 + unsigned char maxValue; /* maximum value for current char */
1.624 + unsigned char one; /* least significant bit in current char */
1.625 +
1.626 + if (m_NumBits == 0)
1.627 + {
1.628 + return *this; /* nothing to decrement */
1.629 + }
1.630 +
1.631 + /* handle arrays that don't use every bit in the last character */
1.632 + i = (m_NumBits % CHAR_BIT);
1.633 + if (i != 0)
1.634 + {
1.635 + maxValue = UCHAR_MAX << (CHAR_BIT - i);
1.636 + one = 1 << (CHAR_BIT - i);
1.637 + }
1.638 + else
1.639 + {
1.640 + maxValue = UCHAR_MAX;
1.641 + one = 1;
1.642 + }
1.643 +
1.644 + for (i = BIT_CHAR(m_NumBits - 1); i >= 0; i--)
1.645 + {
1.646 + if (m_Array[i] >= one)
1.647 + {
1.648 + m_Array[i] = m_Array[i] - one;
1.649 + return *this;
1.650 + }
1.651 + else
1.652 + {
1.653 + /* need to borrow from the next byte */
1.654 + m_Array[i] = maxValue;
1.655 +
1.656 + /* remaining characters must use all bits */
1.657 + maxValue = UCHAR_MAX;
1.658 + one = 1;
1.659 + }
1.660 + }
1.661 +
1.662 + return *this;
1.663 +}
1.664 +
1.665 +/***************************************************************************
1.666 +* Method : operator-- (postfix)
1.667 +* Description: overload of the -- operator. Decrements the contents of
1.668 +* a bit array. Underflows cause rollover.
1.669 +* Parameters : dumy - needed for postfix decrement
1.670 +* Effects : Bit array contents are decremented
1.671 +* Returned : None
1.672 +***************************************************************************/
1.673 +BitArray& BitArray::operator--(int dummy)
1.674 +{
1.675 + --(*this);
1.676 + return *this;
1.677 +}
1.678 +
1.679 +/***************************************************************************
1.680 +* Method : operator=
1.681 +* Description: overload of the = operator. Copies source contents into
1.682 +* this bit array.
1.683 +* Parameters : src - Source bit array
1.684 +* Effects : Source bit array contents are copied into this array
1.685 +* Returned : Reference to this array after copy
1.686 +***************************************************************************/
1.687 +BitArray& BitArray::operator=(const BitArray &src)
1.688 +{
1.689 + if (*this == src)
1.690 + {
1.691 + /* don't do anything for a self assignment */
1.692 + return *this;
1.693 + }
1.694 +
1.695 + if (m_NumBits != src.m_NumBits)
1.696 + {
1.697 + /* don't do assignment with different array sizes */
1.698 + return *this;
1.699 + }
1.700 +
1.701 + if ((m_NumBits == 0) || (src.m_NumBits == 0))
1.702 + {
1.703 + /* don't do assignment with unallocated array */
1.704 + return *this;
1.705 + }
1.706 +
1.707 + /* copy bits from source */
1.708 + int size;
1.709 + size = BITS_TO_CHARS(m_NumBits);
1.710 +
1.711 + copy(src.m_Array, &src.m_Array[size], this->m_Array);
1.712 + return *this;
1.713 +}
1.714 +
1.715 +/***************************************************************************
1.716 +* Method : operator&=
1.717 +* Description: overload of the &= operator. Performs a bitwise and
1.718 +* between the source array and this bit array. This bit
1.719 +* array will contain the result.
1.720 +* Parameters : src - Source bit array
1.721 +* Effects : Results of bitwise and are stored in this array
1.722 +* Returned : Reference to this array after and
1.723 +***************************************************************************/
1.724 +BitArray& BitArray::operator&=(const BitArray &src)
1.725 +{
1.726 + int size;
1.727 +
1.728 + size = BITS_TO_CHARS(m_NumBits);
1.729 +
1.730 + if (m_NumBits != src.m_NumBits)
1.731 + {
1.732 + /* don't do assignment with different array sizes */
1.733 + return *this;
1.734 + }
1.735 +
1.736 + /* AND array one unsigned char at a time */
1.737 + for(int i = 0; i < size; i++)
1.738 + {
1.739 + m_Array[i] = m_Array[i] & src.m_Array[i];
1.740 + }
1.741 +
1.742 + return *this;
1.743 +}
1.744 +
1.745 +/***************************************************************************
1.746 +* Method : operator^=
1.747 +* Description: overload of the ^= operator. Performs a bitwise xor
1.748 +* between the source array and this bit array. This bit
1.749 +* array will contain the result.
1.750 +* Parameters : src - Source bit array
1.751 +* Effects : Results of bitwise xor are stored in this array
1.752 +* Returned : Reference to this array after xor
1.753 +***************************************************************************/
1.754 +BitArray& BitArray::operator^=(const BitArray &src)
1.755 +{
1.756 + int size;
1.757 +
1.758 + size = BITS_TO_CHARS(m_NumBits);
1.759 +
1.760 + if (m_NumBits != src.m_NumBits)
1.761 + {
1.762 + /* don't do assignment with different array sizes */
1.763 + return *this;
1.764 + }
1.765 +
1.766 + /* XOR array one unsigned char at a time */
1.767 + for(int i = 0; i < size; i++)
1.768 + {
1.769 + m_Array[i] = m_Array[i] ^ src.m_Array[i];
1.770 + }
1.771 +
1.772 + return *this;
1.773 +}
1.774 +
1.775 +/***************************************************************************
1.776 +* Method : operator|=
1.777 +* Description: overload of the |= operator. Performs a bitwise or
1.778 +* between the source array and this bit array. This bit
1.779 +* array will contain the result.
1.780 +* Parameters : src - Source bit array
1.781 +* Effects : Results of bitwise or are stored in this array
1.782 +* Returned : Reference to this array after or
1.783 +***************************************************************************/
1.784 +BitArray& BitArray::operator|=(const BitArray &src)
1.785 +{
1.786 + int size;
1.787 +
1.788 + size = BITS_TO_CHARS(m_NumBits);
1.789 +
1.790 + if (m_NumBits != src.m_NumBits)
1.791 + {
1.792 + /* don't do assignment with different array sizes */
1.793 + return *this;
1.794 + }
1.795 +
1.796 + /* OR array one unsigned char at a time */
1.797 + for(int i = 0; i < size; i++)
1.798 + {
1.799 + m_Array[i] = m_Array[i] | src.m_Array[i];
1.800 + }
1.801 +
1.802 + return *this;
1.803 +}
1.804 +
1.805 +/***************************************************************************
1.806 +* Method : Not
1.807 +* Description: Negates all non-spare bits in bit array.
1.808 +* Parameters : None
1.809 +* Effects : Contents of bit array are negated. Any spare bits are
1.810 +* left at 0.
1.811 +* Returned : Reference to this array after not
1.812 +***************************************************************************/
1.813 +BitArray& BitArray::Not(void)
1.814 +{
1.815 + int bits;
1.816 + unsigned char mask;
1.817 + int size;
1.818 +
1.819 + size = BITS_TO_CHARS(m_NumBits);
1.820 +
1.821 + if (m_NumBits == 0)
1.822 + {
1.823 + /* don't do not with unallocated array */
1.824 + return *this;
1.825 + }
1.826 +
1.827 + /* NOT array one unsigned char at a time */
1.828 + for(int i = 0; i < size; i++)
1.829 + {
1.830 + m_Array[i] = ~m_Array[i];
1.831 + }
1.832 +
1.833 + /* zero any spare bits so increment and decrement are consistent */
1.834 + bits = m_NumBits % CHAR_BIT;
1.835 + if (bits != 0)
1.836 + {
1.837 + mask = UCHAR_MAX << (CHAR_BIT - bits);
1.838 + m_Array[BIT_CHAR(m_NumBits - 1)] &= mask;
1.839 + }
1.840 +
1.841 + return *this;
1.842 +}
1.843 +
1.844 +/***************************************************************************
1.845 +* Method : operator<<=
1.846 +* Description: overload of the <<= operator. Performs a left shift on
1.847 +* this bit array. This bit array will contain the result.
1.848 +* Parameters : shifts - number of bit positions to shift
1.849 +* Effects : Results of the shifts are stored in this array
1.850 +* Returned : Reference to this array after shift
1.851 +***************************************************************************/
1.852 +BitArray& BitArray::operator<<=(const unsigned int shifts)
1.853 +{
1.854 + int i;
1.855 + int chars = shifts / CHAR_BIT; /* number of whole byte shifts */
1.856 +
1.857 + if (shifts >= m_NumBits)
1.858 + {
1.859 + /* all bits have been shifted off */
1.860 + this->ClearAll();
1.861 + return *this;
1.862 + }
1.863 +
1.864 + /* first handle big jumps of bytes */
1.865 + if (chars > 0)
1.866 + {
1.867 + int size;
1.868 +
1.869 + size = BITS_TO_CHARS(m_NumBits);
1.870 +
1.871 + for (i = 0; (i + chars) < size; i++)
1.872 + {
1.873 + m_Array[i] = m_Array[i + chars];
1.874 + }
1.875 +
1.876 + /* now zero out new bytes on the right */
1.877 + for (i = size; chars > 0; chars--)
1.878 + {
1.879 + m_Array[i - chars] = 0;
1.880 + }
1.881 + }
1.882 +
1.883 + /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
1.884 + for (i = 0; i < (int)(shifts % CHAR_BIT); i++)
1.885 + {
1.886 + for (unsigned int j = 0; j < BIT_CHAR(m_NumBits - 1); j++)
1.887 + {
1.888 + m_Array[j] <<= 1;
1.889 +
1.890 + /* handle shifts across byte bounds */
1.891 + if (m_Array[j + 1] & MS_BIT)
1.892 + {
1.893 + m_Array[j] |= 0x01;
1.894 + }
1.895 + }
1.896 +
1.897 + m_Array[BIT_CHAR(m_NumBits - 1)] <<= 1;
1.898 + }
1.899 +
1.900 + return *this;
1.901 +}
1.902 +
1.903 +/***************************************************************************
1.904 +* Method : operator>>=
1.905 +* Description: overload of the >>= operator. Performs a right shift on
1.906 +* this bit array. This bit array will contain the result.
1.907 +* Parameters : shifts - number of bit positions to shift
1.908 +* Effects : Results of the shifts are stored in this array
1.909 +* Returned : Reference to this array after shift
1.910 +***************************************************************************/
1.911 +BitArray& BitArray::operator>>=(const unsigned int shifts)
1.912 +{
1.913 + int i;
1.914 + char mask;
1.915 + int chars = shifts / CHAR_BIT; /* number of whole byte shifts */
1.916 +
1.917 + if (shifts >= m_NumBits)
1.918 + {
1.919 + /* all bits have been shifted off */
1.920 + this->ClearAll();
1.921 + return *this;
1.922 + }
1.923 +
1.924 + /* first handle big jumps of bytes */
1.925 + if (chars > 0)
1.926 + {
1.927 + for (i = BIT_CHAR(m_NumBits - 1); (i - chars) >= 0; i--)
1.928 + {
1.929 + m_Array[i] = m_Array[i - chars];
1.930 + }
1.931 +
1.932 + /* now zero out new bytes on the right */
1.933 + for (; chars > 0; chars--)
1.934 + {
1.935 + m_Array[chars - 1] = 0;
1.936 + }
1.937 + }
1.938 +
1.939 + /* now we have at most CHAR_BIT - 1 bit shifts across the whole array */
1.940 + for (i = 0; i < (int)(shifts % CHAR_BIT); i++)
1.941 + {
1.942 + for (unsigned int j = BIT_CHAR(m_NumBits - 1); j > 0; j--)
1.943 + {
1.944 + m_Array[j] >>= 1;
1.945 +
1.946 + /* handle shifts across byte bounds */
1.947 + if (m_Array[j - 1] & 0x01)
1.948 + {
1.949 + m_Array[j] |= MS_BIT;
1.950 + }
1.951 + }
1.952 +
1.953 + m_Array[0] >>= 1;
1.954 + }
1.955 +
1.956 + /***********************************************************************
1.957 + * zero any spare bits that are shifted beyond the end of the bit array
1.958 + * so that increment and decrement are consistent.
1.959 + ***********************************************************************/
1.960 + i = m_NumBits % CHAR_BIT;
1.961 + if (i != 0)
1.962 + {
1.963 + mask = UCHAR_MAX << (CHAR_BIT - i);
1.964 + m_Array[BIT_CHAR(m_NumBits - 1)] &= mask;
1.965 + }
1.966 +
1.967 + return *this;
1.968 +}
1.969 +
1.970 +/***************************************************************************
1.971 +* Method : bit_array_index_c - constructor
1.972 +* Description: This is the bit_array_index_c constructor. It stores a
1.973 +* pointer to the bit array and the bit index.
1.974 +* Parameters : array - pointer to bit array
1.975 +* index - index of bit in array
1.976 +* Effects : Pointer to bit array and bit index are stored.
1.977 +* Returned : None
1.978 +***************************************************************************/
1.979 +BitArrayIndex::BitArrayIndex(BitArray *array,
1.980 + const unsigned int index)
1.981 +{
1.982 + m_BitArray = array;
1.983 + m_Index = index;
1.984 +}
1.985 +
1.986 +/***************************************************************************
1.987 +* Method : operator=
1.988 +* Description: overload of the = operator. Sets the bit array bit to
1.989 +* the value of src.
1.990 +* Parameters : src - bit value
1.991 +* Effects : Bit pointed to by this object is set to the value of
1.992 +* source.
1.993 +* Returned : None
1.994 +***************************************************************************/
1.995 +void BitArrayIndex::operator=(const bool src)
1.996 +{
1.997 + if (m_BitArray == NULL)
1.998 + {
1.999 + return; /* no array */
1.1000 + }
1.1001 +
1.1002 + if (m_BitArray->SizeInBits() <= m_Index)
1.1003 + {
1.1004 + return; /* index is out of bounds */
1.1005 + }
1.1006 +
1.1007 + if (src)
1.1008 + {
1.1009 + m_BitArray->SetBit(m_Index);
1.1010 + }
1.1011 + else
1.1012 + {
1.1013 + m_BitArray->ClearBit(m_Index);
1.1014 + }
1.1015 +}