src/lzo2a_9x.c

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