1 /* lzo1x_c.ch -- implementation of the LZO1[XY]-1 compression algorithm 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 #if 1 && defined(DO_COMPRESS) && !defined(do_compress) 31 /* choose a unique name to better help PGO optimizations */ 32 # define do_compress LZO_PP_ECONCAT2(DO_COMPRESS,_core) 33 #endif 34 35 36 /*********************************************************************** 37 // compress a block of data. 38 ************************************************************************/ 39 40 static __lzo_noinline lzo_uint 41 do_compress ( const lzo_bytep in , lzo_uint in_len, 42 lzo_bytep out, lzo_uintp out_len, 43 lzo_uint ti, lzo_voidp wrkmem) 44 { 45 const lzo_bytep ip; 46 lzo_bytep op; 47 const lzo_bytep const in_end = in + in_len; 48 const lzo_bytep const ip_end = in + in_len - 20; 49 const lzo_bytep ii; 50 lzo_dict_p const dict = (lzo_dict_p) wrkmem; 51 52 op = out; 53 ip = in; 54 ii = ip; 55 56 ip += ti < 4 ? 4 - ti : 0; 57 for (;;) 58 { 59 const lzo_bytep m_pos; 60 #if !(LZO_DETERMINISTIC) 61 LZO_DEFINE_UNINITIALIZED_VAR(lzo_uint, m_off, 0); 62 lzo_uint m_len; 63 lzo_uint dindex; 64 next: 65 if __lzo_unlikely(ip >= ip_end) 66 break; 67 DINDEX1(dindex,ip); 68 GINDEX(m_pos,m_off,dict,dindex,in); 69 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) 70 goto literal; 71 #if 1 72 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) 73 goto try_match; 74 DINDEX2(dindex,ip); 75 #endif 76 GINDEX(m_pos,m_off,dict,dindex,in); 77 if (LZO_CHECK_MPOS_NON_DET(m_pos,m_off,in,ip,M4_MAX_OFFSET)) 78 goto literal; 79 if (m_off <= M2_MAX_OFFSET || m_pos[3] == ip[3]) 80 goto try_match; 81 goto literal; 82 83 try_match: 84 #if (LZO_OPT_UNALIGNED32) 85 if (UA_GET_NE32(m_pos) != UA_GET_NE32(ip)) 86 #else 87 if (m_pos[0] != ip[0] || m_pos[1] != ip[1] || m_pos[2] != ip[2] || m_pos[3] != ip[3]) 88 #endif 89 { 90 /* a literal */ 91 literal: 92 UPDATE_I(dict,0,dindex,ip,in); 93 ip += 1 + ((ip - ii) >> 5); 94 continue; 95 } 96 /*match:*/ 97 UPDATE_I(dict,0,dindex,ip,in); 98 #else 99 lzo_uint m_off; 100 lzo_uint m_len; 101 { 102 lzo_uint32_t dv; 103 lzo_uint dindex; 104 literal: 105 ip += 1 + ((ip - ii) >> 5); 106 next: 107 if __lzo_unlikely(ip >= ip_end) 108 break; 109 dv = UA_GET_LE32(ip); 110 dindex = DINDEX(dv,ip); 111 GINDEX(m_off,m_pos,in+dict,dindex,in); 112 UPDATE_I(dict,0,dindex,ip,in); 113 if __lzo_unlikely(dv != UA_GET_LE32(m_pos)) 114 goto literal; 115 } 116 #endif 117 118 /* a match */ 119 120 ii -= ti; ti = 0; 121 { 122 lzo_uint t = pd(ip,ii); 123 if (t != 0) 124 { 125 if (t <= 3) 126 { 127 op[-2] = LZO_BYTE(op[-2] | t); 128 #if (LZO_OPT_UNALIGNED32) 129 UA_COPY4(op, ii); 130 op += t; 131 #else 132 { do *op++ = *ii++; while (--t > 0); } 133 #endif 134 } 135 #if (LZO_OPT_UNALIGNED32) || (LZO_OPT_UNALIGNED64) 136 else if (t <= 16) 137 { 138 *op++ = LZO_BYTE(t - 3); 139 UA_COPY8(op, ii); 140 UA_COPY8(op+8, ii+8); 141 op += t; 142 } 143 #endif 144 else 145 { 146 if (t <= 18) 147 *op++ = LZO_BYTE(t - 3); 148 else 149 { 150 lzo_uint tt = t - 18; 151 *op++ = 0; 152 while __lzo_unlikely(tt > 255) 153 { 154 tt -= 255; 155 UA_SET1(op, 0); 156 op++; 157 } 158 assert(tt > 0); 159 *op++ = LZO_BYTE(tt); 160 } 161 #if (LZO_OPT_UNALIGNED32) || (LZO_OPT_UNALIGNED64) 162 do { 163 UA_COPY8(op, ii); 164 UA_COPY8(op+8, ii+8); 165 op += 16; ii += 16; t -= 16; 166 } while (t >= 16); if (t > 0) 167 #endif 168 { do *op++ = *ii++; while (--t > 0); } 169 } 170 } 171 } 172 m_len = 4; 173 { 174 #if (LZO_OPT_UNALIGNED64) 175 lzo_uint64_t v; 176 v = UA_GET_NE64(ip + m_len) ^ UA_GET_NE64(m_pos + m_len); 177 if __lzo_unlikely(v == 0) { 178 do { 179 m_len += 8; 180 v = UA_GET_NE64(ip + m_len) ^ UA_GET_NE64(m_pos + m_len); 181 if __lzo_unlikely(ip + m_len >= ip_end) 182 goto m_len_done; 183 } while (v == 0); 184 } 185 #if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_ctlz64) 186 m_len += lzo_bitops_ctlz64(v) / CHAR_BIT; 187 #elif (LZO_ABI_BIG_ENDIAN) 188 if ((v >> (64 - CHAR_BIT)) == 0) do { 189 v <<= CHAR_BIT; 190 m_len += 1; 191 } while ((v >> (64 - CHAR_BIT)) == 0); 192 #elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_cttz64) 193 m_len += lzo_bitops_cttz64(v) / CHAR_BIT; 194 #elif (LZO_ABI_LITTLE_ENDIAN) 195 if ((v & UCHAR_MAX) == 0) do { 196 v >>= CHAR_BIT; 197 m_len += 1; 198 } while ((v & UCHAR_MAX) == 0); 199 #else 200 if (ip[m_len] == m_pos[m_len]) do { 201 m_len += 1; 202 } while (ip[m_len] == m_pos[m_len]); 203 #endif 204 #elif (LZO_OPT_UNALIGNED32) 205 lzo_uint32_t v; 206 v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len); 207 if __lzo_unlikely(v == 0) { 208 do { 209 m_len += 4; 210 v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len); 211 if (v != 0) 212 break; 213 m_len += 4; 214 v = UA_GET_NE32(ip + m_len) ^ UA_GET_NE32(m_pos + m_len); 215 if __lzo_unlikely(ip + m_len >= ip_end) 216 goto m_len_done; 217 } while (v == 0); 218 } 219 #if (LZO_ABI_BIG_ENDIAN) && defined(lzo_bitops_ctlz32) 220 m_len += lzo_bitops_ctlz32(v) / CHAR_BIT; 221 #elif (LZO_ABI_BIG_ENDIAN) 222 if ((v >> (32 - CHAR_BIT)) == 0) do { 223 v <<= CHAR_BIT; 224 m_len += 1; 225 } while ((v >> (32 - CHAR_BIT)) == 0); 226 #elif (LZO_ABI_LITTLE_ENDIAN) && defined(lzo_bitops_cttz32) 227 m_len += lzo_bitops_cttz32(v) / CHAR_BIT; 228 #elif (LZO_ABI_LITTLE_ENDIAN) 229 if ((v & UCHAR_MAX) == 0) do { 230 v >>= CHAR_BIT; 231 m_len += 1; 232 } while ((v & UCHAR_MAX) == 0); 233 #else 234 if (ip[m_len] == m_pos[m_len]) do { 235 m_len += 1; 236 } while (ip[m_len] == m_pos[m_len]); 237 #endif 238 #else 239 if __lzo_unlikely(ip[m_len] == m_pos[m_len]) { 240 do { 241 m_len += 1; 242 if (ip[m_len] != m_pos[m_len]) 243 break; 244 m_len += 1; 245 if (ip[m_len] != m_pos[m_len]) 246 break; 247 m_len += 1; 248 if (ip[m_len] != m_pos[m_len]) 249 break; 250 m_len += 1; 251 if (ip[m_len] != m_pos[m_len]) 252 break; 253 m_len += 1; 254 if (ip[m_len] != m_pos[m_len]) 255 break; 256 m_len += 1; 257 if (ip[m_len] != m_pos[m_len]) 258 break; 259 m_len += 1; 260 if (ip[m_len] != m_pos[m_len]) 261 break; 262 m_len += 1; 263 if __lzo_unlikely(ip + m_len >= ip_end) 264 goto m_len_done; 265 } while (ip[m_len] == m_pos[m_len]); 266 } 267 #endif 268 } 269 m_len_done: 270 m_off = pd(ip,m_pos); 271 ip += m_len; 272 ii = ip; 273 if (m_len <= M2_MAX_LEN && m_off <= M2_MAX_OFFSET) 274 { 275 m_off -= 1; 276 #if defined(LZO1X) 277 *op++ = LZO_BYTE(((m_len - 1) << 5) | ((m_off & 7) << 2)); 278 *op++ = LZO_BYTE(m_off >> 3); 279 #elif defined(LZO1Y) 280 *op++ = LZO_BYTE(((m_len + 1) << 4) | ((m_off & 3) << 2)); 281 *op++ = LZO_BYTE(m_off >> 2); 282 #endif 283 } 284 else if (m_off <= M3_MAX_OFFSET) 285 { 286 m_off -= 1; 287 if (m_len <= M3_MAX_LEN) 288 *op++ = LZO_BYTE(M3_MARKER | (m_len - 2)); 289 else 290 { 291 m_len -= M3_MAX_LEN; 292 *op++ = M3_MARKER | 0; 293 while __lzo_unlikely(m_len > 255) 294 { 295 m_len -= 255; 296 UA_SET1(op, 0); 297 op++; 298 } 299 *op++ = LZO_BYTE(m_len); 300 } 301 *op++ = LZO_BYTE(m_off << 2); 302 *op++ = LZO_BYTE(m_off >> 6); 303 } 304 else 305 { 306 m_off -= 0x4000; 307 if (m_len <= M4_MAX_LEN) 308 *op++ = LZO_BYTE(M4_MARKER | ((m_off >> 11) & 8) | (m_len - 2)); 309 else 310 { 311 m_len -= M4_MAX_LEN; 312 *op++ = LZO_BYTE(M4_MARKER | ((m_off >> 11) & 8)); 313 while __lzo_unlikely(m_len > 255) 314 { 315 m_len -= 255; 316 UA_SET1(op, 0); 317 op++; 318 } 319 *op++ = LZO_BYTE(m_len); 320 } 321 *op++ = LZO_BYTE(m_off << 2); 322 *op++ = LZO_BYTE(m_off >> 6); 323 } 324 goto next; 325 } 326 327 *out_len = pd(op, out); 328 return pd(in_end,ii-ti); 329 } 330 331 332 /*********************************************************************** 333 // public entry point 334 ************************************************************************/ 335 336 LZO_PUBLIC(int) 337 DO_COMPRESS ( const lzo_bytep in , lzo_uint in_len, 338 lzo_bytep out, lzo_uintp out_len, 339 lzo_voidp wrkmem ) 340 { 341 const lzo_bytep ip = in; 342 lzo_bytep op = out; 343 lzo_uint l = in_len; 344 lzo_uint t = 0; 345 346 while (l > 20) 347 { 348 lzo_uint ll = l; 349 lzo_uintptr_t ll_end; 350 #if 0 || (LZO_DETERMINISTIC) 351 ll = LZO_MIN(ll, 49152); 352 #endif 353 ll_end = (lzo_uintptr_t)ip + ll; 354 if ((ll_end + ((t + ll) >> 5)) <= ll_end || (const lzo_bytep)(ll_end + ((t + ll) >> 5)) <= ip + ll) 355 break; 356 #if (LZO_DETERMINISTIC) 357 lzo_memset(wrkmem, 0, ((lzo_uint)1 << D_BITS) * sizeof(lzo_dict_t)); 358 #endif 359 t = do_compress(ip,ll,op,out_len,t,wrkmem); 360 ip += ll; 361 op += *out_len; 362 l -= ll; 363 } 364 t += l; 365 366 if (t > 0) 367 { 368 const lzo_bytep ii = in + in_len - t; 369 370 if (op == out && t <= 238) 371 *op++ = LZO_BYTE(17 + t); 372 else if (t <= 3) 373 op[-2] = LZO_BYTE(op[-2] | t); 374 else if (t <= 18) 375 *op++ = LZO_BYTE(t - 3); 376 else 377 { 378 lzo_uint tt = t - 18; 379 380 *op++ = 0; 381 while (tt > 255) 382 { 383 tt -= 255; 384 UA_SET1(op, 0); 385 op++; 386 } 387 assert(tt > 0); 388 *op++ = LZO_BYTE(tt); 389 } 390 UA_COPYN(op, ii, t); 391 op += t; 392 } 393 394 *op++ = M4_MARKER | 1; 395 *op++ = 0; 396 *op++ = 0; 397 398 *out_len = pd(op, out); 399 return LZO_E_OK; 400 } 401 402 403 /* 404 vi:ts=4:et 405 */ 406
