"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/xdelta3-second.h" (5 Jan 2016, 7326 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-second.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, 2003, 2006, 2007, 2013.  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 #ifndef _XDELTA3_SECOND_H_
   20 #define _XDELTA3_SECOND_H_
   21 
   22 static inline void xd3_bit_state_encode_init (bit_state *bits)
   23 {
   24   bits->cur_byte = 0;
   25   bits->cur_mask = 1;
   26 }
   27 
   28 static inline int xd3_decode_bits (xd3_stream     *stream,
   29                    bit_state      *bits,
   30                    const uint8_t **input,
   31                    const uint8_t  *input_max,
   32                    usize_t         nbits,
   33                    usize_t        *valuep)
   34 {
   35   usize_t value = 0;
   36   usize_t vmask = 1 << nbits;
   37 
   38   if (bits->cur_mask == 0x100) { goto next_byte; }
   39 
   40   for (;;)
   41     {
   42       do
   43     {
   44       vmask >>= 1;
   45 
   46       if (bits->cur_byte & bits->cur_mask)
   47         {
   48           value |= vmask;
   49         }
   50 
   51       bits->cur_mask <<= 1;
   52 
   53       if (vmask == 1) { goto done; }
   54     }
   55       while (bits->cur_mask != 0x100);
   56 
   57     next_byte:
   58 
   59       if (*input == input_max)
   60     {
   61       stream->msg = "secondary decoder end of input";
   62       return XD3_INTERNAL;
   63     }
   64 
   65       bits->cur_byte = *(*input)++;
   66       bits->cur_mask = 1;
   67     }
   68 
   69  done:
   70 
   71   IF_DEBUG2 (DP(RINT "(d) %"W"u ", value));
   72 
   73   (*valuep) = value;
   74   return 0;
   75 }
   76 
   77 #if REGRESSION_TEST
   78 /* There may be extra bits at the end of secondary decompression, this macro
   79  * checks for non-zero bits.  This is overly strict, but helps pass the
   80  * single-bit-error regression test. */
   81 static int
   82 xd3_test_clean_bits (xd3_stream *stream, bit_state *bits)
   83 {
   84   for (; bits->cur_mask != 0x100; bits->cur_mask <<= 1)
   85     {
   86       if (bits->cur_byte & bits->cur_mask)
   87     {
   88       stream->msg = "secondary decoder garbage";
   89       return XD3_INTERNAL;
   90     }
   91     }
   92 
   93   return 0;
   94 }
   95 #endif
   96 
   97 static int
   98 xd3_get_secondary (xd3_stream *stream, xd3_sec_stream **sec_streamp, 
   99            int is_encode)
  100 {
  101   if (*sec_streamp == NULL)
  102     {
  103       int ret;
  104 
  105       if ((*sec_streamp = stream->sec_type->alloc (stream)) == NULL)
  106     {
  107       stream->msg = "error initializing secondary stream";
  108       return XD3_INVALID;
  109     }
  110 
  111       if ((ret = stream->sec_type->init (stream, *sec_streamp, is_encode)) != 0)
  112     {
  113       return ret;
  114     }
  115     }
  116 
  117   return 0;
  118 }
  119 
  120 static int
  121 xd3_decode_secondary (xd3_stream      *stream,
  122               xd3_desect      *sect,
  123               xd3_sec_stream **sec_streamp)
  124 {
  125   usize_t dec_size;
  126   uint8_t *out_used;
  127   int ret;
  128 
  129   if ((ret = xd3_get_secondary (stream, sec_streamp, 0)) != 0)
  130     {
  131       return ret;
  132     }
  133 
  134   /* Decode the size, allocate the buffer. */
  135   if ((ret = xd3_read_size (stream, & sect->buf,
  136                 sect->buf_max, & dec_size)) ||
  137       (ret = xd3_decode_allocate (stream, dec_size,
  138                   & sect->copied2, & sect->alloc2)))
  139     {
  140       return ret;
  141     }
  142 
  143   if (dec_size == 0)
  144     {
  145       stream->msg = "secondary decoder invalid output size";
  146       return XD3_INVALID_INPUT;
  147     }
  148 
  149   out_used = sect->copied2;
  150 
  151   if ((ret = stream->sec_type->decode (stream, *sec_streamp,
  152                        & sect->buf, sect->buf_max,
  153                        & out_used, out_used + dec_size)))
  154     {
  155       return ret;
  156     }
  157 
  158   if (sect->buf != sect->buf_max)
  159     {
  160       stream->msg = "secondary decoder finished with unused input";
  161       return XD3_INTERNAL;
  162     }
  163 
  164   if (out_used != sect->copied2 + dec_size)
  165     {
  166       stream->msg = "secondary decoder short output";
  167       return XD3_INTERNAL;
  168     }
  169 
  170   sect->buf = sect->copied2;
  171   sect->buf_max = sect->copied2 + dec_size;
  172   sect->size = dec_size;
  173 
  174   return 0;
  175 }
  176 
  177 #if XD3_ENCODER
  178 static inline int xd3_encode_bit (xd3_stream      *stream,
  179                   xd3_output     **output,
  180                   bit_state       *bits,
  181                   usize_t          bit)
  182 {
  183   int ret;
  184 
  185   if (bit)
  186     {
  187       bits->cur_byte |= bits->cur_mask;
  188     }
  189 
  190   /* OPT: Might help to buffer more than 8 bits at once. */
  191   if (bits->cur_mask == 0x80)
  192     {
  193       if ((ret = xd3_emit_byte (stream, output, bits->cur_byte)) != 0)
  194     {
  195       return ret;
  196     }
  197 
  198       bits->cur_mask = 1;
  199       bits->cur_byte = 0;
  200     }
  201   else
  202     {
  203       bits->cur_mask <<= 1;
  204     }
  205 
  206   return 0;
  207 }
  208 
  209 static inline int xd3_flush_bits (xd3_stream      *stream,
  210                   xd3_output     **output,
  211                   bit_state       *bits)
  212 {
  213   return (bits->cur_mask == 1) ? 0 :
  214     xd3_emit_byte (stream, output, bits->cur_byte);
  215 }
  216 
  217 static inline int xd3_encode_bits (xd3_stream      *stream,
  218                    xd3_output     **output,
  219                    bit_state       *bits,
  220                    usize_t           nbits,
  221                    usize_t           value)
  222 {
  223   int ret;
  224   usize_t mask = 1 << nbits;
  225 
  226   XD3_ASSERT (nbits > 0);
  227   XD3_ASSERT (nbits < sizeof (usize_t) * 8);
  228   XD3_ASSERT (value < mask);
  229 
  230   do
  231     {
  232       mask >>= 1;
  233 
  234       if ((ret = xd3_encode_bit (stream, output, bits, value & mask)))
  235     {
  236       return ret;
  237     }
  238     }
  239   while (mask != 1);
  240 
  241   IF_DEBUG2 (DP(RINT "(e) %"W"u ", value));
  242 
  243   return 0;
  244 }
  245 
  246 static int
  247 xd3_encode_secondary (xd3_stream      *stream,
  248               xd3_output     **head,
  249               xd3_output     **tail,
  250               xd3_sec_stream **sec_streamp,
  251               xd3_sec_cfg     *cfg,
  252               int             *did_it)
  253 {
  254   xd3_output     *tmp_head;
  255   xd3_output     *tmp_tail;
  256 
  257   usize_t comp_size;
  258   usize_t orig_size;
  259 
  260   int ret;
  261 
  262   orig_size = xd3_sizeof_output (*head);
  263 
  264   if (orig_size < SECONDARY_MIN_INPUT) { return 0; }
  265 
  266   if ((ret = xd3_get_secondary (stream, sec_streamp, 1)) != 0)
  267     {
  268       return ret;
  269     }
  270 
  271   tmp_head = xd3_alloc_output (stream, NULL);
  272 
  273   /* Encode the size, encode the data.  Encoding the size makes it
  274    * simpler, but is a little gross.  Should not need the entire
  275    * section in contiguous memory, but it is much easier this way. */
  276   if ((ret = xd3_emit_size (stream, & tmp_head, orig_size)) ||
  277       (ret = stream->sec_type->encode (stream, *sec_streamp, *head,
  278                        tmp_head, cfg)))
  279     {
  280       goto getout;
  281     }
  282 
  283   /* If the secondary compressor determines it's no good, it returns
  284    * XD3_NOSECOND. */
  285 
  286   /* Setup tmp_tail, comp_size */
  287   tmp_tail  = tmp_head;
  288   comp_size = tmp_head->next;
  289 
  290   while (tmp_tail->next_page != NULL)
  291     {
  292       tmp_tail = tmp_tail->next_page;
  293       comp_size += tmp_tail->next;
  294     }
  295 
  296   XD3_ASSERT (comp_size == xd3_sizeof_output (tmp_head));
  297   XD3_ASSERT (tmp_tail != NULL);
  298 
  299   if (comp_size < (orig_size - SECONDARY_MIN_SAVINGS) || cfg->inefficient)
  300     {
  301       if (comp_size < orig_size)
  302     {
  303       IF_DEBUG1(DP(RINT "[encode_secondary] saved %"W"u bytes: %"W"u -> %"W"u (%0.2f%%)\n",
  304                orig_size - comp_size, orig_size, comp_size,
  305                100.0 * (double) comp_size / (double) orig_size));
  306     }
  307 
  308       xd3_free_output (stream, *head);
  309 
  310       *head = tmp_head;
  311       *tail = tmp_tail;
  312       *did_it = 1;
  313     }
  314   else
  315     {
  316     getout:
  317       if (ret == XD3_NOSECOND) { ret = 0; }
  318       xd3_free_output (stream, tmp_head);
  319     }
  320 
  321   return ret;
  322 }
  323 #endif /* XD3_ENCODER */
  324 #endif /* _XDELTA3_SECOND_H_ */