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   svn_checksum_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_pmemdup(pool, window->ops, ops_size);
 184   build_baton.new_data =
 185     svn_stringbuf_create_from_string(window->new_data, pool);
 186
 187   new_window = svn_txdelta__make_window(&build_baton, pool);
 188   new_window->sview_offset = window->sview_offset;
 189   new_window->sview_len = window->sview_len;
 190   new_window->tview_len = window->tview_len;
 191   return new_window;
 192 }
 193
 194 /* This is a private interlibrary compatibility wrapper. */
 195 svn_txdelta_window_t *
 196 svn_txdelta__copy_window(const svn_txdelta_window_t *window,
 197                          apr_pool_t *pool);
 198 svn_txdelta_window_t *
 199 svn_txdelta__copy_window(const svn_txdelta_window_t *window,
 200                          apr_pool_t *pool)
 201 {
 202   return svn_txdelta_window_dup(window, pool);
 203 }
 204
 205 \f
 206 /* Insert a delta op into a delta window. */
 207
 208 void
 209 svn_txdelta__insert_op(svn_txdelta__ops_baton_t *build_baton,
 210                        enum svn_delta_action opcode,
 211                        apr_size_t offset,
 212                        apr_size_t length,
 213                        const char *new_data,
 214                        apr_pool_t *pool)
 215 {
 216   svn_txdelta_op_t *op;
 217
 218   /* Check if this op can be merged with the previous op. The delta
 219      combiner sometimes generates such ops, and this is the obvious
 220      place to make the check. */
 221   if (build_baton->num_ops > 0)
 222     {
 223       op = &build_baton->ops[build_baton->num_ops - 1];
 224       if (op->action_code == opcode
 225           && (opcode == svn_txdelta_new
 226               || op->offset + op->length == offset))
 227         {
 228           op->length += length;
 229           if (opcode == svn_txdelta_new)
 230             svn_stringbuf_appendbytes(build_baton->new_data,
 231                                       new_data, length);
 232           return;
 233         }
 234     }
 235
 236   /* Create space for the new op. */
 237   if (build_baton->num_ops == build_baton->ops_size)
 238     {
 239       svn_txdelta_op_t *const old_ops = build_baton->ops;
 240       int const new_ops_size = (build_baton->ops_size == 0
 241                                 ? 16 : 2 * build_baton->ops_size);
 242       build_baton->ops =
 243         apr_palloc(pool, new_ops_size * sizeof(*build_baton->ops));
 244
 245       /* Copy any existing ops into the new array */
 246       if (old_ops)
 247         memcpy(build_baton->ops, old_ops,
 248                build_baton->ops_size * sizeof(*build_baton->ops));
 249       build_baton->ops_size = new_ops_size;
 250     }
 251
 252   /* Insert the op. svn_delta_source and svn_delta_target are
 253      just inserted. For svn_delta_new, the new data must be
 254      copied into the window. */
 255   op = &build_baton->ops[build_baton->num_ops];
 256   switch (opcode)
 257     {
 258     case svn_txdelta_source:
 259       ++build_baton->src_ops;
 260       /*** FALLTHRU ***/
 261     case svn_txdelta_target:
 262       op->action_code = opcode;
 263       op->offset = offset;
 264       op->length = length;
 265       break;
 266     case svn_txdelta_new:
 267       op->action_code = opcode;
 268       op->offset = build_baton->new_data->len;
 269       op->length = length;
 270       svn_stringbuf_appendbytes(build_baton->new_data, new_data, length);
 271       break;
 272     default:
 273       assert(!"unknown delta op.");
 274     }
 275
 276   ++build_baton->num_ops;
 277 }
 278
 279 apr_size_t
 280 svn_txdelta__remove_copy(svn_txdelta__ops_baton_t *build_baton,
 281                          apr_size_t max_len)
 282 {
 283   svn_txdelta_op_t *op;
 284   apr_size_t len = 0;
 285
 286   /* remove ops back to front */
 287   while (build_baton->num_ops > 0)
 288     {
 289       op = &build_baton->ops[build_baton->num_ops-1];
 290
 291       /*  we can't modify svn_txdelta_target ops -> stop there */
 292       if (op->action_code == svn_txdelta_target)
 293         break;
 294
 295       /*  handle the case that we cannot remove the op entirely */
 296       if (op->length + len > max_len)
 297         {
 298           /* truncate only insertions. Copies don't benefit
 299              from being truncated. */
 300           if (op->action_code == svn_txdelta_new)
 301             {
 302                build_baton->new_data->len -= max_len - len;
 303                op->length -= max_len - len;
 304                len = max_len;
 305             }
 306
 307           break;
 308         }
 309
 310       /* drop the op entirely */
 311       if (op->action_code == svn_txdelta_new)
 312         build_baton->new_data->len -= op->length;
 313
 314       len += op->length;
 315       --build_baton->num_ops;
 316     }
 317
 318   return len;
 319 }
 320
 321
 322 \f
 323 /* Generic delta stream functions. */
 324
 325 svn_txdelta_stream_t *
 326 svn_txdelta_stream_create(void *baton,
 327                           svn_txdelta_next_window_fn_t next_window,
 328                           svn_txdelta_md5_digest_fn_t md5_digest,
 329                           apr_pool_t *pool)
 330 {
 331   svn_txdelta_stream_t *stream = apr_palloc(pool, sizeof(*stream));
 332
 333   stream->baton = baton;
 334   stream->next_window = next_window;
 335   stream->md5_digest = md5_digest;
 336
 337   return stream;
 338 }
 339
 340 svn_error_t *
 341 svn_txdelta_next_window(svn_txdelta_window_t **window,
 342                         svn_txdelta_stream_t *stream,
 343                         apr_pool_t *pool)
 344 {
 345   return stream->next_window(window, stream->baton, pool);
 346 }
 347
 348 const unsigned char *
 349 svn_txdelta_md5_digest(svn_txdelta_stream_t *stream)
 350 {
 351   return stream->md5_digest(stream->baton);
 352 }
 353
 354
 355 \f
 356 static svn_error_t *
 357 txdelta_next_window(svn_txdelta_window_t **window,
 358                     void *baton,
 359                     apr_pool_t *pool)
 360 {
 361   struct txdelta_baton *b = baton;
 362   apr_size_t source_len = SVN_DELTA_WINDOW_SIZE;
 363   apr_size_t target_len = SVN_DELTA_WINDOW_SIZE;
 364
 365   /* Read the source stream. */
 366   if (b->more_source)
 367     {
 368       SVN_ERR(svn_stream_read_full(b->source, b->buf, &source_len));
 369       b->more_source = (source_len == SVN_DELTA_WINDOW_SIZE);
 370     }
 371   else
 372     source_len = 0;
 373
 374   /* Read the target stream. */
 375   SVN_ERR(svn_stream_read_full(b->target, b->buf + source_len, &target_len));
 376   b->pos += source_len;
 377
 378   if (target_len == 0)
 379     {
 380       /* No target data?  We're done; return the final window. */
 381       if (b->context != NULL)
 382         SVN_ERR(svn_checksum_final(&b->checksum, b->context, b->result_pool));
 383
 384       *window = NULL;
 385       b->more = FALSE;
 386       return SVN_NO_ERROR;
 387     }
 388   else if (b->context != NULL)
 389     SVN_ERR(svn_checksum_update(b->context, b->buf + source_len, target_len));
 390
 391   *window = compute_window(b->buf, source_len, target_len,
 392                            b->pos - source_len, pool);
 393
 394   /* That's it. */
 395   return SVN_NO_ERROR;
 396 }
 397
 398
 399 static const unsigned char *
 400 txdelta_md5_digest(void *baton)
 401 {
 402   struct txdelta_baton *b = baton;
 403   /* If there are more windows for this stream, the digest has not yet
 404      been calculated.  */
 405   if (b->more)
 406     return NULL;
 407
 408   /* If checksumming has not been activated, there will be no digest. */
 409   if (b->context == NULL)
 410     return NULL;
 411
 412   /* The checksum should be there. */
 413   return b->checksum->digest;
 414 }
 415
 416
 417 svn_error_t *
 418 svn_txdelta_run(svn_stream_t *source,
 419                 svn_stream_t *target,
 420                 svn_txdelta_window_handler_t handler,
 421                 void *handler_baton,
 422                 svn_checksum_kind_t checksum_kind,
 423                 svn_checksum_t **checksum,
 424                 svn_cancel_func_t cancel_func,
 425                 void *cancel_baton,
 426                 apr_pool_t *result_pool,
 427                 apr_pool_t *scratch_pool)
 428 {
 429   apr_pool_t *iterpool = svn_pool_create(scratch_pool);
 430   struct txdelta_baton tb = { 0 };
 431   svn_txdelta_window_t *window;
 432
 433   tb.source = source;
 434   tb.target = target;
 435   tb.more_source = TRUE;
 436   tb.more = TRUE;
 437   tb.pos = 0;
 438   tb.buf = apr_palloc(scratch_pool, 2 * SVN_DELTA_WINDOW_SIZE);
 439   tb.result_pool = result_pool;
 440
 441   if (checksum != NULL)
 442     tb.context = svn_checksum_ctx_create(checksum_kind, scratch_pool);
 443
 444   do
 445     {
 446       /* free the window (if any) */
 447       svn_pool_clear(iterpool);
 448
 449       /* read in a single delta window */
 450       SVN_ERR(txdelta_next_window(&window, &tb, iterpool));
 451
 452       /* shove it at the handler */
 453       SVN_ERR((*handler)(window, handler_baton));
 454
 455       if (cancel_func)
 456         SVN_ERR(cancel_func(cancel_baton));
 457     }
 458   while (window != NULL);
 459
 460   svn_pool_destroy(iterpool);
 461
 462   if (checksum != NULL)
 463     *checksum = tb.checksum;  /* should be there! */
 464
 465   return SVN_NO_ERROR;
 466 }
 467
 468
 469 void
 470 svn_txdelta2(svn_txdelta_stream_t **stream,
 471              svn_stream_t *source,
 472              svn_stream_t *target,
 473              svn_boolean_t calculate_checksum,
 474              apr_pool_t *pool)
 475 {
 476   struct txdelta_baton *b = apr_pcalloc(pool, sizeof(*b));
 477
 478   b->source = source;
 479   b->target = target;
 480   b->more_source = TRUE;
 481   b->more = TRUE;
 482   b->buf = apr_palloc(pool, 2 * SVN_DELTA_WINDOW_SIZE);
 483   b->context = calculate_checksum
 484              ? svn_checksum_ctx_create(svn_checksum_md5, pool)
 485              : NULL;
 486   b->result_pool = pool;
 487
 488   *stream = svn_txdelta_stream_create(b, txdelta_next_window,
 489                                       txdelta_md5_digest, pool);
 490 }
 491
 492 void
 493 svn_txdelta(svn_txdelta_stream_t **stream,
 494             svn_stream_t *source,
 495             svn_stream_t *target,
 496             apr_pool_t *pool)
 497 {
 498   svn_txdelta2(stream, source, target, TRUE, pool);
 499 }
 500
 501
 502 \f
 503 /* Functions for implementing a "target push" delta. */
 504
 505 /* This is the write handler for a target-push delta stream.  It reads
 506  * source data, buffers target data, and fires off delta windows when
 507  * the target data buffer is full. */
 508 static svn_error_t *
 509 tpush_write_handler(void *baton, const char *data, apr_size_t *len)
 510 {
 511   struct tpush_baton *tb = baton;
 512   apr_size_t chunk_len, data_len = *len;
 513   apr_pool_t *pool = svn_pool_create(tb->pool);
 514   svn_txdelta_window_t *window;
 515
 516   while (data_len > 0)
 517     {
 518       svn_pool_clear(pool);
 519
 520       /* Make sure we're all full up on source data, if possible. */
 521       if (tb->source_len == 0 && !tb->source_done)
 522         {
 523           tb->source_len = SVN_DELTA_WINDOW_SIZE;
 524           SVN_ERR(svn_stream_read_full(tb->source, tb->buf, &tb->source_len));
 525           if (tb->source_len < SVN_DELTA_WINDOW_SIZE)
 526             tb->source_done = TRUE;
 527         }
 528
 529       /* Copy in the target data, up to SVN_DELTA_WINDOW_SIZE. */
 530       chunk_len = SVN_DELTA_WINDOW_SIZE - tb->target_len;
 531       if (chunk_len > data_len)
 532         chunk_len = data_len;
 533       memcpy(tb->buf + tb->source_len + tb->target_len, data, chunk_len);
 534       data += chunk_len;
 535       data_len -= chunk_len;
 536       tb->target_len += chunk_len;
 537
 538       /* If we're full of target data, compute and fire off a window. */
 539       if (tb->target_len == SVN_DELTA_WINDOW_SIZE)
 540         {
 541           window = compute_window(tb->buf, tb->source_len, tb->target_len,
 542                                   tb->source_offset, pool);
 543           SVN_ERR(tb->wh(window, tb->whb));
 544           tb->source_offset += tb->source_len;
 545           tb->source_len = 0;
 546           tb->target_len = 0;
 547         }
 548     }
 549
 550   svn_pool_destroy(pool);
 551   return SVN_NO_ERROR;
 552 }
 553
 554
 555 /* This is the close handler for a target-push delta stream.  It sends
 556  * a final window if there is any buffered target data, and then sends
 557  * a NULL window signifying the end of the window stream. */
 558 static svn_error_t *
 559 tpush_close_handler(void *baton)
 560 {
 561   struct tpush_baton *tb = baton;
 562   svn_txdelta_window_t *window;
 563
 564   /* Send a final window if we have any residual target data. */
 565   if (tb->target_len > 0)
 566     {
 567       window = compute_window(tb->buf, tb->source_len, tb->target_len,
 568                               tb->source_offset, tb->pool);
 569       SVN_ERR(tb->wh(window, tb->whb));
 570     }
 571
 572   /* Send a final NULL window signifying the end. */
 573   return tb->wh(NULL, tb->whb);
 574 }
 575
 576
 577 svn_stream_t *
 578 svn_txdelta_target_push(svn_txdelta_window_handler_t handler,
 579                         void *handler_baton, svn_stream_t *source,
 580                         apr_pool_t *pool)
 581 {
 582   struct tpush_baton *tb;
 583   svn_stream_t *stream;
 584
 585   /* Initialize baton. */
 586   tb = apr_palloc(pool, sizeof(*tb));
 587   tb->source = source;
 588   tb->wh = handler;
 589   tb->whb = handler_baton;
 590   tb->pool = pool;
 591   tb->buf = apr_palloc(pool, 2 * SVN_DELTA_WINDOW_SIZE);
 592   tb->source_offset = 0;
 593   tb->source_len = 0;
 594   tb->source_done = FALSE;
 595   tb->target_len = 0;
 596
 597   /* Create and return writable stream. */
 598   stream = svn_stream_create(tb, pool);
 599   svn_stream_set_write(stream, tpush_write_handler);
 600   svn_stream_set_close(stream, tpush_close_handler);
 601   return stream;
 602 }
 603
 604
 605 \f
 606 /* Functions for applying deltas.  */
 607
 608 /* Ensure that BUF has enough space for VIEW_LEN bytes.  */
 609 static APR_INLINE svn_error_t *
 610 size_buffer(char **buf, apr_size_t *buf_size,
 611             apr_size_t view_len, apr_pool_t *pool)
 612 {
 613   if (view_len > *buf_size)
 614     {
 615       *buf_size *= 2;
 616       if (*buf_size < view_len)
 617         *buf_size = view_len;
 618       SVN_ERR_ASSERT(APR_ALIGN_DEFAULT(*buf_size) >= *buf_size);
 619       *buf = apr_palloc(pool, *buf_size);
 620     }
 621
 622   return SVN_NO_ERROR;
 623 }
 624
 625 /* Copy LEN bytes from SOURCE to TARGET.  Unlike memmove() or memcpy(),
 626  * create repeating patterns if the source and target ranges overlap.
 627  * Return a pointer to the first byte after the copied target range.  */
 628 static APR_INLINE char *
 629 patterning_copy(char *target, const char *source, apr_size_t len)
 630 {
 631   /* If the source and target overlap, repeat the overlapping pattern
 632      in the target buffer. Always copy from the source buffer because
 633      presumably it will be in the L1 cache after the first iteration
 634      and doing this should avoid pipeline stalls due to write/read
 635      dependencies. */
 636   const apr_size_t overlap = target - source;
 637   while (len > overlap)
 638     {
 639       memcpy(target, source, overlap);
 640       target += overlap;
 641       len -= overlap;
 642     }
 643
 644   /* Copy any remaining source pattern. */
 645   if (len)
 646     {
 647       memcpy(target, source, len);
 648       target += len;
 649     }
 650
 651   return target;
 652 }
 653
 654 void
 655 svn_txdelta_apply_instructions(svn_txdelta_window_t *window,
 656                                const char *sbuf, char *tbuf,
 657                                apr_size_t *tlen)
 658 {
 659   const svn_txdelta_op_t *op;
 660   apr_size_t tpos = 0;
 661
 662   /* Nothing to do for empty buffers.
 663    * This check allows for NULL TBUF in that case. */
 664   if (*tlen == 0)
 665     return;
 666
 667   for (op = window->ops; op < window->ops + window->num_ops; op++)
 668     {
 669       const apr_size_t buf_len = (op->length < *tlen - tpos
 670                                   ? op->length : *tlen - tpos);
 671
 672       /* Check some invariants common to all instructions.  */
 673       assert(tpos + op->length <= window->tview_len);
 674
 675       switch (op->action_code)
 676         {
 677         case svn_txdelta_source:
 678           /* Copy from source area.  */
 679           assert(sbuf);
 680           assert(op->offset + op->length <= window->sview_len);
 681           memcpy(tbuf + tpos, sbuf + op->offset, buf_len);
 682           break;
 683
 684         case svn_txdelta_target:
 685           /* Copy from target area.  We can't use memcpy() or the like
 686            * since we need a specific semantics for overlapping copies:
 687            * they must result in repeating patterns.
 688            * Note that most copies won't have overlapping source and
 689            * target ranges (they are just a result of self-compressed
 690            * data) but a small percentage will.  */
 691           assert(op->offset < tpos);
 692           patterning_copy(tbuf + tpos, tbuf + op->offset, buf_len);
 693           break;
 694
 695         case svn_txdelta_new:
 696           /* Copy from window new area.  */
 697           assert(op->offset + op->length <= window->new_data->len);
 698           memcpy(tbuf + tpos,
 699                  window->new_data->data + op->offset,
 700                  buf_len);
 701           break;
 702
 703         default:
 704           assert(!"Invalid delta instruction code");
 705         }
 706
 707       tpos += op->length;
 708       if (tpos >= *tlen)
 709         return;                 /* The buffer is full. */
 710     }
 711
 712   /* Check that we produced the right amount of data.  */
 713   assert(tpos == window->tview_len);
 714   *tlen = tpos;
 715 }
 716
 717 /* Apply WINDOW to the streams given by APPL.  */
 718 static svn_error_t *
 719 apply_window(svn_txdelta_window_t *window, void *baton)
 720 {
 721   struct apply_baton *ab = (struct apply_baton *) baton;
 722   apr_size_t len;
 723
 724   if (window == NULL)
 725     {
 726       svn_error_t *err = SVN_NO_ERROR;
 727
 728       /* We're done; just clean up.  */
 729       if (ab->result_digest)
 730         {
 731           svn_checksum_t *md5_checksum;
 732
 733           err = svn_checksum_final(&md5_checksum, ab->md5_context, ab->pool);
 734           if (!err)
 735             memcpy(ab->result_digest, md5_checksum->digest,
 736                    svn_checksum_size(md5_checksum));
 737         }
 738
 739       err = svn_error_compose_create(err, svn_stream_close(ab->target));
 740       svn_pool_destroy(ab->pool);
 741
 742       return err;
 743     }
 744
 745   /* Make sure the source view didn't slide backwards.  */
 746   SVN_ERR_ASSERT(window->sview_len == 0
 747                  || (window->sview_offset >= ab->sbuf_offset
 748                      && (window->sview_offset + window->sview_len
 749                          >= ab->sbuf_offset + ab->sbuf_len)));
 750
 751   /* Make sure there's enough room in the target buffer.  */
 752   SVN_ERR(size_buffer(&ab->tbuf, &ab->tbuf_size, window->tview_len, ab->pool));
 753
 754   /* Prepare the source buffer for reading from the input stream.  */
 755   if (window->sview_offset != ab->sbuf_offset
 756       || window->sview_len > ab->sbuf_size)
 757     {
 758       char *old_sbuf = ab->sbuf;
 759
 760       /* Make sure there's enough room.  */
 761       SVN_ERR(size_buffer(&ab->sbuf, &ab->sbuf_size, window->sview_len,
 762               ab->pool));
 763
 764       /* If the existing view overlaps with the new view, copy the
 765        * overlap to the beginning of the new buffer.  */
 766       if (  (apr_size_t)ab->sbuf_offset + ab->sbuf_len
 767           > (apr_size_t)window->sview_offset)
 768         {
 769           apr_size_t start =
 770             (apr_size_t)(window->sview_offset - ab->sbuf_offset);
 771           memmove(ab->sbuf, old_sbuf + start, ab->sbuf_len - start);
 772           ab->sbuf_len -= start;
 773         }
 774       else
 775         ab->sbuf_len = 0;
 776       ab->sbuf_offset = window->sview_offset;
 777     }
 778
 779   /* Read the remainder of the source view into the buffer.  */
 780   if (ab->sbuf_len < window->sview_len)
 781     {
 782       len = window->sview_len - ab->sbuf_len;
 783       SVN_ERR(svn_stream_read_full(ab->source, ab->sbuf + ab->sbuf_len, &len));
 784       if (len != window->sview_len - ab->sbuf_len)
 785         return svn_error_create(SVN_ERR_INCOMPLETE_DATA, NULL,
 786                                 "Delta source ended unexpectedly");
 787       ab->sbuf_len = window->sview_len;
 788     }
 789
 790   /* Apply the window instructions to the source view to generate
 791      the target view.  */
 792   len = window->tview_len;
 793   svn_txdelta_apply_instructions(window, ab->sbuf, ab->tbuf, &len);
 794   SVN_ERR_ASSERT(len == window->tview_len);
 795
 796   /* Write out the output. */
 797
 798   /* Just update the context here. */
 799   if (ab->result_digest)
 800     SVN_ERR(svn_checksum_update(ab->md5_context, ab->tbuf, len));
 801
 802   return svn_stream_write(ab->target, ab->tbuf, &len);
 803 }
 804
 805
 806 void
 807 svn_txdelta_apply(svn_stream_t *source,
 808                   svn_stream_t *target,
 809                   unsigned char *result_digest,
 810                   const char *error_info,
 811                   apr_pool_t *pool,
 812                   svn_txdelta_window_handler_t *handler,
 813                   void **handler_baton)
 814 {
 815   apr_pool_t *subpool = svn_pool_create(pool);
 816   struct apply_baton *ab;
 817
 818   ab = apr_palloc(subpool, sizeof(*ab));
 819   ab->source = source;
 820   ab->target = target;
 821   ab->pool = subpool;
 822   ab->sbuf = NULL;
 823   ab->sbuf_size = 0;
 824   ab->sbuf_offset = 0;
 825   ab->sbuf_len = 0;
 826   ab->tbuf = NULL;
 827   ab->tbuf_size = 0;
 828   ab->result_digest = result_digest;
 829
 830   if (result_digest)
 831     ab->md5_context = svn_checksum_ctx_create(svn_checksum_md5, subpool);
 832
 833   if (error_info)
 834     ab->error_info = apr_pstrdup(subpool, error_info);
 835   else
 836     ab->error_info = NULL;
 837
 838   *handler = apply_window;
 839   *handler_baton = ab;
 840 }
 841
 842
 843 \f
 844 /* Convenience routines */
 845
 846 svn_error_t *
 847 svn_txdelta_send_string(const svn_string_t *string,
 848                         svn_txdelta_window_handler_t handler,
 849                         void *handler_baton,
 850                         apr_pool_t *pool)
 851 {
 852   svn_txdelta_window_t window = { 0 };
 853   svn_txdelta_op_t op;
 854
 855   /* Build a single `new' op */
 856   op.action_code = svn_txdelta_new;
 857   op.offset = 0;
 858   op.length = string->len;
 859
 860   /* Build a single window containing a ptr to the string. */
 861   window.tview_len = string->len;
 862   window.num_ops = 1;
 863   window.ops = &op;
 864   window.new_data = string;
 865
 866   /* Push the one window at the handler. */
 867   SVN_ERR((*handler)(&window, handler_baton));
 868
 869   /* Push a NULL at the handler, because we're done. */
 870   return (*handler)(NULL, handler_baton);
 871 }
 872
 873 svn_error_t *svn_txdelta_send_stream(svn_stream_t *stream,
 874                                      svn_txdelta_window_handler_t handler,
 875                                      void *handler_baton,
 876                                      unsigned char *digest,
 877                                      apr_pool_t *pool)
 878 {
 879   svn_txdelta_window_t delta_window = { 0 };
 880   svn_txdelta_op_t delta_op;
 881   svn_string_t window_data;
 882   char read_buf[SVN__STREAM_CHUNK_SIZE + 1];
 883   svn_checksum_ctx_t *md5_checksum_ctx;
 884
 885   if (digest)
 886     md5_checksum_ctx = svn_checksum_ctx_create(svn_checksum_md5, pool);
 887
 888   while (1)
 889     {
 890       apr_size_t read_len = SVN__STREAM_CHUNK_SIZE;
 891
 892       SVN_ERR(svn_stream_read_full(stream, read_buf, &read_len));
 893       if (read_len == 0)
 894         break;
 895
 896       window_data.data = read_buf;
 897       window_data.len = read_len;
 898
 899       delta_op.action_code = svn_txdelta_new;
 900       delta_op.offset = 0;
 901       delta_op.length = read_len;
 902
 903       delta_window.tview_len = read_len;
 904       delta_window.num_ops = 1;
 905       delta_window.ops = &delta_op;
 906       delta_window.new_data = &window_data;
 907
 908       SVN_ERR(handler(&delta_window, handler_baton));
 909
 910       if (digest)
 911         SVN_ERR(svn_checksum_update(md5_checksum_ctx, read_buf, read_len));
 912
 913       if (read_len < SVN__STREAM_CHUNK_SIZE)
 914         break;
 915     }
 916   SVN_ERR(handler(NULL, handler_baton));
 917
 918   if (digest)
 919     {
 920       svn_checksum_t *md5_checksum;
 921
 922       SVN_ERR(svn_checksum_final(&md5_checksum, md5_checksum_ctx, pool));
 923       memcpy(digest, md5_checksum->digest, APR_MD5_DIGESTSIZE);
 924     }
 925
 926   return SVN_NO_ERROR;
 927 }
 928
 929 svn_error_t *svn_txdelta_send_txstream(svn_txdelta_stream_t *txstream,
 930                                        svn_txdelta_window_handler_t handler,
 931                                        void *handler_baton,
 932                                        apr_pool_t *pool)
 933 {
 934   svn_txdelta_window_t *window;
 935
 936   /* create a pool just for the windows */
 937   apr_pool_t *wpool = svn_pool_create(pool);
 938
 939   do
 940     {
 941       /* free the window (if any) */
 942       svn_pool_clear(wpool);
 943
 944       /* read in a single delta window */
 945       SVN_ERR(svn_txdelta_next_window(&window, txstream, wpool));
 946
 947       /* shove it at the handler */
 948       SVN_ERR((*handler)(window, handler_baton));
 949     }
 950   while (window != NULL);
 951
 952   svn_pool_destroy(wpool);
 953
 954   return SVN_NO_ERROR;
 955 }
 956
 957 svn_error_t *
 958 svn_txdelta_send_contents(const unsigned char *contents,
 959                           apr_size_t len,
 960                           svn_txdelta_window_handler_t handler,
 961                           void *handler_baton,
 962                           apr_pool_t *pool)
 963 {
 964   svn_string_t new_data;
 965   svn_txdelta_op_t op = { svn_txdelta_new, 0, 0 };
 966   svn_txdelta_window_t window = { 0, 0, 0, 1, 0 };
 967   window.ops = &op;
 968   window.new_data = &new_data;
 969
 970   /* send CONTENT as a series of max-sized windows */
 971   while (len > 0)
 972     {
 973       /* stuff next chunk into the window */
 974       window.tview_len = len < SVN_DELTA_WINDOW_SIZE
 975                        ? len
 976                        : SVN_DELTA_WINDOW_SIZE;
 977       op.length = window.tview_len;
 978       new_data.len = window.tview_len;
 979       new_data.data = (const char*)contents;
 980
 981       /* update remaining */
 982       contents += window.tview_len;
 983       len -= window.tview_len;
 984
 985       /* shove it at the handler */
 986       SVN_ERR((*handler)(&window, handler_baton));
 987     }
 988
 989   /* indicate end of stream */
 990   SVN_ERR((*handler)(NULL, handler_baton));
 991
 992   return SVN_NO_ERROR;
 993 }
 994