path: root/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_2.h

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

#include "lz77_buffer_kernel_abstract.h"
#include "../algs.h"



namespace dlib
{

    template <
        typename sliding_buffer
        >
    class lz77_buffer_kernel_2 
    {
        /*!
            REQUIREMENTS ON sliding_buffer
                sliding_buffer must be an implementation of sliding_buffer/sliding_buffer_kernel_abstract.h
                and must be instantiated to contain unsigned char data

            INITIAL VALUE
                history_limit == defined by constructor arguments
                lookahead_limit == defined by constructor arguments
                history_size == 0
                lookahead_size == 0
                buffer.size() == history_limit + lookahead_limit
                buffer[i] == 0 for all valid i

                nodes == an array of history_limit-3 nodes
                id_table == an array of buffer.size() pointers
                hash_table == an array of buffer.size() pointers and all are set to 0
                mask == buffer.size() - 1
                next_free_node == 0


            CONVENTION           
                history_limit == get_history_buffer_limit()
                lookahead_limit == get_lookahead_buffer_limit()
                history_size == get_history_buffer_size()
                lookahead_limit == get_lookahead_buffer_size()
                              
                buffer.size() == history_limit + lookahead_limit

                lookahead_buffer(i) == buffer[lookahead_limit-1-i]
                history_buffer(i) == buffer[lookahead_limit+i]


                hash_table[hash(a,b,c,d)] points to the head of a linked list.
                    Each node in this linked list tells the location in the buffer
                    of a string that begins with abcd or a string who's first four
                    letters have the same hash.  The linked list is terminated by a
                    node with a null next pointer.

                hash_table[i] == 0 if there is no linked list for this element of the hash
                    table.

                each node in the hash table is allocated from the array nodes.
                When adding a node to hash_table:
                    if (if all nodes aren't already in the hash_table) then
                    {
                        the next node to use is nodes[next_free_node].                
                    }
                    else
                    {
                        recycle nodes from the hash_table itself.  This works because
                        when we add new nodes we also have to remove nodes.
                    }

                if (there is a node defined with an id of i) then
                {
                    if (id_table[i] != 0) then
                        id_table[i]->next->id == i
                    else
                        hash_table[some_hash]->id == i
                }
        !*/

    public:

        lz77_buffer_kernel_2 (
            unsigned long total_limit_,
            unsigned long lookahead_limit_  
        );

        virtual ~lz77_buffer_kernel_2 (
        );

        void clear(
        );

        void add (
            unsigned char symbol
        );

        void find_match (
            unsigned long& index,
            unsigned long& length,
            unsigned long min_match_length
        );

        inline unsigned long get_history_buffer_limit (
        ) const { return history_limit; }

        inline unsigned long get_lookahead_buffer_limit (
        ) const { return lookahead_limit; }

        inline unsigned long get_history_buffer_size (
        ) const { return history_size; }

        inline unsigned long get_lookahead_buffer_size (
        ) const { return lookahead_size; }

        inline unsigned char lookahead_buffer (
            unsigned long index
        ) const { return buffer[lookahead_limit-1-index]; }

        inline unsigned char history_buffer (
            unsigned long index
        ) const { return buffer[lookahead_limit+index]; }


        inline void shift_buffers (
            unsigned long N
        ) { shift_buffer(N); }

    private:

        inline unsigned long hash (
            unsigned char a,
            unsigned char b,
            unsigned char c,
            unsigned char d
        ) const
        /*!
            ensures
                - returns a hash of the 4 arguments and the hash is in the range
        !*/
        {
            unsigned long B = b << 3;
            unsigned long C = c << 6;
            unsigned long D = d << 9;

            unsigned long temp = a + B;
            temp += C;
            temp += D;

            return (temp&mask); /**/
        }

        void shift_buffer (
            unsigned long N
        );
        /*!
            requires
                - N <= lookahead_size
            ensuers
                - #lookahead_size == lookahead_size - N
                - if (history_size+N < history_limit) then
                    - #history_size == history_size+N
                - else
                    - #history_size == history_limit
                - for all i where 0 <= i < N:
                  #history_buffer(N-1-i) == lookahead_buffer(i)
                - for all i where 0 <= i < #history_size-N:
                  #history_buffer(N+i) == history_buffer(i)
                - for all i where 0 <= i < #lookahead_size
                  #lookahead_buffer(i) == lookahead_buffer(N+i)                
        !*/



        // member data        
        sliding_buffer buffer;
        unsigned long lookahead_limit;
        unsigned long history_limit;

        struct node
        {
            unsigned long id;
            node* next;
        };
        
        node** hash_table;
        node* nodes;
        node** id_table;
        unsigned long next_free_node;
        unsigned long mask;

        unsigned long lookahead_size;
        unsigned long history_size;


        // restricted functions
        lz77_buffer_kernel_2(lz77_buffer_kernel_2<sliding_buffer>&);        // copy constructor
        lz77_buffer_kernel_2<sliding_buffer>& operator=(lz77_buffer_kernel_2<sliding_buffer>&);    // assignment operator
    };   

// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    // member function definitions
// ----------------------------------------------------------------------------------------
// ----------------------------------------------------------------------------------------
    
    template <
        typename sliding_buffer
        >
    lz77_buffer_kernel_2<sliding_buffer>::
    lz77_buffer_kernel_2 (
        unsigned long total_limit_,
        unsigned long lookahead_limit_  
    ) :        
        lookahead_size(0),       
        history_size(0)
    {
        buffer.set_size(total_limit_);
        lookahead_limit = lookahead_limit_;
        history_limit = buffer.size() - lookahead_limit_;

        nodes = new node[history_limit-3];

        try { id_table = new node*[buffer.size()]; }
        catch (...) { delete [] nodes; throw; }

        try { hash_table = new node*[buffer.size()]; }
        catch (...) { delete [] id_table; delete [] nodes; throw; }

        mask = buffer.size()-1;
        next_free_node = 0;

            
        node** start = hash_table;
        node** end = hash_table + buffer.size();
        while (start != end)
        {
            *start = 0;
            ++start;
        }

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

    }

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

    template <
        typename sliding_buffer
        >
    lz77_buffer_kernel_2<sliding_buffer>::
    ~lz77_buffer_kernel_2 (
    )      
    {
        delete [] nodes;
        delete [] hash_table;
        delete [] id_table;
    }

// ----------------------------------------------------------------------------------------
    
    template <
        typename sliding_buffer
        >
    void lz77_buffer_kernel_2<sliding_buffer>::
    clear(
    )
    {
        lookahead_size = 0;
        history_size = 0;
        next_free_node = 0;

        node** start = hash_table;
        node** end = hash_table + buffer.size();
        while (start != end)
        {
            *start = 0;
            ++start;
        }
    }

// ----------------------------------------------------------------------------------------
      
    template <
        typename sliding_buffer
        >      
    void lz77_buffer_kernel_2<sliding_buffer>::
    shift_buffer (
        unsigned long N
    )        
    {
        unsigned long old_history_size = history_size;
        unsigned long temp = history_size+N;    
        unsigned long new_nodes; // the number of nodes to pull from the nodes array
        unsigned long recycled_nodes; // the number of nodes to pull from hash_table
        lookahead_size -= N;
        if (temp <= history_limit)
        {               
            if (history_size <= 3)
            {
                if ((3-history_size) >= N)
                    new_nodes = 0;
                else
                    new_nodes = N - (3-history_size);
            }
            else
            {
                new_nodes = N;
            }
                
            recycled_nodes = 0;
            history_size = temp;
        }
        else
        {
            if (history_size != history_limit)
            {
                new_nodes = history_limit - history_size;
                recycled_nodes = temp - history_limit;
                history_size = history_limit;                
            }
            else
            {
                new_nodes = 0;
                recycled_nodes = N;
            }
        }

        unsigned long i = lookahead_limit + 2;
    
        // if there are any "new" nodes to add to the hash table 
        if (new_nodes != 0)
        {
            unsigned long stop = i - new_nodes;             
            for (; i > stop; --i)
            {
                nodes[next_free_node].next = 0;
                nodes[next_free_node].id = buffer.get_element_id(i);
                id_table[nodes[next_free_node].id] = 0;

                unsigned long new_hash = hash(buffer[i],buffer[i-1],buffer[i-2],buffer[i-3]);

                if (hash_table[new_hash] != 0)
                    id_table[hash_table[new_hash]->id] = &nodes[next_free_node];
                nodes[next_free_node].next = hash_table[new_hash];
                hash_table[new_hash] = &nodes[next_free_node];

                ++next_free_node;                
            }
        } // if (new_nodes != 0)


    
        unsigned long stop = i - recycled_nodes;     
        unsigned long old = old_history_size-1+lookahead_limit;
        for (; i > stop; --i)
        {            
            // find the next node to recycle in hash_table
            node* recycled_node;
            
            
            unsigned long old_id = buffer.get_element_id(old);
            
            // find the node with id old_id  
            if (id_table[old_id] == 0)
            {
                unsigned long old_hash = hash(buffer[old],buffer[old-1],buffer[old-2],buffer[old-3]);
                recycled_node = hash_table[old_hash];

                // fill the gap left by removing this node
                hash_table[old_hash] = recycled_node->next;
            }
            else
            {
                recycled_node = id_table[old_id]->next;

                // fill the gap left by removing this node
                id_table[old_id]->next = recycled_node->next;
            }

            --old;






            recycled_node->next = 0;
            recycled_node->id = buffer.get_element_id(i);
            id_table[recycled_node->id] = 0;

            unsigned long new_hash = hash(buffer[i],buffer[i-1],buffer[i-2],buffer[i-3]);

            if (hash_table[new_hash] != 0) 
                id_table[hash_table[new_hash]->id] = recycled_node;

            recycled_node->next = hash_table[new_hash];
            hash_table[new_hash] = recycled_node;
       
        } // for (; i > stop; --i)




        buffer.rotate_left(N);
    }

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

    template <
        typename sliding_buffer
        >
    void lz77_buffer_kernel_2<sliding_buffer>::
    add (
        unsigned char symbol
    )
    {
        if (lookahead_size == lookahead_limit)
        {
            shift_buffer(1);            
        }
        buffer[lookahead_limit-1-lookahead_size] = symbol;
        ++lookahead_size;
    }

// ----------------------------------------------------------------------------------------
    
    template <
        typename sliding_buffer
        >
    void lz77_buffer_kernel_2<sliding_buffer>::
    find_match (
        unsigned long& index,
        unsigned long& length,
        unsigned long min_match_length
    )
    {
        unsigned long match_length = 0;   // the length of the longest match we find
        unsigned long match_index = 0;    // the index of the longest match we find

 
        const unsigned long hash_value = hash(lookahead_buffer(0),
                                              lookahead_buffer(1),
                                              lookahead_buffer(2),
                                              lookahead_buffer(3)
                                              );


 
        node* temp = hash_table[hash_value];
        while (temp != 0)
        {             
            // current position in the history buffer
            unsigned long hpos = buffer.get_element_index(temp->id)-lookahead_limit;  
            // current position in the lookahead buffer
            unsigned long lpos = 0;             

            // find length of this match
            while (history_buffer(hpos) == lookahead_buffer(lpos))
            {
                ++lpos;
                if (hpos == 0)
                    break;
                --hpos;
                if (lpos == lookahead_size)
                    break;                    
            }

            if (lpos > match_length)
            {
                match_length = lpos;
                match_index = buffer.get_element_index(temp->id)-lookahead_limit;
                // if this is the longest possible match then stop looking
                if (lpos == lookahead_limit)
                    break;
            }
            

            temp = temp->next;
        } // while (temp != 0)




        // if we found a match that was long enough then report it
        if (match_length >= min_match_length)
        {
            shift_buffer(match_length);
            index = match_index;
            length = match_length;
        }
        else
        {
            length = 0;
        }
    }

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

}

#endif // DLIB_LZ77_BUFFER_KERNEl_2_