1 /*
2 * LZ4 - Fast LZ compression algorithm
3 * Header File
4 * Copyright (C) 2011-2013, Yann Collet.
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * You can contact the author at :
31 * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
32 * - LZ4 source repository : http://code.google.com/p/lz4/
33 */
34
35 /*
36 * N.B. - This file seems to be based on LZ4 r85, dated Dec 10, 2012
37 */
38
39 #include <sys/zfs_context.h>
40 #include <sys/zio_compress.h>
41
42 static int real_LZ4_compress(const char *source, char *dest, int isize,
43 int osize);
44 static int LZ4_compressCtx(void *ctx, const char *source, char *dest,
45 int isize, int osize);
46 static int LZ4_compress64kCtx(void *ctx, const char *source, char *dest,
47 int isize, int osize);
48
49 /* See lz4.c */
50 int LZ4_uncompress_unknownOutputSize(const char *source, char *dest,
51 int isize, int maxOutputSize);
52
53 static void *lz4_alloc(int flags);
54 static void lz4_free(void *ctx);
55
56 size_t
lz4_compress_zfs(void * s_start,void * d_start,size_t s_len,size_t d_len,int n)57 lz4_compress_zfs(void *s_start, void *d_start, size_t s_len,
58 size_t d_len, int n)
59 {
60 (void) n;
61 uint32_t bufsiz;
62 char *dest = d_start;
63
64 ASSERT(d_len >= sizeof (bufsiz));
65
66 bufsiz = real_LZ4_compress(s_start, &dest[sizeof (bufsiz)], s_len,
67 d_len - sizeof (bufsiz));
68
69 /* Signal an error if the compression routine returned zero. */
70 if (bufsiz == 0)
71 return (s_len);
72
73 /*
74 * The exact compressed size is needed by the decompression routine,
75 * so it is stored at the start of the buffer. Note that this may be
76 * less than the compressed block size, which is rounded up to a
77 * multiple of 1<<ashift.
78 */
79 *(uint32_t *)dest = BE_32(bufsiz);
80
81 return (bufsiz + sizeof (bufsiz));
82 }
83
84 int
lz4_decompress_zfs(void * s_start,void * d_start,size_t s_len,size_t d_len,int n)85 lz4_decompress_zfs(void *s_start, void *d_start, size_t s_len,
86 size_t d_len, int n)
87 {
88 (void) n;
89 const char *src = s_start;
90 uint32_t bufsiz = BE_IN32(src);
91
92 /* invalid compressed buffer size encoded at start */
93 if (bufsiz + sizeof (bufsiz) > s_len)
94 return (1);
95
96 /*
97 * Returns 0 on success (decompression function returned non-negative)
98 * and non-zero on failure (decompression function returned negative).
99 */
100 return (LZ4_uncompress_unknownOutputSize(&src[sizeof (bufsiz)],
101 d_start, bufsiz, d_len) < 0);
102 }
103
104 /*
105 * LZ4 API Description:
106 *
107 * Simple Functions:
108 * real_LZ4_compress() :
109 * isize : is the input size. Max supported value is ~1.9GB
110 * return : the number of bytes written in buffer dest
111 * or 0 if the compression fails (if LZ4_COMPRESSMIN is set).
112 * note : destination buffer must be already allocated.
113 * destination buffer must be sized to handle worst cases
114 * situations (input data not compressible) worst case size
115 * evaluation is provided by function LZ4_compressBound().
116 *
117 * real_LZ4_uncompress() :
118 * osize : is the output size, therefore the original size
119 * return : the number of bytes read in the source buffer.
120 * If the source stream is malformed, the function will stop
121 * decoding and return a negative result, indicating the byte
122 * position of the faulty instruction. This function never
123 * writes beyond dest + osize, and is therefore protected
124 * against malicious data packets.
125 * note : destination buffer must be already allocated
126 * note : real_LZ4_uncompress() is not used in ZFS so its code
127 * is not present here.
128 *
129 * Advanced Functions
130 *
131 * LZ4_compressBound() :
132 * Provides the maximum size that LZ4 may output in a "worst case"
133 * scenario (input data not compressible) primarily useful for memory
134 * allocation of output buffer.
135 *
136 * isize : is the input size. Max supported value is ~1.9GB
137 * return : maximum output size in a "worst case" scenario
138 * note : this function is limited by "int" range (2^31-1)
139 *
140 * LZ4_uncompress_unknownOutputSize() :
141 * isize : is the input size, therefore the compressed size
142 * maxOutputSize : is the size of the destination buffer (which must be
143 * already allocated)
144 * return : the number of bytes decoded in the destination buffer
145 * (necessarily <= maxOutputSize). If the source stream is
146 * malformed, the function will stop decoding and return a
147 * negative result, indicating the byte position of the faulty
148 * instruction. This function never writes beyond dest +
149 * maxOutputSize, and is therefore protected against malicious
150 * data packets.
151 * note : Destination buffer must be already allocated.
152 * This version is slightly slower than real_LZ4_uncompress()
153 *
154 * LZ4_compressCtx() :
155 * This function explicitly handles the CTX memory structure.
156 *
157 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
158 * by the caller (either on the stack or using kmem_cache_alloc). Passing
159 * NULL isn't valid.
160 *
161 * LZ4_compress64kCtx() :
162 * Same as LZ4_compressCtx(), but specific to small inputs (<64KB).
163 * isize *Must* be <64KB, otherwise the output will be corrupted.
164 *
165 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
166 * by the caller (either on the stack or using kmem_cache_alloc). Passing
167 * NULL isn't valid.
168 */
169
170 /*
171 * Tuning parameters
172 */
173
174 /*
175 * COMPRESSIONLEVEL: Increasing this value improves compression ratio
176 * Lowering this value reduces memory usage. Reduced memory usage
177 * typically improves speed, due to cache effect (ex: L1 32KB for Intel,
178 * L1 64KB for AMD). Memory usage formula : N->2^(N+2) Bytes
179 * (examples : 12 -> 16KB ; 17 -> 512KB)
180 */
181 #define COMPRESSIONLEVEL 12
182
183 /*
184 * NOTCOMPRESSIBLE_CONFIRMATION: Decreasing this value will make the
185 * algorithm skip faster data segments considered "incompressible".
186 * This may decrease compression ratio dramatically, but will be
187 * faster on incompressible data. Increasing this value will make
188 * the algorithm search more before declaring a segment "incompressible".
189 * This could improve compression a bit, but will be slower on
190 * incompressible data. The default value (6) is recommended.
191 */
192 #define NOTCOMPRESSIBLE_CONFIRMATION 6
193
194 /*
195 * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE: This will provide a boost to
196 * performance for big endian cpu, but the resulting compressed stream
197 * will be incompatible with little-endian CPU. You can set this option
198 * to 1 in situations where data will stay within closed environment.
199 * This option is useless on Little_Endian CPU (such as x86).
200 */
201 /* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */
202
203 /*
204 * CPU Feature Detection
205 */
206
207 /* 32 or 64 bits ? */
208 #if defined(_LP64)
209 #define LZ4_ARCH64 1
210 #else
211 #define LZ4_ARCH64 0
212 #endif
213
214 /*
215 * Little Endian or Big Endian?
216 * Note: overwrite the below #define if you know your architecture endianness.
217 */
218 #if defined(_ZFS_BIG_ENDIAN)
219 #define LZ4_BIG_ENDIAN 1
220 #else
221 /*
222 * Little Endian assumed. PDP Endian and other very rare endian format
223 * are unsupported.
224 */
225 #undef LZ4_BIG_ENDIAN
226 #endif
227
228 /*
229 * Unaligned memory access is automatically enabled for "common" CPU,
230 * such as x86. For others CPU, the compiler will be more cautious, and
231 * insert extra code to ensure aligned access is respected. If you know
232 * your target CPU supports unaligned memory access, you may want to
233 * force this option manually to improve performance
234 */
235 #if defined(__ARM_FEATURE_UNALIGNED)
236 #define LZ4_FORCE_UNALIGNED_ACCESS 1
237 #endif
238
239 /*
240 * Illumos : we can't use GCC's __builtin_ctz family of builtins in the
241 * kernel
242 * Linux : we can use GCC's __builtin_ctz family of builtins in the
243 * kernel
244 */
245 #undef LZ4_FORCE_SW_BITCOUNT
246 #if defined(__sparc)
247 #define LZ4_FORCE_SW_BITCOUNT
248 #endif
249
250 /*
251 * Compiler Options
252 */
253 /* Disable restrict */
254 #define restrict
255
256 /*
257 * Linux : GCC_VERSION is defined as of 3.9-rc1, so undefine it.
258 * torvalds/linux@3f3f8d2f48acfd8ed3b8e6b7377935da57b27b16
259 */
260 #ifdef GCC_VERSION
261 #undef GCC_VERSION
262 #endif
263
264 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
265
266 #if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
267 #define expect(expr, value) (__builtin_expect((expr), (value)))
268 #else
269 #define expect(expr, value) (expr)
270 #endif
271
272 #ifndef likely
273 #define likely(expr) expect((expr) != 0, 1)
274 #endif
275
276 #ifndef unlikely
277 #define unlikely(expr) expect((expr) != 0, 0)
278 #endif
279
280 #define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | \
281 (((x) & 0xffu) << 8)))
282
283 /* Basic types */
284 #define BYTE uint8_t
285 #define U16 uint16_t
286 #define U32 uint32_t
287 #define S32 int32_t
288 #define U64 uint64_t
289
290 #ifndef LZ4_FORCE_UNALIGNED_ACCESS
291 #pragma pack(1)
292 #endif
293
294 typedef struct _U16_S {
295 U16 v;
296 } U16_S;
297 typedef struct _U32_S {
298 U32 v;
299 } U32_S;
300 typedef struct _U64_S {
301 U64 v;
302 } U64_S;
303
304 #ifndef LZ4_FORCE_UNALIGNED_ACCESS
305 #pragma pack()
306 #endif
307
308 #define A64(x) (((U64_S *)(x))->v)
309 #define A32(x) (((U32_S *)(x))->v)
310 #define A16(x) (((U16_S *)(x))->v)
311
312 /*
313 * Constants
314 */
315 #define MINMATCH 4
316
317 #define HASH_LOG COMPRESSIONLEVEL
318 #define HASHTABLESIZE (1 << HASH_LOG)
319 #define HASH_MASK (HASHTABLESIZE - 1)
320
321 #define SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION > 2 ? \
322 NOTCOMPRESSIBLE_CONFIRMATION : 2)
323
324 #define COPYLENGTH 8
325 #define LASTLITERALS 5
326 #define MFLIMIT (COPYLENGTH + MINMATCH)
327 #define MINLENGTH (MFLIMIT + 1)
328
329 #define MAXD_LOG 16
330 #define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
331
332 #define ML_BITS 4
333 #define ML_MASK ((1U<<ML_BITS)-1)
334 #define RUN_BITS (8-ML_BITS)
335 #define RUN_MASK ((1U<<RUN_BITS)-1)
336
337
338 /*
339 * Architecture-specific macros
340 */
341 #if LZ4_ARCH64
342 #define STEPSIZE 8
343 #define UARCH U64
344 #define AARCH A64
345 #define LZ4_COPYSTEP(s, d) A64(d) = A64(s); d += 8; s += 8;
346 #define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d)
347 #define LZ4_SECURECOPY(s, d, e) if (d < e) LZ4_WILDCOPY(s, d, e)
348 #define HTYPE U32
349 #define INITBASE(base) const BYTE* const base = ip
350 #else /* !LZ4_ARCH64 */
351 #define STEPSIZE 4
352 #define UARCH U32
353 #define AARCH A32
354 #define LZ4_COPYSTEP(s, d) A32(d) = A32(s); d += 4; s += 4;
355 #define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d);
356 #define LZ4_SECURECOPY LZ4_WILDCOPY
357 #define HTYPE const BYTE *
358 #define INITBASE(base) const int base = 0
359 #endif /* !LZ4_ARCH64 */
360
361 #if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
362 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) \
363 { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
364 #define LZ4_WRITE_LITTLEENDIAN_16(p, i) \
365 { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; }
366 #else
367 #define LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); }
368 #define LZ4_WRITE_LITTLEENDIAN_16(p, v) { A16(p) = v; p += 2; }
369 #endif
370
371
372 /* Local structures */
373 struct refTables {
374 HTYPE hashTable[HASHTABLESIZE];
375 };
376
377
378 /* Macros */
379 #define LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH * 8) - \
380 HASH_LOG))
381 #define LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p))
382 #define LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e);
383 #define LZ4_BLINDCOPY(s, d, l) { BYTE* e = (d) + l; LZ4_WILDCOPY(s, d, e); \
384 d = e; }
385
386
387 /* Private functions */
388 #if LZ4_ARCH64
389
390 static inline int
LZ4_NbCommonBytes(register U64 val)391 LZ4_NbCommonBytes(register U64 val)
392 {
393 #if defined(LZ4_BIG_ENDIAN)
394 #if ((defined(__GNUC__) && (GCC_VERSION >= 304)) || defined(__clang__)) && \
395 !defined(LZ4_FORCE_SW_BITCOUNT)
396 return (__builtin_clzll(val) >> 3);
397 #else
398 int r;
399 if (!(val >> 32)) {
400 r = 4;
401 } else {
402 r = 0;
403 val >>= 32;
404 }
405 if (!(val >> 16)) {
406 r += 2;
407 val >>= 8;
408 } else {
409 val >>= 24;
410 }
411 r += (!val);
412 return (r);
413 #endif
414 #else
415 #if ((defined(__GNUC__) && (GCC_VERSION >= 304)) || defined(__clang__)) && \
416 !defined(LZ4_FORCE_SW_BITCOUNT)
417 return (__builtin_ctzll(val) >> 3);
418 #else
419 static const int DeBruijnBytePos[64] =
420 { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5,
421 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5,
422 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4,
423 4, 5, 7, 2, 6, 5, 7, 6, 7, 7
424 };
425 return DeBruijnBytePos[((U64) ((val & -val) * 0x0218A392CDABBD3F)) >>
426 58];
427 #endif
428 #endif
429 }
430
431 #else
432
433 static inline int
LZ4_NbCommonBytes(register U32 val)434 LZ4_NbCommonBytes(register U32 val)
435 {
436 #if defined(LZ4_BIG_ENDIAN)
437 #if ((defined(__GNUC__) && (GCC_VERSION >= 304)) || defined(__clang__)) && \
438 !defined(LZ4_FORCE_SW_BITCOUNT)
439 return (__builtin_clz(val) >> 3);
440 #else
441 int r;
442 if (!(val >> 16)) {
443 r = 2;
444 val >>= 8;
445 } else {
446 r = 0;
447 val >>= 24;
448 }
449 r += (!val);
450 return (r);
451 #endif
452 #else
453 #if defined(__GNUC__) && (GCC_VERSION >= 304) && \
454 !defined(LZ4_FORCE_SW_BITCOUNT)
455 return (__builtin_ctz(val) >> 3);
456 #else
457 static const int DeBruijnBytePos[32] = {
458 0, 0, 3, 0, 3, 1, 3, 0,
459 3, 2, 2, 1, 3, 2, 0, 1,
460 3, 3, 1, 2, 2, 2, 2, 0,
461 3, 1, 2, 0, 1, 0, 1, 1
462 };
463 return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >>
464 27];
465 #endif
466 #endif
467 }
468
469 #endif
470
471 /* Compression functions */
472
473 static int
LZ4_compressCtx(void * ctx,const char * source,char * dest,int isize,int osize)474 LZ4_compressCtx(void *ctx, const char *source, char *dest, int isize,
475 int osize)
476 {
477 struct refTables *srt = (struct refTables *)ctx;
478 HTYPE *HashTable = (HTYPE *) (srt->hashTable);
479
480 const BYTE *ip = (BYTE *) source;
481 INITBASE(base);
482 const BYTE *anchor = ip;
483 const BYTE *const iend = ip + isize;
484 const BYTE *const oend = (BYTE *) dest + osize;
485 const BYTE *const mflimit = iend - MFLIMIT;
486 #define matchlimit (iend - LASTLITERALS)
487
488 BYTE *op = (BYTE *) dest;
489
490 int len, length;
491 const int skipStrength = SKIPSTRENGTH;
492 U32 forwardH;
493
494
495 /* Init */
496 if (isize < MINLENGTH)
497 goto _last_literals;
498
499 /* First Byte */
500 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
501 ip++;
502 forwardH = LZ4_HASH_VALUE(ip);
503
504 /* Main Loop */
505 for (;;) {
506 int findMatchAttempts = (1U << skipStrength) + 3;
507 const BYTE *forwardIp = ip;
508 const BYTE *ref;
509 BYTE *token;
510
511 /* Find a match */
512 do {
513 U32 h = forwardH;
514 int step = findMatchAttempts++ >> skipStrength;
515 ip = forwardIp;
516 forwardIp = ip + step;
517
518 if (unlikely(forwardIp > mflimit)) {
519 goto _last_literals;
520 }
521
522 forwardH = LZ4_HASH_VALUE(forwardIp);
523 ref = base + HashTable[h];
524 HashTable[h] = ip - base;
525
526 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
527
528 /* Catch up */
529 while ((ip > anchor) && (ref > (BYTE *) source) &&
530 unlikely(ip[-1] == ref[-1])) {
531 ip--;
532 ref--;
533 }
534
535 /* Encode Literal length */
536 length = ip - anchor;
537 token = op++;
538
539 /* Check output limit */
540 if (unlikely(op + length + (2 + 1 + LASTLITERALS) +
541 (length >> 8) > oend))
542 return (0);
543
544 if (length >= (int)RUN_MASK) {
545 *token = (RUN_MASK << ML_BITS);
546 len = length - RUN_MASK;
547 for (; len > 254; len -= 255)
548 *op++ = 255;
549 *op++ = (BYTE)len;
550 } else
551 *token = (length << ML_BITS);
552
553 /* Copy Literals */
554 LZ4_BLINDCOPY(anchor, op, length);
555
556 _next_match:
557 /* Encode Offset */
558 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
559
560 /* Start Counting */
561 ip += MINMATCH;
562 ref += MINMATCH; /* MinMatch verified */
563 anchor = ip;
564 while (likely(ip < matchlimit - (STEPSIZE - 1))) {
565 UARCH diff = AARCH(ref) ^ AARCH(ip);
566 if (!diff) {
567 ip += STEPSIZE;
568 ref += STEPSIZE;
569 continue;
570 }
571 ip += LZ4_NbCommonBytes(diff);
572 goto _endCount;
573 }
574 #if LZ4_ARCH64
575 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
576 ip += 4;
577 ref += 4;
578 }
579 #endif
580 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
581 ip += 2;
582 ref += 2;
583 }
584 if ((ip < matchlimit) && (*ref == *ip))
585 ip++;
586 _endCount:
587
588 /* Encode MatchLength */
589 len = (ip - anchor);
590 /* Check output limit */
591 if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend))
592 return (0);
593 if (len >= (int)ML_MASK) {
594 *token += ML_MASK;
595 len -= ML_MASK;
596 for (; len > 509; len -= 510) {
597 *op++ = 255;
598 *op++ = 255;
599 }
600 if (len > 254) {
601 len -= 255;
602 *op++ = 255;
603 }
604 *op++ = (BYTE)len;
605 } else
606 *token += len;
607
608 /* Test end of chunk */
609 if (ip > mflimit) {
610 anchor = ip;
611 break;
612 }
613 /* Fill table */
614 HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base;
615
616 /* Test next position */
617 ref = base + HashTable[LZ4_HASH_VALUE(ip)];
618 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
619 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
620 token = op++;
621 *token = 0;
622 goto _next_match;
623 }
624 /* Prepare next loop */
625 anchor = ip++;
626 forwardH = LZ4_HASH_VALUE(ip);
627 }
628
629 _last_literals:
630 /* Encode Last Literals */
631 {
632 int lastRun = iend - anchor;
633 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
634 oend)
635 return (0);
636 if (lastRun >= (int)RUN_MASK) {
637 *op++ = (RUN_MASK << ML_BITS);
638 lastRun -= RUN_MASK;
639 for (; lastRun > 254; lastRun -= 255) {
640 *op++ = 255;
641 }
642 *op++ = (BYTE)lastRun;
643 } else
644 *op++ = (lastRun << ML_BITS);
645 (void) memcpy(op, anchor, iend - anchor);
646 op += iend - anchor;
647 }
648
649 /* End */
650 return (int)(((char *)op) - dest);
651 }
652
653
654
655 /* Note : this function is valid only if isize < LZ4_64KLIMIT */
656 #define LZ4_64KLIMIT ((1 << 16) + (MFLIMIT - 1))
657 #define HASHLOG64K (HASH_LOG + 1)
658 #define HASH64KTABLESIZE (1U << HASHLOG64K)
659 #define LZ4_HASH64K_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8) - \
660 HASHLOG64K))
661 #define LZ4_HASH64K_VALUE(p) LZ4_HASH64K_FUNCTION(A32(p))
662
663 static int
LZ4_compress64kCtx(void * ctx,const char * source,char * dest,int isize,int osize)664 LZ4_compress64kCtx(void *ctx, const char *source, char *dest, int isize,
665 int osize)
666 {
667 struct refTables *srt = (struct refTables *)ctx;
668 U16 *HashTable = (U16 *) (srt->hashTable);
669
670 const BYTE *ip = (BYTE *) source;
671 const BYTE *anchor = ip;
672 const BYTE *const base = ip;
673 const BYTE *const iend = ip + isize;
674 const BYTE *const oend = (BYTE *) dest + osize;
675 const BYTE *const mflimit = iend - MFLIMIT;
676 #define matchlimit (iend - LASTLITERALS)
677
678 BYTE *op = (BYTE *) dest;
679
680 int len, length;
681 const int skipStrength = SKIPSTRENGTH;
682 U32 forwardH;
683
684 /* Init */
685 if (isize < MINLENGTH)
686 goto _last_literals;
687
688 /* First Byte */
689 ip++;
690 forwardH = LZ4_HASH64K_VALUE(ip);
691
692 /* Main Loop */
693 for (;;) {
694 int findMatchAttempts = (1U << skipStrength) + 3;
695 const BYTE *forwardIp = ip;
696 const BYTE *ref;
697 BYTE *token;
698
699 /* Find a match */
700 do {
701 U32 h = forwardH;
702 int step = findMatchAttempts++ >> skipStrength;
703 ip = forwardIp;
704 forwardIp = ip + step;
705
706 if (forwardIp > mflimit) {
707 goto _last_literals;
708 }
709
710 forwardH = LZ4_HASH64K_VALUE(forwardIp);
711 ref = base + HashTable[h];
712 HashTable[h] = ip - base;
713
714 } while (A32(ref) != A32(ip));
715
716 /* Catch up */
717 while ((ip > anchor) && (ref > (BYTE *) source) &&
718 (ip[-1] == ref[-1])) {
719 ip--;
720 ref--;
721 }
722
723 /* Encode Literal length */
724 length = ip - anchor;
725 token = op++;
726
727 /* Check output limit */
728 if (unlikely(op + length + (2 + 1 + LASTLITERALS) +
729 (length >> 8) > oend))
730 return (0);
731
732 if (length >= (int)RUN_MASK) {
733 *token = (RUN_MASK << ML_BITS);
734 len = length - RUN_MASK;
735 for (; len > 254; len -= 255)
736 *op++ = 255;
737 *op++ = (BYTE)len;
738 } else
739 *token = (length << ML_BITS);
740
741 /* Copy Literals */
742 LZ4_BLINDCOPY(anchor, op, length);
743
744 _next_match:
745 /* Encode Offset */
746 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
747
748 /* Start Counting */
749 ip += MINMATCH;
750 ref += MINMATCH; /* MinMatch verified */
751 anchor = ip;
752 while (ip < matchlimit - (STEPSIZE - 1)) {
753 UARCH diff = AARCH(ref) ^ AARCH(ip);
754 if (!diff) {
755 ip += STEPSIZE;
756 ref += STEPSIZE;
757 continue;
758 }
759 ip += LZ4_NbCommonBytes(diff);
760 goto _endCount;
761 }
762 #if LZ4_ARCH64
763 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
764 ip += 4;
765 ref += 4;
766 }
767 #endif
768 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
769 ip += 2;
770 ref += 2;
771 }
772 if ((ip < matchlimit) && (*ref == *ip))
773 ip++;
774 _endCount:
775
776 /* Encode MatchLength */
777 len = (ip - anchor);
778 /* Check output limit */
779 if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend))
780 return (0);
781 if (len >= (int)ML_MASK) {
782 *token += ML_MASK;
783 len -= ML_MASK;
784 for (; len > 509; len -= 510) {
785 *op++ = 255;
786 *op++ = 255;
787 }
788 if (len > 254) {
789 len -= 255;
790 *op++ = 255;
791 }
792 *op++ = (BYTE)len;
793 } else
794 *token += len;
795
796 /* Test end of chunk */
797 if (ip > mflimit) {
798 anchor = ip;
799 break;
800 }
801 /* Fill table */
802 HashTable[LZ4_HASH64K_VALUE(ip - 2)] = ip - 2 - base;
803
804 /* Test next position */
805 ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];
806 HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base;
807 if (A32(ref) == A32(ip)) {
808 token = op++;
809 *token = 0;
810 goto _next_match;
811 }
812 /* Prepare next loop */
813 anchor = ip++;
814 forwardH = LZ4_HASH64K_VALUE(ip);
815 }
816
817 _last_literals:
818 /* Encode Last Literals */
819 {
820 int lastRun = iend - anchor;
821 if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
822 oend)
823 return (0);
824 if (lastRun >= (int)RUN_MASK) {
825 *op++ = (RUN_MASK << ML_BITS);
826 lastRun -= RUN_MASK;
827 for (; lastRun > 254; lastRun -= 255)
828 *op++ = 255;
829 *op++ = (BYTE)lastRun;
830 } else
831 *op++ = (lastRun << ML_BITS);
832 (void) memcpy(op, anchor, iend - anchor);
833 op += iend - anchor;
834 }
835
836 /* End */
837 return (int)(((char *)op) - dest);
838 }
839
840 static int
real_LZ4_compress(const char * source,char * dest,int isize,int osize)841 real_LZ4_compress(const char *source, char *dest, int isize, int osize)
842 {
843 void *ctx;
844 int result;
845
846 ctx = lz4_alloc(KM_SLEEP);
847
848 /*
849 * out of kernel memory, gently fall through - this will disable
850 * compression in zio_compress_data
851 */
852 if (ctx == NULL)
853 return (0);
854
855 memset(ctx, 0, sizeof (struct refTables));
856
857 if (isize < LZ4_64KLIMIT)
858 result = LZ4_compress64kCtx(ctx, source, dest, isize, osize);
859 else
860 result = LZ4_compressCtx(ctx, source, dest, isize, osize);
861
862 lz4_free(ctx);
863 return (result);
864 }
865
866 #ifdef __FreeBSD__
867 /*
868 * FreeBSD has 4, 8 and 16 KB malloc zones which can be used here.
869 * Should struct refTables get resized this may need to be revisited, hence
870 * compiler-time asserts.
871 */
872 _Static_assert(sizeof(struct refTables) <= 16384,
873 "refTables too big for malloc");
874 _Static_assert((sizeof(struct refTables) % 4096) == 0,
875 "refTables not a multiple of page size");
876 #else
877 #define ZFS_LZ4_USE_CACHE
878 #endif
879
880 #ifdef ZFS_LZ4_USE_CACHE
881 static kmem_cache_t *lz4_cache;
882 #endif
883
884 #ifdef ZFS_LZ4_USE_CACHE
885 void
lz4_init(void)886 lz4_init(void)
887 {
888 lz4_cache = kmem_cache_create("lz4_cache",
889 sizeof (struct refTables), 0, NULL, NULL, NULL, NULL, NULL, 0);
890 }
891
892 void
lz4_fini(void)893 lz4_fini(void)
894 {
895 if (lz4_cache) {
896 kmem_cache_destroy(lz4_cache);
897 lz4_cache = NULL;
898 }
899 }
900
901 static void *
lz4_alloc(int flags)902 lz4_alloc(int flags)
903 {
904 ASSERT(lz4_cache != NULL);
905 return (kmem_cache_alloc(lz4_cache, flags));
906 }
907
908 static void
lz4_free(void * ctx)909 lz4_free(void *ctx)
910 {
911 kmem_cache_free(lz4_cache, ctx);
912 }
913 #else
914 void
lz4_init(void)915 lz4_init(void)
916 {
917 }
918
919 void
lz4_fini(void)920 lz4_fini(void)
921 {
922 }
923
924 static void *
lz4_alloc(int flags)925 lz4_alloc(int flags)
926 {
927 return (kmem_alloc(sizeof (struct refTables), flags));
928 }
929
930 static void
lz4_free(void * ctx)931 lz4_free(void *ctx)
932 {
933 kmem_free(ctx, sizeof (struct refTables));
934 }
935 #endif
936