release/src-rt-6.x.4708/router/lzo/src/lzo1f_9x.c

   1 /* lzo1f_9x.c -- implementation of the LZO1F-999 compression algorithm
   2
   3    This file is part of the LZO real-time data compression library.
   4
   5    Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer
   6    All Rights Reserved.
   7
   8    The LZO library is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2 of
  11    the License, or (at your option) any later version.
  12
  13    The LZO library is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with the LZO library; see the file COPYING.
  20    If not, write to the Free Software Foundation, Inc.,
  21    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  22
  23    Markus F.X.J. Oberhumer
  24    <markus@oberhumer.com>
  25    http://www.oberhumer.com/opensource/lzo/
  26  */
  27
  28
  29 #include "config1f.h"
  30
  31
  32 /***********************************************************************
  33 //
  34 ************************************************************************/
  35
  36 #define SWD_N           16383           /* size of ring buffer */
  37 #define SWD_THRESHOLD       2           /* lower limit for match length */
  38 #define SWD_F            2048           /* upper limit for match length */
  39
  40
  41 #define LZO1F 1
  42 #define LZO_COMPRESS_T  lzo1f_999_t
  43 #define lzo_swd_t       lzo1f_999_swd_t
  44 #include "lzo_mchw.ch"
  45
  46
  47
  48 /***********************************************************************
  49 //
  50 ************************************************************************/
  51
  52 static lzo_bytep
  53 code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off )
  54 {
  55     if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
  56     {
  57         m_off -= 1;
  58         *op++ = LZO_BYTE(((m_len - 2) << 5) | ((m_off & 7) << 2));
  59         *op++ = LZO_BYTE(m_off >> 3);
  60         c->m2_m++;
  61     }
  62     else if (m_len == M2_MIN_LEN && m_off <= 2 * M2_MAX_OFFSET &&
  63              c->r1_lit > 0)
  64     {
  65         assert(m_off > M2_MAX_OFFSET);
  66         m_off -= 1 + M2_MAX_OFFSET;
  67         *op++ = LZO_BYTE(((m_off & 7) << 2));
  68         *op++ = LZO_BYTE(m_off >> 3);
  69         c->r1_r++;
  70     }
  71     else
  72     {
  73         if (m_len <= M3_MAX_LEN)
  74             *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
  75         else
  76         {
  77             m_len -= M3_MAX_LEN;
  78             *op++ = M3_MARKER | 0;
  79             while (m_len > 255)
  80             {
  81                 m_len -= 255;
  82                 *op++ = 0;
  83             }
  84             assert(m_len > 0);
  85             *op++ = LZO_BYTE(m_len);
  86         }
  87         *op++ = LZO_BYTE((m_off & 63) << 2);
  88         *op++ = LZO_BYTE(m_off >> 6);
  89         c->m3_m++;
  90     }
  91
  92     return op;
  93 }
  94
  95
  96 static lzo_bytep
  97 STORE_RUN ( lzo_bytep op, const lzo_bytep ii, lzo_uint t, lzo_bytep out )
  98 {
  99     if (t < 4 && op > out)
 100         op[-2] = LZO_BYTE(op[-2] | t);
 101     else if (t <= 31)
 102         *op++ = LZO_BYTE(t);
 103     else
 104     {
 105         lzo_uint tt = t - 31;
 106
 107         *op++ = 0;
 108         while (tt > 255)
 109         {
 110             tt -= 255;
 111             *op++ = 0;
 112         }
 113         assert(tt > 0);
 114         *op++ = LZO_BYTE(tt);
 115     }
 116     do *op++ = *ii++; while (--t > 0);
 117
 118     return op;
 119 }
 120
 121
 122 /***********************************************************************
 123 // this is a public function, but there is no prototype in a header file
 124 ************************************************************************/
 125
 126 LZO_EXTERN(int)
 127 lzo1f_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
 128                                     lzo_bytep out, lzo_uintp out_len,
 129                                     lzo_voidp wrkmem,
 130                                     lzo_callback_p cb,
 131                                     lzo_uint max_chain );
 132
 133 LZO_PUBLIC(int)
 134 lzo1f_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
 135                                     lzo_bytep out, lzo_uintp out_len,
 136                                     lzo_voidp wrkmem,
 137                                     lzo_callback_p cb,
 138                                     lzo_uint max_chain )
 139 {
 140     lzo_bytep op;
 141     const lzo_bytep ii;
 142     lzo_uint lit;
 143     lzo_uint m_len, m_off;
 144     LZO_COMPRESS_T cc;
 145     LZO_COMPRESS_T * const c = &cc;
 146     lzo_swd_p const swd = (lzo_swd_p) wrkmem;
 147     int r;
 148
 149     /* sanity check */
 150     LZO_COMPILE_TIME_ASSERT(LZO1F_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
 151
 152     c->init = 0;
 153     c->ip = c->in = in;
 154     c->in_end = in + in_len;
 155     c->cb = cb;
 156     c->r1_r = c->m2_m = c->m3_m = 0;
 157
 158     op = out;
 159     ii = c->ip;             /* point to start of literal run */
 160     lit = 0;
 161     c->r1_lit = c->r1_m_len = 0;
 162
 163     r = init_match(c,swd,NULL,0,0);
 164     if (r != 0)
 165         return r;
 166     if (max_chain > 0)
 167         swd->max_chain = max_chain;
 168
 169     r = find_match(c,swd,0,0);
 170     if (r != 0)
 171         return r;
 172     while (c->look > 0)
 173     {
 174         int lazy_match_min_gain = -1;
 175         lzo_uint ahead = 0;
 176
 177         m_len = c->m_len;
 178         m_off = c->m_off;
 179
 180         assert(c->ip - c->look >= in);
 181         if (lit == 0)
 182             ii = c->ip - c->look;
 183         assert(ii + lit == c->ip - c->look);
 184         assert(swd->b_char == *(c->ip - c->look));
 185
 186         if ((m_len < M2_MIN_LEN) ||
 187             (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
 188         {
 189             m_len = 0;
 190         }
 191         else
 192         {
 193             assert(c->ip - c->look - m_off >= in);
 194             assert(c->ip - c->look - m_off + m_len < c->ip);
 195             assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
 196                               m_len) == 0);
 197
 198             if (lit < 3)
 199                 lazy_match_min_gain = 1;
 200             else if (lit == 3)
 201                 lazy_match_min_gain = 3;
 202             else if (lit == 31)
 203                 lazy_match_min_gain = 3;
 204             else
 205                 lazy_match_min_gain = 1;
 206         }
 207
 208         /* try a lazy match */
 209         if (m_len > 0 && lazy_match_min_gain >= 0 && c->look > m_len)
 210         {
 211             r = find_match(c,swd,1,0);
 212             assert(r == 0); LZO_UNUSED(r);
 213             assert(c->look > 0);
 214
 215             if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
 216                 c->m_off > M2_MAX_OFFSET)
 217             {
 218                 lazy_match_min_gain += 1;
 219             }
 220             else if (c->m_len <= M2_MAX_LEN &&
 221                      c->m_off <= M2_MAX_OFFSET &&
 222                      m_off > M2_MAX_OFFSET)
 223             {
 224                 if (lazy_match_min_gain > 0)
 225                     lazy_match_min_gain -= 1;
 226             }
 227             else if (m_len == M2_MIN_LEN && c->m_len == M2_MIN_LEN &&
 228                      c->m_off <= 2 * M2_MAX_OFFSET &&
 229                      m_off > M2_MAX_OFFSET)
 230             {
 231                 if (lazy_match_min_gain > 0)
 232                     lazy_match_min_gain -= 1;
 233             }
 234
 235             if (c->m_len >= m_len + lazy_match_min_gain)
 236             {
 237                 c->lazy++;
 238 #if !defined(NDEBUG)
 239                 m_len = c->m_len;
 240                 m_off = c->m_off;
 241                 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
 242                                   m_len) == 0);
 243 #endif
 244                 lit++;
 245                 assert(ii + lit == c->ip - c->look);
 246                 continue;
 247             }
 248             else
 249             {
 250                 ahead = 1;
 251                 assert(ii + lit + 1 == c->ip - c->look);
 252             }
 253             assert(m_len > 0);
 254         }
 255         assert(ii + lit + ahead == c->ip - c->look);
 256
 257
 258         if (m_len == 0)
 259         {
 260             /* a literal */
 261             lit++;
 262             r = find_match(c,swd,1,0);
 263             assert(r == 0); LZO_UNUSED(r);
 264         }
 265         else
 266         {
 267             /* 1 - store run */
 268             if (lit > 0)
 269             {
 270                 op = STORE_RUN(op,ii,lit,out);
 271                 c->r1_m_len = m_len;
 272                 c->r1_lit = lit;
 273                 lit = 0;
 274             }
 275             else
 276                 c->r1_lit = c->r1_m_len = 0;
 277
 278             /* 2 - code match */
 279             op = code_match(c,op,m_len,m_off);
 280             r = find_match(c,swd,m_len,1+ahead);
 281             assert(r == 0); LZO_UNUSED(r);
 282         }
 283
 284         c->codesize = pd(op, out);
 285     }
 286
 287
 288     /* store final run */
 289     if (lit > 0)
 290         op = STORE_RUN(op,ii,lit,out);
 291
 292 #if defined(LZO_EOF_CODE)
 293     *op++ = M3_MARKER | 1;
 294     *op++ = 0;
 295     *op++ = 0;
 296 #endif
 297
 298     c->codesize = pd(op, out);
 299     assert(c->textsize == in_len);
 300
 301     *out_len = pd(op, out);
 302
 303     if (c->cb && c->cb->nprogress)
 304         (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
 305
 306 #if 0
 307     printf("%ld %ld -> %ld: %ld %ld %ld %ld\n",
 308         (long) c->textsize, (long)in_len, (long) c->codesize,
 309         c->r1_r, c->m2_m, c->m3_m, c->lazy);
 310 #endif
 311     return LZO_E_OK;
 312 }
 313
 314
 315
 316 /***********************************************************************
 317 //
 318 ************************************************************************/
 319
 320 LZO_PUBLIC(int)
 321 lzo1f_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
 322                             lzo_bytep out, lzo_uintp out_len,
 323                             lzo_voidp wrkmem )
 324 {
 325     return lzo1f_999_compress_callback(in,in_len,out,out_len,wrkmem,
 326                                        (lzo_callback_p) 0, 0);
 327 }
 328
 329
 330 /*
 331 vi:ts=4:et
 332 */
 333