summaryrefslogtreecommitdiffstats
path: root/src/liblzma/common/index_hash.c
blob: f55f7bc8ff8f24de7508ff8a3b999fc5b258e9dc (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
///////////////////////////////////////////////////////////////////////////////
//
/// \file       index_hash.c
/// \brief      Validates Index by using a hash function
//
//  Author:     Lasse Collin
//
//  This file has been put into the public domain.
//  You can do whatever you want with this file.
//
///////////////////////////////////////////////////////////////////////////////

#include "common.h"
#include "index.h"
#include "check.h"


typedef struct {
	/// Sum of the Block sizes (including Block Padding)
	lzma_vli blocks_size;

	/// Sum of the Uncompressed Size fields
	lzma_vli uncompressed_size;

	/// Number of Records
	lzma_vli count;

	/// Size of the List of Index Records as bytes
	lzma_vli index_list_size;

	/// Check calculated from Unpadded Sizes and Uncompressed Sizes.
	lzma_check_state check;

} lzma_index_hash_info;


struct lzma_index_hash_s {
	enum {
		SEQ_BLOCK,
		SEQ_COUNT,
		SEQ_UNPADDED,
		SEQ_UNCOMPRESSED,
		SEQ_PADDING_INIT,
		SEQ_PADDING,
		SEQ_CRC32,
	} sequence;

	/// Information collected while decoding the actual Blocks.
	lzma_index_hash_info blocks;

	/// Information collected from the Index field.
	lzma_index_hash_info records;

	/// Number of Records not fully decoded
	lzma_vli remaining;

	/// Unpadded Size currently being read from an Index Record.
	lzma_vli unpadded_size;

	/// Uncompressed Size currently being read from an Index Record.
	lzma_vli uncompressed_size;

	/// Position in variable-length integers when decoding them from
	/// the List of Records.
	size_t pos;

	/// CRC32 of the Index
	uint32_t crc32;
};


extern LZMA_API(lzma_index_hash *)
lzma_index_hash_init(lzma_index_hash *index_hash,
		const lzma_allocator *allocator)
{
	if (index_hash == NULL) {
		index_hash = lzma_alloc(sizeof(lzma_index_hash), allocator);
		if (index_hash == NULL)
			return NULL;
	}

	index_hash->sequence = SEQ_BLOCK;
	index_hash->blocks.blocks_size = 0;
	index_hash->blocks.uncompressed_size = 0;
	index_hash->blocks.count = 0;
	index_hash->blocks.index_list_size = 0;
	index_hash->records.blocks_size = 0;
	index_hash->records.uncompressed_size = 0;
	index_hash->records.count = 0;
	index_hash->records.index_list_size = 0;
	index_hash->unpadded_size = 0;
	index_hash->uncompressed_size = 0;
	index_hash->pos = 0;
	index_hash->crc32 = 0;

	// These cannot fail because LZMA_CHECK_BEST is known to be supported.
	(void)lzma_check_init(&index_hash->blocks.check, LZMA_CHECK_BEST);
	(void)lzma_check_init(&index_hash->records.check, LZMA_CHECK_BEST);

	return index_hash;
}


extern LZMA_API(void)
lzma_index_hash_end(lzma_index_hash *index_hash,
		const lzma_allocator *allocator)
{
	lzma_free(index_hash, allocator);
	return;
}


extern LZMA_API(lzma_vli)
lzma_index_hash_size(const lzma_index_hash *index_hash)
{
	// Get the size of the Index from ->blocks instead of ->records for
	// cases where application wants to know the Index Size before
	// decoding the Index.
	return index_size(index_hash->blocks.count,
			index_hash->blocks.index_list_size);
}


/// Updates the sizes and the hash without any validation.
static void
hash_append(lzma_index_hash_info *info, lzma_vli unpadded_size,
		lzma_vli uncompressed_size)
{
	info->blocks_size += vli_ceil4(unpadded_size);
	info->uncompressed_size += uncompressed_size;
	info->index_list_size += lzma_vli_size(unpadded_size)
			+ lzma_vli_size(uncompressed_size);
	++info->count;

	const lzma_vli sizes[2] = { unpadded_size, uncompressed_size };
	lzma_check_update(&info->check, LZMA_CHECK_BEST,
			(const uint8_t *)(sizes), sizeof(sizes));

	return;
}


extern LZMA_API(lzma_ret)
lzma_index_hash_append(lzma_index_hash *index_hash, lzma_vli unpadded_size,
		lzma_vli uncompressed_size)
{
	// Validate the arguments.
	if (index_hash == NULL || index_hash->sequence != SEQ_BLOCK
			|| unpadded_size < UNPADDED_SIZE_MIN
			|| unpadded_size > UNPADDED_SIZE_MAX
			|| uncompressed_size > LZMA_VLI_MAX)
		return LZMA_PROG_ERROR;

	// Update the hash.
	hash_append(&index_hash->blocks, unpadded_size, uncompressed_size);

	// Validate the properties of *info are still in allowed limits.
	if (index_hash->blocks.blocks_size > LZMA_VLI_MAX
			|| index_hash->blocks.uncompressed_size > LZMA_VLI_MAX
			|| index_size(index_hash->blocks.count,
					index_hash->blocks.index_list_size)
				> LZMA_BACKWARD_SIZE_MAX
			|| index_stream_size(index_hash->blocks.blocks_size,
					index_hash->blocks.count,
					index_hash->blocks.index_list_size)
				> LZMA_VLI_MAX)
		return LZMA_DATA_ERROR;

	return LZMA_OK;
}


extern LZMA_API(lzma_ret)
lzma_index_hash_decode(lzma_index_hash *index_hash, const uint8_t *in,
		size_t *in_pos, size_t in_size)
{
	// Catch zero input buffer here, because in contrast to Index encoder
	// and decoder functions, applications call this function directly
	// instead of via lzma_code(), which does the buffer checking.
	if (*in_pos >= in_size)
		return LZMA_BUF_ERROR;

	// NOTE: This function has many similarities to index_encode() and
	// index_decode() functions found from index_encoder.c and
	// index_decoder.c. See the comments especially in index_encoder.c.
	const size_t in_start = *in_pos;
	lzma_ret ret = LZMA_OK;

	while (*in_pos < in_size)
	switch (index_hash->sequence) {
	case SEQ_BLOCK:
		// Check the Index Indicator is present.
		if (in[(*in_pos)++] != INDEX_INDICATOR)
			return LZMA_DATA_ERROR;

		index_hash->sequence = SEQ_COUNT;
		break;

	case SEQ_COUNT: {
		ret = lzma_vli_decode(&index_hash->remaining,
				&index_hash->pos, in, in_pos, in_size);
		if (ret != LZMA_STREAM_END)
			goto out;

		// The count must match the count of the Blocks decoded.
		if (index_hash->remaining != index_hash->blocks.count)
			return LZMA_DATA_ERROR;

		ret = LZMA_OK;
		index_hash->pos = 0;

		// Handle the special case when there are no Blocks.
		index_hash->sequence = index_hash->remaining == 0
				? SEQ_PADDING_INIT : SEQ_UNPADDED;
		break;
	}

	case SEQ_UNPADDED:
	case SEQ_UNCOMPRESSED: {
		lzma_vli *size = index_hash->sequence == SEQ_UNPADDED
				? &index_hash->unpadded_size
				: &index_hash->uncompressed_size;

		ret = lzma_vli_decode(size, &index_hash->pos,
				in, in_pos, in_size);
		if (ret != LZMA_STREAM_END)
			goto out;

		ret = LZMA_OK;
		index_hash->pos = 0;

		if (index_hash->sequence == SEQ_UNPADDED) {
			if (index_hash->unpadded_size < UNPADDED_SIZE_MIN
					|| index_hash->unpadded_size
						> UNPADDED_SIZE_MAX)
				return LZMA_DATA_ERROR;

			index_hash->sequence = SEQ_UNCOMPRESSED;
		} else {
			// Update the hash.
			hash_append(&index_hash->records,
					index_hash->unpadded_size,
					index_hash->uncompressed_size);

			// Verify that we don't go over the known sizes. Note
			// that this validation is simpler than the one used
			// in lzma_index_hash_append(), because here we know
			// that values in index_hash->blocks are already
			// validated and we are fine as long as we don't
			// exceed them in index_hash->records.
			if (index_hash->blocks.blocks_size
					< index_hash->records.blocks_size
					|| index_hash->blocks.uncompressed_size
					< index_hash->records.uncompressed_size
					|| index_hash->blocks.index_list_size
					< index_hash->records.index_list_size)
				return LZMA_DATA_ERROR;

			// Check if this was the last Record.
			index_hash->sequence = --index_hash->remaining == 0
					? SEQ_PADDING_INIT : SEQ_UNPADDED;
		}

		break;
	}

	case SEQ_PADDING_INIT:
		index_hash->pos = (LZMA_VLI_C(4) - index_size_unpadded(
				index_hash->records.count,
				index_hash->records.index_list_size)) & 3;
		index_hash->sequence = SEQ_PADDING;

	// Fall through

	case SEQ_PADDING:
		if (index_hash->pos > 0) {
			--index_hash->pos;
			if (in[(*in_pos)++] != 0x00)
				return LZMA_DATA_ERROR;

			break;
		}

		// Compare the sizes.
		if (index_hash->blocks.blocks_size
				!= index_hash->records.blocks_size
				|| index_hash->blocks.uncompressed_size
				!= index_hash->records.uncompressed_size
				|| index_hash->blocks.index_list_size
				!= index_hash->records.index_list_size)
			return LZMA_DATA_ERROR;

		// Finish the hashes and compare them.
		lzma_check_finish(&index_hash->blocks.check, LZMA_CHECK_BEST);
		lzma_check_finish(&index_hash->records.check, LZMA_CHECK_BEST);
		if (memcmp(index_hash->blocks.check.buffer.u8,
				index_hash->records.check.buffer.u8,
				lzma_check_size(LZMA_CHECK_BEST)) != 0)
			return LZMA_DATA_ERROR;

		// Finish the CRC32 calculation.
		index_hash->crc32 = lzma_crc32(in + in_start,
				*in_pos - in_start, index_hash->crc32);

		index_hash->sequence = SEQ_CRC32;

	// Fall through

	case SEQ_CRC32:
		do {
			if (*in_pos == in_size)
				return LZMA_OK;

			if (((index_hash->crc32 >> (index_hash->pos * 8))
					& 0xFF) != in[(*in_pos)++]) {
#ifndef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
				return LZMA_DATA_ERROR;
#endif
			}

		} while (++index_hash->pos < 4);

		return LZMA_STREAM_END;

	default:
		assert(0);
		return LZMA_PROG_ERROR;
	}

out:
	// Update the CRC32,
	index_hash->crc32 = lzma_crc32(in + in_start,
			*in_pos - in_start, index_hash->crc32);

	return ret;
}