summaryrefslogtreecommitdiffstats
path: root/module/zfs/lz4.c
blob: f8294e85e58eb9de71ff35cdbd976227531ac0fe (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
/*
 * LZ4 - Fast LZ compression algorithm
 * Header File
 * Copyright (C) 2011-2013, Yann Collet.
 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * You can contact the author at :
 * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
 * - LZ4 source repository : http://code.google.com/p/lz4/
 */

#include <sys/zfs_context.h>

static int real_LZ4_compress(const char *source, char *dest, int isize,
    int osize);
static int LZ4_uncompress_unknownOutputSize(const char *source, char *dest,
    int isize, int maxOutputSize);
static int LZ4_compressCtx(void *ctx, const char *source, char *dest,
    int isize, int osize);
static int LZ4_compress64kCtx(void *ctx, const char *source, char *dest,
    int isize, int osize);

static kmem_cache_t *lz4_cache;

/*ARGSUSED*/
size_t
lz4_compress_zfs(void *s_start, void *d_start, size_t s_len,
    size_t d_len, int n)
{
	uint32_t bufsiz;
	char *dest = d_start;

	ASSERT(d_len >= sizeof (bufsiz));

	bufsiz = real_LZ4_compress(s_start, &dest[sizeof (bufsiz)], s_len,
	    d_len - sizeof (bufsiz));

	/* Signal an error if the compression routine returned zero. */
	if (bufsiz == 0)
		return (s_len);

	/*
	 * Encode the compressed buffer size at the start. We'll need this in
	 * decompression to counter the effects of padding which might be
	 * added to the compressed buffer and which, if unhandled, would
	 * confuse the hell out of our decompression function.
	 */
	*(uint32_t *)dest = BE_32(bufsiz);

	return (bufsiz + sizeof (bufsiz));
}

/*ARGSUSED*/
int
lz4_decompress_zfs(void *s_start, void *d_start, size_t s_len,
    size_t d_len, int n)
{
	const char *src = s_start;
	uint32_t bufsiz = BE_IN32(src);

	/* invalid compressed buffer size encoded at start */
	if (bufsiz + sizeof (bufsiz) > s_len)
		return (1);

	/*
	 * Returns 0 on success (decompression function returned non-negative)
	 * and non-zero on failure (decompression function returned negative.
	 */
	return (LZ4_uncompress_unknownOutputSize(&src[sizeof (bufsiz)],
	    d_start, bufsiz, d_len) < 0);
}

/*
 * LZ4 API Description:
 *
 * Simple Functions:
 * real_LZ4_compress() :
 * 	isize  : is the input size. Max supported value is ~1.9GB
 * 	return : the number of bytes written in buffer dest
 *		 or 0 if the compression fails (if LZ4_COMPRESSMIN is set).
 * 	note : destination buffer must be already allocated.
 * 		destination buffer must be sized to handle worst cases
 * 		situations (input data not compressible) worst case size
 * 		evaluation is provided by function LZ4_compressBound().
 *
 * real_LZ4_uncompress() :
 * 	osize  : is the output size, therefore the original size
 * 	return : the number of bytes read in the source buffer.
 * 		If the source stream is malformed, the function will stop
 * 		decoding and return a negative result, indicating the byte
 * 		position of the faulty instruction. This function never
 * 		writes beyond dest + osize, and is therefore protected
 * 		against malicious data packets.
 * 	note : destination buffer must be already allocated
 *	note : real_LZ4_uncompress() is not used in ZFS so its code
 *	       is not present here.
 *
 * Advanced Functions
 *
 * LZ4_compressBound() :
 * 	Provides the maximum size that LZ4 may output in a "worst case"
 * 	scenario (input data not compressible) primarily useful for memory
 * 	allocation of output buffer.
 *
 * 	isize  : is the input size. Max supported value is ~1.9GB
 * 	return : maximum output size in a "worst case" scenario
 * 	note : this function is limited by "int" range (2^31-1)
 *
 * LZ4_uncompress_unknownOutputSize() :
 * 	isize  : is the input size, therefore the compressed size
 * 	maxOutputSize : is the size of the destination buffer (which must be
 * 		already allocated)
 * 	return : the number of bytes decoded in the destination buffer
 * 		(necessarily <= maxOutputSize). If the source stream is
 * 		malformed, the function will stop decoding and return a
 * 		negative result, indicating the byte position of the faulty
 * 		instruction. This function never writes beyond dest +
 * 		maxOutputSize, and is therefore protected against malicious
 * 		data packets.
 * 	note   : Destination buffer must be already allocated.
 *		This version is slightly slower than real_LZ4_uncompress()
 *
 * LZ4_compressCtx() :
 * 	This function explicitly handles the CTX memory structure.
 *
 * 	ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
 * 	by the caller (either on the stack or using kmem_cache_alloc). Passing
 * 	NULL isn't valid.
 *
 * LZ4_compress64kCtx() :
 * 	Same as LZ4_compressCtx(), but specific to small inputs (<64KB).
 * 	isize *Must* be <64KB, otherwise the output will be corrupted.
 *
 * 	ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
 * 	by the caller (either on the stack or using kmem_cache_alloc). Passing
 * 	NULL isn't valid.
 */

/*
 * Tuning parameters
 */

/*
 * COMPRESSIONLEVEL: Increasing this value improves compression ratio
 *	 Lowering this value reduces memory usage. Reduced memory usage
 *	typically improves speed, due to cache effect (ex: L1 32KB for Intel,
 *	L1 64KB for AMD). Memory usage formula : N->2^(N+2) Bytes
 *	(examples : 12 -> 16KB ; 17 -> 512KB)
 */
#define	COMPRESSIONLEVEL 12

/*
 * NOTCOMPRESSIBLE_CONFIRMATION: Decreasing this value will make the
 *	algorithm skip faster data segments considered "incompressible".
 *	This may decrease compression ratio dramatically, but will be
 *	faster on incompressible data. Increasing this value will make
 *	the algorithm search more before declaring a segment "incompressible".
 *	This could improve compression a bit, but will be slower on
 *	incompressible data. The default value (6) is recommended.
 */
#define	NOTCOMPRESSIBLE_CONFIRMATION 6

/*
 * BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE: This will provide a boost to
 * performance for big endian cpu, but the resulting compressed stream
 * will be incompatible with little-endian CPU. You can set this option
 * to 1 in situations where data will stay within closed environment.
 * This option is useless on Little_Endian CPU (such as x86).
 */
/* #define	BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */

/*
 * CPU Feature Detection
 */

/* 32 or 64 bits ? */
#if defined(_LP64)
#define	LZ4_ARCH64 1
#else
#define	LZ4_ARCH64 0
#endif

/*
 * Little Endian or Big Endian?
 * Note: overwrite the below #define if you know your architecture endianness.
 */
#if defined(_BIG_ENDIAN)
#define	LZ4_BIG_ENDIAN 1
#else
/*
 * Little Endian assumed. PDP Endian and other very rare endian format
 * are unsupported.
 */
#undef LZ4_BIG_ENDIAN
#endif

/*
 * Unaligned memory access is automatically enabled for "common" CPU,
 * such as x86. For others CPU, the compiler will be more cautious, and
 * insert extra code to ensure aligned access is respected. If you know
 * your target CPU supports unaligned memory access, you may want to
 * force this option manually to improve performance
 */
#if defined(__ARM_FEATURE_UNALIGNED)
#define	LZ4_FORCE_UNALIGNED_ACCESS 1
#endif

/*
 * Illumos : we can't use GCC's __builtin_ctz family of builtins in the
 * kernel
 * Linux : we can use GCC's __builtin_ctz family of builtins in the
 * kernel
 */
#undef	LZ4_FORCE_SW_BITCOUNT
#if defined(__sparc)
#define	LZ4_FORCE_SW_BITCOUNT
#endif

/*
 * Compiler Options
 */
/* Disable restrict */
#define	restrict

/*
 * Linux : GCC_VERSION is defined as of 3.9-rc1, so undefine it.
 * torvalds/linux@3f3f8d2f48acfd8ed3b8e6b7377935da57b27b16
 */
#ifdef GCC_VERSION
#undef GCC_VERSION
#endif

#define	GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)

#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
#define	expect(expr, value)    (__builtin_expect((expr), (value)))
#else
#define	expect(expr, value)    (expr)
#endif

#ifndef likely
#define	likely(expr)	expect((expr) != 0, 1)
#endif

#ifndef unlikely
#define	unlikely(expr)	expect((expr) != 0, 0)
#endif

#define	lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | \
	(((x) & 0xffu) << 8)))

/* Basic types */
#define	BYTE	uint8_t
#define	U16	uint16_t
#define	U32	uint32_t
#define	S32	int32_t
#define	U64	uint64_t

#ifndef LZ4_FORCE_UNALIGNED_ACCESS
#pragma pack(1)
#endif

typedef struct _U16_S {
	U16 v;
} U16_S;
typedef struct _U32_S {
	U32 v;
} U32_S;
typedef struct _U64_S {
	U64 v;
} U64_S;

#ifndef LZ4_FORCE_UNALIGNED_ACCESS
#pragma pack()
#endif

#define	A64(x) (((U64_S *)(x))->v)
#define	A32(x) (((U32_S *)(x))->v)
#define	A16(x) (((U16_S *)(x))->v)

/*
 * Constants
 */
#define	MINMATCH 4

#define	HASH_LOG COMPRESSIONLEVEL
#define	HASHTABLESIZE (1 << HASH_LOG)
#define	HASH_MASK (HASHTABLESIZE - 1)

#define	SKIPSTRENGTH (NOTCOMPRESSIBLE_CONFIRMATION > 2 ? \
	NOTCOMPRESSIBLE_CONFIRMATION : 2)

#define	COPYLENGTH 8
#define	LASTLITERALS 5
#define	MFLIMIT (COPYLENGTH + MINMATCH)
#define	MINLENGTH (MFLIMIT + 1)

#define	MAXD_LOG 16
#define	MAX_DISTANCE ((1 << MAXD_LOG) - 1)

#define	ML_BITS 4
#define	ML_MASK ((1U<<ML_BITS)-1)
#define	RUN_BITS (8-ML_BITS)
#define	RUN_MASK ((1U<<RUN_BITS)-1)


/*
 * Architecture-specific macros
 */
#if LZ4_ARCH64
#define	STEPSIZE 8
#define	UARCH U64
#define	AARCH A64
#define	LZ4_COPYSTEP(s, d)	A64(d) = A64(s); d += 8; s += 8;
#define	LZ4_COPYPACKET(s, d)	LZ4_COPYSTEP(s, d)
#define	LZ4_SECURECOPY(s, d, e)	if (d < e) LZ4_WILDCOPY(s, d, e)
#define	HTYPE U32
#define	INITBASE(base)		const BYTE* const base = ip
#else /* !LZ4_ARCH64 */
#define	STEPSIZE 4
#define	UARCH U32
#define	AARCH A32
#define	LZ4_COPYSTEP(s, d)	A32(d) = A32(s); d += 4; s += 4;
#define	LZ4_COPYPACKET(s, d)	LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d);
#define	LZ4_SECURECOPY		LZ4_WILDCOPY
#define	HTYPE const BYTE *
#define	INITBASE(base)		const int base = 0
#endif /* !LZ4_ARCH64 */

#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
#define	LZ4_READ_LITTLEENDIAN_16(d, s, p) \
	{ U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
#define	LZ4_WRITE_LITTLEENDIAN_16(p, i) \
	{ U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; }
#else
#define	LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); }
#define	LZ4_WRITE_LITTLEENDIAN_16(p, v)  { A16(p) = v; p += 2; }
#endif


/* Local structures */
struct refTables {
	HTYPE hashTable[HASHTABLESIZE];
};


/* Macros */
#define	LZ4_HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH * 8) - \
	HASH_LOG))
#define	LZ4_HASH_VALUE(p) LZ4_HASH_FUNCTION(A32(p))
#define	LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e);
#define	LZ4_BLINDCOPY(s, d, l) { BYTE* e = (d) + l; LZ4_WILDCOPY(s, d, e); \
	d = e; }


/* Private functions */
#if LZ4_ARCH64

static inline int
LZ4_NbCommonBytes(register U64 val)
{
#if defined(LZ4_BIG_ENDIAN)
#if defined(__GNUC__) && (GCC_VERSION >= 304) && \
	!defined(LZ4_FORCE_SW_BITCOUNT)
	return (__builtin_clzll(val) >> 3);
#else
	int r;
	if (!(val >> 32)) {
		r = 4;
	} else {
		r = 0;
		val >>= 32;
	}
	if (!(val >> 16)) {
		r += 2;
		val >>= 8;
	} else {
		val >>= 24;
	}
	r += (!val);
	return (r);
#endif
#else
#if defined(__GNUC__) && (GCC_VERSION >= 304) && \
	!defined(LZ4_FORCE_SW_BITCOUNT)
	return (__builtin_ctzll(val) >> 3);
#else
	static const int DeBruijnBytePos[64] =
	    { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5,
		3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5,
		5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4,
		4, 5, 7, 2, 6, 5, 7, 6, 7, 7
	};
	return DeBruijnBytePos[((U64) ((val & -val) * 0x0218A392CDABBD3F)) >>
	    58];
#endif
#endif
}

#else

static inline int
LZ4_NbCommonBytes(register U32 val)
{
#if defined(LZ4_BIG_ENDIAN)
#if defined(__GNUC__) && (GCC_VERSION >= 304) && \
	!defined(LZ4_FORCE_SW_BITCOUNT)
	return (__builtin_clz(val) >> 3);
#else
	int r;
	if (!(val >> 16)) {
		r = 2;
		val >>= 8;
	} else {
		r = 0;
		val >>= 24;
	}
	r += (!val);
	return (r);
#endif
#else
#if defined(__GNUC__) && (GCC_VERSION >= 304) && \
	!defined(LZ4_FORCE_SW_BITCOUNT)
	return (__builtin_ctz(val) >> 3);
#else
	static const int DeBruijnBytePos[32] = {
		0, 0, 3, 0, 3, 1, 3, 0,
		3, 2, 2, 1, 3, 2, 0, 1,
		3, 3, 1, 2, 2, 2, 2, 0,
		3, 1, 2, 0, 1, 0, 1, 1
	};
	return DeBruijnBytePos[((U32) ((val & -(S32) val) * 0x077CB531U)) >>
	    27];
#endif
#endif
}

#endif

/* Compression functions */

/*ARGSUSED*/
static int
LZ4_compressCtx(void *ctx, const char *source, char *dest, int isize,
    int osize)
{
	struct refTables *srt = (struct refTables *)ctx;
	HTYPE *HashTable = (HTYPE *) (srt->hashTable);

	const BYTE *ip = (BYTE *) source;
	INITBASE(base);
	const BYTE *anchor = ip;
	const BYTE *const iend = ip + isize;
	const BYTE *const oend = (BYTE *) dest + osize;
	const BYTE *const mflimit = iend - MFLIMIT;
#define	matchlimit (iend - LASTLITERALS)

	BYTE *op = (BYTE *) dest;

	int len, length;
	const int skipStrength = SKIPSTRENGTH;
	U32 forwardH;


	/* Init */
	if (isize < MINLENGTH)
		goto _last_literals;

	/* First Byte */
	HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
	ip++;
	forwardH = LZ4_HASH_VALUE(ip);

	/* Main Loop */
	for (;;) {
		int findMatchAttempts = (1U << skipStrength) + 3;
		const BYTE *forwardIp = ip;
		const BYTE *ref;
		BYTE *token;

		/* Find a match */
		do {
			U32 h = forwardH;
			int step = findMatchAttempts++ >> skipStrength;
			ip = forwardIp;
			forwardIp = ip + step;

			if (unlikely(forwardIp > mflimit)) {
				goto _last_literals;
			}

			forwardH = LZ4_HASH_VALUE(forwardIp);
			ref = base + HashTable[h];
			HashTable[h] = ip - base;

		} while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));

		/* Catch up */
		while ((ip > anchor) && (ref > (BYTE *) source) &&
		    unlikely(ip[-1] == ref[-1])) {
			ip--;
			ref--;
		}

		/* Encode Literal length */
		length = ip - anchor;
		token = op++;

		/* Check output limit */
		if (unlikely(op + length + (2 + 1 + LASTLITERALS) +
		    (length >> 8) > oend))
			return (0);

		if (length >= (int)RUN_MASK) {
			*token = (RUN_MASK << ML_BITS);
			len = length - RUN_MASK;
			for (; len > 254; len -= 255)
				*op++ = 255;
			*op++ = (BYTE)len;
		} else
			*token = (length << ML_BITS);

		/* Copy Literals */
		LZ4_BLINDCOPY(anchor, op, length);

		_next_match:
		/* Encode Offset */
		LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);

		/* Start Counting */
		ip += MINMATCH;
		ref += MINMATCH;	/* MinMatch verified */
		anchor = ip;
		while (likely(ip < matchlimit - (STEPSIZE - 1))) {
			UARCH diff = AARCH(ref) ^ AARCH(ip);
			if (!diff) {
				ip += STEPSIZE;
				ref += STEPSIZE;
				continue;
			}
			ip += LZ4_NbCommonBytes(diff);
			goto _endCount;
		}
#if LZ4_ARCH64
		if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
			ip += 4;
			ref += 4;
		}
#endif
		if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
			ip += 2;
			ref += 2;
		}
		if ((ip < matchlimit) && (*ref == *ip))
			ip++;
		_endCount:

		/* Encode MatchLength */
		len = (ip - anchor);
		/* Check output limit */
		if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend))
			return (0);
		if (len >= (int)ML_MASK) {
			*token += ML_MASK;
			len -= ML_MASK;
			for (; len > 509; len -= 510) {
				*op++ = 255;
				*op++ = 255;
			}
			if (len > 254) {
				len -= 255;
				*op++ = 255;
			}
			*op++ = (BYTE)len;
		} else
			*token += len;

		/* Test end of chunk */
		if (ip > mflimit) {
			anchor = ip;
			break;
		}
		/* Fill table */
		HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base;

		/* Test next position */
		ref = base + HashTable[LZ4_HASH_VALUE(ip)];
		HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
		if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
			token = op++;
			*token = 0;
			goto _next_match;
		}
		/* Prepare next loop */
		anchor = ip++;
		forwardH = LZ4_HASH_VALUE(ip);
	}

	_last_literals:
	/* Encode Last Literals */
	{
		int lastRun = iend - anchor;
		if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
		    oend)
			return (0);
		if (lastRun >= (int)RUN_MASK) {
			*op++ = (RUN_MASK << ML_BITS);
			lastRun -= RUN_MASK;
			for (; lastRun > 254; lastRun -= 255) {
				*op++ = 255;
			}
			*op++ = (BYTE)lastRun;
		} else
			*op++ = (lastRun << ML_BITS);
		(void) memcpy(op, anchor, iend - anchor);
		op += iend - anchor;
	}

	/* End */
	return (int)(((char *)op) - dest);
}



/* Note : this function is valid only if isize < LZ4_64KLIMIT */
#define	LZ4_64KLIMIT ((1 << 16) + (MFLIMIT - 1))
#define	HASHLOG64K (HASH_LOG + 1)
#define	HASH64KTABLESIZE (1U << HASHLOG64K)
#define	LZ4_HASH64K_FUNCTION(i)	(((i) * 2654435761U) >> ((MINMATCH*8) - \
	HASHLOG64K))
#define	LZ4_HASH64K_VALUE(p)	LZ4_HASH64K_FUNCTION(A32(p))

/*ARGSUSED*/
static int
LZ4_compress64kCtx(void *ctx, const char *source, char *dest, int isize,
    int osize)
{
	struct refTables *srt = (struct refTables *)ctx;
	U16 *HashTable = (U16 *) (srt->hashTable);

	const BYTE *ip = (BYTE *) source;
	const BYTE *anchor = ip;
	const BYTE *const base = ip;
	const BYTE *const iend = ip + isize;
	const BYTE *const oend = (BYTE *) dest + osize;
	const BYTE *const mflimit = iend - MFLIMIT;
#define	matchlimit (iend - LASTLITERALS)

	BYTE *op = (BYTE *) dest;

	int len, length;
	const int skipStrength = SKIPSTRENGTH;
	U32 forwardH;

	/* Init */
	if (isize < MINLENGTH)
		goto _last_literals;

	/* First Byte */
	ip++;
	forwardH = LZ4_HASH64K_VALUE(ip);

	/* Main Loop */
	for (;;) {
		int findMatchAttempts = (1U << skipStrength) + 3;
		const BYTE *forwardIp = ip;
		const BYTE *ref;
		BYTE *token;

		/* Find a match */
		do {
			U32 h = forwardH;
			int step = findMatchAttempts++ >> skipStrength;
			ip = forwardIp;
			forwardIp = ip + step;

			if (forwardIp > mflimit) {
				goto _last_literals;
			}

			forwardH = LZ4_HASH64K_VALUE(forwardIp);
			ref = base + HashTable[h];
			HashTable[h] = ip - base;

		} while (A32(ref) != A32(ip));

		/* Catch up */
		while ((ip > anchor) && (ref > (BYTE *) source) &&
		    (ip[-1] == ref[-1])) {
			ip--;
			ref--;
		}

		/* Encode Literal length */
		length = ip - anchor;
		token = op++;

		/* Check output limit */
		if (unlikely(op + length + (2 + 1 + LASTLITERALS) +
		    (length >> 8) > oend))
			return (0);

		if (length >= (int)RUN_MASK) {
			*token = (RUN_MASK << ML_BITS);
			len = length - RUN_MASK;
			for (; len > 254; len -= 255)
				*op++ = 255;
			*op++ = (BYTE)len;
		} else
			*token = (length << ML_BITS);

		/* Copy Literals */
		LZ4_BLINDCOPY(anchor, op, length);

		_next_match:
		/* Encode Offset */
		LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);

		/* Start Counting */
		ip += MINMATCH;
		ref += MINMATCH;	/* MinMatch verified */
		anchor = ip;
		while (ip < matchlimit - (STEPSIZE - 1)) {
			UARCH diff = AARCH(ref) ^ AARCH(ip);
			if (!diff) {
				ip += STEPSIZE;
				ref += STEPSIZE;
				continue;
			}
			ip += LZ4_NbCommonBytes(diff);
			goto _endCount;
		}
#if LZ4_ARCH64
		if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
			ip += 4;
			ref += 4;
		}
#endif
		if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
			ip += 2;
			ref += 2;
		}
		if ((ip < matchlimit) && (*ref == *ip))
			ip++;
		_endCount:

		/* Encode MatchLength */
		len = (ip - anchor);
		/* Check output limit */
		if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend))
			return (0);
		if (len >= (int)ML_MASK) {
			*token += ML_MASK;
			len -= ML_MASK;
			for (; len > 509; len -= 510) {
				*op++ = 255;
				*op++ = 255;
			}
			if (len > 254) {
				len -= 255;
				*op++ = 255;
			}
			*op++ = (BYTE)len;
		} else
			*token += len;

		/* Test end of chunk */
		if (ip > mflimit) {
			anchor = ip;
			break;
		}
		/* Fill table */
		HashTable[LZ4_HASH64K_VALUE(ip - 2)] = ip - 2 - base;

		/* Test next position */
		ref = base + HashTable[LZ4_HASH64K_VALUE(ip)];
		HashTable[LZ4_HASH64K_VALUE(ip)] = ip - base;
		if (A32(ref) == A32(ip)) {
			token = op++;
			*token = 0;
			goto _next_match;
		}
		/* Prepare next loop */
		anchor = ip++;
		forwardH = LZ4_HASH64K_VALUE(ip);
	}

	_last_literals:
	/* Encode Last Literals */
	{
		int lastRun = iend - anchor;
		if (op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
		    oend)
			return (0);
		if (lastRun >= (int)RUN_MASK) {
			*op++ = (RUN_MASK << ML_BITS);
			lastRun -= RUN_MASK;
			for (; lastRun > 254; lastRun -= 255)
				*op++ = 255;
			*op++ = (BYTE)lastRun;
		} else
			*op++ = (lastRun << ML_BITS);
		(void) memcpy(op, anchor, iend - anchor);
		op += iend - anchor;
	}

	/* End */
	return (int)(((char *)op) - dest);
}

static int
real_LZ4_compress(const char *source, char *dest, int isize, int osize)
{
	void *ctx;
	int result;

	ASSERT(lz4_cache != NULL);
	ctx = kmem_cache_alloc(lz4_cache, KM_SLEEP);

	/*
	 * out of kernel memory, gently fall through - this will disable
	 * compression in zio_compress_data
	 */
	if (ctx == NULL)
		return (0);

	memset(ctx, 0, sizeof (struct refTables));

	if (isize < LZ4_64KLIMIT)
		result = LZ4_compress64kCtx(ctx, source, dest, isize, osize);
	else
		result = LZ4_compressCtx(ctx, source, dest, isize, osize);

	kmem_cache_free(lz4_cache, ctx);
	return (result);
}

/* Decompression functions */

/*
 * Note: The decoding functions real_LZ4_uncompress() and
 *	LZ4_uncompress_unknownOutputSize() are safe against "buffer overflow"
 *	attack type. They will never write nor read outside of the provided
 *	output buffers. LZ4_uncompress_unknownOutputSize() also insures that
 *	it will never read outside of the input buffer. A corrupted input
 *	will produce an error result, a negative int, indicating the position
 *	of the error within input stream.
 *
 * Note[2]: real_LZ4_uncompress(), referred to above, is not used in ZFS so
 *	its code is not present here.
 */

static int
LZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize,
    int maxOutputSize)
{
	/* Local Variables */
	const BYTE *restrict ip = (const BYTE *) source;
	const BYTE *const iend = ip + isize;
	const BYTE *ref;

	BYTE *op = (BYTE *) dest;
	BYTE *const oend = op + maxOutputSize;
	BYTE *cpy;

	size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
#if LZ4_ARCH64
	size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
#endif

	/* Main Loop */
	while (ip < iend) {
		unsigned token;
		size_t length;

		/* get runlength */
		token = *ip++;
		if ((length = (token >> ML_BITS)) == RUN_MASK) {
			int s = 255;
			while ((ip < iend) && (s == 255)) {
				s = *ip++;
				length += s;
			}
		}
		/* copy literals */
		cpy = op + length;
		/* CORNER-CASE: cpy might overflow. */
		if (cpy < op)
			goto _output_error;	/* cpy was overflowed, bail! */
		if ((cpy > oend - COPYLENGTH) ||
		    (ip + length > iend - COPYLENGTH)) {
			if (cpy > oend)
				/* Error: writes beyond output buffer */
				goto _output_error;
			if (ip + length != iend)
				/*
				 * Error: LZ4 format requires to consume all
				 * input at this stage
				 */
				goto _output_error;
			(void) memcpy(op, ip, length);
			op += length;
			/* Necessarily EOF, due to parsing restrictions */
			break;
		}
		LZ4_WILDCOPY(ip, op, cpy);
		ip -= (op - cpy);
		op = cpy;

		/* get offset */
		LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
		ip += 2;
		if (ref < (BYTE * const) dest)
			/*
			 * Error: offset creates reference outside of
			 * destination buffer
			 */
			goto _output_error;

		/* get matchlength */
		if ((length = (token & ML_MASK)) == ML_MASK) {
			while (ip < iend) {
				int s = *ip++;
				length += s;
				if (s == 255)
					continue;
				break;
			}
		}
		/* copy repeated sequence */
		if (unlikely(op - ref < STEPSIZE)) {
#if LZ4_ARCH64
			size_t dec64 = dec64table[op-ref];
#else
			const int dec64 = 0;
#endif
			op[0] = ref[0];
			op[1] = ref[1];
			op[2] = ref[2];
			op[3] = ref[3];
			op += 4;
			ref += 4;
			ref -= dec32table[op-ref];
			A32(op) = A32(ref);
			op += STEPSIZE - 4;
			ref -= dec64;
		} else {
			LZ4_COPYSTEP(ref, op);
		}
		cpy = op + length - (STEPSIZE - 4);
		if (cpy > oend - COPYLENGTH) {
			if (cpy > oend)
				/*
				 * Error: request to write outside of
				 * destination buffer
				 */
				goto _output_error;
			LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
			while (op < cpy)
				*op++ = *ref++;
			op = cpy;
			if (op == oend)
				/*
				 * Check EOF (should never happen, since
				 * last 5 bytes are supposed to be literals)
				 */
				goto _output_error;
			continue;
		}
		LZ4_SECURECOPY(ref, op, cpy);
		op = cpy;	/* correction */
	}

	/* end of decoding */
	return (int)(((char *)op) - dest);

	/* write overflow error detected */
	_output_error:
	return (int)(-(((char *)ip) - source));
}

void
lz4_init(void)
{
	lz4_cache = kmem_cache_create("lz4_cache",
	    sizeof (struct refTables), 0, NULL, NULL, NULL, NULL, NULL, 0);
}

void
lz4_fini(void)
{
	if (lz4_cache) {
		kmem_cache_destroy(lz4_cache);
		lz4_cache = NULL;
	}
}