embox
1/*
2* JFFS2 -- Journalling Flash File System, Version 2.
3*
4* Copyright (C) 2001-2003 Red Hat, Inc.
5*
6* Created by Arjan van de Ven <arjanv@redhat.com>
7*
8* For licensing information, see the file 'LICENCE' in this directory.
9*
10* $Id: compr_rtime.c,v 1.15 2005/03/17 20:23:06 gleixner Exp $
11*
12*
13* Very simple lz77-ish encoder.
14*
15* Theory of operation: Both encoder and decoder have a list of "last
16* occurrences" for every possible source-value; after sending the
17* first source-byte, the second byte indicated the "run" length of
18* matches
19*
20* The algorithm is intended to only send "whole bytes", no bit-messing.
21*
22*/
23
24#include <linux/kernel.h>25#include <linux/types.h>26#include <linux/errno.h>27#include <linux/string.h>28#include <fs/jffs2.h>29#include "compr.h"30
31/* _compress returns the compressed size, -1 if bigger */
32static int jffs2_rtime_compress(unsigned char *data_in,33unsigned char *cpage_out,uint32_t *sourcelen,34uint32_t *dstlen, void *model) {35short positions[256];36int outpos = 0;37int pos=0;38
39memset(positions,0,sizeof(positions));40
41while (pos < (*sourcelen) && outpos <= (*dstlen)-2) {42int backpos, runlen=0;43unsigned char value;44
45value = data_in[pos];46
47cpage_out[outpos++] = data_in[pos++];48
49backpos = positions[value];50positions[value]=pos;51
52while ((backpos < pos) && (pos < (*sourcelen)) &&53(data_in[pos]==data_in[backpos++]) && (runlen<255)) {54pos++;55runlen++;56}57cpage_out[outpos++] = runlen;58}59
60if (outpos >= pos) {61/* We failed */62return -1;63}64
65/* Tell the caller how much we managed to compress, and how much space it took */66*sourcelen = pos;67*dstlen = outpos;68return 0;69}
70
71
72static int jffs2_rtime_decompress(unsigned char *data_in,73unsigned char *cpage_out,74uint32_t srclen, uint32_t destlen,75void *model) {76short positions[256];77int outpos = 0;78int pos=0;79
80memset(positions,0,sizeof(positions));81
82while (outpos<destlen) {83unsigned char value;84int backoffs;85int repeat;86
87value = data_in[pos++];88cpage_out[outpos++] = value; /* first the verbatim copied byte */89repeat = data_in[pos++];90backoffs = positions[value];91
92positions[value]=outpos;93if (repeat) {94if (backoffs + repeat >= outpos) {95while(repeat) {96cpage_out[outpos++] = cpage_out[backoffs++];97repeat--;98}99} else {100memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat);101outpos+=repeat;102}103}104}105return 0;106}
107
108static struct jffs2_compressor jffs2_rtime_comp = {109.priority = JFFS2_RTIME_PRIORITY,110.name = "rtime",111.compr = JFFS2_COMPR_RTIME,112.compress = &jffs2_rtime_compress,113.decompress = &jffs2_rtime_decompress,114#ifdef JFFS2_RTIME_DISABLED115.disabled = 1,116#else117.disabled = 0,118#endif119};120
121int jffs2_rtime_init(void) {122return jffs2_register_compressor(&jffs2_rtime_comp);123}
124
125void jffs2_rtime_exit(void) {126jffs2_unregister_compressor(&jffs2_rtime_comp);127}
128