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 #include <sys/zfs_context.h>
36
37 static int real_LZ4_compress(const char *source, char *dest, int isize,
38 int osize);
39 static int real_LZ4_uncompress(const char *source, char *dest, int osize);
40 static int LZ4_compressBound(int isize);
41 static int LZ4_uncompress_unknownOutputSize(const char *source, char *dest,
42 int isize, int maxOutputSize);
43 static int LZ4_compressCtx(void *ctx, const char *source, char *dest,
44 int isize, int osize);
45 static int LZ4_compress64kCtx(void *ctx, const char *source, char *dest,
46 int isize, int osize);
47
48 /*ARGSUSED*/
49 size_t
50 lz4_compress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
51 {
52 uint32_t bufsiz;
53 char *dest = d_start;
54
55 ASSERT(d_len >= sizeof (bufsiz));
56
57 bufsiz = real_LZ4_compress(s_start, &dest[sizeof (bufsiz)], s_len,
58 d_len - sizeof (bufsiz));
59
87 * Returns 0 on success (decompression function returned non-negative)
88 * and non-zero on failure (decompression function returned negative.
89 */
90 return (LZ4_uncompress_unknownOutputSize(&src[sizeof (bufsiz)],
91 d_start, bufsiz, d_len) < 0);
92 }
93
94 /*
95 * LZ4 API Description:
96 *
97 * Simple Functions:
98 * real_LZ4_compress() :
99 * isize : is the input size. Max supported value is ~1.9GB
100 * return : the number of bytes written in buffer dest
101 * or 0 if the compression fails (if LZ4_COMPRESSMIN is set).
102 * note : destination buffer must be already allocated.
103 * destination buffer must be sized to handle worst cases
104 * situations (input data not compressible) worst case size
105 * evaluation is provided by function LZ4_compressBound().
106 *
107 * real_LZ4_uncompress() :
108 * osize : is the output size, therefore the original size
109 * return : the number of bytes read in the source buffer.
110 * If the source stream is malformed, the function will stop
111 * decoding and return a negative result, indicating the byte
112 * position of the faulty instruction. This function never
113 * writes beyond dest + osize, and is therefore protected
114 * against malicious data packets.
115 * note : destination buffer must be already allocated
116 *
117 * Advanced Functions
118 *
119 * LZ4_compressBound() :
120 * Provides the maximum size that LZ4 may output in a "worst case"
121 * scenario (input data not compressible) primarily useful for memory
122 * allocation of output buffer.
123 *
124 * isize : is the input size. Max supported value is ~1.9GB
125 * return : maximum output size in a "worst case" scenario
126 * note : this function is limited by "int" range (2^31-1)
127 *
128 * LZ4_uncompress_unknownOutputSize() :
129 * isize : is the input size, therefore the compressed size
130 * maxOutputSize : is the size of the destination buffer (which must be
131 * already allocated)
132 * return : the number of bytes decoded in the destination buffer
133 * (necessarily <= maxOutputSize). If the source stream is
134 * malformed, the function will stop decoding and return a
135 * negative result, indicating the byte position of the faulty
136 * instruction. This function never writes beyond dest +
137 * maxOutputSize, and is therefore protected against malicious
138 * data packets.
139 * note : Destination buffer must be already allocated.
140 * This version is slightly slower than real_LZ4_uncompress()
141 *
142 * LZ4_compressCtx() :
143 * This function explicitly handles the CTX memory structure.
144 *
145 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
146 * by the caller (either on the stack or using kmem_zalloc). Passing NULL
147 * isn't valid.
148 *
149 * LZ4_compress64kCtx() :
150 * Same as LZ4_compressCtx(), but specific to small inputs (<64KB).
151 * isize *Must* be <64KB, otherwise the output will be corrupted.
152 *
153 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
154 * by the caller (either on the stack or using kmem_zalloc). Passing NULL
155 * isn't valid.
156 */
157
158 /*
159 * Tuning parameters
160 */
515 LZ4_compressCtx(void *ctx, const char *source, char *dest, int isize,
516 int osize)
517 {
518 #if HEAPMODE
519 struct refTables *srt = (struct refTables *)ctx;
520 HTYPE *HashTable = (HTYPE *) (srt->hashTable);
521 #else
522 HTYPE HashTable[HASHTABLESIZE] = { 0 };
523 #endif
524
525 const BYTE *ip = (BYTE *) source;
526 INITBASE(base);
527 const BYTE *anchor = ip;
528 const BYTE *const iend = ip + isize;
529 const BYTE *const oend = (BYTE *) dest + osize;
530 const BYTE *const mflimit = iend - MFLIMIT;
531 #define matchlimit (iend - LASTLITERALS)
532
533 BYTE *op = (BYTE *) dest;
534
535 int len, length;
536 const int skipStrength = SKIPSTRENGTH;
537 U32 forwardH;
538
539
540 /* Init */
541 if (isize < MINLENGTH)
542 goto _last_literals;
543
544 /* First Byte */
545 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
546 ip++;
547 forwardH = LZ4_HASH_VALUE(ip);
548
549 /* Main Loop */
550 for (;;) {
551 int findMatchAttempts = (1U << skipStrength) + 3;
552 const BYTE *forwardIp = ip;
553 const BYTE *ref;
554 BYTE *token;
555
570
571 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
572
573 /* Catch up */
574 while ((ip > anchor) && (ref > (BYTE *) source) &&
575 unlikely(ip[-1] == ref[-1])) {
576 ip--;
577 ref--;
578 }
579
580 /* Encode Literal length */
581 length = ip - anchor;
582 token = op++;
583
584 /* Check output limit */
585 if unlikely(op + length + (2 + 1 + LASTLITERALS) +
586 (length >> 8) > oend)
587 return (0);
588
589 if (length >= (int)RUN_MASK) {
590 *token = (RUN_MASK << ML_BITS);
591 len = length - RUN_MASK;
592 for (; len > 254; len -= 255)
593 *op++ = 255;
594 *op++ = (BYTE)len;
595 } else
596 *token = (length << ML_BITS);
597
598 /* Copy Literals */
599 LZ4_BLINDCOPY(anchor, op, length);
600
601 _next_match:
602 /* Encode Offset */
603 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
604
605 /* Start Counting */
606 ip += MINMATCH;
607 ref += MINMATCH; /* MinMatch verified */
608 anchor = ip;
609 while likely(ip < matchlimit - (STEPSIZE - 1)) {
610 UARCH diff = AARCH(ref) ^ AARCH(ip);
611 if (!diff) {
612 ip += STEPSIZE;
613 ref += STEPSIZE;
614 continue;
615 }
616 ip += LZ4_NbCommonBytes(diff);
617 goto _endCount;
618 }
619 #if LZ4_ARCH64
620 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
621 ip += 4;
622 ref += 4;
623 }
624 #endif
625 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
626 ip += 2;
627 ref += 2;
628 }
629 if ((ip < matchlimit) && (*ref == *ip))
630 ip++;
631 _endCount:
632
633 /* Encode MatchLength */
634 len = (ip - anchor);
635 /* Check output limit */
636 if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
637 return (0);
638 if (len >= (int)ML_MASK) {
639 *token += ML_MASK;
640 len -= ML_MASK;
641 for (; len > 509; len -= 510) {
642 *op++ = 255;
643 *op++ = 255;
644 }
645 if (len > 254) {
646 len -= 255;
647 *op++ = 255;
648 }
649 *op++ = (BYTE)len;
650 } else
651 *token += len;
652
653 /* Test end of chunk */
654 if (ip > mflimit) {
655 anchor = ip;
656 break;
657 }
658 /* Fill table */
659 HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base;
660
661 /* Test next position */
662 ref = base + HashTable[LZ4_HASH_VALUE(ip)];
663 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
664 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
665 token = op++;
666 *token = 0;
667 goto _next_match;
668 }
669 /* Prepare next loop */
670 anchor = ip++;
671 forwardH = LZ4_HASH_VALUE(ip);
900 */
901 if (ctx == NULL)
902 return (0);
903
904 if (isize < LZ4_64KLIMIT)
905 result = LZ4_compress64kCtx(ctx, source, dest, isize, osize);
906 else
907 result = LZ4_compressCtx(ctx, source, dest, isize, osize);
908
909 kmem_free(ctx, sizeof (struct refTables));
910 return (result);
911 #else
912 if (isize < (int)LZ4_64KLIMIT)
913 return (LZ4_compress64kCtx(NULL, source, dest, isize, osize));
914 return (LZ4_compressCtx(NULL, source, dest, isize, osize));
915 #endif
916 }
917
918 /* Decompression functions */
919
920 /*
921 * Note: The decoding functions real_LZ4_uncompress() and
922 * LZ4_uncompress_unknownOutputSize() are safe against "buffer overflow"
923 * attack type. They will never write nor read outside of the provided
924 * output buffers. LZ4_uncompress_unknownOutputSize() also insures that
925 * it will never read outside of the input buffer. A corrupted input
926 * will produce an error result, a negative int, indicating the position
927 * of the error within input stream.
928 */
929
930 static int
931 real_LZ4_uncompress(const char *source, char *dest, int osize)
932 {
933 /* Local Variables */
934 const BYTE *restrict ip = (const BYTE *) source;
935 const BYTE *ref;
936
937 BYTE *op = (BYTE *) dest;
938 BYTE *const oend = op + osize;
939 BYTE *cpy;
940
941 unsigned token;
942
943 size_t length;
944 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
945 #if LZ4_ARCH64
946 size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
947 #endif
948
949 /* Main Loop */
950 for (;;) {
951 /* get runlength */
952 token = *ip++;
953 if ((length = (token >> ML_BITS)) == RUN_MASK) {
954 size_t len;
955 for (; (len = *ip++) == 255; length += 255) {
956 }
957 length += len;
958 }
959 /* copy literals */
960 cpy = op + length;
961 if unlikely(cpy > oend - COPYLENGTH) {
962 if (cpy != oend)
963 /* Error: we must necessarily stand at EOF */
964 goto _output_error;
965 (void) memcpy(op, ip, length);
966 ip += length;
967 break; /* EOF */
968 }
969 LZ4_WILDCOPY(ip, op, cpy);
970 ip -= (op - cpy);
971 op = cpy;
972
973 /* get offset */
974 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
975 ip += 2;
976 if unlikely(ref < (BYTE * const) dest)
977 /*
978 * Error: offset create reference outside destination
979 * buffer
980 */
981 goto _output_error;
982
983 /* get matchlength */
984 if ((length = (token & ML_MASK)) == ML_MASK) {
985 for (; *ip == 255; length += 255) {
986 ip++;
987 }
988 length += *ip++;
989 }
990 /* copy repeated sequence */
991 if unlikely(op - ref < STEPSIZE) {
992 #if LZ4_ARCH64
993 size_t dec64 = dec64table[op-ref];
994 #else
995 const int dec64 = 0;
996 #endif
997 op[0] = ref[0];
998 op[1] = ref[1];
999 op[2] = ref[2];
1000 op[3] = ref[3];
1001 op += 4;
1002 ref += 4;
1003 ref -= dec32table[op-ref];
1004 A32(op) = A32(ref);
1005 op += STEPSIZE - 4;
1006 ref -= dec64;
1007 } else {
1008 LZ4_COPYSTEP(ref, op);
1009 }
1010 cpy = op + length - (STEPSIZE - 4);
1011 if (cpy > oend - COPYLENGTH) {
1012 if (cpy > oend)
1013 /*
1014 * Error: request to write beyond destination
1015 * buffer
1016 */
1017 goto _output_error;
1018 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
1019 while (op < cpy)
1020 *op++ = *ref++;
1021 op = cpy;
1022 if (op == oend)
1023 /*
1024 * Check EOF (should never happen, since last
1025 * 5 bytes are supposed to be literals)
1026 */
1027 goto _output_error;
1028 continue;
1029 }
1030 LZ4_SECURECOPY(ref, op, cpy);
1031 op = cpy; /* correction */
1032 }
1033
1034 /* end of decoding */
1035 return (int)(((char *)ip) - source);
1036
1037 /* write overflow error detected */
1038 _output_error:
1039 return (int)(-(((char *)ip) - source));
1040 }
1041
1042 static int
1043 LZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize,
1044 int maxOutputSize)
1045 {
1046 /* Local Variables */
1047 const BYTE *restrict ip = (const BYTE *) source;
1048 const BYTE *const iend = ip + isize;
1049 const BYTE *ref;
1050
1051 BYTE *op = (BYTE *) dest;
1052 BYTE *const oend = op + maxOutputSize;
1053 BYTE *cpy;
1054
1055 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
1056 #if LZ4_ARCH64
1057 size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
1058 #endif
1059
1060 /* Main Loop */
1061 while (ip < iend) {
1062 unsigned token;
1063 size_t length;
1064
1065 /* get runlength */
1066 token = *ip++;
1067 if ((length = (token >> ML_BITS)) == RUN_MASK) {
1068 int s = 255;
1069 while ((ip < iend) && (s == 255)) {
1070 s = *ip++;
1071 length += s;
1072 }
1073 }
1074 /* copy literals */
1075 cpy = op + length;
1076 if ((cpy > oend - COPYLENGTH) ||
1077 (ip + length > iend - COPYLENGTH)) {
1078 if (cpy > oend)
1079 /* Error: writes beyond output buffer */
1080 goto _output_error;
1081 if (ip + length != iend)
1082 /*
1083 * Error: LZ4 format requires to consume all
1084 * input at this stage
1085 */
1086 goto _output_error;
1087 (void) memcpy(op, ip, length);
1088 op += length;
1089 /* Necessarily EOF, due to parsing restrictions */
1090 break;
1091 }
1092 LZ4_WILDCOPY(ip, op, cpy);
1093 ip -= (op - cpy);
1094 op = cpy;
1095
1096 /* get offset */
1097 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
1098 ip += 2;
1099 if (ref < (BYTE * const) dest)
1100 /*
1101 * Error: offset creates reference outside of
1102 * destination buffer
1103 */
1104 goto _output_error;
1105
1106 /* get matchlength */
1107 if ((length = (token & ML_MASK)) == ML_MASK) {
1108 while (ip < iend) {
1109 int s = *ip++;
1110 length += s;
1111 if (s == 255)
1112 continue;
1113 break;
1114 }
1115 }
1116 /* copy repeated sequence */
1117 if unlikely(op - ref < STEPSIZE) {
1118 #if LZ4_ARCH64
1119 size_t dec64 = dec64table[op-ref];
1120 #else
1121 const int dec64 = 0;
1122 #endif
1123 op[0] = ref[0];
1124 op[1] = ref[1];
1125 op[2] = ref[2];
1126 op[3] = ref[3];
1127 op += 4;
1128 ref += 4;
1129 ref -= dec32table[op-ref];
1130 A32(op) = A32(ref);
1131 op += STEPSIZE - 4;
1132 ref -= dec64;
1133 } else {
1134 LZ4_COPYSTEP(ref, op);
1135 }
1136 cpy = op + length - (STEPSIZE - 4);
1137 if (cpy > oend - COPYLENGTH) {
1138 if (cpy > oend)
1139 /*
1140 * Error: request to write outside of
1141 * destination buffer
1142 */
1143 goto _output_error;
1144 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
1145 while (op < cpy)
1146 *op++ = *ref++;
1147 op = cpy;
1148 if (op == oend)
1149 /*
1150 * Check EOF (should never happen, since
1151 * last 5 bytes are supposed to be literals)
1152 */
1153 goto _output_error;
1154 continue;
1155 }
1156 LZ4_SECURECOPY(ref, op, cpy);
1157 op = cpy; /* correction */
1158 }
1159
1160 /* end of decoding */
1161 return (int)(((char *)op) - dest);
1162
1163 /* write overflow error detected */
1164 _output_error:
1165 return (int)(-(((char *)ip) - source));
1166 }
|
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 * Upstream release : r91
34 */
35
36 #include <sys/zfs_context.h>
37
38 static int real_LZ4_compress(const char *source, char *dest, int isize,
39 int osize);
40 static int LZ4_compressBound(int isize);
41 static int LZ4_uncompress_unknownOutputSize(const char *source, char *dest,
42 int isize, int maxOutputSize);
43 static int LZ4_compressCtx(void *ctx, const char *source, char *dest,
44 int isize, int osize);
45 static int LZ4_compress64kCtx(void *ctx, const char *source, char *dest,
46 int isize, int osize);
47
48 /*ARGSUSED*/
49 size_t
50 lz4_compress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n)
51 {
52 uint32_t bufsiz;
53 char *dest = d_start;
54
55 ASSERT(d_len >= sizeof (bufsiz));
56
57 bufsiz = real_LZ4_compress(s_start, &dest[sizeof (bufsiz)], s_len,
58 d_len - sizeof (bufsiz));
59
87 * Returns 0 on success (decompression function returned non-negative)
88 * and non-zero on failure (decompression function returned negative.
89 */
90 return (LZ4_uncompress_unknownOutputSize(&src[sizeof (bufsiz)],
91 d_start, bufsiz, d_len) < 0);
92 }
93
94 /*
95 * LZ4 API Description:
96 *
97 * Simple Functions:
98 * real_LZ4_compress() :
99 * isize : is the input size. Max supported value is ~1.9GB
100 * return : the number of bytes written in buffer dest
101 * or 0 if the compression fails (if LZ4_COMPRESSMIN is set).
102 * note : destination buffer must be already allocated.
103 * destination buffer must be sized to handle worst cases
104 * situations (input data not compressible) worst case size
105 * evaluation is provided by function LZ4_compressBound().
106 *
107 * Advanced Functions
108 *
109 * LZ4_compressBound() :
110 * Provides the maximum size that LZ4 may output in a "worst case"
111 * scenario (input data not compressible) primarily useful for memory
112 * allocation of output buffer.
113 *
114 * isize : is the input size. Max supported value is ~1.9GB
115 * return : maximum output size in a "worst case" scenario
116 * note : this function is limited by "int" range (2^31-1)
117 *
118 * LZ4_uncompress_unknownOutputSize() :
119 * isize : is the input size, therefore the compressed size
120 * maxOutputSize : is the size of the destination buffer (which must be
121 * already allocated)
122 * return : the number of bytes decoded in the destination buffer
123 * (necessarily <= maxOutputSize). If the source stream is
124 * malformed, the function will stop decoding and return a
125 * negative result, indicating the byte position of the faulty
126 * instruction. This function never writes beyond dest +
127 * maxOutputSize, and is therefore protected against malicious
128 * data packets.
129 * note : Destination buffer must be already allocated.
130 *
131 * LZ4_compressCtx() :
132 * This function explicitly handles the CTX memory structure.
133 *
134 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
135 * by the caller (either on the stack or using kmem_zalloc). Passing NULL
136 * isn't valid.
137 *
138 * LZ4_compress64kCtx() :
139 * Same as LZ4_compressCtx(), but specific to small inputs (<64KB).
140 * isize *Must* be <64KB, otherwise the output will be corrupted.
141 *
142 * ILLUMOS CHANGES: the CTX memory structure must be explicitly allocated
143 * by the caller (either on the stack or using kmem_zalloc). Passing NULL
144 * isn't valid.
145 */
146
147 /*
148 * Tuning parameters
149 */
504 LZ4_compressCtx(void *ctx, const char *source, char *dest, int isize,
505 int osize)
506 {
507 #if HEAPMODE
508 struct refTables *srt = (struct refTables *)ctx;
509 HTYPE *HashTable = (HTYPE *) (srt->hashTable);
510 #else
511 HTYPE HashTable[HASHTABLESIZE] = { 0 };
512 #endif
513
514 const BYTE *ip = (BYTE *) source;
515 INITBASE(base);
516 const BYTE *anchor = ip;
517 const BYTE *const iend = ip + isize;
518 const BYTE *const oend = (BYTE *) dest + osize;
519 const BYTE *const mflimit = iend - MFLIMIT;
520 #define matchlimit (iend - LASTLITERALS)
521
522 BYTE *op = (BYTE *) dest;
523
524 int length;
525 const int skipStrength = SKIPSTRENGTH;
526 U32 forwardH;
527
528
529 /* Init */
530 if (isize < MINLENGTH)
531 goto _last_literals;
532
533 /* First Byte */
534 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
535 ip++;
536 forwardH = LZ4_HASH_VALUE(ip);
537
538 /* Main Loop */
539 for (;;) {
540 int findMatchAttempts = (1U << skipStrength) + 3;
541 const BYTE *forwardIp = ip;
542 const BYTE *ref;
543 BYTE *token;
544
559
560 } while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));
561
562 /* Catch up */
563 while ((ip > anchor) && (ref > (BYTE *) source) &&
564 unlikely(ip[-1] == ref[-1])) {
565 ip--;
566 ref--;
567 }
568
569 /* Encode Literal length */
570 length = ip - anchor;
571 token = op++;
572
573 /* Check output limit */
574 if unlikely(op + length + (2 + 1 + LASTLITERALS) +
575 (length >> 8) > oend)
576 return (0);
577
578 if (length >= (int)RUN_MASK) {
579 int len;
580 *token = (RUN_MASK << ML_BITS);
581 len = length - RUN_MASK;
582 for (; len > 254; len -= 255)
583 *op++ = 255;
584 *op++ = (BYTE)len;
585 } else
586 *token = (length << ML_BITS);
587
588 /* Copy Literals */
589 LZ4_BLINDCOPY(anchor, op, length);
590
591 _next_match:
592 /* Encode Offset */
593 LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
594
595 /* Start Counting */
596 ip += MINMATCH;
597 ref += MINMATCH; /* MinMatch already verified */
598 anchor = ip;
599 while likely(ip < matchlimit - (STEPSIZE - 1)) {
600 UARCH diff = AARCH(ref) ^ AARCH(ip);
601 if (!diff) {
602 ip += STEPSIZE;
603 ref += STEPSIZE;
604 continue;
605 }
606 ip += LZ4_NbCommonBytes(diff);
607 goto _endCount;
608 }
609 #if LZ4_ARCH64
610 if ((ip < (matchlimit - 3)) && (A32(ref) == A32(ip))) {
611 ip += 4;
612 ref += 4;
613 }
614 #endif
615 if ((ip < (matchlimit - 1)) && (A16(ref) == A16(ip))) {
616 ip += 2;
617 ref += 2;
618 }
619 if ((ip < matchlimit) && (*ref == *ip))
620 ip++;
621 _endCount:
622
623 /* Encode MatchLength */
624 length = (int)(ip - anchor);
625 /* Check output limit */
626 if unlikely(op + (1 + LASTLITERALS) + (length >> 8) > oend)
627 return (0);
628 if (length >= (int)ML_MASK) {
629 *token += ML_MASK;
630 length -= ML_MASK;
631 for (; length > 509; length -= 510) {
632 *op++ = 255;
633 *op++ = 255;
634 }
635 if (length > 254) {
636 length -= 255;
637 *op++ = 255;
638 }
639 *op++ = (BYTE)length;
640 } else
641 *token += length;
642
643 /* Test end of chunk */
644 if (ip > mflimit) {
645 anchor = ip;
646 break;
647 }
648 /* Fill table */
649 HashTable[LZ4_HASH_VALUE(ip - 2)] = ip - 2 - base;
650
651 /* Test next position */
652 ref = base + HashTable[LZ4_HASH_VALUE(ip)];
653 HashTable[LZ4_HASH_VALUE(ip)] = ip - base;
654 if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
655 token = op++;
656 *token = 0;
657 goto _next_match;
658 }
659 /* Prepare next loop */
660 anchor = ip++;
661 forwardH = LZ4_HASH_VALUE(ip);
890 */
891 if (ctx == NULL)
892 return (0);
893
894 if (isize < LZ4_64KLIMIT)
895 result = LZ4_compress64kCtx(ctx, source, dest, isize, osize);
896 else
897 result = LZ4_compressCtx(ctx, source, dest, isize, osize);
898
899 kmem_free(ctx, sizeof (struct refTables));
900 return (result);
901 #else
902 if (isize < (int)LZ4_64KLIMIT)
903 return (LZ4_compress64kCtx(NULL, source, dest, isize, osize));
904 return (LZ4_compressCtx(NULL, source, dest, isize, osize));
905 #endif
906 }
907
908 /* Decompression functions */
909
910 static int
911 LZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize,
912 int maxOutputSize)
913 {
914 /* Local Variables */
915 const BYTE *restrict ip = (const BYTE *) source;
916 const BYTE *const iend = ip + isize;
917 const BYTE *ref;
918
919 BYTE *op = (BYTE *) dest;
920 BYTE *const oend = op + maxOutputSize;
921 BYTE *cpy;
922
923 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0};
924 #if LZ4_ARCH64
925 size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3};
926 #endif
927
928 /*
929 * Special case
930 * A correctly formed null-compressed LZ4 must have at least
931 * one byte (token=0)
932 */
933 if (unlikely(ip == iend))
934 goto _output_error;
935
936 /* Main Loop */
937 /*LINTED E_CONSTANT_CONDITION*/
938 while (1) {
939 unsigned token;
940 size_t length;
941
942 /* get runlength */
943 token = *ip++;
944 if ((length = (token >> ML_BITS)) == RUN_MASK) {
945 int s = 255;
946 while ((ip < iend) && (s == 255)) {
947 s = *ip++;
948 length += s;
949 }
950 }
951 /* copy literals */
952 cpy = op + length;
953 if ((cpy > oend - MFLIMIT) ||
954 (ip + length > iend - (2 + 1 + LASTLITERALS))) {
955 if (cpy > oend)
956 /* Error: writes beyond output buffer */
957 goto _output_error;
958 if (ip + length != iend)
959 /*
960 * Error: LZ4 format requires to consume all
961 * input at this stage (no match within the
962 * last 11 bytes, and at least 8 remaining
963 * input bytes for another match + literals
964 */
965 goto _output_error;
966 (void) memcpy(op, ip, length);
967 op += length;
968 /* Necessarily EOF, due to parsing restrictions */
969 break;
970 }
971 LZ4_WILDCOPY(ip, op, cpy);
972 ip -= (op - cpy);
973 op = cpy;
974
975 /* get offset */
976 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
977 ip += 2;
978 if (unlikely(ref < (BYTE * const) dest))
979 /*
980 * Error: offset creates reference outside of
981 * destination buffer
982 */
983 goto _output_error;
984
985 /* get matchlength */
986 if ((length = (token & ML_MASK)) == ML_MASK) {
987 while (likely(ip < iend - (LASTLITERALS + 1))) {
988 int s = *ip++;
989 length += s;
990 if (s == 255)
991 continue;
992 break;
993 }
994 }
995 /* copy repeated sequence */
996 if unlikely(op - ref < STEPSIZE) {
997 #if LZ4_ARCH64
998 size_t dec64 = dec64table[op-ref];
999 #else
1000 const int dec64 = 0;
1001 #endif
1002 op[0] = ref[0];
1003 op[1] = ref[1];
1004 op[2] = ref[2];
1005 op[3] = ref[3];
1006 op += 4;
1007 ref += 4;
1008 ref -= dec32table[op-ref];
1009 A32(op) = A32(ref);
1010 op += STEPSIZE - 4;
1011 ref -= dec64;
1012 } else {
1013 LZ4_COPYSTEP(ref, op);
1014 }
1015 cpy = op + length - (STEPSIZE - 4);
1016 if (unlikely(cpy > oend - (COPYLENGTH + (STEPSIZE - 4)))) {
1017 if (cpy > oend - LASTLITERALS)
1018 /*
1019 * Error: last 5 bytes must be literals
1020 */
1021 goto _output_error;
1022 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
1023 while (op < cpy)
1024 *op++ = *ref++;
1025 op = cpy;
1026 if (op == oend)
1027 /*
1028 * Check EOF (should never happen, since
1029 * last 5 bytes are supposed to be literals)
1030 */
1031 goto _output_error;
1032 continue;
1033 }
1034 LZ4_WILDCOPY(ref, op, cpy);
1035 op = cpy; /* correction */
1036 }
1037
1038 /* end of decoding */
1039 return (int)(((char *)op) - dest);
1040
1041 /* write overflow error detected */
1042 _output_error:
1043 return (int)(-(((char *)ip) - source));
1044 }
|