blob: a7f278d2ed8ff21dbf64c6f0193e60c0ea29d5ac [file] [log] [blame]
Dan Streetman2da572c2015-05-07 13:49:14 -04001/*
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
30static 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
59struct 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)) : \
Dan Streetman5ca636b2015-12-21 12:52:10 -050072 0)
Dan Streetman2da572c2015-05-07 13:49:14 -040073
74static int next_bits(struct sw842_param *p, u64 *d, u8 n);
75
76static 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
96static 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
140static 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
172static 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 */
Dan Streetmanca7fc7e2015-05-11 18:53:36 -0400188 u64 pos = total - section;
Dan Streetman2da572c2015-05-07 13:49:14 -0400189
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
Dan Streetman5ca636b2015-12-21 12:52:10 -0500205 if (size != 2 && size != 4 && size != 8)
206 WARN(1, "__do_index invalid size %x\n", size);
207 else
208 pr_debug("index%x to %lx off %lx adjoff %lx tot %lx data %lx\n",
209 size, (unsigned long)index,
210 (unsigned long)(index * size), (unsigned long)offset,
211 (unsigned long)total,
212 (unsigned long)beN_to_cpu(&p->ostart[offset], size));
Dan Streetman2da572c2015-05-07 13:49:14 -0400213
214 memcpy(p->out, &p->ostart[offset], size);
215 p->out += size;
216 p->olen -= size;
217
218 return 0;
219}
220
Dan Streetmanf7ead7b2015-05-11 07:22:35 -0400221static int do_index(struct sw842_param *p, u8 n)
Dan Streetman2da572c2015-05-07 13:49:14 -0400222{
223 switch (n) {
224 case 2:
225 return __do_index(p, 2, I2_BITS, I2_FIFO_SIZE);
226 case 4:
227 return __do_index(p, 4, I4_BITS, I4_FIFO_SIZE);
228 case 8:
229 return __do_index(p, 8, I8_BITS, I8_FIFO_SIZE);
230 default:
231 return -EINVAL;
232 }
233}
234
Dan Streetmanf7ead7b2015-05-11 07:22:35 -0400235static int do_op(struct sw842_param *p, u8 o)
Dan Streetman2da572c2015-05-07 13:49:14 -0400236{
237 int i, ret = 0;
238
239 if (o >= OPS_MAX)
240 return -EINVAL;
241
242 for (i = 0; i < 4; i++) {
243 u8 op = decomp_ops[o][i];
244
245 pr_debug("op is %x\n", op);
246
247 switch (op & OP_ACTION) {
248 case OP_ACTION_DATA:
249 ret = do_data(p, op & OP_AMOUNT);
250 break;
251 case OP_ACTION_INDEX:
252 ret = do_index(p, op & OP_AMOUNT);
253 break;
254 case OP_ACTION_NOOP:
255 break;
256 default:
257 pr_err("Interal error, invalid op %x\n", op);
258 return -EINVAL;
259 }
260
261 if (ret)
262 return ret;
263 }
264
265 if (sw842_template_counts)
266 atomic_inc(&template_count[o]);
267
268 return 0;
269}
270
271/**
272 * sw842_decompress
273 *
274 * Decompress the 842-compressed buffer of length @ilen at @in
275 * to the output buffer @out, using no more than @olen bytes.
276 *
277 * The compressed buffer must be only a single 842-compressed buffer,
278 * with the standard format described in the comments in 842.h
279 * Processing will stop when the 842 "END" template is detected,
280 * not the end of the buffer.
281 *
282 * Returns: 0 on success, error on failure. The @olen parameter
283 * will contain the number of output bytes written on success, or
284 * 0 on error.
285 */
286int sw842_decompress(const u8 *in, unsigned int ilen,
287 u8 *out, unsigned int *olen)
288{
289 struct sw842_param p;
290 int ret;
291 u64 op, rep, tmp, bytes, total;
Haren Myneniea0b3982015-10-08 13:45:51 -0700292 u64 crc;
Dan Streetman2da572c2015-05-07 13:49:14 -0400293
294 p.in = (u8 *)in;
295 p.bit = 0;
296 p.ilen = ilen;
297 p.out = out;
298 p.ostart = out;
299 p.olen = *olen;
300
301 total = p.olen;
302
303 *olen = 0;
304
305 do {
306 ret = next_bits(&p, &op, OP_BITS);
307 if (ret)
308 return ret;
309
310 pr_debug("template is %lx\n", (unsigned long)op);
311
312 switch (op) {
313 case OP_REPEAT:
314 ret = next_bits(&p, &rep, REPEAT_BITS);
315 if (ret)
316 return ret;
317
318 if (p.out == out) /* no previous bytes */
319 return -EINVAL;
320
321 /* copy rep + 1 */
322 rep++;
323
324 if (rep * 8 > p.olen)
325 return -ENOSPC;
326
327 while (rep-- > 0) {
328 memcpy(p.out, p.out - 8, 8);
329 p.out += 8;
330 p.olen -= 8;
331 }
332
333 if (sw842_template_counts)
334 atomic_inc(&template_repeat_count);
335
336 break;
337 case OP_ZEROS:
338 if (8 > p.olen)
339 return -ENOSPC;
340
341 memset(p.out, 0, 8);
342 p.out += 8;
343 p.olen -= 8;
344
345 if (sw842_template_counts)
346 atomic_inc(&template_zeros_count);
347
348 break;
349 case OP_SHORT_DATA:
350 ret = next_bits(&p, &bytes, SHORT_DATA_BITS);
351 if (ret)
352 return ret;
353
354 if (!bytes || bytes > SHORT_DATA_BITS_MAX)
355 return -EINVAL;
356
357 while (bytes-- > 0) {
358 ret = next_bits(&p, &tmp, 8);
359 if (ret)
360 return ret;
361 *p.out = (u8)tmp;
362 p.out++;
363 p.olen--;
364 }
365
366 if (sw842_template_counts)
367 atomic_inc(&template_short_data_count);
368
369 break;
370 case OP_END:
371 if (sw842_template_counts)
372 atomic_inc(&template_end_count);
373
374 break;
375 default: /* use template */
376 ret = do_op(&p, op);
377 if (ret)
378 return ret;
379 break;
380 }
381 } while (op != OP_END);
382
Haren Myneniea0b3982015-10-08 13:45:51 -0700383 /*
384 * crc(0:31) is saved in compressed data starting with the
385 * next bit after End of stream template.
386 */
387 ret = next_bits(&p, &crc, CRC_BITS);
388 if (ret)
389 return ret;
390
391 /*
392 * Validate CRC saved in compressed data.
393 */
394 if (crc != (u64)crc32_be(0, out, total - p.olen)) {
395 pr_debug("CRC mismatch for decompression\n");
396 return -EINVAL;
397 }
398
Dan Streetman2da572c2015-05-07 13:49:14 -0400399 if (unlikely((total - p.olen) > UINT_MAX))
400 return -ENOSPC;
401
402 *olen = total - p.olen;
403
404 return 0;
405}
406EXPORT_SYMBOL_GPL(sw842_decompress);
407
408static int __init sw842_init(void)
409{
410 if (sw842_template_counts)
411 sw842_debugfs_create();
412
413 return 0;
414}
415module_init(sw842_init);
416
417static void __exit sw842_exit(void)
418{
419 if (sw842_template_counts)
420 sw842_debugfs_remove();
421}
422module_exit(sw842_exit);
423
424MODULE_LICENSE("GPL");
425MODULE_DESCRIPTION("Software 842 Decompressor");
426MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");