GNU Linux-libre 5.19-rc6-gnu
[releases.git] / lib / 842 / 842_decompress.c
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>");