src/lzo1c_9x.c

   1 /* lzo1c_9x.c -- implementation of the LZO1C-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 "config1c.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 LZO1C
  54 #define LZO_COMPRESS_T  lzo1c_999_t
  55 #define lzo_swd_t       lzo1c_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         assert(m_len >= M2_MIN_LEN);
  70         assert(m_off >= M2_MIN_OFFSET);
  71
  72         m_off -= M2_MIN_OFFSET;
  73         /* code match len + low offset bits */
  74         *op++ = LZO_BYTE(((m_len - (M2_MIN_LEN - 2)) << M2O_BITS) |
  75                           (m_off & M2O_MASK));
  76         /* code high offset bits */
  77         *op++ = LZO_BYTE(m_off >> M2O_BITS);
  78         c->m2_m++;
  79     }
  80     else
  81     {
  82         assert(m_len >= M3_MIN_LEN);
  83         assert(m_off <= M3_MAX_OFFSET);
  84
  85         m_off -= M3_MIN_OFFSET - M3_EOF_OFFSET;
  86         /* code match len */
  87         if (m_len <= M3_MAX_LEN)
  88             *op++ = LZO_BYTE(M3_MARKER | (m_len - (M3_MIN_LEN - 1)));
  89         else
  90         {
  91             assert(m_len >= M4_MIN_LEN);
  92             /* code M4 match len flag */
  93             *op++ = M4_MARKER;
  94             /* code match len */
  95             m_len -= M4_MIN_LEN - 1;
  96             while (m_len > 255)
  97             {
  98                 m_len -= 255;
  99                 *op++ = 0;
 100             }
 101             assert(m_len > 0);
 102             *op++ = LZO_BYTE(m_len);
 103         }
 104         /* code low offset bits */
 105         *op++ = LZO_BYTE(m_off & M3O_MASK);
 106         /* code high offset bits */
 107         *op++ = LZO_BYTE(m_off >> M3O_BITS);
 108
 109         c->r1_m_len = 0;
 110         c->m3 = op;
 111         c->m3_m++;
 112     }
 113     return op;
 114 }
 115
 116
 117 /***********************************************************************
 118 // this is a public function, but there is no prototype in a header file
 119 ************************************************************************/
 120
 121 LZO_EXTERN(int)
 122 lzo1c_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
 123                                     lzo_bytep out, lzo_uintp out_len,
 124                                     lzo_voidp wrkmem,
 125                                     lzo_callback_p cb,
 126                                     lzo_uint max_chain );
 127
 128 LZO_PUBLIC(int)
 129 lzo1c_999_compress_callback ( const lzo_bytep in , lzo_uint  in_len,
 130                                     lzo_bytep out, lzo_uintp out_len,
 131                                     lzo_voidp wrkmem,
 132                                     lzo_callback_p cb,
 133                                     lzo_uint max_chain )
 134 {
 135     lzo_bytep op;
 136     const lzo_bytep ii;
 137     lzo_uint lit;
 138     lzo_uint m_len, m_off;
 139     LZO_COMPRESS_T cc;
 140     LZO_COMPRESS_T * const c = &cc;
 141     lzo_swd_p const swd = (lzo_swd_p) wrkmem;
 142     int r;
 143
 144     /* sanity check */
 145     LZO_COMPILE_TIME_ASSERT(LZO1C_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T)
 146
 147     c->init = 0;
 148     c->ip = c->in = in;
 149     c->in_end = in + in_len;
 150     c->cb = cb;
 151     c->r1_r = c->m3_r = c->m2_m = c->m3_m = 0;
 152
 153     op = out;
 154     ii = c->ip;             /* point to start of literal run */
 155     lit = 0;
 156     c->r1_m_len = 0;
 157     c->m3 = out + 1;        /* pointer after last m3/m4 match */
 158
 159     r = init_match(c,swd,NULL,0,0);
 160     if (r != 0)
 161         return r;
 162     if (max_chain > 0)
 163         swd->max_chain = max_chain;
 164
 165     r = find_match(c,swd,0,0);
 166     if (r != 0)
 167         return r;
 168     while (c->look > 0)
 169     {
 170         int lazy_match_min_gain = -1;
 171         lzo_uint ahead = 0;
 172
 173         m_len = c->m_len;
 174         m_off = c->m_off;
 175
 176 #if 0
 177         printf("%5ld: %5d len:%3d off:%5d\n", (c->ip-c->look)-in, c->look,
 178                 m_len, m_off);
 179 #endif
 180
 181         assert(c->ip - c->look >= in);
 182         if (lit == 0)
 183             ii = c->ip - c->look;
 184         assert(ii + lit == c->ip - c->look);
 185         assert(swd->b_char == *(c->ip - c->look));
 186
 187         if ((m_len < M2_MIN_LEN) ||
 188             (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET))
 189         {
 190             m_len = 0;
 191         }
 192         else
 193         {
 194             assert(c->ip - c->look - m_off >= in);
 195             assert(c->ip - c->look - m_off + m_len < c->ip);
 196             assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
 197                               m_len) == 0);
 198
 199             if (lit > 0)
 200             {
 201                 /* we have a current literal run: do not try a lazy match,
 202                    if the literal could be coded into a r1 or m3 match */
 203                 if (lit == 1 && c->r1_m_len == M2_MIN_LEN)
 204                     lazy_match_min_gain = -1;
 205                 else if (lit == 3 && op == c->m3)
 206                     lazy_match_min_gain = -1;
 207                 else if (lit < 3 && op == c->m3)
 208                     lazy_match_min_gain = 0;
 209                 else
 210                     lazy_match_min_gain = 1;
 211
 212 #if (M2_MIN_LEN == 2)
 213                 if (m_len == 2)
 214                 {
 215                     /* don't code a match of len 2 if we have to
 216                        code a literal run. Code a literal instead. */
 217                     m_len = 0;
 218                 }
 219 #endif
 220 #if (M2_MIN_LEN == M3_MIN_LEN)
 221                 if (m_len == M2_MIN_LEN && m_off > M2_MAX_OFFSET)
 222                 {
 223                     /* don't code a M3 match of len 3 if we have to
 224                        code a literal run. Code a literal instead. */
 225                     m_len = 0;
 226                 }
 227 #endif
 228             }
 229             else
 230             {
 231                 /* no current literal run: only try a lazy match,
 232                    if the literal could be coded into a r1 or m3 match */
 233                 if (c->r1_m_len == M2_MIN_LEN || op == c->m3)
 234                     lazy_match_min_gain = 0;
 235                 else
 236                     lazy_match_min_gain = -1;
 237             }
 238         }
 239
 240
 241         /* try a lazy match */
 242         if (m_len == 0)
 243             lazy_match_min_gain = -1;
 244         if (lazy_match_min_gain >= 0 && c->look > m_len)
 245         {
 246             assert(m_len > 0);
 247
 248             r = find_match(c,swd,1,0);
 249             assert(r == 0);
 250             assert(c->look > 0);
 251
 252             if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET &&
 253                 c->m_off > M2_MAX_OFFSET)
 254                 lazy_match_min_gain += 1;
 255
 256             if (c->m_len >= m_len + lazy_match_min_gain)
 257             {
 258                 c->lazy++;
 259 #if !defined(NDEBUG)
 260                 m_len = c->m_len;
 261                 m_off = c->m_off;
 262                 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off,
 263                                   m_len) == 0);
 264 #endif
 265                 lit++;
 266                 assert(ii + lit == c->ip - c->look);
 267                 continue;
 268             }
 269             else
 270             {
 271                 ahead = 1;
 272                 assert(ii + lit + 1 == c->ip - c->look);
 273             }
 274             assert(m_len > 0);
 275         }
 276         assert(ii + lit + ahead == c->ip - c->look);
 277
 278
 279         if (m_len == 0)
 280         {
 281             /* a literal */
 282             lit++;
 283             r = find_match(c,swd,1,0);
 284             assert(r == 0);
 285         }
 286         else
 287         {
 288             /* 1 - store run */
 289             if (lit > 0)
 290             {
 291                 /* code current literal run */
 292                 if (lit == 1 && c->r1_m_len == M2_MIN_LEN)
 293                 {
 294                     /* Code a context sensitive R1 match. */
 295                     assert((op[-2] >> M2O_BITS) == (M2_MARKER >> M2O_BITS));
 296                     op[-2] &= M2O_MASK;
 297                     assert((op[-2] >> M2O_BITS) == 0);
 298                     /* copy 1 literal */
 299                     *op++ = *ii++;
 300                     assert(ii + ahead == c->ip - c->look);
 301                     c->r1_r++;
 302                 }
 303                 else if (lit < 4 && op == c->m3)
 304                 {
 305                     assert((c->m3[-2] >> M3O_BITS) == 0);
 306                     c->m3[-2] |= LZO_BYTE(lit << M3O_BITS);
 307                     MEMCPY_DS(op, ii, lit);
 308                     assert(ii + ahead == c->ip - c->look);
 309                     c->m3_r++;
 310                 }
 311                 else
 312                 {
 313                     op = STORE_RUN(op,ii,lit);
 314                 }
 315                 if (lit < R0FAST)
 316                     c->r1_m_len = m_len;
 317                 else
 318                     c->r1_m_len = 0;
 319                 lit = 0;
 320             }
 321             else
 322                 c->r1_m_len = 0;
 323
 324             /* 2 - code match */
 325             op = code_match(c,op,m_len,m_off);
 326             r = find_match(c,swd,m_len,1+ahead);
 327             assert(r == 0);
 328         }
 329
 330         c->codesize = pd(op, out);
 331     }
 332
 333
 334     /* store final run */
 335     if (lit > 0)
 336         op = STORE_RUN(op,ii,lit);
 337
 338 #if defined(LZO_EOF_CODE)
 339     *op++ = M3_MARKER | 1;
 340     *op++ = 0;
 341     *op++ = 0;
 342 #endif
 343
 344     c->codesize = pd(op, out);
 345     assert(c->textsize == in_len);
 346
 347     *out_len = pd(op, out);
 348
 349     if (c->cb && c->cb->nprogress)
 350         (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0);
 351
 352 #if 0
 353     printf("%ld %ld -> %ld: %ld %ld %ld %ld %ld\n",
 354         (long) c->textsize, (long)in_len, (long) c->codesize,
 355         c->r1_r, c->m3_r, c->m2_m, c->m3_m, c->lazy);
 356 #endif
 357     return LZO_E_OK;
 358 }
 359
 360
 361
 362 /***********************************************************************
 363 //
 364 ************************************************************************/
 365
 366 LZO_PUBLIC(int)
 367 lzo1c_999_compress  ( const lzo_bytep in , lzo_uint  in_len,
 368                             lzo_bytep out, lzo_uintp out_len,
 369                             lzo_voidp wrkmem )
 370 {
 371     return lzo1c_999_compress_callback(in,in_len,out,out_len,wrkmem,
 372                                        (lzo_callback_p) 0, 0);
 373 }
 374
 375
 376 /*
 377 vi:ts=4:et
 378 */
 379