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) 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 "config1f.h"
  42
  43
  44 /***********************************************************************
  45 //
  46 ************************************************************************/
  47
  48 #define N           16383           /* size of ring buffer */
  49 #define THRESHOLD       2           /* lower limit for match length */
  50 #define F            2048           /* upper limit for match length */
  51
  52
  53 #define LZO1F
  54 #define LZO_COMPRESS_T  lzo1f_999_t
  55 #define lzo_swd_t       lzo1f_999_swd_t
  56 #include "lzo_mchw.ch"
  57
  58
  59
  60 /***********************************************************************
  61 //
  62 ************************************************************************/
  63
  64 static lzo_bytep
  65 code_match ( LZO_COMPRESS_T *c, lzo_bytep op, lzo_uint m_len, lzo_uint m_off )
  66 {
  67     if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET)
  68     {
  69         m_off -= 1;
  70         *op++ = LZO_BYTE(((m_len - 2) << 5) | ((m_off & 7) << 2));
  71         *op++ = LZO_BYTE(m_off >> 3);
  72         c->m2_m++;
  73     }
  74     else if (m_len == M2_MIN_LEN && m_off <= 2 * M2_MAX_OFFSET &&
  75              c->r1_lit > 0)
  76     {
  77         assert(m_off > M2_MAX_OFFSET);
  78         m_off -= 1 + M2_MAX_OFFSET;
  79         *op++ = LZO_BYTE(((m_off & 7) << 2));
  80         *op++ = LZO_BYTE(m_off >> 3);
  81         c->r1_r++;
  82     }
  83     else
  84     {
  85         if (m_len <= M3_MAX_LEN)
  86             *op++ = LZO_BYTE(M3_MARKER | (m_len - 2));
  87         else
  88         {
  89             m_len -= M3_MAX_LEN;
  90             *op++ = M3_MARKER | 0;
  91             while (m_len > 255)
  92             {
  93                 m_len -= 255;
  94                 *op++ = 0;
  95             }
  96             assert(m_len > 0);
  97             *op++ = LZO_BYTE(m_len);
  98         }
  99         *op++ = LZO_BYTE((m_off & 63) << 2);
 100         *op++ = LZO_BYTE(m_off >> 6);
 101         c->m3_m++;
 102     }
 103
 104     return op;
 105 }
 106
 107
 108 static lzo_bytep
 109 STORE_RUN ( lzo_bytep op, const lzo_bytep ii, lzo_uint t, lzo_bytep out )
 110 {
 111     if (t < 4 && op > out)
 112         op[-2] |= LZO_BYTE(t);
 113     else if (t <= 31)
 114         *op++ = LZO_BYTE(t);
 115     else
 116     {
 117         lzo_uint tt = t - 31;
 118
 119         *op++ = 0;
 120         while (tt > 255)
 121         {
 122             tt -= 255;
 123             *op++ = 0;
 124         }
 125         assert(tt > 0);
 126         *op++ = LZO_BYTE(tt);
 127     }
 128     do *op++ = *ii++; while (--t > 0);
 129
 130     return op;
 131 }
 132
 133
 134 /***********************************************************************
 135 // this is a public function, but there is no prototype in a header file
 136 ************************************************************************/
 137
 138 LZO_EXTERN(int)
 139 lzo1f_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
 140                                     lzo_bytep out, lzo_uintp out_len,
 141                                     lzo_voidp wrkmem,
 142                                     lzo_callback_p cb,
 143                                     lzo_uint max_chain );
 144
 145 LZO_PUBLIC(int)
 146 lzo1f_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
 147                                     lzo_bytep out, lzo_uintp out_len,
 148                                     lzo_voidp wrkmem,
 149                                     lzo_callback_p cb,
 150                                     lzo_uint max_chain )
 151 {
 152     lzo_bytep op;
 153     const lzo_bytep ii;
 154     lzo_uint lit;
 155     lzo_uint m_len, m_off;
 156     LZO_COMPRESS_T cc;
 157     LZO_COMPRESS_T * const c = &cc;
 158     lzo_swd_p const swd = (lzo_swd_p) wrkmem;
 159     int r;
 160
 161     /* sanity check */
 162     LZO_COMPILE_TIME_ASSERT(LZO1F_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
 163
 164     c->init = 0;
 165     c->ip = c->in = in;
 166     c->in_end = in + in_len;
 167     c->cb = cb;
 168     c->r1_r = c->m2_m = c->m3_m = 0;
 169
 170     op = out;
 171     ii = c->ip;             /* point to start of literal run */
 172     lit = 0;
 173     c->r1_lit = c->r1_m_len = 0;
 174
 175     r = init_match(c,swd,NULL,0,0);
 176     if (r != 0)
 177         return r;
 178     if (max_chain > 0)
 179         swd->max_chain = max_chain;
 180
 181     r = find_match(c,swd,0,0);
 182     if (r != 0)
 183         return r;
 184     while (c->look > 0)
 185     {
 186         int lazy_match_min_gain = -1;
 187         lzo_uint ahead = 0;
 188
 189         m_len = c->m_len;
 190         m_off = c->m_off;
 191
 192         assert(c->ip - c->look >= in);
 193         if (lit == 0)
 194             ii = c->ip - c->look;
 195         assert(ii + lit == c->ip - c->look);
 196         assert(swd->b_char == *(c->ip - c->look));
 197
 198         if ((m_len < M2_MIN_LEN) ||
 199             (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
 200         {
 201             m_len = 0;
 202         }
 203         else
 204         {
 205             assert(c->ip - c->look - m_off >= in);
 206             assert(c->ip - c->look - m_off + m_len < c->ip);
 207             assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
 208                               m_len) == 0);
 209
 210             if (lit < 3)
 211                 lazy_match_min_gain = 1;
 212             else if (lit == 3)
 213                 lazy_match_min_gain = 3;
 214             else if (lit == 31)
 215                 lazy_match_min_gain = 3;
 216             else
 217                 lazy_match_min_gain = 1;
 218         }
 219
 220         /* try a lazy match */
 221         if (m_len > 0 && lazy_match_min_gain >= 0 && c->look > m_len)
 222         {
 223             r = find_match(c,swd,1,0);
 224             assert(r == 0);
 225             assert(c->look > 0);
 226
 227             if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
 228                 c->m_off > M2_MAX_OFFSET)
 229             {
 230                 lazy_match_min_gain += 1;
 231             }
 232             else if (c->m_len <= M2_MAX_LEN &&
 233                      c->m_off <= M2_MAX_OFFSET &&
 234                      m_off > M2_MAX_OFFSET)
 235             {
 236                 if (lazy_match_min_gain > 0)
 237                     lazy_match_min_gain -= 1;
 238             }
 239             else if (m_len == M2_MIN_LEN && c->m_len == M2_MIN_LEN &&
 240                      c->m_off <= 2 * M2_MAX_OFFSET &&
 241                      m_off > M2_MAX_OFFSET)
 242             {
 243                 if (lazy_match_min_gain > 0)
 244                     lazy_match_min_gain -= 1;
 245             }
 246
 247             if (c->m_len >= m_len + lazy_match_min_gain)
 248             {
 249                 c->lazy++;
 250 #if !defined(NDEBUG)
 251                 m_len = c->m_len;
 252                 m_off = c->m_off;
 253                 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
 254                                   m_len) == 0);
 255 #endif
 256                 lit++;
 257                 assert(ii + lit == c->ip - c->look);
 258                 continue;
 259             }
 260             else
 261             {
 262                 ahead = 1;
 263                 assert(ii + lit + 1 == c->ip - c->look);
 264             }
 265             assert(m_len > 0);
 266         }
 267         assert(ii + lit + ahead == c->ip - c->look);
 268
 269
 270         if (m_len == 0)
 271         {
 272             /* a literal */
 273             lit++;
 274             r = find_match(c,swd,1,0);
 275             assert(r == 0);
 276         }
 277         else
 278         {
 279             /* 1 - store run */
 280             if (lit > 0)
 281             {
 282                 op = STORE_RUN(op,ii,lit,out);
 283                 c->r1_m_len = m_len;
 284                 c->r1_lit = lit;
 285                 lit = 0;
 286             }
 287             else
 288                 c->r1_lit = c->r1_m_len = 0;
 289
 290             /* 2 - code match */
 291             op = code_match(c,op,m_len,m_off);
 292             r = find_match(c,swd,m_len,1+ahead);
 293             assert(r == 0);
 294         }
 295
 296         c->codesize = pd(op, out);
 297     }
 298
 299
 300     /* store final run */
 301     if (lit > 0)
 302         op = STORE_RUN(op,ii,lit,out);
 303
 304 #if defined(LZO_EOF_CODE)
 305     *op++ = M3_MARKER | 1;
 306     *op++ = 0;
 307     *op++ = 0;
 308 #endif
 309
 310     c->codesize = pd(op, out);
 311     assert(c->textsize == in_len);
 312
 313     *out_len = pd(op, out);
 314
 315     if (c->cb && c->cb->nprogress)
 316         (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
 317
 318 #if 0
 319     printf("%ld %ld -> %ld: %ld %ld %ld %ld\n",
 320         (long) c->textsize, (long)in_len, (long) c->codesize,
 321         c->r1_r, c->m2_m, c->m3_m, c->lazy);
 322 #endif
 323     return LZO_E_OK;
 324 }
 325
 326
 327
 328 /***********************************************************************
 329 //
 330 ************************************************************************/
 331
 332 LZO_PUBLIC(int)
 333 lzo1f_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
 334                             lzo_bytep out, lzo_uintp out_len,
 335                             lzo_voidp wrkmem )
 336 {
 337     return lzo1f_999_compress_callback(in,in_len,out,out_len,wrkmem,
 338                                        (lzo_callback_p) 0, 0);
 339 }
 340
 341
 342 /*
 343 vi:ts=4:et
 344 */
 345