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 39/* Text delta stream descriptor. */ 40 41struct 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. */ 49struct 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 70struct 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 88struct 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 115svn_txdelta_window_t * 116svn_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. */ 146static svn_txdelta_window_t * 147compute_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 172svn_txdelta_window_t * 173svn_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. */ 196svn_txdelta_window_t * 197svn_txdelta__copy_window(const svn_txdelta_window_t *window, 198 apr_pool_t *pool); 199svn_txdelta_window_t * 200svn_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 207/* Insert a delta op into a delta window. */ 208 209void 210svn_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 280apr_size_t 281svn_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 324/* Generic delta stream functions. */ 325 326svn_txdelta_stream_t * 327svn_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 341svn_error_t * 342svn_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 349const unsigned char * 350svn_txdelta_md5_digest(svn_txdelta_stream_t *stream) 351{ 352 return stream->md5_digest(stream->baton); 353} 354 355 356 357static svn_error_t * 358txdelta_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 400static const unsigned char * 401txdelta_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 418svn_error_t * 419svn_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 470void 471svn_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 493void 494svn_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 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. */ 509static svn_error_t * 510tpush_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. */ 559static svn_error_t * 560tpush_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 578svn_stream_t * 579svn_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 607/* Functions for applying deltas. */ 608 609/* Ensure that BUF has enough space for VIEW_LEN bytes. */ 610static APR_INLINE svn_error_t * 611size_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. */ 640static APR_INLINE char * 641fast_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. */ 663static APR_INLINE char * 664patterning_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 692void 693svn_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. */ 751void 752svn_txdelta__apply_instructions(svn_txdelta_window_t *window, 753 const char *sbuf, char *tbuf, 754 apr_size_t *tlen); 755void 756svn_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. */ 765static svn_error_t * 766apply_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 853void 854svn_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 891/* Convenience routines */ 892 893svn_error_t * 894svn_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 920svn_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 976svn_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 1004svn_error_t * 1005svn_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 1042