1 // Copyright (C) 2005  Davis E. King (davis@dlib.net)
2 // License: Boost Software License   See LICENSE.txt for the full license.
3 #ifndef DLIB_LZP_BUFFER_KERNEl_2_
4 #define DLIB_LZP_BUFFER_KERNEl_2_
5 
6 #include "../algs.h"
7 #include "lzp_buffer_kernel_abstract.h"
8 #include <new>
9 
10 namespace dlib
11 {
12 
13     template <
14         typename sbuf
15         >
16     class lzp_buffer_kernel_2
17     {
18         /*!
19             REQUIREMENTS ON sbuf
20                 sbuf is an implementation of sliding_buffer/sliding_buffer_kernel_abstract.h
21                 T == unsigned char
22 
23             INITIAL VALUE
24                 - buffer.size() == the size as defined by the constructor
25                 - table_size == the number of elements in the table3 and table4 arrays
26                 - for all i: buffer[i] == 0
27                 - for all i: table3[i] == buffer.size()
28                 - for all i: table4[i] == buffer.size()
29 
30             CONVENTION
31                 - table_size == the number of elements in the table3 and table4 arrays
32                 - size() == buffer.size()
33                 - operator[](i) == buffer[i]
34 
35 
36 
37                 - last_element == buffer.size()-1
38 
39 
40                 This is LZP with an order-5-4-3 model with context confirmation.
41                 To save memory the order5 and order3 predictions exist in the same
42                 table, that is, table3.
43 
44         !*/
45 
46     public:
47 
48         explicit lzp_buffer_kernel_2 (
49             unsigned long buffer_size
50         );
51 
52         virtual ~lzp_buffer_kernel_2 (
53         );
54 
55         void clear(
56         );
57 
58         inline void add (
59             unsigned char symbol
60         );
61 
62         inline unsigned long predict_match (
63             unsigned long& index
64         );
65 
66         inline size_t size (
67         ) const;
68 
69         inline unsigned char operator[] (
70             unsigned long index
71         ) const;
72 
73     private:
74 
verify(unsigned long index)75         inline bool verify (
76             unsigned long index
77         ) const
78         /*!
79             ensures
80                 - returns true if buffer[index]'s context matches the current context
81         !*/
82         {
83             if (index+3 < buffer.size())
84             {
85                 if (buffer[0] != buffer[index+1])
86                     return false;
87                 if (buffer[1] != buffer[index+2])
88                     return false;
89                 if (buffer[2] != buffer[index+3])
90                     return false;
91                 return true;
92             }
93             else
94             {
95                 // just call this a match
96                 return true;
97             }
98         }
99 
100 
101         sbuf buffer;
102         unsigned long* table3;
103         unsigned long* table4;
104         unsigned long last_element;
105         const unsigned long table_size;
106 
107         // restricted functions
108         lzp_buffer_kernel_2(const lzp_buffer_kernel_2<sbuf>&);        // copy constructor
109         lzp_buffer_kernel_2<sbuf>& operator=(const lzp_buffer_kernel_2<sbuf>&);    // assignment operator
110 
111     };
112 
113 // ----------------------------------------------------------------------------------------
114 // ----------------------------------------------------------------------------------------
115     // member function definitions
116 // ----------------------------------------------------------------------------------------
117 // ----------------------------------------------------------------------------------------
118 
119     template <
120         typename sbuf
121         >
122     lzp_buffer_kernel_2<sbuf>::
lzp_buffer_kernel_2(unsigned long buffer_size)123     lzp_buffer_kernel_2 (
124         unsigned long buffer_size
125     ) :
126         table3(0),
127         table4(0),
128         table_size(65536)
129     {
130         buffer.set_size(buffer_size);
131 
132         table3 = new (std::nothrow) unsigned long[table_size];
133         table4 = new (std::nothrow) unsigned long[table_size];
134 
135         if (!table3 || !table4)
136         {
137             if (!table3)
138                 delete [] table3;
139             if (!table4)
140                 delete [] table4;
141 
142             throw std::bad_alloc();
143         }
144 
145 
146 
147         for (unsigned long i = 0; i < buffer.size(); ++i)
148             buffer[i] = 0;
149 
150         for (unsigned long i = 0; i < table_size; ++i)
151         {
152             table3[i] = buffer.size();
153             table4[i] = buffer.size();
154         }
155 
156         last_element = buffer.size()-1;
157     }
158 
159 // ----------------------------------------------------------------------------------------
160 
161     template <
162         typename sbuf
163         >
164     lzp_buffer_kernel_2<sbuf>::
~lzp_buffer_kernel_2()165     ~lzp_buffer_kernel_2 (
166     )
167     {
168         delete [] table3;
169         delete [] table4;
170     }
171 
172 // ----------------------------------------------------------------------------------------
173 
174     template <
175         typename sbuf
176         >
177     void lzp_buffer_kernel_2<sbuf>::
clear()178     clear(
179     )
180     {
181         for (unsigned long i = 0; i < buffer.size(); ++i)
182             buffer[i] = 0;
183 
184         for (unsigned long i = 0; i < table_size; ++i)
185         {
186             table3[i] = buffer.size();
187             table4[i] = buffer.size();
188         }
189     }
190 
191 // ----------------------------------------------------------------------------------------
192 
193     template <
194         typename sbuf
195         >
196     void lzp_buffer_kernel_2<sbuf>::
add(unsigned char symbol)197     add (
198         unsigned char symbol
199     )
200     {
201         buffer.rotate_left(1);
202         buffer[0] = symbol;
203     }
204 
205 // ----------------------------------------------------------------------------------------
206 
207     template <
208         typename sbuf
209         >
210     unsigned long lzp_buffer_kernel_2<sbuf>::
predict_match(unsigned long & index)211     predict_match (
212         unsigned long& index
213     )
214     {
215         unsigned long temp1 = buffer[0];
216         unsigned long temp2 = buffer[1];
217         temp2 <<= 8;
218         unsigned long temp3 = buffer[2];
219         temp3 <<= 16;
220         unsigned long temp4 = buffer[3];
221         temp4 <<= 24;
222         unsigned long temp5 = buffer[4];
223         temp5 <<= 12;
224 
225         unsigned long context1 = temp1|temp2|temp3;
226         unsigned long context2 = context1|temp4;
227 
228 
229         const unsigned long i5 = ((temp5|(context2>>20))^context2)&0xFFFF;
230         const unsigned long i4 = ((context2>>15)^context2)&0xFFFF;
231         const unsigned long i3 = ((context1>>11)^context1)&0xFFFF;
232 
233 
234 
235         // check the 5-order context's prediction
236         if (table3[i5] != buffer.size() &&
237             verify(buffer.get_element_index(table3[i5])) )
238         {
239             index = buffer.get_element_index(table3[i5]);
240             if (index > 20)
241             {
242                 // update the prediction for this context
243                 table3[i3] = buffer.get_element_id(last_element);
244                 table4[i4] = table3[i3];
245                 table3[i5] = table3[i3];
246             }
247             return 5;
248         }
249         // check the 4-order context's prediction
250         else if (table4[i4] != buffer.size() &&
251             verify(buffer.get_element_index(table4[i4])) )
252         {
253             index = buffer.get_element_index(table4[i4]);
254             if (index > 20)
255             {
256                 // update the prediction for this context
257                 table3[i3] = buffer.get_element_id(last_element);
258                 table4[i4] = table3[i3];
259                 table3[i5] = table3[i3];
260             }
261             return 4;
262         }
263         // check the 3-order context's prediction
264         else if (table3[i3] != buffer.size() &&
265             verify(buffer.get_element_index(table3[i3])))
266         {
267             index = buffer.get_element_index(table3[i3]);
268 
269             if (index > 20)
270             {
271                 // update the prediction for this context
272                 table3[i3] = buffer.get_element_id(last_element);
273                 table4[i4] = table3[i3];
274                 table3[i5] = table3[i3];
275             }
276             return 3;
277         }
278         else
279         {
280             // update the prediction for this context
281             table3[i3] = buffer.get_element_id(last_element);
282             table4[i4] = table3[i3];
283             table3[i5] = table3[i3];
284 
285             return 0;
286         }
287     }
288 
289 // ----------------------------------------------------------------------------------------
290 
291     template <
292         typename sbuf
293         >
294     size_t lzp_buffer_kernel_2<sbuf>::
size()295     size (
296     ) const
297     {
298         return buffer.size();
299     }
300 
301 // ----------------------------------------------------------------------------------------
302 
303     template <
304         typename sbuf
305         >
306     unsigned char lzp_buffer_kernel_2<sbuf>::
307     operator[] (
308         unsigned long index
309     ) const
310     {
311         return buffer[index];
312     }
313 
314 // ----------------------------------------------------------------------------------------
315 
316 }
317 
318 #endif // DLIB_LZP_BUFFER_KERNEl_2_
319 
320