summaryrefslogtreecommitdiffstats
path: root/ml/dlib/dlib/lz77_buffer
diff options
context:
space:
mode:
Diffstat (limited to 'ml/dlib/dlib/lz77_buffer')
-rw-r--r--ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_1.h263
-rw-r--r--ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_2.h504
-rw-r--r--ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_abstract.h210
-rw-r--r--ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_c.h169
4 files changed, 1146 insertions, 0 deletions
diff --git a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_1.h b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_1.h
new file mode 100644
index 000000000..b93f0628d
--- /dev/null
+++ b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_1.h
@@ -0,0 +1,263 @@
+// 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_1_
+#define DLIB_LZ77_BUFFER_KERNEl_1_
+
+#include "lz77_buffer_kernel_abstract.h"
+#include "../algs.h"
+
+
+
+namespace dlib
+{
+
+ template <
+ typename sliding_buffer
+ >
+ class lz77_buffer_kernel_1
+ {
+ /*!
+ REQUIREMENTS ON sliding_buffer
+ sliding_buffer must be an implementation of sliding_buffer/sliding_buffer_kernel_abstract.h
+
+ 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
+
+
+ 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]
+ !*/
+
+ public:
+
+ lz77_buffer_kernel_1 (
+ unsigned long total_limit_,
+ unsigned long lookahead_limit_
+ );
+
+ virtual ~lz77_buffer_kernel_1 (
+ ) {}
+
+ 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 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)
+ !*/
+ {
+ unsigned long temp = history_size+N;
+ buffer.rotate_left(N);
+ lookahead_size -= N;
+ if (temp < history_limit)
+ history_size = temp;
+ else
+ history_size = history_limit;
+ }
+
+
+ // member data
+ sliding_buffer buffer;
+ unsigned long lookahead_limit;
+ unsigned long history_limit;
+
+
+ unsigned long lookahead_size;
+ unsigned long history_size;
+
+
+ // restricted functions
+ lz77_buffer_kernel_1(lz77_buffer_kernel_1<sliding_buffer>&); // copy constructor
+ lz77_buffer_kernel_1<sliding_buffer>& operator=(lz77_buffer_kernel_1<sliding_buffer>&); // assignment operator
+ };
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename sliding_buffer
+ >
+ lz77_buffer_kernel_1<sliding_buffer>::
+ lz77_buffer_kernel_1 (
+ 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_;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename sliding_buffer
+ >
+ void lz77_buffer_kernel_1<sliding_buffer>::
+ clear(
+ )
+ {
+ lookahead_size = 0;
+ history_size = 0;
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename sliding_buffer
+ >
+ void lz77_buffer_kernel_1<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_1<sliding_buffer>::
+ find_match (
+ unsigned long& index,
+ unsigned long& length,
+ unsigned long min_match_length
+ )
+ {
+ unsigned long hpos = history_size; // current position in the history buffer
+ unsigned long lpos = 0; // current position in the lookahead buffer
+
+ 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
+
+ // try to find a match
+ while (hpos != 0)
+ {
+ --hpos;
+ // if we are finding a match
+ if (history_buffer(hpos) == lookahead_buffer(lpos))
+ {
+ ++lpos;
+ // if we have found a match that is as long as the lookahead buffer
+ // then we are done
+ if (lpos == lookahead_size)
+ break;
+ }
+ // else if we found the end of a match
+ else if (lpos > 0)
+ {
+ // if this match is longer than the last match we saw
+ if (lpos > match_length)
+ {
+ match_length = lpos;
+ match_index = hpos + lpos;
+ }
+ lpos = 0;
+ }
+ } // while (hpos != 0)
+
+ // if we found a match at the end of the loop that is greater than
+ // the match in match_index
+ if (lpos > match_length)
+ {
+ match_length = lpos;
+ match_index = hpos + lpos - 1;
+ }
+
+
+ // 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_1_
+
diff --git a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_2.h b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_2.h
new file mode 100644
index 000000000..f8d332784
--- /dev/null
+++ b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_2.h
@@ -0,0 +1,504 @@
+// 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_
+
diff --git a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_abstract.h b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_abstract.h
new file mode 100644
index 000000000..942b4e3c2
--- /dev/null
+++ b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_abstract.h
@@ -0,0 +1,210 @@
+// Copyright (C) 2004 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#undef DLIB_LZ77_BUFFER_KERNEl_ABSTRACT_
+#ifdef DLIB_LZ77_BUFFER_KERNEl_ABSTRACT_
+
+#include "../algs.h"
+
+namespace dlib
+{
+
+ class lz77_buffer
+ {
+ /*!
+ INITIAL VALUE
+ get_history_buffer_limit() == defined by constructor arguments
+ get_lookahead_buffer_limit() == defined by constructor arguments
+ get_history_buffer_size() == 0
+ get_lookahead_buffer_size() == 0
+
+
+ WHAT THIS OBJECT REPRESENTS
+ This object represents a pair of buffers (history and lookahead buffers)
+ used during lz77 style compression.
+
+ It's main function is to search the history buffer for long strings which
+ match the contents (or a part of the contents) of the lookahead buffer.
+
+
+ HISTORY AND LOOKAHEAD BUFFERS
+ The buffers have the following structure:
+ | history buffer | lookahead buffer | <-- contents of buffers
+ | ...9876543210 | 0123456789... | <-- index numbers
+
+ So this means that history_buffer(0) == 'r', history_buffer(1) == 'e'
+ and so on. And lookahead_buffer(0) == 'l', lookahead_buffer(1) == 'o'
+ and so on.
+
+
+ What shift_buffers() does in english:
+ This function just means that the buffers have their contents shifted
+ left by N elements and that elements shifted out of the lookahead buffer
+ go into the history buffer. An example will make it clearer.
+
+ Suppose that we have the following buffers before we apply shift_buffers()
+ history_buffer() == "hey" and
+ lookahead_buffer() == "lookahead buffer"
+ And in the same format as the above diagram it would be
+ | hey | lookahead buffer | <-- contents of buffers
+ | 210 | 0123456789... | <-- index numbers
+
+ Applying shift_buffers(4) will give
+ lookahead_buffer() == "ahead buffer"
+ history_buffer() == "heylook" or "eylook" or "ylook" or "look"
+
+ You might be wondering why the history_buffer can resize itself in
+ such a nondeterministic way. It is just to allow a lot of freedom in the
+ implementations of this object.
+ !*/
+
+ public:
+
+ lz77_buffer (
+ unsigned long total_limit,
+ unsigned long lookahead_limit
+ );
+ /*!
+ requires
+ - 6 < total_limit < 32
+ - 15 < lookahead_limit <= 2^(total_limit-2)
+ ensures
+ - #*this is properly initialized
+ - #get_history_buffer_limit() == 2^total_limit - lookahead_limit
+ - #get_lookahead_buffer_limit() == lookahead_limit
+ throws
+ - std::bad_alloc
+ !*/
+
+ virtual ~lz77_buffer (
+ );
+ /*!
+ ensures
+ - any resources associated with *this have been released
+ !*/
+
+ void clear(
+ );
+ /*!
+ ensures
+ - #*this has its initial value
+ throws
+ - std::bad_alloc
+ if this exception is thrown then #*this is unusable
+ until clear() is called and succeeds
+ !*/
+
+ void shift_buffers (
+ unsigned long N
+ );
+ /*!
+ requires
+ - N <= get_lookahead_buffer_size()
+ ensures
+ - #get_lookahead_buffer_size() == get_lookahead_buffer_size() - N
+ - #get_history_buffer_size() >= N
+ - #get_history_buffer_size() <= get_history_buffer_size()+N
+ - #get_history_buffer_size() <= get_history_buffer_limit()
+ - for all i where 0 <= i < N:
+ #history_buffer(N-1-i) == lookahead_buffer(i)
+ - for all i where 0 <= i < #get_history_buffer_size()-N:
+ #history_buffer(N+i) == history_buffer(i)
+ - for all i where 0 <= i < #get_lookahead_buffer_size()
+ #lookahead_buffer(i) == lookahead_buffer(N+i)
+ !*/
+
+ void add (
+ unsigned char symbol
+ );
+ /*!
+ ensures
+ - if (get_lookahead_buffer_size() == get_lookahead_buffer_limit()) then
+ - performs shift_buffers(1)
+ - #lookahead_buffer(get_lookahead_buffer_limit()-1) == symbol
+ - #get_lookahead_buffer_size() == get_lookahead_buffer_size()
+ - else
+ - #lookahead_buffer(get_lookahead_buffer_size()) == symbol
+ - #get_lookahead_buffer_size() == get_lookahead_buffer_size() + 1
+ throws
+ - std::bad_alloc
+ if this exception is thrown then #*this is unusable
+ until clear() is called and succeeds
+ !*/
+
+ void find_match (
+ unsigned long& index,
+ unsigned long& length,
+ unsigned long min_match_length
+ );
+ /*!
+ ensures
+ - if (#length != 0) then
+ - #length >= min_match_length
+ - for all i where 0 <= i < #length:
+ history_buffer(#index-i) == lookahead_buffer(i)
+ - performs shift_buffers(#length)
+ throws
+ - std::bad_alloc
+ if this exception is thrown then #*this is unusable
+ until clear() is called and succeeds
+ !*/
+
+ unsigned long get_history_buffer_limit (
+ ) const;
+ /*!
+ ensures
+ - returns the max number of symbols that can fit in the history buffer
+ !*/
+
+ unsigned long get_lookahead_buffer_limit (
+ ) const;
+ /*!
+ ensures
+ - returns the max number of symbols that can fit in the lookahead buffer
+ !*/
+
+ unsigned long get_history_buffer_size (
+ ) const;
+ /*!
+ ensures
+ - returns the number of symbols currently in the history buffer
+ !*/
+
+ unsigned long get_lookahead_buffer_size (
+ ) const;
+ /*!
+ ensures
+ - returns the number of symbols currently in the lookahead buffer
+ !*/
+
+ unsigned char lookahead_buffer (
+ unsigned long index
+ ) const;
+ /*!
+ requires
+ - index < get_lookahead_buffer_size()
+ ensures
+ - returns the symbol in the lookahead buffer at location index
+ !*/
+
+ unsigned char history_buffer (
+ unsigned long index
+ ) const;
+ /*!
+ requires
+ - index < get_history_buffer_size()
+ ensures
+ - returns the symbol in the history buffer at location index
+ !*/
+
+
+ private:
+
+ // restricted functions
+ lz77_buffer(lz77_buffer&); // copy constructor
+ lz77_buffer& operator=(lz77_buffer&); // assignment operator
+
+ };
+}
+
+#endif // DLIB_LZ77_BUFFER_KERNEl_ABSTRACT_
+
diff --git a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_c.h b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_c.h
new file mode 100644
index 000000000..704763ad1
--- /dev/null
+++ b/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_c.h
@@ -0,0 +1,169 @@
+// Copyright (C) 2003 Davis E. King (davis@dlib.net)
+// License: Boost Software License See LICENSE.txt for the full license.
+#ifndef DLIB_LZ77_BUFFER_KERNEl_C_
+#define DLIB_LZ77_BUFFER_KERNEl_C_
+
+#include "lz77_buffer_kernel_abstract.h"
+#include "../algs.h"
+#include "../assert.h"
+#include <iostream>
+
+namespace dlib
+{
+
+ template <
+ typename lz77_base
+ >
+ class lz77_buffer_kernel_c : public lz77_base
+ {
+
+ public:
+ lz77_buffer_kernel_c (
+ unsigned long total_limit,
+ unsigned long lookahead_limit
+ );
+
+ unsigned char lookahead_buffer (
+ unsigned long index
+ ) const;
+
+ unsigned char history_buffer (
+ unsigned long index
+ ) const;
+
+ void shift_buffers (
+ unsigned long N
+ );
+
+
+
+ unsigned long make_safe (
+ unsigned long total_limit,
+ unsigned long lookahead_limit
+ )
+ /*!
+ ensures
+ - if ( 6 < total_limit < 32 &&
+ 15 < lookahead_limit <= 2^(total_limit-2)
+ ) then
+ - returns total_limit
+ - else
+ - throws due to failed CASSERT
+ !*/
+ {
+ unsigned long exp_size = (total_limit!=0)?total_limit-2:0;
+ unsigned long two_pow_total_limit_minus_2 = 1;
+ while (exp_size != 0)
+ {
+ --exp_size;
+ two_pow_total_limit_minus_2 <<= 1;
+ }
+
+ // make sure requires clause is not broken
+ DLIB_CASSERT( 6 < total_limit && total_limit < 32 &&
+ 15 < lookahead_limit && lookahead_limit <= two_pow_total_limit_minus_2,
+ "\tlz77_buffer::lz77_buffer(unsigned long,unsigned long)"
+ << "\n\ttotal_limit must be in the range 7 to 31 and \n\tlookahead_limit in the range 15 to 2^(total_limit-2)"
+ << "\n\tthis: " << this
+ << "\n\ttotal_limit: " << total_limit
+ << "\n\tlookahead_limit: " << lookahead_limit
+ );
+
+ return total_limit;
+ }
+
+ };
+
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+ // member function definitions
+// ----------------------------------------------------------------------------------------
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename lz77_base
+ >
+ void lz77_buffer_kernel_c<lz77_base>::
+ shift_buffers (
+ unsigned long N
+ )
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( N <= this->get_lookahead_buffer_size(),
+ "\tvoid lz77_buffer::shift_buffers(unsigned long)"
+ << "\n\tN must be <= the number of chars in the lookahead buffer"
+ << "\n\tthis: " << this
+ << "\n\tget_lookahead_buffer_size(): " << this->get_lookahead_buffer_size()
+ << "\n\tN: " << N
+ );
+
+ // call the real function
+ lz77_base::shift_buffers(N);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename lz77_base
+ >
+ unsigned char lz77_buffer_kernel_c<lz77_base>::
+ history_buffer (
+ unsigned long index
+ ) const
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( index < this->get_history_buffer_size(),
+ "\tunsigned char lz77_buffer::history_buffer(unsigned long) const"
+ << "\n\tindex must be in the range 0 to get_history_buffer_size()-1"
+ << "\n\tthis: " << this
+ << "\n\tget_history_buffer_size(): " << this->get_history_buffer_size()
+ << "\n\tindex: " << index
+ );
+
+ // call the real function
+ return lz77_base::history_buffer(index);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename lz77_base
+ >
+ unsigned char lz77_buffer_kernel_c<lz77_base>::
+ lookahead_buffer (
+ unsigned long index
+ ) const
+ {
+ // make sure requires clause is not broken
+ DLIB_CASSERT( index < this->get_lookahead_buffer_size(),
+ "\tunsigned char lz77_buffer::lookahead_buffer(unsigned long) const"
+ << "\n\tindex must be in the range 0 to get_lookahead_buffer_size()-1"
+ << "\n\tthis: " << this
+ << "\n\tget_lookahead_buffer_size(): " << this->get_lookahead_buffer_size()
+ << "\n\tindex: " << index
+ );
+
+ // call the real function
+ return lz77_base::lookahead_buffer(index);
+ }
+
+// ----------------------------------------------------------------------------------------
+
+ template <
+ typename lz77_base
+ >
+ lz77_buffer_kernel_c<lz77_base>::
+ lz77_buffer_kernel_c (
+ unsigned long total_limit,
+ unsigned long lookahead_limit
+ ) :
+ lz77_base(make_safe(total_limit,lookahead_limit),lookahead_limit)
+ {
+ }
+
+// ----------------------------------------------------------------------------------------
+
+}
+
+#endif // DLIB_LZ77_BUFFER_KERNEl_C_
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-02 11:55:25 +0000