Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | /* |
| 2 | * JFFS2 -- Journalling Flash File System, Version 2. |
| 3 | * |
David Woodhouse | c00c310 | 2007-04-25 14:16:47 +0100 | [diff] [blame] | 4 | * Copyright © 2001-2007 Red Hat, Inc. |
David Woodhouse | 6088c05 | 2010-08-08 14:15:22 +0100 | [diff] [blame] | 5 | * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 6 | * |
| 7 | * Created by Arjan van de Ven <arjanv@redhat.com> |
| 8 | * |
| 9 | * For licensing information, see the file 'LICENCE' in this directory. |
| 10 | * |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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> |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 27 | #include <linux/string.h> |
| 28 | #include <linux/jffs2.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 29 | #include "compr.h" |
| 30 | |
| 31 | /* _compress returns the compressed size, -1 if bigger */ |
| 32 | static int jffs2_rtime_compress(unsigned char *data_in, |
| 33 | unsigned char *cpage_out, |
Mike Frysinger | 088bd45 | 2010-09-22 22:52:33 -0400 | [diff] [blame] | 34 | uint32_t *sourcelen, uint32_t *dstlen) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 35 | { |
Kamlakant Patel | 3367da5 | 2014-01-06 19:06:54 +0530 | [diff] [blame] | 36 | unsigned short positions[256]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 37 | int outpos = 0; |
| 38 | int pos=0; |
| 39 | |
Yang Yang | 7d1044c | 2021-01-28 02:55:35 -0800 | [diff] [blame] | 40 | if (*dstlen <= 3) |
| 41 | return -1; |
| 42 | |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 43 | memset(positions,0,sizeof(positions)); |
| 44 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 45 | while (pos < (*sourcelen) && outpos <= (*dstlen)-2) { |
| 46 | int backpos, runlen=0; |
| 47 | unsigned char value; |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 48 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 49 | value = data_in[pos]; |
| 50 | |
| 51 | cpage_out[outpos++] = data_in[pos++]; |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 52 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 53 | backpos = positions[value]; |
| 54 | positions[value]=pos; |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 55 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 56 | while ((backpos < pos) && (pos < (*sourcelen)) && |
| 57 | (data_in[pos]==data_in[backpos++]) && (runlen<255)) { |
| 58 | pos++; |
| 59 | runlen++; |
| 60 | } |
| 61 | cpage_out[outpos++] = runlen; |
| 62 | } |
| 63 | |
| 64 | if (outpos >= pos) { |
| 65 | /* We failed */ |
| 66 | return -1; |
| 67 | } |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 68 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 69 | /* Tell the caller how much we managed to compress, and how much space it took */ |
| 70 | *sourcelen = pos; |
| 71 | *dstlen = outpos; |
| 72 | return 0; |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 73 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 74 | |
| 75 | |
| 76 | static int jffs2_rtime_decompress(unsigned char *data_in, |
| 77 | unsigned char *cpage_out, |
Mike Frysinger | 088bd45 | 2010-09-22 22:52:33 -0400 | [diff] [blame] | 78 | uint32_t srclen, uint32_t destlen) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 79 | { |
Kamlakant Patel | 3367da5 | 2014-01-06 19:06:54 +0530 | [diff] [blame] | 80 | unsigned short positions[256]; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 81 | int outpos = 0; |
| 82 | int pos=0; |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 83 | |
| 84 | memset(positions,0,sizeof(positions)); |
| 85 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 86 | while (outpos<destlen) { |
| 87 | unsigned char value; |
| 88 | int backoffs; |
| 89 | int repeat; |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 90 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 91 | value = data_in[pos++]; |
| 92 | cpage_out[outpos++] = value; /* first the verbatim copied byte */ |
| 93 | repeat = data_in[pos++]; |
| 94 | backoffs = positions[value]; |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 95 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 96 | positions[value]=outpos; |
| 97 | if (repeat) { |
| 98 | if (backoffs + repeat >= outpos) { |
| 99 | while(repeat) { |
| 100 | cpage_out[outpos++] = cpage_out[backoffs++]; |
| 101 | repeat--; |
| 102 | } |
| 103 | } else { |
| 104 | memcpy(&cpage_out[outpos],&cpage_out[backoffs],repeat); |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 105 | outpos+=repeat; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 106 | } |
| 107 | } |
| 108 | } |
David Woodhouse | ef53cb0 | 2007-07-10 10:01:22 +0100 | [diff] [blame] | 109 | return 0; |
Thomas Gleixner | 182ec4e | 2005-11-07 11:16:07 +0000 | [diff] [blame] | 110 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 111 | |
| 112 | static struct jffs2_compressor jffs2_rtime_comp = { |
| 113 | .priority = JFFS2_RTIME_PRIORITY, |
| 114 | .name = "rtime", |
| 115 | .compr = JFFS2_COMPR_RTIME, |
| 116 | .compress = &jffs2_rtime_compress, |
| 117 | .decompress = &jffs2_rtime_decompress, |
| 118 | #ifdef JFFS2_RTIME_DISABLED |
| 119 | .disabled = 1, |
| 120 | #else |
| 121 | .disabled = 0, |
| 122 | #endif |
| 123 | }; |
| 124 | |
| 125 | int jffs2_rtime_init(void) |
| 126 | { |
| 127 | return jffs2_register_compressor(&jffs2_rtime_comp); |
| 128 | } |
| 129 | |
| 130 | void jffs2_rtime_exit(void) |
| 131 | { |
| 132 | jffs2_unregister_compressor(&jffs2_rtime_comp); |
| 133 | } |