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