-
-
Notifications
You must be signed in to change notification settings - Fork 3
/
saxman.c
206 lines (157 loc) · 5.88 KB
/
saxman.c
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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
/*
Copyright (c) 2018-2023 Clownacy
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.
*/
#include "saxman.h"
#include <assert.h>
#include <stddef.h>
#include "clowncommon/clowncommon.h"
#include "clownlzss.h"
#include "common.h"
#define TOTAL_DESCRIPTOR_BITS 8
typedef struct SaxmanInstance
{
const ClownLZSS_Callbacks *callbacks;
size_t descriptor_position;
unsigned int descriptor;
unsigned int descriptor_bits_remaining;
} SaxmanInstance;
static size_t GetMatchCost(size_t distance, size_t length, void *user)
{
(void)distance;
(void)length;
(void)user;
if (length >= 3)
return 1 + 16; /* Descriptor bit, offset/length bits */
else
return 0;
}
static void FindExtraMatches(const unsigned char *data, size_t data_size, size_t offset, ClownLZSS_GraphEdge *node_meta_array, void *user)
{
(void)user;
if (offset < 0x1000)
{
size_t i;
const size_t max_read_ahead = CLOWNLZSS_MIN(0x12, data_size - offset);
for (i = 0; i < max_read_ahead && data[offset + i] == 0; ++i)
{
const unsigned int cost = GetMatchCost(0, i + 1, user);
if (cost && node_meta_array[offset + i + 1].u.cost > node_meta_array[offset].u.cost + cost)
{
node_meta_array[offset + i + 1].u.cost = node_meta_array[offset].u.cost + cost;
node_meta_array[offset + i + 1].previous_node_index = offset;
node_meta_array[offset + i + 1].match_offset = 0xFFF;
}
}
}
}
static void BeginDescriptorField(SaxmanInstance *instance)
{
const ClownLZSS_Callbacks* const callbacks = instance->callbacks;
/* Log the placement of the descriptor field. */
instance->descriptor_position = callbacks->tell(callbacks->user_data);
/* Insert a placeholder. */
callbacks->write(callbacks->user_data, 0);
}
static void FinishDescriptorField(SaxmanInstance *instance)
{
const ClownLZSS_Callbacks* const callbacks = instance->callbacks;
/* Back up current position. */
const size_t current_position = callbacks->tell(callbacks->user_data);
/* Go back to the descriptor field. */
callbacks->seek(callbacks->user_data, instance->descriptor_position);
/* Write the complete descriptor field. */
callbacks->write(callbacks->user_data, instance->descriptor & 0xFF);
/* Seek back to where we were before. */
callbacks->seek(callbacks->user_data, current_position);
}
static void PutDescriptorBit(SaxmanInstance *instance, cc_bool bit)
{
assert(bit == 0 || bit == 1);
if (instance->descriptor_bits_remaining == 0)
{
instance->descriptor_bits_remaining = TOTAL_DESCRIPTOR_BITS;
FinishDescriptorField(instance);
BeginDescriptorField(instance);
}
--instance->descriptor_bits_remaining;
instance->descriptor >>= 1;
if (bit)
instance->descriptor |= 1 << (TOTAL_DESCRIPTOR_BITS - 1);
}
static cc_bool SaxmanCompress(const unsigned char *data, size_t data_size, const ClownLZSS_Callbacks *callbacks, cc_bool header)
{
SaxmanInstance instance;
ClownLZSS_Match *matches, *match;
size_t total_matches;
size_t header_position, end_position;
/* Set up the state. */
instance.callbacks = callbacks;
instance.descriptor = 0;
instance.descriptor_bits_remaining = TOTAL_DESCRIPTOR_BITS;
/* Produce a series of LZSS compression matches. */
if (!ClownLZSS_Compress(1, 0x12, 0x1000, FindExtraMatches, 1 + 8, GetMatchCost, data, data_size, &matches, &total_matches, &instance))
return cc_false;
if (header)
{
/* Track the location of the header... */
header_position = callbacks->tell(callbacks->user_data);
/* ...and insert a placeholder there. */
callbacks->write(callbacks->user_data, 0);
callbacks->write(callbacks->user_data, 0);
}
/* Begin first descriptor field. */
BeginDescriptorField(&instance);
/* Produce Saxman-formatted data. */
for (match = matches; match != &matches[total_matches]; ++match)
{
if (CLOWNLZSS_MATCH_IS_LITERAL(match))
{
PutDescriptorBit(&instance, 1);
callbacks->write(callbacks->user_data, data[match->destination]);
}
else
{
const size_t offset = match->source - 0x12;
const size_t length = match->length;
PutDescriptorBit(&instance, 0);
callbacks->write(callbacks->user_data, offset & 0xFF);
callbacks->write(callbacks->user_data, ((offset & 0xF00) >> 4) | (length - 3));
}
}
/* We don't need the matches anymore. */
free(matches);
/* The descriptor field may be incomplete, so move the bits into their proper place. */
instance.descriptor >>= instance.descriptor_bits_remaining;
/* Finish last descriptor field. */
FinishDescriptorField(&instance);
if (header)
{
/* Grab the current position for later. */
end_position = callbacks->tell(callbacks->user_data);
/* Rewind to the header... */
callbacks->seek(callbacks->user_data, header_position);
/* ...and complete it. */
callbacks->write(callbacks->user_data, ((end_position - header_position - 2) >> (8 * 0)) & 0xFF);
callbacks->write(callbacks->user_data, ((end_position - header_position - 2) >> (8 * 1)) & 0xFF);
/* Seek back to the end of the file just as the caller might expect us to do. */
callbacks->seek(callbacks->user_data, end_position);
}
return cc_true;
}
cc_bool ClownLZSS_SaxmanCompressWithHeader(const unsigned char *data, size_t data_size, const ClownLZSS_Callbacks *callbacks)
{
return SaxmanCompress(data, data_size, callbacks, cc_true);
}
cc_bool ClownLZSS_SaxmanCompressWithoutHeader(const unsigned char *data, size_t data_size, const ClownLZSS_Callbacks *callbacks)
{
return SaxmanCompress(data, data_size, callbacks, cc_false);
}