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
21static 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
50struct 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
65static int next_bits(struct sw842_param *p, u64 *d, u8 n);
66
67static 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
87static 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
131static 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
163static 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
212static 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
226static 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 */
277int 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}
397EXPORT_SYMBOL_GPL(sw842_decompress);
398
399static int __init sw842_init(void)
400{
401	if (sw842_template_counts)
402		sw842_debugfs_create();
403
404	return 0;
405}
406module_init(sw842_init);
407
408static void __exit sw842_exit(void)
409{
410	if (sw842_template_counts)
411		sw842_debugfs_remove();
412}
413module_exit(sw842_exit);
414
415MODULE_LICENSE("GPL");
416MODULE_DESCRIPTION("Software 842 Decompressor");
417MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");
418