release/src/router/lzo/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) 2011 Markus Franz Xaver Johannes Oberhumer
   6    Copyright (C) 2010 Markus Franz Xaver Johannes Oberhumer
   7    Copyright (C) 2009 Markus Franz Xaver Johannes Oberhumer
   8    Copyright (C) 2008 Markus Franz Xaver Johannes Oberhumer
   9    Copyright (C) 2007 Markus Franz Xaver Johannes Oberhumer
  10    Copyright (C) 2006 Markus Franz Xaver Johannes Oberhumer
  11    Copyright (C) 2005 Markus Franz Xaver Johannes Oberhumer
  12    Copyright (C) 2004 Markus Franz Xaver Johannes Oberhumer
  13    Copyright (C) 2003 Markus Franz Xaver Johannes Oberhumer
  14    Copyright (C) 2002 Markus Franz Xaver Johannes Oberhumer
  15    Copyright (C) 2001 Markus Franz Xaver Johannes Oberhumer
  16    Copyright (C) 2000 Markus Franz Xaver Johannes Oberhumer
  17    Copyright (C) 1999 Markus Franz Xaver Johannes Oberhumer
  18    Copyright (C) 1998 Markus Franz Xaver Johannes Oberhumer
  19    Copyright (C) 1997 Markus Franz Xaver Johannes Oberhumer
  20    Copyright (C) 1996 Markus Franz Xaver Johannes Oberhumer
  21    All Rights Reserved.
  22
  23    The LZO library is free software; you can redistribute it and/or
  24    modify it under the terms of the GNU General Public License as
  25    published by the Free Software Foundation; either version 2 of
  26    the License, or (at your option) any later version.
  27
  28    The LZO library is distributed in the hope that it will be useful,
  29    but WITHOUT ANY WARRANTY; without even the implied warranty of
  30    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31    GNU General Public License for more details.
  32
  33    You should have received a copy of the GNU General Public License
  34    along with the LZO library; see the file COPYING.
  35    If not, write to the Free Software Foundation, Inc.,
  36    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  37
  38    Markus F.X.J. Oberhumer
  39    <markus@oberhumer.com>
  40    http://www.oberhumer.com/opensource/lzo/
  41  */
  42
  43
  44 #include "lzo_conf.h"
  45 #include "lzo/lzo1f.h"
  46
  47
  48 /***********************************************************************
  49 //
  50 ************************************************************************/
  51
  52 #define M2_MAX_OFFSET   0x0800
  53 #define M3_MAX_OFFSET   0x3fff
  54 #define M3_MARKER       224
  55
  56
  57 #ifndef LZO_HASH
  58 #define LZO_HASH        LZO_HASH_LZO_INCREMENTAL_A
  59 #endif
  60 #define D_BITS          14
  61 #define D_INDEX1(d,p)   d = DM(DMUL(0x21,DX3(p,5,5,6)) >> 5)
  62 #define D_INDEX2(d,p)   d = (d & (D_MASK & 0x7ff)) ^ (D_HIGH | 0x1f)
  63 #include "lzo_dict.h"
  64
  65
  66 /***********************************************************************
  67 // compress a block of data.
  68 ************************************************************************/
  69
  70 static __lzo_noinline
  71 int do_compress          ( const lzo_bytep in , lzo_uint  in_len,
  72                                  lzo_bytep out, lzo_uintp out_len,
  73                                  lzo_voidp wrkmem )
  74 {
  75     register const lzo_bytep ip;
  76     lzo_bytep op;
  77     const lzo_bytep const in_end = in + in_len;
  78     const lzo_bytep const ip_end = in + in_len - 9;
  79     const lzo_bytep ii;
  80     lzo_dict_p const dict = (lzo_dict_p) wrkmem;
  81
  82     op = out;
  83     ip = in;
  84     ii = ip;
  85
  86     ip++;
  87     for (;;)
  88     {
  89         register const lzo_bytep m_pos;
  90         LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0);
  91         lzo_uint m_len;
  92         lzo_uint dindex;
  93         lzo_uint lit;
  94
  95         DINDEX1(dindex,ip);
  96         GINDEX(m_pos,m_off,dict,dindex,in);
  97         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
  98             goto literal;
  99 #if 1
 100         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
 101             goto try_match;
 102         DINDEX2(dindex,ip);
 103 #endif
 104         GINDEX(m_pos,m_off,dict,dindex,in);
 105         if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M3_MAX_OFFSET))
 106             goto literal;
 107         if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3])
 108             goto try_match;
 109         goto literal;
 110
 111
 112 try_match:
 113 #if 0 && defined(LZO_UNALIGNED_OK_2)
 114         if (UA_GET16(m_pos) != UA_GET16(ip))
 115 #else
 116         if (m_pos[0] != ip[0] || m_pos[1] != ip[1])
 117 #endif
 118         {
 119         }
 120         else
 121         {
 122             if (m_pos[2] == ip[2])
 123             {
 124                 m_pos += 3;
 125 #if 0
 126                 if (m_off <= M2_MAX_OFFSET)
 127                     goto match;
 128                 if (lit <= 3)
 129                     goto match;
 130                 if (lit == 3)           /* better compression, but slower */
 131                 {
 132                     assert(op - 2 > out); op[-2] |= LZO_BYTE(3);
 133                     *op++ = *ii++; *op++ = *ii++; *op++ = *ii++;
 134                     goto code_match;
 135                 }
 136                 if (*m_pos == ip[3])
 137 #endif
 138                     goto match;
 139             }
 140         }
 141
 142
 143     /* a literal */
 144 literal:
 145         UPDATE_I(dict,0,dindex,ip,in);
 146         if (++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         lit = pd(ip,ii);
 156         if (lit > 0)
 157         {
 158             register lzo_uint t = lit;
 159
 160             if (t < 4 && op > out)
 161                 op[-2] |= LZO_BYTE(t);
 162             else if (t <= 31)
 163                 *op++ = LZO_BYTE(t);
 164             else
 165             {
 166                 register lzo_uint tt = t - 31;
 167
 168                 *op++ = 0;
 169                 while (tt > 255)
 170                 {
 171                     tt -= 255;
 172                     *op++ = 0;
 173                 }
 174                 assert(tt > 0);
 175                 *op++ = LZO_BYTE(tt);
 176             }
 177             do *op++ = *ii++; while (--t > 0);
 178         }
 179         assert(ii == ip);
 180
 181
 182         /* code the match */
 183         ip += 3;
 184         if (*m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++ ||
 185             *m_pos++ != *ip++ || *m_pos++ != *ip++ || *m_pos++ != *ip++)
 186         {
 187             --ip;
 188             m_len = pd(ip, ii);
 189             assert(m_len >= 3); assert(m_len <= 8);
 190
 191             if (m_off <= M2_MAX_OFFSET)
 192             {
 193                 m_off -= 1;
 194                 *op++ = LZO_BYTE(((m_len - 2) << 5) | ((m_off & 7) << 2));
 195                 *op++ = LZO_BYTE(m_off >> 3);
 196             }
 197             else if (m_len == 3 && m_off <= 2*M2_MAX_OFFSET && lit > 0)
 198             {
 199                 m_off -= 1;
 200                 /* m_off -= M2_MAX_OFFSET; */
 201                 *op++ = LZO_BYTE(((m_off & 7) << 2));
 202                 *op++ = LZO_BYTE(m_off >> 3);
 203             }
 204             else
 205             {
 206                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 207                 *op++ = LZO_BYTE((m_off & 63) << 2);
 208                 *op++ = LZO_BYTE(m_off >> 6);
 209             }
 210         }
 211         else
 212         {
 213             {
 214                 const lzo_bytep end;
 215                 end = in_end;
 216                 while (ip < end && *m_pos == *ip)
 217                     m_pos++, ip++;
 218                 m_len = pd(ip, ii);
 219             }
 220             assert(m_len >= 3);
 221
 222             if (m_len <= 33)
 223                 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
 224             else
 225             {
 226                 m_len -= 33;
 227                 *op++ = M3_MARKER | 0;
 228                 while (m_len > 255)
 229                 {
 230                     m_len -= 255;
 231                     *op++ = 0;
 232                 }
 233                 assert(m_len > 0);
 234                 *op++ = LZO_BYTE(m_len);
 235             }
 236             *op++ = LZO_BYTE((m_off & 63) << 2);
 237             *op++ = LZO_BYTE(m_off >> 6);
 238         }
 239
 240         ii = ip;
 241         if (ip >= ip_end)
 242             break;
 243     }
 244
 245
 246     /* store final literal run */
 247     if (pd(in_end,ii) > 0)
 248     {
 249         register lzo_uint t = pd(in_end,ii);
 250
 251         if (t < 4 && op > out)
 252             op[-2] |= LZO_BYTE(t);
 253         else if (t <= 31)
 254             *op++ = LZO_BYTE(t);
 255         else
 256         {
 257             register lzo_uint tt = t - 31;
 258
 259             *op++ = 0;
 260             while (tt > 255)
 261             {
 262                 tt -= 255;
 263                 *op++ = 0;
 264             }
 265             assert(tt > 0);
 266             *op++ = LZO_BYTE(tt);
 267         }
 268         do *op++ = *ii++; while (--t > 0);
 269     }
 270
 271     *out_len = pd(op, out);
 272     return LZO_E_OK;
 273 }
 274
 275
 276 /***********************************************************************
 277 // public entry point
 278 ************************************************************************/
 279
 280 LZO_PUBLIC(int)
 281 lzo1f_1_compress ( const lzo_bytep in , lzo_uint  in_len,
 282                          lzo_bytep out, lzo_uintp out_len,
 283                          lzo_voidp wrkmem )
 284 {
 285     lzo_bytep op = out;
 286     int r = LZO_E_OK;
 287
 288     if (in_len == 0)
 289         *out_len = 0;
 290     else if (in_len <= 10)
 291     {
 292         *op++ = LZO_BYTE(in_len);
 293         do *op++ = *in++; while (--in_len > 0);
 294         *out_len = pd(op, out);
 295     }
 296     else
 297         r = do_compress(in,in_len,out,out_len,wrkmem);
 298
 299     if (r == LZO_E_OK)
 300     {
 301         op = out + *out_len;
 302         op[0] = M3_MARKER | 1;
 303         op[1] = 0;
 304         op[2] = 0;
 305         *out_len += 3;
 306     }
 307
 308     return r;
 309 }
 310
 311
 312 /*
 313 vi:ts=4:et
 314 */
 315