Enabling test cases execution as part of daily job
[kvmfornfv.git] / kernel / lib / 842 / 842_decompress.c
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>");