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 int lz4_uncompress(const char *source, char *dest, int osize) 51 { 52 const BYTE *ip = (const BYTE *) source; 53 const BYTE *ref; 54 BYTE *op = (BYTE *) dest; 55 BYTE * const oend = op + osize; 56 BYTE *cpy; 57 unsigned token; 58 size_t length; 59 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; 60 #if LZ4_ARCH64 61 size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; 62 #endif 63 64 while (1) { 65 66 /* get runlength */ 67 token = *ip++; 68 length = (token >> ML_BITS); 69 if (length == RUN_MASK) { 70 size_t len; 71 72 len = *ip++; 73 for (; len == 255; length += 255) 74 len = *ip++; 75 if (unlikely(length > (size_t)(length + len))) 76 goto _output_error; 77 length += len; 78 } 79 80 /* copy literals */ 81 cpy = op + length; 82 if (unlikely(cpy > oend - COPYLENGTH)) { 83 /* 84 * Error: not enough place for another match 85 * (min 4) + 5 literals 86 */ 87 if (cpy != oend) 88 goto _output_error; 89 90 memcpy(op, ip, length); 91 ip += length; 92 break; /* EOF */ 93 } 94 LZ4_WILDCOPY(ip, op, cpy); 95 ip -= (op - cpy); 96 op = cpy; 97 98 /* get offset */ 99 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); 100 ip += 2; 101 102 /* Error: offset create reference outside destination buffer */ 103 if (unlikely(ref < (BYTE *const) dest)) 104 goto _output_error; 105 106 /* get matchlength */ 107 length = token & ML_MASK; 108 if (length == ML_MASK) { 109 for (; *ip == 255; length += 255) 110 ip++; 111 if (unlikely(length > (size_t)(length + *ip))) 112 goto _output_error; 113 length += *ip++; 114 } 115 116 /* copy repeated sequence */ 117 if (unlikely((op - ref) < STEPSIZE)) { 118 #if LZ4_ARCH64 119 size_t dec64 = dec64table[op - ref]; 120 #else 121 const int dec64 = 0; 122 #endif 123 op[0] = ref[0]; 124 op[1] = ref[1]; 125 op[2] = ref[2]; 126 op[3] = ref[3]; 127 op += 4; 128 ref += 4; 129 ref -= dec32table[op-ref]; 130 PUT4(ref, op); 131 op += STEPSIZE - 4; 132 ref -= dec64; 133 } else { 134 LZ4_COPYSTEP(ref, op); 135 } 136 cpy = op + length - (STEPSIZE - 4); 137 if (cpy > (oend - COPYLENGTH)) { 138 139 /* Error: request to write beyond destination buffer */ 140 if (cpy > oend) 141 goto _output_error; 142 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); 143 while (op < cpy) 144 *op++ = *ref++; 145 op = cpy; 146 /* 147 * Check EOF (should never happen, since last 5 bytes 148 * are supposed to be literals) 149 */ 150 if (op == oend) 151 goto _output_error; 152 continue; 153 } 154 LZ4_SECURECOPY(ref, op, cpy); 155 op = cpy; /* correction */ 156 } 157 /* end of decoding */ 158 return (int) (((char *)ip) - source); 159 160 /* write overflow error detected */ 161 _output_error: 162 return -1; 163 } 164 165 static int lz4_uncompress_unknownoutputsize(const char *source, char *dest, 166 int isize, size_t maxoutputsize) 167 { 168 const BYTE *ip = (const BYTE *) source; 169 const BYTE *const iend = ip + isize; 170 const BYTE *ref; 171 172 173 BYTE *op = (BYTE *) dest; 174 BYTE * const oend = op + maxoutputsize; 175 BYTE *cpy; 176 177 size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; 178 #if LZ4_ARCH64 179 size_t dec64table[] = {0, 0, 0, -1, 0, 1, 2, 3}; 180 #endif 181 182 /* Main Loop */ 183 while (ip < iend) { 184 185 unsigned token; 186 size_t length; 187 188 /* get runlength */ 189 token = *ip++; 190 length = (token >> ML_BITS); 191 if (length == RUN_MASK) { 192 int s = 255; 193 while ((ip < iend) && (s == 255)) { 194 s = *ip++; 195 if (unlikely(length > (size_t)(length + s))) 196 goto _output_error; 197 length += s; 198 } 199 } 200 /* copy literals */ 201 cpy = op + length; 202 if ((cpy > oend - COPYLENGTH) || 203 (ip + length > iend - COPYLENGTH)) { 204 205 if (cpy > oend) 206 goto _output_error;/* writes beyond buffer */ 207 208 if (ip + length != iend) 209 goto _output_error;/* 210 * Error: LZ4 format requires 211 * to consume all input 212 * at this stage 213 */ 214 memcpy(op, ip, length); 215 op += length; 216 break;/* Necessarily EOF, due to parsing restrictions */ 217 } 218 LZ4_WILDCOPY(ip, op, cpy); 219 ip -= (op - cpy); 220 op = cpy; 221 222 /* get offset */ 223 LZ4_READ_LITTLEENDIAN_16(ref, cpy, ip); 224 ip += 2; 225 if (ref < (BYTE * const) dest) 226 goto _output_error; 227 /* 228 * Error : offset creates reference 229 * outside of destination buffer 230 */ 231 232 /* get matchlength */ 233 length = (token & ML_MASK); 234 if (length == ML_MASK) { 235 while (ip < iend) { 236 int s = *ip++; 237 if (unlikely(length > (size_t)(length + s))) 238 goto _output_error; 239 length += s; 240 if (s == 255) 241 continue; 242 break; 243 } 244 } 245 246 /* copy repeated sequence */ 247 if (unlikely((op - ref) < STEPSIZE)) { 248 #if LZ4_ARCH64 249 size_t dec64 = dec64table[op - ref]; 250 #else 251 const int dec64 = 0; 252 #endif 253 op[0] = ref[0]; 254 op[1] = ref[1]; 255 op[2] = ref[2]; 256 op[3] = ref[3]; 257 op += 4; 258 ref += 4; 259 ref -= dec32table[op - ref]; 260 PUT4(ref, op); 261 op += STEPSIZE - 4; 262 ref -= dec64; 263 } else { 264 LZ4_COPYSTEP(ref, op); 265 } 266 cpy = op + length - (STEPSIZE-4); 267 if (cpy > oend - COPYLENGTH) { 268 if (cpy > oend) 269 goto _output_error; /* write outside of buf */ 270 271 LZ4_SECURECOPY(ref, op, (oend - COPYLENGTH)); 272 while (op < cpy) 273 *op++ = *ref++; 274 op = cpy; 275 /* 276 * Check EOF (should never happen, since last 5 bytes 277 * are supposed to be literals) 278 */ 279 if (op == oend) 280 goto _output_error; 281 continue; 282 } 283 LZ4_SECURECOPY(ref, op, cpy); 284 op = cpy; /* correction */ 285 } 286 /* end of decoding */ 287 return (int) (((char *) op) - dest); 288 289 /* write overflow error detected */ 290 _output_error: 291 return -1; 292 } 293 294 int lz4_decompress(const unsigned char *src, size_t *src_len, 295 unsigned char *dest, size_t actual_dest_len) 296 { 297 int ret = -1; 298 int input_len = 0; 299 300 input_len = lz4_uncompress(src, dest, actual_dest_len); 301 if (input_len < 0) 302 goto exit_0; 303 *src_len = input_len; 304 305 return 0; 306 exit_0: 307 return ret; 308 } 309 #ifndef STATIC 310 EXPORT_SYMBOL(lz4_decompress); 311 #endif 312 313 int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len, 314 unsigned char *dest, size_t *dest_len) 315 { 316 int ret = -1; 317 int out_len = 0; 318 319 out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len, 320 *dest_len); 321 if (out_len < 0) 322 goto exit_0; 323 *dest_len = out_len; 324 325 return 0; 326 exit_0: 327 return ret; 328 } 329 #ifndef STATIC 330 EXPORT_SYMBOL(lz4_decompress_unknownoutputsize); 331 332 MODULE_LICENSE("Dual BSD/GPL"); 333 MODULE_DESCRIPTION("LZ4 Decompressor"); 334 #endif 335