path: root/ml/dlib/dlib/lzp_buffer/lzp_buffer_kernel_2.h

// Copyright (C) 2005  Davis E. King (davis@dlib.net)
// License: Boost Software License   See LICENSE.txt for the full license.
#ifndef DLIB_LZP_BUFFER_KERNEl_2_
#define DLIB_LZP_BUFFER_KERNEl_2_

#include "../algs.h"
#include "lzp_buffer_kernel_abstract.h"
#include <new>

namespace dlib
{

    template <
        typename sbuf
        >
    class lzp_buffer_kernel_2 
    {
        /*!
            REQUIREMENTS ON sbuf
                sbuf is an implementation of sliding_buffer/sliding_buffer_kernel_abstract.h
                T == unsigned char

            INITIAL VALUE
                - buffer.size() == the size as defined by the constructor
                - table_size == the number of elements in the table3 and table4 arrays
                - for all i: buffer[i] == 0
                - for all i: table3[i] == buffer.size()
                - for all i: table4[i] == buffer.size()

            CONVENTION
                - table_size == the number of elements in the table3 and table4 arrays
                - size() == buffer.size()
                - operator[](i) == buffer[i]

                

                - last_element == buffer.size()-1

                
                This is LZP with an order-5-4-3 model with context confirmation.
                To save memory the order5 and order3 predictions exist in the same
                table, that is, table3.
        
        !*/

    public:

        explicit lzp_buffer_kernel_2 (
            unsigned long buffer_size           
        );

        virtual ~lzp_buffer_kernel_2 (
        );

        void clear(
        );

        inline void add (
            unsigned char symbol
        );

        inline unsigned long predict_match (
            unsigned long& index
        );

        inline size_t size (
        ) const;

        inline unsigned char operator[] (
            unsigned long index
        ) const;

    private:

        inline bool verify (
            unsigned long index
        ) const
        /*!
            ensures
                - returns true if buffer[index]'s context matches the current context
        !*/
        { 
            if (index+3 < buffer.size())
            {
                if (buffer[0] != buffer[index+1])
                    return false;
                if (buffer[1] != buffer[index+2])
                    return false;
                if (buffer[2] != buffer[index+3])
                    return false;
                return true;
            }
            else
            {
                // just call this a match
                return true;
            }
        }


        sbuf buffer;        
        unsigned long* table3;
        unsigned long* table4;
        unsigned long last_element;
        const unsigned long table_size;

        // restricted functions
        lzp_buffer_kernel_2(const lzp_buffer_kernel_2<sbuf>&);        // copy constructor
        lzp_buffer_kernel_2<sbuf>& operator=(const lzp_buffer_kernel_2<sbuf>&);    // assignment operator

    };      

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------

    template <
        typename sbuf
        >
    lzp_buffer_kernel_2<sbuf>::
    lzp_buffer_kernel_2 (
        unsigned long buffer_size           
    ) :
        table3(0),
        table4(0),
        table_size(65536)
    {
        buffer.set_size(buffer_size);

        table3 = new (std::nothrow) unsigned long[table_size];
        table4 = new (std::nothrow) unsigned long[table_size];

        if (!table3 || !table4)
        {
            if (!table3)
                delete [] table3;
            if (!table4)
                delete [] table4;

            throw std::bad_alloc();
        }
        
        

        for (unsigned long i = 0; i < buffer.size(); ++i)
            buffer[i] = 0;

        for (unsigned long i = 0; i < table_size; ++i)
        {
            table3[i] = buffer.size();
            table4[i] = buffer.size();
        }

        last_element = buffer.size()-1;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename sbuf
        >
    lzp_buffer_kernel_2<sbuf>::
    ~lzp_buffer_kernel_2 (
    )
    {
        delete [] table3;
        delete [] table4;
    }

// ----------------------------------------------------------------------------------------

    template <
        typename sbuf
        >
    void lzp_buffer_kernel_2<sbuf>::
    clear(
    )
    {
        for (unsigned long i = 0; i < buffer.size(); ++i)
            buffer[i] = 0;

        for (unsigned long i = 0; i < table_size; ++i)
        {
            table3[i] = buffer.size();
            table4[i] = buffer.size();
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename sbuf
        >
    void lzp_buffer_kernel_2<sbuf>::
    add (
        unsigned char symbol
    ) 
    { 
        buffer.rotate_left(1); 
        buffer[0] = symbol; 
    }

// ----------------------------------------------------------------------------------------

    template <
        typename sbuf
        >
    unsigned long lzp_buffer_kernel_2<sbuf>::
    predict_match (
        unsigned long& index
    )
    {
        unsigned long temp1 = buffer[0];
        unsigned long temp2 = buffer[1];
        temp2 <<= 8;
        unsigned long temp3 = buffer[2];
        temp3 <<= 16;
        unsigned long temp4 = buffer[3];
        temp4 <<= 24;
        unsigned long temp5 = buffer[4];
        temp5 <<= 12;
        
        unsigned long context1 = temp1|temp2|temp3;    
        unsigned long context2 = context1|temp4;


        const unsigned long i5 = ((temp5|(context2>>20))^context2)&0xFFFF;
        const unsigned long i4 = ((context2>>15)^context2)&0xFFFF;
        const unsigned long i3 = ((context1>>11)^context1)&0xFFFF;
      


        // check the 5-order context's prediction
        if (table3[i5] != buffer.size() && 
            verify(buffer.get_element_index(table3[i5])) )
        {
            index = buffer.get_element_index(table3[i5]);
            if (index > 20)
            {
                // update the prediction for this context
                table3[i3] = buffer.get_element_id(last_element);
                table4[i4] = table3[i3];     
                table3[i5] = table3[i3];
            }
            return 5;
        }
        // check the 4-order context's prediction
        else if (table4[i4] != buffer.size() && 
            verify(buffer.get_element_index(table4[i4])) )
        {
            index = buffer.get_element_index(table4[i4]);
            if (index > 20)
            {
                // update the prediction for this context
                table3[i3] = buffer.get_element_id(last_element);
                table4[i4] = table3[i3];           
                table3[i5] = table3[i3];          
            }
            return 4;
        }
        // check the 3-order context's prediction
        else if (table3[i3] != buffer.size() &&
            verify(buffer.get_element_index(table3[i3])))
        {
            index = buffer.get_element_index(table3[i3]);
            
            if (index > 20)
            {
                // update the prediction for this context
                table3[i3] = buffer.get_element_id(last_element);
                table4[i4] = table3[i3];        
                table3[i5] = table3[i3];             
            }
            return 3;
        } 
        else
        {
            // update the prediction for this context
            table3[i3] = buffer.get_element_id(last_element);
            table4[i4] = table3[i3];            
            table3[i5] = table3[i3];         
            
            return 0;
        }
    }

// ----------------------------------------------------------------------------------------

    template <
        typename sbuf
        >
    size_t lzp_buffer_kernel_2<sbuf>::
    size (
    ) const 
    { 
        return buffer.size(); 
    }

// ----------------------------------------------------------------------------------------

    template <
        typename sbuf
        >
    unsigned char lzp_buffer_kernel_2<sbuf>::
    operator[] (
        unsigned long index
    ) const 
    { 
        return buffer[index]; 
    }

// ----------------------------------------------------------------------------------------

}

#endif // DLIB_LZP_BUFFER_KERNEl_2_