xref: /linux/lib/842/842_decompress.c (revision f7ead7b4) 
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 % fsize;
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 
289 	p.in = (u8 *)in;
290 	p.bit = 0;
291 	p.ilen = ilen;
292 	p.out = out;
293 	p.ostart = out;
294 	p.olen = *olen;
295 
296 	total = p.olen;
297 
298 	*olen = 0;
299 
300 	do {
301 		ret = next_bits(&p, &op, OP_BITS);
302 		if (ret)
303 			return ret;
304 
305 		pr_debug("template is %lx\n", (unsigned long)op);
306 
307 		switch (op) {
308 		case OP_REPEAT:
309 			ret = next_bits(&p, &rep, REPEAT_BITS);
310 			if (ret)
311 				return ret;
312 
313 			if (p.out == out) /* no previous bytes */
314 				return -EINVAL;
315 
316 			/* copy rep + 1 */
317 			rep++;
318 
319 			if (rep * 8 > p.olen)
320 				return -ENOSPC;
321 
322 			while (rep-- > 0) {
323 				memcpy(p.out, p.out - 8, 8);
324 				p.out += 8;
325 				p.olen -= 8;
326 			}
327 
328 			if (sw842_template_counts)
329 				atomic_inc(&template_repeat_count);
330 
331 			break;
332 		case OP_ZEROS:
333 			if (8 > p.olen)
334 				return -ENOSPC;
335 
336 			memset(p.out, 0, 8);
337 			p.out += 8;
338 			p.olen -= 8;
339 
340 			if (sw842_template_counts)
341 				atomic_inc(&template_zeros_count);
342 
343 			break;
344 		case OP_SHORT_DATA:
345 			ret = next_bits(&p, &bytes, SHORT_DATA_BITS);
346 			if (ret)
347 				return ret;
348 
349 			if (!bytes || bytes > SHORT_DATA_BITS_MAX)
350 				return -EINVAL;
351 
352 			while (bytes-- > 0) {
353 				ret = next_bits(&p, &tmp, 8);
354 				if (ret)
355 					return ret;
356 				*p.out = (u8)tmp;
357 				p.out++;
358 				p.olen--;
359 			}
360 
361 			if (sw842_template_counts)
362 				atomic_inc(&template_short_data_count);
363 
364 			break;
365 		case OP_END:
366 			if (sw842_template_counts)
367 				atomic_inc(&template_end_count);
368 
369 			break;
370 		default: /* use template */
371 			ret = do_op(&p, op);
372 			if (ret)
373 				return ret;
374 			break;
375 		}
376 	} while (op != OP_END);
377 
378 	if (unlikely((total - p.olen) > UINT_MAX))
379 		return -ENOSPC;
380 
381 	*olen = total - p.olen;
382 
383 	return 0;
384 }
385 EXPORT_SYMBOL_GPL(sw842_decompress);
386 
387 static int __init sw842_init(void)
388 {
389 	if (sw842_template_counts)
390 		sw842_debugfs_create();
391 
392 	return 0;
393 }
394 module_init(sw842_init);
395 
396 static void __exit sw842_exit(void)
397 {
398 	if (sw842_template_counts)
399 		sw842_debugfs_remove();
400 }
401 module_exit(sw842_exit);
402 
403 MODULE_LICENSE("GPL");
404 MODULE_DESCRIPTION("Software 842 Decompressor");
405 MODULE_AUTHOR("Dan Streetman <ddstreet@ieee.org>");
406