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