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