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 */ 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 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 1251da177e4SLinus Torvalds int jffs2_rtime_init(void) 1261da177e4SLinus Torvalds { 1271da177e4SLinus Torvalds return jffs2_register_compressor(&jffs2_rtime_comp); 1281da177e4SLinus Torvalds } 1291da177e4SLinus Torvalds 1301da177e4SLinus Torvalds void jffs2_rtime_exit(void) 1311da177e4SLinus Torvalds { 1321da177e4SLinus Torvalds jffs2_unregister_compressor(&jffs2_rtime_comp); 1331da177e4SLinus Torvalds } 134