xdelta3-second.h

   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) %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   uint32_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   out_used = sect->copied2;
 144
 145   if ((ret = stream->sec_type->decode (stream, *sec_streamp,
 146                                        & sect->buf, sect->buf_max,
 147                                        & out_used, out_used + dec_size)))
 148     {
 149       return ret;
 150     }
 151
 152   if (sect->buf != sect->buf_max)
 153     {
 154       stream->msg = "secondary decoder finished with unused input";
 155       return XD3_INTERNAL;
 156     }
 157
 158   if (out_used != sect->copied2 + dec_size)
 159     {
 160       stream->msg = "secondary decoder short output";
 161       return XD3_INTERNAL;
 162     }
 163
 164   sect->buf = sect->copied2;
 165   sect->buf_max = sect->copied2 + dec_size;
 166   sect->size = dec_size;
 167
 168   return 0;
 169 }
 170
 171 #if XD3_ENCODER
 172 static inline int xd3_encode_bit (xd3_stream      *stream,
 173                                   xd3_output     **output,
 174                                   bit_state       *bits,
 175                                   usize_t          bit)
 176 {
 177   int ret;
 178
 179   if (bit)
 180     {
 181       bits->cur_byte |= bits->cur_mask;
 182     }
 183
 184   /* OPT: Might help to buffer more than 8 bits at once. */
 185   if (bits->cur_mask == 0x80)
 186     {
 187       if ((ret = xd3_emit_byte (stream, output, bits->cur_byte)) != 0)
 188         {
 189           return ret;
 190         }
 191
 192       bits->cur_mask = 1;
 193       bits->cur_byte = 0;
 194     }
 195   else
 196     {
 197       bits->cur_mask <<= 1;
 198     }
 199
 200   return 0;
 201 }
 202
 203 static inline int xd3_flush_bits (xd3_stream      *stream,
 204                                   xd3_output     **output,
 205                                   bit_state       *bits)
 206 {
 207   return (bits->cur_mask == 1) ? 0 :
 208     xd3_emit_byte (stream, output, bits->cur_byte);
 209 }
 210
 211 static inline int xd3_encode_bits (xd3_stream      *stream,
 212                                    xd3_output     **output,
 213                                    bit_state       *bits,
 214                                    usize_t           nbits,
 215                                    usize_t           value)
 216 {
 217   int ret;
 218   usize_t mask = 1 << nbits;
 219
 220   XD3_ASSERT (nbits > 0);
 221   XD3_ASSERT (nbits < sizeof (usize_t) * 8);
 222   XD3_ASSERT (value < mask);
 223
 224   do
 225     {
 226       mask >>= 1;
 227
 228       if ((ret = xd3_encode_bit (stream, output, bits, value & mask)))
 229         {
 230           return ret;
 231         }
 232     }
 233   while (mask != 1);
 234
 235   IF_DEBUG2 (DP(RINT "(e) %u ", value));
 236
 237   return 0;
 238 }
 239
 240 static int
 241 xd3_encode_secondary (xd3_stream      *stream,
 242                       xd3_output     **head,
 243                       xd3_output     **tail,
 244                       xd3_sec_stream **sec_streamp,
 245                       xd3_sec_cfg     *cfg,
 246                       int             *did_it)
 247 {
 248   xd3_output     *tmp_head;
 249   xd3_output     *tmp_tail;
 250
 251   usize_t comp_size;
 252   usize_t orig_size;
 253
 254   int ret;
 255
 256   orig_size = xd3_sizeof_output (*head);
 257
 258   if (orig_size < SECONDARY_MIN_INPUT) { return 0; }
 259
 260   if ((ret = xd3_get_secondary (stream, sec_streamp, 1)) != 0)
 261     {
 262       return ret;
 263     }
 264
 265   tmp_head = xd3_alloc_output (stream, NULL);
 266
 267   /* Encode the size, encode the data.  Encoding the size makes it
 268    * simpler, but is a little gross.  Should not need the entire
 269    * section in contiguous memory, but it is much easier this way. */
 270   if ((ret = xd3_emit_size (stream, & tmp_head, orig_size)) ||
 271       (ret = stream->sec_type->encode (stream, *sec_streamp, *head,
 272                                        tmp_head, cfg)))
 273     {
 274       goto getout;
 275     }
 276
 277   /* If the secondary compressor determines it's no good, it returns
 278    * XD3_NOSECOND. */
 279
 280   /* Setup tmp_tail, comp_size */
 281   tmp_tail  = tmp_head;
 282   comp_size = tmp_head->next;
 283
 284   while (tmp_tail->next_page != NULL)
 285     {
 286       tmp_tail = tmp_tail->next_page;
 287       comp_size += tmp_tail->next;
 288     }
 289
 290   XD3_ASSERT (comp_size == xd3_sizeof_output (tmp_head));
 291   XD3_ASSERT (tmp_tail != NULL);
 292
 293   if (comp_size < (orig_size - SECONDARY_MIN_SAVINGS) || cfg->inefficient)
 294     {
 295       IF_DEBUG1(DP(RINT "secondary saved %u bytes: %u -> %u (%0.2f%%)\n",
 296                    orig_size - comp_size, orig_size, comp_size,
 297                100.0 * (double) comp_size / (double) orig_size));
 298
 299       xd3_free_output (stream, *head);
 300
 301       *head = tmp_head;
 302       *tail = tmp_tail;
 303       *did_it = 1;
 304     }
 305   else
 306     {
 307     getout:
 308       if (ret == XD3_NOSECOND) { ret = 0; }
 309       xd3_free_output (stream, tmp_head);
 310     }
 311
 312   return ret;
 313 }
 314 #endif /* XD3_ENCODER */
 315 #endif /* _XDELTA3_SECOND_H_ */