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

Last change on this file since 870 was 185, checked in by geyser, 18 years ago
File size: 21.6 KB
RevLine 
[185]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.