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, d: &tmp, n: n - s); |
78 | if (ret) |
79 | return ret; |
80 | ret = next_bits(p, d, n: 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, s: 32); |
101 | else if (p->ilen < 8 && bits > 32 && bits <= 56) |
102 | return __split_next_bits(p, d, n, s: 16); |
103 | else if (p->ilen < 4 && bits > 16 && bits <= 24) |
104 | return __split_next_bits(p, d, n, s: 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, d: &v, n: 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, d: &index, n: 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, size: 2, I2_BITS, I2_FIFO_SIZE); |
217 | case 4: |
218 | return __do_index(p, size: 4, I4_BITS, I4_FIFO_SIZE); |
219 | case 8: |
220 | return __do_index(p, size: 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, n: op & OP_AMOUNT); |
241 | break; |
242 | case OP_ACTION_INDEX: |
243 | ret = do_index(p, n: 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(v: &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: &p, d: &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: &p, d: &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(v: &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(v: &template_zeros_count); |
338 | |
339 | break; |
340 | case OP_SHORT_DATA: |
341 | ret = next_bits(p: &p, d: &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: &p, d: &tmp, n: 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(v: &template_short_data_count); |
359 | |
360 | break; |
361 | case OP_END: |
362 | if (sw842_template_counts) |
363 | atomic_inc(v: &template_end_count); |
364 | |
365 | break; |
366 | default: /* use template */ |
367 | ret = do_op(p: &p, o: 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: &p, d: &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(crc: 0, p: out, len: 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 | |