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 #if ((CONFIG_COMMANDS & CFG_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 /* ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI)) */