BWTencoder.h

#pragma once


#include <libutl/ArithmeticEncoder.h>


UTL_NS_BEGIN;


class BWTencoder : public Encoder
{
    UTL_CLASS_DECL(BWTencoder, Encoder);

public:
    BWTencoder(uint_t mode, Stream* stream, bool owner = true, uint_t blockSize = KB(256))
    {
        init();
        start(mode, stream, owner, blockSize);
    }

    virtual size_t decode(byte_t* block, size_t num);

    virtual size_t encode(const byte_t* block, size_t num);

    void start(uint_t mode, Stream* stream, bool owner = true, uint_t blockSize = KB(256));

protected:
    virtual void clear();
    virtual void finishEncoding();

private:
    void init();
    void
    deInit()
    {
        close();
    }
    void clearSelf();
    // transform
    void doTransform();
    void undoTransform(byte_t* block);
    // sort
    inline int compare(uint_t i1, uint_t i2, uint_t depth);
    void insertionSort(uint_t begin, uint_t end);
    uint_t medianOfThree(uint_t l, uint_t m, uint_t h, uint_t depth);
    void multiKeyInsertionSort(uint_t begin, uint_t end, uint_t depth);
    void multiKeyQuickSort(uint_t begin, uint_t end, uint_t depth);
    void quickSort(uint_t begin, uint_t end, uint_t depth);
    void stripe();
    inline void swap(uint_t i, uint_t j);
    inline void swap(uint_t i, uint_t j, uint_t n);
    // mtf encoder
    void mtfEncodeBlock();
    void mtfDecodeBlock();
    void mtfEncodeSymbol(uint_t symbol);
    uint_t mtfDecodeSymbol();
    void mtfEncodeRandomWord(uint_t w);
    uint_t mtfDecodeRandomWord();
    void mtfEncodeRandom(uint_t symbol);
    uint_t mtfDecodeRandom();
    void mtfEncodeZeroes();
// debug
#ifdef DEBUG
    void printBlock(uint_t begin = 0, uint_t end = uint_t_max, uint_t numBytes = 32);
#endif
    // sort
    uint_t* _ptr;
    uint_t* _freq;
    uint32_t* _stripe;
    // mtf
    ArithmeticEncoder _A;
    ArithContext* _H[9];
    uint_t _numZeroes;
    uint_t _pos[256];
    // general
    byte_t* _block;
    uint_t _blockSize;
    uint_t _origin;
};


void
BWTencoder::swap(uint_t i, uint_t j)
{
    uint_t tmp = _ptr[i];
    _ptr[i] = _ptr[j];
    _ptr[j] = tmp;
}


void
BWTencoder::swap(uint_t i, uint_t j, uint_t n)
{
    uint_t* pi = _ptr + i;
    uint_t* pj = _ptr + j;
    uint_t* piLim = pi + n;
    uint_t tmp;
    while (pi < piLim)
    {
        tmp = *pi;
        *pi = *pj;
        *pj = tmp;
        pi++;
        pj++;
    }
}


UTL_NS_END;