release/src/router/lzo/src/lzo1a_cm.ch

   1 /* lzo1a_cm.ch -- implementation of the LZO1A compression algorithm
   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 /* WARNING: this file should *not* be used by applications. It is
  45    part of the implementation of the library and is subject
  46    to change.
  47  */
  48
  49
  50
  51 /***********************************************************************
  52 // code the match in LZO1 compatible format
  53 ************************************************************************/
  54
  55 #define THRESHOLD   (M2_MIN_LEN - 1)
  56 #define MSIZE       LZO_SIZE(M2L_BITS)
  57
  58
  59 /***********************************************************************
  60 //
  61 ************************************************************************/
  62
  63 #if (DD_BITS == 0)
  64
  65         /* we already matched M2_MIN_LEN bytes,
  66          * m_pos also already advanced M2_MIN_LEN bytes */
  67         ip += M2_MIN_LEN;
  68         assert(m_pos < ip);
  69
  70         /* try to match another M2_MAX_LEN + 1 - M2_MIN_LEN bytes
  71          * to see if we get more than a M2 match */
  72 #define M2_OR_M3    (MATCH_M2)
  73
  74 #else /* (DD_BITS == 0) */
  75
  76         /* we already matched m_len bytes */
  77         assert(m_len >= M2_MIN_LEN);
  78         ip += m_len;
  79         assert(ip <= in_end);
  80
  81 #define M2_OR_M3    (m_len <= M2_MAX_LEN)
  82
  83 #endif /* (DD_BITS == 0) */
  84
  85
  86         if (M2_OR_M3)
  87         {
  88         /* we've found a short match */
  89             assert(ip <= in_end);
  90
  91         /* 2a) compute match parameters */
  92 #if (DD_BITS == 0)
  93                 assert(pd(ip,m_pos) == m_off);
  94             --ip;   /* ran one too far, point back to non-match */
  95             m_len = ip - ii;
  96 #endif
  97                 assert(m_len >= M2_MIN_LEN);
  98                 assert(m_len <= M2_MAX_LEN);
  99
 100                 assert(m_off >= M2_MIN_OFFSET);
 101                 assert(m_off <= M2_MAX_OFFSET);
 102                 assert(ii-m_off == m_pos_sav);
 103                 assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
 104
 105         /* 2b) code the match */
 106             m_off -= M2_MIN_OFFSET;
 107             /* code short match len + low offset bits */
 108             *op++ = LZO_BYTE(((m_len - THRESHOLD) << M2O_BITS) |
 109                              (m_off & M2O_MASK));
 110             /* code high offset bits */
 111             *op++ = LZO_BYTE(m_off >> M2O_BITS);
 112
 113
 114             if (ip >= ip_end)
 115             {
 116                 ii = ip;
 117                 break;
 118             }
 119
 120
 121         /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
 122
 123 #if (CLEVEL == 9) || (CLEVEL >= 7 && M2L_BITS <= 4) || (CLEVEL >= 5 && M2L_BITS <= 3)
 124         /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
 125             ++ii;
 126             do {
 127                 DVAL_NEXT(dv,ii);
 128 #if 0
 129                 UPDATE_D(dict,drun,dv,ii,in);
 130 #else
 131                 dict[ DINDEX(dv,ii) ] = DENTRY(ii,in);
 132 #endif
 133                 MI
 134             } while (++ii < ip);
 135             DVAL_NEXT(dv,ii);
 136             assert(ii == ip);
 137             DVAL_ASSERT(dv,ip);
 138 #elif (CLEVEL >= 3)
 139             SI   DI DI   XI
 140 #elif (CLEVEL >= 2)
 141             SI   DI      XI
 142 #else
 143                          XI
 144 #endif
 145         }
 146
 147         else
 148
 149         {
 150         /* we've found a long match - see how far we can still go */
 151             const lzo_bytep end;
 152
 153             assert(ip <= in_end);
 154             assert(ii == ip - (M2_MAX_LEN + 1));
 155             assert(lzo_memcmp(m_pos_sav,ii,(lzo_uint)(ip-ii)) == 0);
 156
 157 #if (DD_BITS > 0)
 158             assert(m_len == (lzo_uint)(ip-ii));
 159             m_pos = ip - m_off;
 160             assert(m_pos == m_pos_sav + m_len);
 161 #endif
 162
 163             if (pd(in_end,ip) <= (M3_MAX_LEN - M3_MIN_LEN))
 164                 end = in_end;
 165             else
 166             {
 167                 end = ip + (M3_MAX_LEN - M3_MIN_LEN);
 168                 assert(end < in_end);
 169             }
 170
 171             while (ip < end  &&  *m_pos == *ip)
 172                 m_pos++, ip++;
 173             assert(ip <= in_end);
 174
 175             /* 2a) compute match parameters */
 176             m_len = pd(ip, ii);
 177                 assert(m_len >= M3_MIN_LEN);
 178                 assert(m_len <= M3_MAX_LEN);
 179
 180                 assert(m_off >= M3_MIN_OFFSET);
 181                 assert(m_off <= M3_MAX_OFFSET);
 182                 assert(ii-m_off == m_pos_sav);
 183                 assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
 184                 assert(pd(ip,m_pos) == m_off);
 185
 186         /* 2b) code the match */
 187             m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET;
 188             /* code long match flag + low offset bits */
 189             *op++ = LZO_BYTE(((MSIZE - 1) << M3O_BITS) | (m_off & M3O_MASK));
 190             /* code high offset bits */
 191             *op++ = LZO_BYTE(m_off >> M3O_BITS);
 192             /* code match len */
 193             *op++ = LZO_BYTE(m_len - M3_MIN_LEN);
 194
 195
 196             if (ip >= ip_end)
 197             {
 198                 ii = ip;
 199                 break;
 200             }
 201
 202
 203         /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
 204 #if (CLEVEL == 9)
 205         /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
 206         /* This is not recommended because it can be slow. */
 207             ++ii;
 208             do {
 209                 DVAL_NEXT(dv,ii);
 210 #if 0
 211                 UPDATE_D(dict,drun,dv,ii,in);
 212 #else
 213                 dict[ DINDEX(dv,ii) ] = DENTRY(ii,in);
 214 #endif
 215                 MI
 216             } while (++ii < ip);
 217             DVAL_NEXT(dv,ii);
 218             assert(ii == ip);
 219             DVAL_ASSERT(dv,ip);
 220 #elif (CLEVEL >= 8)
 221             SI   DI DI DI DI DI DI DI DI   XI
 222 #elif (CLEVEL >= 7)
 223             SI   DI DI DI DI DI DI DI      XI
 224 #elif (CLEVEL >= 6)
 225             SI   DI DI DI DI DI DI         XI
 226 #elif (CLEVEL >= 5)
 227             SI   DI DI DI DI               XI
 228 #elif (CLEVEL >= 4)
 229             SI   DI DI DI                  XI
 230 #elif (CLEVEL >= 3)
 231             SI   DI DI                     XI
 232 #elif (CLEVEL >= 2)
 233             SI   DI                        XI
 234 #else
 235                                            XI
 236 #endif
 237         }
 238
 239         /* ii now points to the start of the next literal run */
 240         assert(ii == ip);
 241
 242
 243 /*
 244 vi:ts=4:et
 245 */