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          0)
  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         if (size != 2 && size != 4 && size != 8)
 206                 WARN(1, "__do_index invalid size %x\n", size);
 207         else
 208                 pr_debug("index%x to %lx off %lx adjoff %lx tot %lx data %lx\n",
 209                          size, (unsigned long)index,
 210                          (unsigned long)(index * size), (unsigned long)offset,
 211                          (unsigned long)total,
 212                          (unsigned long)beN_to_cpu(&p->ostart[offset], size));
 213
 214         memcpy(p->out, &p->ostart[offset], size);
 215         p->out += size;
 216         p->olen -= size;
 217
 218         return 0;
 219 }
 220
 221 static int do_index(struct sw842_param *p, u8 n)
 222 {
 223         switch (n) {
 224         case 2:
 225                 return __do_index(p, 2, I2_BITS, I2_FIFO_SIZE);
 226         case 4:
 227                 return __do_index(p, 4, I4_BITS, I4_FIFO_SIZE);
 228         case 8:
 229                 return __do_index(p, 8, I8_BITS, I8_FIFO_SIZE);
 230         default:
 231                 return -EINVAL;
 232         }
 233 }
 234
 235 static int do_op(struct sw842_param *p, u8 o)
 236 {
 237         int i, ret = 0;
 238
 239         if (o >= OPS_MAX)
 240                 return -EINVAL;
 241
 242         for (i = 0; i < 4; i++) {
 243                 u8 op = decomp_ops[o][i];
 244
 245                 pr_debug("op is %x\n", op);
 246
 247                 switch (op & OP_ACTION) {
 248                 case OP_ACTION_DATA:
 249                         ret = do_data(p, op & OP_AMOUNT);
 250                         break;
 251                 case OP_ACTION_INDEX:
 252                         ret = do_index(p, op & OP_AMOUNT);
 253                         break;
 254                 case OP_ACTION_NOOP:
 255                         break;
 256                 default:
 257                         pr_err("Internal error, invalid op %x\n", op);
 258                         return -EINVAL;
 259                 }
 260
 261                 if (ret)
 262                         return ret;
 263         }
 264
 265         if (sw842_template_counts)
 266                 atomic_inc(&template_count[o]);
 267
 268         return 0;
 269 }
 270
 271 /**
 272  * sw842_decompress
 273  *
 274  * Decompress the 842-compressed buffer of length @ilen at @in
 275  * to the output buffer @out, using no more than @olen bytes.
 276  *
 277  * The compressed buffer must be only a single 842-compressed buffer,
 278  * with the standard format described in the comments in 842.h
 279  * Processing will stop when the 842 "END" template is detected,
 280  * not the end of the buffer.
 281  *
 282  * Returns: 0 on success, error on failure.  The @olen parameter
 283  * will contain the number of output bytes written on success, or
 284  * 0 on error.
 285  */
 286 int sw842_decompress(const u8 *in, unsigned int ilen,
 287                      u8 *out, unsigned int *olen)
 288 {
 289         struct sw842_param p;
 290         int ret;
 291         u64 op, rep, tmp, bytes, total;
 292         u64 crc;
 293
 294         p.in = (u8 *)in;
 295         p.bit = 0;
 296         p.ilen = ilen;
 297         p.out = out;
 298         p.ostart = out;
 299         p.olen = *olen;
 300
 301         total = p.olen;
 302
 303         *olen = 0;
 304
 305         do {
 306                 ret = next_bits(&p, &op, OP_BITS);
 307                 if (ret)
 308                         return ret;
 309
 310                 pr_debug("template is %lx\n", (unsigned long)op);
 311
 312                 switch (op) {
 313                 case OP_REPEAT:
 314                         ret = next_bits(&p, &rep, REPEAT_BITS);
 315                         if (ret)
 316                                 return ret;
 317
 318                         if (p.out == out) /* no previous bytes */
 319                                 return -EINVAL;
 320
 321                         /* copy rep + 1 */
 322                         rep++;
 323
 324                         if (rep * 8 > p.olen)
 325                                 return -ENOSPC;
 326
 327                         while (rep-- > 0) {
 328                                 memcpy(p.out, p.out - 8, 8);
 329                                 p.out += 8;
 330                                 p.olen -= 8;
 331                         }
 332
 333                         if (sw842_template_counts)
 334                                 atomic_inc(&template_repeat_count);
 335
 336                         break;
 337                 case OP_ZEROS:
 338                         if (8 > p.olen)
 339                                 return -ENOSPC;
 340
 341                         memset(p.out, 0, 8);
 342                         p.out += 8;
 343                         p.olen -= 8;
 344
 345                         if (sw842_template_counts)
 346                                 atomic_inc(&template_zeros_count);
 347
 348                         break;
 349                 case OP_SHORT_DATA:
 350                         ret = next_bits(&p, &bytes, SHORT_DATA_BITS);
 351                         if (ret)
 352                                 return ret;
 353
 354                         if (!bytes || bytes > SHORT_DATA_BITS_MAX)
 355                                 return -EINVAL;
 356
 357                         while (bytes-- > 0) {
 358                                 ret = next_bits(&p, &tmp, 8);
 359                                 if (ret)
 360                                         return ret;
 361                                 *p.out = (u8)tmp;
 362                                 p.out++;
 363                                 p.olen--;
 364                         }
 365
 366                         if (sw842_template_counts)
 367                                 atomic_inc(&template_short_data_count);
 368
 369                         break;
 370                 case OP_END:
 371                         if (sw842_template_counts)
 372                                 atomic_inc(&template_end_count);
 373
 374                         break;
 375                 default: /* use template */
 376                         ret = do_op(&p, op);
 377                         if (ret)
 378                                 return ret;
 379                         break;
 380                 }
 381         } while (op != OP_END);
 382
 383         /*
 384          * crc(0:31) is saved in compressed data starting with the
 385          * next bit after End of stream template.
 386          */
 387         ret = next_bits(&p, &crc, CRC_BITS);
 388         if (ret)
 389                 return ret;
 390
 391         /*
 392          * Validate CRC saved in compressed data.
 393          */
 394         if (crc != (u64)crc32_be(0, out, total - p.olen)) {
 395                 pr_debug("CRC mismatch for decompression\n");
 396                 return -EINVAL;
 397         }
 398
 399         if (unlikely((total - p.olen) > UINT_MAX))
 400                 return -ENOSPC;
 401
 402         *olen = total - p.olen;
 403
 404         return 0;
 405 }
 406 EXPORT_SYMBOL_GPL(sw842_decompress);
 407
 408 static int __init sw842_init(void)
 409 {
 410         if (sw842_template_counts)
 411                 sw842_debugfs_create();
 412
 413         return 0;
 414 }
 415 module_init(sw842_init);
 416
 417 static void __exit sw842_exit(void)
 418 {
 419         if (sw842_template_counts)
 420                 sw842_debugfs_remove();
 421 }
 422 module_exit(sw842_exit);
 423
 424 MODULE_LICENSE("GPL");
 425 MODULE_DESCRIPTION("Software 842 Decompressor");
 426 MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");