compress.h

Go to the documentation of this file.

/************************************************************
 **
 ** @file data/compress/compress.h
 **
 ** Copyright (C) 2012  Xpace, LLC.  All rights reserved
 **
 ** www.xpace.net
 **
 **************************************************************/

#ifndef XPACE_COMPRESS_H
#define XPACE_COMPRESS_H

#include "data/compress/list_int.h"
#include "base/decimalfloat.h"

namespace Xpace
{
  template <typename N, typename B = N>
  class CompressibleInt
  {
  public:
    typedef N type;
    typedef CompressibleInt<B> baseType;
    typedef CompressibleInt<SIGN(N), N> diffType;
    typedef CompressibleInt<UNSIGN(N), N> normType;

    CompressibleInt
      (N n = 0)
    {
      num = n;
    }

    CompressibleInt
      (MemBitStream* b,
       BytePool*) :
        num(getVar(b))
    {
    }

    static N min
      ()
    {
      return std::numeric_limits<N>::min();
    }
    static N max
      ()
    {
      return std::numeric_limits<N>::max();
    }

    operator N
      ()
      const
    {
      return num;
    }

    operator CompressibleInt<CHANGE_SIGN(N), B>
      ()
      const
    {
      return static_cast<CHANGE_SIGN(N)>(num);
    }

    bool operator==
      (const CompressibleInt<N, B>& rhs)
    {
      return num == rhs.num;
    }
    bool operator !=
      (const CompressibleInt<N, B>& rhs)
    {
      return num != rhs.num;
    }
    bool operator>
      (const CompressibleInt<N, B>& rhs)
    {
      return num > rhs.num;
    }
    bool operator<
      (const CompressibleInt<N, B>& rhs)
    {
      return num < rhs.num;
    }

    diffType diff
      (const CompressibleInt<N, B>& rhs,
       BytePool* = 0)
      const
    {
      return num - rhs.num;
    }
    N operator-
      (const CompressibleInt<N, B>& rhs)
    {
      return diff(rhs);
    }
    N sum
      (diffType rhs,
       BytePool* = 0)
    {
      return num + rhs;
    }
    CompressibleInt<N, B>& operator+
      (diffType rhs)
    {
      sum(rhs);
      return *this;
    }
    CompressibleInt<N, B>& operator++
      ()
    {
      ++num;
      return *this;
    }
    CompressibleInt<N, B>& operator+=
      (N n)
    {
      num += n;
      return *this;
    }

    template<typename T, typename LIST>
    static uint32 GCF
      (const LIST& list, T minVal = 0);

    static bool writeGCF
      (uint32 gcf,
       MemBitStream* b)
    {
      return b->addVar(gcf - 1);
    }
    static uint32 readGCF
      (MemBitStream* b)
    {
      return 1 + b->getVar<uint32>();
    }

    UNSIGN(N) operator/
      (uint d)
      const
    {
      return static_cast<UNSIGN(N)>(num) / d;
    }

    size_t bitsNeeded
      ()
      const
    {
      return Xpace::bitsNeeded(num);
    }

    bool addBits
      (size_t bits,
       MemBitStream* b)
      const
    {
      return b->addBits(bits, num);
    }

    size_t lenVar
      ()
      const
    {
      return MemBitStream::lenVar(num);
    }

    bool addVar
      (MemBitStream* b)
      const
    {
      return b->addVar(num);
    }

    static
    N getBits
      (MemBitStream* b,
       size_t numBits,
       BytePool* = 0)
    {
      return b->getBits<N>(numBits);
    }

    static
    N getVar
      (MemBitStream* b,
       BytePool* = 0)
    {
      return b->getVar<N>();
    }

  private:
    N num;
  };

  // ============================== STRING ====================

  template <typename CH>
  inline
  void readString
    (MemBitStream* b, 
     CH* ch,
     size_t length)
  {
    if (length)
    {
      size_t cs(1 + b->getBits<size_t>(3 + (sizeof(*ch) > 1)));
      for ( ; length--; ++ch)
        *ch = b->getBits<uint>(cs);          
    }
  }

  template <typename STR>
  inline
  void readString
    (MemBitStream* b, 
     STR* str)
  {
    readString(b, str->data, str->length);
  }

  template <typename CH>
  inline
  size_t charSize
    (const CH* str,
     size_t length)
  {
    CH max_ch(0);
    for (size_t i(length); i--; ++str)
      max_ch = std::max(max_ch, *str);
    return Xpace::bitsNeeded(max_ch);
  }

  template <typename CH>
  inline
  size_t stringLen
    (const CH* str,
     size_t len)
  {
    size_t cs(charSize(str, len));
    return MemBitStream::lenVar(len) + 
           3 + 
           len * cs;
  }

  template <typename STR>
  inline
  size_t stringLen
    (const STR& str)
  {
    return stringLen(str.data, str.length);
  }

  template <typename CH>
  inline
  bool writeString
    (const CH* str,
     size_t length,
     MemBitStream* b)
  {
    if (!b->addVar(length))
      return false;
    if (length)
    {
      size_t cs(charSize(str, length));
      if (!b->addBits(3 + (sizeof(*str) > 1), cs - 1))
        return false;

      const CH* ch(str);
      for (size_t i(length); i--; ++ch)
        if (!b->addBits(cs, *ch))
          return false;
    }

    return true;
  }

  template <typename STR>
  inline
  bool writeString
    (const STR& str,
     MemBitStream* b)
  {
    return writeString(str.data, str.length, b);
  }

  template <typename STR>
  class CompressibleString
  {
  public:
    typedef CompressibleString<STR> baseType;
    class diffType;
    typedef diffType normType;

    CompressibleString
      (int = 0) 
    {
    }
      
    CompressibleString
      (const STR& s) :
        str(s)
    {
    }

    CompressibleString
      (MemBitStream* b,
       BytePool* pool) :
        str(pool->allocString<STR>(b->getVar<uint>()))
    {
      readString(b, &str);
    }

    CompressibleString& operator=
      (const STR& s)
    {
      str = s;
      return *this;
    }

    operator const STR&
      ()
      const
    {
      return str;
    }

    const typename STR::charType* data
      ()
      const
    {
      return str.data;
    }

    size_t length
      () 
      const
    {
      return str.length;
    }  

    static STR min
      ()
    {
      return min_str;
    }
    static STR max
      ()
    {
      return max_str;
    }

    bool operator==
      (const CompressibleString<STR>& rhs)
      const
    {
      return str == rhs.str;
    }
    bool operator!=
      (const CompressibleString<STR>& rhs)
      const
    {
      return str != rhs.str;
    }
    bool operator>
      (const CompressibleString<STR>& rhs)
      const
    {
      return str > rhs.str;
    }
    bool operator<
      (const CompressibleString<STR>& rhs)
      const
    {
      return str < rhs.str;
    }

    diffType diff
      (const CompressibleString&,
       BytePool*)
      const;
    diffType operator-
      (const CompressibleString&)
    {
      assert(0);
      return min_str;
    }
    CompressibleString sum
      (const diffType&,
       BytePool*)
      const;
    CompressibleString operator+
      (const diffType&)
    {
      assert(0);
      return min_str;
    }

    CompressibleString& operator+=
      (const CompressibleString&);
    CompressibleString& operator*
      (uint32 rhs)
    {
      rhs = rhs;
      assert(rhs == 1);
      return *this;
    }
    CompressibleString& operator/
      (uint32 rhs)
    {
      rhs = rhs;
      assert(rhs == 1);
      return *this;
    }

    template<typename T, typename LIST>
    static uint32 GCF
      (const LIST& /*list*/, T /*minVal*/ = 0)
    {
      return 1;
    }

    static bool writeGCF
      (uint32,
       MemBitStream*)
    {
      return true;
    }

    static uint32 readGCF
      (MemBitStream*)
    {
      return 1;
    }

    size_t bitsNeeded
      ()
      const
    {
      return 1000000; // TODO; max str is not the biggest str
    }

    bool addBits
      (size_t,
       MemBitStream*)
      const
    {
      assert(0);
      return false;
    }

    size_t lenVar
      ()
      const
    {
      return stringLen(str);
    }

    virtual 
    bool addVar
      (MemBitStream* b)
      const
    {
      return writeString(str, b);
    }

    static
    CompressibleString<STR> getBits
      (MemBitStream* /*b*/,
       size_t /*numBits*/)
    {
      assert(0);
      return CompressibleString();
    }

    static
    CompressibleString<STR> getVar
      (MemBitStream* b,
       BytePool* pool)
    {            
      return CompressibleString(b, pool);
    }

    friend uint qHash
      (const CompressibleString& cs)
    {
      return qHash(QByteArray(reinterpret_cast<const char*>(cs.str.data), int(sizeof(typename STR::charType) * cs.str.length)));
    }

  private:
    STR str;
    static STR min_str, max_str;
  };

  template <typename STR>
  class CompressibleString<STR>::diffType
  {
    friend class CompressibleString<STR>;
  public:
    typedef diffType normType;

    diffType
      (int = 0) :
        prefix(0)
    {
    }
    
    diffType
      (MemBitStream* b,
       BytePool* pool) :
        prefix(b->getVar<uint>()),
        str(b, pool)
    {
    }

    static diffType min
      ()
    {
      return diffType();
    }

    static diffType max
      ()
    {
      diffType ret;
      ret.prefix = ~0;
      ret.str = CompressibleString<STR>::max();
      return ret;
    }

    bool operator==
      (const diffType& rhs)
      const
    {
      return (prefix == rhs.prefix) && (str == rhs.str);
    }
    bool operator!=
      (const diffType& rhs)
      const
    {
      return !(*this == rhs);
    }
    bool operator>
      (const diffType& rhs)
      const
    {
      if (prefix > rhs.prefix)
        return true;
      if (prefix < rhs.prefix)
        return false;
      return str > rhs.str;
    }
    bool operator<
      (const diffType& rhs)
      const
    {
      if (prefix < rhs.prefix)
        return true;
      if (prefix > rhs.prefix)
        return false;
      return str < rhs.str;
    }

    diffType& operator=
      (const STR& s)
    {
      str = s;
      prefix = 0;
      return *this;
    }

    const diffType& operator*
      (uint32 rhs)
      const
    {
      rhs = rhs;
      assert(rhs == 1);
      return *this;
    }
    const diffType& operator/
      (uint32 rhs)
      const
    {
      rhs = rhs;
      assert(rhs == 1);
      return *this;
    }

    template<typename T, typename LIST>
    static uint32 GCF
      (const LIST& /*list*/, 
       T /*minVal*/ = 0)
    {
      return 1;
    }

    static bool writeGCF
      (uint32,
       MemBitStream*)
    {
      return true;
    }

    static uint32 readGCF
      (MemBitStream*)
    {
      return 1;
    }

    size_t bitsNeeded
      ()
      const
    {
      return 1000000; // TODO; max str is not the biggest str
    }

    bool addBits
      (size_t,
       MemBitStream*)
      const
    {
      assert(0);
      return false;
    }

    size_t lenVar
      ()
      const
    {
      return MemBitStream::lenVar(prefix) + str.lenVar();
    }

    bool addVar
      (MemBitStream* b)
      const
    {
      return b->addVar(prefix) + str.addVar(b);
    }

    static 
    diffType getVar
      (MemBitStream* b,
       BytePool* pool)
    {
      return diffType(b, pool);
    } 

    static
    diffType getBits
      (MemBitStream* b,
       size_t numBits)
    {
      assert(0);
      return diffType();
    }

    const diffType& diff
      (const diffType&,
       BytePool*)
      const
    {
      return *this;
    }

    const diffType& sum
      (const diffType& rhs,
       BytePool*)
    {
      return rhs;
    }
    
    friend uint qHash
      (const diffType& dt)
    {
      return ::qHash(dt.prefix) + qHash(dt.str);
    }

  private:
    uint prefix;
    CompressibleString<STR> str;
  };

  // ================================ COMPRESS LIST ===========

  template <typename T>
  class CompressList
  {
  public: 
    size_t findLength
      (const std::vector<T>& vals,
       size_t count,
       BytePool* pool = 0);     // pool for temps if Ts aren't self-contained

    void continueEncode
      (const std::vector<T>& vals,
       MemBitStream* b);

    void encode
      (const std::vector<T>& vals,
       size_t count,
       MemBitStream* b,
       BytePool* pool = 0)
    {
      findLength(vals, count, pool);
      continueEncode(vals, b);
    }

    void decode
      (MemBitStream* b,
       std::vector<T>* vals,
       BytePool* pool = 0,    // pool for Ts' content if they aren't self contained 
       size_t maxVals = ~0);  // maximum number of values to decode

  private:
    iList<T> vals_list;
    std::vector<typename T::diffType> deltas;
    iList<typename T::diffType> deltas_list;

    // communication from findLength to continueEncode
    bool is_single;
    size_t vals_len, deltas_len;
  };

  class FloatList
  {
  public:
    FloatList
      (uint precision = ~0);

    void encode
      (const std::vector<DecimalFloat>& startVals,
       size_t count,
       MemBitStream* b);

    void decode
      (MemBitStream* b,
       std::vector<DecimalFloat>* vals);

  private:
    const uint precision;
    std::vector<CompressibleInt<int64> > ints;
    CompressList<CompressibleInt<int64> > int_list;
  };


  // ==========================================================
  // ==========================================================
  // ==========================================================

  // ================================ COMPRESS LIST ===========

  template<typename T>
  inline
  size_t CompressList<T>::findLength
    (const std::vector<T>& vals,
     size_t count,    
     BytePool* pool) 
  {
    if (count == 1)
    {
      is_single = true;
      return vals.front().lenVar();
    }

    is_single = false;

    vals_list.set(vals, count, pool);
    vals_len = vals_list.getLen();

    deltas.clear();
    for (typename std::vector<T>::const_iterator v(vals.begin()); ++v != vals.begin() + count; )
      deltas.push_back(v->diff(*(v - 1), pool));
    deltas_list.set(deltas, count - 1, pool);

    deltas_len = MemBitStream::lenVar(vals[0]) + deltas_list.getLen();

    return std::min(vals_len, deltas_len);
  }

  template<typename T>
  inline
  void CompressList<T>::continueEncode
    (const std::vector<T>& vals,
     MemBitStream* b)
  {
    if (is_single)
    {
      #if SHOW_STATS
      _is_delta = false;
      #endif

      b->addBit(0);
      vals.front().addVar(b);
    }

    else
    {
      #if SHOW_STATS
      _is_delta = (deltas_len < vals_len);
      #endif

      if (vals_len <= deltas_len)
      {
        b->addBit(0);
        vals_list.encode(b);
      }
      else
      {
        b->addBit(1);
        vals.front().addVar(b);
        deltas_list.encode(b);
      }
    }
  }

  template<typename T>
  inline
  void CompressList<T>::decode
    (MemBitStream* b,
     std::vector<T>* vals,
     BytePool* pool,
     size_t maxVals) 
  {
    if (b->getBit())
    {
      vals->push_back(T::getVar(b, pool));
      deltas.clear();
      if (!INVALID(maxVals))
        --maxVals;
      deltas_list.decode(b, pool, &deltas, maxVals);
      for (typename std::vector<typename T::diffType>::const_iterator d(deltas.begin()); d != deltas.end(); ++d)
        vals->push_back(vals->back().sum(*d, pool));
    }
    else
      vals_list.decode(b, pool, vals, maxVals);
  }

  // ================================ GCF =====================

  // static
  template <typename N, typename B>
  template<typename T, typename LIST>
  inline
  uint32 CompressibleInt<N, B>::GCF(const LIST& list, T minVal)
  {
    auto it(list.begin());
    while (*it == minVal)
      if (++it == list.end())
        return 1;
    
    std::vector<uint32> factors;
    typename T::normType n(*it - minVal);
    static uint32 primes[] = { 2u, 3u, 5u, 7u, 11u, 13u, 17u, 19u, 23u, 29u, 31u, 37u, 41u, 
                               43u, 47u, 53u, 59u, 61u, 67u, 71u, 73u, 79u, 83u, 89u, 97u, 
                               ~0u }; 
    for (uint32 *f(primes); (typename T::type(n) > typename T::type(*f)) && (*f != ~0u); )
    {
      divide<typename T::normType> d(n, *f);
      if (d.rem == 0)
      {
        factors.push_back(*f);
        n = d.quot;
      }
      else
        ++f;
    }

    uint32 gcf(1);
    for (std::vector<uint32>::const_iterator f(factors.begin()); f < factors.end(); ++f)
      gcf *= *f;

    if (gcf > 1)
      for (it = list.begin(); ++it != list.end(); )
      {
        if (*it == *(it - 1))
          continue;

        n = *it - minVal;
        for (std::vector<uint32>::iterator f(factors.begin()); f < factors.end(); ++f)
        {
          divide<typename T::normType> d(n, *f);
          if (d.rem == 0)
            n = d.quot;
          else
          {
            if ((gcf /= *f) == 1)
              return 1;
            *f = 1;   
          }
        }
    }

    return gcf;
  }

  // ================================ COMPRESS STRING =========


  template <typename STR>
  typename CompressibleString<STR>::diffType CompressibleString<STR>::diff
    (const CompressibleString<STR>& rhs,
     BytePool* pool)
    const
  {
    diffType result;

    typename STR::charType *l(str.data), *r(rhs.str.data);
    size_t len(std::min(str.length, rhs.str.length));
    for (result.prefix = 0; len -- && (*l == *r); ++l, ++r)
      ++result.prefix;

    typename STR::charType* d(result.str.str.data = reinterpret_cast<typename STR::charType*>(pool->alloc(sizeof(typename STR::charType) * (result.str.str.length = str.length - result.prefix))));

    while (l < str.data + str.length)
      *d++ = *l++;

    assert(ptrdiff_t(result.str.str.length) == d - result.str.str.data);

    return result;
  }

  template <typename STR>
  CompressibleString<STR> CompressibleString<STR>::sum
    (const diffType& rhs,
     BytePool* pool)
    const
  {
    CompressibleString<STR> result;
    result.str.length = rhs.prefix + rhs.str.str.length;
    result.str.data = reinterpret_cast<typename STR::charType*>(pool->alloc(sizeof(typename STR::charType) * result.str.length));

    typename STR::charType* d(result.str.data);

    typename STR::charType *l(str.data);
    for (size_t prefix(rhs.prefix); prefix--; )
      *d++ = *l++;

    typename STR::charType *r(rhs.str.str.data);
    for (size_t body(rhs.str.str.length); body--; )
      *d++ = *r++;

    return result;
  }  
}

#endif