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
#include "hashmap.h"
#include "bitwriter.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
if (argc != 2)
{
printf("Usage: %s <input file>\n", argv[0]);
exit(1);
}
char *input_file_name = argv[1];
char *output_file_name = malloc(sizeof(char) *
(strlen(input_file_name) + strlen(".deflate") + 1));
sprintf(output_file_name, "%s.deflate", input_file_name);
FILE *input_file = fopen(input_file_name, "r");
FILE *output_file = fopen(output_file_name, "w");
free(output_file_name);
BitWriter *bitWriter = BitWriter_init(output_file);
Hashmap *hashMap = Hashmap_init();
BitWriter_write_bit(bitWriter, 1); /* BFINAL */
BitWriter_write_bit(bitWriter, 1); /* BTYPE */
BitWriter_write_bit(bitWriter, 0);
fseek(input_file, 0, SEEK_END);
size_t input_file_length = ftell(input_file);
fseek(input_file, 0, SEEK_SET);
size_t cursor = 0;
while (cursor < input_file_length)
{
printf("Compressed %ld/%ld\n", cursor, input_file_length);
uint32_t best_length = 0;
size_t best_length_start = 0;
size_t scan_start = 0;
if (cursor > 32768) scan_start = cursor - 32768;
for (size_t start = scan_start; start < cursor; start++)
{
uint32_t length = 0;
while (start + length < cursor && cursor + length < input_file_length && length < 258)
{
uint8_t back, cur;
fseek(input_file, start + length, SEEK_SET);
fread(&back, 1, 1, input_file);
fseek(input_file, cursor + length, SEEK_SET);
fread(&cur, 1, 1, input_file);
if (back == cur) length += 1;
else break;
}
if (length > best_length)
{
best_length = length;
best_length_start = start;
}
}
if (best_length > 2)
{
uint32_t backtrack = cursor - best_length_start;
BitWriter_write_length(bitWriter, best_length);
BitWriter_write_distance(bitWriter, backtrack);
cursor += best_length;
}
else
{
fseek(input_file, cursor, SEEK_SET);
uint8_t b;
fread(&b, 1, 1, input_file);
BitWriter_write_alpha(bitWriter, b);
cursor += 1;
}
}
BitWriter_write_bin(bitWriter, 0, 7); /* EOB */
BitWriter_flush(bitWriter);
Hashmap_free(hashMap);
BitWriter_free(bitWriter);
fclose(input_file);
fclose(output_file);
}