1246586Sdelphij/* 2246586Sdelphij * LZ4 - Fast LZ compression algorithm 3246586Sdelphij * Header File 4246586Sdelphij * Copyright (C) 2011-2013, Yann Collet. 5246586Sdelphij * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 6246586Sdelphij * 7246586Sdelphij * Redistribution and use in source and binary forms, with or without 8246586Sdelphij * modification, are permitted provided that the following conditions are 9246586Sdelphij * met: 10246586Sdelphij * 11246586Sdelphij * * Redistributions of source code must retain the above copyright 12246586Sdelphij * notice, this list of conditions and the following disclaimer. 13246586Sdelphij * * Redistributions in binary form must reproduce the above 14246586Sdelphij * copyright notice, this list of conditions and the following disclaimer 15246586Sdelphij * in the documentation and/or other materials provided with the 16246586Sdelphij * distribution. 17246586Sdelphij * 18246586Sdelphij * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19246586Sdelphij * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20246586Sdelphij * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21246586Sdelphij * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22246586Sdelphij * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23246586Sdelphij * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24246586Sdelphij * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25246586Sdelphij * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26246586Sdelphij * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27246586Sdelphij * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28246586Sdelphij * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29246586Sdelphij * 30246586Sdelphij * You can contact the author at : 31246586Sdelphij * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html 32246586Sdelphij * - LZ4 source repository : http://code.google.com/p/lz4/ 33246586Sdelphij * 34246586Sdelphij * $FreeBSD$ 35246586Sdelphij */ 36246586Sdelphij 37246586Sdelphijstatic int LZ4_uncompress_unknownOutputSize(const char *source, char *dest, 38246586Sdelphij int isize, int maxOutputSize); 39246586Sdelphij 40246586Sdelphij/* ARGSUSED */ 41246586Sdelphijstatic int 42246586Sdelphijlz4_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len, int dummy __unused) 43246586Sdelphij{ 44246586Sdelphij const uint8_t *src = s_start; 45246586Sdelphij uint32_t bufsiz = htonl(*(uint32_t *)src); 46246586Sdelphij 47246586Sdelphij /* invalid compressed buffer size encoded at start */ 48246586Sdelphij if (bufsiz + 4 > s_len) 49246586Sdelphij return (1); 50246586Sdelphij 51246586Sdelphij /* 52246586Sdelphij * Returns 0 on success (decompression function returned non-negative) 53246586Sdelphij * and non-zero on failure (decompression function returned negative). 54246586Sdelphij */ 55246586Sdelphij return (LZ4_uncompress_unknownOutputSize(s_start + 4, d_start, bufsiz, 56246586Sdelphij d_len) < 0); 57246586Sdelphij} 58246586Sdelphij 59246586Sdelphij/* 60246586Sdelphij * CPU Feature Detection 61246586Sdelphij */ 62246586Sdelphij 63246586Sdelphij/* 32 or 64 bits ? */ 64246586Sdelphij#if (defined(__x86_64__) || defined(__x86_64) || defined(__amd64__) || \ 65246586Sdelphij defined(__amd64) || defined(__ppc64__) || defined(_WIN64) || \ 66246586Sdelphij defined(__LP64__) || defined(_LP64)) 67246586Sdelphij#define LZ4_ARCH64 1 68246586Sdelphij#else 69246586Sdelphij#define LZ4_ARCH64 0 70246586Sdelphij#endif 71246586Sdelphij 72246586Sdelphij/* 73246586Sdelphij * Little Endian or Big Endian? 74246586Sdelphij * Note: overwrite the below #define if you know your architecture endianess. 75246586Sdelphij */ 76246586Sdelphij#if BYTE_ORDER == BIG_ENDIAN 77246586Sdelphij#define LZ4_BIG_ENDIAN 1 78246586Sdelphij#else 79246586Sdelphij /* 80246586Sdelphij * Little Endian assumed. PDP Endian and other very rare endian format 81246586Sdelphij * are unsupported. 82246586Sdelphij */ 83246586Sdelphij#endif 84246586Sdelphij 85246586Sdelphij/* 86246586Sdelphij * Compiler Options 87246586Sdelphij */ 88246586Sdelphij#if __STDC_VERSION__ >= 199901L /* C99 */ 89246586Sdelphij/* "restrict" is a known keyword */ 90246586Sdelphij#else 91246586Sdelphij/* Disable restrict */ 92246586Sdelphij#define restrict 93246586Sdelphij#endif 94246586Sdelphij 95246586Sdelphij#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 96246586Sdelphij 97246586Sdelphij#define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) \ 98246586Sdelphij | (((x) & 0xffu) << 8))) 99246586Sdelphij 100246586Sdelphij#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__) 101246586Sdelphij#define expect(expr, value) (__builtin_expect((expr), (value))) 102246586Sdelphij#else 103246586Sdelphij#define expect(expr, value) (expr) 104246586Sdelphij#endif 105246586Sdelphij 106246586Sdelphij#define likely(expr) expect((expr) != 0, 1) 107246586Sdelphij#define unlikely(expr) expect((expr) != 0, 0) 108246586Sdelphij 109246586Sdelphij/* Basic types */ 110246586Sdelphij#define BYTE uint8_t 111246586Sdelphij#define U16 uint16_t 112246586Sdelphij#define U32 uint32_t 113246586Sdelphij#define S32 int32_t 114246586Sdelphij#define U64 uint64_t 115246586Sdelphij 116246586Sdelphijtypedef struct _U16_S { 117246586Sdelphij U16 v; 118246586Sdelphij} U16_S; 119246586Sdelphijtypedef struct _U32_S { 120246586Sdelphij U32 v; 121246586Sdelphij} U32_S; 122246586Sdelphijtypedef struct _U64_S { 123246586Sdelphij U64 v; 124246586Sdelphij} U64_S; 125246586Sdelphij 126246586Sdelphij#define A64(x) (((U64_S *)(x))->v) 127246586Sdelphij#define A32(x) (((U32_S *)(x))->v) 128246586Sdelphij#define A16(x) (((U16_S *)(x))->v) 129246586Sdelphij 130246586Sdelphij/* 131246586Sdelphij * Constants 132246586Sdelphij */ 133246586Sdelphij#define MINMATCH 4 134246586Sdelphij 135246586Sdelphij#define COPYLENGTH 8 136246586Sdelphij#define LASTLITERALS 5 137246586Sdelphij 138246586Sdelphij#define ML_BITS 4 139246586Sdelphij#define ML_MASK ((1U<<ML_BITS)-1) 140246586Sdelphij#define RUN_BITS (8-ML_BITS) 141246586Sdelphij#define RUN_MASK ((1U<<RUN_BITS)-1) 142246586Sdelphij 143246586Sdelphij/* 144246586Sdelphij * Architecture-specific macros 145246586Sdelphij */ 146246586Sdelphij#if LZ4_ARCH64 147246586Sdelphij#define STEPSIZE 8 148246586Sdelphij#define UARCH U64 149246586Sdelphij#define AARCH A64 150246586Sdelphij#define LZ4_COPYSTEP(s, d) A64(d) = A64(s); d += 8; s += 8; 151246586Sdelphij#define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d) 152246586Sdelphij#define LZ4_SECURECOPY(s, d, e) if (d < e) LZ4_WILDCOPY(s, d, e) 153246586Sdelphij#define HTYPE U32 154246586Sdelphij#define INITBASE(base) const BYTE* const base = ip 155246586Sdelphij#else 156246586Sdelphij#define STEPSIZE 4 157246586Sdelphij#define UARCH U32 158246586Sdelphij#define AARCH A32 159246586Sdelphij#define LZ4_COPYSTEP(s, d) A32(d) = A32(s); d += 4; s += 4; 160246586Sdelphij#define LZ4_COPYPACKET(s, d) LZ4_COPYSTEP(s, d); LZ4_COPYSTEP(s, d); 161246586Sdelphij#define LZ4_SECURECOPY LZ4_WILDCOPY 162246586Sdelphij#define HTYPE const BYTE* 163246586Sdelphij#define INITBASE(base) const int base = 0 164246586Sdelphij#endif 165246586Sdelphij 166246586Sdelphij#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE)) 167246586Sdelphij#define LZ4_READ_LITTLEENDIAN_16(d, s, p) \ 168246586Sdelphij { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; } 169246586Sdelphij#define LZ4_WRITE_LITTLEENDIAN_16(p, i) \ 170246586Sdelphij { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p += 2; } 171246586Sdelphij#else 172246586Sdelphij#define LZ4_READ_LITTLEENDIAN_16(d, s, p) { d = (s) - A16(p); } 173246586Sdelphij#define LZ4_WRITE_LITTLEENDIAN_16(p, v) { A16(p) = v; p += 2; } 174246586Sdelphij#endif 175246586Sdelphij 176246586Sdelphij/* Macros */ 177246586Sdelphij#define LZ4_WILDCOPY(s, d, e) do { LZ4_COPYPACKET(s, d) } while (d < e); 178246586Sdelphij 179246586Sdelphij/* Decompression functions */ 180246586Sdelphij 181246586Sdelphijstatic int 182246586SdelphijLZ4_uncompress_unknownOutputSize(const char *source, 183246586Sdelphij char *dest, int isize, int maxOutputSize) 184246586Sdelphij{ 185246586Sdelphij /* Local Variables */ 186246586Sdelphij const BYTE *restrict ip = (const BYTE *) source; 187246586Sdelphij const BYTE *const iend = ip + isize; 188246586Sdelphij const BYTE *restrict ref; 189246586Sdelphij 190246586Sdelphij BYTE *restrict op = (BYTE *) dest; 191246586Sdelphij BYTE *const oend = op + maxOutputSize; 192246586Sdelphij BYTE *cpy; 193246586Sdelphij 194246586Sdelphij size_t dec[] = { 0, 3, 2, 3, 0, 0, 0, 0 }; 195246586Sdelphij 196246586Sdelphij /* Main Loop */ 197246586Sdelphij while (ip < iend) { 198246586Sdelphij BYTE token; 199246586Sdelphij int length; 200246586Sdelphij 201246586Sdelphij /* get runlength */ 202246586Sdelphij token = *ip++; 203246586Sdelphij if ((length = (token >> ML_BITS)) == RUN_MASK) { 204246586Sdelphij int s = 255; 205246586Sdelphij while ((ip < iend) && (s == 255)) { 206246586Sdelphij s = *ip++; 207246586Sdelphij length += s; 208246586Sdelphij } 209246586Sdelphij } 210246586Sdelphij /* copy literals */ 211246586Sdelphij cpy = op + length; 212246586Sdelphij if ((cpy > oend - COPYLENGTH) || 213246586Sdelphij (ip + length > iend - COPYLENGTH)) { 214246586Sdelphij if (cpy > oend) 215246586Sdelphij /* 216246586Sdelphij * Error: request to write beyond destination 217246586Sdelphij * buffer. 218246586Sdelphij */ 219246586Sdelphij goto _output_error; 220246586Sdelphij if (ip + length > iend) 221246586Sdelphij /* 222246586Sdelphij * Error : request to read beyond source 223246586Sdelphij * buffer. 224246586Sdelphij */ 225246586Sdelphij goto _output_error; 226246586Sdelphij memcpy(op, ip, length); 227246586Sdelphij op += length; 228246586Sdelphij ip += length; 229246586Sdelphij if (ip < iend) 230246586Sdelphij /* Error : LZ4 format violation */ 231246586Sdelphij goto _output_error; 232246586Sdelphij /* Necessarily EOF, due to parsing restrictions. */ 233246586Sdelphij break; 234246586Sdelphij } 235246586Sdelphij LZ4_WILDCOPY(ip, op, cpy); 236246586Sdelphij ip -= (op - cpy); 237246586Sdelphij op = cpy; 238246586Sdelphij 239246586Sdelphij /* get offset */ 240246586Sdelphij LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); 241246586Sdelphij ip += 2; 242246586Sdelphij if (ref < (BYTE * const) dest) 243246586Sdelphij /* 244246586Sdelphij * Error: offset creates reference outside of 245246586Sdelphij * destination buffer. 246246586Sdelphij */ 247246586Sdelphij goto _output_error; 248246586Sdelphij 249246586Sdelphij /* get matchlength */ 250246586Sdelphij if ((length = (token & ML_MASK)) == ML_MASK) { 251246586Sdelphij while (ip < iend) { 252246586Sdelphij int s = *ip++; 253246586Sdelphij length += s; 254246586Sdelphij if (s == 255) 255246586Sdelphij continue; 256246586Sdelphij break; 257246586Sdelphij } 258246586Sdelphij } 259246586Sdelphij /* copy repeated sequence */ 260246586Sdelphij if unlikely(op - ref < STEPSIZE) { 261246586Sdelphij#if LZ4_ARCH64 262246586Sdelphij size_t dec2table[] = { 0, 0, 0, -1, 0, 1, 2, 3 }; 263246586Sdelphij size_t dec2 = dec2table[op - ref]; 264246586Sdelphij#else 265246586Sdelphij const int dec2 = 0; 266246586Sdelphij#endif 267246586Sdelphij *op++ = *ref++; 268246586Sdelphij *op++ = *ref++; 269246586Sdelphij *op++ = *ref++; 270246586Sdelphij *op++ = *ref++; 271246586Sdelphij ref -= dec[op - ref]; 272246586Sdelphij A32(op) = A32(ref); 273246586Sdelphij op += STEPSIZE - 4; 274246586Sdelphij ref -= dec2; 275246586Sdelphij } else { 276246586Sdelphij LZ4_COPYSTEP(ref, op); 277246586Sdelphij } 278246586Sdelphij cpy = op + length - (STEPSIZE - 4); 279246586Sdelphij if (cpy > oend - COPYLENGTH) { 280246586Sdelphij if (cpy > oend) 281246586Sdelphij /* 282246586Sdelphij * Error: request to write outside of 283246586Sdelphij * destination buffer. 284246586Sdelphij */ 285246586Sdelphij goto _output_error; 286246586Sdelphij LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); 287246586Sdelphij while (op < cpy) 288246586Sdelphij *op++ = *ref++; 289246586Sdelphij op = cpy; 290246586Sdelphij if (op == oend) 291246586Sdelphij /* 292246586Sdelphij * Check EOF (should never happen, since last 293246586Sdelphij * 5 bytes are supposed to be literals). 294246586Sdelphij */ 295246586Sdelphij break; 296246586Sdelphij continue; 297246586Sdelphij } 298246586Sdelphij LZ4_SECURECOPY(ref, op, cpy); 299246586Sdelphij op = cpy; /* correction */ 300246586Sdelphij } 301246586Sdelphij 302246586Sdelphij /* end of decoding */ 303246586Sdelphij return (int)(((char *)op) - dest); 304246586Sdelphij 305246586Sdelphij /* write overflow error detected */ 306246586Sdelphij _output_error: 307246586Sdelphij return (int)(-(((char *)ip) - source)); 308246586Sdelphij} 309