xdelta3-fgk.h

   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_ */