1 /* lzo_swd.ch -- sliding window dictionary 2 3 This file is part of the LZO real-time data compression library. 4 5 Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer 6 All Rights Reserved. 7 8 The LZO library is free software; you can redistribute it and/or 9 modify it under the terms of the GNU General Public License as 10 published by the Free Software Foundation; either version 2 of 11 the License, or (at your option) any later version. 12 13 The LZO library is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with the LZO library; see the file COPYING. 20 If not, write to the Free Software Foundation, Inc., 21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 22 23 Markus F.X.J. Oberhumer 24 <markus (at) oberhumer.com> 25 http://www.oberhumer.com/opensource/lzo/ 26 */ 27 28 29 #if (LZO_UINT_MAX < LZO_0xffffffffL) 30 # error "LZO_UINT_MAX" 31 #endif 32 #if defined(LZO_DEBUG) 33 # include <stdio.h> 34 #endif 35 #if defined(__LZO_CHECKER) 36 # include <stdlib.h> 37 #endif 38 39 40 /*********************************************************************** 41 // 42 ************************************************************************/ 43 44 /* unsigned type for dictionary access - don't waste memory here */ 45 #if (0UL + SWD_N + SWD_F + SWD_F < 65535UL) 46 typedef lzo_uint16_t swd_uint; 47 # define SWD_UINT_MAX 0xffffu 48 #else 49 typedef lzo_uint32_t swd_uint; 50 # define SWD_UINT_MAX 0xffffffffu 51 #endif 52 #define swd_uintp swd_uint * 53 #define SWD_UINT(x) ((swd_uint)(x)) 54 55 56 #ifndef SWD_HSIZE 57 # define SWD_HSIZE 16384 58 #endif 59 #ifndef SWD_MAX_CHAIN 60 # define SWD_MAX_CHAIN 2048 61 #endif 62 63 #if !defined(HEAD3) 64 #if 1 65 # define HEAD3(b,p) \ 66 ((DMUL(0x9f5f,(((((lzo_xint)b[p]<<5)^b[p+1])<<5)^b[p+2]))>>5) & (SWD_HSIZE-1)) 67 #else 68 # define HEAD3(b,p) \ 69 ((DMUL(0x9f5f,(((((lzo_xint)b[p+2]<<5)^b[p+1])<<5)^b[p]))>>5) & (SWD_HSIZE-1)) 70 #endif 71 #endif 72 73 #if !(SWD_NO_HEAD2) && (SWD_THRESHOLD == 1) && !defined(HEAD2) 74 # if 1 && (LZO_OPT_UNALIGNED16) 75 # define HEAD2(b,p) UA_GET_NE16((b)+(p)) 76 # else 77 # define HEAD2(b,p) (b[p] ^ ((unsigned)b[(p)+1]<<8)) 78 # endif 79 # define NIL2 SWD_UINT_MAX 80 #endif 81 #ifndef IF_HEAD2 82 #define IF_HEAD2(s) /*empty*/ 83 #endif 84 85 86 typedef struct 87 { 88 /* public - "built-in" */ 89 lzo_uint swd_n; 90 lzo_uint swd_f; 91 lzo_uint swd_threshold; 92 93 /* public - configuration */ 94 lzo_uint max_chain; 95 lzo_uint nice_length; 96 lzo_bool use_best_off; 97 lzo_uint lazy_insert; 98 99 /* public - output */ 100 lzo_uint m_len; 101 lzo_uint m_off; 102 lzo_uint look; 103 int b_char; 104 #if defined(SWD_BEST_OFF) 105 lzo_uint best_off[ SWD_BEST_OFF ]; 106 #endif 107 108 /* semi public */ 109 LZO_COMPRESS_T *c; 110 lzo_uint m_pos; 111 #if defined(SWD_BEST_OFF) 112 lzo_uint best_pos[ SWD_BEST_OFF ]; 113 #endif 114 115 /* private */ 116 const lzo_bytep dict; 117 const lzo_bytep dict_end; 118 lzo_uint dict_len; 119 120 /* private */ 121 lzo_uint ip; /* input pointer (lookahead) */ 122 lzo_uint bp; /* buffer pointer */ 123 lzo_uint rp; /* remove pointer */ 124 lzo_uint b_size; 125 126 lzo_bytep b_wrap; 127 128 lzo_uint node_count; 129 lzo_uint first_rp; 130 131 #if defined(__LZO_CHECKER) 132 /* malloc arrays of the exact size to detect any overrun */ 133 unsigned char *b; 134 swd_uint *head3; 135 swd_uint *succ3; 136 swd_uint *best3; 137 swd_uint *llen3; 138 # ifdef HEAD2 139 swd_uint *head2; 140 # endif 141 142 #else 143 unsigned char b [ SWD_N + SWD_F + SWD_F ]; 144 swd_uint head3 [ SWD_HSIZE ]; 145 swd_uint succ3 [ SWD_N + SWD_F ]; 146 swd_uint best3 [ SWD_N + SWD_F ]; 147 swd_uint llen3 [ SWD_HSIZE ]; 148 # ifdef HEAD2 149 swd_uint head2 [ 65536L ]; 150 # endif 151 #endif 152 } 153 lzo_swd_t; 154 #define lzo_swd_p lzo_swd_t * 155 156 157 #define s_b(s) s->b 158 #define s_head3(s) s->head3 159 #define s_succ3(s) s->succ3 160 #define s_best3(s) s->best3 161 #define s_llen3(s) s->llen3 162 #ifdef HEAD2 163 #define s_head2(s) s->head2 164 #endif 165 #define SIZEOF_LZO_SWD_T (sizeof(lzo_swd_t)) 166 167 168 /* Access macro for head3. 169 * head3[key] may be uninitialized if the list is emtpy, 170 * but then its value will never be used. 171 */ 172 #if 1 || defined(__LZO_CHECKER) 173 # define s_get_head3(s,key) \ 174 ((swd_uint)((s_llen3(s)[key] == 0) ? SWD_UINT_MAX : s_head3(s)[key])) 175 #else 176 # define s_get_head3(s,key) (s_head3(s)[key]) 177 #endif 178 179 180 /*********************************************************************** 181 // 182 ************************************************************************/ 183 184 static 185 void swd_initdict(lzo_swd_p s, const lzo_bytep dict, lzo_uint dict_len) 186 { 187 s->dict = s->dict_end = NULL; 188 s->dict_len = 0; 189 190 if (!dict || dict_len == 0) 191 return; 192 if (dict_len > s->swd_n) 193 { 194 dict += dict_len - s->swd_n; 195 dict_len = s->swd_n; 196 } 197 198 s->dict = dict; 199 s->dict_len = dict_len; 200 s->dict_end = dict + dict_len; 201 lzo_memcpy(s_b(s),dict,dict_len); 202 s->ip = dict_len; 203 } 204 205 206 static 207 void swd_insertdict(lzo_swd_p s, lzo_uint node, lzo_uint len) 208 { 209 lzo_uint key; 210 211 s->node_count = s->swd_n - len; 212 s->first_rp = node; 213 214 if (len) do 215 { 216 key = HEAD3(s_b(s),node); 217 s_succ3(s)[node] = s_get_head3(s,key); 218 s_head3(s)[key] = SWD_UINT(node); 219 s_best3(s)[node] = SWD_UINT(s->swd_f + 1); 220 s_llen3(s)[key]++; 221 assert(s_llen3(s)[key] <= s->swd_n); 222 223 #ifdef HEAD2 224 IF_HEAD2(s) { 225 key = HEAD2(s_b(s),node); 226 s_head2(s)[key] = SWD_UINT(node); 227 } 228 #endif 229 230 node++; 231 } 232 while (--len != 0); 233 } 234 235 236 /*********************************************************************** 237 // 238 ************************************************************************/ 239 240 static 241 int swd_init(lzo_swd_p s, const lzo_bytep dict, lzo_uint dict_len) 242 { 243 #if defined(__LZO_CHECKER) 244 s->b = (lzo_bytep) malloc(SWD_N + SWD_F + SWD_F); 245 s->head3 = (swd_uintp) malloc(sizeof(swd_uint) * SWD_HSIZE); 246 s->succ3 = (swd_uintp) malloc(sizeof(swd_uint) * (SWD_N + SWD_F)); 247 s->best3 = (swd_uintp) malloc(sizeof(swd_uint) * (SWD_N + SWD_F)); 248 s->llen3 = (swd_uintp) malloc(sizeof(swd_uint) * SWD_HSIZE); 249 #ifdef HEAD2 250 IF_HEAD2(s) { 251 s->head2 = (swd_uintp) malloc(sizeof(swd_uint) * 65536L); 252 } 253 #endif 254 #endif 255 256 s->m_len = 0; 257 s->m_off = 0; 258 #if defined(SWD_BEST_OFF) 259 { 260 unsigned i; 261 for (i = 0; i < SWD_BEST_OFF; i++) 262 s->best_off[i] = s->best_pos[i] = 0; 263 } 264 #endif 265 266 s->swd_n = SWD_N; 267 s->swd_f = SWD_F; 268 s->swd_threshold = SWD_THRESHOLD; 269 270 /* defaults */ 271 s->max_chain = SWD_MAX_CHAIN; 272 s->nice_length = s->swd_f; 273 s->use_best_off = 0; 274 s->lazy_insert = 0; 275 276 s->b_size = s->swd_n + s->swd_f; 277 #if 0 278 if (2 * s->swd_f >= s->swd_n || s->b_size + s->swd_f >= SWD_UINT_MAX) 279 return LZO_E_ERROR; 280 #else 281 LZO_COMPILE_TIME_ASSERT(!(0ul + 2 * SWD_F >= SWD_N)) 282 LZO_COMPILE_TIME_ASSERT(!(0ul + SWD_N + SWD_F + SWD_F >= SWD_UINT_MAX)) 283 #endif 284 s->b_wrap = s_b(s) + s->b_size; 285 s->node_count = s->swd_n; 286 287 lzo_memset(s_llen3(s), 0, (lzo_uint)sizeof(s_llen3(s)[0]) * (lzo_uint)SWD_HSIZE); 288 #ifdef HEAD2 289 IF_HEAD2(s) { 290 #if 1 291 lzo_memset(s_head2(s), 0xff, (lzo_uint)sizeof(s_head2(s)[0]) * 65536L); 292 assert(s_head2(s)[0] == NIL2); 293 #else 294 lzo_xint i; 295 for (i = 0; i < 65536L; i++) 296 s_head2(s)[i] = NIL2; 297 #endif 298 } 299 #endif 300 301 s->ip = 0; 302 swd_initdict(s,dict,dict_len); 303 s->bp = s->ip; 304 s->first_rp = s->ip; 305 306 assert(s->ip + s->swd_f <= s->b_size); 307 #if 1 308 s->look = (lzo_uint) (s->c->in_end - s->c->ip); 309 if (s->look > 0) 310 { 311 if (s->look > s->swd_f) 312 s->look = s->swd_f; 313 lzo_memcpy(&s_b(s)[s->ip],s->c->ip,s->look); 314 s->c->ip += s->look; 315 s->ip += s->look; 316 } 317 #else 318 s->look = 0; 319 while (s->look < s->swd_f) 320 { 321 int c; 322 if ((c = getbyte(*(s->c))) < 0) 323 break; 324 s_b(s)[s->ip] = LZO_BYTE(c); 325 s->ip++; 326 s->look++; 327 } 328 #endif 329 if (s->ip == s->b_size) 330 s->ip = 0; 331 332 if (s->look >= 2 && s->dict_len > 0) 333 swd_insertdict(s,0,s->dict_len); 334 335 s->rp = s->first_rp; 336 if (s->rp >= s->node_count) 337 s->rp -= s->node_count; 338 else 339 s->rp += s->b_size - s->node_count; 340 341 #if 1 || defined(__LZO_CHECKER) 342 /* initialize memory for the first few HEAD3 (if s->ip is not far 343 * enough ahead to do this job for us). The value doesn't matter. */ 344 if (s->look < 3) { 345 lzo_bytep p = &s_b(s)[s->bp+s->look]; 346 p[0] = p[1] = p[2] = 0; 347 } 348 #endif 349 350 return LZO_E_OK; 351 } 352 353 354 static 355 void swd_exit(lzo_swd_p s) 356 { 357 #if defined(__LZO_CHECKER) 358 /* free in reverse order of allocations */ 359 #ifdef HEAD2 360 free(s->head2); s->head2 = NULL; 361 #endif 362 free(s->llen3); s->llen3 = NULL; 363 free(s->best3); s->best3 = NULL; 364 free(s->succ3); s->succ3 = NULL; 365 free(s->head3); s->head3 = NULL; 366 free(s->b); s->b = NULL; 367 #else 368 LZO_UNUSED(s); 369 #endif 370 } 371 372 373 #define swd_pos2off(s,pos) \ 374 (s->bp > (pos) ? s->bp - (pos) : s->b_size - ((pos) - s->bp)) 375 376 377 /*********************************************************************** 378 // 379 ************************************************************************/ 380 381 static __lzo_inline 382 void swd_getbyte(lzo_swd_p s) 383 { 384 int c; 385 386 if ((c = getbyte(*(s->c))) < 0) 387 { 388 if (s->look > 0) 389 --s->look; 390 #if 1 || defined(__LZO_CHECKER) 391 /* initialize memory - value doesn't matter */ 392 s_b(s)[s->ip] = 0; 393 if (s->ip < s->swd_f) 394 s->b_wrap[s->ip] = 0; 395 #endif 396 } 397 else 398 { 399 s_b(s)[s->ip] = LZO_BYTE(c); 400 if (s->ip < s->swd_f) 401 s->b_wrap[s->ip] = LZO_BYTE(c); 402 } 403 if (++s->ip == s->b_size) 404 s->ip = 0; 405 if (++s->bp == s->b_size) 406 s->bp = 0; 407 if (++s->rp == s->b_size) 408 s->rp = 0; 409 } 410 411 412 /*********************************************************************** 413 // remove node from lists 414 ************************************************************************/ 415 416 static __lzo_inline 417 void swd_remove_node(lzo_swd_p s, lzo_uint node) 418 { 419 if (s->node_count == 0) 420 { 421 lzo_uint key; 422 423 #ifdef LZO_DEBUG 424 if (s->first_rp != LZO_UINT_MAX) 425 { 426 if (node != s->first_rp) 427 printf("Remove %5ld: %5ld %5ld %5ld %5ld %6ld %6ld\n", 428 (long)node, (long)s->rp, (long)s->ip, (long)s->bp, 429 (long)s->first_rp, (long)(s->ip - node), 430 (long)(s->ip - s->bp)); 431 assert(node == s->first_rp); 432 s->first_rp = LZO_UINT_MAX; 433 } 434 #endif 435 436 key = HEAD3(s_b(s),node); 437 assert(s_llen3(s)[key] > 0); 438 --s_llen3(s)[key]; 439 440 #ifdef HEAD2 441 IF_HEAD2(s) { 442 key = HEAD2(s_b(s),node); 443 assert(s_head2(s)[key] != NIL2); 444 if ((lzo_uint) s_head2(s)[key] == node) 445 s_head2(s)[key] = NIL2; 446 } 447 #endif 448 } 449 else 450 --s->node_count; 451 } 452 453 454 /*********************************************************************** 455 // 456 ************************************************************************/ 457 458 static 459 void swd_accept(lzo_swd_p s, lzo_uint n) 460 { 461 assert(n <= s->look); 462 463 if (n) do 464 { 465 lzo_uint key; 466 467 swd_remove_node(s,s->rp); 468 469 /* add bp into HEAD3 */ 470 key = HEAD3(s_b(s),s->bp); 471 s_succ3(s)[s->bp] = s_get_head3(s,key); 472 s_head3(s)[key] = SWD_UINT(s->bp); 473 s_best3(s)[s->bp] = SWD_UINT(s->swd_f + 1); 474 s_llen3(s)[key]++; 475 assert(s_llen3(s)[key] <= s->swd_n); 476 477 #ifdef HEAD2 478 /* add bp into HEAD2 */ 479 IF_HEAD2(s) { 480 key = HEAD2(s_b(s),s->bp); 481 s_head2(s)[key] = SWD_UINT(s->bp); 482 } 483 #endif 484 485 swd_getbyte(s); 486 } while (--n != 0); 487 } 488 489 490 /*********************************************************************** 491 // 492 ************************************************************************/ 493 494 static 495 void swd_search(lzo_swd_p s, lzo_uint node, lzo_uint cnt) 496 { 497 const lzo_bytep p1; 498 const lzo_bytep p2; 499 const lzo_bytep px; 500 lzo_uint m_len = s->m_len; 501 const lzo_bytep b = s_b(s); 502 const lzo_bytep bp = s_b(s) + s->bp; 503 const lzo_bytep bx = s_b(s) + s->bp + s->look; 504 unsigned char scan_end1; 505 506 assert(s->m_len > 0); 507 508 scan_end1 = bp[m_len - 1]; 509 for ( ; cnt-- > 0; node = s_succ3(s)[node]) 510 { 511 p1 = bp; 512 p2 = b + node; 513 px = bx; 514 515 assert(m_len < s->look); 516 517 if ( 518 #if 1 519 p2[m_len - 1] == scan_end1 && 520 p2[m_len] == p1[m_len] && 521 #endif 522 p2[0] == p1[0] && 523 p2[1] == p1[1]) 524 { 525 lzo_uint i; 526 assert(lzo_memcmp(bp,&b[node],3) == 0); 527 528 #if 0 && (LZO_OPT_UNALIGNED32) 529 p1 += 3; p2 += 3; 530 while (p1 + 4 <= px && UA_GET_NE32(p1) == UA_GET_NE32(p2)) 531 p1 += 4, p2 += 4; 532 while (p1 < px && *p1 == *p2) 533 p1 += 1, p2 += 1; 534 #else 535 p1 += 2; p2 += 2; 536 do {} while (++p1 < px && *p1 == *++p2); 537 #endif 538 i = pd(p1, bp); 539 540 #ifdef LZO_DEBUG 541 if (lzo_memcmp(bp,&b[node],i) != 0) 542 printf("%5ld %5ld %5ld %02x/%02x %02x/%02x\n", 543 (long)s->bp, (long) node, (long) i, 544 bp[0], bp[1], b[node], b[node+1]); 545 #endif 546 assert(lzo_memcmp(bp,&b[node],i) == 0); 547 548 #if defined(SWD_BEST_OFF) 549 if (i < SWD_BEST_OFF) 550 { 551 if (s->best_pos[i] == 0) 552 s->best_pos[i] = node + 1; 553 } 554 #endif 555 if (i > m_len) 556 { 557 s->m_len = m_len = i; 558 s->m_pos = node; 559 if (m_len == s->look) 560 return; 561 if (m_len >= s->nice_length) 562 return; 563 if (m_len > (lzo_uint) s_best3(s)[node]) 564 return; 565 scan_end1 = bp[m_len - 1]; 566 } 567 } 568 } 569 } 570 571 572 /*********************************************************************** 573 // 574 ************************************************************************/ 575 576 #ifdef HEAD2 577 578 static 579 lzo_bool swd_search2(lzo_swd_p s) 580 { 581 lzo_uint key; 582 583 assert(s->look >= 2); 584 assert(s->m_len > 0); 585 586 key = s_head2(s)[ HEAD2(s_b(s),s->bp) ]; 587 if (key == NIL2) 588 return 0; 589 #ifdef LZO_DEBUG 590 if (lzo_memcmp(&s_b(s)[s->bp],&s_b(s)[key],2) != 0) 591 printf("%5ld %5ld %02x/%02x %02x/%02x\n", (long)s->bp, (long)key, 592 s_b(s)[s->bp], s_b(s)[s->bp+1], s_b(s)[key], s_b(s)[key+1]); 593 #endif 594 assert(lzo_memcmp(&s_b(s)[s->bp],&s_b(s)[key],2) == 0); 595 #if defined(SWD_BEST_OFF) 596 if (s->best_pos[2] == 0) 597 s->best_pos[2] = key + 1; 598 #endif 599 600 if (s->m_len < 2) 601 { 602 s->m_len = 2; 603 s->m_pos = key; 604 } 605 return 1; 606 } 607 608 #endif 609 610 611 /*********************************************************************** 612 // 613 ************************************************************************/ 614 615 static 616 void swd_findbest(lzo_swd_p s) 617 { 618 lzo_uint key; 619 lzo_uint cnt, node; 620 lzo_uint len; 621 622 assert(s->m_len > 0); 623 624 /* get current head, add bp into HEAD3 */ 625 key = HEAD3(s_b(s),s->bp); 626 node = s_succ3(s)[s->bp] = s_get_head3(s,key); 627 cnt = s_llen3(s)[key]++; 628 assert(s_llen3(s)[key] <= s->swd_n + s->swd_f); 629 if (cnt > s->max_chain && s->max_chain > 0) 630 cnt = s->max_chain; 631 s_head3(s)[key] = SWD_UINT(s->bp); 632 633 s->b_char = s_b(s)[s->bp]; 634 len = s->m_len; 635 if (s->m_len >= s->look) 636 { 637 if (s->look == 0) 638 s->b_char = -1; 639 s->m_off = 0; 640 s_best3(s)[s->bp] = SWD_UINT(s->swd_f + 1); 641 } 642 else 643 { 644 #if defined(HEAD2) 645 if (swd_search2(s) && s->look >= 3) 646 swd_search(s,node,cnt); 647 #else 648 if (s->look >= 3) 649 swd_search(s,node,cnt); 650 #endif 651 if (s->m_len > len) 652 s->m_off = swd_pos2off(s,s->m_pos); 653 s_best3(s)[s->bp] = SWD_UINT(s->m_len); 654 655 #if defined(SWD_BEST_OFF) 656 if (s->use_best_off) 657 { 658 unsigned i; 659 for (i = 2; i < SWD_BEST_OFF; i++) 660 if (s->best_pos[i] > 0) 661 s->best_off[i] = swd_pos2off(s,s->best_pos[i]-1); 662 else 663 s->best_off[i] = 0; 664 } 665 #endif 666 } 667 668 swd_remove_node(s,s->rp); 669 670 #ifdef HEAD2 671 /* add bp into HEAD2 */ 672 IF_HEAD2(s) { 673 key = HEAD2(s_b(s),s->bp); 674 s_head2(s)[key] = SWD_UINT(s->bp); 675 } 676 #endif 677 } 678 679 680 #undef HEAD3 681 #undef HEAD2 682 #undef IF_HEAD2 683 #undef s_get_head3 684 685 686 /* 687 vi:ts=4:et 688 */ 689 690
