fs/jffs2/compr_rtime.c

0001 /*
0002  * JFFS2 -- Journalling Flash File System, Version 2.
0003  *
0004  * Copyright © 2001-2007 Red Hat, Inc.
0005  * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
0006  *
0007  * Created by Arjan van de Ven <arjanv@redhat.com>
0008  *
0009  * For licensing information, see the file 'LICENCE' in this directory.
0010  *
0011  *
0012  *
0013  * Very simple lz77-ish encoder.
0014  *
0015  * Theory of operation: Both encoder and decoder have a list of "last
0016  * occurrences" for every possible source-value; after sending the
0017  * first source-byte, the second byte indicated the "run" length of
0018  * matches
0019  *
0020  * The algorithm is intended to only send "whole bytes", no bit-messing.
0021  *
0022  */
0023
0024 #include <linux/kernel.h>
0025 #include <linux/types.h>
0026 #include <linux/errno.h>
0027 #include <linux/string.h>
0028 #include <linux/jffs2.h>
0029 #include "compr.h"
0030
0031 /* _compress returns the compressed size, -1 if bigger */
0032 static int jffs2_rtime_compress(unsigned char *data_in,
0033                 unsigned char *cpage_out,
0034                 uint32_t *sourcelen, uint32_t *dstlen)
0035 {
0036     unsigned short positions[256];
0037     int outpos = 0;
0038     int pos=0;
0039
0040     if (*dstlen <= 3)
0041         return -1;
0042
0043     memset(positions,0,sizeof(positions));
0044
0045     while (pos < (*sourcelen) && outpos <= (*dstlen)-2) {
0046         int backpos, runlen=0;
0047         unsigned char value;
0048
0049         value = data_in[pos];
0050
0051         cpage_out[outpos++] = data_in[pos++];
0052
0053         backpos = positions[value];
0054         positions[value]=pos;
0055
0056         while ((backpos < pos) && (pos < (*sourcelen)) &&
0057                (data_in[pos]==data_in[backpos++]) && (runlen<255)) {
0058             pos++;
0059             runlen++;
0060         }
0061         cpage_out[outpos++] = runlen;
0062     }
0063
0064     if (outpos >= pos) {
0065         /* We failed */
0066         return -1;
0067     }
0068
0069     /* Tell the caller how much we managed to compress, and how much space it took */
0070     *sourcelen = pos;
0071     *dstlen = outpos;
0072     return 0;
0073 }
0074
0075
0076 static int jffs2_rtime_decompress(unsigned char *data_in,
0077                   unsigned char *cpage_out,
0078                   uint32_t srclen, uint32_t destlen)
0079 {
0080     unsigned short positions[256];
0081     int outpos = 0;
0082     int pos=0;
0083
0084     memset(positions,0,sizeof(positions));
0085
0086     while (outpos<destlen) {
0087         unsigned char value;
0088         int backoffs;
0089         int repeat;
0090
0091         value = data_in[pos++];
0092         cpage_out[outpos++] = value; /* first the verbatim copied byte */
0093         repeat = data_in[pos++];
0094         backoffs = positions[value];
0095
0096         positions[value]=outpos;
0097         if (repeat) {
0098             if (backoffs + repeat >= outpos) {
0099                 while(repeat) {
0100                     cpage_out[outpos++] = cpage_out[backoffs++];
0101                     repeat--;
0102                 }
0103             } else {
0104                 memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat);
0105                 outpos+=repeat;
0106             }
0107         }
0108     }
0109     return 0;
0110 }
0111
0112 static struct jffs2_compressor jffs2_rtime_comp = {
0113     .priority = JFFS2_RTIME_PRIORITY,
0114     .name = "rtime",
0115     .compr = JFFS2_COMPR_RTIME,
0116     .compress = &jffs2_rtime_compress,
0117     .decompress = &jffs2_rtime_decompress,
0118 #ifdef JFFS2_RTIME_DISABLED
0119     .disabled = 1,
0120 #else
0121     .disabled = 0,
0122 #endif
0123 };
0124
0125 int jffs2_rtime_init(void)
0126 {
0127     return jffs2_register_compressor(&jffs2_rtime_comp);
0128 }
0129
0130 void jffs2_rtime_exit(void)
0131 {
0132     jffs2_unregister_compressor(&jffs2_rtime_comp);
0133 }