lzo/src/lzo1x_c.ch

   1 /* lzo1x_c.ch -- implementation of the LZO1[XY]-1 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
  42 /***********************************************************************
  43 // compress a block of data.
  44 ************************************************************************/
  45
  46 static __lzo_noinline lzo_uint
  47 do_compress ( const lzo_bytep in , lzo_uint  in_len,
  48                     lzo_bytep out, lzo_uintp out_len,
  49                     lzo_voidp wrkmem )
  50 {
  51     register const lzo_bytep ip;
  52     lzo_bytep op;
  53     const lzo_bytep const in_end = in + in_len;
  54     const lzo_bytep const ip_end = in + in_len - M2_MAX_LEN - 5;
  55     const lzo_bytep ii;
  56     lzo_dict_p const dict = (lzo_dict_p) wrkmem;
  57
  58     op = out;
  59     ip = in;
  60     ii = ip;
  61
  62     ip += 4;
  63     for (;;)
  64     {
  65         register const lzo_bytep m_pos;
  66         lzo_uint m_off;
  67         lzo_uint m_len;
  68         lzo_uint dindex;
  69
  70         DINDEX1(dindex,ip);
  71         GINDEX(m_pos,m_off,dict,dindex,in);
  72         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
  73             goto literal;
  74 #if 1
  75         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
  76             goto try_match;
  77         DINDEX2(dindex,ip);
  78 #endif
  79         GINDEX(m_pos,m_off,dict,dindex,in);
  80         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET))
  81             goto literal;
  82         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
  83             goto try_match;
  84         goto literal;
  85
  86
  87 try_match:
  88 #if 1 && defined(LZO_UNALIGNED_OK_2)
  89         if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
  90 #else
  91         if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
  92 #endif
  93         {
  94         }
  95         else
  96         {
  97             if __lzo_likely(m_pos[2] == ip[2])
  98             {
  99 #if 0
 100                 if (m_off <= M2_MAX_OFFSET)
 101                     goto match;
 102                 if (lit <= 3)
 103                     goto match;
 104                 if (lit == 3)           /* better compression, but slower */
 105                 {
 106                     assert(op - 2 > out); op[-2] |= LZO_BYTE(3);
 107                     *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
 108                     goto code_match;
 109                 }
 110                 if (m_pos[3] == ip[3])
 111 #endif
 112                     goto match;
 113             }
 114             else
 115             {
 116                 /* still need a better way for finding M1 matches */
 117 #if 0
 118                 /* a M1 match */
 119 #if 0
 120                 if (m_off <= M1_MAX_OFFSET && lit > 0 && lit <= 3)
 121 #else
 122                 if (m_off <= M1_MAX_OFFSET && lit == 3)
 123 #endif
 124                 {
 125                     register lzo_uint t;
 126
 127                     t = lit;
 128                     assert(op - 2 > out); op[-2] |= LZO_BYTE(t);
 129                     do *op++ = *ii++; while (--t > 0);
 130                     assert(ii == ip);
 131                     m_off -= 1;
 132                     *op++ = LZO_BYTE(M1_MARKER | ((m_off & 3) << 2));
 133                     *op++ = LZO_BYTE(m_off >> 2);
 134                     ip += 2;
 135                     goto match_done;
 136                 }
 137 #endif
 138             }
 139         }
 140
 141
 142     /* a literal */
 143 literal:
 144         UPDATE_I(dict,0,dindex,ip,in);
 145         ++ip;
 146         if __lzo_unlikely(ip >= ip_end)
 147             break;
 148         continue;
 149
 150
 151     /* a match */
 152 match:
 153         UPDATE_I(dict,0,dindex,ip,in);
 154         /* store current literal run */
 155         if (pd(ip,ii) > 0)
 156         {
 157             register lzo_uint t = pd(ip,ii);
 158
 159             if (t <= 3)
 160             {
 161                 assert(op - 2 > out);
 162                 op[-2] |= LZO_BYTE(t);
 163             }
 164             else if (t <= 18)
 165                 *op++ = LZO_BYTE(t - 3);
 166             else
 167             {
 168                 register lzo_uint tt = t - 18;
 169
 170                 *op++ = 0;
 171                 while (tt > 255)
 172                 {
 173                     tt -= 255;
 174                     *op++ = 0;
 175                 }
 176                 assert(tt > 0);
 177                 *op++ = LZO_BYTE(tt);
 178             }
 179             do *op++ = *ii++; while (--t > 0);
 180         }
 181
 182         /* code the match */
 183         assert(ii == ip);
 184         ip += 3;
 185         if (m_pos[3] != *ip++ || m_pos[4] != *ip++ || m_pos[5] != *ip++ ||
 186             m_pos[6] != *ip++ || m_pos[7] != *ip++ || m_pos[8] != *ip++
 187 #ifdef LZO1Y
 188             || m_pos[ 9] != *ip++ || m_pos[10] != *ip++ || m_pos[11] != *ip++
 189             || m_pos[12] != *ip++ || m_pos[13] != *ip++ || m_pos[14] != *ip++
 190 #endif
 191            )
 192         {
 193             --ip;
 194             m_len = pd(ip, ii);
 195             assert(m_len >= 3); assert(m_len <= M2_MAX_LEN);
 196
 197             if (m_off <= M2_MAX_OFFSET)
 198             {
 199                 m_off -= 1;
 200 #if defined(LZO1X)
 201                 *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2));
 202                 *op++ = LZO_BYTE(m_off >> 3);
 203 #elif defined(LZO1Y)
 204                 *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2));
 205                 *op++ = LZO_BYTE(m_off >> 2);
 206 #endif
 207             }
 208             else if (m_off <= M3_MAX_OFFSET)
 209             {
 210                 m_off -= 1;
 211                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 212                 goto m3_m4_offset;
 213             }
 214             else
 215 #if defined(LZO1X)
 216             {
 217                 m_off -= 0x4000;
 218                 assert(m_off > 0); assert(m_off <= 0x7fff);
 219                 *op++ = LZO_BYTE(M4_MARKER |
 220                                  ((m_off & 0x4000) >> 11) | (m_len - 2));
 221                 goto m3_m4_offset;
 222             }
 223 #elif defined(LZO1Y)
 224                 goto m4_match;
 225 #endif
 226         }
 227         else
 228         {
 229             {
 230                 const lzo_bytep end = in_end;
 231                 const lzo_bytep m = m_pos + M2_MAX_LEN + 1;
 232                 while (ip < end && *m == *ip)
 233                     m++, ip++;
 234                 m_len = pd(ip, ii);
 235             }
 236             assert(m_len > M2_MAX_LEN);
 237
 238             if (m_off <= M3_MAX_OFFSET)
 239             {
 240                 m_off -= 1;
 241                 if (m_len <= 33)
 242                     *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 243                 else
 244                 {
 245                     m_len -= 33;
 246                     *op++ = M3_MARKER | 0;
 247                     goto m3_m4_len;
 248                 }
 249             }
 250             else
 251             {
 252 #if defined(LZO1Y)
 253 m4_match:
 254 #endif
 255                 m_off -= 0x4000;
 256                 assert(m_off > 0); assert(m_off <= 0x7fff);
 257                 if (m_len <= M4_MAX_LEN)
 258                     *op++ = LZO_BYTE(M4_MARKER |
 259                                      ((m_off & 0x4000) >> 11) | (m_len - 2));
 260                 else
 261                 {
 262                     m_len -= M4_MAX_LEN;
 263                     *op++ = LZO_BYTE(M4_MARKER | ((m_off & 0x4000) >> 11));
 264 m3_m4_len:
 265                     while (m_len > 255)
 266                     {
 267                         m_len -= 255;
 268                         *op++ = 0;
 269                     }
 270                     assert(m_len > 0);
 271                     *op++ = LZO_BYTE(m_len);
 272                 }
 273             }
 274
 275 m3_m4_offset:
 276             *op++ = LZO_BYTE((m_off & 63) << 2);
 277             *op++ = LZO_BYTE(m_off >> 6);
 278         }
 279
 280 #if 0
 281 match_done:
 282 #endif
 283         ii = ip;
 284         if __lzo_unlikely(ip >= ip_end)
 285             break;
 286     }
 287
 288     *out_len = pd(op, out);
 289     return pd(in_end,ii);
 290 }
 291
 292
 293 /***********************************************************************
 294 // public entry point
 295 ************************************************************************/
 296
 297 LZO_PUBLIC(int)
 298 DO_COMPRESS      ( const lzo_bytep in , lzo_uint  in_len,
 299                          lzo_bytep out, lzo_uintp out_len,
 300                          lzo_voidp wrkmem )
 301 {
 302     lzo_bytep op = out;
 303     lzo_uint t;
 304
 305     if __lzo_unlikely(in_len <= M2_MAX_LEN + 5)
 306         t = in_len;
 307     else
 308     {
 309         t = do_compress(in,in_len,op,out_len,wrkmem);
 310         op += *out_len;
 311     }
 312
 313     if (t > 0)
 314     {
 315         const lzo_bytep ii = in + in_len - t;
 316
 317         if (op == out && t <= 238)
 318             *op++ = LZO_BYTE(17 + t);
 319         else if (t <= 3)
 320             op[-2] |= LZO_BYTE(t);
 321         else if (t <= 18)
 322             *op++ = LZO_BYTE(t - 3);
 323         else
 324         {
 325             lzo_uint tt = t - 18;
 326
 327             *op++ = 0;
 328             while (tt > 255)
 329             {
 330                 tt -= 255;
 331                 *op++ = 0;
 332             }
 333             assert(tt > 0);
 334             *op++ = LZO_BYTE(tt);
 335         }
 336         do *op++ = *ii++; while (--t > 0);
 337     }
 338
 339     *op++ = M4_MARKER | 1;
 340     *op++ = 0;
 341     *op++ = 0;
 342
 343     *out_len = pd(op, out);
 344     return LZO_E_OK;
 345 }
 346
 347
 348 /*
 349 vi:ts=4:et
 350 */
 351