src/lzo1b_cm.ch

   1 /* lzo1b_cm.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) 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 /* WARNING: this file should *not* be used by applications. It is
  42    part of the implementation of the library and is subject
  43    to change.
  44  */
  45
  46
  47
  48 /***********************************************************************
  49 // code the match
  50 ************************************************************************/
  51
  52 #if (DD_BITS == 0)
  53
  54         /* we already matched M2_MIN_LEN bytes,
  55          * m_pos also already advanced M2_MIN_LEN bytes */
  56         ip += M2_MIN_LEN;
  57         assert(m_pos < ip);
  58
  59         /* try to match another M2_MAX_LEN + 1 - M2_MIN_LEN bytes
  60          * to see if we get more than a M2 match */
  61 #define M2_OR_M3    (MATCH_M2)
  62
  63 #else /* (DD_BITS == 0) */
  64
  65         /* we already matched m_len bytes */
  66         assert(m_len >= M2_MIN_LEN);
  67         ip += m_len;
  68         assert(ip <= in_end);
  69
  70 #define M2_OR_M3    (m_len <= M2_MAX_LEN)
  71
  72 #endif /* (DD_BITS == 0) */
  73
  74
  75
  76         if (M2_OR_M3)
  77         {
  78         /* we've found a M2 or M3 match */
  79             assert(ip <= in_end);
  80
  81         /* 2a) compute match parameters */
  82 #if (DD_BITS == 0)
  83             assert(pd(ip,m_pos) == m_off);
  84             --ip;   /* ran one too far, point back to non-match */
  85             m_len = pd(ip, ii);
  86 #endif
  87
  88         /* 2a2) verify match parameters */
  89             assert(m_len >= M2_MIN_LEN);
  90             assert(m_len <= M2_MAX_LEN);
  91             assert(m_len <= M3_MAX_LEN);
  92
  93             assert(m_off >= M2_MIN_OFFSET);
  94             assert(m_off >= M3_MIN_OFFSET);
  95             assert(m_off <= M3_MAX_OFFSET);
  96             assert(ii-m_off == m_pos_sav);
  97             assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
  98
  99         /* 2b) code the match */
 100 #if (_M2_MAX_OFFSET != _M3_MAX_OFFSET)
 101             if (m_off <= M2_MAX_OFFSET)
 102             {
 103 #else
 104                 assert(m_off <= M2_MAX_OFFSET);
 105 #endif
 106                 m_off -= M2_MIN_OFFSET;
 107                 /* code match len + low offset bits */
 108                 *op++ = LZO_BYTE(((m_len - (M2_MIN_LEN - 2)) << M2O_BITS) |
 109                                   (m_off & M2O_MASK));
 110                 /* code high offset bits */
 111                 *op++ = LZO_BYTE(m_off >> M2O_BITS);
 112                 LZO_STATS(lzo_stats->m2_matches++);
 113                 LZO_STATS(lzo_stats->m2_match[m_len]++);
 114 #if (_M2_MAX_OFFSET != _M3_MAX_OFFSET)
 115             }
 116             else
 117             {
 118 #if defined(LZO_HAVE_R1)
 119 #if (M3_MIN_LEN == M2_MIN_LEN)
 120                 r1 = ip_end;    /* invalidate R1 pointer */
 121 #endif
 122 #endif
 123                 assert(m_len >= M3_MIN_LEN);
 124                 m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET;
 125                 /* code match len */
 126                 *op++ = LZO_BYTE(M3_MARKER | (m_len - (M3_MIN_LEN - 1)));
 127                 /* code low offset bits */
 128                 *op++ = LZO_BYTE(m_off & M3O_MASK);
 129                 /* code high offset bits */
 130                 *op++ = LZO_BYTE(m_off >> M3O_BITS);
 131                 LZO_STATS(lzo_stats->m3_matches++);
 132                 LZO_STATS(lzo_stats->m3_match[m_len]++);
 133 #if defined(LZO_HAVE_M3)
 134                 m3 = op;        /* set M3 pointer */
 135 #endif
 136             }
 137 #endif /* (_M2_MAX_OFFSET != _M3_MAX_OFFSET) */
 138
 139
 140             if (ip >= ip_end)
 141             {
 142                 ii = ip;
 143                 break;
 144             }
 145
 146
 147         /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
 148
 149 #if (CLEVEL == 9) || (CLEVEL >= 7 && M2L_BITS <= 4) || (CLEVEL >= 5 && M2L_BITS <= 3)
 150         /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
 151             ++ii;
 152             do {
 153                 DVAL_NEXT(dv,ii);
 154 #if 0
 155                 UPDATE_D(dict,drun,dv,ii,in);
 156 #else
 157                 dict[ DINDEX(dv,ii) ] = DENTRY(ii,in);
 158 #endif
 159                 MI
 160             } while (++ii < ip);
 161             DVAL_NEXT(dv,ii);
 162             assert(ii == ip);
 163             DVAL_ASSERT(dv,ip);
 164 #elif (CLEVEL >= 3)
 165             SI   DI DI   XI
 166 #elif (CLEVEL >= 2)
 167             SI   DI      XI
 168 #else
 169                          XI
 170 #endif
 171         }
 172
 173         else
 174
 175         {
 176         /* we've found a M3 or M4 match - see how far we can still go */
 177             assert(ip <= in_end);
 178             assert(lzo_memcmp(m_pos_sav,ii,(lzo_uint)(ip-ii)) == 0);
 179
 180         /* 2a) compute match parameters */
 181 #if !defined(MATCH_IP_END)
 182             assert(ii == ip - (M2_MAX_LEN + 1));
 183 #if (DD_BITS > 0)
 184             assert(m_len == (lzo_uint)(ip-ii));
 185             m_pos = ip - m_off;
 186             assert(m_pos == m_pos_sav + m_len);
 187 #endif
 188             {
 189                 const lzo_bytep end;
 190                 end = in_end;
 191                 while (ip < end  &&  *m_pos == *ip)
 192                     m_pos++, ip++;
 193                 assert(ip <= in_end);
 194                 m_len = pd(ip, ii);
 195             }
 196             assert(pd(ip,m_pos) == m_off);
 197 #endif
 198
 199         /* 2a2) verify match parameters */
 200             assert(m_len >= M3_MIN_LEN);
 201
 202             assert(m_off >= M3_MIN_OFFSET);
 203             assert(m_off >= M4_MIN_OFFSET);
 204             assert(m_off <= M3_MAX_OFFSET);
 205             assert(m_off <= M4_MAX_OFFSET);
 206             assert(ii-m_off == m_pos_sav);
 207             assert(lzo_memcmp(m_pos_sav,ii,m_len) == 0);
 208
 209         /* 2b) code the match */
 210             if (m_len <= M3_MAX_LEN)
 211             {
 212                 /* code match len */
 213                 *op++ = LZO_BYTE(M3_MARKER | (m_len - (M3_MIN_LEN - 1)));
 214                 LZO_STATS(lzo_stats->m3_matches++);
 215                 LZO_STATS(lzo_stats->m3_match[m_len]++);
 216             }
 217             else
 218             {
 219                 assert(m_len >= M4_MIN_LEN);
 220                 /* code M4 match len flag */
 221                 *op++ = M4_MARKER;
 222                 /* code match len */
 223                 m_len -= M4_MIN_LEN - 1;
 224                 while (m_len > 255)
 225                 {
 226                     m_len -= 255;
 227                     *op++ = 0;
 228                 }
 229                 assert(m_len > 0);
 230                 *op++ = LZO_BYTE(m_len);
 231                 LZO_STATS(lzo_stats->m4_matches++);
 232             }
 233
 234             m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET;
 235             /* code low offset bits */
 236             *op++ = LZO_BYTE(m_off & M3O_MASK);
 237             /* code high offset bits */
 238             *op++ = LZO_BYTE(m_off >> M3O_BITS);
 239
 240 #if defined(LZO_HAVE_M3)
 241             m3 = op;        /* set M3 pointer */
 242 #endif
 243
 244
 245             if (ip >= ip_end)
 246             {
 247                 ii = ip;
 248                 break;
 249             }
 250
 251
 252         /* 2c) Insert phrases (beginning with ii+1) into the dictionary. */
 253 #if (CLEVEL == 9)
 254         /* Insert the whole match (ii+1)..(ip-1) into dictionary.  */
 255         /* This is not recommended because it can be slow. */
 256             ++ii;
 257             do {
 258                 DVAL_NEXT(dv,ii);
 259 #if 0
 260                 UPDATE_D(dict,drun,dv,ii,in);
 261 #else
 262                 dict[ DINDEX(dv,ii) ] = DENTRY(ii,in);
 263 #endif
 264                 MI
 265             } while (++ii < ip);
 266             DVAL_NEXT(dv,ii);
 267             assert(ii == ip);
 268             DVAL_ASSERT(dv,ip);
 269 #elif (CLEVEL >= 8)
 270             SI   DI DI DI DI DI DI DI DI   XI
 271 #elif (CLEVEL >= 7)
 272             SI   DI DI DI DI DI DI DI      XI
 273 #elif (CLEVEL >= 6)
 274             SI   DI DI DI DI DI DI         XI
 275 #elif (CLEVEL >= 5)
 276             SI   DI DI DI DI               XI
 277 #elif (CLEVEL >= 4)
 278             SI   DI DI DI                  XI
 279 #elif (CLEVEL >= 3)
 280             SI   DI DI                     XI
 281 #elif (CLEVEL >= 2)
 282             SI   DI                        XI
 283 #else
 284                                            XI
 285 #endif
 286         }
 287
 288         /* ii now points to the start of the next literal run */
 289         assert(ii == ip);
 290
 291
 292 /*
 293 vi:ts=4:et
 294 */