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

Last change on this file since 185 was 185, checked in by geyser, 14 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.