Print this page
4936 lz4 could theoretically overflow a pointer with a certain input
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/uts/common/fs/zfs/lz4.c
+++ new/usr/src/uts/common/fs/zfs/lz4.c
1 1 /*
2 2 * LZ4 - Fast LZ compression algorithm
3 3 * Header File
4 4 * Copyright (C) 2011-2013, Yann Collet.
5 5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 6 *
7 7 * Redistribution and use in source and binary forms, with or without
8 8 * modification, are permitted provided that the following conditions are
9 9 * met:
10 10 *
11 11 * * Redistributions of source code must retain the above copyright
12 12 * notice, this list of conditions and the following disclaimer.
13 13 * * Redistributions in binary form must reproduce the above
14 14 * copyright notice, this list of conditions and the following disclaimer
15 15 * in the documentation and/or other materials provided with the
16 16 * distribution.
17 17 *
18 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 29 *
30 30 * You can contact the author at :
31 31 * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
32 32 * - LZ4 source repository : http://code.google.com/p/lz4/
33 33 */
34 34
35 35 #include <sys/zfs_context.h>
36 36
37 37 static int real_LZ4_compress(const char *source, char *dest, int isize,
38 38 int osize);
39 39 static int real_LZ4_uncompress(const char *source, char *dest, int osize);
40 40 static int LZ4_compressBound(int isize);
41 41 static int LZ4_uncompress_unknownOutputSize(const char *source, char *dest,
42 42 int isize, int maxOutputSize);
43 43 static int LZ4_compressCtx(void *ctx, const char *source, char *dest,
44 44 int isize, int osize);
45 45 static int LZ4_compress64kCtx(void *ctx, const char *source, char *dest,
46 46 int isize, int osize);
47 47
48 48 /*ARGSUSED*/
49 49 size_t
50 50 lz4_compress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
51 51 {
52 52 uint32_t bufsiz;
53 53 char *dest = d_start;
54 54
55 55 ASSERT(d_len >= sizeof (bufsiz));
56 56
57 57 bufsiz = real_LZ4_compress(s_start, &dest[sizeof (bufsiz)], s_len,
58 58 d_len - sizeof (bufsiz));
59 59
60 60 /* Signal an error if the compression routine returned zero. */
61 61 if (bufsiz == 0)
62 62 return (s_len);
63 63
64 64 /*
65 65 * Encode the compresed buffer size at the start. We'll need this in
66 66 * decompression to counter the effects of padding which might be
67 67 * added to the compressed buffer and which, if unhandled, would
68 68 * confuse the hell out of our decompression function.
69 69 */
70 70 *(uint32_t *)dest = BE_32(bufsiz);
71 71
72 72 return (bufsiz + sizeof (bufsiz));
73 73 }
74 74
75 75 /*ARGSUSED*/
76 76 int
77 77 lz4_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
78 78 {
79 79 const char *src = s_start;
80 80 uint32_t bufsiz = BE_IN32(src);
81 81
82 82 /* invalid compressed buffer size encoded at start */
83 83 if (bufsiz + sizeof (bufsiz) > s_len)
84 84 return (1);
85 85
86 86 /*
87 87 * Returns 0 on success (decompression function returned non-negative)
88 88 * and non-zero on failure (decompression function returned negative.
89 89 */
90 90 return (LZ4_uncompress_unknownOutputSize(&src[sizeof (bufsiz)],
91 91 d_start, bufsiz, d_len) < 0);
92 92 }
93 93
94 94 /*
95 95 * LZ4 API Description:
96 96 *
97 97 * Simple Functions:
98 98 * real_LZ4_compress() :
99 99 * isize : is the input size. Max supported value is ~1.9GB
100 100 * return : the number of bytes written in buffer dest
101 101 * or 0 if the compression fails (if LZ4_COMPRESSMIN is set).
102 102 * note : destination buffer must be already allocated.
103 103 * destination buffer must be sized to handle worst cases
104 104 * situations (input data not compressible) worst case size
105 105 * evaluation is provided by function LZ4_compressBound().
106 106 *
107 107 * real_LZ4_uncompress() :
108 108 * osize : is the output size, therefore the original size
109 109 * return : the number of bytes read in the source buffer.
110 110 * If the source stream is malformed, the function will stop
111 111 * decoding and return a negative result, indicating the byte
112 112 * position of the faulty instruction. This function never
113 113 * writes beyond dest + osize, and is therefore protected
114 114 * against malicious data packets.
115 115 * note : destination buffer must be already allocated
116 116 *
117 117 * Advanced Functions
118 118 *
119 119 * LZ4_compressBound() :
120 120 * Provides the maximum size that LZ4 may output in a "worst case"
121 121 * scenario (input data not compressible) primarily useful for memory
122 122 * allocation of output buffer.
123 123 *
124 124 * isize : is the input size. Max supported value is ~1.9GB
125 125 * return : maximum output size in a "worst case" scenario
126 126 * note : this function is limited by "int" range (2^31-1)
127 127 *
128 128 * LZ4_uncompress_unknownOutputSize() :
129 129 * isize : is the input size, therefore the compressed size
130 130 * maxOutputSize : is the size of the destination buffer (which must be
131 131 * already allocated)
132 132 * return : the number of bytes decoded in the destination buffer
133 133 * (necessarily <= maxOutputSize). If the source stream is
134 134 * malformed, the function will stop decoding and return a
135 135 * negative result, indicating the byte position of the faulty
136 136 * instruction. This function never writes beyond dest +
137 137 * maxOutputSize, and is therefore protected against malicious
138 138 * data packets.
139 139 * note : Destination buffer must be already allocated.
140 140 * This version is slightly slower than real_LZ4_uncompress()
141 141 *
142 142 * LZ4_compressCtx() :
143 143 * This function explicitly handles the CTX memory structure.
144 144 *
145 145 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
146 146 * by the caller (either on the stack or using kmem_zalloc). Passing NULL
147 147 * isn't valid.
148 148 *
149 149 * LZ4_compress64kCtx() :
150 150 * Same as LZ4_compressCtx(), but specific to small inputs (<64KB).
151 151 * isize *Must* be <64KB, otherwise the output will be corrupted.
152 152 *
153 153 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
154 154 * by the caller (either on the stack or using kmem_zalloc). Passing NULL
155 155 * isn't valid.
156 156 */
157 157
158 158 /*
159 159 * Tuning parameters
160 160 */
161 161
162 162 /*
163 163 * COMPRESSIONLEVEL: Increasing this value improves compression ratio
164 164 * Lowering this value reduces memory usage. Reduced memory usage
165 165 * typically improves speed, due to cache effect (ex: L1 32KB for Intel,
166 166 * L1 64KB for AMD). Memory usage formula : N->2^(N+2) Bytes
167 167 * (examples : 12 -> 16KB ; 17 -> 512KB)
168 168 */
169 169 #define COMPRESSIONLEVEL 12
170 170
171 171 /*
172 172 * NOTCOMPRESSIBLE_CONFIRMATION: Decreasing this value will make the
173 173 * algorithm skip faster data segments considered "incompressible".
174 174 * This may decrease compression ratio dramatically, but will be
175 175 * faster on incompressible data. Increasing this value will make
176 176 * the algorithm search more before declaring a segment "incompressible".
177 177 * This could improve compression a bit, but will be slower on
178 178 * incompressible data. The default value (6) is recommended.
179 179 */
180 180 #define NOTCOMPRESSIBLE_CONFIRMATION 6
181 181
182 182 /*
183 183 * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE: This will provide a boost to
184 184 * performance for big endian cpu, but the resulting compressed stream
185 185 * will be incompatible with little-endian CPU. You can set this option
186 186 * to 1 in situations where data will stay within closed environment.
187 187 * This option is useless on Little_Endian CPU (such as x86).
188 188 */
189 189 /* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */
190 190
191 191 /*
192 192 * CPU Feature Detection
193 193 */
194 194
195 195 /* 32 or 64 bits ? */
196 196 #if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || \
197 197 defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || \
198 198 defined(__LP64__) || defined(_LP64))
199 199 #define LZ4_ARCH64 1
200 200 #else
201 201 #define LZ4_ARCH64 0
202 202 #endif
203 203
204 204 /*
205 205 * Limits the amount of stack space that the algorithm may consume to hold
206 206 * the compression lookup table. The value `9' here means we'll never use
207 207 * more than 2k of stack (see above for a description of COMPRESSIONLEVEL).
208 208 * If more memory is needed, it is allocated from the heap.
209 209 */
210 210 #define STACKLIMIT 9
211 211
212 212 /*
213 213 * Little Endian or Big Endian?
214 214 * Note: overwrite the below #define if you know your architecture endianess.
215 215 */
216 216 #if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || \
217 217 defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || \
218 218 defined(__PPC) || defined(PPC) || defined(__powerpc__) || \
219 219 defined(__powerpc) || defined(powerpc) || \
220 220 ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))))
221 221 #define LZ4_BIG_ENDIAN 1
222 222 #else
223 223 /*
224 224 * Little Endian assumed. PDP Endian and other very rare endian format
225 225 * are unsupported.
226 226 */
227 227 #endif
228 228
229 229 /*
230 230 * Unaligned memory access is automatically enabled for "common" CPU,
231 231 * such as x86. For others CPU, the compiler will be more cautious, and
232 232 * insert extra code to ensure aligned access is respected. If you know
233 233 * your target CPU supports unaligned memory access, you may want to
234 234 * force this option manually to improve performance
235 235 */
236 236 #if defined(__ARM_FEATURE_UNALIGNED)
237 237 #define LZ4_FORCE_UNALIGNED_ACCESS 1
238 238 #endif
239 239
240 240 #ifdef __sparc
241 241 #define LZ4_FORCE_SW_BITCOUNT
242 242 #endif
243 243
244 244 /*
245 245 * Compiler Options
246 246 */
247 247 #if __STDC_VERSION__ >= 199901L /* C99 */
248 248 /* "restrict" is a known keyword */
249 249 #else
250 250 /* Disable restrict */
251 251 #define restrict
252 252 #endif
253 253
254 254 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
255 255
256 256 #ifdef _MSC_VER
257 257 /* Visual Studio */
258 258 /* Visual is not C99, but supports some kind of inline */
259 259 #define inline __forceinline
260 260 #if LZ4_ARCH64
261 261 /* For Visual 2005 */
262 262 #pragma intrinsic(_BitScanForward64)
263 263 #pragma intrinsic(_BitScanReverse64)
264 264 #else /* !LZ4_ARCH64 */
265 265 /* For Visual 2005 */
266 266 #pragma intrinsic(_BitScanForward)
267 267 #pragma intrinsic(_BitScanReverse)
268 268 #endif /* !LZ4_ARCH64 */
269 269 #endif /* _MSC_VER */
270 270
271 271 #ifdef _MSC_VER
272 272 #define lz4_bswap16(x) _byteswap_ushort(x)
273 273 #else /* !_MSC_VER */
274 274 #define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | \
275 275 (((x) & 0xffu) << 8)))
276 276 #endif /* !_MSC_VER */
277 277
278 278 #if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
279 279 #define expect(expr, value) (__builtin_expect((expr), (value)))
280 280 #else
281 281 #define expect(expr, value) (expr)
282 282 #endif
283 283
284 284 #define likely(expr) expect((expr) != 0, 1)
285 285 #define unlikely(expr) expect((expr) != 0, 0)
286 286
287 287 /* Basic types */
288 288 #if defined(_MSC_VER)
289 289 /* Visual Studio does not support 'stdint' natively */
290 290 #define BYTE unsigned __int8
291 291 #define U16 unsigned __int16
292 292 #define U32 unsigned __int32
293 293 #define S32 __int32
294 294 #define U64 unsigned __int64
295 295 #else /* !defined(_MSC_VER) */
296 296 #define BYTE uint8_t
297 297 #define U16 uint16_t
298 298 #define U32 uint32_t
299 299 #define S32 int32_t
300 300 #define U64 uint64_t
301 301 #endif /* !defined(_MSC_VER) */
302 302
303 303 #ifndef LZ4_FORCE_UNALIGNED_ACCESS
304 304 #pragma pack(1)
305 305 #endif
306 306
307 307 typedef struct _U16_S {
308 308 U16 v;
309 309 } U16_S;
310 310 typedef struct _U32_S {
311 311 U32 v;
312 312 } U32_S;
313 313 typedef struct _U64_S {
314 314 U64 v;
315 315 } U64_S;
316 316
317 317 #ifndef LZ4_FORCE_UNALIGNED_ACCESS
318 318 #pragma pack()
319 319 #endif
320 320
321 321 #define A64(x) (((U64_S *)(x))->v)
322 322 #define A32(x) (((U32_S *)(x))->v)
323 323 #define A16(x) (((U16_S *)(x))->v)
324 324
325 325 /*
326 326 * Constants
327 327 */
328 328 #define MINMATCH 4
329 329
330 330 #define HASH_LOG COMPRESSIONLEVEL
331 331 #define HASHTABLESIZE (1 << HASH_LOG)
332 332 #define HASH_MASK (HASHTABLESIZE - 1)
333 333
334 334 #define SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION > 2 ? \
335 335 NOTCOMPRESSIBLE_CONFIRMATION : 2)
336 336
337 337 /*
338 338 * Defines if memory is allocated into the stack (local variable),
339 339 * or into the heap (kmem_alloc()).
340 340 */
341 341 #define HEAPMODE (HASH_LOG > STACKLIMIT)
342 342 #define COPYLENGTH 8
343 343 #define LASTLITERALS 5
344 344 #define MFLIMIT (COPYLENGTH + MINMATCH)
345 345 #define MINLENGTH (MFLIMIT + 1)
346 346
347 347 #define MAXD_LOG 16
348 348 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
349 349
350 350 #define ML_BITS 4
351 351 #define ML_MASK ((1U<<ML_BITS)-1)
352 352 #define RUN_BITS (8-ML_BITS)
353 353 #define RUN_MASK ((1U<<RUN_BITS)-1)
354 354
355 355
356 356 /*
357 357 * Architecture-specific macros
358 358 */
359 359 #if LZ4_ARCH64
360 360 #define STEPSIZE 8
361 361 #define UARCH U64
362 362 #define AARCH A64
363 363 #define LZ4_COPYSTEP(s, d) A64(d) = A64(s); d += 8; s += 8;
364 364 #define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d)
365 365 #define LZ4_SECURECOPY(s, d, e) if (d < e) LZ4_WILDCOPY(s, d, e)
366 366 #define HTYPE U32
367 367 #define INITBASE(base) const BYTE* const base = ip
368 368 #else /* !LZ4_ARCH64 */
369 369 #define STEPSIZE 4
370 370 #define UARCH U32
371 371 #define AARCH A32
372 372 #define LZ4_COPYSTEP(s, d) A32(d) = A32(s); d += 4; s += 4;
373 373 #define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d);
374 374 #define LZ4_SECURECOPY LZ4_WILDCOPY
375 375 #define HTYPE const BYTE *
376 376 #define INITBASE(base) const int base = 0
377 377 #endif /* !LZ4_ARCH64 */
378 378
379 379 #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
380 380 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) \
381 381 { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
382 382 #define LZ4_WRITE_LITTLEENDIAN_16(p, i) \
383 383 { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; }
384 384 #else
385 385 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); }
386 386 #define LZ4_WRITE_LITTLEENDIAN_16(p, v) { A16(p) = v; p += 2; }
387 387 #endif
388 388
389 389
390 390 /* Local structures */
391 391 struct refTables {
392 392 HTYPE hashTable[HASHTABLESIZE];
393 393 };
394 394
395 395
396 396 /* Macros */
397 397 #define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH * 8) - \
398 398 HASH_LOG))
399 399 #define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p))
400 400 #define LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e);
401 401 #define LZ4_BLINDCOPY(s, d, l) { BYTE* e = (d) + l; LZ4_WILDCOPY(s, d, e); \
402 402 d = e; }
403 403
404 404
405 405 /* Private functions */
406 406 #if LZ4_ARCH64
407 407
408 408 static inline int
409 409 LZ4_NbCommonBytes(register U64 val)
410 410 {
411 411 #if defined(LZ4_BIG_ENDIAN)
412 412 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
413 413 unsigned long r = 0;
414 414 _BitScanReverse64(&r, val);
415 415 return (int)(r >> 3);
416 416 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
417 417 !defined(LZ4_FORCE_SW_BITCOUNT)
418 418 return (__builtin_clzll(val) >> 3);
419 419 #else
420 420 int r;
421 421 if (!(val >> 32)) {
422 422 r = 4;
423 423 } else {
424 424 r = 0;
425 425 val >>= 32;
426 426 }
427 427 if (!(val >> 16)) {
428 428 r += 2;
429 429 val >>= 8;
430 430 } else {
431 431 val >>= 24;
432 432 }
433 433 r += (!val);
434 434 return (r);
435 435 #endif
436 436 #else
437 437 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
438 438 unsigned long r = 0;
439 439 _BitScanForward64(&r, val);
440 440 return (int)(r >> 3);
441 441 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
442 442 !defined(LZ4_FORCE_SW_BITCOUNT)
443 443 return (__builtin_ctzll(val) >> 3);
444 444 #else
445 445 static const int DeBruijnBytePos[64] =
446 446 { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5,
447 447 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5,
448 448 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4,
449 449 4, 5, 7, 2, 6, 5, 7, 6, 7, 7
450 450 };
451 451 return DeBruijnBytePos[((U64) ((val & -val) * 0x0218A392CDABBD3F)) >>
452 452 58];
453 453 #endif
454 454 #endif
455 455 }
456 456
457 457 #else
458 458
459 459 static inline int
460 460 LZ4_NbCommonBytes(register U32 val)
461 461 {
462 462 #if defined(LZ4_BIG_ENDIAN)
463 463 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
464 464 unsigned long r = 0;
465 465 _BitScanReverse(&r, val);
466 466 return (int)(r >> 3);
467 467 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
468 468 !defined(LZ4_FORCE_SW_BITCOUNT)
469 469 return (__builtin_clz(val) >> 3);
470 470 #else
471 471 int r;
472 472 if (!(val >> 16)) {
473 473 r = 2;
474 474 val >>= 8;
475 475 } else {
476 476 r = 0;
477 477 val >>= 24;
478 478 }
479 479 r += (!val);
480 480 return (r);
481 481 #endif
482 482 #else
483 483 #if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
484 484 unsigned long r = 0;
485 485 _BitScanForward(&r, val);
486 486 return (int)(r >> 3);
487 487 #elif defined(__GNUC__) && (GCC_VERSION >= 304) && \
488 488 !defined(LZ4_FORCE_SW_BITCOUNT)
489 489 return (__builtin_ctz(val) >> 3);
490 490 #else
491 491 static const int DeBruijnBytePos[32] = {
492 492 0, 0, 3, 0, 3, 1, 3, 0,
493 493 3, 2, 2, 1, 3, 2, 0, 1,
494 494 3, 3, 1, 2, 2, 2, 2, 0,
495 495 3, 1, 2, 0, 1, 0, 1, 1
496 496 };
497 497 return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >>
498 498 27];
499 499 #endif
500 500 #endif
501 501 }
502 502
503 503 #endif
504 504
505 505 /* Public functions */
506 506
507 507 static int
508 508 LZ4_compressBound(int isize)
509 509 {
510 510 return (isize + (isize / 255) + 16);
511 511 }
512 512
513 513 /* Compression functions */
514 514
515 515 /*ARGSUSED*/
516 516 static int
517 517 LZ4_compressCtx(void *ctx, const char *source, char *dest, int isize,
518 518 int osize)
519 519 {
520 520 #if HEAPMODE
521 521 struct refTables *srt = (struct refTables *)ctx;
522 522 HTYPE *HashTable = (HTYPE *) (srt->hashTable);
523 523 #else
524 524 HTYPE HashTable[HASHTABLESIZE] = { 0 };
525 525 #endif
526 526
527 527 const BYTE *ip = (BYTE *) source;
528 528 INITBASE(base);
529 529 const BYTE *anchor = ip;
530 530 const BYTE *const iend = ip + isize;
531 531 const BYTE *const oend = (BYTE *) dest + osize;
532 532 const BYTE *const mflimit = iend - MFLIMIT;
533 533 #define matchlimit (iend - LASTLITERALS)
534 534
535 535 BYTE *op = (BYTE *) dest;
536 536
537 537 int len, length;
538 538 const int skipStrength = SKIPSTRENGTH;
539 539 U32 forwardH;
540 540
541 541
542 542 /* Init */
543 543 if (isize < MINLENGTH)
544 544 goto _last_literals;
545 545
546 546 /* First Byte */
547 547 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
548 548 ip++;
549 549 forwardH = LZ4_HASH_VALUE(ip);
550 550
551 551 /* Main Loop */
552 552 for (;;) {
553 553 int findMatchAttempts = (1U << skipStrength) + 3;
554 554 const BYTE *forwardIp = ip;
555 555 const BYTE *ref;
556 556 BYTE *token;
557 557
558 558 /* Find a match */
559 559 do {
560 560 U32 h = forwardH;
561 561 int step = findMatchAttempts++ >> skipStrength;
562 562 ip = forwardIp;
563 563 forwardIp = ip + step;
564 564
565 565 if unlikely(forwardIp > mflimit) {
566 566 goto _last_literals;
567 567 }
568 568
569 569 forwardH = LZ4_HASH_VALUE(forwardIp);
570 570 ref = base + HashTable[h];
571 571 HashTable[h] = ip - base;
572 572
573 573 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
574 574
575 575 /* Catch up */
576 576 while ((ip > anchor) && (ref > (BYTE *) source) &&
577 577 unlikely(ip[-1] == ref[-1])) {
578 578 ip--;
579 579 ref--;
580 580 }
581 581
582 582 /* Encode Literal length */
583 583 length = ip - anchor;
584 584 token = op++;
585 585
586 586 /* Check output limit */
587 587 if unlikely(op + length + (2 + 1 + LASTLITERALS) +
588 588 (length >> 8) > oend)
589 589 return (0);
590 590
591 591 if (length >= (int)RUN_MASK) {
592 592 *token = (RUN_MASK << ML_BITS);
593 593 len = length - RUN_MASK;
594 594 for (; len > 254; len -= 255)
595 595 *op++ = 255;
596 596 *op++ = (BYTE)len;
597 597 } else
598 598 *token = (length << ML_BITS);
599 599
600 600 /* Copy Literals */
601 601 LZ4_BLINDCOPY(anchor, op, length);
602 602
603 603 _next_match:
604 604 /* Encode Offset */
605 605 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
606 606
607 607 /* Start Counting */
608 608 ip += MINMATCH;
609 609 ref += MINMATCH; /* MinMatch verified */
610 610 anchor = ip;
611 611 while likely(ip < matchlimit - (STEPSIZE - 1)) {
612 612 UARCH diff = AARCH(ref) ^ AARCH(ip);
613 613 if (!diff) {
614 614 ip += STEPSIZE;
615 615 ref += STEPSIZE;
616 616 continue;
617 617 }
618 618 ip += LZ4_NbCommonBytes(diff);
619 619 goto _endCount;
620 620 }
621 621 #if LZ4_ARCH64
622 622 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
623 623 ip += 4;
624 624 ref += 4;
625 625 }
626 626 #endif
627 627 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
628 628 ip += 2;
629 629 ref += 2;
630 630 }
631 631 if ((ip < matchlimit) && (*ref == *ip))
632 632 ip++;
633 633 _endCount:
634 634
635 635 /* Encode MatchLength */
636 636 len = (ip - anchor);
637 637 /* Check output limit */
638 638 if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
639 639 return (0);
640 640 if (len >= (int)ML_MASK) {
641 641 *token += ML_MASK;
642 642 len -= ML_MASK;
643 643 for (; len > 509; len -= 510) {
644 644 *op++ = 255;
645 645 *op++ = 255;
646 646 }
647 647 if (len > 254) {
648 648 len -= 255;
649 649 *op++ = 255;
650 650 }
651 651 *op++ = (BYTE)len;
652 652 } else
653 653 *token += len;
654 654
655 655 /* Test end of chunk */
656 656 if (ip > mflimit) {
657 657 anchor = ip;
658 658 break;
659 659 }
660 660 /* Fill table */
661 661 HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base;
662 662
663 663 /* Test next position */
664 664 ref = base + HashTable[LZ4_HASH_VALUE(ip)];
665 665 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
666 666 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
667 667 token = op++;
668 668 *token = 0;
669 669 goto _next_match;
670 670 }
671 671 /* Prepare next loop */
672 672 anchor = ip++;
673 673 forwardH = LZ4_HASH_VALUE(ip);
674 674 }
675 675
676 676 _last_literals:
677 677 /* Encode Last Literals */
678 678 {
679 679 int lastRun = iend - anchor;
680 680 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
681 681 oend)
682 682 return (0);
683 683 if (lastRun >= (int)RUN_MASK) {
684 684 *op++ = (RUN_MASK << ML_BITS);
685 685 lastRun -= RUN_MASK;
686 686 for (; lastRun > 254; lastRun -= 255) {
687 687 *op++ = 255;
688 688 }
689 689 *op++ = (BYTE)lastRun;
690 690 } else
691 691 *op++ = (lastRun << ML_BITS);
692 692 (void) memcpy(op, anchor, iend - anchor);
693 693 op += iend - anchor;
694 694 }
695 695
696 696 /* End */
697 697 return (int)(((char *)op) - dest);
698 698 }
699 699
700 700
701 701
702 702 /* Note : this function is valid only if isize < LZ4_64KLIMIT */
703 703 #define LZ4_64KLIMIT ((1 << 16) + (MFLIMIT - 1))
704 704 #define HASHLOG64K (HASH_LOG + 1)
705 705 #define HASH64KTABLESIZE (1U << HASHLOG64K)
706 706 #define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8) - \
707 707 HASHLOG64K))
708 708 #define LZ4_HASH64K_VALUE(p) LZ4_HASH64K_FUNCTION(A32(p))
709 709
710 710 /*ARGSUSED*/
711 711 static int
712 712 LZ4_compress64kCtx(void *ctx, const char *source, char *dest, int isize,
713 713 int osize)
714 714 {
715 715 #if HEAPMODE
716 716 struct refTables *srt = (struct refTables *)ctx;
717 717 U16 *HashTable = (U16 *) (srt->hashTable);
718 718 #else
719 719 U16 HashTable[HASH64KTABLESIZE] = { 0 };
720 720 #endif
721 721
722 722 const BYTE *ip = (BYTE *) source;
723 723 const BYTE *anchor = ip;
724 724 const BYTE *const base = ip;
725 725 const BYTE *const iend = ip + isize;
726 726 const BYTE *const oend = (BYTE *) dest + osize;
727 727 const BYTE *const mflimit = iend - MFLIMIT;
728 728 #define matchlimit (iend - LASTLITERALS)
729 729
730 730 BYTE *op = (BYTE *) dest;
731 731
732 732 int len, length;
733 733 const int skipStrength = SKIPSTRENGTH;
734 734 U32 forwardH;
735 735
736 736 /* Init */
737 737 if (isize < MINLENGTH)
738 738 goto _last_literals;
739 739
740 740 /* First Byte */
741 741 ip++;
742 742 forwardH = LZ4_HASH64K_VALUE(ip);
743 743
744 744 /* Main Loop */
745 745 for (;;) {
746 746 int findMatchAttempts = (1U << skipStrength) + 3;
747 747 const BYTE *forwardIp = ip;
748 748 const BYTE *ref;
749 749 BYTE *token;
750 750
751 751 /* Find a match */
752 752 do {
753 753 U32 h = forwardH;
754 754 int step = findMatchAttempts++ >> skipStrength;
755 755 ip = forwardIp;
756 756 forwardIp = ip + step;
757 757
758 758 if (forwardIp > mflimit) {
759 759 goto _last_literals;
760 760 }
761 761
762 762 forwardH = LZ4_HASH64K_VALUE(forwardIp);
763 763 ref = base + HashTable[h];
764 764 HashTable[h] = ip - base;
765 765
766 766 } while (A32(ref) != A32(ip));
767 767
768 768 /* Catch up */
769 769 while ((ip > anchor) && (ref > (BYTE *) source) &&
770 770 (ip[-1] == ref[-1])) {
771 771 ip--;
772 772 ref--;
773 773 }
774 774
775 775 /* Encode Literal length */
776 776 length = ip - anchor;
777 777 token = op++;
778 778
779 779 /* Check output limit */
780 780 if unlikely(op + length + (2 + 1 + LASTLITERALS) +
781 781 (length >> 8) > oend)
782 782 return (0);
783 783
784 784 if (length >= (int)RUN_MASK) {
785 785 *token = (RUN_MASK << ML_BITS);
786 786 len = length - RUN_MASK;
787 787 for (; len > 254; len -= 255)
788 788 *op++ = 255;
789 789 *op++ = (BYTE)len;
790 790 } else
791 791 *token = (length << ML_BITS);
792 792
793 793 /* Copy Literals */
794 794 LZ4_BLINDCOPY(anchor, op, length);
795 795
796 796 _next_match:
797 797 /* Encode Offset */
798 798 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
799 799
800 800 /* Start Counting */
801 801 ip += MINMATCH;
802 802 ref += MINMATCH; /* MinMatch verified */
803 803 anchor = ip;
804 804 while (ip < matchlimit - (STEPSIZE - 1)) {
805 805 UARCH diff = AARCH(ref) ^ AARCH(ip);
806 806 if (!diff) {
807 807 ip += STEPSIZE;
808 808 ref += STEPSIZE;
809 809 continue;
810 810 }
811 811 ip += LZ4_NbCommonBytes(diff);
812 812 goto _endCount;
813 813 }
814 814 #if LZ4_ARCH64
815 815 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
816 816 ip += 4;
817 817 ref += 4;
818 818 }
819 819 #endif
820 820 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
821 821 ip += 2;
822 822 ref += 2;
823 823 }
824 824 if ((ip < matchlimit) && (*ref == *ip))
825 825 ip++;
826 826 _endCount:
827 827
828 828 /* Encode MatchLength */
829 829 len = (ip - anchor);
830 830 /* Check output limit */
831 831 if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
832 832 return (0);
833 833 if (len >= (int)ML_MASK) {
834 834 *token += ML_MASK;
835 835 len -= ML_MASK;
836 836 for (; len > 509; len -= 510) {
837 837 *op++ = 255;
838 838 *op++ = 255;
839 839 }
840 840 if (len > 254) {
841 841 len -= 255;
842 842 *op++ = 255;
843 843 }
844 844 *op++ = (BYTE)len;
845 845 } else
846 846 *token += len;
847 847
848 848 /* Test end of chunk */
849 849 if (ip > mflimit) {
850 850 anchor = ip;
851 851 break;
852 852 }
853 853 /* Fill table */
854 854 HashTable[LZ4_HASH64K_VALUE(ip - 2)] = ip - 2 - base;
855 855
856 856 /* Test next position */
857 857 ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];
858 858 HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base;
859 859 if (A32(ref) == A32(ip)) {
860 860 token = op++;
861 861 *token = 0;
862 862 goto _next_match;
863 863 }
864 864 /* Prepare next loop */
865 865 anchor = ip++;
866 866 forwardH = LZ4_HASH64K_VALUE(ip);
867 867 }
868 868
869 869 _last_literals:
870 870 /* Encode Last Literals */
871 871 {
872 872 int lastRun = iend - anchor;
873 873 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
874 874 oend)
875 875 return (0);
876 876 if (lastRun >= (int)RUN_MASK) {
877 877 *op++ = (RUN_MASK << ML_BITS);
878 878 lastRun -= RUN_MASK;
879 879 for (; lastRun > 254; lastRun -= 255)
880 880 *op++ = 255;
881 881 *op++ = (BYTE)lastRun;
882 882 } else
883 883 *op++ = (lastRun << ML_BITS);
884 884 (void) memcpy(op, anchor, iend - anchor);
885 885 op += iend - anchor;
886 886 }
887 887
888 888 /* End */
889 889 return (int)(((char *)op) - dest);
890 890 }
891 891
892 892 static int
893 893 real_LZ4_compress(const char *source, char *dest, int isize, int osize)
894 894 {
895 895 #if HEAPMODE
896 896 void *ctx = kmem_zalloc(sizeof (struct refTables), KM_NOSLEEP);
897 897 int result;
898 898
899 899 /*
900 900 * out of kernel memory, gently fall through - this will disable
901 901 * compression in zio_compress_data
902 902 */
903 903 if (ctx == NULL)
904 904 return (0);
905 905
906 906 if (isize < LZ4_64KLIMIT)
907 907 result = LZ4_compress64kCtx(ctx, source, dest, isize, osize);
908 908 else
909 909 result = LZ4_compressCtx(ctx, source, dest, isize, osize);
910 910
911 911 kmem_free(ctx, sizeof (struct refTables));
912 912 return (result);
913 913 #else
914 914 if (isize < (int)LZ4_64KLIMIT)
915 915 return (LZ4_compress64kCtx(NULL, source, dest, isize, osize));
916 916 return (LZ4_compressCtx(NULL, source, dest, isize, osize));
917 917 #endif
918 918 }
919 919
920 920 /* Decompression functions */
921 921
922 922 /*
923 923 * Note: The decoding functions real_LZ4_uncompress() and
924 924 * LZ4_uncompress_unknownOutputSize() are safe against "buffer overflow"
925 925 * attack type. They will never write nor read outside of the provided
926 926 * output buffers. LZ4_uncompress_unknownOutputSize() also insures that
927 927 * it will never read outside of the input buffer. A corrupted input
928 928 * will produce an error result, a negative int, indicating the position
929 929 * of the error within input stream.
930 930 */
931 931
932 932 static int
933 933 real_LZ4_uncompress(const char *source, char *dest, int osize)
934 934 {
935 935 /* Local Variables */
936 936 const BYTE *restrict ip = (const BYTE *) source;
937 937 const BYTE *ref;
938 938
939 939 BYTE *op = (BYTE *) dest;
940 940 BYTE *const oend = op + osize;
941 941 BYTE *cpy;
942 942
943 943 unsigned token;
944 944
945 945 size_t length;
946 946 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
947 947 #if LZ4_ARCH64
948 948 size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
949 949 #endif
950 950
951 951 /* Main Loop */
952 952 for (;;) {
|
↓ open down ↓ |
952 lines elided |
↑ open up ↑ |
953 953 /* get runlength */
954 954 token = *ip++;
955 955 if ((length = (token >> ML_BITS)) == RUN_MASK) {
956 956 size_t len;
957 957 for (; (len = *ip++) == 255; length += 255) {
958 958 }
959 959 length += len;
960 960 }
961 961 /* copy literals */
962 962 cpy = op + length;
963 + /* CORNER-CASE: cpy might overflow. */
964 + if (cpy < op)
965 + goto _output_error; /* cpy was overflowed, bail! */
963 966 if unlikely(cpy > oend - COPYLENGTH) {
964 967 if (cpy != oend)
965 968 /* Error: we must necessarily stand at EOF */
966 969 goto _output_error;
967 970 (void) memcpy(op, ip, length);
968 971 ip += length;
969 972 break; /* EOF */
970 973 }
971 974 LZ4_WILDCOPY(ip, op, cpy);
972 975 ip -= (op - cpy);
973 976 op = cpy;
974 977
975 978 /* get offset */
976 979 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
977 980 ip += 2;
978 981 if unlikely(ref < (BYTE * const) dest)
979 982 /*
980 983 * Error: offset create reference outside destination
981 984 * buffer
982 985 */
983 986 goto _output_error;
984 987
985 988 /* get matchlength */
986 989 if ((length = (token & ML_MASK)) == ML_MASK) {
987 990 for (; *ip == 255; length += 255) {
988 991 ip++;
989 992 }
990 993 length += *ip++;
991 994 }
992 995 /* copy repeated sequence */
993 996 if unlikely(op - ref < STEPSIZE) {
994 997 #if LZ4_ARCH64
995 998 size_t dec64 = dec64table[op-ref];
996 999 #else
997 1000 const int dec64 = 0;
998 1001 #endif
999 1002 op[0] = ref[0];
1000 1003 op[1] = ref[1];
1001 1004 op[2] = ref[2];
1002 1005 op[3] = ref[3];
1003 1006 op += 4;
1004 1007 ref += 4;
1005 1008 ref -= dec32table[op-ref];
1006 1009 A32(op) = A32(ref);
1007 1010 op += STEPSIZE - 4;
1008 1011 ref -= dec64;
1009 1012 } else {
1010 1013 LZ4_COPYSTEP(ref, op);
1011 1014 }
1012 1015 cpy = op + length - (STEPSIZE - 4);
1013 1016 if (cpy > oend - COPYLENGTH) {
1014 1017 if (cpy > oend)
1015 1018 /*
1016 1019 * Error: request to write beyond destination
1017 1020 * buffer
1018 1021 */
1019 1022 goto _output_error;
1020 1023 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
1021 1024 while (op < cpy)
1022 1025 *op++ = *ref++;
1023 1026 op = cpy;
1024 1027 if (op == oend)
1025 1028 /*
1026 1029 * Check EOF (should never happen, since last
1027 1030 * 5 bytes are supposed to be literals)
1028 1031 */
1029 1032 goto _output_error;
1030 1033 continue;
1031 1034 }
1032 1035 LZ4_SECURECOPY(ref, op, cpy);
1033 1036 op = cpy; /* correction */
1034 1037 }
1035 1038
1036 1039 /* end of decoding */
1037 1040 return (int)(((char *)ip) - source);
1038 1041
1039 1042 /* write overflow error detected */
1040 1043 _output_error:
1041 1044 return (int)(-(((char *)ip) - source));
1042 1045 }
1043 1046
1044 1047 static int
1045 1048 LZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize,
1046 1049 int maxOutputSize)
1047 1050 {
1048 1051 /* Local Variables */
1049 1052 const BYTE *restrict ip = (const BYTE *) source;
1050 1053 const BYTE *const iend = ip + isize;
1051 1054 const BYTE *ref;
1052 1055
1053 1056 BYTE *op = (BYTE *) dest;
1054 1057 BYTE *const oend = op + maxOutputSize;
1055 1058 BYTE *cpy;
1056 1059
1057 1060 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
1058 1061 #if LZ4_ARCH64
1059 1062 size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
1060 1063 #endif
1061 1064
1062 1065 /* Main Loop */
1063 1066 while (ip < iend) {
1064 1067 unsigned token;
1065 1068 size_t length;
1066 1069
1067 1070 /* get runlength */
|
↓ open down ↓ |
95 lines elided |
↑ open up ↑ |
1068 1071 token = *ip++;
1069 1072 if ((length = (token >> ML_BITS)) == RUN_MASK) {
1070 1073 int s = 255;
1071 1074 while ((ip < iend) && (s == 255)) {
1072 1075 s = *ip++;
1073 1076 length += s;
1074 1077 }
1075 1078 }
1076 1079 /* copy literals */
1077 1080 cpy = op + length;
1081 + /* CORNER-CASE: cpy might overflow. */
1082 + if (cpy < op)
1083 + goto _output_error; /* cpy was overflowed, bail! */
1078 1084 if ((cpy > oend - COPYLENGTH) ||
1079 1085 (ip + length > iend - COPYLENGTH)) {
1080 1086 if (cpy > oend)
1081 1087 /* Error: writes beyond output buffer */
1082 1088 goto _output_error;
1083 1089 if (ip + length != iend)
1084 1090 /*
1085 1091 * Error: LZ4 format requires to consume all
1086 1092 * input at this stage
1087 1093 */
1088 1094 goto _output_error;
1089 1095 (void) memcpy(op, ip, length);
1090 1096 op += length;
1091 1097 /* Necessarily EOF, due to parsing restrictions */
1092 1098 break;
1093 1099 }
1094 1100 LZ4_WILDCOPY(ip, op, cpy);
1095 1101 ip -= (op - cpy);
1096 1102 op = cpy;
1097 1103
1098 1104 /* get offset */
1099 1105 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
1100 1106 ip += 2;
1101 1107 if (ref < (BYTE * const) dest)
1102 1108 /*
1103 1109 * Error: offset creates reference outside of
1104 1110 * destination buffer
1105 1111 */
1106 1112 goto _output_error;
1107 1113
1108 1114 /* get matchlength */
1109 1115 if ((length = (token & ML_MASK)) == ML_MASK) {
1110 1116 while (ip < iend) {
1111 1117 int s = *ip++;
1112 1118 length += s;
1113 1119 if (s == 255)
1114 1120 continue;
1115 1121 break;
1116 1122 }
1117 1123 }
1118 1124 /* copy repeated sequence */
1119 1125 if unlikely(op - ref < STEPSIZE) {
1120 1126 #if LZ4_ARCH64
1121 1127 size_t dec64 = dec64table[op-ref];
1122 1128 #else
1123 1129 const int dec64 = 0;
1124 1130 #endif
1125 1131 op[0] = ref[0];
1126 1132 op[1] = ref[1];
1127 1133 op[2] = ref[2];
1128 1134 op[3] = ref[3];
1129 1135 op += 4;
1130 1136 ref += 4;
1131 1137 ref -= dec32table[op-ref];
1132 1138 A32(op) = A32(ref);
1133 1139 op += STEPSIZE - 4;
1134 1140 ref -= dec64;
1135 1141 } else {
1136 1142 LZ4_COPYSTEP(ref, op);
1137 1143 }
1138 1144 cpy = op + length - (STEPSIZE - 4);
1139 1145 if (cpy > oend - COPYLENGTH) {
1140 1146 if (cpy > oend)
1141 1147 /*
1142 1148 * Error: request to write outside of
1143 1149 * destination buffer
1144 1150 */
1145 1151 goto _output_error;
1146 1152 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
1147 1153 while (op < cpy)
1148 1154 *op++ = *ref++;
1149 1155 op = cpy;
1150 1156 if (op == oend)
1151 1157 /*
1152 1158 * Check EOF (should never happen, since
1153 1159 * last 5 bytes are supposed to be literals)
1154 1160 */
1155 1161 goto _output_error;
1156 1162 continue;
1157 1163 }
1158 1164 LZ4_SECURECOPY(ref, op, cpy);
1159 1165 op = cpy; /* correction */
1160 1166 }
1161 1167
1162 1168 /* end of decoding */
1163 1169 return (int)(((char *)op) - dest);
1164 1170
1165 1171 /* write overflow error detected */
1166 1172 _output_error:
1167 1173 return (int)(-(((char *)ip) - source));
1168 1174 }
|
↓ open down ↓ |
81 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX