lib/842/842_decompress.c

0001 // SPDX-License-Identifier: GPL-2.0-or-later
0002 /*
0003  * 842 Software Decompression
0004  *
0005  * Copyright (C) 2015 Dan Streetman, IBM Corp
0006  *
0007  * See 842.h for details of the 842 compressed format.
0008  */
0009
0010 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
0011 #define MODULE_NAME "842_decompress"
0012
0013 #include "842.h"
0014 #include "842_debugfs.h"
0015
0016 /* rolling fifo sizes */
0017 #define I2_FIFO_SIZE    (2 * (1 << I2_BITS))
0018 #define I4_FIFO_SIZE    (4 * (1 << I4_BITS))
0019 #define I8_FIFO_SIZE    (8 * (1 << I8_BITS))
0020
0021 static u8 decomp_ops[OPS_MAX][4] = {
0022     { D8, N0, N0, N0 },
0023     { D4, D2, I2, N0 },
0024     { D4, I2, D2, N0 },
0025     { D4, I2, I2, N0 },
0026     { D4, I4, N0, N0 },
0027     { D2, I2, D4, N0 },
0028     { D2, I2, D2, I2 },
0029     { D2, I2, I2, D2 },
0030     { D2, I2, I2, I2 },
0031     { D2, I2, I4, N0 },
0032     { I2, D2, D4, N0 },
0033     { I2, D4, I2, N0 },
0034     { I2, D2, I2, D2 },
0035     { I2, D2, I2, I2 },
0036     { I2, D2, I4, N0 },
0037     { I2, I2, D4, N0 },
0038     { I2, I2, D2, I2 },
0039     { I2, I2, I2, D2 },
0040     { I2, I2, I2, I2 },
0041     { I2, I2, I4, N0 },
0042     { I4, D4, N0, N0 },
0043     { I4, D2, I2, N0 },
0044     { I4, I2, D2, N0 },
0045     { I4, I2, I2, N0 },
0046     { I4, I4, N0, N0 },
0047     { I8, N0, N0, N0 }
0048 };
0049
0050 struct sw842_param {
0051     u8 *in;
0052     u8 bit;
0053     u64 ilen;
0054     u8 *out;
0055     u8 *ostart;
0056     u64 olen;
0057 };
0058
0059 #define beN_to_cpu(d, s)                    \
0060     ((s) == 2 ? be16_to_cpu(get_unaligned((__be16 *)d)) :   \
0061      (s) == 4 ? be32_to_cpu(get_unaligned((__be32 *)d)) :   \
0062      (s) == 8 ? be64_to_cpu(get_unaligned((__be64 *)d)) :   \
0063      0)
0064
0065 static int next_bits(struct sw842_param *p, u64 *d, u8 n);
0066
0067 static int __split_next_bits(struct sw842_param *p, u64 *d, u8 n, u8 s)
0068 {
0069     u64 tmp = 0;
0070     int ret;
0071
0072     if (n <= s) {
0073         pr_debug("split_next_bits invalid n %u s %u\n", n, s);
0074         return -EINVAL;
0075     }
0076
0077     ret = next_bits(p, &tmp, n - s);
0078     if (ret)
0079         return ret;
0080     ret = next_bits(p, d, s);
0081     if (ret)
0082         return ret;
0083     *d |= tmp << s;
0084     return 0;
0085 }
0086
0087 static int next_bits(struct sw842_param *p, u64 *d, u8 n)
0088 {
0089     u8 *in = p->in, b = p->bit, bits = b + n;
0090
0091     if (n > 64) {
0092         pr_debug("next_bits invalid n %u\n", n);
0093         return -EINVAL;
0094     }
0095
0096     /* split this up if reading > 8 bytes, or if we're at the end of
0097      * the input buffer and would read past the end
0098      */
0099     if (bits > 64)
0100         return __split_next_bits(p, d, n, 32);
0101     else if (p->ilen < 8 && bits > 32 && bits <= 56)
0102         return __split_next_bits(p, d, n, 16);
0103     else if (p->ilen < 4 && bits > 16 && bits <= 24)
0104         return __split_next_bits(p, d, n, 8);
0105
0106     if (DIV_ROUND_UP(bits, 8) > p->ilen)
0107         return -EOVERFLOW;
0108
0109     if (bits <= 8)
0110         *d = *in >> (8 - bits);
0111     else if (bits <= 16)
0112         *d = be16_to_cpu(get_unaligned((__be16 *)in)) >> (16 - bits);
0113     else if (bits <= 32)
0114         *d = be32_to_cpu(get_unaligned((__be32 *)in)) >> (32 - bits);
0115     else
0116         *d = be64_to_cpu(get_unaligned((__be64 *)in)) >> (64 - bits);
0117
0118     *d &= GENMASK_ULL(n - 1, 0);
0119
0120     p->bit += n;
0121
0122     if (p->bit > 7) {
0123         p->in += p->bit / 8;
0124         p->ilen -= p->bit / 8;
0125         p->bit %= 8;
0126     }
0127
0128     return 0;
0129 }
0130
0131 static int do_data(struct sw842_param *p, u8 n)
0132 {
0133     u64 v;
0134     int ret;
0135
0136     if (n > p->olen)
0137         return -ENOSPC;
0138
0139     ret = next_bits(p, &v, n * 8);
0140     if (ret)
0141         return ret;
0142
0143     switch (n) {
0144     case 2:
0145         put_unaligned(cpu_to_be16((u16)v), (__be16 *)p->out);
0146         break;
0147     case 4:
0148         put_unaligned(cpu_to_be32((u32)v), (__be32 *)p->out);
0149         break;
0150     case 8:
0151         put_unaligned(cpu_to_be64((u64)v), (__be64 *)p->out);
0152         break;
0153     default:
0154         return -EINVAL;
0155     }
0156
0157     p->out += n;
0158     p->olen -= n;
0159
0160     return 0;
0161 }
0162
0163 static int __do_index(struct sw842_param *p, u8 size, u8 bits, u64 fsize)
0164 {
0165     u64 index, offset, total = round_down(p->out - p->ostart, 8);
0166     int ret;
0167
0168     ret = next_bits(p, &index, bits);
0169     if (ret)
0170         return ret;
0171
0172     offset = index * size;
0173
0174     /* a ring buffer of fsize is used; correct the offset */
0175     if (total > fsize) {
0176         /* this is where the current fifo is */
0177         u64 section = round_down(total, fsize);
0178         /* the current pos in the fifo */
0179         u64 pos = total - section;
0180
0181         /* if the offset is past/at the pos, we need to
0182          * go back to the last fifo section
0183          */
0184         if (offset >= pos)
0185             section -= fsize;
0186
0187         offset += section;
0188     }
0189
0190     if (offset + size > total) {
0191         pr_debug("index%x %lx points past end %lx\n", size,
0192              (unsigned long)offset, (unsigned long)total);
0193         return -EINVAL;
0194     }
0195
0196     if (size != 2 && size != 4 && size != 8)
0197         WARN(1, "__do_index invalid size %x\n", size);
0198     else
0199         pr_debug("index%x to %lx off %lx adjoff %lx tot %lx data %lx\n",
0200              size, (unsigned long)index,
0201              (unsigned long)(index * size), (unsigned long)offset,
0202              (unsigned long)total,
0203              (unsigned long)beN_to_cpu(&p->ostart[offset], size));
0204
0205     memcpy(p->out, &p->ostart[offset], size);
0206     p->out += size;
0207     p->olen -= size;
0208
0209     return 0;
0210 }
0211
0212 static int do_index(struct sw842_param *p, u8 n)
0213 {
0214     switch (n) {
0215     case 2:
0216         return __do_index(p, 2, I2_BITS, I2_FIFO_SIZE);
0217     case 4:
0218         return __do_index(p, 4, I4_BITS, I4_FIFO_SIZE);
0219     case 8:
0220         return __do_index(p, 8, I8_BITS, I8_FIFO_SIZE);
0221     default:
0222         return -EINVAL;
0223     }
0224 }
0225
0226 static int do_op(struct sw842_param *p, u8 o)
0227 {
0228     int i, ret = 0;
0229
0230     if (o >= OPS_MAX)
0231         return -EINVAL;
0232
0233     for (i = 0; i < 4; i++) {
0234         u8 op = decomp_ops[o][i];
0235
0236         pr_debug("op is %x\n", op);
0237
0238         switch (op & OP_ACTION) {
0239         case OP_ACTION_DATA:
0240             ret = do_data(p, op & OP_AMOUNT);
0241             break;
0242         case OP_ACTION_INDEX:
0243             ret = do_index(p, op & OP_AMOUNT);
0244             break;
0245         case OP_ACTION_NOOP:
0246             break;
0247         default:
0248             pr_err("Internal error, invalid op %x\n", op);
0249             return -EINVAL;
0250         }
0251
0252         if (ret)
0253             return ret;
0254     }
0255
0256     if (sw842_template_counts)
0257         atomic_inc(&template_count[o]);
0258
0259     return 0;
0260 }
0261
0262 /**
0263  * sw842_decompress
0264  *
0265  * Decompress the 842-compressed buffer of length @ilen at @in
0266  * to the output buffer @out, using no more than @olen bytes.
0267  *
0268  * The compressed buffer must be only a single 842-compressed buffer,
0269  * with the standard format described in the comments in 842.h
0270  * Processing will stop when the 842 "END" template is detected,
0271  * not the end of the buffer.
0272  *
0273  * Returns: 0 on success, error on failure.  The @olen parameter
0274  * will contain the number of output bytes written on success, or
0275  * 0 on error.
0276  */
0277 int sw842_decompress(const u8 *in, unsigned int ilen,
0278              u8 *out, unsigned int *olen)
0279 {
0280     struct sw842_param p;
0281     int ret;
0282     u64 op, rep, tmp, bytes, total;
0283     u64 crc;
0284
0285     p.in = (u8 *)in;
0286     p.bit = 0;
0287     p.ilen = ilen;
0288     p.out = out;
0289     p.ostart = out;
0290     p.olen = *olen;
0291
0292     total = p.olen;
0293
0294     *olen = 0;
0295
0296     do {
0297         ret = next_bits(&p, &op, OP_BITS);
0298         if (ret)
0299             return ret;
0300
0301         pr_debug("template is %lx\n", (unsigned long)op);
0302
0303         switch (op) {
0304         case OP_REPEAT:
0305             ret = next_bits(&p, &rep, REPEAT_BITS);
0306             if (ret)
0307                 return ret;
0308
0309             if (p.out == out) /* no previous bytes */
0310                 return -EINVAL;
0311
0312             /* copy rep + 1 */
0313             rep++;
0314
0315             if (rep * 8 > p.olen)
0316                 return -ENOSPC;
0317
0318             while (rep-- > 0) {
0319                 memcpy(p.out, p.out - 8, 8);
0320                 p.out += 8;
0321                 p.olen -= 8;
0322             }
0323
0324             if (sw842_template_counts)
0325                 atomic_inc(&template_repeat_count);
0326
0327             break;
0328         case OP_ZEROS:
0329             if (8 > p.olen)
0330                 return -ENOSPC;
0331
0332             memset(p.out, 0, 8);
0333             p.out += 8;
0334             p.olen -= 8;
0335
0336             if (sw842_template_counts)
0337                 atomic_inc(&template_zeros_count);
0338
0339             break;
0340         case OP_SHORT_DATA:
0341             ret = next_bits(&p, &bytes, SHORT_DATA_BITS);
0342             if (ret)
0343                 return ret;
0344
0345             if (!bytes || bytes > SHORT_DATA_BITS_MAX)
0346                 return -EINVAL;
0347
0348             while (bytes-- > 0) {
0349                 ret = next_bits(&p, &tmp, 8);
0350                 if (ret)
0351                     return ret;
0352                 *p.out = (u8)tmp;
0353                 p.out++;
0354                 p.olen--;
0355             }
0356
0357             if (sw842_template_counts)
0358                 atomic_inc(&template_short_data_count);
0359
0360             break;
0361         case OP_END:
0362             if (sw842_template_counts)
0363                 atomic_inc(&template_end_count);
0364
0365             break;
0366         default: /* use template */
0367             ret = do_op(&p, op);
0368             if (ret)
0369                 return ret;
0370             break;
0371         }
0372     } while (op != OP_END);
0373
0374     /*
0375      * crc(0:31) is saved in compressed data starting with the
0376      * next bit after End of stream template.
0377      */
0378     ret = next_bits(&p, &crc, CRC_BITS);
0379     if (ret)
0380         return ret;
0381
0382     /*
0383      * Validate CRC saved in compressed data.
0384      */
0385     if (crc != (u64)crc32_be(0, out, total - p.olen)) {
0386         pr_debug("CRC mismatch for decompression\n");
0387         return -EINVAL;
0388     }
0389
0390     if (unlikely((total - p.olen) > UINT_MAX))
0391         return -ENOSPC;
0392
0393     *olen = total - p.olen;
0394
0395     return 0;
0396 }
0397 EXPORT_SYMBOL_GPL(sw842_decompress);
0398
0399 static int __init sw842_init(void)
0400 {
0401     if (sw842_template_counts)
0402         sw842_debugfs_create();
0403
0404     return 0;
0405 }
0406 module_init(sw842_init);
0407
0408 static void __exit sw842_exit(void)
0409 {
0410     if (sw842_template_counts)
0411         sw842_debugfs_remove();
0412 }
0413 module_exit(sw842_exit);
0414
0415 MODULE_LICENSE("GPL");
0416 MODULE_DESCRIPTION("Software 842 Decompressor");
0417 MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");