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