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(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(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(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, optimizing for the case where LEN
 627  * is often very small.  Return a pointer to the first byte after the copied
 628  * target range, unlike standard memcpy(), as a potential further
 629  * optimization for the caller.
 630  *
 631  * memcpy() is hard to tune for a wide range of buffer lengths.  Therefore,
 632  * it is often tuned for high throughput on large buffers and relatively
 633  * low latency for mid-sized buffers (tens of bytes).  However, the overhead
 634  * for very small buffers (<10 bytes) is still high.  Even passing the
 635  * parameters, for instance, may take as long as copying 3 bytes.
 636  *
 637  * Because short copy sequences seem to be a common case, at least in
 638  * "format 2" FSFS repositories, we copy them directly.  Larger buffer sizes
 639  * aren't hurt measurably by the exta 'if' clause.  */
 640 static APR_INLINE char *
 641 fast_memcpy(char *target, const char *source, apr_size_t len)
 642 {
 643   if (len > 7)
 644     {
 645       memcpy(target, source, len);
 646       target += len;
 647     }
 648   else
 649     {
 650       /* memcpy is not exactly fast for small block sizes.
 651        * Since they are common, let's run optimized code for them. */
 652       const char *end = source + len;
 653       for (; source != end; source++)
 654         *(target++) = *source;
 655     }
 656
 657   return target;
 658 }
 659
 660 /* Copy LEN bytes from SOURCE to TARGET.  Unlike memmove() or memcpy(),
 661  * create repeating patterns if the source and target ranges overlap.
 662  * Return a pointer to the first byte after the copied target range.  */
 663 static APR_INLINE char *
 664 patterning_copy(char *target, const char *source, apr_size_t len)
 665 {
 666   const char *end = source + len;
 667
 668   /* On many machines, we can do "chunky" copies. */
 669
 670 #if SVN_UNALIGNED_ACCESS_IS_OK
 671
 672   if (end + sizeof(apr_uint32_t) <= target)
 673     {
 674       /* Source and target are at least 4 bytes apart, so we can copy in
 675        * 4-byte chunks.  */
 676       for (; source + sizeof(apr_uint32_t) <= end;
 677            source += sizeof(apr_uint32_t),
 678            target += sizeof(apr_uint32_t))
 679       *(apr_uint32_t *)(target) = *(apr_uint32_t *)(source);
 680     }
 681
 682 #endif
 683
 684   /* fall through to byte-wise copy (either for the below-chunk-size tail
 685    * or the whole copy) */
 686   for (; source != end; source++)
 687     *(target++) = *source;
 688
 689   return target;
 690 }
 691
 692 void
 693 svn_txdelta_apply_instructions(svn_txdelta_window_t *window,
 694                                const char *sbuf, char *tbuf,
 695                                apr_size_t *tlen)
 696 {
 697   const svn_txdelta_op_t *op;
 698   apr_size_t tpos = 0;
 699
 700   for (op = window->ops; op < window->ops + window->num_ops; op++)
 701     {
 702       const apr_size_t buf_len = (op->length < *tlen - tpos
 703                                   ? op->length : *tlen - tpos);
 704
 705       /* Check some invariants common to all instructions.  */
 706       assert(tpos + op->length <= window->tview_len);
 707
 708       switch (op->action_code)
 709         {
 710         case svn_txdelta_source:
 711           /* Copy from source area.  */
 712           assert(sbuf);
 713           assert(op->offset + op->length <= window->sview_len);
 714           fast_memcpy(tbuf + tpos, sbuf + op->offset, buf_len);
 715           break;
 716
 717         case svn_txdelta_target:
 718           /* Copy from target area.  We can't use memcpy() or the like
 719            * since we need a specific semantics for overlapping copies:
 720            * they must result in repeating patterns.
 721            * Note that most copies won't have overlapping source and
 722            * target ranges (they are just a result of self-compressed
 723            * data) but a small percentage will.  */
 724           assert(op->offset < tpos);
 725           patterning_copy(tbuf + tpos, tbuf + op->offset, buf_len);
 726           break;
 727
 728         case svn_txdelta_new:
 729           /* Copy from window new area.  */
 730           assert(op->offset + op->length <= window->new_data->len);
 731           fast_memcpy(tbuf + tpos,
 732                       window->new_data->data + op->offset,
 733                       buf_len);
 734           break;
 735
 736         default:
 737           assert(!"Invalid delta instruction code");
 738         }
 739
 740       tpos += op->length;
 741       if (tpos >= *tlen)
 742         return;                 /* The buffer is full. */
 743     }
 744
 745   /* Check that we produced the right amount of data.  */
 746   assert(tpos == window->tview_len);
 747   *tlen = tpos;
 748 }
 749
 750 /* This is a private interlibrary compatibility wrapper. */
 751 void
 752 svn_txdelta__apply_instructions(svn_txdelta_window_t *window,
 753                                 const char *sbuf, char *tbuf,
 754                                 apr_size_t *tlen);
 755 void
 756 svn_txdelta__apply_instructions(svn_txdelta_window_t *window,
 757                                 const char *sbuf, char *tbuf,
 758                                 apr_size_t *tlen)
 759 {
 760   svn_txdelta_apply_instructions(window, sbuf, tbuf, tlen);
 761 }
 762
 763
 764 /* Apply WINDOW to the streams given by APPL.  */
 765 static svn_error_t *
 766 apply_window(svn_txdelta_window_t *window, void *baton)
 767 {
 768   struct apply_baton *ab = (struct apply_baton *) baton;
 769   apr_size_t len;
 770   svn_error_t *err;
 771
 772   if (window == NULL)
 773     {
 774       /* We're done; just clean up.  */
 775       if (ab->result_digest)
 776         apr_md5_final(ab->result_digest, &(ab->md5_context));
 777
 778       err = svn_stream_close(ab->target);
 779       svn_pool_destroy(ab->pool);
 780
 781       return err;
 782     }
 783
 784   /* Make sure the source view didn't slide backwards.  */
 785   SVN_ERR_ASSERT(window->sview_len == 0
 786                  || (window->sview_offset >= ab->sbuf_offset
 787                      && (window->sview_offset + window->sview_len
 788                          >= ab->sbuf_offset + ab->sbuf_len)));
 789
 790   /* Make sure there's enough room in the target buffer.  */
 791   SVN_ERR(size_buffer(&ab->tbuf, &ab->tbuf_size, window->tview_len, ab->pool));
 792
 793   /* Prepare the source buffer for reading from the input stream.  */
 794   if (window->sview_offset != ab->sbuf_offset
 795       || window->sview_len > ab->sbuf_size)
 796     {
 797       char *old_sbuf = ab->sbuf;
 798
 799       /* Make sure there's enough room.  */
 800       SVN_ERR(size_buffer(&ab->sbuf, &ab->sbuf_size, window->sview_len,
 801               ab->pool));
 802
 803       /* If the existing view overlaps with the new view, copy the
 804        * overlap to the beginning of the new buffer.  */
 805       if (  (apr_size_t)ab->sbuf_offset + ab->sbuf_len
 806           > (apr_size_t)window->sview_offset)
 807         {
 808           apr_size_t start =
 809             (apr_size_t)(window->sview_offset - ab->sbuf_offset);
 810           memmove(ab->sbuf, old_sbuf + start, ab->sbuf_len - start);
 811           ab->sbuf_len -= start;
 812         }
 813       else
 814         ab->sbuf_len = 0;
 815       ab->sbuf_offset = window->sview_offset;
 816     }
 817
 818   /* Read the remainder of the source view into the buffer.  */
 819   if (ab->sbuf_len < window->sview_len)
 820     {
 821       len = window->sview_len - ab->sbuf_len;
 822       err = svn_stream_read(ab->source, ab->sbuf + ab->sbuf_len, &len);
 823       if (err == SVN_NO_ERROR && len != window->sview_len - ab->sbuf_len)
 824         err = svn_error_create(SVN_ERR_INCOMPLETE_DATA, NULL,
 825                                "Delta source ended unexpectedly");
 826       if (err != SVN_NO_ERROR)
 827         return err;
 828       ab->sbuf_len = window->sview_len;
 829     }
 830
 831   /* Apply the window instructions to the source view to generate
 832      the target view.  */
 833   len = window->tview_len;
 834   svn_txdelta_apply_instructions(window, ab->sbuf, ab->tbuf, &len);
 835   SVN_ERR_ASSERT(len == window->tview_len);
 836
 837   /* Write out the output. */
 838
 839   /* ### We've also considered just adding two (optionally null)
 840      arguments to svn_stream_create(): read_checksum and
 841      write_checksum.  Then instead of every caller updating an md5
 842      context when it calls svn_stream_write() or svn_stream_read(),
 843      streams would do it automatically, and verify the checksum in
 844      svn_stream_closed().  But this might be overkill for issue #689;
 845      so for now we just update the context here. */
 846   if (ab->result_digest)
 847     apr_md5_update(&(ab->md5_context), ab->tbuf, len);
 848
 849   return svn_stream_write(ab->target, ab->tbuf, &len);
 850 }
 851
 852
 853 void
 854 svn_txdelta_apply(svn_stream_t *source,
 855                   svn_stream_t *target,
 856                   unsigned char *result_digest,
 857                   const char *error_info,
 858                   apr_pool_t *pool,
 859                   svn_txdelta_window_handler_t *handler,
 860                   void **handler_baton)
 861 {
 862   apr_pool_t *subpool = svn_pool_create(pool);
 863   struct apply_baton *ab;
 864
 865   ab = apr_palloc(subpool, sizeof(*ab));
 866   ab->source = source;
 867   ab->target = target;
 868   ab->pool = subpool;
 869   ab->sbuf = NULL;
 870   ab->sbuf_size = 0;
 871   ab->sbuf_offset = 0;
 872   ab->sbuf_len = 0;
 873   ab->tbuf = NULL;
 874   ab->tbuf_size = 0;
 875   ab->result_digest = result_digest;
 876
 877   if (result_digest)
 878     apr_md5_init(&(ab->md5_context));
 879
 880   if (error_info)
 881     ab->error_info = apr_pstrdup(subpool, error_info);
 882   else
 883     ab->error_info = NULL;
 884
 885   *handler = apply_window;
 886   *handler_baton = ab;
 887 }
 888
 889
 890 \f
 891 /* Convenience routines */
 892
 893 svn_error_t *
 894 svn_txdelta_send_string(const svn_string_t *string,
 895                         svn_txdelta_window_handler_t handler,
 896                         void *handler_baton,
 897                         apr_pool_t *pool)
 898 {
 899   svn_txdelta_window_t window = { 0 };
 900   svn_txdelta_op_t op;
 901
 902   /* Build a single `new' op */
 903   op.action_code = svn_txdelta_new;
 904   op.offset = 0;
 905   op.length = string->len;
 906
 907   /* Build a single window containing a ptr to the string. */
 908   window.tview_len = string->len;
 909   window.num_ops = 1;
 910   window.ops = &op;
 911   window.new_data = string;
 912
 913   /* Push the one window at the handler. */
 914   SVN_ERR((*handler)(&window, handler_baton));
 915
 916   /* Push a NULL at the handler, because we're done. */
 917   return (*handler)(NULL, handler_baton);
 918 }
 919
 920 svn_error_t *svn_txdelta_send_stream(svn_stream_t *stream,
 921                                      svn_txdelta_window_handler_t handler,
 922                                      void *handler_baton,
 923                                      unsigned char *digest,
 924                                      apr_pool_t *pool)
 925 {
 926   svn_txdelta_window_t delta_window = { 0 };
 927   svn_txdelta_op_t delta_op;
 928   svn_string_t window_data;
 929   char read_buf[SVN__STREAM_CHUNK_SIZE + 1];
 930   svn_checksum_ctx_t *md5_checksum_ctx;
 931
 932   if (digest)
 933     md5_checksum_ctx = svn_checksum_ctx_create(svn_checksum_md5, pool);
 934
 935   while (1)
 936     {
 937       apr_size_t read_len = SVN__STREAM_CHUNK_SIZE;
 938
 939       SVN_ERR(svn_stream_read(stream, read_buf, &read_len));
 940       if (read_len == 0)
 941         break;
 942
 943       window_data.data = read_buf;
 944       window_data.len = read_len;
 945
 946       delta_op.action_code = svn_txdelta_new;
 947       delta_op.offset = 0;
 948       delta_op.length = read_len;
 949
 950       delta_window.tview_len = read_len;
 951       delta_window.num_ops = 1;
 952       delta_window.ops = &delta_op;
 953       delta_window.new_data = &window_data;
 954
 955       SVN_ERR(handler(&delta_window, handler_baton));
 956
 957       if (digest)
 958         SVN_ERR(svn_checksum_update(md5_checksum_ctx, read_buf, read_len));
 959
 960       if (read_len < SVN__STREAM_CHUNK_SIZE)
 961         break;
 962     }
 963   SVN_ERR(handler(NULL, handler_baton));
 964
 965   if (digest)
 966     {
 967       svn_checksum_t *md5_checksum;
 968
 969       SVN_ERR(svn_checksum_final(&md5_checksum, md5_checksum_ctx, pool));
 970       memcpy(digest, md5_checksum->digest, APR_MD5_DIGESTSIZE);
 971     }
 972
 973   return SVN_NO_ERROR;
 974 }
 975
 976 svn_error_t *svn_txdelta_send_txstream(svn_txdelta_stream_t *txstream,
 977                                        svn_txdelta_window_handler_t handler,
 978                                        void *handler_baton,
 979                                        apr_pool_t *pool)
 980 {
 981   svn_txdelta_window_t *window;
 982
 983   /* create a pool just for the windows */
 984   apr_pool_t *wpool = svn_pool_create(pool);
 985
 986   do
 987     {
 988       /* free the window (if any) */
 989       svn_pool_clear(wpool);
 990
 991       /* read in a single delta window */
 992       SVN_ERR(svn_txdelta_next_window(&window, txstream, wpool));
 993
 994       /* shove it at the handler */
 995       SVN_ERR((*handler)(window, handler_baton));
 996     }
 997   while (window != NULL);
 998
 999   svn_pool_destroy(wpool);
1000
1001   return SVN_NO_ERROR;
1002 }
1003
1004 svn_error_t *
1005 svn_txdelta_send_contents(const unsigned char *contents,
1006                           apr_size_t len,
1007                           svn_txdelta_window_handler_t handler,
1008                           void *handler_baton,
1009                           apr_pool_t *pool)
1010 {
1011   svn_string_t new_data;
1012   svn_txdelta_op_t op = { svn_txdelta_new, 0, 0 };
1013   svn_txdelta_window_t window = { 0, 0, 0, 1, 0 };
1014   window.ops = &op;
1015   window.new_data = &new_data;
1016
1017   /* send CONTENT as a series of max-sized windows */
1018   while (len > 0)
1019     {
1020       /* stuff next chunk into the window */
1021       window.tview_len = len < SVN_DELTA_WINDOW_SIZE
1022                        ? len
1023                        : SVN_DELTA_WINDOW_SIZE;
1024       op.length = window.tview_len;
1025       new_data.len = window.tview_len;
1026       new_data.data = (const char*)contents;
1027
1028       /* update remaining */
1029       contents += window.tview_len;
1030       len -= window.tview_len;
1031
1032       /* shove it at the handler */
1033       SVN_ERR((*handler)(&window, handler_baton));
1034     }
1035
1036   /* indicate end of stream */
1037   SVN_ERR((*handler)(NULL, handler_baton));
1038
1039   return SVN_NO_ERROR;
1040 }
1041