ObjFW  Check-in [aee3bc12f7]

Overview
Comment:OFDeflateStream: Fix tree construction.

When a bit length had more than 255 occurrences, it caused an integer
overflow and thus a corrupt tree.

This also cleans up tree walking.

Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: aee3bc12f7aded30a6cd005b70ca8dfad5d1cc3d45c44f8613a85e3e3cb5a717
User & Date: js on 2013-10-29 22:15:49
Other Links: manifest | tags
Context
2013-10-29
22:56
OFDeflateStream: Fix reading uncompressed header. check-in: d1293b647a user: js tags: trunk
22:15
OFDeflateStream: Fix tree construction. check-in: aee3bc12f7 user: js tags: trunk
18:00
OFZIPArchive: Only check lower byte of minVersion. check-in: 1ce5d53f93 user: js tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Modified src/OFDeflateStream.m from [b262daf9b1] to [a8810ba694].

︙︙
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

#define MAX_BITS    15

struct huffman_tree {
	struct huffman_tree *leafs[2];
	uint16_t value;
};

static uint8_t lengthCodes[29] = {
	/* indices are -257, values -3 */
	0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
	64, 80, 96, 112, 128, 160, 192, 224, 255
};
static uint8_t lengthExtraBits[29] = {
	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4,
	5, 5, 5, 5, 0
};
static uint16_t distanceCodes[30] = {
	1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385,
	513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
};
static uint8_t distanceExtraBits[30] = {
	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
	10, 11, 11, 12, 12, 13, 13
};
static uint8_t codeLengthsOrder[19] = {
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};
static struct huffman_tree *fixedLitLenTree, *fixedDistTree;

static bool
tryReadBits(OFDeflateStream *stream, uint_fast16_t *bits, uint_fast8_t count)
{








|




|



|



|



|








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

#define MAX_BITS    15

struct huffman_tree {
	struct huffman_tree *leafs[2];
	uint16_t value;
};

static const uint8_t lengthCodes[29] = {
	/* indices are -257, values -3 */
	0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
	64, 80, 96, 112, 128, 160, 192, 224, 255
};
static const uint8_t lengthExtraBits[29] = {
	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4,
	5, 5, 5, 5, 0
};
static const uint16_t distanceCodes[30] = {
	1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385,
	513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
};
static const uint8_t distanceExtraBits[30] = {
	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10,
	10, 11, 11, 12, 12, 13, 13
};
static const uint8_t codeLengthsOrder[19] = {
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};
static struct huffman_tree *fixedLitLenTree, *fixedDistTree;

static bool
tryReadBits(OFDeflateStream *stream, uint_fast16_t *bits, uint_fast8_t count)
{
︙︙
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

	tree->value = value;
}

static struct huffman_tree*
constructTree(uint8_t lengths[], uint_fast16_t count)
{
	struct huffman_tree *tree;
	uint8_t lengthCount[MAX_BITS + 1] = { 0 };
	uint16_t code, maxCode, nextCode[MAX_BITS + 1];
	uint_fast16_t i;

	for (i = 0; i < count; i++) {
		uint8_t length = lengths[i];

		if OF_UNLIKELY (length > MAX_BITS)








|








155
156
157
158
159
160
161
162
163
164
165
166
167
168
169

	tree->value = value;
}

static struct huffman_tree*
constructTree(uint8_t lengths[], uint_fast16_t count)
{
	struct huffman_tree *tree;
	uint16_t lengthCount[MAX_BITS + 1] = { 0 };
	uint16_t code, maxCode, nextCode[MAX_BITS + 1];
	uint_fast16_t i;

	for (i = 0; i < count; i++) {
		uint8_t length = lengths[i];

		if OF_UNLIKELY (length > MAX_BITS)
︙︙
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


static bool
walkTree(OFDeflateStream *stream, struct huffman_tree **tree, uint16_t *value)
{
	struct huffman_tree *iter = *tree;
	uint_fast16_t bits;

	for (;;) {
		if OF_UNLIKELY (iter->leafs[0] == NULL &&
		    iter->leafs[1] == NULL)
			break;

		if OF_UNLIKELY (!tryReadBits(stream, &bits, 1)) {
			*tree = iter;
			return false;
		}

		if OF_UNLIKELY (iter->leafs[bits] == NULL)
			break;

		iter = iter->leafs[bits];
	}

	if OF_UNLIKELY (iter->value == 0xFFFF)
		@throw [OFInvalidFormatException exception];

	*value = iter->value;
	return true;
}

static void
releaseTree(struct huffman_tree *tree)
{








<
<
<
<
|






|




<
<
<








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


static bool
walkTree(OFDeflateStream *stream, struct huffman_tree **tree, uint16_t *value)
{
	struct huffman_tree *iter = *tree;
	uint_fast16_t bits;





	while (iter->value == 0xFFFF) {
		if OF_UNLIKELY (!tryReadBits(stream, &bits, 1)) {
			*tree = iter;
			return false;
		}

		if OF_UNLIKELY (iter->leafs[bits] == NULL)
			@throw [OFInvalidFormatException exception];

		iter = iter->leafs[bits];
	}




	*value = iter->value;
	return true;
}

static void
releaseTree(struct huffman_tree *tree)
{
︙︙

Fossil 2.23 [47362306a7] 2023-11-01 18:56:47
This page was generated in about 0.016s