fs/jffs2/compr_lzo.c

   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
 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
 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 }