xdelta3-merge.h

   1 /* xdelta 3 - delta compression tools and library
   2  * Copyright (C) 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 #ifndef _XDELTA3_MERGE_H_
  20 #define _XDELTA3_MERGE_H_
  21
  22 int xd3_merge_inputs (xd3_stream *stream,
  23                       xd3_whole_state *source,
  24                       xd3_whole_state *input);
  25
  26 static int
  27 xd3_whole_state_init (xd3_stream *stream)
  28 {
  29   XD3_ASSERT (stream->whole_target.adds == NULL);
  30   XD3_ASSERT (stream->whole_target.inst == NULL);
  31   XD3_ASSERT (stream->whole_target.wininfo == NULL);
  32   XD3_ASSERT (stream->whole_target.length == 0);
  33
  34   stream->whole_target.adds_alloc = XD3_ALLOCSIZE;
  35   stream->whole_target.inst_alloc = XD3_ALLOCSIZE;
  36   stream->whole_target.wininfo_alloc = XD3_ALLOCSIZE;
  37
  38   if ((stream->whole_target.adds = (uint8_t*)
  39        xd3_alloc (stream, stream->whole_target.adds_alloc, 1)) == NULL ||
  40       (stream->whole_target.inst = (xd3_winst*)
  41        xd3_alloc (stream, stream->whole_target.inst_alloc, 1)) == NULL ||
  42       (stream->whole_target.wininfo = (xd3_wininfo*)
  43        xd3_alloc (stream, stream->whole_target.wininfo_alloc, 1)) == NULL)
  44     {
  45       return ENOMEM;
  46     }
  47   return 0;
  48 }
  49
  50 static void
  51 xd3_swap_whole_state (xd3_whole_state *a,
  52                       xd3_whole_state *b)
  53 {
  54   xd3_whole_state tmp;
  55   XD3_ASSERT (a->inst != NULL && a->adds != NULL);
  56   XD3_ASSERT (b->inst != NULL && b->adds != NULL);
  57   XD3_ASSERT (b->wininfo != NULL && b->wininfo != NULL);
  58   memcpy (&tmp, a, sizeof (xd3_whole_state));
  59   memcpy (a, b, sizeof (xd3_whole_state));
  60   memcpy (b, &tmp, sizeof (xd3_whole_state));
  61 }
  62
  63 static int
  64 xd3_realloc_buffer (xd3_stream *stream,
  65                     usize_t current_units,
  66                     usize_t unit_size,
  67                     usize_t new_units,
  68                     usize_t *alloc_size,
  69                     void **alloc_ptr)
  70 {
  71   usize_t needed;
  72   usize_t new_alloc;
  73   usize_t cur_size;
  74   uint8_t *new_buf;
  75
  76   needed = (current_units + new_units) * unit_size;
  77
  78   if (needed <= *alloc_size)
  79     {
  80       return 0;
  81     }
  82
  83   cur_size = current_units * unit_size;
  84   new_alloc = xd3_round_blksize (needed * 2, XD3_ALLOCSIZE);
  85
  86   if ((new_buf = (uint8_t*) xd3_alloc (stream, new_alloc, 1)) == NULL)
  87     {
  88       return ENOMEM;
  89     }
  90
  91   if (cur_size != 0)
  92     {
  93       memcpy (new_buf, *alloc_ptr, cur_size);
  94     }
  95
  96   if (*alloc_ptr != NULL)
  97     {
  98       xd3_free (stream, *alloc_ptr);
  99     }
 100
 101   *alloc_size = new_alloc;
 102   *alloc_ptr = new_buf;
 103
 104   return 0;
 105 }
 106
 107 /* allocate one new output instruction */
 108 static int
 109 xd3_whole_alloc_winst (xd3_stream *stream,
 110                        xd3_winst **winstp)
 111 {
 112   int ret;
 113
 114   if ((ret = xd3_realloc_buffer (stream,
 115                                  stream->whole_target.instlen,
 116                                  sizeof (xd3_winst),
 117                                  1,
 118                                  & stream->whole_target.inst_alloc,
 119                                  (void**) & stream->whole_target.inst)))
 120     {
 121       return ret;
 122     }
 123
 124   *winstp = &stream->whole_target.inst[stream->whole_target.instlen++];
 125
 126   return 0;
 127 }
 128
 129 static int
 130 xd3_whole_alloc_adds (xd3_stream *stream,
 131                       usize_t count)
 132 {
 133   return xd3_realloc_buffer (stream,
 134                              stream->whole_target.addslen,
 135                              1,
 136                              count,
 137                              & stream->whole_target.adds_alloc,
 138                              (void**) & stream->whole_target.adds);
 139 }
 140
 141 static int
 142 xd3_whole_alloc_wininfo (xd3_stream *stream,
 143                          xd3_wininfo **wininfop)
 144 {
 145   int ret;
 146
 147   if ((ret = xd3_realloc_buffer (stream,
 148                                  stream->whole_target.wininfolen,
 149                                  sizeof (xd3_wininfo),
 150                                  1,
 151                                  & stream->whole_target.wininfo_alloc,
 152                                  (void**) & stream->whole_target.wininfo)))
 153     {
 154       return ret;
 155     }
 156
 157   *wininfop = &stream->whole_target.wininfo[stream->whole_target.wininfolen++];
 158
 159   return 0;
 160 }
 161
 162 static int
 163 xd3_whole_append_inst (xd3_stream *stream,
 164                        xd3_hinst *inst)
 165 {
 166   int ret;
 167   xd3_winst *winst;
 168
 169   if ((ret = xd3_whole_alloc_winst (stream, &winst)))
 170     {
 171       return ret;
 172     }
 173
 174   winst->type = inst->type;
 175   winst->mode = 0;
 176   winst->size = inst->size;
 177   winst->position = stream->whole_target.length;
 178   stream->whole_target.length += inst->size;
 179
 180   if (((inst->type == XD3_ADD) || (inst->type == XD3_RUN)) &&
 181       (ret = xd3_whole_alloc_adds (stream,
 182                                    (inst->type == XD3_RUN ? 1 : inst->size))))
 183     {
 184       return ret;
 185     }
 186
 187   switch (inst->type)
 188     {
 189     case XD3_RUN:
 190       winst->addr = stream->whole_target.addslen;
 191       stream->whole_target.adds[stream->whole_target.addslen++] =
 192         *stream->data_sect.buf++;
 193       break;
 194
 195     case XD3_ADD:
 196       winst->addr = stream->whole_target.addslen;
 197       memcpy (stream->whole_target.adds + stream->whole_target.addslen,
 198               stream->data_sect.buf,
 199               inst->size);
 200       stream->data_sect.buf += inst->size;
 201       stream->whole_target.addslen += inst->size;
 202       break;
 203
 204     default:
 205       if (inst->addr < stream->dec_cpylen)
 206         {
 207           winst->mode = SRCORTGT (stream->dec_win_ind);
 208           winst->addr = stream->dec_cpyoff + inst->addr;
 209         }
 210       else
 211         {
 212           winst->addr = (stream->dec_winstart +
 213                          inst->addr -
 214                          stream->dec_cpylen);
 215         }
 216       break;
 217     }
 218
 219   return 0;
 220 }
 221
 222 int
 223 xd3_whole_append_window (xd3_stream *stream)
 224 {
 225   int ret;
 226   xd3_wininfo *wininfo;
 227
 228   if ((ret = xd3_whole_alloc_wininfo (stream, &wininfo))) { return ret; }
 229
 230   wininfo->length = stream->dec_tgtlen;
 231   wininfo->offset = stream->dec_winstart;
 232   wininfo->adler32 = stream->dec_adler32;
 233
 234   while (stream->inst_sect.buf < stream->inst_sect.buf_max)
 235     {
 236       if ((ret = xd3_decode_instruction (stream)))
 237         {
 238           return ret;
 239         }
 240
 241       if ((stream->dec_current1.type != XD3_NOOP) &&
 242           (ret = xd3_whole_append_inst (stream,
 243                                         & stream->dec_current1)))
 244         {
 245           return ret;
 246         }
 247
 248       if ((stream->dec_current2.type != XD3_NOOP) &&
 249           (ret = xd3_whole_append_inst (stream,
 250                                         & stream->dec_current2)))
 251         {
 252           return ret;
 253         }
 254     }
 255
 256   return 0;
 257 }
 258
 259 /* xd3_merge_input_output applies *source to *stream, returns the
 260  * result in stream. */
 261 int xd3_merge_input_output (xd3_stream *stream,
 262                             xd3_whole_state *source)
 263 {
 264   int ret;
 265   xd3_stream tmp_stream;
 266   memset (& tmp_stream, 0, sizeof (tmp_stream));
 267   if ((ret = xd3_config_stream (& tmp_stream, NULL)) ||
 268       (ret = xd3_whole_state_init (& tmp_stream)) ||
 269       (ret = xd3_merge_inputs (& tmp_stream,
 270                                source,
 271                                & stream->whole_target)))
 272     {
 273       XPR(NT XD3_LIB_ERRMSG (&tmp_stream, ret));
 274       return ret;
 275     }
 276
 277   /* the output is in tmp_stream.whole_state, swap into input */
 278   xd3_swap_whole_state (& stream->whole_target,
 279                         & tmp_stream.whole_target);
 280   /* total allocation counts are preserved */
 281   xd3_free_stream (& tmp_stream);
 282   return 0;
 283 }
 284
 285 static int
 286 xd3_merge_run (xd3_stream *stream,
 287                xd3_whole_state *target,
 288                xd3_winst *iinst)
 289 {
 290   int ret;
 291   xd3_winst *oinst;
 292
 293   if ((ret = xd3_whole_alloc_winst (stream, &oinst)) ||
 294       (ret = xd3_whole_alloc_adds (stream, 1)))
 295     {
 296       return ret;
 297     }
 298
 299   oinst->type = iinst->type;
 300   oinst->mode = iinst->mode;
 301   oinst->size = iinst->size;
 302   oinst->addr = stream->whole_target.addslen;
 303
 304   XD3_ASSERT (stream->whole_target.length == iinst->position);
 305   oinst->position = stream->whole_target.length;
 306   stream->whole_target.length += iinst->size;
 307
 308   stream->whole_target.adds[stream->whole_target.addslen++] =
 309     target->adds[iinst->addr];
 310
 311   return 0;
 312 }
 313
 314 static int
 315 xd3_merge_add (xd3_stream *stream,
 316                xd3_whole_state *target,
 317                xd3_winst *iinst)
 318 {
 319   int ret;
 320   xd3_winst *oinst;
 321
 322   if ((ret = xd3_whole_alloc_winst (stream, &oinst)) ||
 323       (ret = xd3_whole_alloc_adds (stream, iinst->size)))
 324     {
 325       return ret;
 326     }
 327
 328   oinst->type = iinst->type;
 329   oinst->mode = iinst->mode;
 330   oinst->size = iinst->size;
 331   oinst->addr = stream->whole_target.addslen;
 332
 333   XD3_ASSERT (stream->whole_target.length == iinst->position);
 334   oinst->position = stream->whole_target.length;
 335   stream->whole_target.length += iinst->size;
 336
 337   memcpy(stream->whole_target.adds + stream->whole_target.addslen,
 338          target->adds + iinst->addr,
 339          iinst->size);
 340
 341   stream->whole_target.addslen += iinst->size;
 342
 343   return 0;
 344 }
 345
 346 static int
 347 xd3_merge_target_copy (xd3_stream *stream,
 348                        xd3_winst *iinst)
 349 {
 350   int ret;
 351   xd3_winst *oinst;
 352
 353   if ((ret = xd3_whole_alloc_winst (stream, &oinst)))
 354     {
 355       return ret;
 356     }
 357
 358   XD3_ASSERT (stream->whole_target.length == iinst->position);
 359
 360   memcpy (oinst, iinst, sizeof (*oinst));
 361   return 0;
 362 }
 363
 364 static int
 365 xd3_merge_find_position (xd3_stream *stream,
 366                          xd3_whole_state *source,
 367                          xoff_t address,
 368                          usize_t *inst_num)
 369 {
 370   usize_t low;
 371   usize_t high;
 372
 373   if (address >= source->length)
 374     {
 375       stream->msg = "Invalid copy offset in merge";
 376       return XD3_INVALID_INPUT;
 377     }
 378
 379   low = 0;
 380   high = source->instlen;
 381
 382   while (low != high)
 383     {
 384       xoff_t mid_lpos;
 385       xoff_t mid_hpos;
 386       usize_t mid = low + (high - low) / 2;
 387       mid_lpos = source->inst[mid].position;
 388
 389       if (address < mid_lpos)
 390         {
 391           high = mid;
 392           continue;
 393         }
 394
 395       mid_hpos = mid_lpos + source->inst[mid].size;
 396
 397       if (address >= mid_hpos)
 398         {
 399           low = mid + 1;
 400           continue;
 401         }
 402
 403       *inst_num = mid;
 404       return 0;
 405     }
 406
 407   stream->msg = "Internal error in merge";
 408   return XD3_INTERNAL;
 409 }
 410
 411 static int
 412 xd3_merge_source_copy (xd3_stream *stream,
 413                        xd3_whole_state *source,
 414                        const xd3_winst *iinst_orig)
 415 {
 416   int ret;
 417   xd3_winst iinst;
 418   usize_t sinst_num;
 419
 420   memcpy (& iinst, iinst_orig, sizeof (iinst));
 421
 422   XD3_ASSERT (iinst.mode == VCD_SOURCE);
 423
 424   if ((ret = xd3_merge_find_position (stream, source,
 425                                       iinst.addr, &sinst_num)))
 426     {
 427       return ret;
 428     }
 429
 430   while (iinst.size > 0)
 431     {
 432       xd3_winst *sinst;
 433       xd3_winst *minst;
 434       usize_t sinst_offset;
 435       usize_t sinst_left;
 436       usize_t this_take;
 437
 438       XD3_ASSERT (sinst_num < source->instlen);
 439
 440       sinst = &source->inst[sinst_num];
 441
 442       XD3_ASSERT (iinst.addr >= sinst->position);
 443
 444       sinst_offset = (usize_t)(iinst.addr - sinst->position);
 445
 446       XD3_ASSERT (sinst->size > sinst_offset);
 447
 448       sinst_left = sinst->size - sinst_offset;
 449       this_take = min (iinst.size, sinst_left);
 450
 451       XD3_ASSERT (this_take > 0);
 452
 453       if ((ret = xd3_whole_alloc_winst (stream, &minst)))
 454         {
 455           return ret;
 456         }
 457
 458       minst->size = this_take;
 459       minst->type = sinst->type;
 460       minst->position = iinst.position;
 461       minst->mode = 0;
 462
 463       switch (sinst->type)
 464         {
 465         case XD3_RUN:
 466           if ((ret = xd3_whole_alloc_adds (stream, 1)))
 467             {
 468               return ret;
 469             }
 470
 471           minst->addr = stream->whole_target.addslen;
 472           stream->whole_target.adds[stream->whole_target.addslen++] =
 473             source->adds[sinst->addr];
 474           break;
 475         case XD3_ADD:
 476           if ((ret = xd3_whole_alloc_adds (stream, this_take)))
 477             {
 478               return ret;
 479             }
 480
 481           minst->addr = stream->whole_target.addslen;
 482           memcpy(stream->whole_target.adds + stream->whole_target.addslen,
 483                  source->adds + sinst->addr + sinst_offset,
 484                  this_take);
 485           stream->whole_target.addslen += this_take;
 486           break;
 487         default:
 488           if (sinst->mode != 0)
 489             {
 490               minst->mode = sinst->mode;
 491               minst->addr = sinst->addr + sinst_offset;
 492             }
 493           else
 494             {
 495               // TODO: this is slow because of the recursion, which
 496               // could reach a depth equal to the number of target
 497               // copies, and this is compression-inefficient because
 498               // it can produce duplicate adds.
 499               xd3_winst tinst;
 500               tinst.type = XD3_CPY;
 501               tinst.mode = iinst.mode;
 502               tinst.addr = sinst->addr + sinst_offset;
 503               tinst.size = this_take;
 504               tinst.position = iinst.position;
 505
 506               // The instruction allocated in this frame will not be used.
 507               stream->whole_target.instlen -= 1;
 508
 509               if ((ret = xd3_merge_source_copy (stream, source, &tinst)))
 510                 {
 511                   return ret;
 512                 }
 513             }
 514           break;
 515         }
 516
 517       iinst.position += this_take;
 518       iinst.addr += this_take;
 519       iinst.size -= this_take;
 520       sinst_num += 1;
 521     }
 522
 523   return 0;
 524 }
 525
 526 /* xd3_merge_inputs() applies *input to *source, returns its result in
 527  * stream. */
 528 int xd3_merge_inputs (xd3_stream *stream,
 529                       xd3_whole_state *source,
 530                       xd3_whole_state *input)
 531 {
 532   int ret = 0;
 533   usize_t i;
 534   size_t input_i;
 535
 536   for (i = 0; i < input->wininfolen; ++i) {
 537     xd3_wininfo *copyinfo;
 538
 539     if ((ret = xd3_whole_alloc_wininfo (stream, &copyinfo))) { return ret; }
 540
 541     *copyinfo = input->wininfo[i];
 542   }
 543
 544   /* iterate over each instruction. */
 545   for (input_i = 0; ret == 0 && input_i < input->instlen; ++input_i)
 546     {
 547       xd3_winst *iinst = &input->inst[input_i];
 548
 549       switch (iinst->type)
 550         {
 551         case XD3_RUN:
 552           ret = xd3_merge_run (stream, input, iinst);
 553           break;
 554         case XD3_ADD:
 555           ret = xd3_merge_add (stream, input, iinst);
 556           break;
 557         default:
 558           /* TODO: VCD_TARGET support is completely untested all
 559            * throughout. */
 560           if (iinst->mode == 0 || iinst->mode == VCD_TARGET)
 561             {
 562               ret = xd3_merge_target_copy (stream, iinst);
 563             }
 564           else
 565             {
 566               ret = xd3_merge_source_copy (stream, source, iinst);
 567             }
 568
 569           /* The whole_target.length is not updated in the xd3_merge*copy
 570            * routine because of recursion in xd3_merge_source_copy. */
 571           stream->whole_target.length += iinst->size;
 572           break;
 573         }
 574     }
 575
 576   return ret;
 577 }
 578
 579 #endif