// 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&); // copy constructor lz77_buffer_kernel_2& operator=(lz77_buffer_kernel_2&); // assignment operator }; // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- // member function definitions // ---------------------------------------------------------------------------------------- // ---------------------------------------------------------------------------------------- template < typename sliding_buffer > lz77_buffer_kernel_2:: 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:: ~lz77_buffer_kernel_2 ( ) { delete [] nodes; delete [] hash_table; delete [] id_table; } // ---------------------------------------------------------------------------------------- template < typename sliding_buffer > void lz77_buffer_kernel_2:: 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:: 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:: 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:: 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_