1 /* lzo_mchw.ch -- matching functions using a window 2 3 This file is part of the LZO real-time data compression library. 4 5 Copyright (C) 1996-2014 Markus Franz Xaver Johannes Oberhumer 6 All Rights Reserved. 7 8 The LZO library is free software; you can redistribute it and/or 9 modify it under the terms of the GNU General Public License as 10 published by the Free Software Foundation; either version 2 of 11 the License, or (at your option) any later version. 12 13 The LZO library is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with the LZO library; see the file COPYING. 20 If not, write to the Free Software Foundation, Inc., 21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 22 23 Markus F.X.J. Oberhumer 24 <markus (at) oberhumer.com> 25 http://www.oberhumer.com/opensource/lzo/ 26 */ 27 28 29 /*********************************************************************** 30 // 31 ************************************************************************/ 32 33 typedef struct 34 { 35 unsigned init; 36 37 lzo_uint look; /* bytes in lookahead buffer */ 38 39 lzo_uint m_len; 40 lzo_uint m_off; 41 42 lzo_uint last_m_len; 43 lzo_uint last_m_off; 44 45 const lzo_bytep bp; 46 const lzo_bytep ip; 47 const lzo_bytep in; 48 const lzo_bytep in_end; 49 lzo_bytep out; 50 51 lzo_callback_p cb; 52 53 lzo_uint textsize; /* text size counter */ 54 lzo_uint codesize; /* code size counter */ 55 lzo_uint printcount; /* counter for reporting progress every 1K bytes */ 56 57 /* some stats */ 58 unsigned long lit_bytes; 59 unsigned long match_bytes; 60 unsigned long rep_bytes; 61 unsigned long lazy; 62 63 #if defined(LZO1B) 64 lzo_uint r1_m_len; 65 66 /* some stats */ 67 unsigned long r1_r, m3_r, m2_m, m3_m; 68 #endif 69 70 #if defined(LZO1C) 71 lzo_uint r1_m_len; 72 lzo_bytep m3; 73 74 /* some stats */ 75 unsigned long r1_r, m3_r, m2_m, m3_m; 76 #endif 77 78 #if defined(LZO1F) 79 lzo_uint r1_lit; 80 lzo_uint r1_m_len; 81 82 /* some stats */ 83 unsigned long r1_r, m2_m, m3_m; 84 #endif 85 86 #if defined(LZO1X) || defined(LZO1Y) || defined(LZO1Z) 87 lzo_uint r1_lit; 88 lzo_uint r1_m_len; 89 90 /* some stats */ 91 unsigned long m1a_m, m1b_m, m2_m, m3_m, m4_m; 92 unsigned long lit1_r, lit2_r, lit3_r; 93 #endif 94 95 #if defined(LZO2A) 96 /* some stats */ 97 unsigned long m1, m2, m3, m4; 98 #endif 99 } 100 LZO_COMPRESS_T; 101 102 103 #define getbyte(c) ((c).ip < (c).in_end ? *((c).ip)++ : (-1)) 104 105 #include "lzo_swd.ch" 106 107 108 /*********************************************************************** 109 // 110 ************************************************************************/ 111 112 static int 113 init_match ( LZO_COMPRESS_T *c, lzo_swd_p s, 114 const lzo_bytep dict, lzo_uint dict_len, 115 lzo_uint32_t flags ) 116 { 117 int r; 118 119 assert(!c->init); 120 c->init = 1; 121 122 s->c = c; 123 124 c->last_m_len = c->last_m_off = 0; 125 126 c->textsize = c->codesize = c->printcount = 0; 127 c->lit_bytes = c->match_bytes = c->rep_bytes = 0; 128 c->lazy = 0; 129 130 r = swd_init(s,dict,dict_len); 131 if (r != LZO_E_OK) 132 { 133 swd_exit(s); 134 return r; 135 } 136 137 s->use_best_off = (flags & 1) ? 1 : 0; 138 return LZO_E_OK; 139 } 140 141 142 /*********************************************************************** 143 // 144 ************************************************************************/ 145 146 static int 147 find_match ( LZO_COMPRESS_T *c, lzo_swd_p s, 148 lzo_uint this_len, lzo_uint skip ) 149 { 150 assert(c->init); 151 152 if (skip > 0) 153 { 154 assert(this_len >= skip); 155 swd_accept(s, this_len - skip); 156 c->textsize += this_len - skip + 1; 157 } 158 else 159 { 160 assert(this_len <= 1); 161 c->textsize += this_len - skip; 162 } 163 164 s->m_len = SWD_THRESHOLD; 165 s->m_off = 0; 166 #ifdef SWD_BEST_OFF 167 if (s->use_best_off) 168 lzo_memset(s->best_pos,0,sizeof(s->best_pos)); 169 #endif 170 swd_findbest(s); 171 c->m_len = s->m_len; 172 c->m_off = s->m_off; 173 174 swd_getbyte(s); 175 176 if (s->b_char < 0) 177 { 178 c->look = 0; 179 c->m_len = 0; 180 swd_exit(s); 181 } 182 else 183 { 184 c->look = s->look + 1; 185 } 186 c->bp = c->ip - c->look; 187 188 #if 0 189 /* brute force match search */ 190 if (c->m_len > SWD_THRESHOLD && c->m_len + 1 <= c->look) 191 { 192 const lzo_bytep ip = c->bp; 193 const lzo_bytep m = c->bp - c->m_off; 194 const lzo_bytep in = c->in; 195 196 if (ip - in > s->swd_n) 197 in = ip - s->swd_n; 198 for (;;) 199 { 200 while (*in != *ip) 201 in++; 202 if (in == ip) 203 break; 204 if (in != m) 205 if (lzo_memcmp(in,ip,c->m_len+1) == 0) 206 printf("%p %p %p %5d\n",in,ip,m,c->m_len); 207 in++; 208 } 209 } 210 #endif 211 212 if (c->cb && c->cb->nprogress && c->textsize > c->printcount) 213 { 214 (*c->cb->nprogress)(c->cb, c->textsize, c->codesize, 0); 215 c->printcount += 1024; 216 } 217 218 return LZO_E_OK; 219 } 220 221 222 /* 223 vi:ts=4:et 224 */ 225 226