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