src/lzo1f_1.c

   1 /* lzo1f_1.c -- implementation of the LZO1F-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 #include "lzo_conf.h"
  42 #include "lzo/lzo1f.h"
  43
  44
  45 /***********************************************************************
  46 //
  47 ************************************************************************/
  48
  49 #define M2_MAX_OFFSET   0x0800
  50 #define M3_MAX_OFFSET   0x3fff
  51 #define M3_MARKER       224
  52
  53
  54 #ifndef LZO_HASH
  55 #define LZO_HASH        LZO_HASH_LZO_INCREMENTAL_A
  56 #endif
  57 #define D_BITS          14
  58 #define D_INDEX1(d,p)   d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5)
  59 #define D_INDEX2(d,p)   d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
  60 #include "lzo_dict.h"
  61
  62
  63 /***********************************************************************
  64 // compress a block of data.
  65 ************************************************************************/
  66
  67 static __lzo_noinline
  68 int do_compress          ( const lzo_bytep in , lzo_uint  in_len,
  69                                  lzo_bytep out, lzo_uintp out_len,
  70                                  lzo_voidp wrkmem )
  71 {
  72     register const lzo_bytep ip;
  73     lzo_bytep op;
  74     const lzo_bytep const in_end = in + in_len;
  75     const lzo_bytep const ip_end = in + in_len - 9;
  76     const lzo_bytep ii;
  77     lzo_dict_p const dict = (lzo_dict_p) wrkmem;
  78
  79     op = out;
  80     ip = in;
  81     ii = ip;
  82
  83     ip++;
  84     for (;;)
  85     {
  86         register const lzo_bytep m_pos;
  87         lzo_uint m_off;
  88         lzo_uint m_len;
  89         lzo_uint dindex;
  90         lzo_uint lit;
  91
  92         DINDEX1(dindex,ip);
  93         GINDEX(m_pos,m_off,dict,dindex,in);
  94         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
  95             goto literal;
  96 #if 1
  97         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
  98             goto try_match;
  99         DINDEX2(dindex,ip);
 100 #endif
 101         GINDEX(m_pos,m_off,dict,dindex,in);
 102         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
 103             goto literal;
 104         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
 105             goto try_match;
 106         goto literal;
 107
 108
 109 try_match:
 110 #if 0 && defined(LZO_UNALIGNED_OK_2)
 111         if (* (const lzo_ushortp) m_pos != * (const lzo_ushortp) ip)
 112 #else
 113         if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
 114 #endif
 115         {
 116         }
 117         else
 118         {
 119             if (m_pos[2] == ip[2])
 120             {
 121                 m_pos += 3;
 122 #if 0
 123                 if (m_off <= M2_MAX_OFFSET)
 124                     goto match;
 125                 if (lit <= 3)
 126                     goto match;
 127                 if (lit == 3)           /* better compression, but slower */
 128                 {
 129                     assert(op - 2 > out); op[-2] |= LZO_BYTE(3);
 130                     *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
 131                     goto code_match;
 132                 }
 133                 if (*m_pos == ip[3])
 134 #endif
 135                     goto match;
 136             }
 137         }
 138
 139
 140     /* a literal */
 141 literal:
 142         UPDATE_I(dict,0,dindex,ip,in);
 143         if (++ip >= ip_end)
 144             break;
 145         continue;
 146
 147
 148     /* a match */
 149 match:
 150         UPDATE_I(dict,0,dindex,ip,in);
 151         /* store current literal run */
 152         lit = pd(ip,ii);
 153         if (lit > 0)
 154         {
 155             register lzo_uint t = lit;
 156
 157             if (t < 4 && op > out)
 158                 op[-2] |= LZO_BYTE(t);
 159             else if (t <= 31)
 160                 *op++ = LZO_BYTE(t);
 161             else
 162             {
 163                 register lzo_uint tt = t - 31;
 164
 165                 *op++ = 0;
 166                 while (tt > 255)
 167                 {
 168                     tt -= 255;
 169                     *op++ = 0;
 170                 }
 171                 assert(tt > 0);
 172                 *op++ = LZO_BYTE(tt);
 173             }
 174             do *op++ = *ii++; while (--t > 0);
 175         }
 176         assert(ii == ip);
 177
 178
 179         /* code the match */
 180         ip += 3;
 181         if (*m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++ ||
 182             *m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++)
 183         {
 184             --ip;
 185             m_len = pd(ip, ii);
 186             assert(m_len >= 3); assert(m_len <= 8);
 187
 188             if (m_off <= M2_MAX_OFFSET)
 189             {
 190                 m_off -= 1;
 191                 *op++ = LZO_BYTE(((m_len - 2) << 5) | ((m_off & 7) << 2));
 192                 *op++ = LZO_BYTE(m_off >> 3);
 193             }
 194             else if (m_len == 3 && m_off <= 2*M2_MAX_OFFSET && lit > 0)
 195             {
 196                 m_off -= 1;
 197                 /* m_off -= M2_MAX_OFFSET; */
 198                 *op++ = LZO_BYTE(((m_off & 7) << 2));
 199                 *op++ = LZO_BYTE(m_off >> 3);
 200             }
 201             else
 202             {
 203                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 204                 *op++ = LZO_BYTE((m_off & 63) << 2);
 205                 *op++ = LZO_BYTE(m_off >> 6);
 206             }
 207         }
 208         else
 209         {
 210             {
 211                 const lzo_bytep end;
 212                 end = in_end;
 213                 while (ip < end && *m_pos == *ip)
 214                     m_pos++, ip++;
 215                 m_len = pd(ip, ii);
 216             }
 217             assert(m_len >= 3);
 218
 219             if (m_len <= 33)
 220                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 221             else
 222             {
 223                 m_len -= 33;
 224                 *op++ = M3_MARKER | 0;
 225                 while (m_len > 255)
 226                 {
 227                     m_len -= 255;
 228                     *op++ = 0;
 229                 }
 230                 assert(m_len > 0);
 231                 *op++ = LZO_BYTE(m_len);
 232             }
 233             *op++ = LZO_BYTE((m_off & 63) << 2);
 234             *op++ = LZO_BYTE(m_off >> 6);
 235         }
 236
 237         ii = ip;
 238         if (ip >= ip_end)
 239             break;
 240     }
 241
 242
 243     /* store final literal run */
 244     if (pd(in_end,ii) > 0)
 245     {
 246         register lzo_uint t = pd(in_end,ii);
 247
 248         if (t < 4 && op > out)
 249             op[-2] |= LZO_BYTE(t);
 250         else if (t <= 31)
 251             *op++ = LZO_BYTE(t);
 252         else
 253         {
 254             register lzo_uint tt = t - 31;
 255
 256             *op++ = 0;
 257             while (tt > 255)
 258             {
 259                 tt -= 255;
 260                 *op++ = 0;
 261             }
 262             assert(tt > 0);
 263             *op++ = LZO_BYTE(tt);
 264         }
 265         do *op++ = *ii++; while (--t > 0);
 266     }
 267
 268     *out_len = pd(op, out);
 269     return LZO_E_OK;
 270 }
 271
 272
 273 /***********************************************************************
 274 // public entry point
 275 ************************************************************************/
 276
 277 LZO_PUBLIC(int)
 278 lzo1f_1_compress ( const lzo_bytep in , lzo_uint  in_len,
 279                          lzo_bytep out, lzo_uintp out_len,
 280                          lzo_voidp wrkmem )
 281 {
 282     lzo_bytep op = out;
 283     int r = LZO_E_OK;
 284
 285     if (in_len <= 0)
 286         *out_len = 0;
 287     else if (in_len <= 10)
 288     {
 289         *op++ = LZO_BYTE(in_len);
 290         do *op++ = *in++; while (--in_len > 0);
 291         *out_len = pd(op, out);
 292     }
 293     else
 294         r = do_compress(in,in_len,out,out_len,wrkmem);
 295
 296     if (r == LZO_E_OK)
 297     {
 298         op = out + *out_len;
 299         *op++ = M3_MARKER | 1;
 300         *op++ = 0;
 301         *op++ = 0;
 302         *out_len += 3;
 303     }
 304
 305     return r;
 306 }
 307
 308
 309 /*
 310 vi:ts=4:et
 311 */
 312