1/* lzo1b_9x.c -- implementation of the LZO1B-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 "config1b.h" 42 43 44/*********************************************************************** 45// 46************************************************************************/ 47 48#define N 0xffffL /* 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 LZO1B 54#define LZO_COMPRESS_T lzo1b_999_t 55#define lzo_swd_t lzo1b_999_swd_t 56#include "lzo_mchw.ch" 57 58 59 60/*********************************************************************** 61// 62************************************************************************/ 63 64static lzo_bytep 65code_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_m++; 111 } 112 return op; 113} 114 115 116/*********************************************************************** 117// this is a public function, but there is no prototype in a header file 118************************************************************************/ 119 120LZO_EXTERN(int) 121lzo1b_999_compress_callback ( const lzo_bytep in , lzo_uint in_len, 122 lzo_bytep out, lzo_uintp out_len, 123 lzo_voidp wrkmem, 124 lzo_callback_p cb, 125 lzo_uint max_chain ); 126 127LZO_PUBLIC(int) 128lzo1b_999_compress_callback ( const lzo_bytep in , lzo_uint in_len, 129 lzo_bytep out, lzo_uintp out_len, 130 lzo_voidp wrkmem, 131 lzo_callback_p cb, 132 lzo_uint max_chain ) 133{ 134 lzo_bytep op; 135 const lzo_bytep ii; 136 lzo_uint lit; 137 lzo_uint m_len, m_off; 138 LZO_COMPRESS_T cc; 139 LZO_COMPRESS_T * const c = &cc; 140 lzo_swd_p const swd = (lzo_swd_p) wrkmem; 141 int r; 142 143 /* sanity check */ 144 LZO_COMPILE_TIME_ASSERT(LZO1B_999_MEM_COMPRESS >= SIZEOF_LZO_SWD_T) 145 146 c->init = 0; 147 c->ip = c->in = in; 148 c->in_end = in + in_len; 149 c->cb = cb; 150 c->r1_r = c->m3_r = c->m2_m = c->m3_m = 0; 151 152 op = out; 153 ii = c->ip; /* point to start of literal run */ 154 lit = 0; 155 c->r1_m_len = 0; 156 157 r = init_match(c,swd,NULL,0,0); 158 if (r != 0) 159 return r; 160 if (max_chain > 0) 161 swd->max_chain = max_chain; 162 163 r = find_match(c,swd,0,0); 164 if (r != 0) 165 return r; 166 while (c->look > 0) 167 { 168 int lazy_match_min_gain = -1; 169 lzo_uint ahead = 0; 170 171 m_len = c->m_len; 172 m_off = c->m_off; 173 174#if 0 175 printf("%5ld: %5d len:%3d off:%5d\n", (c->ip-c->look)-in, c->look, 176 m_len, m_off); 177#endif 178 179 assert(c->ip - c->look >= in); 180 if (lit == 0) 181 ii = c->ip - c->look; 182 assert(ii + lit == c->ip - c->look); 183 assert(swd->b_char == *(c->ip - c->look)); 184 185 if ((m_len < M2_MIN_LEN) || 186 (m_len < M3_MIN_LEN && m_off > M2_MAX_OFFSET)) 187 { 188 m_len = 0; 189 } 190 else 191 { 192 assert(c->ip - c->look - m_off >= in); 193 assert(c->ip - c->look - m_off + m_len < c->ip); 194 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off, 195 m_len) == 0); 196 197 if (lit > 0) 198 { 199 /* we have a current literal run: do not try a lazy match, 200 if the literal could be coded into a r1 match */ 201 if (lit == 1 && c->r1_m_len == M2_MIN_LEN) 202 lazy_match_min_gain = -1; 203 else 204 lazy_match_min_gain = 1; 205 206#if (M2_MIN_LEN == 2) 207 if (m_len == 2) 208 { 209 /* don't code a match of len 2 if we have to 210 code a literal run. Code a literal instead. */ 211 m_len = 0; 212 } 213#endif 214#if (M2_MIN_LEN == M3_MIN_LEN) 215 if (m_len == M2_MIN_LEN && m_off > M2_MAX_OFFSET) 216 { 217 /* don't code a M3 match of len 3 if we have to 218 code a literal run. Code a literal instead. */ 219 m_len = 0; 220 } 221#endif 222 } 223 else 224 { 225 /* no current literal run: only try a lazy match, 226 if the literal could be coded into a r1 match */ 227 if (c->r1_m_len == M2_MIN_LEN) 228 lazy_match_min_gain = 0; 229 else 230 lazy_match_min_gain = -1; 231 } 232 } 233 234 235 /* try a lazy match */ 236 if (m_len == 0) 237 lazy_match_min_gain = -1; 238 if (lazy_match_min_gain >= 0 && c->look > m_len) 239 { 240 assert(m_len > 0); 241 242 r = find_match(c,swd,1,0); 243 assert(r == 0); 244 assert(c->look > 0); 245 246 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET && 247 c->m_off > M2_MAX_OFFSET) 248 lazy_match_min_gain += 1; 249 250 if (c->m_len >= m_len + lazy_match_min_gain) 251 { 252 c->lazy++; 253#if !defined(NDEBUG) 254 m_len = c->m_len; 255 m_off = c->m_off; 256 assert(lzo_memcmp(c->ip - c->look, c->ip - c->look - m_off, 257 m_len) == 0); 258#endif 259 lit++; 260 assert(ii + lit == c->ip - c->look); 261 continue; 262 } 263 else 264 { 265 ahead = 1; 266 assert(ii + lit + 1 == c->ip - c->look); 267 } 268 assert(m_len > 0); 269 } 270 assert(ii + lit + ahead == c->ip - c->look); 271 272 273 if (m_len == 0) 274 { 275 /* a literal */ 276 lit++; 277 r = find_match(c,swd,1,0); 278 assert(r == 0); 279 } 280 else 281 { 282 /* 1 - store run */ 283 if (lit > 0) 284 { 285 /* code current literal run */ 286 if (lit == 1 && c->r1_m_len == M2_MIN_LEN) 287 { 288 /* Code a context sensitive R1 match. */ 289 assert((op[-2] >> M2O_BITS) == (M2_MARKER >> M2O_BITS)); 290 op[-2] &= M2O_MASK; 291 assert((op[-2] >> M2O_BITS) == 0); 292 /* copy 1 literal */ 293 *op++ = *ii++; 294 assert(ii + ahead == c->ip - c->look); 295 c->r1_r++; 296 } 297 else 298 { 299 op = STORE_RUN(op,ii,lit); 300 } 301 if (lit < R0FAST) 302 c->r1_m_len = m_len; 303 else 304 c->r1_m_len = 0; 305 lit = 0; 306 } 307 else 308 c->r1_m_len = 0; 309 310 /* 2 - code match */ 311 op = code_match(c,op,m_len,m_off); 312 r = find_match(c,swd,m_len,1+ahead); 313 assert(r == 0); 314 } 315 316 c->codesize = pd(op, out); 317 } 318 319 320 /* store final run */ 321 if (lit > 0) 322 op = STORE_RUN(op,ii,lit); 323 324#if defined(LZO_EOF_CODE) 325 *op++ = M3_MARKER | 1; 326 *op++ = 0; 327 *op++ = 0; 328#endif 329 330 c->codesize = pd(op, out); 331 assert(c->textsize == in_len); 332 333 *out_len = pd(op, out); 334 335 if (c->cb && c->cb->nprogress) 336 (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0); 337 338#if 0 339 printf("%ld %ld -> %ld: %ld %ld %ld %ld %ld\n", 340 (long) c->textsize, (long)in_len, (long) c->codesize, 341 c->r1_r, c->m3_r, c->m2_m, c->m3_m, c->lazy); 342#endif 343 return LZO_E_OK; 344} 345 346 347 348/*********************************************************************** 349// 350************************************************************************/ 351 352LZO_PUBLIC(int) 353lzo1b_999_compress ( const lzo_bytep in , lzo_uint in_len, 354 lzo_bytep out, lzo_uintp out_len, 355 lzo_voidp wrkmem ) 356{ 357 return lzo1b_999_compress_callback(in,in_len,out,out_len,wrkmem, 358 (lzo_callback_p) 0, 0); 359} 360 361 362/* 363vi:ts=4:et 364*/ 365 366