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
|
*/
#include "config.h"
#include <stdint.h>
#include <stdlib.h>
#import "huffman_tree.h"
#import "OFInvalidFormatException.h"
#import "OFOutOfMemoryException.h"
static struct of_huffman_tree *
newTree(void)
{
struct of_huffman_tree *tree;
tree = OFAllocMemory(1, sizeof(*tree));
tree->leaves[0] = tree->leaves[1] = NULL;
tree->value = 0xFFFF;
return tree;
}
static void
insertTree(struct of_huffman_tree *tree, uint16_t code, uint8_t length,
uint16_t value)
{
while (length > 0) {
uint8_t bit;
length--;
bit = (code & (1u << length)) >> length;
if (tree->leaves[bit] == NULL)
tree->leaves[bit] = newTree();
tree = tree->leaves[bit];
}
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 = NULL;
uint16_t code, maxCode = 0, *nextCode = NULL;
uint_fast8_t maxBit = 0;
@try {
for (uint16_t i = 0; i < count; i++) {
uint_fast8_t length = lengths[i];
|
|
|
|
|
<
|
|
|
|
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
|
*/
#include "config.h"
#include <stdint.h>
#include <stdlib.h>
#import "OFHuffmanTree.h"
#import "OFInvalidFormatException.h"
#import "OFOutOfMemoryException.h"
static OFHuffmanTree *
newTree(void)
{
OFHuffmanTree *tree;
tree = OFAllocMemory(1, sizeof(*tree));
tree->leaves[0] = tree->leaves[1] = NULL;
tree->value = 0xFFFF;
return tree;
}
static void
insertTree(OFHuffmanTree *tree, uint16_t code, uint8_t length, uint16_t value)
{
while (length > 0) {
uint8_t bit;
length--;
bit = (code & (1u << length)) >> length;
if (tree->leaves[bit] == NULL)
tree->leaves[bit] = newTree();
tree = tree->leaves[bit];
}
tree->value = value;
}
OFHuffmanTree *
OFHuffmanTreeNew(uint8_t lengths[], uint16_t count)
{
OFHuffmanTree *tree;
uint16_t *lengthCount = NULL;
uint16_t code, maxCode = 0, *nextCode = NULL;
uint_fast8_t maxBit = 0;
@try {
for (uint16_t i = 0; i < count; i++) {
uint_fast8_t length = lengths[i];
|
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
|
OFFreeMemory(lengthCount);
OFFreeMemory(nextCode);
}
return tree;
}
struct of_huffman_tree *
of_huffman_tree_construct_single(uint16_t value)
{
struct of_huffman_tree *tree = newTree();
tree->value = value;
return tree;
}
void
of_huffman_tree_release(struct of_huffman_tree *tree)
{
for (uint_fast8_t i = 0; i < 2; i++)
if OF_LIKELY (tree->leaves[i] != NULL)
of_huffman_tree_release(tree->leaves[i]);
OFFreeMemory(tree);
}
|
|
|
|
|
|
|
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
|
OFFreeMemory(lengthCount);
OFFreeMemory(nextCode);
}
return tree;
}
OFHuffmanTree *
OFHuffmanTreeNewSingle(uint16_t value)
{
OFHuffmanTree *tree = newTree();
tree->value = value;
return tree;
}
void
OFHuffmanTreeFree(OFHuffmanTree *tree)
{
for (uint_fast8_t i = 0; i < 2; i++)
if OF_LIKELY (tree->leaves[i] != NULL)
OFHuffmanTreeFree(tree->leaves[i]);
OFFreeMemory(tree);
}
|