176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* lzo1x_oo.ch -- LZO1X compressed data optimizer 276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman This file is part of the LZO real-time data compression library. 476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer 676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman All Rights Reserved. 776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman The LZO library is free software; you can redistribute it and/or 976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman modify it under the terms of the GNU General Public License as 1076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman published by the Free Software Foundation; either version 2 of 1176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman the License, or (at your option) any later version. 1276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman The LZO library is distributed in the hope that it will be useful, 1476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman but WITHOUT ANY WARRANTY; without even the implied warranty of 1576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman GNU General Public License for more details. 1776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 1876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman You should have received a copy of the GNU General Public License 1976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman along with the LZO library; see the file COPYING. 2076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman If not, write to the Free Software Foundation, Inc., 2176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 2276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman Markus F.X.J. Oberhumer 2476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman <markus@oberhumer.com> 2576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman http://www.oberhumer.com/opensource/lzo/ 2676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman */ 2776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 2976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define TEST_IP (ip < ip_end) 3076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define TEST_OP (op <= op_end) 3176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define TEST_IP_AND_TEST_OP (TEST_IP && TEST_OP) 3276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#define NO_LIT LZO_UINT_MAX 3476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 3676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*********************************************************************** 3776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman// 3876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman************************************************************************/ 3976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 4076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void copy2(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off) 4176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 4276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(off > 0); 4376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[0] = m_pos[0]; 4476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (off == 1) 4576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[1] = m_pos[0]; 4676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 4776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[1] = m_pos[1]; 4876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 4976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 5176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanstatic void copy3(lzo_bytep ip, const lzo_bytep m_pos, lzo_uint off) 5276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 5376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(off > 0); 5476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[0] = m_pos[0]; 5576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (off == 1) 5676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 5776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[2] = ip[1] = m_pos[0]; 5876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 5976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else if (off == 2) 6076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 6176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[1] = m_pos[1]; 6276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[2] = m_pos[0]; 6376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 6476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 6576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 6676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[1] = m_pos[1]; 6776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[2] = m_pos[2]; 6876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 6976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 7076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/*********************************************************************** 7376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman// optimize a block of data. 7476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman************************************************************************/ 7576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 7676d05dc695b06c4e987bb8078f78032441e1430cGreg HartmanLZO_PUBLIC(int) 7776d05dc695b06c4e987bb8078f78032441e1430cGreg HartmanDO_OPTIMIZE ( lzo_bytep in , lzo_uint in_len, 7876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_bytep out, lzo_uintp out_len, 7976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_voidp wrkmem ) 8076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman{ 8176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_bytep op; 8276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_bytep ip; 8376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_uint t; 8476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_bytep m_pos; 8576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_bytep const ip_end = in + in_len; 8676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_bytep const op_end = out + *out_len; 8776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_bytep litp = NULL; 8876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_uint lit = 0; 8976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_uint next_lit = NO_LIT; 9076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_uint nl; 9176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman unsigned long o_m1_a = 0, o_m1_b = 0, o_m2 = 0, o_m3_a = 0, o_m3_b = 0; 9276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman LZO_UNUSED(wrkmem); 9476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *out_len = 0; 9676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 9776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman op = out; 9876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip = in; 9976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 10076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(in_len >= 3); 10176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (*ip > 17) 10276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 10376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = *ip++ - 17; 10476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t < 4) 10576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto match_next; 10676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto first_literal_run; 10776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 10876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(*ip < 16 || (*ip == 17 && in_len == 3)); 10976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 11076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (TEST_IP_AND_TEST_OP) 11176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 11276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = *ip++; 11376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t >= 16) 11476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto match; 11576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* a literal run */ 11676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman litp = ip - 1; 11776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t == 0) 11876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 11976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = 15; 12076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (*ip == 0) 12176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t += 255, ip++; 12276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t += *ip++; 12376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 12476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lit = t + 3; 12576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* copy literals */ 12676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmancopy_literal_run: 12776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *op++ = *ip++; *op++ = *ip++; *op++ = *ip++; 12876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanfirst_literal_run: 12976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman do *op++ = *ip++; while (--t > 0); 13076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = *ip++; 13376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 13476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t >= 16) 13576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto match; 13676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#if defined(LZO1X) 13776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos = op - 1 - 0x800; 13876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#elif defined(LZO1Y) 13976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos = op - 1 - 0x400; 14076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 14176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= t >> 2; 14276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= *ip++ << 2; 14376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++; 14476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lit = 0; 14576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto match_done; 14676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 14776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 14876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* handle matches */ 14976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman do { 15076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t < 16) /* a M1 match */ 15176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 15276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos = op - 1; 15376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= t >> 2; 15476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= *ip++ << 2; 15576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (litp == NULL) 15776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto copy_m1; 15876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 15976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* assert that there was a match just before */ 16076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(lit >= 1 && lit <= 3); 16176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(litp == ip - 2 - lit - 2); 16276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert((lzo_uint)(*litp & 3) == lit); 16376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nl = ip[-2] & 3; 16476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* test if a match follows */ 16576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (nl == 0 && lit == 1 && ip[0] >= 16) 16676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 16776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman next_lit = nl; 16876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* adjust length of previous short run */ 16976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lit += 2; 17076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *litp = LZO_BYTE((*litp & ~3) | lit); 17176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* copy over the 2 literals that replace the match */ 17276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copy2(ip-2,m_pos,pd(op,m_pos)); 17376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o_m1_a++; 17476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 17576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* test if a literal run follows */ 17676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else if (nl == 0 && ip[0] < 16 && ip[0] != 0 && 17776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (lit + 2 + ip[0] < 16)) 17876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 17976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = *ip++; 18076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* remove short run */ 18176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *litp &= ~3; 18276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* copy over the 2 literals that replace the match */ 18376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copy2(ip-3+1,m_pos,pd(op,m_pos)); 18476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* move literals 1 byte ahead */ 18576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman litp += 2; 18676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (lit > 0) 18776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_memmove(litp+1,litp,lit); 18876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* insert new length of long literal run */ 18976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lit += 2 + t + 3; assert(lit <= 18); 19076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *litp = LZO_BYTE(lit - 3); 19176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 19276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o_m1_b++; 19376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *op++ = *m_pos++; *op++ = *m_pos++; 19476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto copy_literal_run; 19576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 19676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmancopy_m1: 19776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *op++ = *m_pos++; *op++ = *m_pos++; 19876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 19976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 20076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 20176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanmatch: 20276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t >= 64) /* a M2 match */ 20376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 20476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos = op - 1; 20576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#if defined(LZO1X) 20676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= (t >> 2) & 7; 20776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= *ip++ << 3; 20876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = (t >> 5) - 1; 20976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#elif defined(LZO1Y) 21076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= (t >> 2) & 3; 21176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= *ip++ << 2; 21276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = (t >> 4) - 3; 21376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 21476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (litp == NULL) 21576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto copy_m; 21676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 21776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nl = ip[-2] & 3; 21876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* test if in beetween two long literal runs */ 21976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t == 1 && lit > 3 && nl == 0 && 22076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16)) 22176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 22276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(*litp == lit - 3); 22376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = *ip++; 22476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* copy over the 3 literals that replace the match */ 22576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copy3(ip-1-2,m_pos,pd(op,m_pos)); 22676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* set new length of previous literal run */ 22776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lit += 3 + t + 3; assert(lit <= 18); 22876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *litp = LZO_BYTE(lit - 3); 22976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o_m2++; 23076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++; 23176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto copy_literal_run; 23276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 23376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 23476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 23576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 23676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t >= 32) /* a M3 match */ 23776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 23876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t &= 31; 23976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t == 0) 24076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 24176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = 31; 24276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (*ip == 0) 24376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t += 255, ip++; 24476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t += *ip++; 24576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 24676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos = op - 1; 24776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= *ip++ >> 2; 24876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= *ip++ << 6; 24976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 25076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else /* a M4 match */ 25176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 25276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos = op; 25376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= (t & 8) << 11; 25476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t &= 7; 25576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t == 0) 25676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 25776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = 7; 25876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman while (*ip == 0) 25976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t += 255, ip++; 26076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t += *ip++; 26176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 26276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= *ip++ >> 2; 26376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= *ip++ << 6; 26476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (m_pos == op) 26576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto eof_found; 26676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman m_pos -= 0x4000; 26776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 26876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (litp == NULL) 26976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto copy_m; 27076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 27176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman nl = ip[-2] & 3; 27276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* test if in beetween two matches */ 27376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t == 1 && lit == 0 && nl == 0 && ip[0] >= 16) 27476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 27576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(litp == ip - 3 - lit - 2); 27676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert((lzo_uint)(*litp & 3) == lit); 27776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman next_lit = nl; 27876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* make a previous short run */ 27976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lit += 3; 28076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *litp = LZO_BYTE((*litp & ~3) | lit); 28176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* copy over the 3 literals that replace the match */ 28276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copy3(ip-3,m_pos,pd(op,m_pos)); 28376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o_m3_a++; 28476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 28576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* test if a literal run follows */ 28676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else if (t == 1 && lit <= 3 && nl == 0 && 28776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman ip[0] < 16 && ip[0] != 0 && (lit + 3 + ip[0] < 16)) 28876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 28976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(litp == ip - 3 - lit - 2); 29076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert((lzo_uint)(*litp & 3) == lit); 29176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = *ip++; 29276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* remove short run */ 29376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *litp &= ~3; 29476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* copy over the 3 literals that replace the match */ 29576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman copy3(ip-4+1,m_pos,pd(op,m_pos)); 29676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* move literals 1 byte ahead */ 29776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman litp += 2; 29876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (lit > 0) 29976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lzo_memmove(litp+1,litp,lit); 30076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* insert new length of long literal run */ 30176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lit += 3 + t + 3; assert(lit <= 18); 30276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *litp = LZO_BYTE(lit - 3); 30376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 30476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o_m3_b++; 30576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *op++ = *m_pos++; *op++ = *m_pos++; *op++ = *m_pos++; 30676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman goto copy_literal_run; 30776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 30876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 30976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmancopy_m: 31076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *op++ = *m_pos++; *op++ = *m_pos++; 31176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman do *op++ = *m_pos++; while (--t > 0); 31276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 31376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 31476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanmatch_done: 31576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (next_lit == NO_LIT) 31676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman { 31776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = ip[-2] & 3; 31876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman lit = t; 31976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman litp = ip - 2; 32076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 32176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman else 32276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = next_lit; 32376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(t <= 3); 32476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman next_lit = NO_LIT; 32576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman if (t == 0) 32676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman break; 32776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* copy literals */ 32876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanmatch_next: 32976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman do *op++ = *ip++; while (--t > 0); 33076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman t = *ip++; 33176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } while (TEST_IP_AND_TEST_OP); 33276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman } 33376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 33476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman /* no EOF code was found */ 33576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *out_len = pd(op, out); 33676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return LZO_E_EOF_NOT_FOUND; 33776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 33876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmaneof_found: 33976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman assert(t == 1); 34076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#if 0 34176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman printf("optimize: %5lu %5lu %5lu %5lu %5lu\n", 34276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman o_m1_a, o_m1_b, o_m2, o_m3_a, o_m3_b); 34376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman#endif 34476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman LZO_UNUSED(o_m1_a); LZO_UNUSED(o_m1_b); LZO_UNUSED(o_m2); 34576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman LZO_UNUSED(o_m3_a); LZO_UNUSED(o_m3_b); 34676d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman *out_len = pd(op, out); 34776d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman return (ip == ip_end ? LZO_E_OK : 34876d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman (ip < ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); 34976d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman} 35076d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 35176d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 35276d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman/* 35376d05dc695b06c4e987bb8078f78032441e1430cGreg Hartmanvi:ts=4:et 35476d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman*/ 35576d05dc695b06c4e987bb8078f78032441e1430cGreg Hartman 356