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) 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
 102 typedef 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 }
 194 lzo_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
 228 static
 229 void 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
 250 static
 251 void 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
 281 static
 282 int 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
 382 static
 383 void 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
 409 static __lzo_inline
 410 void 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
 444 static __lzo_inline
 445 void 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
 483 static
 484 void 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
 517 static
 518 void 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
 601 static
 602 lzo_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
 638 static
 639 void 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 /*
 705 vi:ts=4:et
 706 */
 707