mini_inflate.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391
  1. /*-------------------------------------------------------------------------
  2. * Filename: mini_inflate.c
  3. * Version: $Id: mini_inflate.c,v 1.3 2002/01/24 22:58:42 rfeany Exp $
  4. * Copyright: Copyright (C) 2001, Russ Dill
  5. * Author: Russ Dill <Russ.Dill@asu.edu>
  6. * Description: Mini inflate implementation (RFC 1951)
  7. *-----------------------------------------------------------------------*/
  8. /*
  9. *
  10. * This program is free software; you can redistribute it and/or modify
  11. * it under the terms of the GNU General Public License as published by
  12. * the Free Software Foundation; either version 2 of the License, or
  13. * (at your option) any later version.
  14. *
  15. * This program is distributed in the hope that it will be useful,
  16. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  18. * GNU General Public License for more details.
  19. *
  20. * You should have received a copy of the GNU General Public License
  21. * along with this program; if not, write to the Free Software
  22. * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  23. *
  24. */
  25. #include <config.h>
  26. #include <jffs2/mini_inflate.h>
  27. /* The order that the code lengths in section 3.2.7 are in */
  28. static unsigned char huffman_order[] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
  29. 11, 4, 12, 3, 13, 2, 14, 1, 15};
  30. inline void cramfs_memset(int *s, const int c, size n)
  31. {
  32. n--;
  33. for (;n > 0; n--) s[n] = c;
  34. s[0] = c;
  35. }
  36. /* associate a stream with a block of data and reset the stream */
  37. static void init_stream(struct bitstream *stream, unsigned char *data,
  38. void *(*inflate_memcpy)(void *, const void *, size))
  39. {
  40. stream->error = NO_ERROR;
  41. stream->memcpy = inflate_memcpy;
  42. stream->decoded = 0;
  43. stream->data = data;
  44. stream->bit = 0; /* The first bit of the stream is the lsb of the
  45. * first byte */
  46. /* really sorry about all this initialization, think of a better way,
  47. * let me know and it will get cleaned up */
  48. stream->codes.bits = 8;
  49. stream->codes.num_symbols = 19;
  50. stream->codes.lengths = stream->code_lengths;
  51. stream->codes.symbols = stream->code_symbols;
  52. stream->codes.count = stream->code_count;
  53. stream->codes.first = stream->code_first;
  54. stream->codes.pos = stream->code_pos;
  55. stream->lengths.bits = 16;
  56. stream->lengths.num_symbols = 288;
  57. stream->lengths.lengths = stream->length_lengths;
  58. stream->lengths.symbols = stream->length_symbols;
  59. stream->lengths.count = stream->length_count;
  60. stream->lengths.first = stream->length_first;
  61. stream->lengths.pos = stream->length_pos;
  62. stream->distance.bits = 16;
  63. stream->distance.num_symbols = 32;
  64. stream->distance.lengths = stream->distance_lengths;
  65. stream->distance.symbols = stream->distance_symbols;
  66. stream->distance.count = stream->distance_count;
  67. stream->distance.first = stream->distance_first;
  68. stream->distance.pos = stream->distance_pos;
  69. }
  70. /* pull 'bits' bits out of the stream. The last bit pulled it returned as the
  71. * msb. (section 3.1.1)
  72. */
  73. inline unsigned long pull_bits(struct bitstream *stream,
  74. const unsigned int bits)
  75. {
  76. unsigned long ret;
  77. int i;
  78. ret = 0;
  79. for (i = 0; i < bits; i++) {
  80. ret += ((*(stream->data) >> stream->bit) & 1) << i;
  81. /* if, before incrementing, we are on bit 7,
  82. * go to the lsb of the next byte */
  83. if (stream->bit++ == 7) {
  84. stream->bit = 0;
  85. stream->data++;
  86. }
  87. }
  88. return ret;
  89. }
  90. inline int pull_bit(struct bitstream *stream)
  91. {
  92. int ret = ((*(stream->data) >> stream->bit) & 1);
  93. if (stream->bit++ == 7) {
  94. stream->bit = 0;
  95. stream->data++;
  96. }
  97. return ret;
  98. }
  99. /* discard bits up to the next whole byte */
  100. static void discard_bits(struct bitstream *stream)
  101. {
  102. if (stream->bit != 0) {
  103. stream->bit = 0;
  104. stream->data++;
  105. }
  106. }
  107. /* No decompression, the data is all literals (section 3.2.4) */
  108. static void decompress_none(struct bitstream *stream, unsigned char *dest)
  109. {
  110. unsigned int length;
  111. discard_bits(stream);
  112. length = *(stream->data++);
  113. length += *(stream->data++) << 8;
  114. pull_bits(stream, 16); /* throw away the inverse of the size */
  115. stream->decoded += length;
  116. stream->memcpy(dest, stream->data, length);
  117. stream->data += length;
  118. }
  119. /* Read in a symbol from the stream (section 3.2.2) */
  120. static int read_symbol(struct bitstream *stream, struct huffman_set *set)
  121. {
  122. int bits = 0;
  123. int code = 0;
  124. while (!(set->count[bits] && code < set->first[bits] +
  125. set->count[bits])) {
  126. code = (code << 1) + pull_bit(stream);
  127. if (++bits > set->bits) {
  128. /* error decoding (corrupted data?) */
  129. stream->error = CODE_NOT_FOUND;
  130. return -1;
  131. }
  132. }
  133. return set->symbols[set->pos[bits] + code - set->first[bits]];
  134. }
  135. /* decompress a stream of data encoded with the passed length and distance
  136. * huffman codes */
  137. static void decompress_huffman(struct bitstream *stream, unsigned char *dest)
  138. {
  139. struct huffman_set *lengths = &(stream->lengths);
  140. struct huffman_set *distance = &(stream->distance);
  141. int symbol, length, dist, i;
  142. do {
  143. if ((symbol = read_symbol(stream, lengths)) < 0) return;
  144. if (symbol < 256) {
  145. *(dest++) = symbol; /* symbol is a literal */
  146. stream->decoded++;
  147. } else if (symbol > 256) {
  148. /* Determine the length of the repitition
  149. * (section 3.2.5) */
  150. if (symbol < 265) length = symbol - 254;
  151. else if (symbol == 285) length = 258;
  152. else {
  153. length = pull_bits(stream, (symbol - 261) >> 2);
  154. length += (4 << ((symbol - 261) >> 2)) + 3;
  155. length += ((symbol - 1) % 4) <<
  156. ((symbol - 261) >> 2);
  157. }
  158. /* Determine how far back to go */
  159. if ((symbol = read_symbol(stream, distance)) < 0)
  160. return;
  161. if (symbol < 4) dist = symbol + 1;
  162. else {
  163. dist = pull_bits(stream, (symbol - 2) >> 1);
  164. dist += (2 << ((symbol - 2) >> 1)) + 1;
  165. dist += (symbol % 2) << ((symbol - 2) >> 1);
  166. }
  167. stream->decoded += length;
  168. for (i = 0; i < length; i++) {
  169. *dest = dest[-dist];
  170. dest++;
  171. }
  172. }
  173. } while (symbol != 256); /* 256 is the end of the data block */
  174. }
  175. /* Fill the lookup tables (section 3.2.2) */
  176. static void fill_code_tables(struct huffman_set *set)
  177. {
  178. int code = 0, i, length;
  179. /* fill in the first code of each bit length, and the pos pointer */
  180. set->pos[0] = 0;
  181. for (i = 1; i < set->bits; i++) {
  182. code = (code + set->count[i - 1]) << 1;
  183. set->first[i] = code;
  184. set->pos[i] = set->pos[i - 1] + set->count[i - 1];
  185. }
  186. /* Fill in the table of symbols in order of their huffman code */
  187. for (i = 0; i < set->num_symbols; i++) {
  188. if ((length = set->lengths[i]))
  189. set->symbols[set->pos[length]++] = i;
  190. }
  191. /* reset the pos pointer */
  192. for (i = 1; i < set->bits; i++) set->pos[i] -= set->count[i];
  193. }
  194. static void init_code_tables(struct huffman_set *set)
  195. {
  196. cramfs_memset(set->lengths, 0, set->num_symbols);
  197. cramfs_memset(set->count, 0, set->bits);
  198. cramfs_memset(set->first, 0, set->bits);
  199. }
  200. /* read in the huffman codes for dynamic decoding (section 3.2.7) */
  201. static void decompress_dynamic(struct bitstream *stream, unsigned char *dest)
  202. {
  203. /* I tried my best to minimize the memory footprint here, while still
  204. * keeping up performance. I really dislike the _lengths[] tables, but
  205. * I see no way of eliminating them without a sizable performance
  206. * impact. The first struct table keeps track of stats on each bit
  207. * length. The _length table keeps a record of the bit length of each
  208. * symbol. The _symbols table is for looking up symbols by the huffman
  209. * code (the pos element points to the first place in the symbol table
  210. * where that bit length occurs). I also hate the initization of these
  211. * structs, if someone knows how to compact these, lemme know. */
  212. struct huffman_set *codes = &(stream->codes);
  213. struct huffman_set *lengths = &(stream->lengths);
  214. struct huffman_set *distance = &(stream->distance);
  215. int hlit = pull_bits(stream, 5) + 257;
  216. int hdist = pull_bits(stream, 5) + 1;
  217. int hclen = pull_bits(stream, 4) + 4;
  218. int length, curr_code, symbol, i, last_code;
  219. last_code = 0;
  220. init_code_tables(codes);
  221. init_code_tables(lengths);
  222. init_code_tables(distance);
  223. /* fill in the count of each bit length' as well as the lengths
  224. * table */
  225. for (i = 0; i < hclen; i++) {
  226. length = pull_bits(stream, 3);
  227. codes->lengths[huffman_order[i]] = length;
  228. if (length) codes->count[length]++;
  229. }
  230. fill_code_tables(codes);
  231. /* Do the same for the length codes, being carefull of wrap through
  232. * to the distance table */
  233. curr_code = 0;
  234. while (curr_code < hlit) {
  235. if ((symbol = read_symbol(stream, codes)) < 0) return;
  236. if (symbol == 0) {
  237. curr_code++;
  238. last_code = 0;
  239. } else if (symbol < 16) { /* Literal length */
  240. lengths->lengths[curr_code] = last_code = symbol;
  241. lengths->count[symbol]++;
  242. curr_code++;
  243. } else if (symbol == 16) { /* repeat the last symbol 3 - 6
  244. * times */
  245. length = 3 + pull_bits(stream, 2);
  246. for (;length; length--, curr_code++)
  247. if (curr_code < hlit) {
  248. lengths->lengths[curr_code] =
  249. last_code;
  250. lengths->count[last_code]++;
  251. } else { /* wrap to the distance table */
  252. distance->lengths[curr_code - hlit] =
  253. last_code;
  254. distance->count[last_code]++;
  255. }
  256. } else if (symbol == 17) { /* repeat a bit length 0 */
  257. curr_code += 3 + pull_bits(stream, 3);
  258. last_code = 0;
  259. } else { /* same, but more times */
  260. curr_code += 11 + pull_bits(stream, 7);
  261. last_code = 0;
  262. }
  263. }
  264. fill_code_tables(lengths);
  265. /* Fill the distance table, don't need to worry about wrapthrough
  266. * here */
  267. curr_code -= hlit;
  268. while (curr_code < hdist) {
  269. if ((symbol = read_symbol(stream, codes)) < 0) return;
  270. if (symbol == 0) {
  271. curr_code++;
  272. last_code = 0;
  273. } else if (symbol < 16) {
  274. distance->lengths[curr_code] = last_code = symbol;
  275. distance->count[symbol]++;
  276. curr_code++;
  277. } else if (symbol == 16) {
  278. length = 3 + pull_bits(stream, 2);
  279. for (;length; length--, curr_code++) {
  280. distance->lengths[curr_code] =
  281. last_code;
  282. distance->count[last_code]++;
  283. }
  284. } else if (symbol == 17) {
  285. curr_code += 3 + pull_bits(stream, 3);
  286. last_code = 0;
  287. } else {
  288. curr_code += 11 + pull_bits(stream, 7);
  289. last_code = 0;
  290. }
  291. }
  292. fill_code_tables(distance);
  293. decompress_huffman(stream, dest);
  294. }
  295. /* fill in the length and distance huffman codes for fixed encoding
  296. * (section 3.2.6) */
  297. static void decompress_fixed(struct bitstream *stream, unsigned char *dest)
  298. {
  299. /* let gcc fill in the initial values */
  300. struct huffman_set *lengths = &(stream->lengths);
  301. struct huffman_set *distance = &(stream->distance);
  302. cramfs_memset(lengths->count, 0, 16);
  303. cramfs_memset(lengths->first, 0, 16);
  304. cramfs_memset(lengths->lengths, 8, 144);
  305. cramfs_memset(lengths->lengths + 144, 9, 112);
  306. cramfs_memset(lengths->lengths + 256, 7, 24);
  307. cramfs_memset(lengths->lengths + 280, 8, 8);
  308. lengths->count[7] = 24;
  309. lengths->count[8] = 152;
  310. lengths->count[9] = 112;
  311. cramfs_memset(distance->count, 0, 16);
  312. cramfs_memset(distance->first, 0, 16);
  313. cramfs_memset(distance->lengths, 5, 32);
  314. distance->count[5] = 32;
  315. fill_code_tables(lengths);
  316. fill_code_tables(distance);
  317. decompress_huffman(stream, dest);
  318. }
  319. /* returns the number of bytes decoded, < 0 if there was an error. Note that
  320. * this function assumes that the block starts on a byte boundry
  321. * (non-compliant, but I don't see where this would happen). section 3.2.3 */
  322. long decompress_block(unsigned char *dest, unsigned char *source,
  323. void *(*inflate_memcpy)(void *, const void *, size))
  324. {
  325. int bfinal, btype;
  326. struct bitstream stream;
  327. init_stream(&stream, source, inflate_memcpy);
  328. do {
  329. bfinal = pull_bit(&stream);
  330. btype = pull_bits(&stream, 2);
  331. if (btype == NO_COMP) decompress_none(&stream, dest + stream.decoded);
  332. else if (btype == DYNAMIC_COMP)
  333. decompress_dynamic(&stream, dest + stream.decoded);
  334. else if (btype == FIXED_COMP) decompress_fixed(&stream, dest + stream.decoded);
  335. else stream.error = COMP_UNKNOWN;
  336. } while (!bfinal && !stream.error);
  337. #if 0
  338. putstr("decompress_block start\r\n");
  339. putLabeledWord("stream.error = ",stream.error);
  340. putLabeledWord("stream.decoded = ",stream.decoded);
  341. putLabeledWord("dest = ",dest);
  342. putstr("decompress_block end\r\n");
  343. #endif
  344. return stream.error ? -stream.error : stream.decoded;
  345. }