]>
git.ipfire.org Git - people/ms/u-boot.git/blob - fs/jffs2/compr_lzari.c
2 * JFFS2 -- Journalling Flash File System, Version 2.
4 * Copyright (C) 2004 Patrik Kluba,
5 * University of Szeged, Hungary
7 * For licensing information, see the file 'LICENCE' in the
10 * $Id: compr_lzari.c,v 1.3 2004/06/23 16:34:39 havasi Exp $
15 Lempel-Ziv-Arithmetic coding compression module for jffs2
16 Based on the LZARI source included in LDS (lossless datacompression sources)
19 /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
22 Original copyright follows:
24 **************************************************************
25 LZARI.C -- A Data Compression Program
27 **************************************************************
28 4/7/1989 Haruhiko Okumura
29 Use, distribute, and modify this program freely.
30 Please send me your improved versions.
34 **************************************************************
36 LZARI.C (c)1989 by Haruyasu Yoshizaki, Haruhiko Okumura, and Kenji Rikitake.
37 All rights reserved. Permission granted for non-commercial use.
43 2004-02-18 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
44 Removed unused variables and fixed no return value
46 2004-02-16 pajko <pajko(AT)halom(DOT)u-szeged(DOT)hu>
53 #if ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI))
55 #include <linux/stddef.h>
56 #include <jffs2/jffs2.h>
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 */
66 text_buf
[N
+ F
- 1]; /* ring buffer of size N,
67 with extra F-1 bytes to facilitate string comparison */
69 /********** Arithmetic Compression **********/
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. */
78 /* Q1 (= 2 to the M) must be sufficiently large, but not so
79 large as the unsigned long 4 * Q1 * (Q1 - 1) overflows. */
85 #define MAX_CUM (Q1 - 1)
87 #define N_CHAR (256 - THRESHOLD + F)
88 /* character code = 0, 1, ..., N_CHAR - 1 */
90 static unsigned long char_to_sym
[N_CHAR
], sym_to_char
[N_CHAR
+ 1];
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 */
96 static void StartModel(void) /* Initialize model */
98 unsigned long ch
, sym
, i
;
101 for (sym
= N_CHAR
; sym
>= 1; sym
--) {
103 char_to_sym
[ch
] = sym
; sym_to_char
[sym
] = ch
;
105 sym_cum
[sym
- 1] = sym_cum
[sym
] + sym_freq
[sym
];
107 sym_freq
[0] = 0; /* sentinel (!= sym_freq[1]) */
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! */
115 static void UpdateModel(unsigned long sym
)
117 unsigned long c
, ch_i
, ch_sym
;
119 if (sym_cum
[0] >= MAX_CUM
) {
121 for (i
= N_CHAR
; i
> 0; i
--) {
123 c
+= (sym_freq
[i
] = (sym_freq
[i
] + 1) >> 1);
127 for (i
= sym
; sym_freq
[i
] == sym_freq
[i
- 1]; i
--) ;
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
;
134 while (--i
> 0) sym_cum
[i
]++;
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 */
143 unsigned long i
, j
, k
;
148 if (sym_cum
[k
] > x
) i
= k
+ 1; else j
= k
;
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 */
158 unsigned long i
, j
, k
;
163 if (position_cum
[k
] > x
) i
= k
+ 1; else j
= k
;
168 static int Decode(unsigned char *srcbuf
, unsigned char *dstbuf
, unsigned long srclen
,
169 unsigned long dstlen
) /* Just the reverse of Encode(). */
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;
183 for (i
= 0; i
< M
+ 2; i
++) {
185 if ((mask
>>= 1) == 0) {
186 buffer
= (ip
>= srcend
) ? 0 : *(ip
++);
189 value
+= ((buffer
& mask
) != 0);
193 for (i
= 0; i
< N
- F
; i
++) text_buf
[i
] = ' ';
196 while (op
< dstend
) {
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];
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
;
210 if ((mask
>>= 1) == 0) {
211 buffer
= (ip
>= srcend
) ? 0 : *(ip
++);
214 value
+= ((buffer
& mask
) != 0);
216 c
= sym_to_char
[sym
];
219 if (op
>= dstend
) return -1;
224 j
= c
- 255 + THRESHOLD
;
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];
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
;
238 if ((mask
>>= 1) == 0) {
239 buffer
= (ip
>= srcend
) ? 0 : *(ip
++);
242 value
+= ((buffer
& mask
) != 0);
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;
257 int lzari_decompress(unsigned char *data_in
, unsigned char *cpage_out
,
258 u32 srclen
, u32 destlen
)
260 return Decode(data_in
, cpage_out
, srclen
, destlen
);
262 #endif /* ((CONFIG_COMMANDS & CFG_CMD_JFFS2) && defined(CONFIG_JFFS2_LZO_LZARI)) */