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, 0 insertions, 1146 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
deleted file mode 100644
index b93f0628d..000000000
--- a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_1.h
+++ /dev/null
@@ -1,263 +0,0 @@
-// 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
deleted file mode 100644
index f8d332784..000000000
--- a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_2.h
+++ /dev/null
@@ -1,504 +0,0 @@
-// 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
deleted file mode 100644
index 942b4e3c2..000000000
--- a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_abstract.h
+++ /dev/null
@@ -1,210 +0,0 @@
-// 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
deleted file mode 100644
index 704763ad1..000000000
--- a/ml/dlib/dlib/lz77_buffer/lz77_buffer_kernel_c.h
+++ /dev/null
@@ -1,169 +0,0 @@
-// 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-25 20:11:06 +0000