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