/* * 842 Software Decompression * * Copyright (C) 2015 Dan Streetman, IBM Corp * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * See 842.h for details of the 842 compressed format. */ #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt #define MODULE_NAME "842_decompress" #include "842.h" #include "842_debugfs.h" /* rolling fifo sizes */ #define I2_FIFO_SIZE (2 * (1 << I2_BITS)) #define I4_FIFO_SIZE (4 * (1 << I4_BITS)) #define I8_FIFO_SIZE (8 * (1 << I8_BITS)) static u8 decomp_ops[OPS_MAX][4] = { { D8, N0, N0, N0 }, { D4, D2, I2, N0 }, { D4, I2, D2, N0 }, { D4, I2, I2, N0 }, { D4, I4, N0, N0 }, { D2, I2, D4, N0 }, { D2, I2, D2, I2 }, { D2, I2, I2, D2 }, { D2, I2, I2, I2 }, { D2, I2, I4, N0 }, { I2, D2, D4, N0 }, { I2, D4, I2, N0 }, { I2, D2, I2, D2 }, { I2, D2, I2, I2 }, { I2, D2, I4, N0 }, { I2, I2, D4, N0 }, { I2, I2, D2, I2 }, { I2, I2, I2, D2 }, { I2, I2, I2, I2 }, { I2, I2, I4, N0 }, { I4, D4, N0, N0 }, { I4, D2, I2, N0 }, { I4, I2, D2, N0 }, { I4, I2, I2, N0 }, { I4, I4, N0, N0 }, { I8, N0, N0, N0 } }; struct sw842_param { u8 *in; u8 bit; u64 ilen; u8 *out; u8 *ostart; u64 olen; }; #define beN_to_cpu(d, s) \ ((s) == 2 ? be16_to_cpu(get_unaligned((__be16 *)d)) : \ (s) == 4 ? be32_to_cpu(get_unaligned((__be32 *)d)) : \ (s) == 8 ? be64_to_cpu(get_unaligned((__be64 *)d)) : \ 0) static int next_bits(struct sw842_param *p, u64 *d, u8 n); static int __split_next_bits(struct sw842_param *p, u64 *d, u8 n, u8 s) { u64 tmp = 0; int ret; if (n <= s) { pr_debug("split_next_bits invalid n %u s %u\n", n, s); return -EINVAL; } ret = next_bits(p, &tmp, n - s); if (ret) return ret; ret = next_bits(p, d, s); if (ret) return ret; *d |= tmp << s; return 0; } static int next_bits(struct sw842_param *p, u64 *d, u8 n) { u8 *in = p->in, b = p->bit, bits = b + n; if (n > 64) { pr_debug("next_bits invalid n %u\n", n); return -EINVAL; } /* split this up if reading > 8 bytes, or if we're at the end of * the input buffer and would read past the end */ if (bits > 64) return __split_next_bits(p, d, n, 32); else if (p->ilen < 8 && bits > 32 && bits <= 56) return __split_next_bits(p, d, n, 16); else if (p->ilen < 4 && bits > 16 && bits <= 24) return __split_next_bits(p, d, n, 8); if (DIV_ROUND_UP(bits, 8) > p->ilen) return -EOVERFLOW; if (bits <= 8) *d = *in >> (8 - bits); else if (bits <= 16) *d = be16_to_cpu(get_unaligned((__be16 *)in)) >> (16 - bits); else if (bits <= 32) *d = be32_to_cpu(get_unaligned((__be32 *)in)) >> (32 - bits); else *d = be64_to_cpu(get_unaligned((__be64 *)in)) >> (64 - bits); *d &= GENMASK_ULL(n - 1, 0); p->bit += n; if (p->bit > 7) { p->in += p->bit / 8; p->ilen -= p->bit / 8; p->bit %= 8; } return 0; } static int do_data(struct sw842_param *p, u8 n) { u64 v; int ret; if (n > p->olen) return -ENOSPC; ret = next_bits(p, &v, n * 8); if (ret) return ret; switch (n) { case 2: put_unaligned(cpu_to_be16((u16)v), (__be16 *)p->out); break; case 4: put_unaligned(cpu_to_be32((u32)v), (__be32 *)p->out); break; case 8: put_unaligned(cpu_to_be64((u64)v), (__be64 *)p->out); break; default: return -EINVAL; } p->out += n; p->olen -= n; return 0; } static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize) { u64 index, offset, total = round_down(p->out - p->ostart, 8); int ret; ret = next_bits(p, &index, bits); if (ret) return ret; offset = index * size; /* a ring buffer of fsize is used; correct the offset */ if (total > fsize) { /* this is where the current fifo is */ u64 section = round_down(total, fsize); /* the current pos in the fifo */ u64 pos = total - section; /* if the offset is past/at the pos, we need to * go back to the last fifo section */ if (offset >= pos) section -= fsize; offset += section; } if (offset + size > total) { pr_debug("index%x %lx points past end %lx\n", size, (unsigned long)offset, (unsigned long)total); return -EINVAL; } if (size != 2 && size != 4 && size != 8) WARN(1, "__do_index invalid size %x\n", size); else pr_debug("index%x to %lx off %lx adjoff %lx tot %lx data %lx\n", size, (unsigned long)index, (unsigned long)(index * size), (unsigned long)offset, (unsigned long)total, (unsigned long)beN_to_cpu(&p->ostart[offset], size)); memcpy(p->out, &p->ostart[offset], size); p->out += size; p->olen -= size; return 0; } static int do_index(struct sw842_param *p, u8 n) { switch (n) { case 2: return __do_index(p, 2, I2_BITS, I2_FIFO_SIZE); case 4: return __do_index(p, 4, I4_BITS, I4_FIFO_SIZE); case 8: return __do_index(p, 8, I8_BITS, I8_FIFO_SIZE); default: return -EINVAL; } } static int do_op(struct sw842_param *p, u8 o) { int i, ret = 0; if (o >= OPS_MAX) return -EINVAL; for (i = 0; i < 4; i++) { u8 op = decomp_ops[o][i]; pr_debug("op is %x\n", op); switch (op & OP_ACTION) { case OP_ACTION_DATA: ret = do_data(p, op & OP_AMOUNT); break; case OP_ACTION_INDEX: ret = do_index(p, op & OP_AMOUNT); break; case OP_ACTION_NOOP: break; default: pr_err("Internal error, invalid op %x\n", op); return -EINVAL; } if (ret) return ret; } if (sw842_template_counts) atomic_inc(&template_count[o]); return 0; } /** * sw842_decompress * * Decompress the 842-compressed buffer of length @ilen at @in * to the output buffer @out, using no more than @olen bytes. * * The compressed buffer must be only a single 842-compressed buffer, * with the standard format described in the comments in 842.h * Processing will stop when the 842 "END" template is detected, * not the end of the buffer. * * Returns: 0 on success, error on failure. The @olen parameter * will contain the number of output bytes written on success, or * 0 on error. */ int sw842_decompress(const u8 *in, unsigned int ilen, u8 *out, unsigned int *olen) { struct sw842_param p; int ret; u64 op, rep, tmp, bytes, total; u64 crc; p.in = (u8 *)in; p.bit = 0; p.ilen = ilen; p.out = out; p.ostart = out; p.olen = *olen; total = p.olen; *olen = 0; do { ret = next_bits(&p, &op, OP_BITS); if (ret) return ret; pr_debug("template is %lx\n", (unsigned long)op); switch (op) { case OP_REPEAT: ret = next_bits(&p, &rep, REPEAT_BITS); if (ret) return ret; if (p.out == out) /* no previous bytes */ return -EINVAL; /* copy rep + 1 */ rep++; if (rep * 8 > p.olen) return -ENOSPC; while (rep-- > 0) { memcpy(p.out, p.out - 8, 8); p.out += 8; p.olen -= 8; } if (sw842_template_counts) atomic_inc(&template_repeat_count); break; case OP_ZEROS: if (8 > p.olen) return -ENOSPC; memset(p.out, 0, 8); p.out += 8; p.olen -= 8; if (sw842_template_counts) atomic_inc(&template_zeros_count); break; case OP_SHORT_DATA: ret = next_bits(&p, &bytes, SHORT_DATA_BITS); if (ret) return ret; if (!bytes || bytes > SHORT_DATA_BITS_MAX) return -EINVAL; while (bytes-- > 0) { ret = next_bits(&p, &tmp, 8); if (ret) return ret; *p.out = (u8)tmp; p.out++; p.olen--; } if (sw842_template_counts) atomic_inc(&template_short_data_count); break; case OP_END: if (sw842_template_counts) atomic_inc(&template_end_count); break; default: /* use template */ ret = do_op(&p, op); if (ret) return ret; break; } } while (op != OP_END); /* * crc(0:31) is saved in compressed data starting with the * next bit after End of stream template. */ ret = next_bits(&p, &crc, CRC_BITS); if (ret) return ret; /* * Validate CRC saved in compressed data. */ if (crc != (u64)crc32_be(0, out, total - p.olen)) { pr_debug("CRC mismatch for decompression\n"); return -EINVAL; } if (unlikely((total - p.olen) > UINT_MAX)) return -ENOSPC; *olen = total - p.olen; return 0; } EXPORT_SYMBOL_GPL(sw842_decompress); static int __init sw842_init(void) { if (sw842_template_counts) sw842_debugfs_create(); return 0; } module_init(sw842_init); static void __exit sw842_exit(void) { if (sw842_template_counts) sw842_debugfs_remove(); } module_exit(sw842_exit); MODULE_LICENSE("GPL"); MODULE_DESCRIPTION("Software 842 Decompressor"); MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");