lib: add software 842 compression/decompression

Add 842-format software compression and decompression functions.
Update the MAINTAINERS 842 section to include the new files.

The 842 compression function can compress any input data into the 842
compression format.  The 842 decompression function can decompress any
standard-format 842 compressed data - specifically, either a compressed
data buffer created by the 842 software compression function, or a
compressed data buffer created by the 842 hardware compressor (located
in PowerPC coprocessors).

The 842 compressed data format is explained in the header comments.

This is used in a later patch to provide a full software 842 compression
and decompression crypto interface.

Signed-off-by: Dan Streetman <ddstreet@ieee.org>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

1 files changed, 405 insertions, 0 deletions

diff --git a/lib/842/842_decompress.c b/lib/842/842_decompress.c
new file mode 100644
index 000000000000..6b2b45aecde3
--- /dev/null
+++ b/lib/842/842_decompress.c
@@ -0,0 +1,405 @@
+/*
+ * 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)) :   \
+         WARN(1, "pr_debug param err invalid size %x\n", s))
+
+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 % fsize;
+
+                /* 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;
+        }
+
+        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;
+}
+
+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;
+        }
+}
+
+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("Interal 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;
+
+        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);
+
+        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>");