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