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