1 /*
2 Inflate implementation
3
4 Copyright (c) 2006 Michal Molhanec
5
6 This software is provided 'as-is', without any express or implied
7 warranty. In no event will the authors be held liable for any damages
8 arising from the use of this software.
9
10 Permission is granted to anyone to use this software for any purpose,
11 including commercial applications, and to alter it and redistribute
12 it freely, subject to the following restrictions:
13
14 1. The origin of this software must not be misrepresented;
15 you must not claim that you wrote the original software.
16 If you use this software in a product, an acknowledgment
17 in the product documentation would be appreciated but
18 is not required.
19
20 2. Altered source versions must be plainly marked as such,
21 and must not be misrepresented as being the original software.
22
23 3. This notice may not be removed or altered from any
24 source distribution.
25 */
26
27 /*
28
29 huffman.c -- Static Huffman tree implementation.
30
31 This second version of implementation uses now heaptree structure.
32 Note that it uses Pascal-like indexes [1..max] instead
33 of C-like [0..max-1], because it simplifies heaptree
34 implementation. To make it easy we just allocate max + 1
35 array items and ignore the first array item.
36
37 */
38
39 #if !defined(ALPNG_ZLIB) || (ALPNG_ZLIB == 0)
40
41 #include <stdlib.h> /* malloc, free */
42 #include <string.h> /* memset */
43
44 #include "input.h"
45 #include "huffman.h"
46
47 #define HUFFMAN_HEAP_MAX 65535
48 #define HUFFMAN_HEAP_SIZE (HUFFMAN_HEAP_MAX + 1)
49 #define HUFFMAN_EMPTY_NODE -1
50 #define HUFFMAN_NONLEAF_NODE -2
51
huffman_create_tree(void)52 struct huffman_tree* huffman_create_tree(void) {
53 struct huffman_tree* tree = (struct huffman_tree*) malloc(sizeof(struct huffman_tree));
54 if (tree) {
55 tree->data = malloc(HUFFMAN_HEAP_SIZE * sizeof(int));
56 if (tree->data) {
57 memset(tree->data, HUFFMAN_EMPTY_NODE, HUFFMAN_HEAP_SIZE * sizeof(int));
58 } else {
59 free(tree);
60 tree = 0;
61 }
62 }
63 return tree;
64 }
65
huffman_reset_tree(struct huffman_tree * tree)66 void huffman_reset_tree(struct huffman_tree* tree) {
67 int i = 1;
68 while (tree->data[1] != HUFFMAN_EMPTY_NODE) {
69 if (i * 2 > HUFFMAN_HEAP_MAX) {
70 tree->data[i] = HUFFMAN_EMPTY_NODE;
71 i /= 2;
72 } else if (tree->data[i * 2] != HUFFMAN_EMPTY_NODE) {
73 i = i * 2;
74 } else if (tree->data[i * 2 + 1] != HUFFMAN_EMPTY_NODE) {
75 i = i * 2 + 1;
76 } else {
77 tree->data[i] = HUFFMAN_EMPTY_NODE;
78 i /= 2;
79 }
80 }
81 tree->last_free_parent = 1;
82 tree->last_depth = 0;
83 tree->data[1] = HUFFMAN_NONLEAF_NODE;
84 }
85
huffman_destroy_tree(struct huffman_tree * tree)86 void huffman_destroy_tree(struct huffman_tree* tree) {
87 free(tree->data);
88 free(tree);
89 }
90
huffman_add(struct huffman_tree * tree,int depth,int value)91 int huffman_add(struct huffman_tree* tree, int depth, int value) {
92 int i;
93 if (depth > 15 || depth <= tree->last_depth) {
94 return 0;
95 }
96 while (1) {
97 i = 2 * tree->last_free_parent;
98 if (i > HUFFMAN_HEAP_MAX) {
99 return 0;
100 }
101 if (tree->last_depth == depth - 1) {
102 if (tree->data[i] == HUFFMAN_EMPTY_NODE) {
103 tree->data[i] = value;
104 } else {
105 tree->data[i + 1] = value;
106 while (tree->last_free_parent != 1 && tree->data[2 * tree->last_free_parent + 1] != HUFFMAN_EMPTY_NODE) {
107 tree->data[tree->last_free_parent] = HUFFMAN_NONLEAF_NODE;
108 tree->last_free_parent /= 2;
109 tree->last_depth--;
110 }
111 }
112 return 1;
113 } else {
114 tree->last_depth++;
115 if (tree->data[i] == HUFFMAN_EMPTY_NODE) {
116 tree->last_free_parent = i;
117 } else {
118 tree->last_free_parent = i + 1;
119 }
120 }
121 }
122 }
123
huffman_read_next_code(struct huffman_tree * tree,struct input_data * data)124 int huffman_read_next_code(struct huffman_tree* tree, struct input_data* data) {
125 int i = 1;
126 int bit;
127
128 while (tree->data[i] < 0) {
129 bit = input_read_bit(data);
130 if (data->error) {
131 return HUFFMAN_EMPTY_NODE;
132 }
133 switch (bit) {
134 case 0: i = i * 2; break;
135 case 1: i = i * 2 + 1; break;
136 }
137 if (i > HUFFMAN_HEAP_MAX) {
138 return -1;
139 }
140 }
141
142 return tree->data[i];
143 }
144
145 #endif /* !defined(ALPNG_ZLIB) || (ALPNG_ZLIB == 0) */
146