ObjFW  Check-in [e9398866eb]

Overview
Comment:huffman_tree.m: Do not limit codes to 15 bit

This limitation is only present in DEFLATE, LHA does not have this
limitation.

Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: e9398866eb6fd745f2040891d9764e7627657438ed31d87753db37cd90581464
User & Date: js on 2018-12-01 21:06:48
Other Links: manifest | tags
Context
2018-12-01
21:32
ofarc: Fix a typo check-in: e62556c4a5 user: js tags: trunk
21:06
huffman_tree.m: Do not limit codes to 15 bit check-in: e9398866eb user: js tags: trunk
19:33
ObjFW.h: Fix unicode.h import check-in: f1e2e08017 user: js tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Modified src/huffman_tree.m from [d14cb85d84] to [fc3617ec1a].

︙
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

21
22
23
24
25
26
27


28
29
30
31
32
33
34








-
-








#include <stdlib.h>

#import "huffman_tree.h"

#import "OFInvalidFormatException.h"
#import "OFOutOfMemoryException.h"

#define MAX_BIT 15

static struct of_huffman_tree *
newTree(void)
{
	struct of_huffman_tree *tree;

	if ((tree = malloc(sizeof(*tree))) == NULL)
		@throw [OFOutOfMemoryException
︙
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

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








-
-
-
+
+
+
-

+
-
-
+
+

-
-
+
+
+
+
+
+
+

+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
-
-
+
+
+
+
+

-
-
-
-
-
+
+
+
+
+

-
+

-
-
+
+

-
-
+
+
+
+
+
+








	tree->value = value;
}

struct of_huffman_tree *
of_huffman_tree_construct(uint8_t lengths[], uint16_t count)
{
	struct of_huffman_tree *tree;
	uint16_t lengthCount[MAX_BIT + 1];
	uint16_t code, maxCode = 0, nextCode[MAX_BIT + 1];

	uint16_t *lengthCount = NULL;
	uint16_t code, maxCode = 0, *nextCode = NULL;
	uint_fast8_t maxBit = 0;
	memset(&lengthCount, 0, (MAX_BIT + 1) * 2);

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

		if OF_UNLIKELY (length > MAX_BIT)
			@throw [OFInvalidFormatException exception];
			if OF_UNLIKELY (length > maxBit) {
				size_t size = (length + 1) * sizeof(uint16_t);
				uint16_t *new;

				if ((new = realloc(lengthCount, size)) == NULL)
					@throw [OFOutOfMemoryException
					    exceptionWithRequestedSize: size];

				lengthCount = new;

				if ((new = realloc(nextCode, size)) == NULL)
					@throw [OFOutOfMemoryException
					    exceptionWithRequestedSize: size];

				nextCode = new;

				for (uint_fast8_t j = maxBit + 1; j <= length;
				    j++) {
					lengthCount[j] = 0;
					nextCode[j] = 0;
				}

				maxBit = length;
			}

		if (length > 0) {
			lengthCount[length]++;
			maxCode = i;
		}
	}
			if (length > 0) {
				lengthCount[length]++;
				maxCode = i;
			}
		}

	code = 0;
	for (size_t i = 1; i <= MAX_BIT; i++) {
		code = (code + lengthCount[i - 1]) << 1;
		nextCode[i] = code;
	}
		code = 0;
		for (size_t i = 1; i <= maxBit; i++) {
			code = (code + lengthCount[i - 1]) << 1;
			nextCode[i] = code;
		}

	tree = newTree();
		tree = newTree();

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

		if (length > 0)
			insertTree(tree, nextCode[length]++, length, i);
			if (length > 0)
				insertTree(tree, nextCode[length]++, length, i);
		}
	} @finally {
		free(lengthCount);
		free(nextCode);
	}

	return tree;
}

struct of_huffman_tree *
of_huffman_tree_construct_single(uint16_t value)
︙

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