1/* 2 * JFFS2 -- Journalling Flash File System, Version 2. 3 * 4 * Copyright (C) 2001 Red Hat, Inc. 5 * 6 * Created by Arjan van de Ven <arjanv@redhat.com> 7 * 8 * The original JFFS, from which the design for JFFS2 was derived, 9 * was designed and implemented by Axis Communications AB. 10 * 11 * The contents of this file are subject to the Red Hat eCos Public 12 * License Version 1.1 (the "Licence"); you may not use this file 13 * except in compliance with the Licence. You may obtain a copy of 14 * the Licence at http://www.redhat.com/ 15 * 16 * Software distributed under the Licence is distributed on an "AS IS" 17 * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. 18 * See the Licence for the specific language governing rights and 19 * limitations under the Licence. 20 * 21 * The Original Code is JFFS2 - Journalling Flash File System, version 2 22 * 23 * Alternatively, the contents of this file may be used under the 24 * terms of the GNU General Public License version 2 (the "GPL"), in 25 * which case the provisions of the GPL are applicable instead of the 26 * above. If you wish to allow the use of your version of this file 27 * only under the terms of the GPL and not to allow others to use your 28 * version of this file under the RHEPL, indicate your decision by 29 * deleting the provisions above and replace them with the notice and 30 * other provisions required by the GPL. If you do not delete the 31 * provisions above, a recipient may use your version of this file 32 * under either the RHEPL or the GPL. 33 * 34 * $Id: compr_rubin.c,v 1.1.1.1 2008/10/15 03:27:07 james26_jang Exp $ 35 * 36 */ 37 38 39#include <linux/string.h> 40#include <linux/types.h> 41#include "compr_rubin.h" 42#include "histo_mips.h" 43 44 45 46void init_rubin(struct rubin_state *rs, int div, int *bits) 47{ 48 int c; 49 50 rs->q = 0; 51 rs->p = (long) (2 * UPPER_BIT_RUBIN); 52 rs->bit_number = (long) 0; 53 rs->bit_divider = div; 54 for (c=0; c<8; c++) 55 rs->bits[c] = bits[c]; 56} 57 58 59int encode(struct rubin_state *rs, long A, long B, int symbol) 60{ 61 62 long i0, i1; 63 int ret; 64 65 while ((rs->q >= UPPER_BIT_RUBIN) || ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) { 66 rs->bit_number++; 67 68 ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0); 69 if (ret) 70 return ret; 71 rs->q &= LOWER_BITS_RUBIN; 72 rs->q <<= 1; 73 rs->p <<= 1; 74 } 75 i0 = A * rs->p / (A + B); 76 if (i0 <= 0) { 77 i0 = 1; 78 } 79 if (i0 >= rs->p) { 80 i0 = rs->p - 1; 81 } 82 i1 = rs->p - i0; 83 84 if (symbol == 0) 85 rs->p = i0; 86 else { 87 rs->p = i1; 88 rs->q += i0; 89 } 90 return 0; 91} 92 93 94void end_rubin(struct rubin_state *rs) 95{ 96 97 int i; 98 99 for (i = 0; i < RUBIN_REG_SIZE; i++) { 100 pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1); 101 rs->q &= LOWER_BITS_RUBIN; 102 rs->q <<= 1; 103 } 104} 105 106 107void init_decode(struct rubin_state *rs, int div, int *bits) 108{ 109 init_rubin(rs, div, bits); 110 111 /* behalve lower */ 112 rs->rec_q = 0; 113 114 for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE; rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp))) 115 ; 116} 117 118static void __do_decode(struct rubin_state *rs, unsigned long p, unsigned long q) 119{ 120 register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN; 121 unsigned long rec_q; 122 int c, bits = 0; 123 124 /* 125 * First, work out how many bits we need from the input stream. 126 * Note that we have already done the initial check on this 127 * loop prior to calling this function. 128 */ 129 do { 130 bits++; 131 q &= lower_bits_rubin; 132 q <<= 1; 133 p <<= 1; 134 } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN)); 135 136 rs->p = p; 137 rs->q = q; 138 139 rs->bit_number += bits; 140 141 /* 142 * Now get the bits. We really want this to be "get n bits". 143 */ 144 rec_q = rs->rec_q; 145 do { 146 c = pullbit(&rs->pp); 147 rec_q &= lower_bits_rubin; 148 rec_q <<= 1; 149 rec_q += c; 150 } while (--bits); 151 rs->rec_q = rec_q; 152} 153 154int decode(struct rubin_state *rs, long A, long B) 155{ 156 unsigned long p = rs->p, q = rs->q; 157 long i0, threshold; 158 int symbol; 159 160 if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN)) 161 __do_decode(rs, p, q); 162 163 i0 = A * rs->p / (A + B); 164 if (i0 <= 0) { 165 i0 = 1; 166 } 167 if (i0 >= rs->p) { 168 i0 = rs->p - 1; 169 } 170 171 threshold = rs->q + i0; 172 symbol = rs->rec_q >= threshold; 173 if (rs->rec_q >= threshold) { 174 rs->q += i0; 175 i0 = rs->p - i0; 176 } 177 178 rs->p = i0; 179 180 return symbol; 181} 182 183 184 185static int out_byte(struct rubin_state *rs, unsigned char byte) 186{ 187 int i, ret; 188 struct rubin_state rs_copy; 189 rs_copy = *rs; 190 191 for (i=0;i<8;i++) { 192 ret = encode(rs, rs->bit_divider-rs->bits[i],rs->bits[i],byte&1); 193 if (ret) { 194 /* Failed. Restore old state */ 195 *rs = rs_copy; 196 return ret; 197 } 198 byte=byte>>1; 199 } 200 return 0; 201} 202 203static int in_byte(struct rubin_state *rs) 204{ 205 int i, result = 0, bit_divider = rs->bit_divider; 206 207 for (i = 0; i < 8; i++) 208 result |= decode(rs, bit_divider - rs->bits[i], rs->bits[i]) << i; 209 210 return result; 211} 212 213 214 215int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in, 216 unsigned char *cpage_out, __u32 *sourcelen, __u32 *dstlen) 217 { 218 int outpos = 0; 219 int pos=0; 220 struct rubin_state rs; 221 222 init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32); 223 224 init_rubin(&rs, bit_divider, bits); 225 226 while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos])) 227 pos++; 228 229 end_rubin(&rs); 230 231 if (outpos > pos) { 232 /* We failed */ 233 return -1; 234 } 235 236 /* Tell the caller how much we managed to compress, 237 * and how much space it took */ 238 239 outpos = (pushedbits(&rs.pp)+7)/8; 240 241 if (outpos >= pos) 242 return -1; /* We didn't actually compress */ 243 *sourcelen = pos; 244 *dstlen = outpos; 245 return 0; 246} 247int dynrubin_compress(unsigned char *data_in, unsigned char *cpage_out, 248 __u32 *sourcelen, __u32 *dstlen) 249{ 250 int bits[8]; 251 unsigned char histo[256]; 252 int i; 253 int ret; 254 __u32 mysrclen, mydstlen; 255 256 mysrclen = *sourcelen; 257 mydstlen = *dstlen - 8; 258 259 if (*dstlen <= 12) 260 return -1; 261 262 memset(histo, 0, 256); 263 for (i=0; i<mysrclen; i++) { 264 histo[data_in[i]]++; 265 } 266 memset(bits, 0, sizeof(int)*8); 267 for (i=0; i<256; i++) { 268 if (i&128) 269 bits[7] += histo[i]; 270 if (i&64) 271 bits[6] += histo[i]; 272 if (i&32) 273 bits[5] += histo[i]; 274 if (i&16) 275 bits[4] += histo[i]; 276 if (i&8) 277 bits[3] += histo[i]; 278 if (i&4) 279 bits[2] += histo[i]; 280 if (i&2) 281 bits[1] += histo[i]; 282 if (i&1) 283 bits[0] += histo[i]; 284 } 285 286 for (i=0; i<8; i++) { 287 bits[i] = (bits[i] * 256) / mysrclen; 288 if (!bits[i]) bits[i] = 1; 289 if (bits[i] > 255) bits[i] = 255; 290 cpage_out[i] = bits[i]; 291 } 292 293 ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen, &mydstlen); 294 if (ret) 295 return ret; 296 297 /* Add back the 8 bytes we took for the probabilities */ 298 mydstlen += 8; 299 300 if (mysrclen <= mydstlen) { 301 /* We compressed */ 302 return -1; 303 } 304 305 *sourcelen = mysrclen; 306 *dstlen = mydstlen; 307 return 0; 308} 309 310void rubin_do_decompress(int bit_divider, int *bits, unsigned char *cdata_in, 311 unsigned char *page_out, __u32 srclen, __u32 destlen) 312{ 313 int outpos = 0; 314 struct rubin_state rs; 315 316 init_pushpull(&rs.pp, cdata_in, srclen, 0, 0); 317 init_decode(&rs, bit_divider, bits); 318 319 while (outpos < destlen) { 320 page_out[outpos++] = in_byte(&rs); 321 } 322} 323 324 325void rubinmips_decompress(unsigned char *data_in, unsigned char *cpage_out, 326 __u32 sourcelen, __u32 dstlen) 327{ 328 rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in, cpage_out, sourcelen, dstlen); 329} 330 331void dynrubin_decompress(unsigned char *data_in, unsigned char *cpage_out, 332 __u32 sourcelen, __u32 dstlen) 333{ 334 int bits[8]; 335 int c; 336 337 for (c=0; c<8; c++) 338 bits[c] = data_in[c]; 339 340 rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8, dstlen); 341} 342