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