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