compr_rubin.c 8.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452
  1. /*
  2. * JFFS2 -- Journalling Flash File System, Version 2.
  3. *
  4. * Copyright © 2001-2007 Red Hat, Inc.
  5. * Copyright © 2004-2010 David Woodhouse <dwmw2@infradead.org>
  6. *
  7. * Created by Arjan van de Ven <arjanv@redhat.com>
  8. *
  9. * For licensing information, see the file 'LICENCE' in this directory.
  10. *
  11. */
  12. #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  13. #include <linux/string.h>
  14. #include <linux/types.h>
  15. #include <linux/jffs2.h>
  16. #include <linux/errno.h>
  17. #include "compr.h"
  18. #define RUBIN_REG_SIZE 16
  19. #define UPPER_BIT_RUBIN (((long) 1)<<(RUBIN_REG_SIZE-1))
  20. #define LOWER_BITS_RUBIN ((((long) 1)<<(RUBIN_REG_SIZE-1))-1)
  21. #define BIT_DIVIDER_MIPS 1043
  22. static int bits_mips[8] = { 277, 249, 290, 267, 229, 341, 212, 241};
  23. struct pushpull {
  24. unsigned char *buf;
  25. unsigned int buflen;
  26. unsigned int ofs;
  27. unsigned int reserve;
  28. };
  29. struct rubin_state {
  30. unsigned long p;
  31. unsigned long q;
  32. unsigned long rec_q;
  33. long bit_number;
  34. struct pushpull pp;
  35. int bit_divider;
  36. int bits[8];
  37. };
  38. static inline void init_pushpull(struct pushpull *pp, char *buf,
  39. unsigned buflen, unsigned ofs,
  40. unsigned reserve)
  41. {
  42. pp->buf = buf;
  43. pp->buflen = buflen;
  44. pp->ofs = ofs;
  45. pp->reserve = reserve;
  46. }
  47. static inline int pushbit(struct pushpull *pp, int bit, int use_reserved)
  48. {
  49. if (pp->ofs >= pp->buflen - (use_reserved?0:pp->reserve))
  50. return -ENOSPC;
  51. if (bit)
  52. pp->buf[pp->ofs >> 3] |= (1<<(7-(pp->ofs & 7)));
  53. else
  54. pp->buf[pp->ofs >> 3] &= ~(1<<(7-(pp->ofs & 7)));
  55. pp->ofs++;
  56. return 0;
  57. }
  58. static inline int pushedbits(struct pushpull *pp)
  59. {
  60. return pp->ofs;
  61. }
  62. static inline int pullbit(struct pushpull *pp)
  63. {
  64. int bit;
  65. bit = (pp->buf[pp->ofs >> 3] >> (7-(pp->ofs & 7))) & 1;
  66. pp->ofs++;
  67. return bit;
  68. }
  69. static void init_rubin(struct rubin_state *rs, int div, int *bits)
  70. {
  71. int c;
  72. rs->q = 0;
  73. rs->p = (long) (2 * UPPER_BIT_RUBIN);
  74. rs->bit_number = (long) 0;
  75. rs->bit_divider = div;
  76. for (c=0; c<8; c++)
  77. rs->bits[c] = bits[c];
  78. }
  79. static int encode(struct rubin_state *rs, long A, long B, int symbol)
  80. {
  81. long i0, i1;
  82. int ret;
  83. while ((rs->q >= UPPER_BIT_RUBIN) ||
  84. ((rs->p + rs->q) <= UPPER_BIT_RUBIN)) {
  85. rs->bit_number++;
  86. ret = pushbit(&rs->pp, (rs->q & UPPER_BIT_RUBIN) ? 1 : 0, 0);
  87. if (ret)
  88. return ret;
  89. rs->q &= LOWER_BITS_RUBIN;
  90. rs->q <<= 1;
  91. rs->p <<= 1;
  92. }
  93. i0 = A * rs->p / (A + B);
  94. if (i0 <= 0)
  95. i0 = 1;
  96. if (i0 >= rs->p)
  97. i0 = rs->p - 1;
  98. i1 = rs->p - i0;
  99. if (symbol == 0)
  100. rs->p = i0;
  101. else {
  102. rs->p = i1;
  103. rs->q += i0;
  104. }
  105. return 0;
  106. }
  107. static void end_rubin(struct rubin_state *rs)
  108. {
  109. int i;
  110. for (i = 0; i < RUBIN_REG_SIZE; i++) {
  111. pushbit(&rs->pp, (UPPER_BIT_RUBIN & rs->q) ? 1 : 0, 1);
  112. rs->q &= LOWER_BITS_RUBIN;
  113. rs->q <<= 1;
  114. }
  115. }
  116. static void init_decode(struct rubin_state *rs, int div, int *bits)
  117. {
  118. init_rubin(rs, div, bits);
  119. /* behalve lower */
  120. rs->rec_q = 0;
  121. for (rs->bit_number = 0; rs->bit_number++ < RUBIN_REG_SIZE;
  122. rs->rec_q = rs->rec_q * 2 + (long) (pullbit(&rs->pp)))
  123. ;
  124. }
  125. static void __do_decode(struct rubin_state *rs, unsigned long p,
  126. unsigned long q)
  127. {
  128. register unsigned long lower_bits_rubin = LOWER_BITS_RUBIN;
  129. unsigned long rec_q;
  130. int c, bits = 0;
  131. /*
  132. * First, work out how many bits we need from the input stream.
  133. * Note that we have already done the initial check on this
  134. * loop prior to calling this function.
  135. */
  136. do {
  137. bits++;
  138. q &= lower_bits_rubin;
  139. q <<= 1;
  140. p <<= 1;
  141. } while ((q >= UPPER_BIT_RUBIN) || ((p + q) <= UPPER_BIT_RUBIN));
  142. rs->p = p;
  143. rs->q = q;
  144. rs->bit_number += bits;
  145. /*
  146. * Now get the bits. We really want this to be "get n bits".
  147. */
  148. rec_q = rs->rec_q;
  149. do {
  150. c = pullbit(&rs->pp);
  151. rec_q &= lower_bits_rubin;
  152. rec_q <<= 1;
  153. rec_q += c;
  154. } while (--bits);
  155. rs->rec_q = rec_q;
  156. }
  157. static int decode(struct rubin_state *rs, long A, long B)
  158. {
  159. unsigned long p = rs->p, q = rs->q;
  160. long i0, threshold;
  161. int symbol;
  162. if (q >= UPPER_BIT_RUBIN || ((p + q) <= UPPER_BIT_RUBIN))
  163. __do_decode(rs, p, q);
  164. i0 = A * rs->p / (A + B);
  165. if (i0 <= 0)
  166. i0 = 1;
  167. if (i0 >= rs->p)
  168. i0 = rs->p - 1;
  169. threshold = rs->q + i0;
  170. symbol = rs->rec_q >= threshold;
  171. if (rs->rec_q >= threshold) {
  172. rs->q += i0;
  173. i0 = rs->p - i0;
  174. }
  175. rs->p = i0;
  176. return symbol;
  177. }
  178. static int out_byte(struct rubin_state *rs, unsigned char byte)
  179. {
  180. int i, ret;
  181. struct rubin_state rs_copy;
  182. rs_copy = *rs;
  183. for (i=0; i<8; i++) {
  184. ret = encode(rs, rs->bit_divider-rs->bits[i],
  185. rs->bits[i], byte & 1);
  186. if (ret) {
  187. /* Failed. Restore old state */
  188. *rs = rs_copy;
  189. return ret;
  190. }
  191. byte >>= 1 ;
  192. }
  193. return 0;
  194. }
  195. static int in_byte(struct rubin_state *rs)
  196. {
  197. int i, result = 0, bit_divider = rs->bit_divider;
  198. for (i = 0; i < 8; i++)
  199. result |= decode(rs, bit_divider - rs->bits[i],
  200. rs->bits[i]) << i;
  201. return result;
  202. }
  203. static int rubin_do_compress(int bit_divider, int *bits, unsigned char *data_in,
  204. unsigned char *cpage_out, uint32_t *sourcelen,
  205. uint32_t *dstlen)
  206. {
  207. int outpos = 0;
  208. int pos=0;
  209. struct rubin_state rs;
  210. init_pushpull(&rs.pp, cpage_out, *dstlen * 8, 0, 32);
  211. init_rubin(&rs, bit_divider, bits);
  212. while (pos < (*sourcelen) && !out_byte(&rs, data_in[pos]))
  213. pos++;
  214. end_rubin(&rs);
  215. if (outpos > pos) {
  216. /* We failed */
  217. return -1;
  218. }
  219. /* Tell the caller how much we managed to compress,
  220. * and how much space it took */
  221. outpos = (pushedbits(&rs.pp)+7)/8;
  222. if (outpos >= pos)
  223. return -1; /* We didn't actually compress */
  224. *sourcelen = pos;
  225. *dstlen = outpos;
  226. return 0;
  227. }
  228. #if 0
  229. /* _compress returns the compressed size, -1 if bigger */
  230. int jffs2_rubinmips_compress(unsigned char *data_in, unsigned char *cpage_out,
  231. uint32_t *sourcelen, uint32_t *dstlen)
  232. {
  233. return rubin_do_compress(BIT_DIVIDER_MIPS, bits_mips, data_in,
  234. cpage_out, sourcelen, dstlen);
  235. }
  236. #endif
  237. static int jffs2_dynrubin_compress(unsigned char *data_in,
  238. unsigned char *cpage_out,
  239. uint32_t *sourcelen, uint32_t *dstlen)
  240. {
  241. int bits[8];
  242. unsigned char histo[256];
  243. int i;
  244. int ret;
  245. uint32_t mysrclen, mydstlen;
  246. mysrclen = *sourcelen;
  247. mydstlen = *dstlen - 8;
  248. if (*dstlen <= 12)
  249. return -1;
  250. memset(histo, 0, 256);
  251. for (i=0; i<mysrclen; i++)
  252. histo[data_in[i]]++;
  253. memset(bits, 0, sizeof(int)*8);
  254. for (i=0; i<256; i++) {
  255. if (i&128)
  256. bits[7] += histo[i];
  257. if (i&64)
  258. bits[6] += histo[i];
  259. if (i&32)
  260. bits[5] += histo[i];
  261. if (i&16)
  262. bits[4] += histo[i];
  263. if (i&8)
  264. bits[3] += histo[i];
  265. if (i&4)
  266. bits[2] += histo[i];
  267. if (i&2)
  268. bits[1] += histo[i];
  269. if (i&1)
  270. bits[0] += histo[i];
  271. }
  272. for (i=0; i<8; i++) {
  273. bits[i] = (bits[i] * 256) / mysrclen;
  274. if (!bits[i]) bits[i] = 1;
  275. if (bits[i] > 255) bits[i] = 255;
  276. cpage_out[i] = bits[i];
  277. }
  278. ret = rubin_do_compress(256, bits, data_in, cpage_out+8, &mysrclen,
  279. &mydstlen);
  280. if (ret)
  281. return ret;
  282. /* Add back the 8 bytes we took for the probabilities */
  283. mydstlen += 8;
  284. if (mysrclen <= mydstlen) {
  285. /* We compressed */
  286. return -1;
  287. }
  288. *sourcelen = mysrclen;
  289. *dstlen = mydstlen;
  290. return 0;
  291. }
  292. static void rubin_do_decompress(int bit_divider, int *bits,
  293. unsigned char *cdata_in,
  294. unsigned char *page_out, uint32_t srclen,
  295. uint32_t destlen)
  296. {
  297. int outpos = 0;
  298. struct rubin_state rs;
  299. init_pushpull(&rs.pp, cdata_in, srclen, 0, 0);
  300. init_decode(&rs, bit_divider, bits);
  301. while (outpos < destlen)
  302. page_out[outpos++] = in_byte(&rs);
  303. }
  304. static int jffs2_rubinmips_decompress(unsigned char *data_in,
  305. unsigned char *cpage_out,
  306. uint32_t sourcelen, uint32_t dstlen)
  307. {
  308. rubin_do_decompress(BIT_DIVIDER_MIPS, bits_mips, data_in,
  309. cpage_out, sourcelen, dstlen);
  310. return 0;
  311. }
  312. static int jffs2_dynrubin_decompress(unsigned char *data_in,
  313. unsigned char *cpage_out,
  314. uint32_t sourcelen, uint32_t dstlen)
  315. {
  316. int bits[8];
  317. int c;
  318. for (c=0; c<8; c++)
  319. bits[c] = data_in[c];
  320. rubin_do_decompress(256, bits, data_in+8, cpage_out, sourcelen-8,
  321. dstlen);
  322. return 0;
  323. }
  324. static struct jffs2_compressor jffs2_rubinmips_comp = {
  325. .priority = JFFS2_RUBINMIPS_PRIORITY,
  326. .name = "rubinmips",
  327. .compr = JFFS2_COMPR_DYNRUBIN,
  328. .compress = NULL, /*&jffs2_rubinmips_compress,*/
  329. .decompress = &jffs2_rubinmips_decompress,
  330. #ifdef JFFS2_RUBINMIPS_DISABLED
  331. .disabled = 1,
  332. #else
  333. .disabled = 0,
  334. #endif
  335. };
  336. int jffs2_rubinmips_init(void)
  337. {
  338. return jffs2_register_compressor(&jffs2_rubinmips_comp);
  339. }
  340. void jffs2_rubinmips_exit(void)
  341. {
  342. jffs2_unregister_compressor(&jffs2_rubinmips_comp);
  343. }
  344. static struct jffs2_compressor jffs2_dynrubin_comp = {
  345. .priority = JFFS2_DYNRUBIN_PRIORITY,
  346. .name = "dynrubin",
  347. .compr = JFFS2_COMPR_RUBINMIPS,
  348. .compress = jffs2_dynrubin_compress,
  349. .decompress = &jffs2_dynrubin_decompress,
  350. #ifdef JFFS2_DYNRUBIN_DISABLED
  351. .disabled = 1,
  352. #else
  353. .disabled = 0,
  354. #endif
  355. };
  356. int jffs2_dynrubin_init(void)
  357. {
  358. return jffs2_register_compressor(&jffs2_dynrubin_comp);
  359. }
  360. void jffs2_dynrubin_exit(void)
  361. {
  362. jffs2_unregister_compressor(&jffs2_dynrubin_comp);
  363. }