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 #if ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI))
  54
  55 #include <linux/stddef.h>
  56 #include <jffs2/jffs2.h>
  57
  58
  59 #define N                       4096    /* size of ring buffer */
  60 #define F                       60      /* upper limit for match_length */
  61 #define THRESHOLD               2       /* encode string into position and length
  62                                            if match_length is greater than this */
  63 #define NIL                     N       /* index for root of binary search trees */
  64
  65 static unsigned char
  66                 text_buf[N + F - 1];    /* ring buffer of size N,
  67                         with extra F-1 bytes to facilitate string comparison */
  68
  69 /********** Arithmetic Compression **********/
  70
  71 /*  If you are not familiar with arithmetic compression, you should read
  72                 I. E. Witten, R. M. Neal, and J. G. Cleary,
  73                         Communications of the ACM, Vol. 30, pp. 520-540 (1987),
  74         from which much have been borrowed.  */
  75
  76 #define M   15
  77
  78 /*      Q1 (= 2 to the M) must be sufficiently large, but not so
  79         large as the unsigned long 4 * Q1 * (Q1 - 1) overflows.  */
  80
  81 #define Q1  (1UL << M)
  82 #define Q2  (2 * Q1)
  83 #define Q3  (3 * Q1)
  84 #define Q4  (4 * Q1)
  85 #define MAX_CUM (Q1 - 1)
  86
  87 #define N_CHAR  (256 - THRESHOLD + F)
  88         /* character code = 0, 1, ..., N_CHAR - 1 */
  89
  90 static unsigned long char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
  91 static unsigned long
  92         sym_freq[N_CHAR + 1],  /* frequency for symbols */
  93         sym_cum[N_CHAR + 1],   /* cumulative freq for symbols */
  94         position_cum[N + 1];   /* cumulative freq for positions */
  95
  96 static void StartModel(void)  /* Initialize model */
  97 {
  98         unsigned long ch, sym, i;
  99
 100         sym_cum[N_CHAR] = 0;
 101         for (sym = N_CHAR; sym >= 1; sym--) {
 102                 ch = sym - 1;
 103                 char_to_sym[ch] = sym;  sym_to_char[sym] = ch;
 104                 sym_freq[sym] = 1;
 105                 sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
 106         }
 107         sym_freq[0] = 0;  /* sentinel (!= sym_freq[1]) */
 108         position_cum[N] = 0;
 109         for (i = N; i >= 1; i--)
 110                 position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
 111                         /* empirical distribution function (quite tentative) */
 112                         /* Please devise a better mechanism! */
 113 }
 114
 115 static void UpdateModel(unsigned long sym)
 116 {
 117         unsigned long c, ch_i, ch_sym;
 118         unsigned long i;
 119         if (sym_cum[0] >= MAX_CUM) {
 120                 c = 0;
 121                 for (i = N_CHAR; i > 0; i--) {
 122                         sym_cum[i] = c;
 123                         c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
 124                 }
 125                 sym_cum[0] = c;
 126         }
 127         for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
 128         if (i < sym) {
 129                 ch_i = sym_to_char[i];    ch_sym = sym_to_char[sym];
 130                 sym_to_char[i] = ch_sym;  sym_to_char[sym] = ch_i;
 131                 char_to_sym[ch_i] = sym;  char_to_sym[ch_sym] = i;
 132         }
 133         sym_freq[i]++;
 134         while (--i > 0) sym_cum[i]++;
 135         sym_cum[0]++;
 136 }
 137
 138 static unsigned long BinarySearchSym(unsigned long x)
 139         /* 1      if x >= sym_cum[1],
 140            N_CHAR if sym_cum[N_CHAR] > x,
 141            i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
 142 {
 143         unsigned long i, j, k;
 144
 145         i = 1;  j = N_CHAR;
 146         while (i < j) {
 147                 k = (i + j) / 2;
 148                 if (sym_cum[k] > x) i = k + 1;  else j = k;
 149         }
 150         return i;
 151 }
 152
 153 unsigned long BinarySearchPos(unsigned long x)
 154         /* 0 if x >= position_cum[1],
 155            N - 1 if position_cum[N] > x,
 156            i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
 157 {
 158         unsigned long i, j, k;
 159
 160         i = 1;  j = N;
 161         while (i < j) {
 162                 k = (i + j) / 2;
 163                 if (position_cum[k] > x) i = k + 1;  else j = k;
 164         }
 165         return i - 1;
 166 }
 167
 168 static int Decode(unsigned char *srcbuf, unsigned char *dstbuf, unsigned long srclen,
 169                                         unsigned long dstlen)   /* Just the reverse of Encode(). */
 170 {
 171         unsigned long i, r, j, k, c, range, sym;
 172         unsigned char *ip, *op;
 173         unsigned char *srcend = srcbuf + srclen;
 174         unsigned char *dstend = dstbuf + dstlen;
 175         unsigned char buffer = 0;
 176         unsigned char mask = 0;
 177         unsigned long low = 0;
 178         unsigned long high = Q4;
 179         unsigned long value = 0;
 180
 181         ip = srcbuf;
 182         op = dstbuf;
 183         for (i = 0; i < M + 2; i++) {
 184                 value *= 2;
 185                 if ((mask >>= 1) == 0) {
 186                         buffer = (ip >= srcend) ? 0 : *(ip++);
 187                         mask = 128;
 188                 }
 189                 value += ((buffer & mask) != 0);
 190         }
 191
 192         StartModel();
 193         for (i = 0; i < N - F; i++) text_buf[i] = ' ';
 194         r = N - F;
 195
 196         while (op < dstend) {
 197                 range = high - low;
 198                 sym = BinarySearchSym((unsigned long)
 199                                 (((value - low + 1) * sym_cum[0] - 1) / range));
 200                 high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
 201                 low +=       (range * sym_cum[sym    ]) / sym_cum[0];
 202                 for ( ; ; ) {
 203                         if (low >= Q2) {
 204                                 value -= Q2;  low -= Q2;  high -= Q2;
 205                         } else if (low >= Q1 && high <= Q3) {
 206                                 value -= Q1;  low -= Q1;  high -= Q1;
 207                         } else if (high > Q2) break;
 208                         low += low;  high += high;
 209                         value *= 2;
 210                         if ((mask >>= 1) == 0) {
 211                                 buffer = (ip >= srcend) ? 0 : *(ip++);
 212                                 mask = 128;
 213                         }
 214                         value += ((buffer & mask) != 0);
 215                 }
 216                 c = sym_to_char[sym];
 217                 UpdateModel(sym);
 218                 if (c < 256) {
 219                         if (op >= dstend) return -1;
 220                         *(op++) = c;
 221                         text_buf[r++] = c;
 222                         r &= (N - 1);
 223                 } else {
 224                         j = c - 255 + THRESHOLD;
 225                         range = high - low;
 226                         i = BinarySearchPos((unsigned long)
 227                                 (((value - low + 1) * position_cum[0] - 1) / range));
 228                         high = low + (range * position_cum[i    ]) / position_cum[0];
 229                         low +=       (range * position_cum[i + 1]) / position_cum[0];
 230                         for ( ; ; ) {
 231                                 if (low >= Q2) {
 232                                         value -= Q2;  low -= Q2;  high -= Q2;
 233                                 } else if (low >= Q1 && high <= Q3) {
 234                                         value -= Q1;  low -= Q1;  high -= Q1;
 235                                 } else if (high > Q2) break;
 236                                 low += low;  high += high;
 237                                 value *= 2;
 238                                 if ((mask >>= 1) == 0) {
 239                                         buffer = (ip >= srcend) ? 0 : *(ip++);
 240                                         mask = 128;
 241                                 }
 242                                 value += ((buffer & mask) != 0);
 243                         }
 244                         i = (r - i - 1) & (N - 1);
 245                         for (k = 0; k < j; k++) {
 246                                 c = text_buf[(i + k) & (N - 1)];
 247                                 if (op >= dstend) return -1;
 248                                 *(op++) = c;
 249                                 text_buf[r++] = c;
 250                                 r &= (N - 1);
 251                         }
 252                 }
 253         }
 254         return 0;
 255 }
 256
 257 int lzari_decompress(unsigned char *data_in, unsigned char *cpage_out,
 258                       u32 srclen, u32 destlen)
 259 {
 260     return Decode(data_in, cpage_out, srclen, destlen);
 261 }
 262 #endif /* ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI)) */