xref: /linux/lib/842/842_decompress.c (revision 75bf465f0bc33e9b776a46d6a1b9b990f5fb7c37)
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 
__split_next_bits(struct sw842_param * p,u64 * d,u8 n,u8 s)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 
next_bits(struct sw842_param * p,u64 * d,u8 n)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 
do_data(struct sw842_param * p,u8 n)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 
__do_index(struct sw842_param * p,u8 size,u8 bits,u64 fsize)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 
do_index(struct sw842_param * p,u8 n)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 
do_op(struct sw842_param * p,u8 o)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  */
sw842_decompress(const u8 * in,unsigned int ilen,u8 * out,unsigned int * olen)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 
sw842_init(void)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 
sw842_exit(void)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