1 /* 2 * JFFS2 -- Journalling Flash File System, Version 2. 3 * 4 * Copyright (C) 2004 Patrik Kluba, 5 * University of Szeged, Hungary 6 * 7 * For licensing information, see the file 'LICENCE' in the 8 * jffs2 directory. 9 * 10 * $Id: compr_lzo.c,v 1.3 2004/06/23 16:34:39 havasi Exp $ 11 * 12 */ 13 14 /* 15 LZO1X-1 (and -999) compression module for jffs2 16 based on the original LZO sources 17 */ 18 19 /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */ 20 21 /* 22 Original copyright notice follows: 23 24 lzo1x_9x.c -- implementation of the LZO1X-999 compression algorithm 25 lzo_ptr.h -- low-level pointer constructs 26 lzo_swd.ch -- sliding window dictionary 27 lzoconf.h -- configuration for the LZO real-time data compression library 28 lzo_mchw.ch -- matching functions using a window 29 minilzo.c -- mini subset of the LZO real-time data compression library 30 config1x.h -- configuration for the LZO1X algorithm 31 lzo1x.h -- public interface of the LZO1X compression algorithm 32 33 These files are part of the LZO real-time data compression library. 34 35 Copyright (C) 1996-2002 Markus Franz Xaver Johannes Oberhumer 36 All Rights Reserved. 37 38 The LZO library is free software; you can redistribute it and/or 39 modify it under the terms of the GNU General Public License as 40 published by the Free Software Foundation; either version 2 of 41 the License, or (at your option) any later version. 42 43 The LZO library is distributed in the hope that it will be useful, 44 but WITHOUT ANY WARRANTY; without even the implied warranty of 45 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 46 GNU General Public License for more details. 47 48 You should have received a copy of the GNU General Public License 49 along with the LZO library; see the file COPYING. 50 If not, write to the Free Software Foundation, Inc., 51 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 52 53 Markus F.X.J. Oberhumer 54 <markus@oberhumer.com> 55 */ 56 57 /* 58 59 2004-02-16 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu> 60 Initial release 61 -removed all 16 bit code 62 -all sensitive data will be on 4 byte boundary 63 -removed check parts for library use 64 -removed all but LZO1X-* compression 65 66 */ 67 68 69 #include <config.h> 70 #include <linux/stddef.h> 71 #include <jffs2/jffs2.h> 72 #include <jffs2/compr_rubin.h> 73 74 /* Integral types that have *exactly* the same number of bits as a lzo_voidp */ 75 typedef unsigned long lzo_ptr_t; 76 typedef long lzo_sptr_t; 77 78 /* data type definitions */ 79 #define U32 unsigned long 80 #define S32 signed long 81 #define I32 long 82 #define U16 unsigned short 83 #define S16 signed short 84 #define I16 short 85 #define U8 unsigned char 86 #define S8 signed char 87 #define I8 char 88 89 #define M1_MAX_OFFSET 0x0400 90 #define M2_MAX_OFFSET 0x0800 91 #define M3_MAX_OFFSET 0x4000 92 #define M4_MAX_OFFSET 0xbfff 93 94 #define __COPY4(dst,src) * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src) 95 #define COPY4(dst,src) __COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src)) 96 97 #define TEST_IP (ip < ip_end) 98 #define TEST_OP (op <= op_end) 99 100 #define NEED_IP(x) \ 101 if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x)) goto input_overrun 102 #define NEED_OP(x) \ 103 if ((lzo_uint)(op_end - op) < (lzo_uint)(x)) goto output_overrun 104 #define TEST_LOOKBEHIND(m_pos,out) if (m_pos < out) goto lookbehind_overrun 105 106 typedef U32 lzo_uint32; 107 typedef I32 lzo_int32; 108 typedef U32 lzo_uint; 109 typedef I32 lzo_int; 110 typedef int lzo_bool; 111 112 #define lzo_byte U8 113 #define lzo_bytep U8 * 114 #define lzo_charp char * 115 #define lzo_voidp void * 116 #define lzo_shortp short * 117 #define lzo_ushortp unsigned short * 118 #define lzo_uint32p lzo_uint32 * 119 #define lzo_int32p lzo_int32 * 120 #define lzo_uintp lzo_uint * 121 #define lzo_intp lzo_int * 122 #define lzo_voidpp lzo_voidp * 123 #define lzo_bytepp lzo_bytep * 124 #define lzo_sizeof_dict_t sizeof(lzo_bytep) 125 126 #define LZO_E_OK 0 127 #define LZO_E_ERROR (-1) 128 #define LZO_E_OUT_OF_MEMORY (-2) /* not used right now */ 129 #define LZO_E_NOT_COMPRESSIBLE (-3) /* not used right now */ 130 #define LZO_E_INPUT_OVERRUN (-4) 131 #define LZO_E_OUTPUT_OVERRUN (-5) 132 #define LZO_E_LOOKBEHIND_OVERRUN (-6) 133 #define LZO_E_EOF_NOT_FOUND (-7) 134 #define LZO_E_INPUT_NOT_CONSUMED (-8) 135 136 #define PTR(a) ((lzo_ptr_t) (a)) 137 #define PTR_LINEAR(a) PTR(a) 138 #define PTR_ALIGNED_4(a) ((PTR_LINEAR(a) & 3) == 0) 139 #define PTR_ALIGNED_8(a) ((PTR_LINEAR(a) & 7) == 0) 140 #define PTR_ALIGNED2_4(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0) 141 #define PTR_ALIGNED2_8(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0) 142 #define PTR_LT(a,b) (PTR(a) < PTR(b)) 143 #define PTR_GE(a,b) (PTR(a) >= PTR(b)) 144 #define PTR_DIFF(a,b) ((lzo_ptrdiff_t) (PTR(a) - PTR(b))) 145 #define pd(a,b) ((lzo_uint) ((a)-(b))) 146 147 typedef ptrdiff_t lzo_ptrdiff_t; 148 149 static int lzo1x_decompress(const lzo_byte * in,lzo_uint in_len,lzo_byte * out,lzo_uintp out_len,lzo_voidp wrkmem)150 lzo1x_decompress (const lzo_byte * in, lzo_uint in_len, 151 lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem) 152 { 153 register lzo_byte *op; 154 register const lzo_byte *ip; 155 register lzo_uint t; 156 157 register const lzo_byte *m_pos; 158 159 const lzo_byte *const ip_end = in + in_len; 160 lzo_byte *const op_end = out + *out_len; 161 162 *out_len = 0; 163 164 op = out; 165 ip = in; 166 167 if (*ip > 17) 168 { 169 t = *ip++ - 17; 170 if (t < 4) 171 goto match_next; 172 NEED_OP (t); 173 NEED_IP (t + 1); 174 do 175 *op++ = *ip++; 176 while (--t > 0); 177 goto first_literal_run; 178 } 179 180 while (TEST_IP && TEST_OP) 181 { 182 t = *ip++; 183 if (t >= 16) 184 goto match; 185 if (t == 0) 186 { 187 NEED_IP (1); 188 while (*ip == 0) 189 { 190 t += 255; 191 ip++; 192 NEED_IP (1); 193 } 194 t += 15 + *ip++; 195 } 196 NEED_OP (t + 3); 197 NEED_IP (t + 4); 198 if (PTR_ALIGNED2_4 (op, ip)) 199 { 200 COPY4 (op, ip); 201 202 op += 4; 203 ip += 4; 204 if (--t > 0) 205 { 206 if (t >= 4) 207 { 208 do 209 { 210 COPY4 (op, ip); 211 op += 4; 212 ip += 4; 213 t -= 4; 214 } 215 while (t >= 4); 216 if (t > 0) 217 do 218 *op++ = *ip++; 219 while (--t > 0); 220 } 221 else 222 do 223 *op++ = *ip++; 224 while (--t > 0); 225 } 226 } 227 else 228 { 229 *op++ = *ip++; 230 *op++ = *ip++; 231 *op++ = *ip++; 232 do 233 *op++ = *ip++; 234 while (--t > 0); 235 } 236 first_literal_run: 237 238 t = *ip++; 239 if (t >= 16) 240 goto match; 241 242 m_pos = op - (1 + M2_MAX_OFFSET); 243 m_pos -= t >> 2; 244 m_pos -= *ip++ << 2; 245 TEST_LOOKBEHIND (m_pos, out); 246 NEED_OP (3); 247 *op++ = *m_pos++; 248 *op++ = *m_pos++; 249 *op++ = *m_pos; 250 251 goto match_done; 252 253 while (TEST_IP && TEST_OP) 254 { 255 match: 256 if (t >= 64) 257 { 258 m_pos = op - 1; 259 m_pos -= (t >> 2) & 7; 260 m_pos -= *ip++ << 3; 261 t = (t >> 5) - 1; 262 TEST_LOOKBEHIND (m_pos, out); 263 NEED_OP (t + 3 - 1); 264 goto copy_match; 265 266 } 267 else if (t >= 32) 268 { 269 t &= 31; 270 if (t == 0) 271 { 272 NEED_IP (1); 273 while (*ip == 0) 274 { 275 t += 255; 276 ip++; 277 NEED_IP (1); 278 } 279 t += 31 + *ip++; 280 } 281 282 m_pos = op - 1; 283 m_pos -= (ip[0] >> 2) + (ip[1] << 6); 284 285 ip += 2; 286 } 287 else if (t >= 16) 288 { 289 m_pos = op; 290 m_pos -= (t & 8) << 11; 291 292 t &= 7; 293 if (t == 0) 294 { 295 NEED_IP (1); 296 while (*ip == 0) 297 { 298 t += 255; 299 ip++; 300 NEED_IP (1); 301 } 302 t += 7 + *ip++; 303 } 304 305 m_pos -= (ip[0] >> 2) + (ip[1] << 6); 306 307 ip += 2; 308 if (m_pos == op) 309 goto eof_found; 310 m_pos -= 0x4000; 311 } 312 else 313 { 314 315 m_pos = op - 1; 316 m_pos -= t >> 2; 317 m_pos -= *ip++ << 2; 318 TEST_LOOKBEHIND (m_pos, out); 319 NEED_OP (2); 320 *op++ = *m_pos++; 321 *op++ = *m_pos; 322 323 goto match_done; 324 } 325 326 TEST_LOOKBEHIND (m_pos, out); 327 NEED_OP (t + 3 - 1); 328 if (t >= 2 * 4 - (3 - 1) 329 && PTR_ALIGNED2_4 (op, m_pos)) 330 { 331 COPY4 (op, m_pos); 332 op += 4; 333 m_pos += 4; 334 t -= 4 - (3 - 1); 335 do 336 { 337 COPY4 (op, m_pos); 338 op += 4; 339 m_pos += 4; 340 t -= 4; 341 } 342 while (t >= 4); 343 if (t > 0) 344 do 345 *op++ = *m_pos++; 346 while (--t > 0); 347 } 348 else 349 350 { 351 copy_match: 352 *op++ = *m_pos++; 353 *op++ = *m_pos++; 354 do 355 *op++ = *m_pos++; 356 while (--t > 0); 357 } 358 359 match_done: 360 t = ip[-2] & 3; 361 362 if (t == 0) 363 break; 364 365 match_next: 366 NEED_OP (t); 367 NEED_IP (t + 1); 368 do 369 *op++ = *ip++; 370 while (--t > 0); 371 t = *ip++; 372 } 373 } 374 *out_len = op - out; 375 return LZO_E_EOF_NOT_FOUND; 376 377 eof_found: 378 *out_len = op - out; 379 return (ip == ip_end ? LZO_E_OK : 380 (ip < 381 ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); 382 383 input_overrun: 384 *out_len = op - out; 385 return LZO_E_INPUT_OVERRUN; 386 387 output_overrun: 388 *out_len = op - out; 389 return LZO_E_OUTPUT_OVERRUN; 390 391 lookbehind_overrun: 392 *out_len = op - out; 393 return LZO_E_LOOKBEHIND_OVERRUN; 394 } 395 lzo_decompress(unsigned char * data_in,unsigned char * cpage_out,u32 srclen,u32 destlen)396 int lzo_decompress(unsigned char *data_in, unsigned char *cpage_out, 397 u32 srclen, u32 destlen) 398 { 399 lzo_uint outlen = destlen; 400 return lzo1x_decompress (data_in, srclen, cpage_out, &outlen, NULL); 401 } 402