Logo Search packages:      
Sourcecode: maria version File versions

BitBuffer.h

Go to the documentation of this file.
// 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 Mäkelä (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
00082 typedef unsigned char word_t;
# endif // BYTE_ORDER
/** Length of the machine word in bits */
00085 # define WORD_T_BIT (CHAR_BIT * sizeof (word_t))

/** Buffer for packing bits */
00088 class BitPacker
{
public:
  /** Constructor
   * @param increment   Buffer allocation granularity (in WORD_T_BITs)
   */
00094   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 */
00103   ~BitPacker () { delete[] myBuf; }

  /** Append data to the buffer
   * @param data  Data to be appended
   * @param bits  Length of data in bits
   */
00109   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
   */
00143   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 */
00162   void clear () {
    myLength = 0;
    memset (myBuf, 0, myAllocated * sizeof *myBuf);
  }
  /** Determine whether the buffer is empty */
00167   bool empty () const { return myLength == 0; }
  /** Determine the length of the encoded data in bits */
00169   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
   */
00174   unsigned getNumBlocks (unsigned size) const {
    return (myLength + size - 1) / size;
  }
  /** Determine the length of the encoded data in bytes */
00178   unsigned getNumBytes () const { return getNumBlocks (CHAR_T_BIT); }
  /** Determine the length of the encoded data in words */
00180   unsigned getNumWords () const { return getNumBlocks (WORD_T_BIT); }

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

  /** Remove leading zero bytes from the last word */
00186   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 */
00195   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
   */
00207   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
   */
00220   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 */
00232   word_t* myBuf;
  /** Actual size of the buffer in WORD_T_BITs */
00234   unsigned myAllocated;
  /** Number of bits used of the buffer */
00236   unsigned myLength;
  /** Amount of WORD_T_BITs to allocate when more memory is needed */
00238   unsigned myIncrement;
};

/** Class for unpacking bits from a read-only buffer */
00242 class BitUnpacker
{
public:
  /** Constructor for read-only access
   * @param buf         a previously encoded string (read-only)
   */
00248   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 */
00256   ~BitUnpacker () {}

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

  /** Extract data from the encoded string
   * @param bits  length of data in bits
   * @return            the data
   */
00265   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 */
00295   const word_t* const myBuf;
  /** offset to the encoded string */
00297   unsigned myOffset;
};

#endif // BITBUFFER_H_

Generated by  Doxygen 1.6.0   Back to index