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 { 361da177e4SLinus Torvalds short positions[256]; 371da177e4SLinus Torvalds int outpos = 0; 381da177e4SLinus Torvalds int pos=0; 391da177e4SLinus Torvalds 401da177e4SLinus Torvalds memset(positions,0,sizeof(positions)); 411da177e4SLinus Torvalds 421da177e4SLinus Torvalds while (pos < (*sourcelen) && outpos <= (*dstlen)-2) { 431da177e4SLinus Torvalds int backpos, runlen=0; 441da177e4SLinus Torvalds unsigned char value; 451da177e4SLinus Torvalds 461da177e4SLinus Torvalds value = data_in[pos]; 471da177e4SLinus Torvalds 481da177e4SLinus Torvalds cpage_out[outpos++] = data_in[pos++]; 491da177e4SLinus Torvalds 501da177e4SLinus Torvalds backpos = positions[value]; 511da177e4SLinus Torvalds positions[value]=pos; 521da177e4SLinus Torvalds 531da177e4SLinus Torvalds while ((backpos < pos) && (pos < (*sourcelen)) && 541da177e4SLinus Torvalds (data_in[pos]==data_in[backpos++]) && (runlen<255)) { 551da177e4SLinus Torvalds pos++; 561da177e4SLinus Torvalds runlen++; 571da177e4SLinus Torvalds } 581da177e4SLinus Torvalds cpage_out[outpos++] = runlen; 591da177e4SLinus Torvalds } 601da177e4SLinus Torvalds 611da177e4SLinus Torvalds if (outpos >= pos) { 621da177e4SLinus Torvalds /* We failed */ 631da177e4SLinus Torvalds return -1; 641da177e4SLinus Torvalds } 651da177e4SLinus Torvalds 661da177e4SLinus Torvalds /* Tell the caller how much we managed to compress, and how much space it took */ 671da177e4SLinus Torvalds *sourcelen = pos; 681da177e4SLinus Torvalds *dstlen = outpos; 691da177e4SLinus Torvalds return 0; 701da177e4SLinus Torvalds } 711da177e4SLinus Torvalds 721da177e4SLinus Torvalds 731da177e4SLinus Torvalds static int jffs2_rtime_decompress(unsigned char *data_in, 741da177e4SLinus Torvalds unsigned char *cpage_out, 75088bd455SMike Frysinger uint32_t srclen, uint32_t destlen) 761da177e4SLinus Torvalds { 771da177e4SLinus Torvalds short positions[256]; 781da177e4SLinus Torvalds int outpos = 0; 791da177e4SLinus Torvalds int pos=0; 801da177e4SLinus Torvalds 811da177e4SLinus Torvalds memset(positions,0,sizeof(positions)); 821da177e4SLinus Torvalds 831da177e4SLinus Torvalds while (outpos<destlen) { 841da177e4SLinus Torvalds unsigned char value; 851da177e4SLinus Torvalds int backoffs; 861da177e4SLinus Torvalds int repeat; 871da177e4SLinus Torvalds 881da177e4SLinus Torvalds value = data_in[pos++]; 891da177e4SLinus Torvalds cpage_out[outpos++] = value; /* first the verbatim copied byte */ 901da177e4SLinus Torvalds repeat = data_in[pos++]; 911da177e4SLinus Torvalds backoffs = positions[value]; 921da177e4SLinus Torvalds 931da177e4SLinus Torvalds positions[value]=outpos; 941da177e4SLinus Torvalds if (repeat) { 951da177e4SLinus Torvalds if (backoffs + repeat >= outpos) { 961da177e4SLinus Torvalds while(repeat) { 971da177e4SLinus Torvalds cpage_out[outpos++] = cpage_out[backoffs++]; 981da177e4SLinus Torvalds repeat--; 991da177e4SLinus Torvalds } 1001da177e4SLinus Torvalds } else { 1011da177e4SLinus Torvalds memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat); 1021da177e4SLinus Torvalds outpos+=repeat; 1031da177e4SLinus Torvalds } 1041da177e4SLinus Torvalds } 1051da177e4SLinus Torvalds } 1061da177e4SLinus Torvalds return 0; 1071da177e4SLinus Torvalds } 1081da177e4SLinus Torvalds 1091da177e4SLinus Torvalds static struct jffs2_compressor jffs2_rtime_comp = { 1101da177e4SLinus Torvalds .priority = JFFS2_RTIME_PRIORITY, 1111da177e4SLinus Torvalds .name = "rtime", 1121da177e4SLinus Torvalds .compr = JFFS2_COMPR_RTIME, 1131da177e4SLinus Torvalds .compress = &jffs2_rtime_compress, 1141da177e4SLinus Torvalds .decompress = &jffs2_rtime_decompress, 1151da177e4SLinus Torvalds #ifdef JFFS2_RTIME_DISABLED 1161da177e4SLinus Torvalds .disabled = 1, 1171da177e4SLinus Torvalds #else 1181da177e4SLinus Torvalds .disabled = 0, 1191da177e4SLinus Torvalds #endif 1201da177e4SLinus Torvalds }; 1211da177e4SLinus Torvalds 1221da177e4SLinus Torvalds int jffs2_rtime_init(void) 1231da177e4SLinus Torvalds { 1241da177e4SLinus Torvalds return jffs2_register_compressor(&jffs2_rtime_comp); 1251da177e4SLinus Torvalds } 1261da177e4SLinus Torvalds 1271da177e4SLinus Torvalds void jffs2_rtime_exit(void) 1281da177e4SLinus Torvalds { 1291da177e4SLinus Torvalds jffs2_unregister_compressor(&jffs2_rtime_comp); 1301da177e4SLinus Torvalds } 131