summaryrefslogtreecommitdiffstats
path: root/lib/decompress_unxz.c
blob: abea25310ac730e4da122bc9c1764c81f505943f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
/*
 * Wrapper for decompressing XZ-compressed kernel, initramfs, and initrd
 *
 * Author: Lasse Collin <lasse.collin@tukaani.org>
 *
 * This file has been put into the public domain.
 * You can do whatever you want with this file.
 */

/*
 * Important notes about in-place decompression
 *
 * At least on x86, the kernel is decompressed in place: the compressed data
 * is placed to the end of the output buffer, and the decompressor overwrites
 * most of the compressed data. There must be enough safety margin to
 * guarantee that the write position is always behind the read position.
 *
 * The safety margin for XZ with LZMA2 or BCJ+LZMA2 is calculated below.
 * Note that the margin with XZ is bigger than with Deflate (gzip)!
 *
 * The worst case for in-place decompression is that the beginning of
 * the file is compressed extremely well, and the rest of the file is
 * uncompressible. Thus, we must look for worst-case expansion when the
 * compressor is encoding uncompressible data.
 *
 * The structure of the .xz file in case of a compresed kernel is as follows.
 * Sizes (as bytes) of the fields are in parenthesis.
 *
 *    Stream Header (12)
 *    Block Header:
 *      Block Header (8-12)
 *      Compressed Data (N)
 *      Block Padding (0-3)
 *      CRC32 (4)
 *    Index (8-20)
 *    Stream Footer (12)
 *
 * Normally there is exactly one Block, but let's assume that there are
 * 2-4 Blocks just in case. Because Stream Header and also Block Header
 * of the first Block don't make the decompressor produce any uncompressed
 * data, we can ignore them from our calculations. Block Headers of possible
 * additional Blocks have to be taken into account still. With these
 * assumptions, it is safe to assume that the total header overhead is
 * less than 128 bytes.
 *
 * Compressed Data contains LZMA2 or BCJ+LZMA2 encoded data. Since BCJ
 * doesn't change the size of the data, it is enough to calculate the
 * safety margin for LZMA2.
 *
 * LZMA2 stores the data in chunks. Each chunk has a header whose size is
 * a maximum of 6 bytes, but to get round 2^n numbers, let's assume that
 * the maximum chunk header size is 8 bytes. After the chunk header, there
 * may be up to 64 KiB of actual payload in the chunk. Often the payload is
 * quite a bit smaller though; to be safe, let's assume that an average
 * chunk has only 32 KiB of payload.
 *
 * The maximum uncompressed size of the payload is 2 MiB. The minimum
 * uncompressed size of the payload is in practice never less than the
 * payload size itself. The LZMA2 format would allow uncompressed size
 * to be less than the payload size, but no sane compressor creates such
 * files. LZMA2 supports storing uncompressible data in uncompressed form,
 * so there's never a need to create payloads whose uncompressed size is
 * smaller than the compressed size.
 *
 * The assumption, that the uncompressed size of the payload is never
 * smaller than the payload itself, is valid only when talking about
 * the payload as a whole. It is possible that the payload has parts where
 * the decompressor consumes more input than it produces output. Calculating
 * the worst case for this would be tricky. Instead of trying to do that,
 * let's simply make sure that the decompressor never overwrites any bytes
 * of the payload which it is currently reading.
 *
 * Now we have enough information to calculate the safety margin. We need
 *   - 128 bytes for the .xz file format headers;
 *   - 8 bytes per every 32 KiB of uncompressed size (one LZMA2 chunk header
 *     per chunk, each chunk having average payload size of 32 KiB); and
 *   - 64 KiB (biggest possible LZMA2 chunk payload size) to make sure that
 *     the decompressor never overwrites anything from the LZMA2 chunk
 *     payload it is currently reading.
 *
 * We get the following formula:
 *
 *    safety_margin = 128 + uncompressed_size * 8 / 32768 + 65536
 *                  = 128 + (uncompressed_size >> 12) + 65536
 *
 * For comparison, according to arch/x86/boot/compressed/misc.c, the
 * equivalent formula for Deflate is this:
 *
 *    safety_margin = 18 + (uncompressed_size >> 12) + 32768
 *
 * Thus, when updating Deflate-only in-place kernel decompressor to
 * support XZ, the fixed overhead has to be increased from 18+32768 bytes
 * to 128+65536 bytes.
 */

/*
 * STATIC is defined to "static" if we are being built for kernel
 * decompression (pre-boot code). <linux/decompress/mm.h> will define
 * STATIC to empty if it wasn't already defined. Since we will need to
 * know later if we are being used for kernel decompression, we define
 * XZ_PREBOOT here.
 */
#ifdef STATIC
#	define XZ_PREBOOT
#endif
#ifdef __KERNEL__
#	include <linux/decompress/mm.h>
#endif
#define XZ_EXTERN STATIC

#ifndef XZ_PREBOOT
#	include <linux/slab.h>
#	include <linux/xz.h>
#else
/*
 * Use the internal CRC32 code instead of kernel's CRC32 module, which
 * is not available in early phase of booting.
 */
#define XZ_INTERNAL_CRC32 1

/*
 * For boot time use, we enable only the BCJ filter of the current
 * architecture or none if no BCJ filter is available for the architecture.
 */
#ifdef CONFIG_X86
#	define XZ_DEC_X86
#endif
#ifdef CONFIG_PPC
#	define XZ_DEC_POWERPC
#endif
#ifdef CONFIG_ARM
#	define XZ_DEC_ARM
#endif
#ifdef CONFIG_IA64
#	define XZ_DEC_IA64
#endif
#ifdef CONFIG_SPARC
#	define XZ_DEC_SPARC
#endif

/*
 * This will get the basic headers so that memeq() and others
 * can be defined.
 */
#include "xz/xz_private.h"

/*
 * Replace the normal allocation functions with the versions from
 * <linux/decompress/mm.h>. vfree() needs to support vfree(NULL)
 * when XZ_DYNALLOC is used, but the pre-boot free() doesn't support it.
 * Workaround it here because the other decompressors don't need it.
 */
#undef kmalloc
#undef kfree
#undef vmalloc
#undef vfree
#define kmalloc(size, flags) malloc(size)
#define kfree(ptr) free(ptr)
#define vmalloc(size) malloc(size)
#define vfree(ptr) do { if (ptr != NULL) free(ptr); } while (0)

/*
 * FIXME: Not all basic memory functions are provided in architecture-specific
 * files (yet). We define our own versions here for now, but this should be
 * only a temporary solution.
 *
 * memeq and memzero are not used much and any remotely sane implementation
 * is fast enough. memcpy/memmove speed matters in multi-call mode, but
 * the kernel image is decompressed in single-call mode, in which only
 * memmove speed can matter and only if there is a lot of uncompressible data
 * (LZMA2 stores uncompressible chunks in uncompressed form). Thus, the
 * functions below should just be kept small; it's probably not worth
 * optimizing for speed.
 */

#ifndef memeq
static bool memeq(const void *a, const void *b, size_t size)
{
	const uint8_t *x = a;
	const uint8_t *y = b;
	size_t i;

	for (i = 0; i < size; ++i)
		if (x[i] != y[i])
			return false;

	return true;
}
#endif

#ifndef memzero
static void memzero(void *buf, size_t size)
{
	uint8_t *b = buf;
	uint8_t *e = b + size;

	while (b != e)
		*b++ = '\0';
}
#endif

#ifndef memmove
/* Not static to avoid a conflict with the prototype in the Linux headers. */
void *memmove(void *dest, const void *src, size_t size)
{
	uint8_t *d = dest;
	const uint8_t *s = src;
	size_t i;

	if (d < s) {
		for (i = 0; i < size; ++i)
			d[i] = s[i];
	} else if (d > s) {
		i = size;
		while (i-- > 0)
			d[i] = s[i];
	}

	return dest;
}
#endif

/*
 * Since we need memmove anyway, would use it as memcpy too.
 * Commented out for now to avoid breaking things.
 */
/*
#ifndef memcpy
#	define memcpy memmove
#endif
*/

#include "xz/xz_crc32.c"
#include "xz/xz_dec_stream.c"
#include "xz/xz_dec_lzma2.c"
#include "xz/xz_dec_bcj.c"

#endif /* XZ_PREBOOT */

/* Size of the input and output buffers in multi-call mode */
#define XZ_IOBUF_SIZE 4096

/*
 * This function implements the API defined in <linux/decompress/generic.h>.
 *
 * This wrapper will automatically choose single-call or multi-call mode
 * of the native XZ decoder API. The single-call mode can be used only when
 * both input and output buffers are available as a single chunk, i.e. when
 * fill() and flush() won't be used.
 */
STATIC int INIT unxz(unsigned char *in, long in_size,
		     long (*fill)(void *dest, unsigned long size),
		     long (*flush)(void *src, unsigned long size),
		     unsigned char *out, long *in_used,
		     void (*error)(char *x))
{
	struct xz_buf b;
	struct xz_dec *s;
	enum xz_ret ret;
	bool must_free_in = false;

#if XZ_INTERNAL_CRC32
	xz_crc32_init();
#endif

	if (in_used != NULL)
		*in_used = 0;

	if (fill == NULL && flush == NULL)
		s = xz_dec_init(XZ_SINGLE, 0);
	else
		s = xz_dec_init(XZ_DYNALLOC, (uint32_t)-1);

	if (s == NULL)
		goto error_alloc_state;

	if (flush == NULL) {
		b.out = out;
		b.out_size = (size_t)-1;
	} else {
		b.out_size = XZ_IOBUF_SIZE;
		b.out = malloc(XZ_IOBUF_SIZE);
		if (b.out == NULL)
			goto error_alloc_out;
	}

	if (in == NULL) {
		must_free_in = true;
		in = malloc(XZ_IOBUF_SIZE);
		if (in == NULL)
			goto error_alloc_in;
	}

	b.in = in;
	b.in_pos = 0;
	b.in_size = in_size;
	b.out_pos = 0;

	if (fill == NULL && flush == NULL) {
		ret = xz_dec_run(s, &b);
	} else {
		do {
			if (b.in_pos == b.in_size && fill != NULL) {
				if (in_used != NULL)
					*in_used += b.in_pos;

				b.in_pos = 0;

				in_size = fill(in, XZ_IOBUF_SIZE);
				if (in_size < 0) {
					/*
					 * This isn't an optimal error code
					 * but it probably isn't worth making
					 * a new one either.
					 */
					ret = XZ_BUF_ERROR;
					break;
				}

				b.in_size = in_size;
			}

			ret = xz_dec_run(s, &b);

			if (flush != NULL && (b.out_pos == b.out_size
					|| (ret != XZ_OK && b.out_pos > 0))) {
				/*
				 * Setting ret here may hide an error
				 * returned by xz_dec_run(), but probably
				 * it's not too bad.
				 */
				if (flush(b.out, b.out_pos) != (long)b.out_pos)
					ret = XZ_BUF_ERROR;

				b.out_pos = 0;
			}
		} while (ret == XZ_OK);

		if (must_free_in)
			free(in);

		if (flush != NULL)
			free(b.out);
	}

	if (in_used != NULL)
		*in_used += b.in_pos;

	xz_dec_end(s);

	switch (ret) {
	case XZ_STREAM_END:
		return 0;

	case XZ_MEM_ERROR:
		/* This can occur only in multi-call mode. */
		error("XZ decompressor ran out of memory");
		break;

	case XZ_FORMAT_ERROR:
		error("Input is not in the XZ format (wrong magic bytes)");
		break;

	case XZ_OPTIONS_ERROR:
		error("Input was encoded with settings that are not "
				"supported by this XZ decoder");
		break;

	case XZ_DATA_ERROR:
	case XZ_BUF_ERROR:
		error("XZ-compressed data is corrupt");
		break;

	default:
		error("Bug in the XZ decompressor");
		break;
	}

	return -1;

error_alloc_in:
	if (flush != NULL)
		free(b.out);

error_alloc_out:
	xz_dec_end(s);

error_alloc_state:
	error("XZ decompressor ran out of memory");
	return -1;
}

/*
 * This macro is used by architecture-specific files to decompress
 * the kernel image.
 */
#ifdef XZ_PREBOOT
STATIC int INIT __decompress(unsigned char *buf, long len,
			   long (*fill)(void*, unsigned long),
			   long (*flush)(void*, unsigned long),
			   unsigned char *out_buf, long olen,
			   long *pos,
			   void (*error)(char *x))
{
	return unxz(buf, len, fill, flush, out_buf, pos, error);
}
#endif