release/src/router/lzo/src/lzo_swd.ch

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