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