11da177e4SLinus Torvalds /*
21da177e4SLinus Torvalds * JFFS2 -- Journalling Flash File System, Version 2.
31da177e4SLinus Torvalds *
4c00c310eSDavid Woodhouse * Copyright © 2001-2007 Red Hat, Inc.
56088c058SDavid Woodhouse * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
61da177e4SLinus Torvalds *
71da177e4SLinus Torvalds * Created by Arjan van de Ven <arjanv@redhat.com>
81da177e4SLinus Torvalds *
91da177e4SLinus Torvalds * For licensing information, see the file 'LICENCE' in this directory.
101da177e4SLinus Torvalds *
111da177e4SLinus Torvalds *
121da177e4SLinus Torvalds *
131da177e4SLinus Torvalds * Very simple lz77-ish encoder.
141da177e4SLinus Torvalds *
151da177e4SLinus Torvalds * Theory of operation: Both encoder and decoder have a list of "last
161da177e4SLinus Torvalds * occurrences" for every possible source-value; after sending the
171da177e4SLinus Torvalds * first source-byte, the second byte indicated the "run" length of
181da177e4SLinus Torvalds * matches
191da177e4SLinus Torvalds *
201da177e4SLinus Torvalds * The algorithm is intended to only send "whole bytes", no bit-messing.
211da177e4SLinus Torvalds *
221da177e4SLinus Torvalds */
231da177e4SLinus Torvalds
241da177e4SLinus Torvalds #include <linux/kernel.h>
251da177e4SLinus Torvalds #include <linux/types.h>
261da177e4SLinus Torvalds #include <linux/errno.h>
271da177e4SLinus Torvalds #include <linux/string.h>
281da177e4SLinus Torvalds #include <linux/jffs2.h>
291da177e4SLinus Torvalds #include "compr.h"
301da177e4SLinus Torvalds
311da177e4SLinus Torvalds /* _compress returns the compressed size, -1 if bigger */
jffs2_rtime_compress(unsigned char * data_in,unsigned char * cpage_out,uint32_t * sourcelen,uint32_t * dstlen)321da177e4SLinus Torvalds static int jffs2_rtime_compress(unsigned char *data_in,
331da177e4SLinus Torvalds unsigned char *cpage_out,
34088bd455SMike Frysinger uint32_t *sourcelen, uint32_t *dstlen)
351da177e4SLinus Torvalds {
363367da56SKamlakant Patel unsigned short positions[256];
371da177e4SLinus Torvalds int outpos = 0;
381da177e4SLinus Torvalds int pos=0;
391da177e4SLinus Torvalds
40*90ada91fSYang Yang if (*dstlen <= 3)
41*90ada91fSYang Yang return -1;
42*90ada91fSYang Yang
431da177e4SLinus Torvalds memset(positions,0,sizeof(positions));
441da177e4SLinus Torvalds
451da177e4SLinus Torvalds while (pos < (*sourcelen) && outpos <= (*dstlen)-2) {
461da177e4SLinus Torvalds int backpos, runlen=0;
471da177e4SLinus Torvalds unsigned char value;
481da177e4SLinus Torvalds
491da177e4SLinus Torvalds value = data_in[pos];
501da177e4SLinus Torvalds
511da177e4SLinus Torvalds cpage_out[outpos++] = data_in[pos++];
521da177e4SLinus Torvalds
531da177e4SLinus Torvalds backpos = positions[value];
541da177e4SLinus Torvalds positions[value]=pos;
551da177e4SLinus Torvalds
561da177e4SLinus Torvalds while ((backpos < pos) && (pos < (*sourcelen)) &&
571da177e4SLinus Torvalds (data_in[pos]==data_in[backpos++]) && (runlen<255)) {
581da177e4SLinus Torvalds pos++;
591da177e4SLinus Torvalds runlen++;
601da177e4SLinus Torvalds }
611da177e4SLinus Torvalds cpage_out[outpos++] = runlen;
621da177e4SLinus Torvalds }
631da177e4SLinus Torvalds
641da177e4SLinus Torvalds if (outpos >= pos) {
651da177e4SLinus Torvalds /* We failed */
661da177e4SLinus Torvalds return -1;
671da177e4SLinus Torvalds }
681da177e4SLinus Torvalds
691da177e4SLinus Torvalds /* Tell the caller how much we managed to compress, and how much space it took */
701da177e4SLinus Torvalds *sourcelen = pos;
711da177e4SLinus Torvalds *dstlen = outpos;
721da177e4SLinus Torvalds return 0;
731da177e4SLinus Torvalds }
741da177e4SLinus Torvalds
751da177e4SLinus Torvalds
jffs2_rtime_decompress(unsigned char * data_in,unsigned char * cpage_out,uint32_t srclen,uint32_t destlen)761da177e4SLinus Torvalds static int jffs2_rtime_decompress(unsigned char *data_in,
771da177e4SLinus Torvalds unsigned char *cpage_out,
78088bd455SMike Frysinger uint32_t srclen, uint32_t destlen)
791da177e4SLinus Torvalds {
803367da56SKamlakant Patel unsigned short positions[256];
811da177e4SLinus Torvalds int outpos = 0;
821da177e4SLinus Torvalds int pos=0;
831da177e4SLinus Torvalds
841da177e4SLinus Torvalds memset(positions,0,sizeof(positions));
851da177e4SLinus Torvalds
861da177e4SLinus Torvalds while (outpos<destlen) {
871da177e4SLinus Torvalds unsigned char value;
881da177e4SLinus Torvalds int backoffs;
891da177e4SLinus Torvalds int repeat;
901da177e4SLinus Torvalds
911da177e4SLinus Torvalds value = data_in[pos++];
921da177e4SLinus Torvalds cpage_out[outpos++] = value; /* first the verbatim copied byte */
931da177e4SLinus Torvalds repeat = data_in[pos++];
941da177e4SLinus Torvalds backoffs = positions[value];
951da177e4SLinus Torvalds
961da177e4SLinus Torvalds positions[value]=outpos;
971da177e4SLinus Torvalds if (repeat) {
981da177e4SLinus Torvalds if (backoffs + repeat >= outpos) {
991da177e4SLinus Torvalds while(repeat) {
1001da177e4SLinus Torvalds cpage_out[outpos++] = cpage_out[backoffs++];
1011da177e4SLinus Torvalds repeat--;
1021da177e4SLinus Torvalds }
1031da177e4SLinus Torvalds } else {
1041da177e4SLinus Torvalds memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat);
1051da177e4SLinus Torvalds outpos+=repeat;
1061da177e4SLinus Torvalds }
1071da177e4SLinus Torvalds }
1081da177e4SLinus Torvalds }
1091da177e4SLinus Torvalds return 0;
1101da177e4SLinus Torvalds }
1111da177e4SLinus Torvalds
1121da177e4SLinus Torvalds static struct jffs2_compressor jffs2_rtime_comp = {
1131da177e4SLinus Torvalds .priority = JFFS2_RTIME_PRIORITY,
1141da177e4SLinus Torvalds .name = "rtime",
1151da177e4SLinus Torvalds .compr = JFFS2_COMPR_RTIME,
1161da177e4SLinus Torvalds .compress = &jffs2_rtime_compress,
1171da177e4SLinus Torvalds .decompress = &jffs2_rtime_decompress,
1181da177e4SLinus Torvalds #ifdef JFFS2_RTIME_DISABLED
1191da177e4SLinus Torvalds .disabled = 1,
1201da177e4SLinus Torvalds #else
1211da177e4SLinus Torvalds .disabled = 0,
1221da177e4SLinus Torvalds #endif
1231da177e4SLinus Torvalds };
1241da177e4SLinus Torvalds
jffs2_rtime_init(void)1251da177e4SLinus Torvalds int jffs2_rtime_init(void)
1261da177e4SLinus Torvalds {
1271da177e4SLinus Torvalds return jffs2_register_compressor(&jffs2_rtime_comp);
1281da177e4SLinus Torvalds }
1291da177e4SLinus Torvalds
jffs2_rtime_exit(void)1301da177e4SLinus Torvalds void jffs2_rtime_exit(void)
1311da177e4SLinus Torvalds {
1321da177e4SLinus Torvalds jffs2_unregister_compressor(&jffs2_rtime_comp);
1331da177e4SLinus Torvalds }
134