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 86LZO_EXTERN(int) 87lzo2a_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 93LZO_PUBLIC(int) 94lzo2a_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 344LZO_PUBLIC(int) 345lzo2a_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/* 355vi:ts=4:et 356*/ 357 358