"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/xdelta3-fgk.h" (26 Sep 2015, 22461 Bytes) of package /linux/misc/xdelta3-3.1.0.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 and the latest Fossies "Diffs" side-by-side code changes report: 3.0.11_vs_3.1.0.

    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 usize_t         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 usize_t         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 usize_t 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       usize_t where, shift;
  253       usize_t 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 usize_t 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_ */