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