// Buffer for packing bits and values -*- c++ -*-

#ifndef BITBUFFER_H_
# define BITBUFFER_H_
# ifdef __GNUC__
#  pragma interface
# endif // __GNUC__

/** @file BitBuffer.h
 * Encoding and decoding numbers and values in bit strings
 */

/* Copyright  1999-2002 Marko Mkel (msmakela@tcs.hut.fi).

   This file is part of MARIA, a reachability analyzer and model checker
   for high-level Petri nets.

   MARIA is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   MARIA is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   The GNU General Public License is often shipped with GNU software, and
   is generally kept in a file called COPYING or LICENSE.  If you do not
   have a copy of the license, write to the Free Software Foundation,
   59 Temple Place, Suite 330, Boston, MA 02111 USA. */

# include "typedefs.h"
# include <string.h>
# include <assert.h>
# if defined (__linux__)
#  include <endian.h>
#  if !defined BYTE_ORDER
#   define BYTE_ORDER __BYTE_ORDER
#   define LITTLE_ENDIAN __LITTLE_ENDIAN
#   define BIG_ENDIAN __BIG_ENDIAN
#  endif /* !defined BYTE_ORDER */
# elif defined (_AIX)
#  include <sys/machine.h>
# elif defined (__alpha)
#  include <machine/endian.h>
# elif defined (__sun) || defined (__hpux)
#  include <sys/byteorder.h>
#  if !defined (BYTE_ORDER)
#   define LITTLE_ENDIAN 1234
#   define BIG_ENDIAN 4321
#   if !defined (_LITTLE_ENDIAN) && !defined (_BIG_ENDIAN)
#    ifdef ntohl
#     define _LITTLE_ENDIAN
#    else
#     define _BIG_ENDIAN
#    endif
#   endif
#   if defined (_LITTLE_ENDIAN)
#    define BYTE_ORDER LITTLE_ENDIAN
#   elif defined (_BIG_ENDIAN)
#    define BYTE_ORDER BIG_ENDIAN
#   endif // little/big endian
#  endif // !defined(BYTE_ORDER)
# elif defined (__sgi)
#  include <standards.h>
#  include <sys/endian.h>
# elif !defined BYTE_ORDER
#  define LITTLE_ENDIAN 1234
#  define BIG_ENDIAN 4321
#  if defined __i386
#   define BYTE_ORDER LITTLE_ENDIAN
#  else
#   error "cannot determine the byte order"
#  endif
# endif

/** Machine word */
# if (BYTE_ORDER == BIG_ENDIAN || BYTE_ORDER == LITTLE_ENDIAN)
typedef unsigned long word_t;
# else // middle-endian
typedef unsigned char word_t;
# endif // BYTE_ORDER
/** Length of the machine word in bits */
# define WORD_T_BIT (CHAR_BIT * sizeof (word_t))

/** Buffer for packing bits */
class BitPacker
{
public:
  /** Constructor
   * @param increment	Buffer allocation granularity (in WORD_T_BITs)
   */
  explicit BitPacker (card_t increment = 16) :
    myBuf (0), myAllocated (0), myLength (0), myIncrement (increment) {}
private:
  /** Copy constructor */
  explicit BitPacker (const class BitPacker& old);
  /** Assignment operator */
  class BitPacker& operator= (const class BitPacker& old);
public:
  /** Destructor */
  ~BitPacker () { delete[] myBuf; }

  /** Append data to the buffer
   * @param data	Data to be appended
   * @param bits	Length of data in bits
   */
  void append (card_t data, unsigned bits) {
    assert (myIncrement);
    assert (bits && bits <= CARD_T_BIT);
    assert (bits == CARD_T_BIT || !(data >> bits));
    // enlarge the buffer if necessary
    if (myLength + bits > myAllocated * WORD_T_BIT) {
      do
	myAllocated += myIncrement;
      while (myLength + bits > myAllocated * WORD_T_BIT);
      word_t* buf = new word_t[myAllocated];
      size_t offset = (myLength + WORD_T_BIT - 1) / WORD_T_BIT;
      memcpy (buf, myBuf, offset * sizeof *buf);
      memset (buf + offset, 0, (myAllocated - offset) * sizeof *buf);
      delete[] myBuf;
      myBuf = buf;
    }

    // append the data to the buffer
    unsigned wordpos = myLength / WORD_T_BIT, bitpos = myLength % WORD_T_BIT;
    assert (!(myBuf[wordpos] >> bitpos));
    myLength += bits;
    myBuf[wordpos] |= word_t (data) << bitpos;
    if (bitpos + bits > WORD_T_BIT) {
      bitpos = WORD_T_BIT - bitpos;
      myBuf[++wordpos] = data >>= bitpos;
# if !(BYTE_ORDER == BIG_ENDIAN || BYTE_ORDER == LITTLE_ENDIAN)
      for (bits -= bitpos; bits > WORD_T_BIT; bits -= WORD_T_BIT)
	myBuf[++wordpos] = data >>= WORD_T_BIT;
# endif
    }
  }
  /** Remove data from the buffer
   * @param bits	number of bits to remove
   */
  void remove (unsigned bits) {
    assert (myLength >= bits);
    myLength -= bits;
    // calculate the word and bit offsets
    unsigned wordpos = myLength / WORD_T_BIT, bitpos = myLength % WORD_T_BIT;
    // clear the remaining bits of the last word
    if (bitpos)
      myBuf[wordpos] &= (word_t (1) << bitpos) - 1;
    // clear the remaining whole words
    memset (myBuf + wordpos, 0,
	    ((myLength + bits) / WORD_T_BIT - wordpos) * sizeof *myBuf);
  }

  /** Append a value to the buffer
   * @param value	Value to be appended
   */
  void append (const class Value& value);

  /** Clear the buffer */
  void clear () {
    myLength = 0;
    memset (myBuf, 0, myAllocated * sizeof *myBuf);
  }
  /** Determine whether the buffer is empty */
  bool empty () const { return myLength == 0; }
  /** Determine the length of the encoded data in bits */
  unsigned getLength () const { return myLength; }
  /** Determine the length of the encoded data in blocks of bits
   * @param size	the block size in bits
   * @return		number of blocks
   */
  unsigned getNumBlocks (unsigned size) const {
    return (myLength + size - 1) / size;
  }
  /** Determine the length of the encoded data in bytes */
  unsigned getNumBytes () const { return getNumBlocks (CHAR_T_BIT); }
  /** Determine the length of the encoded data in words */
  unsigned getNumWords () const { return getNumBlocks (WORD_T_BIT); }

  /** Get the buffer contents */
  const word_t* getBuf () const { return myBuf; }

  /** Remove leading zero bytes from the last word */
  void deflate () {
# if BYTE_ORDER == BIG_ENDIAN
    if (myLength % WORD_T_BIT)
      deflate (myBuf[myLength / WORD_T_BIT],
	       unsigned (-getNumBytes ()) % sizeof (word_t));
# endif // big endian
  }

  /** Restore leading zero bytes to the last word */
  void inflate () {
# if BYTE_ORDER == BIG_ENDIAN
    if (myLength % WORD_T_BIT)
      inflate (myBuf[myLength / WORD_T_BIT],
	       unsigned (-getNumBytes ()) % sizeof (word_t));
# endif // big endian
  }

  /** Remove leading zero bytes from a word
   * @param word	word to be deflated
   * @param bytes	number of zero bytes to remove
   */
  inline static void deflate (word_t& word, unsigned bytes) {
    assert (bytes < sizeof (word_t));
    assert (!bytes ||
	    !(word & ~((word_t (1) << (WORD_T_BIT - CHAR_BIT * bytes)) - 1)));
# if BYTE_ORDER == BIG_ENDIAN
    word <<= CHAR_BIT * bytes;
# endif // big endian
  }

  /** Pad a deflated word with leading zero bytes
   * @param word	word to be inflated
   * @param bytes	number of zero bytes to add
   */
  inline static void inflate (word_t& word, unsigned bytes) {
    assert (bytes < sizeof (word_t));
# if BYTE_ORDER == LITTLE_ENDIAN
    if (bytes)
      word &= (word_t (1) << (WORD_T_BIT - CHAR_BIT * bytes)) - 1;
# elif BYTE_ORDER == BIG_ENDIAN
    word >>= CHAR_BIT * bytes;
# endif
  }

private:
  /** The buffer */
  word_t* myBuf;
  /** Actual size of the buffer in WORD_T_BITs */
  unsigned myAllocated;
  /** Number of bits used of the buffer */
  unsigned myLength;
  /** Amount of WORD_T_BITs to allocate when more memory is needed */
  unsigned myIncrement;
};

/** Class for unpacking bits from a read-only buffer */
class BitUnpacker
{
public:
  /** Constructor for read-only access
   * @param buf		a previously encoded string (read-only)
   */
  explicit BitUnpacker (const word_t* buf) : myBuf (buf), myOffset (0) {}
private:
  /** Copy constructor */
  explicit BitUnpacker (const class BitUnpacker& old);
  /** Assignment operator */
  class BitUnpacker& operator= (const class BitUnpacker& old);
public:
  /** Destructor */
  ~BitUnpacker () {}

  /** Read the number of decoded bits */
  unsigned getNumBits () const { return myOffset; }

  /** Extract data from the encoded string
   * @param bits	length of data in bits
   * @return		the data
   */
  card_t extract (unsigned bits) {
    assert (bits && bits <= CARD_T_BIT);
    unsigned wordpos = myOffset / WORD_T_BIT, bitpos = myOffset % WORD_T_BIT;
    myOffset += bits;

    const card_t mask =
      bits < CARD_T_BIT ? (card_t (1) << bits) - 1 : card_t (-1);
    card_t data = (myBuf[wordpos] >> bitpos) & mask;
    if (bitpos + bits > WORD_T_BIT) {
      bitpos = WORD_T_BIT - bitpos;
      data |= (card_t (myBuf[++wordpos]) << bitpos) & mask;
# if !(BYTE_ORDER == BIG_ENDIAN || BYTE_ORDER == LITTLE_ENDIAN)
      for (bits -= bitpos, bitpos = WORD_T_BIT;
	   bits > WORD_T_BIT;
	   bits -= WORD_T_BIT, bitpos += WORD_T_BIT)
	data |= (card_t (myBuf[++wordpos]) << bitpos) & mask;
# endif
    }

    return data;
  }

  /** Extract a value from the encoded string
   * @param type	type of the value
   * @return		the value
   */
  class Value* extract (const class Type& type);

private:
  /** the encoded bit string */
  const word_t* const myBuf;
  /** offset to the encoded string */
  unsigned myOffset;
};

#endif // BITBUFFER_H_