kernel/lib/842/842_decompress.c

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