Print this page
Integrated r91 LZ4.
@@ -28,17 +28,17 @@
* 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/
+ * Upstream release : r91
*/
#include <sys/zfs_context.h>
static int real_LZ4_compress(const char *source, char *dest, int isize,
int osize);
-static int real_LZ4_uncompress(const char *source, char *dest, int osize);
static int LZ4_compressBound(int isize);
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);
@@ -102,20 +102,10 @@
* 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
- *
* 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
@@ -135,11 +125,10 @@
* 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
@@ -530,11 +519,11 @@
const BYTE *const mflimit = iend - MFLIMIT;
#define matchlimit (iend - LASTLITERALS)
BYTE *op = (BYTE *) dest;
- int len, length;
+ int length;
const int skipStrength = SKIPSTRENGTH;
U32 forwardH;
/* Init */
@@ -585,10 +574,11 @@
if unlikely(op + length + (2 + 1 + LASTLITERALS) +
(length >> 8) > oend)
return (0);
if (length >= (int)RUN_MASK) {
+ int len;
*token = (RUN_MASK << ML_BITS);
len = length - RUN_MASK;
for (; len > 254; len -= 255)
*op++ = 255;
*op++ = (BYTE)len;
@@ -602,11 +592,11 @@
/* Encode Offset */
LZ4_WRITE_LITTLEENDIAN_16(op, ip - ref);
/* Start Counting */
ip += MINMATCH;
- ref += MINMATCH; /* MinMatch verified */
+ ref += MINMATCH; /* MinMatch already verified */
anchor = ip;
while likely(ip < matchlimit - (STEPSIZE - 1)) {
UARCH diff = AARCH(ref) ^ AARCH(ip);
if (!diff) {
ip += STEPSIZE;
@@ -629,28 +619,28 @@
if ((ip < matchlimit) && (*ref == *ip))
ip++;
_endCount:
/* Encode MatchLength */
- len = (ip - anchor);
+ length = (int)(ip - anchor);
/* Check output limit */
- if unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend)
+ if unlikely(op + (1 + LASTLITERALS) + (length >> 8) > oend)
return (0);
- if (len >= (int)ML_MASK) {
+ if (length >= (int)ML_MASK) {
*token += ML_MASK;
- len -= ML_MASK;
- for (; len > 509; len -= 510) {
+ length -= ML_MASK;
+ for (; length > 509; length -= 510) {
*op++ = 255;
*op++ = 255;
}
- if (len > 254) {
- len -= 255;
+ if (length > 254) {
+ length -= 255;
*op++ = 255;
}
- *op++ = (BYTE)len;
+ *op++ = (BYTE)length;
} else
- *token += len;
+ *token += length;
/* Test end of chunk */
if (ip > mflimit) {
anchor = ip;
break;
@@ -915,133 +905,11 @@
#endif
}
/* 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.
- */
-
static int
-real_LZ4_uncompress(const char *source, char *dest, int osize)
-{
- /* Local Variables */
- const BYTE *restrict ip = (const BYTE *) source;
- const BYTE *ref;
-
- BYTE *op = (BYTE *) dest;
- BYTE *const oend = op + osize;
- BYTE *cpy;
-
- unsigned token;
-
- size_t length;
- 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 */
- for (;;) {
- /* get runlength */
- token = *ip++;
- if ((length = (token >> ML_BITS)) == RUN_MASK) {
- size_t len;
- for (; (len = *ip++) == 255; length += 255) {
- }
- length += len;
- }
- /* copy literals */
- cpy = op + length;
- if unlikely(cpy > oend - COPYLENGTH) {
- if (cpy != oend)
- /* Error: we must necessarily stand at EOF */
- goto _output_error;
- (void) memcpy(op, ip, length);
- ip += length;
- break; /* EOF */
- }
- LZ4_WILDCOPY(ip, op, cpy);
- ip -= (op - cpy);
- op = cpy;
-
- /* get offset */
- LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
- ip += 2;
- if unlikely(ref < (BYTE * const) dest)
- /*
- * Error: offset create reference outside destination
- * buffer
- */
- goto _output_error;
-
- /* get matchlength */
- if ((length = (token & ML_MASK)) == ML_MASK) {
- for (; *ip == 255; length += 255) {
- ip++;
- }
- length += *ip++;
- }
- /* 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 beyond 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 *)ip) - source);
-
- /* write overflow error detected */
- _output_error:
- return (int)(-(((char *)ip) - source));
-}
-
-static int
LZ4_uncompress_unknownOutputSize(const char *source, char *dest, int isize,
int maxOutputSize)
{
/* Local Variables */
const BYTE *restrict ip = (const BYTE *) source;
@@ -1055,12 +923,21 @@
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
+ /*
+ * Special case
+ * A correctly formed null-compressed LZ4 must have at least
+ * one byte (token=0)
+ */
+ if (unlikely(ip == iend))
+ goto _output_error;
+
/* Main Loop */
- while (ip < iend) {
+ /*LINTED E_CONSTANT_CONDITION*/
+ while (1) {
unsigned token;
size_t length;
/* get runlength */
token = *ip++;
@@ -1071,19 +948,21 @@
length += s;
}
}
/* copy literals */
cpy = op + length;
- if ((cpy > oend - COPYLENGTH) ||
- (ip + length > iend - COPYLENGTH)) {
+ if ((cpy > oend - MFLIMIT) ||
+ (ip + length > iend - (2 + 1 + LASTLITERALS))) {
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
+ * input at this stage (no match within the
+ * last 11 bytes, and at least 8 remaining
+ * input bytes for another match + literals
*/
goto _output_error;
(void) memcpy(op, ip, length);
op += length;
/* Necessarily EOF, due to parsing restrictions */
@@ -1094,20 +973,20 @@
op = cpy;
/* get offset */
LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip);
ip += 2;
- if (ref < (BYTE * const) dest)
+ if (unlikely(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) {
+ while (likely(ip < iend - (LASTLITERALS + 1))) {
int s = *ip++;
length += s;
if (s == 255)
continue;
break;
@@ -1132,15 +1011,14 @@
ref -= dec64;
} else {
LZ4_COPYSTEP(ref, op);
}
cpy = op + length - (STEPSIZE - 4);
- if (cpy > oend - COPYLENGTH) {
- if (cpy > oend)
+ if (unlikely(cpy > oend - (COPYLENGTH + (STEPSIZE - 4)))) {
+ if (cpy > oend - LASTLITERALS)
/*
- * Error: request to write outside of
- * destination buffer
+ * Error: last 5 bytes must be literals
*/
goto _output_error;
LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH));
while (op < cpy)
*op++ = *ref++;
@@ -1151,11 +1029,11 @@
* last 5 bytes are supposed to be literals)
*/
goto _output_error;
continue;
}
- LZ4_SECURECOPY(ref, op, cpy);
+ LZ4_WILDCOPY(ref, op, cpy);
op = cpy; /* correction */
}
/* end of decoding */
return (int)(((char *)op) - dest);