source: nikanabo/current/xdelta/diy/xdelta3-second.h@ 185

Last change on this file since 185 was 185, checked in by geyser, 18 years ago
File size: 8.2 KB
Line 
1/* xdelta 3 - delta compression tools and library
2 * Copyright (C) 2002, 2003, 2006, 2007. Joshua P. MacDonald
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; either version 2 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 */
18
19#ifndef _XDELTA3_SECOND_H_
20#define _XDELTA3_SECOND_H_
21
22/******************************************************************************************
23 Secondary compression
24 ******************************************************************************************/
25
26#define xd3_sec_data(s) ((s)->sec_stream_d)
27#define xd3_sec_inst(s) ((s)->sec_stream_i)
28#define xd3_sec_addr(s) ((s)->sec_stream_a)
29
30struct _xd3_sec_type
31{
32 int id;
33 const char *name;
34 xd3_secondary_flags flags;
35
36 /* xd3_sec_stream is opaque to the generic code */
37 xd3_sec_stream* (*alloc) (xd3_stream *stream);
38 void (*destroy) (xd3_stream *stream,
39 xd3_sec_stream *sec);
40 void (*init) (xd3_sec_stream *sec);
41 int (*decode) (xd3_stream *stream,
42 xd3_sec_stream *sec_stream,
43 const uint8_t **input,
44 const uint8_t *input_end,
45 uint8_t **output,
46 const uint8_t *output_end);
47#if XD3_ENCODER
48 int (*encode) (xd3_stream *stream,
49 xd3_sec_stream *sec_stream,
50 xd3_output *input,
51 xd3_output *output,
52 xd3_sec_cfg *cfg);
53#endif
54};
55
56#define BIT_STATE_ENCODE_INIT { 0, 1 }
57#define BIT_STATE_DECODE_INIT { 0, 0x100 }
58
59typedef struct _bit_state bit_state;
60struct _bit_state
61{
62 usize_t cur_byte;
63 usize_t cur_mask;
64};
65
66static INLINE void xd3_bit_state_encode_init (bit_state *bits)
67{
68 bits->cur_byte = 0;
69 bits->cur_mask = 1;
70}
71
72static INLINE int xd3_decode_bits (xd3_stream *stream,
73 bit_state *bits,
74 const uint8_t **input,
75 const uint8_t *input_max,
76 usize_t nbits,
77 usize_t *valuep)
78{
79 usize_t value = 0;
80 usize_t vmask = 1 << nbits;
81
82 if (bits->cur_mask == 0x100) { goto next_byte; }
83
84 for (;;)
85 {
86 do
87 {
88 vmask >>= 1;
89
90 if (bits->cur_byte & bits->cur_mask)
91 {
92 value |= vmask;
93 }
94
95 bits->cur_mask <<= 1;
96
97 if (vmask == 1) { goto done; }
98 }
99 while (bits->cur_mask != 0x100);
100
101 next_byte:
102
103 if (*input == input_max)
104 {
105 stream->msg = "secondary decoder end of input";
106 return XD3_INTERNAL;
107 }
108
109 bits->cur_byte = *(*input)++;
110 bits->cur_mask = 1;
111 }
112
113 done:
114
115 IF_DEBUG2 (DP(RINT "(d) %u ", value));
116
117 (*valuep) = value;
118 return 0;
119}
120
121#if REGRESSION_TEST
122/* There may be extra bits at the end of secondary decompression, this macro checks for
123 * non-zero bits. This is overly strict, but helps pass the single-bit-error regression
124 * test. */
125static int
126xd3_test_clean_bits (xd3_stream *stream, bit_state *bits)
127{
128 for (; bits->cur_mask != 0x100; bits->cur_mask <<= 1)
129 {
130 if (bits->cur_byte & bits->cur_mask)
131 {
132 stream->msg = "secondary decoder garbage";
133 return XD3_INTERNAL;
134 }
135 }
136
137 return 0;
138}
139#endif
140
141static xd3_sec_stream*
142xd3_get_secondary (xd3_stream *stream, xd3_sec_stream **sec_streamp)
143{
144 xd3_sec_stream *sec_stream;
145
146 if ((sec_stream = *sec_streamp) == NULL)
147 {
148 if ((*sec_streamp = stream->sec_type->alloc (stream)) == NULL)
149 {
150 return NULL;
151 }
152
153 sec_stream = *sec_streamp;
154
155 /* If cuumulative stats, init once. */
156 stream->sec_type->init (sec_stream);
157 }
158
159 return sec_stream;
160}
161
162static int
163xd3_decode_secondary (xd3_stream *stream,
164 xd3_desect *sect,
165 xd3_sec_stream **sec_streamp)
166{
167 xd3_sec_stream *sec_stream;
168 uint32_t dec_size;
169 uint8_t *out_used;
170 int ret;
171
172 if ((sec_stream = xd3_get_secondary (stream, sec_streamp)) == NULL) { return ENOMEM; }
173
174 /* Decode the size, allocate the buffer. */
175 if ((ret = xd3_read_size (stream, & sect->buf, sect->buf_max, & dec_size)) ||
176 (ret = xd3_decode_allocate (stream, dec_size, & sect->copied2, & sect->alloc2, NULL, NULL)))
177 {
178 return ret;
179 }
180
181 out_used = sect->copied2;
182
183 if ((ret = stream->sec_type->decode (stream, sec_stream,
184 & sect->buf, sect->buf_max,
185 & out_used, out_used + dec_size))) { return ret; }
186
187 if (sect->buf != sect->buf_max)
188 {
189 stream->msg = "secondary decoder finished with unused input";
190 return XD3_INTERNAL;
191 }
192
193 if (out_used != sect->copied2 + dec_size)
194 {
195 stream->msg = "secondary decoder short output";
196 return XD3_INTERNAL;
197 }
198
199 sect->buf = sect->copied2;
200 sect->buf_max = sect->copied2 + dec_size;
201
202 return 0;
203}
204
205#if XD3_ENCODER
206/* OPT: Should these be inline? */
207static INLINE int xd3_encode_bit (xd3_stream *stream,
208 xd3_output **output,
209 bit_state *bits,
210 int bit)
211{
212 int ret;
213
214 if (bit)
215 {
216 bits->cur_byte |= bits->cur_mask;
217 }
218
219 /* OPT: Might help to buffer more than 8 bits at once. */
220 if (bits->cur_mask == 0x80)
221 {
222 if ((ret = xd3_emit_byte (stream, output, bits->cur_byte)) != 0) { return ret; }
223
224 bits->cur_mask = 1;
225 bits->cur_byte = 0;
226 }
227 else
228 {
229 bits->cur_mask <<= 1;
230 }
231
232 return 0;
233}
234
235static INLINE int xd3_flush_bits (xd3_stream *stream,
236 xd3_output **output,
237 bit_state *bits)
238{
239 return (bits->cur_mask == 1) ? 0 : xd3_emit_byte (stream, output, bits->cur_byte);
240}
241
242static INLINE int xd3_encode_bits (xd3_stream *stream,
243 xd3_output **output,
244 bit_state *bits,
245 usize_t nbits,
246 usize_t value)
247{
248 int ret;
249 usize_t mask = 1 << nbits;
250
251 XD3_ASSERT (nbits > 0);
252 XD3_ASSERT (nbits < sizeof (usize_t) * 8);
253 XD3_ASSERT (value < mask);
254
255 do
256 {
257 mask >>= 1;
258
259 if ((ret = xd3_encode_bit (stream, output, bits, value & mask))) { return ret; }
260 }
261 while (mask != 1);
262
263 IF_DEBUG2 (DP(RINT "(e) %u ", value));
264
265 return 0;
266}
267
268static int
269xd3_encode_secondary (xd3_stream *stream,
270 xd3_output **head,
271 xd3_output **tail,
272 xd3_sec_stream **sec_streamp,
273 xd3_sec_cfg *cfg,
274 int *did_it)
275{
276 xd3_sec_stream *sec_stream;
277 xd3_output *tmp_head;
278 xd3_output *tmp_tail;
279
280 usize_t comp_size;
281 usize_t orig_size;
282
283 int ret;
284
285 orig_size = xd3_sizeof_output (*head);
286
287 if (orig_size < SECONDARY_MIN_INPUT) { return 0; }
288
289 if ((sec_stream = xd3_get_secondary (stream, sec_streamp)) == NULL) { return ENOMEM; }
290
291 tmp_head = xd3_alloc_output (stream, NULL);
292
293 /* Encode the size, encode the data. @@ Encoding the size makes it simpler, but is a
294 * little gross. Should not need the entire section in contiguous memory, but it is
295 * much easier this way. */
296 if ((ret = xd3_emit_size (stream, & tmp_head, orig_size)) ||
297 (ret = stream->sec_type->encode (stream, sec_stream, *head, tmp_head, cfg))) { goto getout; }
298
299 /* If the secondary compressor determines its no good, it returns XD3_NOSECOND. */
300
301 /* Setup tmp_tail, comp_size */
302 tmp_tail = tmp_head;
303 comp_size = tmp_head->next;
304
305 while (tmp_tail->next_page != NULL)
306 {
307 tmp_tail = tmp_tail->next_page;
308 comp_size += tmp_tail->next;
309 }
310
311 XD3_ASSERT (comp_size == xd3_sizeof_output (tmp_head));
312 XD3_ASSERT (tmp_tail != NULL);
313
314 if (comp_size < (orig_size - SECONDARY_MIN_SAVINGS))
315 {
316 IF_DEBUG1(DP(RINT "secondary saved %u bytes: %u -> %u (%0.2f%%)\n",
317 orig_size - comp_size, orig_size, comp_size,
318 (double) comp_size / (double) orig_size));
319
320 xd3_free_output (stream, *head);
321
322 *head = tmp_head;
323 *tail = tmp_tail;
324 *did_it = 1;
325 }
326 else
327 {
328 getout:
329 if (ret == XD3_NOSECOND) { ret = 0; }
330 xd3_free_output (stream, tmp_head);
331 }
332
333 return ret;
334}
335#endif /* XD3_ENCODER */
336#endif /* _XDELTA3_SECOND_H_ */
Note: See TracBrowser for help on using the repository browser.