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

Last change on this file since 185 was 185, checked in by geyser, 14 years ago
File size: 21.6 KB
Line 
1/* xdelta 3 - delta compression tools and library
2 * Copyright (C) 2002, 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/* For demonstration purposes only.
20 */
21
22#ifndef _XDELTA3_FGK_h_
23#define _XDELTA3_FGK_h_
24
25/* An implementation of the FGK algorithm described by D.E. Knuth in "Dynamic Huffman
26 * Coding" in Journal of Algorithms 6. */
27
28/* A 32bit counter (fgk_weight) is used as the frequency counter for nodes in the huffman
29 * tree.  @!@ Need to test for overflow and/or reset stats. */
30
31typedef struct _fgk_stream fgk_stream;
32typedef struct _fgk_node   fgk_node;
33typedef struct _fgk_block  fgk_block;
34typedef unsigned int       fgk_bit;
35typedef uint32_t           fgk_weight;
36
37struct _fgk_block {
38  union {
39    fgk_node  *un_leader;
40    fgk_block *un_freeptr;
41  } un;
42};
43
44#define block_leader  un.un_leader
45#define block_freeptr un.un_freeptr
46
47/* The code can also support fixed huffman encoding/decoding. */
48#define IS_ADAPTIVE 1
49
50/* weight is a count of the number of times this element has been seen in the current
51 * encoding/decoding.  parent, right_child, and left_child are pointers defining the tree
52 * structure.  right and left point to neighbors in an ordered sequence of
53 * weights.  The left child of a node is always guaranteed to have weight not greater than
54 * its sibling.  fgk_blockLeader points to the element with the same weight as itself which is
55 * closest to the next increasing weight block.  */
56struct _fgk_node
57{
58  fgk_weight  weight;
59  fgk_node   *parent;
60  fgk_node   *left_child;
61  fgk_node   *right_child;
62  fgk_node   *left;
63  fgk_node   *right;
64  fgk_block  *my_block;
65};
66
67/* alphabet_size is the a count of the number of possible leaves in the huffman tree.  The
68 * number of total nodes counting internal nodes is ((2 * alphabet_size) - 1).
69 * zero_freq_count is the number of elements remaining which have zero frequency.
70 * zero_freq_exp and zero_freq_rem satisfy the equation zero_freq_count = 2^zero_freq_exp +
71 * zero_freq_rem.  root_node is the root of the tree, which is initialized to a node with
72 * zero frequency and contains the 0th such element.  free_node contains a pointer to the
73 * next available fgk_node space.  alphabet contains all the elements and is indexed by N.
74 * remaining_zeros points to the head of the list of zeros.  */
75struct _fgk_stream
76{
77  int alphabet_size;
78  int zero_freq_count;
79  int zero_freq_exp;
80  int zero_freq_rem;
81  int coded_depth;
82
83  int total_nodes;
84  int total_blocks;
85
86  fgk_bit *coded_bits;
87
88  fgk_block *block_array;
89  fgk_block *free_block;
90
91  fgk_node *decode_ptr;
92  fgk_node *remaining_zeros;
93  fgk_node *alphabet;
94  fgk_node *root_node;
95  fgk_node *free_node;
96};
97
98/*********************************************************************/
99/*                             Encoder                               */
100/*********************************************************************/
101
102static fgk_stream*     fgk_alloc           (xd3_stream *stream /*, int alphabet_size */);
103static void            fgk_init            (fgk_stream *h);
104static int             fgk_encode_data     (fgk_stream *h,
105                                            int         n);
106static INLINE fgk_bit  fgk_get_encoded_bit (fgk_stream *h);
107
108static int             xd3_encode_fgk      (xd3_stream  *stream,
109                                            fgk_stream  *sec_stream,
110                                            xd3_output  *input,
111                                            xd3_output  *output,
112                                            xd3_sec_cfg *cfg);
113
114/*********************************************************************/
115/*                             Decoder                               */
116/*********************************************************************/
117
118static INLINE int      fgk_decode_bit      (fgk_stream *h,
119                                            fgk_bit     b);
120static int             fgk_decode_data     (fgk_stream *h);
121static void            fgk_destroy         (xd3_stream *stream,
122                                            fgk_stream *h);
123
124static int             xd3_decode_fgk      (xd3_stream     *stream,
125                                            fgk_stream     *sec_stream,
126                                            const uint8_t **input,
127                                            const uint8_t  *const input_end,
128                                            uint8_t       **output,
129                                            const uint8_t  *const output_end);
130
131/*********************************************************************/
132/*                             Private                               */
133/*********************************************************************/
134
135static unsigned int fgk_find_nth_zero        (fgk_stream *h, int n);
136static int          fgk_nth_zero             (fgk_stream *h, int n);
137static void         fgk_update_tree          (fgk_stream *h, int n);
138static fgk_node*    fgk_increase_zero_weight (fgk_stream *h, int n);
139static void         fgk_eliminate_zero       (fgk_stream* h, fgk_node *node);
140static void         fgk_move_right           (fgk_stream *h, fgk_node *node);
141static void         fgk_promote              (fgk_stream *h, fgk_node *node);
142static void         fgk_init_node            (fgk_node *node, int i, int size);
143static fgk_block*   fgk_make_block           (fgk_stream *h, fgk_node *l);
144static void         fgk_free_block           (fgk_stream *h, fgk_block *b);
145static void         fgk_factor_remaining     (fgk_stream *h);
146static INLINE void  fgk_swap_ptrs            (fgk_node **one, fgk_node **two);
147
148/*********************************************************************/
149/*                          Basic Routines                           */
150/*********************************************************************/
151
152/* returns an initialized huffman encoder for an alphabet with the
153 * given size.  returns NULL if enough memory cannot be allocated */
154static fgk_stream* fgk_alloc (xd3_stream *stream /*, int alphabet_size0 */)
155{
156  int alphabet_size0 = ALPHABET_SIZE;
157  fgk_stream *h;
158
159  if ((h = (fgk_stream*) xd3_alloc (stream, 1, sizeof (fgk_stream))) == NULL)
160    {
161      return NULL;
162    }
163
164  h->total_nodes  = (2 * alphabet_size0) - 1;
165  h->total_blocks = (2 * h->total_nodes);
166  h->alphabet     = (fgk_node*)  xd3_alloc (stream, h->total_nodes,    sizeof (fgk_node));
167  h->block_array  = (fgk_block*) xd3_alloc (stream, h->total_blocks,   sizeof (fgk_block));
168  h->coded_bits   = (fgk_bit*)   xd3_alloc (stream, alphabet_size0, sizeof (fgk_bit));
169
170  if (h->coded_bits  == NULL ||
171      h->alphabet    == NULL ||
172      h->block_array == NULL)
173    {
174      fgk_destroy (stream, h);
175      return NULL;
176    }
177
178  h->alphabet_size   = alphabet_size0;
179
180  return h;
181}
182
183static void fgk_init (fgk_stream *h)
184{
185  int i;
186
187  h->root_node       = h->alphabet;
188  h->decode_ptr      = h->root_node;
189  h->free_node       = h->alphabet + h->alphabet_size;
190  h->remaining_zeros = h->alphabet;
191  h->coded_depth     = 0;
192  h->zero_freq_count = h->alphabet_size + 2;
193
194  /* after two calls to factor_remaining, zero_freq_count == alphabet_size */
195  fgk_factor_remaining(h); /* set ZFE and ZFR */
196  fgk_factor_remaining(h); /* set ZFDB according to prev state */
197
198  IF_DEBUG (memset (h->alphabet, 0, sizeof (h->alphabet[0]) * h->total_nodes));
199
200  for (i = 0; i < h->total_blocks-1; i += 1)
201    {
202      h->block_array[i].block_freeptr = &h->block_array[i + 1];
203    }
204
205  h->block_array[h->total_blocks - 1].block_freeptr = NULL;
206  h->free_block = h->block_array;
207
208  /* Zero frequency nodes are inserted in the first alphabet_size
209   * positions, with Value, weight, and a pointer to the next zero
210   * frequency node.  */
211  for (i = h->alphabet_size - 1; i >= 0; i -= 1)
212    {
213      fgk_init_node (h->alphabet + i, i, h->alphabet_size);
214    }
215}
216
217static void fgk_swap_ptrs(fgk_node **one, fgk_node **two)
218{
219  fgk_node *tmp = *one;
220  *one = *two;
221  *two = tmp;
222}
223
224/* Takes huffman transmitter h and n, the nth elt in the alphabet, and
225 * returns the number of required to encode n. */
226static int fgk_encode_data (fgk_stream* h, int n)
227{
228  fgk_node *target_ptr = h->alphabet + n;
229
230  XD3_ASSERT (n < h->alphabet_size);
231
232  h->coded_depth = 0;
233
234  /* First encode the binary representation of the nth remaining
235   * zero frequency element in reverse such that bit, which will be
236   * encoded from h->coded_depth down to 0 will arrive in increasing
237   * order following the tree path.  If there is only one left, it
238   * is not neccesary to encode these bits. */
239  if (IS_ADAPTIVE && target_ptr->weight == 0)
240    {
241      unsigned int where, shift;
242      int bits;
243
244      where = fgk_find_nth_zero(h, n);
245      shift = 1;
246
247      if (h->zero_freq_rem == 0)
248        {
249          bits = h->zero_freq_exp;
250        }
251      else
252        {
253          bits = h->zero_freq_exp + 1;
254        }
255
256      while (bits > 0)
257        {
258          h->coded_bits[h->coded_depth++] = (shift & where) && 1;
259
260          bits   -= 1;
261          shift <<= 1;
262        };
263
264      target_ptr = h->remaining_zeros;
265    }
266
267  /* The path from root to node is filled into coded_bits in reverse so
268   * that it is encoded in the right order */
269  while (target_ptr != h->root_node)
270    {
271      h->coded_bits[h->coded_depth++] = (target_ptr->parent->right_child == target_ptr);
272
273      target_ptr = target_ptr->parent;
274    }
275
276  if (IS_ADAPTIVE)
277    {
278      fgk_update_tree(h, n);
279    }
280
281  return h->coded_depth;
282}
283
284/* Should be called as many times as fgk_encode_data returns.
285 */
286static INLINE fgk_bit fgk_get_encoded_bit (fgk_stream *h)
287{
288  XD3_ASSERT (h->coded_depth > 0);
289
290  return h->coded_bits[--h->coded_depth];
291}
292
293/* This procedure updates the tree after alphabet[n] has been encoded
294 * or decoded.
295 */
296static void fgk_update_tree (fgk_stream *h, int n)
297{
298  fgk_node *incr_node;
299
300  if (h->alphabet[n].weight == 0)
301    {
302      incr_node = fgk_increase_zero_weight (h, n);
303    }
304  else
305    {
306      incr_node = h->alphabet + n;
307    }
308
309  while (incr_node != h->root_node)
310    {
311      fgk_move_right (h, incr_node);
312      fgk_promote    (h, incr_node);
313      incr_node->weight += 1;   /* incr the parent */
314      incr_node = incr_node->parent; /* repeat */
315    }
316
317  h->root_node->weight += 1;
318}
319
320static void fgk_move_right (fgk_stream *h, fgk_node *move_fwd)
321{
322  fgk_node **fwd_par_ptr, **back_par_ptr;
323  fgk_node *move_back, *tmp;
324
325  move_back = move_fwd->my_block->block_leader;
326
327  if (move_fwd         == move_back ||
328      move_fwd->parent == move_back ||
329      move_fwd->weight == 0)
330    {
331      return;
332    }
333
334  move_back->right->left = move_fwd;
335
336  if (move_fwd->left)
337    {
338      move_fwd->left->right = move_back;
339    }
340
341  tmp = move_fwd->right;
342  move_fwd->right = move_back->right;
343
344  if (tmp == move_back)
345    {
346      move_back->right = move_fwd;
347    }
348  else
349    {
350      tmp->left = move_back;
351      move_back->right = tmp;
352    }
353
354  tmp = move_back->left;
355  move_back->left = move_fwd->left;
356
357  if (tmp == move_fwd)
358    {
359      move_fwd->left = move_back;
360    }
361  else
362    {
363      tmp->right = move_fwd;
364      move_fwd->left = tmp;
365    }
366
367  if (move_fwd->parent->right_child == move_fwd)
368    {
369      fwd_par_ptr = &move_fwd->parent->right_child;
370    }
371  else
372    {
373      fwd_par_ptr = &move_fwd->parent->left_child;
374    }
375
376  if (move_back->parent->right_child == move_back)
377    {
378      back_par_ptr = &move_back->parent->right_child;
379    }
380  else
381    {
382      back_par_ptr = &move_back->parent->left_child;
383    }
384
385  fgk_swap_ptrs (&move_fwd->parent, &move_back->parent);
386  fgk_swap_ptrs (fwd_par_ptr, back_par_ptr);
387
388  move_fwd->my_block->block_leader = move_fwd;
389}
390
391/* Shifts node, the leader of its block, into the next block. */
392static void fgk_promote (fgk_stream *h, fgk_node *node)
393{
394  fgk_node *my_left, *my_right;
395  fgk_block *cur_block;
396
397  my_right  = node->right;
398  my_left   = node->left;
399  cur_block = node->my_block;
400
401  if (node->weight == 0)
402    {
403      return;
404    }
405
406  /* if left is right child, parent of remaining zeros case (?), means parent
407   * has same weight as right child. */
408  if (my_left == node->right_child &&
409      node->left_child &&
410      node->left_child->weight == 0)
411    {
412      XD3_ASSERT (node->left_child == h->remaining_zeros);
413      XD3_ASSERT (node->right_child->weight == (node->weight+1)); /* child weight was already incremented */
414     
415      if (node->weight == (my_right->weight - 1) && my_right != h->root_node)
416        {
417          fgk_free_block (h, cur_block);
418          node->my_block    = my_right->my_block;
419          my_left->my_block = my_right->my_block;
420        }
421
422      return;
423    }
424
425  if (my_left == h->remaining_zeros)
426    {
427      return;
428    }
429
430  /* true if not the leftmost node */
431  if (my_left->my_block == cur_block)
432    {
433      my_left->my_block->block_leader = my_left;
434    }
435  else
436    {
437      fgk_free_block (h, cur_block);
438    }
439
440  /* node->parent != my_right */
441  if ((node->weight == (my_right->weight - 1)) && (my_right != h->root_node))
442    {
443      node->my_block = my_right->my_block;
444    }
445  else
446    {
447      node->my_block = fgk_make_block (h, node);
448    }
449}
450
451/* When an element is seen the first time this is called to remove it from the list of
452 * zero weight elements and introduce a new internal node to the tree.  */
453static fgk_node* fgk_increase_zero_weight (fgk_stream *h, int n)
454{
455  fgk_node *this_zero, *new_internal, *zero_ptr;
456
457  this_zero = h->alphabet + n;
458
459  if (h->zero_freq_count == 1)
460    {
461      /* this is the last one */
462      this_zero->right_child = NULL;
463
464      if (this_zero->right->weight == 1)
465        {
466          this_zero->my_block = this_zero->right->my_block;
467        }
468      else
469        {
470          this_zero->my_block = fgk_make_block (h, this_zero);
471        }
472
473      h->remaining_zeros = NULL;
474
475      return this_zero;
476    }
477
478  zero_ptr = h->remaining_zeros;
479
480  new_internal = h->free_node++;
481
482  new_internal->parent      = zero_ptr->parent;
483  new_internal->right       = zero_ptr->right;
484  new_internal->weight      = 0;
485  new_internal->right_child = this_zero;
486  new_internal->left        = this_zero;
487
488  if (h->remaining_zeros == h->root_node)
489    {
490      /* This is the first element to be coded */
491      h->root_node           = new_internal;
492      this_zero->my_block    = fgk_make_block (h, this_zero);
493      new_internal->my_block = fgk_make_block (h, new_internal);
494    }
495  else
496    {
497      new_internal->right->left = new_internal;
498
499      if (zero_ptr->parent->right_child == zero_ptr)
500        {
501          zero_ptr->parent->right_child = new_internal;
502        }
503      else
504        {
505          zero_ptr->parent->left_child = new_internal;
506        }
507
508      if (new_internal->right->weight == 1)
509        {
510          new_internal->my_block = new_internal->right->my_block;
511        }
512      else
513        {
514          new_internal->my_block = fgk_make_block (h, new_internal);
515        }
516
517      this_zero->my_block = new_internal->my_block;
518    }
519
520  fgk_eliminate_zero (h, this_zero);
521
522  new_internal->left_child = h->remaining_zeros;
523
524  this_zero->right       = new_internal;
525  this_zero->left        = h->remaining_zeros;
526  this_zero->parent      = new_internal;
527  this_zero->left_child  = NULL;
528  this_zero->right_child = NULL;
529
530  h->remaining_zeros->parent = new_internal;
531  h->remaining_zeros->right  = this_zero;
532
533  return this_zero;
534}
535
536/* When a zero frequency element is encoded, it is followed by the binary representation
537 * of the index into the remaining elements.  Sets a cache to the element before it so
538 * that it can be removed without calling this procedure again.  */
539static unsigned int fgk_find_nth_zero (fgk_stream* h, int n)
540{
541  fgk_node *target_ptr = h->alphabet + n;
542  fgk_node *head_ptr = h->remaining_zeros;
543  unsigned int idx = 0;
544
545  while (target_ptr != head_ptr)
546    {
547      head_ptr = head_ptr->right_child;
548      idx += 1;
549    }
550
551  return idx;
552}
553
554/* Splices node out of the list of zeros. */
555static void fgk_eliminate_zero (fgk_stream* h, fgk_node *node)
556{
557  if (h->zero_freq_count == 1)
558    {
559      return;
560    }
561
562  fgk_factor_remaining(h);
563
564  if (node->left_child == NULL)
565    {
566      h->remaining_zeros = h->remaining_zeros->right_child;
567      h->remaining_zeros->left_child = NULL;
568    }
569  else if (node->right_child == NULL)
570    {
571      node->left_child->right_child = NULL;
572    }
573  else
574    {
575      node->right_child->left_child = node->left_child;
576      node->left_child->right_child = node->right_child;
577    }
578}
579
580static void fgk_init_node (fgk_node *node, int i, int size)
581{
582  if (i < size - 1)
583    {
584      node->right_child = node + 1;
585    }
586  else
587    {
588      node->right_child = NULL;
589    }
590
591  if (i >= 1)
592    {
593      node->left_child = node - 1;
594    }
595  else
596    {
597      node->left_child = NULL;
598    }
599
600  node->weight      = 0;
601  node->parent      = NULL;
602  node->right = NULL;
603  node->left  = NULL;
604  node->my_block    = NULL;
605}
606
607/* The data structure used is an array of blocks, which are unions of free pointers and
608 * huffnode pointers.  free blocks are a linked list of free blocks, the front of which is
609 * h->free_block.  The used blocks are pointers to the head of each block.  */
610static fgk_block* fgk_make_block (fgk_stream *h, fgk_node* lead)
611{
612  fgk_block *ret = h->free_block;
613
614  XD3_ASSERT (h->free_block != NULL);
615
616  h->free_block = h->free_block->block_freeptr;
617
618  ret->block_leader = lead;
619
620  return ret;
621}
622
623/* Restores the block to the front of the free list. */
624static void fgk_free_block (fgk_stream *h, fgk_block *b)
625{
626  b->block_freeptr = h->free_block;
627  h->free_block = b;
628}
629
630/* sets zero_freq_count, zero_freq_rem, and zero_freq_exp to satsity the equation given
631 * above.  */
632static void fgk_factor_remaining (fgk_stream *h)
633{
634  unsigned int i;
635
636  i = (--h->zero_freq_count);
637  h->zero_freq_exp = 0;
638
639  while (i > 1)
640    {
641      h->zero_freq_exp += 1;
642      i >>= 1;
643    }
644
645  i = 1 << h->zero_freq_exp;
646
647  h->zero_freq_rem = h->zero_freq_count - i;
648}
649
650/* receives a bit at a time and returns true when a complete code has
651 * been received.
652 */
653static int INLINE fgk_decode_bit (fgk_stream* h, fgk_bit b)
654{
655  XD3_ASSERT (b == 1 || b == 0);
656
657  if (IS_ADAPTIVE && h->decode_ptr->weight == 0)
658    {
659      int bitsreq;
660
661      if (h->zero_freq_rem == 0)
662        {
663          bitsreq = h->zero_freq_exp;
664        }
665      else
666        {
667          bitsreq = h->zero_freq_exp + 1;
668        }
669
670      h->coded_bits[h->coded_depth] = b;
671      h->coded_depth += 1;
672
673      return h->coded_depth >= bitsreq;
674    }
675  else
676    {
677      if (b)
678        {
679          h->decode_ptr = h->decode_ptr->right_child;
680        }
681      else
682        {
683          h->decode_ptr = h->decode_ptr->left_child;
684        }
685
686      if (h->decode_ptr->left_child == NULL)
687        {
688          /* If the weight is non-zero, finished. */
689          if (h->decode_ptr->weight != 0)
690            {
691              return 1;
692            }
693
694          /* zero_freq_count is dropping to 0, finished. */
695          return h->zero_freq_count == 1;
696        }
697      else
698        {
699          return 0;
700        }
701    }
702}
703
704static int fgk_nth_zero (fgk_stream* h, int n)
705{
706  fgk_node *ret = h->remaining_zeros;
707
708  /* ERROR: if during this loop (ret->right_child == NULL) then the encoder's zero count
709   * is too high.  Could return an error code now, but is probably unnecessary overhead,
710   * since the caller should check integrity anyway. */
711  for (; n != 0 && ret->right_child != NULL; n -= 1)
712    {
713      ret = ret->right_child;
714    }
715
716  return ret - h->alphabet;
717}
718
719/* once fgk_decode_bit returns 1, this retrieves an index into the
720 * alphabet otherwise this returns 0, indicating more bits are
721 * required.
722 */
723static int fgk_decode_data (fgk_stream* h)
724{
725  unsigned int elt = h->decode_ptr - h->alphabet;
726
727  if (IS_ADAPTIVE && h->decode_ptr->weight == 0) {
728    int i;
729    unsigned int n = 0;
730
731    for (i = 0; i < h->coded_depth - 1; i += 1)
732      {
733        n |= h->coded_bits[i];
734        n <<= 1;
735      }
736
737    n |= h->coded_bits[i];
738    elt = fgk_nth_zero(h, n);
739  }
740
741  h->coded_depth = 0;
742
743  if (IS_ADAPTIVE)
744    {
745      fgk_update_tree(h, elt);
746    }
747
748  h->decode_ptr = h->root_node;
749
750  return elt;
751}
752
753static void fgk_destroy (xd3_stream *stream,
754                         fgk_stream *h)
755{
756  if (h != NULL)
757    {
758      xd3_free (stream, h->alphabet);
759      xd3_free (stream, h->coded_bits);
760      xd3_free (stream, h->block_array);
761      xd3_free (stream, h);
762    }
763}
764
765/*********************************************************************/
766/*                             Xdelta                                */
767/*********************************************************************/
768
769static int
770xd3_encode_fgk (xd3_stream *stream, fgk_stream *sec_stream, xd3_output *input, xd3_output *output, xd3_sec_cfg *cfg)
771{
772  bit_state   bstate = BIT_STATE_ENCODE_INIT;
773  xd3_output *cur_page;
774  int ret;
775
776  /* OPT: quit compression early if it looks bad */
777  for (cur_page = input; cur_page; cur_page = cur_page->next_page)
778    {
779      const uint8_t *inp     = cur_page->base;
780      const uint8_t *inp_max = inp + cur_page->next;
781
782      while (inp < inp_max)
783        {
784          usize_t bits = fgk_encode_data (sec_stream, *inp++);
785
786          while (bits--)
787            {
788              if ((ret = xd3_encode_bit (stream, & output, & bstate, fgk_get_encoded_bit (sec_stream)))) { return ret; }
789            }
790        }
791    }
792
793  return xd3_flush_bits (stream, & output, & bstate);
794}
795
796static int
797xd3_decode_fgk (xd3_stream     *stream,
798                fgk_stream     *sec_stream,
799                const uint8_t **input_pos,
800                const uint8_t  *const input_max,
801                uint8_t       **output_pos,
802                const uint8_t  *const output_max)
803{
804  bit_state bstate;
805  uint8_t *output = *output_pos;
806  const uint8_t *input = *input_pos;
807
808  for (;;)
809    {
810      if (input == input_max)
811        {
812          stream->msg = "secondary decoder end of input";
813          return XD3_INTERNAL;
814        }
815
816      bstate.cur_byte = *input++;
817
818      for (bstate.cur_mask = 1; bstate.cur_mask != 0x100; bstate.cur_mask <<= 1)
819        {
820          int done = fgk_decode_bit (sec_stream, (bstate.cur_byte & bstate.cur_mask) && 1);
821
822          if (! done) { continue; }
823
824          *output++ = fgk_decode_data (sec_stream);
825
826          if (unlikely (output == output_max))
827            {
828              /* During regression testing: */
829              IF_REGRESSION ({
830                int ret;
831                bstate.cur_mask <<= 1;
832                if ((ret = xd3_test_clean_bits (stream, & bstate))) { return ret; }
833              });
834
835              (*output_pos) = output;
836              (*input_pos) = input;
837              return 0;
838            }
839        }
840    }
841}
842
843#endif /* _XDELTA3_FGK_ */
Note: See TracBrowser for help on using the repository browser.