rangecoder.hh

Go to the documentation of this file.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/*                                                                           */
/*  This file is part of the library KASKADE 7                               */
/*  https://www.zib.de/research/projects/kaskade7-finite-element-toolbox     */
/*                                                                           */
/*  Copyright (C) 2002-2015 Zuse Institute Berlin                            */
/*                                                                           */
/*  KASKADE 7 is distributed under the terms of the ZIB Academic License.    */
/*    see $KASKADE/academic.txt                                              */
/*                                                                           */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef RANGECODER_HH
#define RANGECODER_HH
 
#include <algorithm>
#include <cassert>
#include <exception>
#include <ios>
#include <limits>
#include <numeric>
#include <vector>
 
 
template <class UInt>
class RangeCoder
{
protected:
  // The number of binary digits in our unsigned integral type UInt.
  static int  const digits = std::numeric_limits<UInt>::digits;
 
  // Mask for shifting of ranges during normalization. All numbers
  // smaller than top have 8 zero leading bits.
  //
  // Smaller value of top, e.g. 1 << digits-16, would allow to shift
  // the range by a larger amount and output short's instead of char's
  // for improved performance. A dawback of this is that bottom needs
  // to be decreased as well, which leads to a small maxRange and
  // hence a low resolution of the alphabet's probability table.
  static UInt const top    = static_cast<UInt>(1) << (digits-8);
 
  // The smallest value of range that is possible. The class invariant
  // is range>=bottom. In contrast to top, the shift of bottom does
  // not need to be a multiple of 8. Smaller values of bottom lead to
  // a lower resolution of the alphabet's probability table (and hence
  // a worse approximation of symbol probabilities, in particular for
  // very different probabilities), however, it also saves space due
  // to fewer carry compensations.
  static UInt const bottom = static_cast<UInt>(1) << (digits-16);
  
public:
  static const UInt maxRange = bottom;
 
  size_t size() const {
    return count;
  }
 
protected:
  RangeCoder()
    : low(0), range(std::numeric_limits<UInt>::max()), count(0)
  {
    assert(std::numeric_limits<UInt>::is_specialized);
    assert(!std::numeric_limits<UInt>::is_signed);
    assert(digits > 16);
  }
  
  UInt low, range;
  size_t count;
};
 
//---------------------------------------------------------------------
 
template <class UInt>
class RangeEncoder:public RangeCoder<UInt>
{
  static UInt const bottom = RangeCoder<UInt>::bottom;
  static UInt const top = RangeCoder<UInt>::top;
  static UInt const digits = RangeCoder<UInt>::digits;
  
public:
  static UInt const maxRange = RangeCoder<UInt>::maxRange;
 
  RangeEncoder(std::ostream& out_)
    : out(out_), fill(0)
  {}
  
  ~RangeEncoder() {
    for(int i=0; i<digits/8; i++) 
      put();
    out.write((char const*)buf,fill);
  }
 
  void push(std::pair<UInt,UInt> s, UInt totalRange) 
  {
    // Check parameters.
    assert(s.first<s.second);
    assert(totalRange <= maxRange);
    
    UInt& range = this->range;
    UInt& low = this->low;
 
    // Check class invariant
    assert(range >= bottom);
    assert(range-1 <= std::numeric_limits<UInt>::max()-low);
    
    
    range /= totalRange;
    low += s.first*range;
    range *= s.second-s.first;
 
    // Perform range normalization
    while ( (low^(low+range)) < top
            || (range<bottom && ((range= -low & (bottom-1)),true)) ) 
      put();       // Output of highest byte and shifting of range
    
    // Check class invariant
    assert(range >= bottom);
    assert(range-1 <= std::numeric_limits<UInt>::max()-low);
  }
 
private:
  std::ostream& out;
 
  // Putting one char at a time into the std::ostream is quite
  // inefficient. We store the bytes in a small buffer and feed the
  // buffer into the ostream once it is full. A buffer size of 64
  // seems to be a good compromise between performance improvement and
  // memory consumption.
  static int const bufsize = 64;
  unsigned char buf[bufsize];
  int fill;  
 
  void put() {
    UInt& range = this->range;
    UInt& low = this->low;
 
    if (fill==bufsize) {
      out.write((char const*)buf,bufsize);
      if (!out)
        throw std::ios_base::failure("write error");
      fill = 0;
      this->count += bufsize;
    }
 
    // Store eight most significant bits (top) in stream buffer.
    buf[fill] = low >> (digits-8);
    ++fill;
    
    // shift window
    range <<= 8;
    low <<= 8;
  }
};
 
//---------------------------------------------------------------------
 
template <class UInt>
class RangeDecoder:public RangeCoder<UInt>
{
  static UInt const bottom = RangeCoder<UInt>::bottom;
  static UInt const top = RangeCoder<UInt>::top;
  static UInt const digits = RangeCoder<UInt>::digits;
 
  UInt code;
  std::istream& in;
 
public:
  static UInt const maxRange = RangeCoder<UInt>::maxRange;
 
  RangeDecoder(std::istream& input_)
    : code(0), in(input_)
  {
    // Throw ios_base::failure if end of stream is reached.
    in.exceptions(std::ios_base::eofbit | in.exceptions());
    
    // Fill range
    for(int i=0; i<digits/8; i++) {
      code = (code << 8) | in.get();
      if (!in) throw std::ios_base::failure("read error");
      ++this->count;
    }
  }
 
  UInt front(UInt totalRange) const {
    UInt const& range = this->range;
    UInt const& low = this->low;
 
    return (code-low)/(range/totalRange);
  }
 
  void pop(std::pair<UInt,UInt> s, UInt totalRange) {
    UInt& range = this->range;
    UInt& low = this->low;
 
    assert(s.first<=front(totalRange)
           && front(totalRange)<s.second);
    
    range /= totalRange;
    low += s.first*range;
    range *= s.second-s.first;
 
    // Perform range normalization
    while ( (low^(low+range))<top
            || (range<bottom && ((range= -low & (bottom-1)),true)) ) {
      code = code<<8 | in.get();
      range <<= 8;
      low <<= 8;
      ++this->count;
    }
  }
};
 
 
//---------------------------------------------------------------------
//---------------------------------------------------------------------
 
template <class UInt>
class Alphabet {
public:
  template <class InIter>
  Alphabet(InIter first, InIter last)
    : cumFreq(std::distance(first,last)+1) 
  {
    cumFreq[0] = 0;
    std::partial_sum(first,last,cumFreq.begin()+1,std::plus<UInt>());
  }
 
  template <class InIter>
  void update(InIter first, InIter last) 
  {
    assert(std::distance(first,last)==size()); // check that all symbols are covered
    assert(std::find(first,last,0)==last);     // check that all frequencies are greater than zero
    std::partial_sum(first,last,cumFreq.begin()+1,std::plus<UInt>()); // compute cumulative distribution
  }
 
  UInt totalRange() const 
  {
    return cumFreq.back();
  }
 
  UInt size() const 
  {
    return cumFreq.size()-1;
  }
 
  UInt symbol(UInt value) const 
  {
    typename std::vector<UInt>::const_iterator i
      = std::upper_bound(cumFreq.begin(),cumFreq.end(), value);
    assert(i==cumFreq.end() || *i>value);
    assert(i!=cumFreq.begin());
    return i-cumFreq.begin()-1;
  }
 
  std::pair<UInt,UInt> range(UInt symbol) const 
  {
    assert(symbol<size());
    return std::make_pair(cumFreq[symbol],cumFreq[symbol+1]);
  }
  
 
private:
  // cumulated frequencies for the symbols
  std::vector<UInt> cumFreq;
};
 
//---------------------------------------------------------------------
//---------------------------------------------------------------------
 
template <class UInt, class Symbol>
void encodeSymbol(RangeEncoder<UInt>& encoder, Alphabet<UInt> const& alphabet,
                  Symbol const& s) {
  encoder.push(alphabet.range(s),alphabet.totalRange());
}
 
 
template <class UInt>
UInt decodeSymbol(RangeDecoder<UInt>& decoder, Alphabet<UInt> const& alphabet) {
  UInt s = alphabet.symbol(decoder.front(alphabet.totalRange()));
  decoder.pop(alphabet.range(s),alphabet.totalRange());
  return s;
}
 
//---------------------------------------------------------------------
//---------------------------------------------------------------------
 
 
 
#endif