/*
 * Copyright (c) 2001 by Cliff Green. All rights reserved. Individual files
 * may be covered by other copyrights (as noted in the file itself).
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that this entire copyright notice is duplicated in all such
 * copies.
 *
 * This software is provided "as is" and without any expressed or implied
 * warranties, including, without limitation, the implied warranties of
 * merchantibility and fitness for any particular purpose.
*/
//----------------------------------------------------------------------
// Source file:   bitbuffer.h
// Written by:    Cliff Green, 2001
// Compiler:      Metrowerks CodeWarrior Pro 6
// History:
//   Modified:    11/22/2001
//   By:          Cliff Green
//   Comments:    Modified to use policy classes for the storage of the
//                bits (default to std::vector<bool>) and for the binary
//                buffer input / output objects (defaulted to
//                std::basic_string instantiated on unsigned char).
//                Boost concept checking has been added to verify policy
//                classes meet the requirements.
//----------------------------------------------------------------------
// This commentheader supports documentation tools such as Doc++ and
// Doxygen: http://www.doxygen.org/
//----------------------------------------------------------------------
/// Utility to handle variable / dynamic sized bit buffers.
/**
 *  This is a utility class and related functions to handle variable /
 *  dynamically sized bit buffers, pushing and extracting arbitrary bit
 *  groups on and off a bit buffer. This utility is meant to be used in
 *  situations where a std::bitset can not be used - for example, a
 *  variable length bit buffer where the contents and number of bit fields
 *  are not fixed at compile time and are dependent on run-time data.
 *
 *  The original version of this utility was written without looking at
 *  Herb Sutter's GOTW #72 - this class was simplified and re-written after
 *  reading the GOTW. See http://www.gotw.ca/ for more details.
 *
 *  A BinaryBuf utility class is used as input and output instead of a
 *  std::string or unsigned char array. See the documentation in BinaryBuf.h
 *  for further information. Where the bit manipulation algorithms (in the
 *  BitBuffer class) require unsigned char types, appropriate casting is
 *  performed (which results in a slight risk of non-portability).
 *
 *  The storage policy template type is used as an encapsulated container to
 *  store boolean values (corresponding to bits). The required capabilities of
 *  the storage policy type corresponds to a subset of the std::vector<bool>
 *  interface. Specifically the following functionality is required:
 *     1. Default constructor and copy constructor
 *     2. size() method, returning number of bits in the container
 *     3. push_back method, appends a bit to the end of the container
 *     4. operator[], for both accessing and setting an existing bit
 *  Note that std::deque<bool> can be used as the storage policy, if desired
 *  (although more memory might be used).
 *
 *  The BinaryBuf template type is a type corresponding to the Util::BinaryBuf
 *  interface. A plain std::string can also be used, since BinaryBuf follows
 *  the std::string interface, although care should be taken to ensure correct
 *  binary access is followed when using a plain std::string.
 *
 *  Usage examples:
 *     // Create with default template parms:
 *     Util::BitBuffer<> t1;
 *
 *     // Create with vector<bool>, BinaryBuf with default char type:
 *     Util::BitBuffer<std::vector<bool>, Util::BinaryBuf<> > t2;
 *
 *     // Create with deque<bool>, BinaryBuf with unsigned char:
 *     Util::BitBuffer<std::deque<bool>, Util::BinBufUnChar> t3;
 *
 *     t1.getBinaryBuf();                  // returns BinaryBuf of all the bits
 *     t1.getBinaryBuf(startBit, numBits); // returns BinaryBuf, starting at
 *                                         // startBit, for numBits 
 *     t1.size():                          // returns num bits in BitBuffer
 *     t1.appendBit (bool):                // pushes bit on to BitBuffer
 *     t1.appendVal (val, numBits);        // pushes numBits from val on to BitBuffer -
 *                         // val must be unsigned integral type, supporting bit shifting
 *     t1[5]                               // returns bool value at idx location
 *     t1.template getVal<T>(startBit, numBits); // returns value of type T, starting at
 *                         // startBit, for numBits; T must be unsigned integral type,
 *                         // supporting bit shifting; the 'template' keyword is required
 *                         // for compilers to disambiguate member template function syntax
 *                         // (since the template type cannot be deduced from the function
 *                         // arguments)
 *
 *  The getVal and appendVal have requirements on the templatized type, namely that they are
 *  unsigned integral types supporting the following operations:
 *     getVal: numeric initialization, << (left bit shift), + (addition), = (assignment)
 *     appendVal: initialization, <<, -- (decrement), =, & (bit and)
 *
 *  Where a startbit, number of bits, or index parameter is required, the value should be
 *  within the correct range. Invalid values result in either undefined results or an
 *  exception being thrown. Specifically, some of the pre-conditions include:
 *     BitBuffer(const BinBuf& b, size_t numBits) : b must have at least numBits bits,
 *          otherwise undefined results occur; b must also have zero-padded characters
 *          on the end of the binary buffer, if a non-modulo 8 number of bits is stored
 *     getBinaryBuf(size_t start, size_t numBits) : start+numBits must be within range,
 *          otherwise a std::invalid_argument exception is thrown
 *     appendBinaryBuf (const BinBuf& b, size_t numBits): same as constructor above
 *     setBit(idx), [idx]: index must be within range, else undefined results occur
 *     appendVal(T val, size_t numBits) : val must have at least numBits in the type
 *     getVal (size_t start, size_t numBits) : same as getBinaryBuf
 *
 *  The post-conditions should be obvious - append / set methods modify the container data
 *  accordingly, the const methods (get, size, etc) leave the data unmodified.
 */


#ifndef BITBUFFER_H
#define BITBUFFER_H

#include <vector>    // std::vector<bool> used for BitBuffer default storage type
#include <string>    // std::basic_string used for BitBuffer default buffer type
#include <stdexcept> // for error detection and handling
#include <stddef.h>  // for size_t
#include <limits>    // to get num bits per char

namespace Util {

// Helper classes to support member template functions

template <typename T, class StorPol>
   void appendVal (T val, size_t numBits, StorPol&);

template <typename T, class StorPol>
   T getVal (size_t startBit, size_t numBits, const StorPol&);

// BitBuffer class
// Note: BinBufUnChar is a typedef from BinaryBuf.h for BinaryBuf<std::basic_string<unsigned char> >

template < class StorPol = std::vector<bool>, class BinBuf = std::basic_string<unsigned char> >
class BitBuffer {
public:
   BitBuffer () : mBits() { }
   BitBuffer (const BinBuf& buf, size_t numBits) : mBits() { appendBinaryBuf(buf, numBits); }

   // ~BitBuffer(); // implicit
   // BitBuffer (const BitBuffer& ); // copy ctor implicit
   // BitBuffer& operator=(const BitBuffer& ); // assign op implicit

   const BinBuf getBinaryBuf() const { return getBinaryBuf(0, size()); }
   const BinBuf getBinaryBuf(size_t startBit, size_t numBits) const;
   void appendBinaryBuf( const BinBuf& buf, size_t numBits);

   size_t size () const { return mBits.size(); }

   void appendBit (bool bit) { mBits.push_back(bit); }
   void setBit (bool bit, size_t idx) { mBits[idx] = bit; }
   bool operator[] (size_t idx) const { return mBits[idx]; }

   template <typename T>
   inline void appendVal (T val, size_t numBits) {
      Util::appendVal(val, numBits, mBits);
   }

   template <typename T>
   inline T getVal (size_t startBit, size_t numBits) const {
      return Util::getVal<T>(startBit, numBits, mBits);
   }

private:
   StorPol   mBits;

}; // end BitBuffer class

// ---------- move to implementation file when 'export' is supported

template <class StorPol, class BinBuf >
const BinBuf BitBuffer<StorPol, BinBuf>::getBinaryBuf( size_t startBit, size_t numBits ) const {

   const int bitsPerChar = std::numeric_limits<unsigned char>::digits;

   if ( (startBit+numBits) > mBits.size() ) {
      throw std::invalid_argument ("Bit extraction ran off end of buffer");
   }

   BinBuf buf;
   buf.resize((numBits%bitsPerChar == 0 ? (numBits / bitsPerChar) : (numBits / bitsPerChar + 1)), 0);

   typedef typename BinBuf::value_type CharType;

   // Be very careful with the next statement - potentially unportable and unsafe code, depending
   // on the implementation of the BinBuf string class. An unsigned character pointer is needed,
   // however, since the bit manipulation depends on unsigned type characteristics.
   unsigned char* p (reinterpret_cast<unsigned char*>(const_cast<CharType*>(buf.data())));
   *p = 0;
   for( size_t i (0); i < numBits; ++i ) {
      unsigned char t(mBits[startBit+i]);
      *p |= static_cast<unsigned char>(t << (bitsPerChar-1 - i%bitsPerChar));
      if ( (i+1) % bitsPerChar == 0 ) {
         *++p = 0;
      }
   }
   return buf;
}

template <class StorPol, class BinBuf >
void BitBuffer<StorPol, BinBuf>::appendBinaryBuf( const BinBuf& buf, size_t numBits) {

   const int bitsPerChar = std::numeric_limits<unsigned char>::digits;

   const unsigned char* p (reinterpret_cast<const unsigned char*>(buf.data()));
   for( typename StorPol::size_type i(0); i < numBits; ++i ) {
      mBits.push_back( (*p & (1 << (bitsPerChar-1 - i%bitsPerChar)) ) != 0 );
      if ( (i+1) % bitsPerChar == 0 ) {
         ++p;
      }
   }
}

template <typename T, class StorPol>
void appendVal (T val, size_t numBits, StorPol& bits) {
   T mask (0);
   while (numBits > 0) {
      mask = static_cast<T>(1 << --numBits);
      bits.push_back ((val & mask) != 0);
   }
}

template <typename T, class StorPol>
T getVal (size_t startBit, size_t numBits, const StorPol& bits) {
   if ( (startBit+numBits) > bits.size() ) {
      throw std::invalid_argument ("Bit extraction ran off end of buffer");
   }
   T val(0);
   for (size_t i (startBit); i < startBit+numBits; ++i) {
      val = static_cast<T>((val << 1) + bits[i]);
   }
   return val;
}

// ---------- end of template function implementations

}  // end namespace

#endif