~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/jffs2/compr_rubin.c

Version: ~ [ linux-5.6-rc1 ] ~ [ linux-5.5.2 ] ~ [ linux-5.4.17 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.102 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.170 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.213 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.213 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.81 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  * JFFS2 -- Journalling Flash File System, Version 2.
  3  *
  4  * Copyright © 2001-2007 Red Hat, Inc.
  5  * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
  6  *
  7  * Created by Arjan van de Ven <arjanv@redhat.com>
  8  *
  9  * For licensing information, see the file 'LICENCE' in this directory.
 10  *
 11  */
 12 
 13 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
 14 
 15 #include <linux/string.h>
 16 #include <linux/types.h>
 17 #include <linux/jffs2.h>
 18 #include <linux/errno.h>
 19 #include "compr.h"
 20 
 21 
 22 #define RUBIN_REG_SIZE   16
 23 #define UPPER_BIT_RUBIN    (((long) 1)<<(RUBIN_REG_SIZE-1))
 24 #define LOWER_BITS_RUBIN   ((((long) 1)<<(RUBIN_REG_SIZE-1))-1)
 25 
 26 
 27 #define BIT_DIVIDER_MIPS 1043
 28 static int bits_mips[8] = { 277, 249, 290, 267, 229, 341, 212, 241};
 29 
 30 struct pushpull {
 31         unsigned char *buf;
 32         unsigned int buflen;
 33         unsigned int ofs;
 34         unsigned int reserve;
 35 };
 36 
 37 struct rubin_state {
 38         unsigned long p;
 39         unsigned long q;
 40         unsigned long rec_q;
 41         long bit_number;
 42         struct pushpull pp;
 43         int bit_divider;
 44         int bits[8];
 45 };
 46 
 47 static inline void init_pushpull(struct pushpull *pp, char *buf,
 48                                  unsigned buflen, unsigned ofs,
 49                                  unsigned reserve)
 50 {
 51         pp->buf = buf;
 52         pp->buflen = buflen;
 53         pp->ofs = ofs;
 54         pp->reserve = reserve;
 55 }
 56 
 57 static inline int pushbit(struct pushpull *pp, int bit, int use_reserved)
 58 {
 59         if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve))
 60                 return -ENOSPC;
 61 
 62         if (bit)
 63                 pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs & 7)));
 64         else
 65                 pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs & 7)));
 66 
 67         pp->ofs++;
 68 
 69         return 0;
 70 }
 71 
 72 static inline int pushedbits(struct pushpull *pp)
 73 {
 74         return pp->ofs;
 75 }
 76 
 77 static inline int pullbit(struct pushpull *pp)
 78 {
 79         int bit;
 80 
 81         bit = (pp->buf[pp->ofs >> 3] >> (7-(pp->ofs & 7))) & 1;
 82 
 83         pp->ofs++;
 84         return bit;
 85 }
 86 
 87 
 88 static void init_rubin(struct rubin_state *rs, int div, int *bits)
 89 {
 90         int c;
 91 
 92         rs->q = 0;
 93         rs->p = (long) (2 * UPPER_BIT_RUBIN);
 94         rs->bit_number = (long) 0;
 95         rs->bit_divider = div;
 96 
 97         for (c=0; c<8; c++)
 98                 rs->bits[c] = bits[c];
 99 }
100 
101 
102 static int encode(struct rubin_state *rs, long A, long B, int symbol)
103 {
104 
105         long i0, i1;
106         int ret;
107 
108         while ((rs->q >= UPPER_BIT_RUBIN) ||
109                ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
110                 rs->bit_number++;
111 
112                 ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
113                 if (ret)
114                         return ret;
115                 rs->q &= LOWER_BITS_RUBIN;
116                 rs->q <<= 1;
117                 rs->p <<= 1;
118         }
119         i0 = A * rs->p / (A + B);
120         if (i0 <= 0)
121                 i0 = 1;
122 
123         if (i0 >= rs->p)
124                 i0 = rs->p - 1;
125 
126         i1 = rs->p - i0;
127 
128         if (symbol == 0)
129                 rs->p = i0;
130         else {
131                 rs->p = i1;
132                 rs->q += i0;
133         }
134         return 0;
135 }
136 
137 
138 static void end_rubin(struct rubin_state *rs)
139 {
140 
141         int i;
142 
143         for (i = 0; i < RUBIN_REG_SIZE; i++) {
144                 pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);
145                 rs->q &= LOWER_BITS_RUBIN;
146                 rs->q <<= 1;
147         }
148 }
149 
150 
151 static void init_decode(struct rubin_state *rs, int div, int *bits)
152 {
153         init_rubin(rs, div, bits);
154 
155         /* behalve lower */
156         rs->rec_q = 0;
157 
158         for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE;
159              rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
160                 ;
161 }
162 
163 static void __do_decode(struct rubin_state *rs, unsigned long p,
164                         unsigned long q)
165 {
166         register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
167         unsigned long rec_q;
168         int c, bits = 0;
169 
170         /*
171          * First, work out how many bits we need from the input stream.
172          * Note that we have already done the initial check on this
173          * loop prior to calling this function.
174          */
175         do {
176                 bits++;
177                 q &= lower_bits_rubin;
178                 q <<= 1;
179                 p <<= 1;
180         } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
181 
182         rs->p = p;
183         rs->q = q;
184 
185         rs->bit_number += bits;
186 
187         /*
188          * Now get the bits.  We really want this to be "get n bits".
189          */
190         rec_q = rs->rec_q;
191         do {
192                 c = pullbit(&rs->pp);
193                 rec_q &= lower_bits_rubin;
194                 rec_q <<= 1;
195                 rec_q += c;
196         } while (--bits);
197         rs->rec_q = rec_q;
198 }
199 
200 static int decode(struct rubin_state *rs, long A, long B)
201 {
202         unsigned long p = rs->p, q = rs->q;
203         long i0, threshold;
204         int symbol;
205 
206         if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN))
207                 __do_decode(rs, p, q);
208 
209         i0 = A * rs->p / (A + B);
210         if (i0 <= 0)
211                 i0 = 1;
212 
213         if (i0 >= rs->p)
214                 i0 = rs->p - 1;
215 
216         threshold = rs->q + i0;
217         symbol = rs->rec_q >= threshold;
218         if (rs->rec_q >= threshold) {
219                 rs->q += i0;
220                 i0 = rs->p - i0;
221         }
222 
223         rs->p = i0;
224 
225         return symbol;
226 }
227 
228 
229 
230 static int out_byte(struct rubin_state *rs, unsigned char byte)
231 {
232         int i, ret;
233         struct rubin_state rs_copy;
234         rs_copy = *rs;
235 
236         for (i=0; i<8; i++) {
237                 ret = encode(rs, rs->bit_divider-rs->bits[i],
238                              rs->bits[i], byte & 1);
239                 if (ret) {
240                         /* Failed. Restore old state */
241                         *rs = rs_copy;
242                         return ret;
243                 }
244                 byte >>= 1 ;
245         }
246         return 0;
247 }
248 
249 static int in_byte(struct rubin_state *rs)
250 {
251         int i, result = 0, bit_divider = rs->bit_divider;
252 
253         for (i = 0; i < 8; i++)
254                 result |= decode(rs, bit_divider - rs->bits[i],
255                                  rs->bits[i]) << i;
256 
257         return result;
258 }
259 
260 
261 
262 static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
263                              unsigned char *cpage_out, uint32_t *sourcelen,
264                              uint32_t *dstlen)
265         {
266         int outpos = 0;
267         int pos=0;
268         struct rubin_state rs;
269 
270         init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
271 
272         init_rubin(&rs, bit_divider, bits);
273 
274         while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
275                 pos++;
276 
277         end_rubin(&rs);
278 
279         if (outpos > pos) {
280                 /* We failed */
281                 return -1;
282         }
283 
284         /* Tell the caller how much we managed to compress,
285          * and how much space it took */
286 
287         outpos = (pushedbits(&rs.pp)+7)/8;
288 
289         if (outpos >= pos)
290                 return -1; /* We didn't actually compress */
291         *sourcelen = pos;
292         *dstlen = outpos;
293         return 0;
294 }
295 #if 0
296 /* _compress returns the compressed size, -1 if bigger */
297 int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
298                    uint32_t *sourcelen, uint32_t *dstlen)
299 {
300         return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in,
301                                  cpage_out, sourcelen, dstlen);
302 }
303 #endif
304 static int jffs2_dynrubin_compress(unsigned char *data_in,
305                                    unsigned char *cpage_out,
306                                    uint32_t *sourcelen, uint32_t *dstlen)
307 {
308         int bits[8];
309         unsigned char histo[256];
310         int i;
311         int ret;
312         uint32_t mysrclen, mydstlen;
313 
314         mysrclen = *sourcelen;
315         mydstlen = *dstlen - 8;
316 
317         if (*dstlen <= 12)
318                 return -1;
319 
320         memset(histo, 0, 256);
321         for (i=0; i<mysrclen; i++)
322                 histo[data_in[i]]++;
323         memset(bits, 0, sizeof(int)*8);
324         for (i=0; i<256; i++) {
325                 if (i&128)
326                         bits[7] += histo[i];
327                 if (i&64)
328                         bits[6] += histo[i];
329                 if (i&32)
330                         bits[5] += histo[i];
331                 if (i&16)
332                         bits[4] += histo[i];
333                 if (i&8)
334                         bits[3] += histo[i];
335                 if (i&4)
336                         bits[2] += histo[i];
337                 if (i&2)
338                         bits[1] += histo[i];
339                 if (i&1)
340                         bits[0] += histo[i];
341         }
342 
343         for (i=0; i<8; i++) {
344                 bits[i] = (bits[i] * 256) / mysrclen;
345                 if (!bits[i]) bits[i] = 1;
346                 if (bits[i] > 255) bits[i] = 255;
347                 cpage_out[i] = bits[i];
348         }
349 
350         ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen,
351                                 &mydstlen);
352         if (ret)
353                 return ret;
354 
355         /* Add back the 8 bytes we took for the probabilities */
356         mydstlen += 8;
357 
358         if (mysrclen <= mydstlen) {
359                 /* We compressed */
360                 return -1;
361         }
362 
363         *sourcelen = mysrclen;
364         *dstlen = mydstlen;
365         return 0;
366 }
367 
368 static void rubin_do_decompress(int bit_divider, int *bits,
369                                 unsigned char *cdata_in, 
370                                 unsigned char *page_out, uint32_t srclen,
371                                 uint32_t destlen)
372 {
373         int outpos = 0;
374         struct rubin_state rs;
375 
376         init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
377         init_decode(&rs, bit_divider, bits);
378 
379         while (outpos < destlen)
380                 page_out[outpos++] = in_byte(&rs);
381 }
382 
383 
384 static int jffs2_rubinmips_decompress(unsigned char *data_in,
385                                       unsigned char *cpage_out,
386                                       uint32_t sourcelen, uint32_t dstlen)
387 {
388         rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in,
389                             cpage_out, sourcelen, dstlen);
390         return 0;
391 }
392 
393 static int jffs2_dynrubin_decompress(unsigned char *data_in,
394                                      unsigned char *cpage_out,
395                                      uint32_t sourcelen, uint32_t dstlen)
396 {
397         int bits[8];
398         int c;
399 
400         for (c=0; c<8; c++)
401                 bits[c] = data_in[c];
402 
403         rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8,
404                             dstlen);
405         return 0;
406 }
407 
408 static struct jffs2_compressor jffs2_rubinmips_comp = {
409         .priority = JFFS2_RUBINMIPS_PRIORITY,
410         .name = "rubinmips",
411         .compr = JFFS2_COMPR_DYNRUBIN,
412         .compress = NULL, /*&jffs2_rubinmips_compress,*/
413         .decompress = &jffs2_rubinmips_decompress,
414 #ifdef JFFS2_RUBINMIPS_DISABLED
415         .disabled = 1,
416 #else
417         .disabled = 0,
418 #endif
419 };
420 
421 int jffs2_rubinmips_init(void)
422 {
423         return jffs2_register_compressor(&jffs2_rubinmips_comp);
424 }
425 
426 void jffs2_rubinmips_exit(void)
427 {
428         jffs2_unregister_compressor(&jffs2_rubinmips_comp);
429 }
430 
431 static struct jffs2_compressor jffs2_dynrubin_comp = {
432         .priority = JFFS2_DYNRUBIN_PRIORITY,
433         .name = "dynrubin",
434         .compr = JFFS2_COMPR_RUBINMIPS,
435         .compress = jffs2_dynrubin_compress,
436         .decompress = &jffs2_dynrubin_decompress,
437 #ifdef JFFS2_DYNRUBIN_DISABLED
438         .disabled = 1,
439 #else
440         .disabled = 0,
441 #endif
442 };
443 
444 int jffs2_dynrubin_init(void)
445 {
446         return jffs2_register_compressor(&jffs2_dynrubin_comp);
447 }
448 
449 void jffs2_dynrubin_exit(void)
450 {
451         jffs2_unregister_compressor(&jffs2_dynrubin_comp);
452 }
453 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp