home *** CD-ROM | disk | FTP | other *** search
/ PC Online 1997 March / PCO3_97.ISO / filesbbs / os2 / lzo026.arj / LZO026.ZIP / lzo-0.26 / src / lzo1b_sm.ch < prev    next >
Encoding:
Text File  |  1996-11-16  |  4.0 KB  |  177 lines
  1. /* lzo1b_sm.ch -- implementation of the LZO1B compression algorithm
  2.  
  3.    This file is part of the LZO real-time data compression library.
  4.  
  5.    Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  6.  
  7.    The LZO library is free software; you can redistribute it and/or
  8.    modify it under the terms of the GNU General Public License as
  9.    published by the Free Software Foundation; either version 2 of
  10.    the License, or (at your option) any later version.
  11.  
  12.    The LZO library is distributed in the hope that it will be useful,
  13.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15.    GNU General Public License for more details.
  16.  
  17.    You should have received a copy of the GNU General Public License
  18.    along with the LZO library; see the file COPYING.
  19.    If not, write to the Free Software Foundation, Inc.,
  20.    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  21.  
  22.    Markus F.X.J. Oberhumer
  23.    markus.oberhumer@jk.uni-linz.ac.at
  24.  */
  25.  
  26.  
  27. /* WARNING: this file should *not* be used by applications. It is
  28.    part of the implementation of the library and is subject
  29.    to change.
  30.  */
  31.  
  32.  
  33.  
  34. /***********************************************************************
  35. // search for a match
  36. ************************************************************************/
  37.  
  38. #if (DD_BITS == 0)
  39.  
  40.         /* search ip in the dictionary */
  41.         {
  42.             lzo_uint dindex;
  43.  
  44.             dindex = DINDEX(dv,ip);
  45.             m_pos = dict[dindex];
  46.             UPDATE_I(dict,cycle,dindex,ip);
  47.  
  48. #if !defined(NDEBUG)
  49.             DVAL_ASSERT(dv,ip);
  50. #if defined(LZO_DETERMINISTIC)
  51.             assert(m_pos == NULL || m_pos >= in);
  52.             assert(m_pos == NULL || m_pos < ip);
  53. #endif
  54.             m_pos_sav = m_pos;
  55. #endif
  56.         }
  57.  
  58.  
  59.  
  60. #else /* (DD_BITS == 0) */
  61.  
  62.  
  63.  
  64.         /* search ip in the deepened dictionary */
  65.         {
  66.             const lzo_bytepp d = &dict [ DINDEX(dv,ip) ];
  67.             const lzo_byte *ip_sav;
  68.             unsigned j = DD_SIZE;
  69.             lzo_uint x_len;
  70.             lzo_ptrdiff_t x_off;
  71.  
  72.             DVAL_ASSERT(dv,ip);
  73.  
  74.             ip_sav = ip;
  75.             m_len = 0;
  76.             do {
  77.                 assert(ip == ip_sav);
  78.                 m_pos = *d;
  79. #if defined(LZO_DETERMINISTIC)
  80.                 assert(m_pos == NULL || m_pos >= in);
  81.                 assert(m_pos == NULL || m_pos < ip);
  82. #endif
  83.  
  84.                 if (LZO_CHECK_MPOS(m_pos,x_off,in,ip,MAX_OFFSET))
  85. #if (CLEVEL == 9)
  86.                     *d = ip;
  87. #else
  88.                     ((void)(0));
  89. #endif
  90.                 else if (m_pos[m_len] != ip[m_len])
  91.                     ((void)(0));
  92.                 else if (*m_pos++ == *ip++ && *m_pos++ == *ip++ && *m_pos++ == *ip++)
  93.                 {
  94.                     /* a match */
  95.                     if (MATCH_M2)
  96.                     {
  97.                         x_len = (ip - 1) - ip_sav;
  98.                         if (x_len > m_len)
  99.                         {
  100.                             m_len = x_len;
  101.                             m_off = x_off;
  102.                             assert((m_pos_sav = *d) != NULL);
  103.                         }
  104. #if (CLEVEL == 9)
  105.                         /* try to find a closer match */
  106.                         else if (x_len == m_len && x_off < m_off)
  107.                         {
  108.                             m_off = x_off;
  109.                             assert((m_pos_sav = *d) != NULL);
  110.                         }
  111. #endif
  112.                     }
  113.                     else
  114.                     {
  115.                         assert((ip - ip_sav) == M2_MAX_LEN + 1);
  116. #if (CLEVEL == 9)
  117. #if defined(MATCH_IP_END)
  118.                         {
  119.                             const lzo_byte *end;
  120.                             end = MATCH_IP_END;
  121.                             while (ip < end  &&  *m_pos == *ip)
  122.                                 m_pos++, ip++;
  123.                             assert(ip <= in_end);
  124.                             x_len = ip - ip_sav;
  125.                         }
  126.                         if (x_len > m_len)
  127.                         {
  128.                             m_len = x_len;
  129.                             m_off = x_off;
  130.                             assert((m_pos_sav = *d) != NULL);
  131.                         }
  132.                         else if (x_len == m_len && x_off < m_off)
  133.                         {
  134.                             m_off = x_off;
  135.                             assert((m_pos_sav = *d) != NULL);
  136.                         }
  137. #else
  138.                         /* try to find a closer match */
  139.                         if (m_len < M2_MAX_LEN + 1 || x_off < m_off)
  140.                         {
  141.                             m_len = M2_MAX_LEN + 1;
  142.                             m_off = x_off;
  143.                             assert((m_pos_sav = *d) != NULL);
  144.                         }
  145. #endif
  146. #else
  147.                         /* don't search for a longer/closer match */
  148.                         m_len = M2_MAX_LEN + 1;
  149.                         m_off = x_off;
  150.                         assert((m_pos_sav = *d) != NULL);
  151.                         ip = ip_sav;
  152.                         d -= DD_SIZE - j;
  153.                         assert(d == &dict [ DINDEX(dv,ip) ]);
  154.                         UPDATE_P(d,cycle,ip);
  155.                         goto match;
  156. #endif
  157.                     }
  158.                     ip = ip_sav;
  159.                 }
  160.                 else
  161.                     ip = ip_sav;
  162.                 d++;
  163.             } while (--j > 0);
  164.             assert(ip == ip_sav);
  165.  
  166.             d -= DD_SIZE;
  167.             assert(d == &dict [ DINDEX(dv,ip) ]);
  168.             UPDATE_P(d,cycle,ip);
  169.         }
  170.  
  171. #endif /* (DD_BITS == 0) */
  172.  
  173.  
  174. /*
  175. vi:ts=4
  176. */
  177.