a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * LZ4 - Fast LZ compression algorithm
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Header File
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Copyright (C) 2011-2013, Yann Collet.
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Redistribution and use in source and binary forms, with or without
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * modification, are permitted provided that the following conditions are
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * * Redistributions of source code must retain the above copyright
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * notice, this list of conditions and the following disclaimer.
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * * Redistributions in binary form must reproduce the above
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * copyright notice, this list of conditions and the following disclaimer
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * in the documentation and/or other materials provided with the
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * distribution.
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * You can contact the author at :
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * - LZ4 source repository : http://code.google.com/p/lz4/
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkovstatic int LZ4_uncompress_unknownOutputSize(const char *source, char *dest,
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkovlz4_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len)
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov uint32_t bufsiz = (src[0] << 24) | (src[1] << 16) | (src[2] << 8) |
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* invalid compressed buffer size encoded at start */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Returns 0 on success (decompression function returned non-negative)
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * and non-zero on failure (decompression function returned negative).
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov return (LZ4_uncompress_unknownOutputSize(s_start + 4, d_start, bufsiz,
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * CPU Feature Detection
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov/* 32 or 64 bits ? */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || \
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || \
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Little Endian or Big Endian?
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Note: overwrite the below #define if you know your architecture endianess.
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#if (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || \
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov defined(_BIG_ENDIAN) || defined(_ARCH_PPC) || defined(__PPC__) || \
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov defined(__PPC) || defined(PPC) || defined(__powerpc__) || \
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov ((defined(__BYTE_ORDER__)&&(__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))))
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Little Endian assumed. PDP Endian and other very rare endian format
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * are unsupported.
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Compiler Options
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov/* "restrict" is a known keyword */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov/* Disable restrict */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define restrict
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) \
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define expect(expr, value) (__builtin_expect((expr), (value)))
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov/* Basic types */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Architecture-specific macros
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define LZ4_COPYSTEP(s, d) A64(d) = A64(s); d += 8; s += 8;
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d)
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define LZ4_SECURECOPY(s, d, e) if (d < e) LZ4_WILDCOPY(s, d, e)
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define INITBASE(base) const BYTE* const base = ip
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define LZ4_COPYSTEP(s, d) A32(d) = A32(s); d += 4; s += 4;
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d);
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE))
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; }
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; }
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); }
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define LZ4_WRITE_LITTLEENDIAN_16(p, v) { A16(p) = v; p += 2; }
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov#define LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e);
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov/* Decompression functions */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo KiselkovLZ4_uncompress_unknownOutputSize(const char *source,
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* Local Variables */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov const BYTE *restrict ip = (const BYTE *) source;
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* Main Loop */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* get runlength */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov if ((length = (token >> ML_BITS)) == RUN_MASK) {
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* copy literals */
58d0718061c87e3d647c891ec5281b93c08dba4eDan McDonald /* CORNER-CASE: cpy might overflow. */
58d0718061c87e3d647c891ec5281b93c08dba4eDan McDonald goto _output_error; /* cpy was overflowed, bail! */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Error: request to write beyond destination
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Error : request to read beyond source
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* Error : LZ4 format violation */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* Necessarily EOF, due to parsing restrictions. */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* get offset */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Error: offset creates reference outside of
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * destination buffer.
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* get matchlength */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov if ((length = (token & ML_MASK)) == ML_MASK) {
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov if (s == 255)
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* copy repeated sequence */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov size_t dec2table[] = { 0, 0, 0, -1, 0, 1, 2, 3 };
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov const int dec2 = 0;
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Error: request to write outside of
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * destination buffer.
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * Check EOF (should never happen, since last
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov * 5 bytes are supposed to be literals).
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* end of decoding */
a6f561b4aee75d0d028e7b36b151c8ed8a86bc76Sašo Kiselkov /* write overflow error detected */