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>"); 427