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
|
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct node {
bool is_char;
char ch;
struct node *left;
struct node *right;
} node_t;
node_t *node_char_create(char ch);
// left right flipped because tree has to be inverted for some reason
node_t *node_link_create(node_t* right, node_t* left);
void node_free(node_t *root);
void node_print(node_t *root, int indent);
size_t read_tree_data(char *buf);
node_t *read_tree_shape(char *char_buf, size_t bits);
char read_decoded(node_t *root);
void decode();
FILE *in;
FILE *out;
node_t *root;
char read_decoded(node_t *root)
{
static size_t i = 0;
static char cur_byte = 0;
if(root == NULL) {
fprintf(stderr, "ERROR: real_decoded: root cannot be NULL");
exit(1);
}
if(root->is_char) return root->ch;
if(i % 8 == 0) {
if(fread(&cur_byte, sizeof(char), 1, in) <= 0) {
fprintf(stderr, "ERROR: An error has occured while reading the encoded bytes\n");
exit(1);
}
i = 0;
}
char bit = (cur_byte >> i++) & 1;
if(bit == 0) {
return read_decoded(root->left);
}
return read_decoded(root->right);
}
void decode()
{
char buf[256] = {0};
size_t chars = read_tree_data(buf);
root = read_tree_shape(buf, chars*2 - 1);
size_t text_len;
fread(&text_len, sizeof(size_t), 1, in);
for(int i = 0; i < text_len; i++) {
char ch = read_decoded(root);
fwrite(&ch, sizeof(char), 1, out);
}
}
int main(void)
{
in = stdin;
out = stdout;
// in = fopen(argv[1], "rb");
// if(!in) {
// fprintf(stderr, "ERROR: Could not open file %s\n", argv[1]);
// exit(1);
// }
// out = fopen(argv[1], "wb");
// if(!out) {
// fprintf(stderr, "ERROR Could not open file %s\n", argv[1]);
// exit(1);
// }
decode();
node_free(root);
// fclose(in);
// fclose(out);
return 0;
}
size_t read_tree_data(char *buf)
{
unsigned int chars = 0;
fread(&chars, sizeof(char), 1, in);
fread(buf, sizeof(char), chars, in);
return chars;
}
node_t *read_tree_shape(char *char_buf, size_t bits)
{
static size_t buf_i = 0;
static size_t read_bits = 0;
static char cur_byte = 0;
if(read_bits == bits) {
fprintf(stderr, "ERROR: An error has occred while reading the tree shape (read_bits == bits)");
exit(1);
}
if(read_bits % 8 == 0) {
if(fread(&cur_byte, sizeof(char), 1, in) <= 0) {
fprintf(stderr, "ERROR: An error has occured while reading the tree shape\n");
exit(1);
}
}
node_t *root;
char bit = (cur_byte >> (read_bits++ % 8)) & 1;
if(bit == 0) {
root = node_link_create(read_tree_shape(char_buf, bits),
read_tree_shape(char_buf, bits));
} else {
root = node_char_create(char_buf[buf_i++]);
}
return root;
}
node_t *node_char_create(char ch)
{
node_t *node = malloc(sizeof(node_t));
node->is_char = true;
node->ch = ch;
node->left = NULL;
node->right = NULL;
return node;
}
node_t *node_link_create(node_t* right, node_t* left)
{
node_t *node = malloc(sizeof(node_t));
node->is_char = false;
node->ch = 0;
node->left = left;
node->right = right;
return node;
}
void node_free(node_t *root)
{
if(root == NULL) return;
node_free(root->left);
node_free(root->right);
free(root);
}
void node_print(node_t *root, int indent)
{
if(root == NULL) return;
for(int i = 0; i < indent; i++) fprintf(stderr, " ");
fprintf(stderr, "%d '%c'\n", root->is_char, (root->ch == 0) ? '-' : root->ch);
node_print(root->left, indent + 2);
node_print(root->right, indent + 2);
}
|
