1/* lzo1x_oo.ch -- LZO1X compressed data optimizer 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#define TEST_IP (ip < ip_end) 42#define TEST_OP (op <= op_end) 43 44#define NO_LIT LZO_UINT_MAX 45 46 47/*********************************************************************** 48// 49************************************************************************/ 50 51static void copy2(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off) 52{ 53 assert(off > 0); 54 ip[0] = m_pos[0]; 55 if (off == 1) 56 ip[1] = m_pos[0]; 57 else 58 ip[1] = m_pos[1]; 59} 60 61 62static void copy3(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off) 63{ 64 assert(off > 0); 65 ip[0] = m_pos[0]; 66 if (off == 1) 67 { 68 ip[2] = ip[1] = m_pos[0]; 69 } 70 else if (off == 2) 71 { 72 ip[1] = m_pos[1]; 73 ip[2] = m_pos[0]; 74 } 75 else 76 { 77 ip[1] = m_pos[1]; 78 ip[2] = m_pos[2]; 79 } 80} 81 82 83/*********************************************************************** 84// optimize a block of data. 85************************************************************************/ 86 87LZO_PUBLIC(int) 88DO_OPTIMIZE ( lzo_bytep in , lzo_uint in_len, 89 lzo_bytep out, lzo_uintp out_len, 90 lzo_voidp wrkmem ) 91{ 92 lzo_bytep op; 93 lzo_bytep ip; 94 lzo_uint t; 95 lzo_bytep m_pos; 96 lzo_bytep const ip_end = in + in_len; 97 lzo_bytep const op_end = out + *out_len; 98 lzo_bytep litp = NULL; 99 lzo_uint lit = 0; 100 lzo_uint next_lit = NO_LIT; 101 lzo_uint nl; 102 unsigned long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0; 103 104 LZO_UNUSED(wrkmem); 105 106 *out_len = 0; 107 108 op = out; 109 ip = in; 110 111 assert(in_len >= 3); 112 if (*ip > 17) 113 { 114 t = *ip++ - 17; 115 if (t < 4) 116 goto match_next; 117 goto first_literal_run; 118 } 119 assert(*ip < 16 || (*ip == 17 && in_len == 3)); 120 121 while (TEST_IP && TEST_OP) 122 { 123 t = *ip++; 124 if (t >= 16) 125 goto match; 126 /* a literal run */ 127 litp = ip - 1; 128 if (t == 0) 129 { 130 t = 15; 131 while (*ip == 0) 132 t += 255, ip++; 133 t += *ip++; 134 } 135 lit = t + 3; 136 /* copy literals */ 137copy_literal_run: 138 *op++ = *ip++; *op++ = *ip++; *op++ = *ip++; 139first_literal_run: 140 do *op++ = *ip++; while (--t > 0); 141 142 143 t = *ip++; 144 145 if (t >= 16) 146 goto match; 147#if defined(LZO1X) 148 m_pos = op - 1 - 0x800; 149#elif defined(LZO1Y) 150 m_pos = op - 1 - 0x400; 151#endif 152 m_pos -= t >> 2; 153 m_pos -= *ip++ << 2; 154 *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++; 155 lit = 0; 156 goto match_done; 157 158 159 /* handle matches */ 160 do { 161 if (t < 16) /* a M1 match */ 162 { 163 m_pos = op - 1; 164 m_pos -= t >> 2; 165 m_pos -= *ip++ << 2; 166 167 if (litp == NULL) 168 goto copy_m1; 169 170 /* assert that there was a match just before */ 171 assert(lit >= 1 && lit <= 3); 172 assert(litp == ip - 2 - lit - 2); 173 assert((lzo_uint)(*litp & 3) == lit); 174 nl = ip[-2] & 3; 175 /* test if a match follows */ 176 if (nl == 0 && lit == 1 && ip[0] >= 16) 177 { 178 next_lit = nl; 179 /* adjust length of previous short run */ 180 lit += 2; 181 *litp = LZO_BYTE((*litp & ~3) | lit); 182 /* copy over the 2 literals that replace the match */ 183 copy2(ip-2,m_pos,pd(op,m_pos)); 184 o_m1_a++; 185 } 186 /* test if a literal run follows */ 187 else if (nl == 0 && ip[0] < 16 && ip[0] != 0 && 188 (lit + 2 + ip[0] < 16)) 189 { 190 t = *ip++; 191 /* remove short run */ 192 *litp &= ~3; 193 /* copy over the 2 literals that replace the match */ 194 copy2(ip-3+1,m_pos,pd(op,m_pos)); 195 /* move literals 1 byte ahead */ 196 litp += 2; 197 if (lit > 0) 198 lzo_memmove(litp+1,litp,lit); 199 /* insert new length of long literal run */ 200 lit += 2 + t + 3; assert(lit <= 18); 201 *litp = LZO_BYTE(lit - 3); 202 203 o_m1_b++; 204 *op++ = *m_pos++; *op++ = *m_pos++; 205 goto copy_literal_run; 206 } 207copy_m1: 208 *op++ = *m_pos++; *op++ = *m_pos++; 209 } 210 else 211 { 212match: 213 if (t >= 64) /* a M2 match */ 214 { 215 m_pos = op - 1; 216#if defined(LZO1X) 217 m_pos -= (t >> 2) & 7; 218 m_pos -= *ip++ << 3; 219 t = (t >> 5) - 1; 220#elif defined(LZO1Y) 221 m_pos -= (t >> 2) & 3; 222 m_pos -= *ip++ << 2; 223 t = (t >> 4) - 3; 224#endif 225 if (litp == NULL) 226 goto copy_m; 227 228 nl = ip[-2] & 3; 229 /* test if in beetween two long literal runs */ 230 if (t == 1 && lit > 3 && nl == 0 && 231 ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16)) 232 { 233 assert(*litp == lit - 3); 234 t = *ip++; 235 /* copy over the 3 literals that replace the match */ 236 copy3(ip-1-2,m_pos,pd(op,m_pos)); 237 /* set new length of previous literal run */ 238 lit += 3 + t + 3; assert(lit <= 18); 239 *litp = LZO_BYTE(lit - 3); 240 o_m2++; 241 *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++; 242 goto copy_literal_run; 243 } 244 } 245 else 246 { 247 if (t >= 32) /* a M3 match */ 248 { 249 t &= 31; 250 if (t == 0) 251 { 252 t = 31; 253 while (*ip == 0) 254 t += 255, ip++; 255 t += *ip++; 256 } 257 m_pos = op - 1; 258 m_pos -= *ip++ >> 2; 259 m_pos -= *ip++ << 6; 260 } 261 else /* a M4 match */ 262 { 263 m_pos = op; 264 m_pos -= (t & 8) << 11; 265 t &= 7; 266 if (t == 0) 267 { 268 t = 7; 269 while (*ip == 0) 270 t += 255, ip++; 271 t += *ip++; 272 } 273 m_pos -= *ip++ >> 2; 274 m_pos -= *ip++ << 6; 275 if (m_pos == op) 276 goto eof_found; 277 m_pos -= 0x4000; 278 } 279 if (litp == NULL) 280 goto copy_m; 281 282 nl = ip[-2] & 3; 283 /* test if in beetween two matches */ 284 if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16) 285 { 286 assert(litp == ip - 3 - lit - 2); 287 assert((lzo_uint)(*litp & 3) == lit); 288 next_lit = nl; 289 /* make a previous short run */ 290 lit += 3; 291 *litp = LZO_BYTE((*litp & ~3) | lit); 292 /* copy over the 3 literals that replace the match */ 293 copy3(ip-3,m_pos,pd(op,m_pos)); 294 o_m3_a++; 295 } 296 /* test if a literal run follows */ 297 else if (t == 1 && lit <= 3 && nl == 0 && 298 ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16)) 299 { 300 assert(litp == ip - 3 - lit - 2); 301 assert((lzo_uint)(*litp & 3) == lit); 302 t = *ip++; 303 /* remove short run */ 304 *litp &= ~3; 305 /* copy over the 3 literals that replace the match */ 306 copy3(ip-4+1,m_pos,pd(op,m_pos)); 307 /* move literals 1 byte ahead */ 308 litp += 2; 309 if (lit > 0) 310 lzo_memmove(litp+1,litp,lit); 311 /* insert new length of long literal run */ 312 lit += 3 + t + 3; assert(lit <= 18); 313 *litp = LZO_BYTE(lit - 3); 314 315 o_m3_b++; 316 *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++; 317 goto copy_literal_run; 318 } 319 } 320copy_m: 321 *op++ = *m_pos++; *op++ = *m_pos++; 322 do *op++ = *m_pos++; while (--t > 0); 323 } 324 325match_done: 326 if (next_lit == NO_LIT) 327 { 328 t = ip[-2] & 3; 329 lit = t; 330 litp = ip - 2; 331 } 332 else 333 t = next_lit; 334 assert(t <= 3); 335 next_lit = NO_LIT; 336 if (t == 0) 337 break; 338 /* copy literals */ 339match_next: 340 do *op++ = *ip++; while (--t > 0); 341 t = *ip++; 342 } while (TEST_IP && TEST_OP); 343 } 344 345 /* no EOF code was found */ 346 *out_len = pd(op, out); 347 return LZO_E_EOF_NOT_FOUND; 348 349eof_found: 350 assert(t == 1); 351#if 0 352 printf("optimize: %5lu %5lu %5lu %5lu %5lu\n", 353 o_m1_a, o_m1_b, o_m2, o_m3_a, o_m3_b); 354#endif 355 LZO_UNUSED(o_m1_a); LZO_UNUSED(o_m1_b); LZO_UNUSED(o_m2); 356 LZO_UNUSED(o_m3_a); LZO_UNUSED(o_m3_b); 357 *out_len = pd(op, out); 358 return (ip == ip_end ? LZO_E_OK : 359 (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); 360} 361 362 363/* 364vi:ts=4:et 365*/ 366 367