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@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 86typedef 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} 153lzo_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 184static 185void 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 206static 207void 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 240static 241int 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 354static 355void 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 381static __lzo_inline 382void 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 416static __lzo_inline 417void 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 458static 459void 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 494static 495void 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 578static 579lzo_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 615static 616void 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/* 687vi:ts=4:et 688*/ 689 690