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 #if defined(CONFIG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI) 71 72 #include <linux/stddef.h> 73 #include <jffs2/jffs2.h> 74 #include <jffs2/compr_rubin.h> 75 76 /* Integral types that have *exactly* the same number of bits as a lzo_voidp */ 77 typedef unsigned long lzo_ptr_t; 78 typedef long lzo_sptr_t; 79 80 /* data type definitions */ 81 #define U32 unsigned long 82 #define S32 signed long 83 #define I32 long 84 #define U16 unsigned short 85 #define S16 signed short 86 #define I16 short 87 #define U8 unsigned char 88 #define S8 signed char 89 #define I8 char 90 91 #define M1_MAX_OFFSET 0x0400 92 #define M2_MAX_OFFSET 0x0800 93 #define M3_MAX_OFFSET 0x4000 94 #define M4_MAX_OFFSET 0xbfff 95 96 #define __COPY4(dst,src) * (lzo_uint32p)(dst) = * (const lzo_uint32p)(src) 97 #define COPY4(dst,src) __COPY4((lzo_ptr_t)(dst),(lzo_ptr_t)(src)) 98 99 #define TEST_IP (ip < ip_end) 100 #define TEST_OP (op <= op_end) 101 102 #define NEED_IP(x) \ 103 if ((lzo_uint)(ip_end - ip) < (lzo_uint)(x)) goto input_overrun 104 #define NEED_OP(x) \ 105 if ((lzo_uint)(op_end - op) < (lzo_uint)(x)) goto output_overrun 106 #define TEST_LOOKBEHIND(m_pos,out) if (m_pos < out) goto lookbehind_overrun 107 108 typedef U32 lzo_uint32; 109 typedef I32 lzo_int32; 110 typedef U32 lzo_uint; 111 typedef I32 lzo_int; 112 typedef int lzo_bool; 113 114 #define lzo_byte U8 115 #define lzo_bytep U8 * 116 #define lzo_charp char * 117 #define lzo_voidp void * 118 #define lzo_shortp short * 119 #define lzo_ushortp unsigned short * 120 #define lzo_uint32p lzo_uint32 * 121 #define lzo_int32p lzo_int32 * 122 #define lzo_uintp lzo_uint * 123 #define lzo_intp lzo_int * 124 #define lzo_voidpp lzo_voidp * 125 #define lzo_bytepp lzo_bytep * 126 #define lzo_sizeof_dict_t sizeof(lzo_bytep) 127 128 #define LZO_E_OK 0 129 #define LZO_E_ERROR (-1) 130 #define LZO_E_OUT_OF_MEMORY (-2) /* not used right now */ 131 #define LZO_E_NOT_COMPRESSIBLE (-3) /* not used right now */ 132 #define LZO_E_INPUT_OVERRUN (-4) 133 #define LZO_E_OUTPUT_OVERRUN (-5) 134 #define LZO_E_LOOKBEHIND_OVERRUN (-6) 135 #define LZO_E_EOF_NOT_FOUND (-7) 136 #define LZO_E_INPUT_NOT_CONSUMED (-8) 137 138 #define PTR(a) ((lzo_ptr_t) (a)) 139 #define PTR_LINEAR(a) PTR(a) 140 #define PTR_ALIGNED_4(a) ((PTR_LINEAR(a) & 3) == 0) 141 #define PTR_ALIGNED_8(a) ((PTR_LINEAR(a) & 7) == 0) 142 #define PTR_ALIGNED2_4(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 3) == 0) 143 #define PTR_ALIGNED2_8(a,b) (((PTR_LINEAR(a) | PTR_LINEAR(b)) & 7) == 0) 144 #define PTR_LT(a,b) (PTR(a) < PTR(b)) 145 #define PTR_GE(a,b) (PTR(a) >= PTR(b)) 146 #define PTR_DIFF(a,b) ((lzo_ptrdiff_t) (PTR(a) - PTR(b))) 147 #define pd(a,b) ((lzo_uint) ((a)-(b))) 148 149 typedef ptrdiff_t lzo_ptrdiff_t; 150 151 static int 152 lzo1x_decompress (const lzo_byte * in, lzo_uint in_len, 153 lzo_byte * out, lzo_uintp out_len, lzo_voidp wrkmem) 154 { 155 register lzo_byte *op; 156 register const lzo_byte *ip; 157 register lzo_uint t; 158 159 register const lzo_byte *m_pos; 160 161 const lzo_byte *const ip_end = in + in_len; 162 lzo_byte *const op_end = out + *out_len; 163 164 *out_len = 0; 165 166 op = out; 167 ip = in; 168 169 if (*ip > 17) 170 { 171 t = *ip++ - 17; 172 if (t < 4) 173 goto match_next; 174 NEED_OP (t); 175 NEED_IP (t + 1); 176 do 177 *op++ = *ip++; 178 while (--t > 0); 179 goto first_literal_run; 180 } 181 182 while (TEST_IP && TEST_OP) 183 { 184 t = *ip++; 185 if (t >= 16) 186 goto match; 187 if (t == 0) 188 { 189 NEED_IP (1); 190 while (*ip == 0) 191 { 192 t += 255; 193 ip++; 194 NEED_IP (1); 195 } 196 t += 15 + *ip++; 197 } 198 NEED_OP (t + 3); 199 NEED_IP (t + 4); 200 if (PTR_ALIGNED2_4 (op, ip)) 201 { 202 COPY4 (op, ip); 203 204 op += 4; 205 ip += 4; 206 if (--t > 0) 207 { 208 if (t >= 4) 209 { 210 do 211 { 212 COPY4 (op, ip); 213 op += 4; 214 ip += 4; 215 t -= 4; 216 } 217 while (t >= 4); 218 if (t > 0) 219 do 220 *op++ = *ip++; 221 while (--t > 0); 222 } 223 else 224 do 225 *op++ = *ip++; 226 while (--t > 0); 227 } 228 } 229 else 230 { 231 *op++ = *ip++; 232 *op++ = *ip++; 233 *op++ = *ip++; 234 do 235 *op++ = *ip++; 236 while (--t > 0); 237 } 238 first_literal_run: 239 240 t = *ip++; 241 if (t >= 16) 242 goto match; 243 244 m_pos = op - (1 + M2_MAX_OFFSET); 245 m_pos -= t >> 2; 246 m_pos -= *ip++ << 2; 247 TEST_LOOKBEHIND (m_pos, out); 248 NEED_OP (3); 249 *op++ = *m_pos++; 250 *op++ = *m_pos++; 251 *op++ = *m_pos; 252 253 goto match_done; 254 255 while (TEST_IP && TEST_OP) 256 { 257 match: 258 if (t >= 64) 259 { 260 m_pos = op - 1; 261 m_pos -= (t >> 2) & 7; 262 m_pos -= *ip++ << 3; 263 t = (t >> 5) - 1; 264 TEST_LOOKBEHIND (m_pos, out); 265 NEED_OP (t + 3 - 1); 266 goto copy_match; 267 268 } 269 else if (t >= 32) 270 { 271 t &= 31; 272 if (t == 0) 273 { 274 NEED_IP (1); 275 while (*ip == 0) 276 { 277 t += 255; 278 ip++; 279 NEED_IP (1); 280 } 281 t += 31 + *ip++; 282 } 283 284 m_pos = op - 1; 285 m_pos -= (ip[0] >> 2) + (ip[1] << 6); 286 287 ip += 2; 288 } 289 else if (t >= 16) 290 { 291 m_pos = op; 292 m_pos -= (t & 8) << 11; 293 294 t &= 7; 295 if (t == 0) 296 { 297 NEED_IP (1); 298 while (*ip == 0) 299 { 300 t += 255; 301 ip++; 302 NEED_IP (1); 303 } 304 t += 7 + *ip++; 305 } 306 307 m_pos -= (ip[0] >> 2) + (ip[1] << 6); 308 309 ip += 2; 310 if (m_pos == op) 311 goto eof_found; 312 m_pos -= 0x4000; 313 } 314 else 315 { 316 317 m_pos = op - 1; 318 m_pos -= t >> 2; 319 m_pos -= *ip++ << 2; 320 TEST_LOOKBEHIND (m_pos, out); 321 NEED_OP (2); 322 *op++ = *m_pos++; 323 *op++ = *m_pos; 324 325 goto match_done; 326 } 327 328 TEST_LOOKBEHIND (m_pos, out); 329 NEED_OP (t + 3 - 1); 330 if (t >= 2 * 4 - (3 - 1) 331 && PTR_ALIGNED2_4 (op, m_pos)) 332 { 333 COPY4 (op, m_pos); 334 op += 4; 335 m_pos += 4; 336 t -= 4 - (3 - 1); 337 do 338 { 339 COPY4 (op, m_pos); 340 op += 4; 341 m_pos += 4; 342 t -= 4; 343 } 344 while (t >= 4); 345 if (t > 0) 346 do 347 *op++ = *m_pos++; 348 while (--t > 0); 349 } 350 else 351 352 { 353 copy_match: 354 *op++ = *m_pos++; 355 *op++ = *m_pos++; 356 do 357 *op++ = *m_pos++; 358 while (--t > 0); 359 } 360 361 match_done: 362 t = ip[-2] & 3; 363 364 if (t == 0) 365 break; 366 367 match_next: 368 NEED_OP (t); 369 NEED_IP (t + 1); 370 do 371 *op++ = *ip++; 372 while (--t > 0); 373 t = *ip++; 374 } 375 } 376 *out_len = op - out; 377 return LZO_E_EOF_NOT_FOUND; 378 379 eof_found: 380 *out_len = op - out; 381 return (ip == ip_end ? LZO_E_OK : 382 (ip < 383 ip_end ? LZO_E_INPUT_NOT_CONSUMED : LZO_E_INPUT_OVERRUN)); 384 385 input_overrun: 386 *out_len = op - out; 387 return LZO_E_INPUT_OVERRUN; 388 389 output_overrun: 390 *out_len = op - out; 391 return LZO_E_OUTPUT_OVERRUN; 392 393 lookbehind_overrun: 394 *out_len = op - out; 395 return LZO_E_LOOKBEHIND_OVERRUN; 396 } 397 398 int lzo_decompress(unsigned char *data_in, unsigned char *cpage_out, 399 u32 srclen, u32 destlen) 400 { 401 lzo_uint outlen = destlen; 402 return lzo1x_decompress (data_in, srclen, cpage_out, &outlen, NULL); 403 } 404 405 #endif 406