aboutsummaryrefslogtreecommitdiff
path: root/fs/jffs2/compr_rubin.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/jffs2/compr_rubin.c')
-rw-r--r--fs/jffs2/compr_rubin.c230
1 files changed, 154 insertions, 76 deletions
diff --git a/fs/jffs2/compr_rubin.c b/fs/jffs2/compr_rubin.c
index 09422388fb9..92e0644bf86 100644
--- a/fs/jffs2/compr_rubin.c
+++ b/fs/jffs2/compr_rubin.c
@@ -1,32 +1,104 @@
/*
* JFFS2 -- Journalling Flash File System, Version 2.
*
- * Copyright (C) 2001, 2002 Red Hat, Inc.
+ * Copyright © 2001-2007 Red Hat, Inc.
+ * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
*
* Created by Arjan van de Ven <arjanv@redhat.com>
*
* For licensing information, see the file 'LICENCE' in this directory.
*
- * $Id: compr_rubin.c,v 1.20 2004/06/23 16:34:40 havasi Exp $
- *
*/
-
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
#include <linux/string.h>
#include <linux/types.h>
#include <linux/jffs2.h>
-#include "compr_rubin.h"
-#include "histo_mips.h"
+#include <linux/errno.h>
#include "compr.h"
+
+#define RUBIN_REG_SIZE 16
+#define UPPER_BIT_RUBIN (((long) 1)<<(RUBIN_REG_SIZE-1))
+#define LOWER_BITS_RUBIN ((((long) 1)<<(RUBIN_REG_SIZE-1))-1)
+
+
+#define BIT_DIVIDER_MIPS 1043
+static int bits_mips[8] = { 277, 249, 290, 267, 229, 341, 212, 241};
+
+struct pushpull {
+ unsigned char *buf;
+ unsigned int buflen;
+ unsigned int ofs;
+ unsigned int reserve;
+};
+
+struct rubin_state {
+ unsigned long p;
+ unsigned long q;
+ unsigned long rec_q;
+ long bit_number;
+ struct pushpull pp;
+ int bit_divider;
+ int bits[8];
+};
+
+static inline void init_pushpull(struct pushpull *pp, char *buf,
+ unsigned buflen, unsigned ofs,
+ unsigned reserve)
+{
+ pp->buf = buf;
+ pp->buflen = buflen;
+ pp->ofs = ofs;
+ pp->reserve = reserve;
+}
+
+static inline int pushbit(struct pushpull *pp, int bit, int use_reserved)
+{
+ if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve))
+ return -ENOSPC;
+
+ if (bit)
+ pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs & 7)));
+ else
+ pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs & 7)));
+
+ pp->ofs++;
+
+ return 0;
+}
+
+static inline int pushedbits(struct pushpull *pp)
+{
+ return pp->ofs;
+}
+
+static inline int pullbit(struct pushpull *pp)
+{
+ int bit;
+
+ bit = (pp->buf[pp->ofs >> 3] >> (7-(pp->ofs & 7))) & 1;
+
+ pp->ofs++;
+ return bit;
+}
+
+static inline int pulledbits(struct pushpull *pp)
+{
+ return pp->ofs;
+}
+
+
static void init_rubin(struct rubin_state *rs, int div, int *bits)
-{
+{
int c;
rs->q = 0;
rs->p = (long) (2 * UPPER_BIT_RUBIN);
rs->bit_number = (long) 0;
rs->bit_divider = div;
+
for (c=0; c<8; c++)
rs->bits[c] = bits[c];
}
@@ -38,9 +110,10 @@ static int encode(struct rubin_state *rs, long A, long B, int symbol)
long i0, i1;
int ret;
- while ((rs->q >= UPPER_BIT_RUBIN) || ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
+ while ((rs->q >= UPPER_BIT_RUBIN) ||
+ ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
rs->bit_number++;
-
+
ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
if (ret)
return ret;
@@ -49,12 +122,12 @@ static int encode(struct rubin_state *rs, long A, long B, int symbol)
rs->p <<= 1;
}
i0 = A * rs->p / (A + B);
- if (i0 <= 0) {
+ if (i0 <= 0)
i0 = 1;
- }
- if (i0 >= rs->p) {
+
+ if (i0 >= rs->p)
i0 = rs->p - 1;
- }
+
i1 = rs->p - i0;
if (symbol == 0)
@@ -68,7 +141,7 @@ static int encode(struct rubin_state *rs, long A, long B, int symbol)
static void end_rubin(struct rubin_state *rs)
-{
+{
int i;
@@ -82,16 +155,18 @@ static void end_rubin(struct rubin_state *rs)
static void init_decode(struct rubin_state *rs, int div, int *bits)
{
- init_rubin(rs, div, bits);
+ init_rubin(rs, div, bits);
/* behalve lower */
rs->rec_q = 0;
- for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
+ for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE;
+ rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
;
}
-static void __do_decode(struct rubin_state *rs, unsigned long p, unsigned long q)
+static void __do_decode(struct rubin_state *rs, unsigned long p,
+ unsigned long q)
{
register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
unsigned long rec_q;
@@ -137,12 +212,11 @@ static int decode(struct rubin_state *rs, long A, long B)
__do_decode(rs, p, q);
i0 = A * rs->p / (A + B);
- if (i0 <= 0) {
+ if (i0 <= 0)
i0 = 1;
- }
- if (i0 >= rs->p) {
+
+ if (i0 >= rs->p)
i0 = rs->p - 1;
- }
threshold = rs->q + i0;
symbol = rs->rec_q >= threshold;
@@ -164,14 +238,15 @@ static int out_byte(struct rubin_state *rs, unsigned char byte)
struct rubin_state rs_copy;
rs_copy = *rs;
- for (i=0;i<8;i++) {
- ret = encode(rs, rs->bit_divider-rs->bits[i],rs->bits[i],byte&1);
+ for (i=0; i<8; i++) {
+ ret = encode(rs, rs->bit_divider-rs->bits[i],
+ rs->bits[i], byte & 1);
if (ret) {
/* Failed. Restore old state */
*rs = rs_copy;
return ret;
}
- byte=byte>>1;
+ byte >>= 1 ;
}
return 0;
}
@@ -181,15 +256,17 @@ static int in_byte(struct rubin_state *rs)
int i, result = 0, bit_divider = rs->bit_divider;
for (i = 0; i < 8; i++)
- result |= decode(rs, bit_divider - rs->bits[i], rs->bits[i]) << i;
+ result |= decode(rs, bit_divider - rs->bits[i],
+ rs->bits[i]) << i;
return result;
}
-static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
- unsigned char *cpage_out, uint32_t *sourcelen, uint32_t *dstlen)
+static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
+ unsigned char *cpage_out, uint32_t *sourcelen,
+ uint32_t *dstlen)
{
int outpos = 0;
int pos=0;
@@ -198,40 +275,40 @@ static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
init_rubin(&rs, bit_divider, bits);
-
+
while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
pos++;
-
+
end_rubin(&rs);
if (outpos > pos) {
/* We failed */
return -1;
}
-
- /* Tell the caller how much we managed to compress,
+
+ /* Tell the caller how much we managed to compress,
* and how much space it took */
-
+
outpos = (pushedbits(&rs.pp)+7)/8;
-
+
if (outpos >= pos)
return -1; /* We didn't actually compress */
*sourcelen = pos;
*dstlen = outpos;
return 0;
-}
+}
#if 0
/* _compress returns the compressed size, -1 if bigger */
-int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
- uint32_t *sourcelen, uint32_t *dstlen, void *model)
+int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
+ uint32_t *sourcelen, uint32_t *dstlen)
{
- return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
+ return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in,
+ cpage_out, sourcelen, dstlen);
}
#endif
static int jffs2_dynrubin_compress(unsigned char *data_in,
unsigned char *cpage_out,
- uint32_t *sourcelen, uint32_t *dstlen,
- void *model)
+ uint32_t *sourcelen, uint32_t *dstlen)
{
int bits[8];
unsigned char histo[256];
@@ -246,9 +323,8 @@ static int jffs2_dynrubin_compress(unsigned char *data_in,
return -1;
memset(histo, 0, 256);
- for (i=0; i<mysrclen; i++) {
+ for (i=0; i<mysrclen; i++)
histo[data_in[i]]++;
- }
memset(bits, 0, sizeof(int)*8);
for (i=0; i<256; i++) {
if (i&128)
@@ -276,8 +352,9 @@ static int jffs2_dynrubin_compress(unsigned char *data_in,
cpage_out[i] = bits[i];
}
- ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen);
- if (ret)
+ ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen,
+ &mydstlen);
+ if (ret)
return ret;
/* Add back the 8 bytes we took for the probabilities */
@@ -293,34 +370,34 @@ static int jffs2_dynrubin_compress(unsigned char *data_in,
return 0;
}
-static void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in,
- unsigned char *page_out, uint32_t srclen, uint32_t destlen)
+static void rubin_do_decompress(int bit_divider, int *bits,
+ unsigned char *cdata_in,
+ unsigned char *page_out, uint32_t srclen,
+ uint32_t destlen)
{
int outpos = 0;
struct rubin_state rs;
-
+
init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
init_decode(&rs, bit_divider, bits);
-
- while (outpos < destlen) {
+
+ while (outpos < destlen)
page_out[outpos++] = in_byte(&rs);
- }
-}
+}
static int jffs2_rubinmips_decompress(unsigned char *data_in,
unsigned char *cpage_out,
- uint32_t sourcelen, uint32_t dstlen,
- void *model)
+ uint32_t sourcelen, uint32_t dstlen)
{
- rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen);
- return 0;
+ rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in,
+ cpage_out, sourcelen, dstlen);
+ return 0;
}
static int jffs2_dynrubin_decompress(unsigned char *data_in,
unsigned char *cpage_out,
- uint32_t sourcelen, uint32_t dstlen,
- void *model)
+ uint32_t sourcelen, uint32_t dstlen)
{
int bits[8];
int c;
@@ -328,52 +405,53 @@ static int jffs2_dynrubin_decompress(unsigned char *data_in,
for (c=0; c<8; c++)
bits[c] = data_in[c];
- rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen);
- return 0;
+ rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8,
+ dstlen);
+ return 0;
}
static struct jffs2_compressor jffs2_rubinmips_comp = {
- .priority = JFFS2_RUBINMIPS_PRIORITY,
- .name = "rubinmips",
- .compr = JFFS2_COMPR_DYNRUBIN,
- .compress = NULL, /*&jffs2_rubinmips_compress,*/
- .decompress = &jffs2_rubinmips_decompress,
+ .priority = JFFS2_RUBINMIPS_PRIORITY,
+ .name = "rubinmips",
+ .compr = JFFS2_COMPR_DYNRUBIN,
+ .compress = NULL, /*&jffs2_rubinmips_compress,*/
+ .decompress = &jffs2_rubinmips_decompress,
#ifdef JFFS2_RUBINMIPS_DISABLED
- .disabled = 1,
+ .disabled = 1,
#else
- .disabled = 0,
+ .disabled = 0,
#endif
};
int jffs2_rubinmips_init(void)
{
- return jffs2_register_compressor(&jffs2_rubinmips_comp);
+ return jffs2_register_compressor(&jffs2_rubinmips_comp);
}
void jffs2_rubinmips_exit(void)
{
- jffs2_unregister_compressor(&jffs2_rubinmips_comp);
+ jffs2_unregister_compressor(&jffs2_rubinmips_comp);
}
static struct jffs2_compressor jffs2_dynrubin_comp = {
- .priority = JFFS2_DYNRUBIN_PRIORITY,
- .name = "dynrubin",
- .compr = JFFS2_COMPR_RUBINMIPS,
- .compress = jffs2_dynrubin_compress,
- .decompress = &jffs2_dynrubin_decompress,
+ .priority = JFFS2_DYNRUBIN_PRIORITY,
+ .name = "dynrubin",
+ .compr = JFFS2_COMPR_RUBINMIPS,
+ .compress = jffs2_dynrubin_compress,
+ .decompress = &jffs2_dynrubin_decompress,
#ifdef JFFS2_DYNRUBIN_DISABLED
- .disabled = 1,
+ .disabled = 1,
#else
- .disabled = 0,
+ .disabled = 0,
#endif
};
int jffs2_dynrubin_init(void)
{
- return jffs2_register_compressor(&jffs2_dynrubin_comp);
+ return jffs2_register_compressor(&jffs2_dynrubin_comp);
}
void jffs2_dynrubin_exit(void)
{
- jffs2_unregister_compressor(&jffs2_dynrubin_comp);
+ jffs2_unregister_compressor(&jffs2_dynrubin_comp);
}
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-12-05 20:13:46 +0000