fs/jffs2/compr_lzari.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_lzari.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
  11  *
  12  */
  13
  14 /*
  15    Lempel-Ziv-Arithmetic coding compression module for jffs2
  16    Based on the LZARI source included in LDS (lossless datacompression sources)
  17 */
  18
  19 /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
  20
  21 /*
  22 Original copyright follows:
  23
  24 **************************************************************
  25         LZARI.C -- A Data Compression Program
  26         (tab = 4 spaces)
  27 **************************************************************
  28         4/7/1989 Haruhiko Okumura
  29         Use, distribute, and modify this program freely.
  30         Please send me your improved versions.
  31                 PC-VAN          SCIENCE
  32                 NIFTY-Serve     PAF01022
  33                 CompuServe      74050,1022
  34 **************************************************************
  35
  36 LZARI.C (c)1989 by Haruyasu Yoshizaki, Haruhiko Okumura, and Kenji Rikitake.
  37 All rights reserved. Permission granted for non-commercial use.
  38
  39 */
  40
  41 /*
  42
  43         2004-02-18  pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
  44                                 Removed unused variables and fixed no return value
  45
  46         2004-02-16  pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
  47                                 Initial release
  48
  49 */
  50
  51
  52 #include <config.h>
  53 #include <linux/stddef.h>
  54 #include <jffs2/jffs2.h>
  55
  56
  57 #define N                       4096    /* size of ring buffer */
  58 #define F                       60      /* upper limit for match_length */
  59 #define THRESHOLD               2       /* encode string into position and length
  60                                            if match_length is greater than this */
  61 #define NIL                     N       /* index for root of binary search trees */
  62
  63 static unsigned char
  64                 text_buf[N + F - 1];    /* ring buffer of size N,
  65                         with extra F-1 bytes to facilitate string comparison */
  66
  67 /********** Arithmetic Compression **********/
  68
  69 /*  If you are not familiar with arithmetic compression, you should read
  70                 I. E. Witten, R. M. Neal, and J. G. Cleary,
  71                         Communications of the ACM, Vol. 30, pp. 520-540 (1987),
  72         from which much have been borrowed.  */
  73
  74 #define M   15
  75
  76 /*      Q1 (= 2 to the M) must be sufficiently large, but not so
  77         large as the unsigned long 4 * Q1 * (Q1 - 1) overflows.  */
  78
  79 #define Q1  (1UL << M)
  80 #define Q2  (2 * Q1)
  81 #define Q3  (3 * Q1)
  82 #define Q4  (4 * Q1)
  83 #define MAX_CUM (Q1 - 1)
  84
  85 #define N_CHAR  (256 - THRESHOLD + F)
  86         /* character code = 0, 1, ..., N_CHAR - 1 */
  87
  88 static unsigned long char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
  89 static unsigned long
  90         sym_freq[N_CHAR + 1],  /* frequency for symbols */
  91         sym_cum[N_CHAR + 1],   /* cumulative freq for symbols */
  92         position_cum[N + 1];   /* cumulative freq for positions */
  93
  94 static void StartModel(void)  /* Initialize model */
  95 {
  96         unsigned long ch, sym, i;
  97
  98         sym_cum[N_CHAR] = 0;
  99         for (sym = N_CHAR; sym >= 1; sym--) {
 100                 ch = sym - 1;
 101                 char_to_sym[ch] = sym;  sym_to_char[sym] = ch;
 102                 sym_freq[sym] = 1;
 103                 sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
 104         }
 105         sym_freq[0] = 0;  /* sentinel (!= sym_freq[1]) */
 106         position_cum[N] = 0;
 107         for (i = N; i >= 1; i--)
 108                 position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
 109                         /* empirical distribution function (quite tentative) */
 110                         /* Please devise a better mechanism! */
 111 }
 112
 113 static void UpdateModel(unsigned long sym)
 114 {
 115         unsigned long c, ch_i, ch_sym;
 116         unsigned long i;
 117         if (sym_cum[0] >= MAX_CUM) {
 118                 c = 0;
 119                 for (i = N_CHAR; i > 0; i--) {
 120                         sym_cum[i] = c;
 121                         c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
 122                 }
 123                 sym_cum[0] = c;
 124         }
 125         for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
 126         if (i < sym) {
 127                 ch_i = sym_to_char[i];    ch_sym = sym_to_char[sym];
 128                 sym_to_char[i] = ch_sym;  sym_to_char[sym] = ch_i;
 129                 char_to_sym[ch_i] = sym;  char_to_sym[ch_sym] = i;
 130         }
 131         sym_freq[i]++;
 132         while (--i > 0) sym_cum[i]++;
 133         sym_cum[0]++;
 134 }
 135
 136 static unsigned long BinarySearchSym(unsigned long x)
 137         /* 1      if x >= sym_cum[1],
 138            N_CHAR if sym_cum[N_CHAR] > x,
 139            i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
 140 {
 141         unsigned long i, j, k;
 142
 143         i = 1;  j = N_CHAR;
 144         while (i < j) {
 145                 k = (i + j) / 2;
 146                 if (sym_cum[k] > x) i = k + 1;  else j = k;
 147         }
 148         return i;
 149 }
 150
 151 unsigned long BinarySearchPos(unsigned long x)
 152         /* 0 if x >= position_cum[1],
 153            N - 1 if position_cum[N] > x,
 154            i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
 155 {
 156         unsigned long i, j, k;
 157
 158         i = 1;  j = N;
 159         while (i < j) {
 160                 k = (i + j) / 2;
 161                 if (position_cum[k] > x) i = k + 1;  else j = k;
 162         }
 163         return i - 1;
 164 }
 165
 166 static int Decode(unsigned char *srcbuf, unsigned char *dstbuf, unsigned long srclen,
 167                                         unsigned long dstlen)   /* Just the reverse of Encode(). */
 168 {
 169         unsigned long i, r, j, k, c, range, sym;
 170         unsigned char *ip, *op;
 171         unsigned char *srcend = srcbuf + srclen;
 172         unsigned char *dstend = dstbuf + dstlen;
 173         unsigned char buffer = 0;
 174         unsigned char mask = 0;
 175         unsigned long low = 0;
 176         unsigned long high = Q4;
 177         unsigned long value = 0;
 178
 179         ip = srcbuf;
 180         op = dstbuf;
 181         for (i = 0; i < M + 2; i++) {
 182                 value *= 2;
 183                 if ((mask >>= 1) == 0) {
 184                         buffer = (ip >= srcend) ? 0 : *(ip++);
 185                         mask = 128;
 186                 }
 187                 value += ((buffer & mask) != 0);
 188         }
 189
 190         StartModel();
 191         for (i = 0; i < N - F; i++) text_buf[i] = ' ';
 192         r = N - F;
 193
 194         while (op < dstend) {
 195                 range = high - low;
 196                 sym = BinarySearchSym((unsigned long)
 197                                 (((value - low + 1) * sym_cum[0] - 1) / range));
 198                 high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
 199                 low +=       (range * sym_cum[sym    ]) / sym_cum[0];
 200                 for ( ; ; ) {
 201                         if (low >= Q2) {
 202                                 value -= Q2;  low -= Q2;  high -= Q2;
 203                         } else if (low >= Q1 && high <= Q3) {
 204                                 value -= Q1;  low -= Q1;  high -= Q1;
 205                         } else if (high > Q2) break;
 206                         low += low;  high += high;
 207                         value *= 2;
 208                         if ((mask >>= 1) == 0) {
 209                                 buffer = (ip >= srcend) ? 0 : *(ip++);
 210                                 mask = 128;
 211                         }
 212                         value += ((buffer & mask) != 0);
 213                 }
 214                 c = sym_to_char[sym];
 215                 UpdateModel(sym);
 216                 if (c < 256) {
 217                         if (op >= dstend) return -1;
 218                         *(op++) = c;
 219                         text_buf[r++] = c;
 220                         r &= (N - 1);
 221                 } else {
 222                         j = c - 255 + THRESHOLD;
 223                         range = high - low;
 224                         i = BinarySearchPos((unsigned long)
 225                                 (((value - low + 1) * position_cum[0] - 1) / range));
 226                         high = low + (range * position_cum[i    ]) / position_cum[0];
 227                         low +=       (range * position_cum[i + 1]) / position_cum[0];
 228                         for ( ; ; ) {
 229                                 if (low >= Q2) {
 230                                         value -= Q2;  low -= Q2;  high -= Q2;
 231                                 } else if (low >= Q1 && high <= Q3) {
 232                                         value -= Q1;  low -= Q1;  high -= Q1;
 233                                 } else if (high > Q2) break;
 234                                 low += low;  high += high;
 235                                 value *= 2;
 236                                 if ((mask >>= 1) == 0) {
 237                                         buffer = (ip >= srcend) ? 0 : *(ip++);
 238                                         mask = 128;
 239                                 }
 240                                 value += ((buffer & mask) != 0);
 241                         }
 242                         i = (r - i - 1) & (N - 1);
 243                         for (k = 0; k < j; k++) {
 244                                 c = text_buf[(i + k) & (N - 1)];
 245                                 if (op >= dstend) return -1;
 246                                 *(op++) = c;
 247                                 text_buf[r++] = c;
 248                                 r &= (N - 1);
 249                         }
 250                 }
 251         }
 252         return 0;
 253 }
 254
 255 int lzari_decompress(unsigned char *data_in, unsigned char *cpage_out,
 256                       u32 srclen, u32 destlen)
 257 {
 258     return Decode(data_in, cpage_out, srclen, destlen);
 259 }