842_decompress.c 8.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /*
  3. * 842 Software Decompression
  4. *
  5. * Copyright (C) 2015 Dan Streetman, IBM Corp
  6. *
  7. * See 842.h for details of the 842 compressed format.
  8. */
  9. #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
  10. #define MODULE_NAME "842_decompress"
  11. #include "842.h"
  12. #include "842_debugfs.h"
  13. /* rolling fifo sizes */
  14. #define I2_FIFO_SIZE (2 * (1 << I2_BITS))
  15. #define I4_FIFO_SIZE (4 * (1 << I4_BITS))
  16. #define I8_FIFO_SIZE (8 * (1 << I8_BITS))
  17. static u8 decomp_ops[OPS_MAX][4] = {
  18. { D8, N0, N0, N0 },
  19. { D4, D2, I2, N0 },
  20. { D4, I2, D2, N0 },
  21. { D4, I2, I2, N0 },
  22. { D4, I4, N0, N0 },
  23. { D2, I2, D4, N0 },
  24. { D2, I2, D2, I2 },
  25. { D2, I2, I2, D2 },
  26. { D2, I2, I2, I2 },
  27. { D2, I2, I4, N0 },
  28. { I2, D2, D4, N0 },
  29. { I2, D4, I2, N0 },
  30. { I2, D2, I2, D2 },
  31. { I2, D2, I2, I2 },
  32. { I2, D2, I4, N0 },
  33. { I2, I2, D4, N0 },
  34. { I2, I2, D2, I2 },
  35. { I2, I2, I2, D2 },
  36. { I2, I2, I2, I2 },
  37. { I2, I2, I4, N0 },
  38. { I4, D4, N0, N0 },
  39. { I4, D2, I2, N0 },
  40. { I4, I2, D2, N0 },
  41. { I4, I2, I2, N0 },
  42. { I4, I4, N0, N0 },
  43. { I8, N0, N0, N0 }
  44. };
  45. struct sw842_param {
  46. u8 *in;
  47. u8 bit;
  48. u64 ilen;
  49. u8 *out;
  50. u8 *ostart;
  51. u64 olen;
  52. };
  53. #define beN_to_cpu(d, s) \
  54. ((s) == 2 ? be16_to_cpu(get_unaligned((__be16 *)d)) : \
  55. (s) == 4 ? be32_to_cpu(get_unaligned((__be32 *)d)) : \
  56. (s) == 8 ? be64_to_cpu(get_unaligned((__be64 *)d)) : \
  57. 0)
  58. static int next_bits(struct sw842_param *p, u64 *d, u8 n);
  59. static int __split_next_bits(struct sw842_param *p, u64 *d, u8 n, u8 s)
  60. {
  61. u64 tmp = 0;
  62. int ret;
  63. if (n <= s) {
  64. pr_debug("split_next_bits invalid n %u s %u\n", n, s);
  65. return -EINVAL;
  66. }
  67. ret = next_bits(p, &tmp, n - s);
  68. if (ret)
  69. return ret;
  70. ret = next_bits(p, d, s);
  71. if (ret)
  72. return ret;
  73. *d |= tmp << s;
  74. return 0;
  75. }
  76. static int next_bits(struct sw842_param *p, u64 *d, u8 n)
  77. {
  78. u8 *in = p->in, b = p->bit, bits = b + n;
  79. if (n > 64) {
  80. pr_debug("next_bits invalid n %u\n", n);
  81. return -EINVAL;
  82. }
  83. /* split this up if reading > 8 bytes, or if we're at the end of
  84. * the input buffer and would read past the end
  85. */
  86. if (bits > 64)
  87. return __split_next_bits(p, d, n, 32);
  88. else if (p->ilen < 8 && bits > 32 && bits <= 56)
  89. return __split_next_bits(p, d, n, 16);
  90. else if (p->ilen < 4 && bits > 16 && bits <= 24)
  91. return __split_next_bits(p, d, n, 8);
  92. if (DIV_ROUND_UP(bits, 8) > p->ilen)
  93. return -EOVERFLOW;
  94. if (bits <= 8)
  95. *d = *in >> (8 - bits);
  96. else if (bits <= 16)
  97. *d = be16_to_cpu(get_unaligned((__be16 *)in)) >> (16 - bits);
  98. else if (bits <= 32)
  99. *d = be32_to_cpu(get_unaligned((__be32 *)in)) >> (32 - bits);
  100. else
  101. *d = be64_to_cpu(get_unaligned((__be64 *)in)) >> (64 - bits);
  102. *d &= GENMASK_ULL(n - 1, 0);
  103. p->bit += n;
  104. if (p->bit > 7) {
  105. p->in += p->bit / 8;
  106. p->ilen -= p->bit / 8;
  107. p->bit %= 8;
  108. }
  109. return 0;
  110. }
  111. static int do_data(struct sw842_param *p, u8 n)
  112. {
  113. u64 v;
  114. int ret;
  115. if (n > p->olen)
  116. return -ENOSPC;
  117. ret = next_bits(p, &v, n * 8);
  118. if (ret)
  119. return ret;
  120. switch (n) {
  121. case 2:
  122. put_unaligned(cpu_to_be16((u16)v), (__be16 *)p->out);
  123. break;
  124. case 4:
  125. put_unaligned(cpu_to_be32((u32)v), (__be32 *)p->out);
  126. break;
  127. case 8:
  128. put_unaligned(cpu_to_be64((u64)v), (__be64 *)p->out);
  129. break;
  130. default:
  131. return -EINVAL;
  132. }
  133. p->out += n;
  134. p->olen -= n;
  135. return 0;
  136. }
  137. static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize)
  138. {
  139. u64 index, offset, total = round_down(p->out - p->ostart, 8);
  140. int ret;
  141. ret = next_bits(p, &index, bits);
  142. if (ret)
  143. return ret;
  144. offset = index * size;
  145. /* a ring buffer of fsize is used; correct the offset */
  146. if (total > fsize) {
  147. /* this is where the current fifo is */
  148. u64 section = round_down(total, fsize);
  149. /* the current pos in the fifo */
  150. u64 pos = total - section;
  151. /* if the offset is past/at the pos, we need to
  152. * go back to the last fifo section
  153. */
  154. if (offset >= pos)
  155. section -= fsize;
  156. offset += section;
  157. }
  158. if (offset + size > total) {
  159. pr_debug("index%x %lx points past end %lx\n", size,
  160. (unsigned long)offset, (unsigned long)total);
  161. return -EINVAL;
  162. }
  163. if (size != 2 && size != 4 && size != 8)
  164. WARN(1, "__do_index invalid size %x\n", size);
  165. else
  166. pr_debug("index%x to %lx off %lx adjoff %lx tot %lx data %lx\n",
  167. size, (unsigned long)index,
  168. (unsigned long)(index * size), (unsigned long)offset,
  169. (unsigned long)total,
  170. (unsigned long)beN_to_cpu(&p->ostart[offset], size));
  171. memcpy(p->out, &p->ostart[offset], size);
  172. p->out += size;
  173. p->olen -= size;
  174. return 0;
  175. }
  176. static int do_index(struct sw842_param *p, u8 n)
  177. {
  178. switch (n) {
  179. case 2:
  180. return __do_index(p, 2, I2_BITS, I2_FIFO_SIZE);
  181. case 4:
  182. return __do_index(p, 4, I4_BITS, I4_FIFO_SIZE);
  183. case 8:
  184. return __do_index(p, 8, I8_BITS, I8_FIFO_SIZE);
  185. default:
  186. return -EINVAL;
  187. }
  188. }
  189. static int do_op(struct sw842_param *p, u8 o)
  190. {
  191. int i, ret = 0;
  192. if (o >= OPS_MAX)
  193. return -EINVAL;
  194. for (i = 0; i < 4; i++) {
  195. u8 op = decomp_ops[o][i];
  196. pr_debug("op is %x\n", op);
  197. switch (op & OP_ACTION) {
  198. case OP_ACTION_DATA:
  199. ret = do_data(p, op & OP_AMOUNT);
  200. break;
  201. case OP_ACTION_INDEX:
  202. ret = do_index(p, op & OP_AMOUNT);
  203. break;
  204. case OP_ACTION_NOOP:
  205. break;
  206. default:
  207. pr_err("Internal error, invalid op %x\n", op);
  208. return -EINVAL;
  209. }
  210. if (ret)
  211. return ret;
  212. }
  213. if (sw842_template_counts)
  214. atomic_inc(&template_count[o]);
  215. return 0;
  216. }
  217. /**
  218. * sw842_decompress
  219. *
  220. * Decompress the 842-compressed buffer of length @ilen at @in
  221. * to the output buffer @out, using no more than @olen bytes.
  222. *
  223. * The compressed buffer must be only a single 842-compressed buffer,
  224. * with the standard format described in the comments in 842.h
  225. * Processing will stop when the 842 "END" template is detected,
  226. * not the end of the buffer.
  227. *
  228. * Returns: 0 on success, error on failure. The @olen parameter
  229. * will contain the number of output bytes written on success, or
  230. * 0 on error.
  231. */
  232. int sw842_decompress(const u8 *in, unsigned int ilen,
  233. u8 *out, unsigned int *olen)
  234. {
  235. struct sw842_param p;
  236. int ret;
  237. u64 op, rep, tmp, bytes, total;
  238. u64 crc;
  239. p.in = (u8 *)in;
  240. p.bit = 0;
  241. p.ilen = ilen;
  242. p.out = out;
  243. p.ostart = out;
  244. p.olen = *olen;
  245. total = p.olen;
  246. *olen = 0;
  247. do {
  248. ret = next_bits(&p, &op, OP_BITS);
  249. if (ret)
  250. return ret;
  251. pr_debug("template is %lx\n", (unsigned long)op);
  252. switch (op) {
  253. case OP_REPEAT:
  254. ret = next_bits(&p, &rep, REPEAT_BITS);
  255. if (ret)
  256. return ret;
  257. if (p.out == out) /* no previous bytes */
  258. return -EINVAL;
  259. /* copy rep + 1 */
  260. rep++;
  261. if (rep * 8 > p.olen)
  262. return -ENOSPC;
  263. while (rep-- > 0) {
  264. memcpy(p.out, p.out - 8, 8);
  265. p.out += 8;
  266. p.olen -= 8;
  267. }
  268. if (sw842_template_counts)
  269. atomic_inc(&template_repeat_count);
  270. break;
  271. case OP_ZEROS:
  272. if (8 > p.olen)
  273. return -ENOSPC;
  274. memset(p.out, 0, 8);
  275. p.out += 8;
  276. p.olen -= 8;
  277. if (sw842_template_counts)
  278. atomic_inc(&template_zeros_count);
  279. break;
  280. case OP_SHORT_DATA:
  281. ret = next_bits(&p, &bytes, SHORT_DATA_BITS);
  282. if (ret)
  283. return ret;
  284. if (!bytes || bytes > SHORT_DATA_BITS_MAX)
  285. return -EINVAL;
  286. while (bytes-- > 0) {
  287. ret = next_bits(&p, &tmp, 8);
  288. if (ret)
  289. return ret;
  290. *p.out = (u8)tmp;
  291. p.out++;
  292. p.olen--;
  293. }
  294. if (sw842_template_counts)
  295. atomic_inc(&template_short_data_count);
  296. break;
  297. case OP_END:
  298. if (sw842_template_counts)
  299. atomic_inc(&template_end_count);
  300. break;
  301. default: /* use template */
  302. ret = do_op(&p, op);
  303. if (ret)
  304. return ret;
  305. break;
  306. }
  307. } while (op != OP_END);
  308. /*
  309. * crc(0:31) is saved in compressed data starting with the
  310. * next bit after End of stream template.
  311. */
  312. ret = next_bits(&p, &crc, CRC_BITS);
  313. if (ret)
  314. return ret;
  315. /*
  316. * Validate CRC saved in compressed data.
  317. */
  318. if (crc != (u64)crc32_be(0, out, total - p.olen)) {
  319. pr_debug("CRC mismatch for decompression\n");
  320. return -EINVAL;
  321. }
  322. if (unlikely((total - p.olen) > UINT_MAX))
  323. return -ENOSPC;
  324. *olen = total - p.olen;
  325. return 0;
  326. }
  327. EXPORT_SYMBOL_GPL(sw842_decompress);
  328. static int __init sw842_init(void)
  329. {
  330. if (sw842_template_counts)
  331. sw842_debugfs_create();
  332. return 0;
  333. }
  334. module_init(sw842_init);
  335. static void __exit sw842_exit(void)
  336. {
  337. if (sw842_template_counts)
  338. sw842_debugfs_remove();
  339. }
  340. module_exit(sw842_exit);
  341. MODULE_LICENSE("GPL");
  342. MODULE_DESCRIPTION("Software 842 Decompressor");
  343. MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");