1 /* 2 * LZ4 Decompressor for Linux kernel 3 * 4 * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com> 5 * 6 * Based on LZ4 implementation by Yann Collet. 7 * 8 * LZ4 - Fast LZ compression algorithm 9 * Copyright (C) 2011-2012, Yann Collet. 10 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions are 14 * met: 15 * 16 * * Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * * Redistributions in binary form must reproduce the above 19 * copyright notice, this list of conditions and the following disclaimer 20 * in the documentation and/or other materials provided with the 21 * distribution. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 30 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 31 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 * 35 * You can contact the author at : 36 * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html 37 * - LZ4 source repository : http://code.google.com/p/lz4/ 38 */ 39 40 #ifndef STATIC 41 #include <linux/module.h> 42 #include <linux/kernel.h> 43 #endif 44 #include <linux/lz4.h> 45 46 #include <asm/unaligned.h> 47 48 #include "lz4defs.h" 49 50 static const int dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; 51 #if LZ4_ARCH64 52 static const int dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; 53 #endif 54 55 static int lz4_uncompress(const char *source, char *dest, int osize) 56 { 57 const BYTE *ip = (const BYTE *) source; 58 const BYTE *ref; 59 BYTE *op = (BYTE *) dest; 60 BYTE * const oend = op + osize; 61 BYTE *cpy; 62 unsigned token; 63 size_t length; 64 65 while (1) { 66 67 /* get runlength */ 68 token = *ip++; 69 length = (token >> ML_BITS); 70 if (length == RUN_MASK) { 71 size_t len; 72 73 len = *ip++; 74 for (; len == 255; length += 255) 75 len = *ip++; 76 if (unlikely(length > (size_t)(length + len))) 77 goto _output_error; 78 length += len; 79 } 80 81 /* copy literals */ 82 cpy = op + length; 83 if (unlikely(cpy > oend - COPYLENGTH)) { 84 /* 85 * Error: not enough place for another match 86 * (min 4) + 5 literals 87 */ 88 if (cpy != oend) 89 goto _output_error; 90 91 memcpy(op, ip, length); 92 ip += length; 93 break; /* EOF */ 94 } 95 LZ4_WILDCOPY(ip, op, cpy); 96 ip -= (op - cpy); 97 op = cpy; 98 99 /* get offset */ 100 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); 101 ip += 2; 102 103 /* Error: offset create reference outside destination buffer */ 104 if (unlikely(ref < (BYTE *const) dest)) 105 goto _output_error; 106 107 /* get matchlength */ 108 length = token & ML_MASK; 109 if (length == ML_MASK) { 110 for (; *ip == 255; length += 255) 111 ip++; 112 if (unlikely(length > (size_t)(length + *ip))) 113 goto _output_error; 114 length += *ip++; 115 } 116 117 /* copy repeated sequence */ 118 if (unlikely((op - ref) < STEPSIZE)) { 119 #if LZ4_ARCH64 120 int dec64 = dec64table[op - ref]; 121 #else 122 const int dec64 = 0; 123 #endif 124 op[0] = ref[0]; 125 op[1] = ref[1]; 126 op[2] = ref[2]; 127 op[3] = ref[3]; 128 op += 4; 129 ref += 4; 130 ref -= dec32table[op-ref]; 131 PUT4(ref, op); 132 op += STEPSIZE - 4; 133 ref -= dec64; 134 } else { 135 LZ4_COPYSTEP(ref, op); 136 } 137 cpy = op + length - (STEPSIZE - 4); 138 if (cpy > (oend - COPYLENGTH)) { 139 140 /* Error: request to write beyond destination buffer */ 141 if (cpy > oend) 142 goto _output_error; 143 if ((ref + COPYLENGTH) > oend || 144 (op + COPYLENGTH) > oend) 145 goto _output_error; 146 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); 147 while (op < cpy) 148 *op++ = *ref++; 149 op = cpy; 150 /* 151 * Check EOF (should never happen, since last 5 bytes 152 * are supposed to be literals) 153 */ 154 if (op == oend) 155 goto _output_error; 156 continue; 157 } 158 LZ4_SECURECOPY(ref, op, cpy); 159 op = cpy; /* correction */ 160 } 161 /* end of decoding */ 162 return (int) (((char *)ip) - source); 163 164 /* write overflow error detected */ 165 _output_error: 166 return -1; 167 } 168 169 static int lz4_uncompress_unknownoutputsize(const char *source, char *dest, 170 int isize, size_t maxoutputsize) 171 { 172 const BYTE *ip = (const BYTE *) source; 173 const BYTE *const iend = ip + isize; 174 const BYTE *ref; 175 176 177 BYTE *op = (BYTE *) dest; 178 BYTE * const oend = op + maxoutputsize; 179 BYTE *cpy; 180 181 /* Main Loop */ 182 while (ip < iend) { 183 184 unsigned token; 185 size_t length; 186 187 /* get runlength */ 188 token = *ip++; 189 length = (token >> ML_BITS); 190 if (length == RUN_MASK) { 191 int s = 255; 192 while ((ip < iend) && (s == 255)) { 193 s = *ip++; 194 if (unlikely(length > (size_t)(length + s))) 195 goto _output_error; 196 length += s; 197 } 198 } 199 /* copy literals */ 200 cpy = op + length; 201 if ((cpy > oend - COPYLENGTH) || 202 (ip + length > iend - COPYLENGTH)) { 203 204 if (cpy > oend) 205 goto _output_error;/* writes beyond buffer */ 206 207 if (ip + length != iend) 208 goto _output_error;/* 209 * Error: LZ4 format requires 210 * to consume all input 211 * at this stage 212 */ 213 memcpy(op, ip, length); 214 op += length; 215 break;/* Necessarily EOF, due to parsing restrictions */ 216 } 217 LZ4_WILDCOPY(ip, op, cpy); 218 ip -= (op - cpy); 219 op = cpy; 220 221 /* get offset */ 222 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); 223 ip += 2; 224 if (ref < (BYTE * const) dest) 225 goto _output_error; 226 /* 227 * Error : offset creates reference 228 * outside of destination buffer 229 */ 230 231 /* get matchlength */ 232 length = (token & ML_MASK); 233 if (length == ML_MASK) { 234 while (ip < iend) { 235 int s = *ip++; 236 if (unlikely(length > (size_t)(length + s))) 237 goto _output_error; 238 length += s; 239 if (s == 255) 240 continue; 241 break; 242 } 243 } 244 245 /* copy repeated sequence */ 246 if (unlikely((op - ref) < STEPSIZE)) { 247 #if LZ4_ARCH64 248 int dec64 = dec64table[op - ref]; 249 #else 250 const int dec64 = 0; 251 #endif 252 op[0] = ref[0]; 253 op[1] = ref[1]; 254 op[2] = ref[2]; 255 op[3] = ref[3]; 256 op += 4; 257 ref += 4; 258 ref -= dec32table[op - ref]; 259 PUT4(ref, op); 260 op += STEPSIZE - 4; 261 ref -= dec64; 262 } else { 263 LZ4_COPYSTEP(ref, op); 264 } 265 cpy = op + length - (STEPSIZE-4); 266 if (cpy > oend - COPYLENGTH) { 267 if (cpy > oend) 268 goto _output_error; /* write outside of buf */ 269 270 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); 271 while (op < cpy) 272 *op++ = *ref++; 273 op = cpy; 274 /* 275 * Check EOF (should never happen, since last 5 bytes 276 * are supposed to be literals) 277 */ 278 if (op == oend) 279 goto _output_error; 280 continue; 281 } 282 LZ4_SECURECOPY(ref, op, cpy); 283 op = cpy; /* correction */ 284 } 285 /* end of decoding */ 286 return (int) (((char *) op) - dest); 287 288 /* write overflow error detected */ 289 _output_error: 290 return -1; 291 } 292 293 int lz4_decompress(const unsigned char *src, size_t *src_len, 294 unsigned char *dest, size_t actual_dest_len) 295 { 296 int ret = -1; 297 int input_len = 0; 298 299 input_len = lz4_uncompress(src, dest, actual_dest_len); 300 if (input_len < 0) 301 goto exit_0; 302 *src_len = input_len; 303 304 return 0; 305 exit_0: 306 return ret; 307 } 308 #ifndef STATIC 309 EXPORT_SYMBOL(lz4_decompress); 310 #endif 311 312 int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len, 313 unsigned char *dest, size_t *dest_len) 314 { 315 int ret = -1; 316 int out_len = 0; 317 318 out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len, 319 *dest_len); 320 if (out_len < 0) 321 goto exit_0; 322 *dest_len = out_len; 323 324 return 0; 325 exit_0: 326 return ret; 327 } 328 #ifndef STATIC 329 EXPORT_SYMBOL(lz4_decompress_unknownoutputsize); 330 331 MODULE_LICENSE("Dual BSD/GPL"); 332 MODULE_DESCRIPTION("LZ4 Decompressor"); 333 #endif 334