contrib/subversion/subversion/libsvn_delta/text_delta.c

   1 /*
   2  * text-delta.c -- Internal text delta representation
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24
  25 #include <assert.h>
  26 #include <string.h>
  27
  28 #include <apr_general.h>        /* for APR_INLINE */
  29 #include <apr_md5.h>            /* for, um...MD5 stuff */
  30
  31 #include "svn_delta.h"
  32 #include "svn_io.h"
  33 #include "svn_pools.h"
  34 #include "svn_checksum.h"
  35
  36 #include "delta.h"
  37
  38 \f
  39 /* Text delta stream descriptor. */
  40
  41 struct svn_txdelta_stream_t {
  42   /* Copied from parameters to svn_txdelta_stream_create. */
  43   void *baton;
  44   svn_txdelta_next_window_fn_t next_window;
  45   svn_txdelta_md5_digest_fn_t md5_digest;
  46 };
  47
  48 /* Delta stream baton. */
  49 struct txdelta_baton {
  50   /* These are copied from parameters passed to svn_txdelta. */
  51   svn_stream_t *source;
  52   svn_stream_t *target;
  53
  54   /* Private data */
  55   svn_boolean_t more_source;    /* FALSE if source stream hit EOF. */
  56   svn_boolean_t more;           /* TRUE if there are more data in the pool. */
  57   svn_filesize_t pos;           /* Offset of next read in source file. */
  58   char *buf;                    /* Buffer for input data. */
  59
  60   svn_checksum_ctx_t *context;  /* If not NULL, the context for computing
  61                                    the checksum. */
  62   svn_checksum_t *checksum;     /* If non-NULL, the checksum of TARGET. */
  63
  64   apr_pool_t *result_pool;      /* For results (e.g. checksum) */
  65 };
  66
  67
  68 /* Target-push stream descriptor. */
  69
  70 struct tpush_baton {
  71   /* These are copied from parameters passed to svn_txdelta_target_push. */
  72   svn_stream_t *source;
  73   svn_txdelta_window_handler_t wh;
  74   void *whb;
  75   apr_pool_t *pool;
  76
  77   /* Private data */
  78   char *buf;
  79   svn_filesize_t source_offset;
  80   apr_size_t source_len;
  81   svn_boolean_t source_done;
  82   apr_size_t target_len;
  83 };
  84
  85
  86 /* Text delta applicator.  */
  87
  88 struct apply_baton {
  89   /* These are copied from parameters passed to svn_txdelta_apply.  */
  90   svn_stream_t *source;
  91   svn_stream_t *target;
  92
  93   /* Private data.  Between calls, SBUF contains the data from the
  94    * last window's source view, as specified by SBUF_OFFSET and
  95    * SBUF_LEN.  The contents of TBUF are not interesting between
  96    * calls.  */
  97   apr_pool_t *pool;             /* Pool to allocate data from */
  98   char *sbuf;                   /* Source buffer */
  99   apr_size_t sbuf_size;         /* Allocated source buffer space */
 100   svn_filesize_t sbuf_offset;   /* Offset of SBUF data in source stream */
 101   apr_size_t sbuf_len;          /* Length of SBUF data */
 102   char *tbuf;                   /* Target buffer */
 103   apr_size_t tbuf_size;         /* Allocated target buffer space */
 104
 105   apr_md5_ctx_t md5_context;    /* Leads to result_digest below. */
 106   unsigned char *result_digest; /* MD5 digest of resultant fulltext;
 107                                    must point to at least APR_MD5_DIGESTSIZE
 108                                    bytes of storage. */
 109
 110   const char *error_info;       /* Optional extra info for error returns. */
 111 };
 112
 113
 114 \f
 115 svn_txdelta_window_t *
 116 svn_txdelta__make_window(const svn_txdelta__ops_baton_t *build_baton,
 117                          apr_pool_t *pool)
 118 {
 119   svn_txdelta_window_t *window;
 120   svn_string_t *new_data = apr_palloc(pool, sizeof(*new_data));
 121
 122   window = apr_palloc(pool, sizeof(*window));
 123   window->sview_offset = 0;
 124   window->sview_len = 0;
 125   window->tview_len = 0;
 126
 127   window->num_ops = build_baton->num_ops;
 128   window->src_ops = build_baton->src_ops;
 129   window->ops = build_baton->ops;
 130
 131   /* just copy the fields over, rather than alloc/copying into a whole new
 132      svn_string_t structure. */
 133   /* ### would be much nicer if window->new_data were not a ptr... */
 134   new_data->data = build_baton->new_data->data;
 135   new_data->len = build_baton->new_data->len;
 136   window->new_data = new_data;
 137
 138   return window;
 139 }
 140
 141
 142 /* Compute and return a delta window using the xdelta algorithm on
 143    DATA, which contains SOURCE_LEN bytes of source data and TARGET_LEN
 144    bytes of target data.  SOURCE_OFFSET gives the offset of the source
 145    data, and is simply copied into the window's sview_offset field. */
 146 static svn_txdelta_window_t *
 147 compute_window(const char *data, apr_size_t source_len, apr_size_t target_len,
 148                svn_filesize_t source_offset, apr_pool_t *pool)
 149 {
 150   svn_txdelta__ops_baton_t build_baton = { 0 };
 151   svn_txdelta_window_t *window;
 152
 153   /* Compute the delta operations. */
 154   build_baton.new_data = svn_stringbuf_create_empty(pool);
 155
 156   if (source_len == 0)
 157     svn_txdelta__insert_op(&build_baton, svn_txdelta_new, 0, target_len, data,
 158                            pool);
 159   else
 160     svn_txdelta__xdelta(&build_baton, data, source_len, target_len, pool);
 161
 162   /* Create and return the delta window. */
 163   window = svn_txdelta__make_window(&build_baton, pool);
 164   window->sview_offset = source_offset;
 165   window->sview_len = source_len;
 166   window->tview_len = target_len;
 167   return window;
 168 }
 169
 170
 171 \f
 172 svn_txdelta_window_t *
 173 svn_txdelta_window_dup(const svn_txdelta_window_t *window,
 174                        apr_pool_t *pool)
 175 {
 176   svn_txdelta__ops_baton_t build_baton = { 0 };
 177   svn_txdelta_window_t *new_window;
 178   const apr_size_t ops_size = (window->num_ops * sizeof(*build_baton.ops));
 179
 180   build_baton.num_ops = window->num_ops;
 181   build_baton.src_ops = window->src_ops;
 182   build_baton.ops_size = window->num_ops;
 183   build_baton.ops = apr_palloc(pool, ops_size);
 184   memcpy(build_baton.ops, window->ops, ops_size);
 185   build_baton.new_data =
 186     svn_stringbuf_create_from_string(window->new_data, pool);
 187
 188   new_window = svn_txdelta__make_window(&build_baton, pool);
 189   new_window->sview_offset = window->sview_offset;
 190   new_window->sview_len = window->sview_len;
 191   new_window->tview_len = window->tview_len;
 192   return new_window;
 193 }
 194
 195 /* This is a private interlibrary compatibility wrapper. */
 196 svn_txdelta_window_t *
 197 svn_txdelta__copy_window(const svn_txdelta_window_t *window,
 198                          apr_pool_t *pool);
 199 svn_txdelta_window_t *
 200 svn_txdelta__copy_window(const svn_txdelta_window_t *window,
 201                          apr_pool_t *pool)
 202 {
 203   return svn_txdelta_window_dup(window, pool);
 204 }
 205
 206 \f
 207 /* Insert a delta op into a delta window. */
 208
 209 void
 210 svn_txdelta__insert_op(svn_txdelta__ops_baton_t *build_baton,
 211                        enum svn_delta_action opcode,
 212                        apr_size_t offset,
 213                        apr_size_t length,
 214                        const char *new_data,
 215                        apr_pool_t *pool)
 216 {
 217   svn_txdelta_op_t *op;
 218
 219   /* Check if this op can be merged with the previous op. The delta
 220      combiner sometimes generates such ops, and this is the obvious
 221      place to make the check. */
 222   if (build_baton->num_ops > 0)
 223     {
 224       op = &build_baton->ops[build_baton->num_ops - 1];
 225       if (op->action_code == opcode
 226           && (opcode == svn_txdelta_new
 227               || op->offset + op->length == offset))
 228         {
 229           op->length += length;
 230           if (opcode == svn_txdelta_new)
 231             svn_stringbuf_appendbytes(build_baton->new_data,
 232                                       new_data, length);
 233           return;
 234         }
 235     }
 236
 237   /* Create space for the new op. */
 238   if (build_baton->num_ops == build_baton->ops_size)
 239     {
 240       svn_txdelta_op_t *const old_ops = build_baton->ops;
 241       int const new_ops_size = (build_baton->ops_size == 0
 242                                 ? 16 : 2 * build_baton->ops_size);
 243       build_baton->ops =
 244         apr_palloc(pool, new_ops_size * sizeof(*build_baton->ops));
 245
 246       /* Copy any existing ops into the new array */
 247       if (old_ops)
 248         memcpy(build_baton->ops, old_ops,
 249                build_baton->ops_size * sizeof(*build_baton->ops));
 250       build_baton->ops_size = new_ops_size;
 251     }
 252
 253   /* Insert the op. svn_delta_source and svn_delta_target are
 254      just inserted. For svn_delta_new, the new data must be
 255      copied into the window. */
 256   op = &build_baton->ops[build_baton->num_ops];
 257   switch (opcode)
 258     {
 259     case svn_txdelta_source:
 260       ++build_baton->src_ops;
 261       /*** FALLTHRU ***/
 262     case svn_txdelta_target:
 263       op->action_code = opcode;
 264       op->offset = offset;
 265       op->length = length;
 266       break;
 267     case svn_txdelta_new:
 268       op->action_code = opcode;
 269       op->offset = build_baton->new_data->len;
 270       op->length = length;
 271       svn_stringbuf_appendbytes(build_baton->new_data, new_data, length);
 272       break;
 273     default:
 274       assert(!"unknown delta op.");
 275     }
 276
 277   ++build_baton->num_ops;
 278 }
 279
 280 apr_size_t
 281 svn_txdelta__remove_copy(svn_txdelta__ops_baton_t *build_baton,
 282                          apr_size_t max_len)
 283 {
 284   svn_txdelta_op_t *op;
 285   apr_size_t len = 0;
 286
 287   /* remove ops back to front */
 288   while (build_baton->num_ops > 0)
 289     {
 290       op = &build_baton->ops[build_baton->num_ops-1];
 291
 292       /*  we can't modify svn_txdelta_target ops -> stop there */
 293       if (op->action_code == svn_txdelta_target)
 294         break;
 295
 296       /*  handle the case that we cannot remove the op entirely */
 297       if (op->length + len > max_len)
 298         {
 299           /* truncate only insertions. Copies don't benefit
 300              from being truncated. */
 301           if (op->action_code == svn_txdelta_new)
 302             {
 303                build_baton->new_data->len -= max_len - len;
 304                op->length -= max_len - len;
 305                len = max_len;
 306             }
 307
 308           break;
 309         }
 310
 311       /* drop the op entirely */
 312       if (op->action_code == svn_txdelta_new)
 313         build_baton->new_data->len -= op->length;
 314
 315       len += op->length;
 316       --build_baton->num_ops;
 317     }
 318
 319   return len;
 320 }
 321
 322
 323 \f
 324 /* Generic delta stream functions. */
 325
 326 svn_txdelta_stream_t *
 327 svn_txdelta_stream_create(void *baton,
 328                           svn_txdelta_next_window_fn_t next_window,
 329                           svn_txdelta_md5_digest_fn_t md5_digest,
 330                           apr_pool_t *pool)
 331 {
 332   svn_txdelta_stream_t *stream = apr_palloc(pool, sizeof(*stream));
 333
 334   stream->baton = baton;
 335   stream->next_window = next_window;
 336   stream->md5_digest = md5_digest;
 337
 338   return stream;
 339 }
 340
 341 svn_error_t *
 342 svn_txdelta_next_window(svn_txdelta_window_t **window,
 343                         svn_txdelta_stream_t *stream,
 344                         apr_pool_t *pool)
 345 {
 346   return stream->next_window(window, stream->baton, pool);
 347 }
 348
 349 const unsigned char *
 350 svn_txdelta_md5_digest(svn_txdelta_stream_t *stream)
 351 {
 352   return stream->md5_digest(stream->baton);
 353 }
 354
 355
 356 \f
 357 static svn_error_t *
 358 txdelta_next_window(svn_txdelta_window_t **window,
 359                     void *baton,
 360                     apr_pool_t *pool)
 361 {
 362   struct txdelta_baton *b = baton;
 363   apr_size_t source_len = SVN_DELTA_WINDOW_SIZE;
 364   apr_size_t target_len = SVN_DELTA_WINDOW_SIZE;
 365
 366   /* Read the source stream. */
 367   if (b->more_source)
 368     {
 369       SVN_ERR(svn_stream_read_full(b->source, b->buf, &source_len));
 370       b->more_source = (source_len == SVN_DELTA_WINDOW_SIZE);
 371     }
 372   else
 373     source_len = 0;
 374
 375   /* Read the target stream. */
 376   SVN_ERR(svn_stream_read_full(b->target, b->buf + source_len, &target_len));
 377   b->pos += source_len;
 378
 379   if (target_len == 0)
 380     {
 381       /* No target data?  We're done; return the final window. */
 382       if (b->context != NULL)
 383         SVN_ERR(svn_checksum_final(&b->checksum, b->context, b->result_pool));
 384
 385       *window = NULL;
 386       b->more = FALSE;
 387       return SVN_NO_ERROR;
 388     }
 389   else if (b->context != NULL)
 390     SVN_ERR(svn_checksum_update(b->context, b->buf + source_len, target_len));
 391
 392   *window = compute_window(b->buf, source_len, target_len,
 393                            b->pos - source_len, pool);
 394
 395   /* That's it. */
 396   return SVN_NO_ERROR;
 397 }
 398
 399
 400 static const unsigned char *
 401 txdelta_md5_digest(void *baton)
 402 {
 403   struct txdelta_baton *b = baton;
 404   /* If there are more windows for this stream, the digest has not yet
 405      been calculated.  */
 406   if (b->more)
 407     return NULL;
 408
 409   /* If checksumming has not been activated, there will be no digest. */
 410   if (b->context == NULL)
 411     return NULL;
 412
 413   /* The checksum should be there. */
 414   return b->checksum->digest;
 415 }
 416
 417
 418 svn_error_t *
 419 svn_txdelta_run(svn_stream_t *source,
 420                 svn_stream_t *target,
 421                 svn_txdelta_window_handler_t handler,
 422                 void *handler_baton,
 423                 svn_checksum_kind_t checksum_kind,
 424                 svn_checksum_t **checksum,
 425                 svn_cancel_func_t cancel_func,
 426                 void *cancel_baton,
 427                 apr_pool_t *result_pool,
 428                 apr_pool_t *scratch_pool)
 429 {
 430   apr_pool_t *iterpool = svn_pool_create(scratch_pool);
 431   struct txdelta_baton tb = { 0 };
 432   svn_txdelta_window_t *window;
 433
 434   tb.source = source;
 435   tb.target = target;
 436   tb.more_source = TRUE;
 437   tb.more = TRUE;
 438   tb.pos = 0;
 439   tb.buf = apr_palloc(scratch_pool, 2 * SVN_DELTA_WINDOW_SIZE);
 440   tb.result_pool = result_pool;
 441
 442   if (checksum != NULL)
 443     tb.context = svn_checksum_ctx_create(checksum_kind, scratch_pool);
 444
 445   do
 446     {
 447       /* free the window (if any) */
 448       svn_pool_clear(iterpool);
 449
 450       /* read in a single delta window */
 451       SVN_ERR(txdelta_next_window(&window, &tb, iterpool));
 452
 453       /* shove it at the handler */
 454       SVN_ERR((*handler)(window, handler_baton));
 455
 456       if (cancel_func)
 457         SVN_ERR(cancel_func(cancel_baton));
 458     }
 459   while (window != NULL);
 460
 461   svn_pool_destroy(iterpool);
 462
 463   if (checksum != NULL)
 464     *checksum = tb.checksum;  /* should be there! */
 465
 466   return SVN_NO_ERROR;
 467 }
 468
 469
 470 void
 471 svn_txdelta2(svn_txdelta_stream_t **stream,
 472              svn_stream_t *source,
 473              svn_stream_t *target,
 474              svn_boolean_t calculate_checksum,
 475              apr_pool_t *pool)
 476 {
 477   struct txdelta_baton *b = apr_pcalloc(pool, sizeof(*b));
 478
 479   b->source = source;
 480   b->target = target;
 481   b->more_source = TRUE;
 482   b->more = TRUE;
 483   b->buf = apr_palloc(pool, 2 * SVN_DELTA_WINDOW_SIZE);
 484   b->context = calculate_checksum
 485              ? svn_checksum_ctx_create(svn_checksum_md5, pool)
 486              : NULL;
 487   b->result_pool = pool;
 488
 489   *stream = svn_txdelta_stream_create(b, txdelta_next_window,
 490                                       txdelta_md5_digest, pool);
 491 }
 492
 493 void
 494 svn_txdelta(svn_txdelta_stream_t **stream,
 495             svn_stream_t *source,
 496             svn_stream_t *target,
 497             apr_pool_t *pool)
 498 {
 499   svn_txdelta2(stream, source, target, TRUE, pool);
 500 }
 501
 502
 503 \f
 504 /* Functions for implementing a "target push" delta. */
 505
 506 /* This is the write handler for a target-push delta stream.  It reads
 507  * source data, buffers target data, and fires off delta windows when
 508  * the target data buffer is full. */
 509 static svn_error_t *
 510 tpush_write_handler(void *baton, const char *data, apr_size_t *len)
 511 {
 512   struct tpush_baton *tb = baton;
 513   apr_size_t chunk_len, data_len = *len;
 514   apr_pool_t *pool = svn_pool_create(tb->pool);
 515   svn_txdelta_window_t *window;
 516
 517   while (data_len > 0)
 518     {
 519       svn_pool_clear(pool);
 520
 521       /* Make sure we're all full up on source data, if possible. */
 522       if (tb->source_len == 0 && !tb->source_done)
 523         {
 524           tb->source_len = SVN_DELTA_WINDOW_SIZE;
 525           SVN_ERR(svn_stream_read_full(tb->source, tb->buf, &tb->source_len));
 526           if (tb->source_len < SVN_DELTA_WINDOW_SIZE)
 527             tb->source_done = TRUE;
 528         }
 529
 530       /* Copy in the target data, up to SVN_DELTA_WINDOW_SIZE. */
 531       chunk_len = SVN_DELTA_WINDOW_SIZE - tb->target_len;
 532       if (chunk_len > data_len)
 533         chunk_len = data_len;
 534       memcpy(tb->buf + tb->source_len + tb->target_len, data, chunk_len);
 535       data += chunk_len;
 536       data_len -= chunk_len;
 537       tb->target_len += chunk_len;
 538
 539       /* If we're full of target data, compute and fire off a window. */
 540       if (tb->target_len == SVN_DELTA_WINDOW_SIZE)
 541         {
 542           window = compute_window(tb->buf, tb->source_len, tb->target_len,
 543                                   tb->source_offset, pool);
 544           SVN_ERR(tb->wh(window, tb->whb));
 545           tb->source_offset += tb->source_len;
 546           tb->source_len = 0;
 547           tb->target_len = 0;
 548         }
 549     }
 550
 551   svn_pool_destroy(pool);
 552   return SVN_NO_ERROR;
 553 }
 554
 555
 556 /* This is the close handler for a target-push delta stream.  It sends
 557  * a final window if there is any buffered target data, and then sends
 558  * a NULL window signifying the end of the window stream. */
 559 static svn_error_t *
 560 tpush_close_handler(void *baton)
 561 {
 562   struct tpush_baton *tb = baton;
 563   svn_txdelta_window_t *window;
 564
 565   /* Send a final window if we have any residual target data. */
 566   if (tb->target_len > 0)
 567     {
 568       window = compute_window(tb->buf, tb->source_len, tb->target_len,
 569                               tb->source_offset, tb->pool);
 570       SVN_ERR(tb->wh(window, tb->whb));
 571     }
 572
 573   /* Send a final NULL window signifying the end. */
 574   return tb->wh(NULL, tb->whb);
 575 }
 576
 577
 578 svn_stream_t *
 579 svn_txdelta_target_push(svn_txdelta_window_handler_t handler,
 580                         void *handler_baton, svn_stream_t *source,
 581                         apr_pool_t *pool)
 582 {
 583   struct tpush_baton *tb;
 584   svn_stream_t *stream;
 585
 586   /* Initialize baton. */
 587   tb = apr_palloc(pool, sizeof(*tb));
 588   tb->source = source;
 589   tb->wh = handler;
 590   tb->whb = handler_baton;
 591   tb->pool = pool;
 592   tb->buf = apr_palloc(pool, 2 * SVN_DELTA_WINDOW_SIZE);
 593   tb->source_offset = 0;
 594   tb->source_len = 0;
 595   tb->source_done = FALSE;
 596   tb->target_len = 0;
 597
 598   /* Create and return writable stream. */
 599   stream = svn_stream_create(tb, pool);
 600   svn_stream_set_write(stream, tpush_write_handler);
 601   svn_stream_set_close(stream, tpush_close_handler);
 602   return stream;
 603 }
 604
 605
 606 \f
 607 /* Functions for applying deltas.  */
 608
 609 /* Ensure that BUF has enough space for VIEW_LEN bytes.  */
 610 static APR_INLINE svn_error_t *
 611 size_buffer(char **buf, apr_size_t *buf_size,
 612             apr_size_t view_len, apr_pool_t *pool)
 613 {
 614   if (view_len > *buf_size)
 615     {
 616       *buf_size *= 2;
 617       if (*buf_size < view_len)
 618         *buf_size = view_len;
 619       SVN_ERR_ASSERT(APR_ALIGN_DEFAULT(*buf_size) >= *buf_size);
 620       *buf = apr_palloc(pool, *buf_size);
 621     }
 622
 623   return SVN_NO_ERROR;
 624 }
 625
 626 /* Copy LEN bytes from SOURCE to TARGET.  Unlike memmove() or memcpy(),
 627  * create repeating patterns if the source and target ranges overlap.
 628  * Return a pointer to the first byte after the copied target range.  */
 629 static APR_INLINE char *
 630 patterning_copy(char *target, const char *source, apr_size_t len)
 631 {
 632   /* If the source and target overlap, repeat the overlapping pattern
 633      in the target buffer. Always copy from the source buffer because
 634      presumably it will be in the L1 cache after the first iteration
 635      and doing this should avoid pipeline stalls due to write/read
 636      dependencies. */
 637   const apr_size_t overlap = target - source;
 638   while (len > overlap)
 639     {
 640       memcpy(target, source, overlap);
 641       target += overlap;
 642       len -= overlap;
 643     }
 644
 645   /* Copy any remaining source pattern. */
 646   if (len)
 647     {
 648       memcpy(target, source, len);
 649       target += len;
 650     }
 651
 652   return target;
 653 }
 654
 655 void
 656 svn_txdelta_apply_instructions(svn_txdelta_window_t *window,
 657                                const char *sbuf, char *tbuf,
 658                                apr_size_t *tlen)
 659 {
 660   const svn_txdelta_op_t *op;
 661   apr_size_t tpos = 0;
 662
 663   /* Nothing to do for empty buffers.
 664    * This check allows for NULL TBUF in that case. */
 665   if (*tlen == 0)
 666     return;
 667
 668   for (op = window->ops; op < window->ops + window->num_ops; op++)
 669     {
 670       const apr_size_t buf_len = (op->length < *tlen - tpos
 671                                   ? op->length : *tlen - tpos);
 672
 673       /* Check some invariants common to all instructions.  */
 674       assert(tpos + op->length <= window->tview_len);
 675
 676       switch (op->action_code)
 677         {
 678         case svn_txdelta_source:
 679           /* Copy from source area.  */
 680           assert(sbuf);
 681           assert(op->offset + op->length <= window->sview_len);
 682           memcpy(tbuf + tpos, sbuf + op->offset, buf_len);
 683           break;
 684
 685         case svn_txdelta_target:
 686           /* Copy from target area.  We can't use memcpy() or the like
 687            * since we need a specific semantics for overlapping copies:
 688            * they must result in repeating patterns.
 689            * Note that most copies won't have overlapping source and
 690            * target ranges (they are just a result of self-compressed
 691            * data) but a small percentage will.  */
 692           assert(op->offset < tpos);
 693           patterning_copy(tbuf + tpos, tbuf + op->offset, buf_len);
 694           break;
 695
 696         case svn_txdelta_new:
 697           /* Copy from window new area.  */
 698           assert(op->offset + op->length <= window->new_data->len);
 699           memcpy(tbuf + tpos,
 700                  window->new_data->data + op->offset,
 701                  buf_len);
 702           break;
 703
 704         default:
 705           assert(!"Invalid delta instruction code");
 706         }
 707
 708       tpos += op->length;
 709       if (tpos >= *tlen)
 710         return;                 /* The buffer is full. */
 711     }
 712
 713   /* Check that we produced the right amount of data.  */
 714   assert(tpos == window->tview_len);
 715   *tlen = tpos;
 716 }
 717
 718 /* Apply WINDOW to the streams given by APPL.  */
 719 static svn_error_t *
 720 apply_window(svn_txdelta_window_t *window, void *baton)
 721 {
 722   struct apply_baton *ab = (struct apply_baton *) baton;
 723   apr_size_t len;
 724   svn_error_t *err;
 725
 726   if (window == NULL)
 727     {
 728       /* We're done; just clean up.  */
 729       if (ab->result_digest)
 730         apr_md5_final(ab->result_digest, &(ab->md5_context));
 731
 732       err = svn_stream_close(ab->target);
 733       svn_pool_destroy(ab->pool);
 734
 735       return err;
 736     }
 737
 738   /* Make sure the source view didn't slide backwards.  */
 739   SVN_ERR_ASSERT(window->sview_len == 0
 740                  || (window->sview_offset >= ab->sbuf_offset
 741                      && (window->sview_offset + window->sview_len
 742                          >= ab->sbuf_offset + ab->sbuf_len)));
 743
 744   /* Make sure there's enough room in the target buffer.  */
 745   SVN_ERR(size_buffer(&ab->tbuf, &ab->tbuf_size, window->tview_len, ab->pool));
 746
 747   /* Prepare the source buffer for reading from the input stream.  */
 748   if (window->sview_offset != ab->sbuf_offset
 749       || window->sview_len > ab->sbuf_size)
 750     {
 751       char *old_sbuf = ab->sbuf;
 752
 753       /* Make sure there's enough room.  */
 754       SVN_ERR(size_buffer(&ab->sbuf, &ab->sbuf_size, window->sview_len,
 755               ab->pool));
 756
 757       /* If the existing view overlaps with the new view, copy the
 758        * overlap to the beginning of the new buffer.  */
 759       if (  (apr_size_t)ab->sbuf_offset + ab->sbuf_len
 760           > (apr_size_t)window->sview_offset)
 761         {
 762           apr_size_t start =
 763             (apr_size_t)(window->sview_offset - ab->sbuf_offset);
 764           memmove(ab->sbuf, old_sbuf + start, ab->sbuf_len - start);
 765           ab->sbuf_len -= start;
 766         }
 767       else
 768         ab->sbuf_len = 0;
 769       ab->sbuf_offset = window->sview_offset;
 770     }
 771
 772   /* Read the remainder of the source view into the buffer.  */
 773   if (ab->sbuf_len < window->sview_len)
 774     {
 775       len = window->sview_len - ab->sbuf_len;
 776       err = svn_stream_read_full(ab->source, ab->sbuf + ab->sbuf_len, &len);
 777       if (err == SVN_NO_ERROR && len != window->sview_len - ab->sbuf_len)
 778         err = svn_error_create(SVN_ERR_INCOMPLETE_DATA, NULL,
 779                                "Delta source ended unexpectedly");
 780       if (err != SVN_NO_ERROR)
 781         return err;
 782       ab->sbuf_len = window->sview_len;
 783     }
 784
 785   /* Apply the window instructions to the source view to generate
 786      the target view.  */
 787   len = window->tview_len;
 788   svn_txdelta_apply_instructions(window, ab->sbuf, ab->tbuf, &len);
 789   SVN_ERR_ASSERT(len == window->tview_len);
 790
 791   /* Write out the output. */
 792
 793   /* Just update the context here. */
 794   if (ab->result_digest)
 795     apr_md5_update(&(ab->md5_context), ab->tbuf, len);
 796
 797   return svn_stream_write(ab->target, ab->tbuf, &len);
 798 }
 799
 800
 801 void
 802 svn_txdelta_apply(svn_stream_t *source,
 803                   svn_stream_t *target,
 804                   unsigned char *result_digest,
 805                   const char *error_info,
 806                   apr_pool_t *pool,
 807                   svn_txdelta_window_handler_t *handler,
 808                   void **handler_baton)
 809 {
 810   apr_pool_t *subpool = svn_pool_create(pool);
 811   struct apply_baton *ab;
 812
 813   ab = apr_palloc(subpool, sizeof(*ab));
 814   ab->source = source;
 815   ab->target = target;
 816   ab->pool = subpool;
 817   ab->sbuf = NULL;
 818   ab->sbuf_size = 0;
 819   ab->sbuf_offset = 0;
 820   ab->sbuf_len = 0;
 821   ab->tbuf = NULL;
 822   ab->tbuf_size = 0;
 823   ab->result_digest = result_digest;
 824
 825   if (result_digest)
 826     apr_md5_init(&(ab->md5_context));
 827
 828   if (error_info)
 829     ab->error_info = apr_pstrdup(subpool, error_info);
 830   else
 831     ab->error_info = NULL;
 832
 833   *handler = apply_window;
 834   *handler_baton = ab;
 835 }
 836
 837
 838 \f
 839 /* Convenience routines */
 840
 841 svn_error_t *
 842 svn_txdelta_send_string(const svn_string_t *string,
 843                         svn_txdelta_window_handler_t handler,
 844                         void *handler_baton,
 845                         apr_pool_t *pool)
 846 {
 847   svn_txdelta_window_t window = { 0 };
 848   svn_txdelta_op_t op;
 849
 850   /* Build a single `new' op */
 851   op.action_code = svn_txdelta_new;
 852   op.offset = 0;
 853   op.length = string->len;
 854
 855   /* Build a single window containing a ptr to the string. */
 856   window.tview_len = string->len;
 857   window.num_ops = 1;
 858   window.ops = &op;
 859   window.new_data = string;
 860
 861   /* Push the one window at the handler. */
 862   SVN_ERR((*handler)(&window, handler_baton));
 863
 864   /* Push a NULL at the handler, because we're done. */
 865   return (*handler)(NULL, handler_baton);
 866 }
 867
 868 svn_error_t *svn_txdelta_send_stream(svn_stream_t *stream,
 869                                      svn_txdelta_window_handler_t handler,
 870                                      void *handler_baton,
 871                                      unsigned char *digest,
 872                                      apr_pool_t *pool)
 873 {
 874   svn_txdelta_window_t delta_window = { 0 };
 875   svn_txdelta_op_t delta_op;
 876   svn_string_t window_data;
 877   char read_buf[SVN__STREAM_CHUNK_SIZE + 1];
 878   svn_checksum_ctx_t *md5_checksum_ctx;
 879
 880   if (digest)
 881     md5_checksum_ctx = svn_checksum_ctx_create(svn_checksum_md5, pool);
 882
 883   while (1)
 884     {
 885       apr_size_t read_len = SVN__STREAM_CHUNK_SIZE;
 886
 887       SVN_ERR(svn_stream_read_full(stream, read_buf, &read_len));
 888       if (read_len == 0)
 889         break;
 890
 891       window_data.data = read_buf;
 892       window_data.len = read_len;
 893
 894       delta_op.action_code = svn_txdelta_new;
 895       delta_op.offset = 0;
 896       delta_op.length = read_len;
 897
 898       delta_window.tview_len = read_len;
 899       delta_window.num_ops = 1;
 900       delta_window.ops = &delta_op;
 901       delta_window.new_data = &window_data;
 902
 903       SVN_ERR(handler(&delta_window, handler_baton));
 904
 905       if (digest)
 906         SVN_ERR(svn_checksum_update(md5_checksum_ctx, read_buf, read_len));
 907
 908       if (read_len < SVN__STREAM_CHUNK_SIZE)
 909         break;
 910     }
 911   SVN_ERR(handler(NULL, handler_baton));
 912
 913   if (digest)
 914     {
 915       svn_checksum_t *md5_checksum;
 916
 917       SVN_ERR(svn_checksum_final(&md5_checksum, md5_checksum_ctx, pool));
 918       memcpy(digest, md5_checksum->digest, APR_MD5_DIGESTSIZE);
 919     }
 920
 921   return SVN_NO_ERROR;
 922 }
 923
 924 svn_error_t *svn_txdelta_send_txstream(svn_txdelta_stream_t *txstream,
 925                                        svn_txdelta_window_handler_t handler,
 926                                        void *handler_baton,
 927                                        apr_pool_t *pool)
 928 {
 929   svn_txdelta_window_t *window;
 930
 931   /* create a pool just for the windows */
 932   apr_pool_t *wpool = svn_pool_create(pool);
 933
 934   do
 935     {
 936       /* free the window (if any) */
 937       svn_pool_clear(wpool);
 938
 939       /* read in a single delta window */
 940       SVN_ERR(svn_txdelta_next_window(&window, txstream, wpool));
 941
 942       /* shove it at the handler */
 943       SVN_ERR((*handler)(window, handler_baton));
 944     }
 945   while (window != NULL);
 946
 947   svn_pool_destroy(wpool);
 948
 949   return SVN_NO_ERROR;
 950 }
 951
 952 svn_error_t *
 953 svn_txdelta_send_contents(const unsigned char *contents,
 954                           apr_size_t len,
 955                           svn_txdelta_window_handler_t handler,
 956                           void *handler_baton,
 957                           apr_pool_t *pool)
 958 {
 959   svn_string_t new_data;
 960   svn_txdelta_op_t op = { svn_txdelta_new, 0, 0 };
 961   svn_txdelta_window_t window = { 0, 0, 0, 1, 0 };
 962   window.ops = &op;
 963   window.new_data = &new_data;
 964
 965   /* send CONTENT as a series of max-sized windows */
 966   while (len > 0)
 967     {
 968       /* stuff next chunk into the window */
 969       window.tview_len = len < SVN_DELTA_WINDOW_SIZE
 970                        ? len
 971                        : SVN_DELTA_WINDOW_SIZE;
 972       op.length = window.tview_len;
 973       new_data.len = window.tview_len;
 974       new_data.data = (const char*)contents;
 975
 976       /* update remaining */
 977       contents += window.tview_len;
 978       len -= window.tview_len;
 979
 980       /* shove it at the handler */
 981       SVN_ERR((*handler)(&window, handler_baton));
 982     }
 983
 984   /* indicate end of stream */
 985   SVN_ERR((*handler)(NULL, handler_baton));
 986
 987   return SVN_NO_ERROR;
 988 }
 989