1251881Speter/* 2251881Speter * text-delta.c -- Internal text delta representation 3251881Speter * 4251881Speter * ==================================================================== 5251881Speter * Licensed to the Apache Software Foundation (ASF) under one 6251881Speter * or more contributor license agreements. See the NOTICE file 7251881Speter * distributed with this work for additional information 8251881Speter * regarding copyright ownership. The ASF licenses this file 9251881Speter * to you under the Apache License, Version 2.0 (the 10251881Speter * "License"); you may not use this file except in compliance 11251881Speter * with the License. You may obtain a copy of the License at 12251881Speter * 13251881Speter * http://www.apache.org/licenses/LICENSE-2.0 14251881Speter * 15251881Speter * Unless required by applicable law or agreed to in writing, 16251881Speter * software distributed under the License is distributed on an 17251881Speter * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 18251881Speter * KIND, either express or implied. See the License for the 19251881Speter * specific language governing permissions and limitations 20251881Speter * under the License. 21251881Speter * ==================================================================== 22251881Speter */ 23251881Speter 24251881Speter 25251881Speter#include <assert.h> 26251881Speter#include <string.h> 27251881Speter 28251881Speter#include <apr_general.h> /* for APR_INLINE */ 29251881Speter#include <apr_md5.h> /* for, um...MD5 stuff */ 30251881Speter 31251881Speter#include "svn_delta.h" 32251881Speter#include "svn_io.h" 33251881Speter#include "svn_pools.h" 34251881Speter#include "svn_checksum.h" 35251881Speter 36251881Speter#include "delta.h" 37251881Speter 38251881Speter 39251881Speter/* Text delta stream descriptor. */ 40251881Speter 41251881Speterstruct svn_txdelta_stream_t { 42251881Speter /* Copied from parameters to svn_txdelta_stream_create. */ 43251881Speter void *baton; 44251881Speter svn_txdelta_next_window_fn_t next_window; 45251881Speter svn_txdelta_md5_digest_fn_t md5_digest; 46251881Speter}; 47251881Speter 48251881Speter/* Delta stream baton. */ 49251881Speterstruct txdelta_baton { 50251881Speter /* These are copied from parameters passed to svn_txdelta. */ 51251881Speter svn_stream_t *source; 52251881Speter svn_stream_t *target; 53251881Speter 54251881Speter /* Private data */ 55251881Speter svn_boolean_t more_source; /* FALSE if source stream hit EOF. */ 56251881Speter svn_boolean_t more; /* TRUE if there are more data in the pool. */ 57251881Speter svn_filesize_t pos; /* Offset of next read in source file. */ 58251881Speter char *buf; /* Buffer for input data. */ 59251881Speter 60251881Speter svn_checksum_ctx_t *context; /* If not NULL, the context for computing 61251881Speter the checksum. */ 62251881Speter svn_checksum_t *checksum; /* If non-NULL, the checksum of TARGET. */ 63251881Speter 64251881Speter apr_pool_t *result_pool; /* For results (e.g. checksum) */ 65251881Speter}; 66251881Speter 67251881Speter 68251881Speter/* Target-push stream descriptor. */ 69251881Speter 70251881Speterstruct tpush_baton { 71251881Speter /* These are copied from parameters passed to svn_txdelta_target_push. */ 72251881Speter svn_stream_t *source; 73251881Speter svn_txdelta_window_handler_t wh; 74251881Speter void *whb; 75251881Speter apr_pool_t *pool; 76251881Speter 77251881Speter /* Private data */ 78251881Speter char *buf; 79251881Speter svn_filesize_t source_offset; 80251881Speter apr_size_t source_len; 81251881Speter svn_boolean_t source_done; 82251881Speter apr_size_t target_len; 83251881Speter}; 84251881Speter 85251881Speter 86251881Speter/* Text delta applicator. */ 87251881Speter 88251881Speterstruct apply_baton { 89251881Speter /* These are copied from parameters passed to svn_txdelta_apply. */ 90251881Speter svn_stream_t *source; 91251881Speter svn_stream_t *target; 92251881Speter 93251881Speter /* Private data. Between calls, SBUF contains the data from the 94251881Speter * last window's source view, as specified by SBUF_OFFSET and 95251881Speter * SBUF_LEN. The contents of TBUF are not interesting between 96251881Speter * calls. */ 97251881Speter apr_pool_t *pool; /* Pool to allocate data from */ 98251881Speter char *sbuf; /* Source buffer */ 99251881Speter apr_size_t sbuf_size; /* Allocated source buffer space */ 100251881Speter svn_filesize_t sbuf_offset; /* Offset of SBUF data in source stream */ 101251881Speter apr_size_t sbuf_len; /* Length of SBUF data */ 102251881Speter char *tbuf; /* Target buffer */ 103251881Speter apr_size_t tbuf_size; /* Allocated target buffer space */ 104251881Speter 105362181Sdim svn_checksum_ctx_t *md5_context; /* Leads to result_digest below. */ 106251881Speter unsigned char *result_digest; /* MD5 digest of resultant fulltext; 107251881Speter must point to at least APR_MD5_DIGESTSIZE 108251881Speter bytes of storage. */ 109251881Speter 110251881Speter const char *error_info; /* Optional extra info for error returns. */ 111251881Speter}; 112251881Speter 113251881Speter 114251881Speter 115251881Spetersvn_txdelta_window_t * 116251881Spetersvn_txdelta__make_window(const svn_txdelta__ops_baton_t *build_baton, 117251881Speter apr_pool_t *pool) 118251881Speter{ 119251881Speter svn_txdelta_window_t *window; 120251881Speter svn_string_t *new_data = apr_palloc(pool, sizeof(*new_data)); 121251881Speter 122251881Speter window = apr_palloc(pool, sizeof(*window)); 123251881Speter window->sview_offset = 0; 124251881Speter window->sview_len = 0; 125251881Speter window->tview_len = 0; 126251881Speter 127251881Speter window->num_ops = build_baton->num_ops; 128251881Speter window->src_ops = build_baton->src_ops; 129251881Speter window->ops = build_baton->ops; 130251881Speter 131251881Speter /* just copy the fields over, rather than alloc/copying into a whole new 132251881Speter svn_string_t structure. */ 133251881Speter /* ### would be much nicer if window->new_data were not a ptr... */ 134251881Speter new_data->data = build_baton->new_data->data; 135251881Speter new_data->len = build_baton->new_data->len; 136251881Speter window->new_data = new_data; 137251881Speter 138251881Speter return window; 139251881Speter} 140251881Speter 141251881Speter 142251881Speter/* Compute and return a delta window using the xdelta algorithm on 143251881Speter DATA, which contains SOURCE_LEN bytes of source data and TARGET_LEN 144251881Speter bytes of target data. SOURCE_OFFSET gives the offset of the source 145251881Speter data, and is simply copied into the window's sview_offset field. */ 146251881Speterstatic svn_txdelta_window_t * 147251881Spetercompute_window(const char *data, apr_size_t source_len, apr_size_t target_len, 148251881Speter svn_filesize_t source_offset, apr_pool_t *pool) 149251881Speter{ 150251881Speter svn_txdelta__ops_baton_t build_baton = { 0 }; 151251881Speter svn_txdelta_window_t *window; 152251881Speter 153251881Speter /* Compute the delta operations. */ 154251881Speter build_baton.new_data = svn_stringbuf_create_empty(pool); 155251881Speter 156251881Speter if (source_len == 0) 157251881Speter svn_txdelta__insert_op(&build_baton, svn_txdelta_new, 0, target_len, data, 158251881Speter pool); 159251881Speter else 160251881Speter svn_txdelta__xdelta(&build_baton, data, source_len, target_len, pool); 161251881Speter 162251881Speter /* Create and return the delta window. */ 163251881Speter window = svn_txdelta__make_window(&build_baton, pool); 164251881Speter window->sview_offset = source_offset; 165251881Speter window->sview_len = source_len; 166251881Speter window->tview_len = target_len; 167251881Speter return window; 168251881Speter} 169251881Speter 170251881Speter 171251881Speter 172251881Spetersvn_txdelta_window_t * 173251881Spetersvn_txdelta_window_dup(const svn_txdelta_window_t *window, 174251881Speter apr_pool_t *pool) 175251881Speter{ 176251881Speter svn_txdelta__ops_baton_t build_baton = { 0 }; 177251881Speter svn_txdelta_window_t *new_window; 178251881Speter const apr_size_t ops_size = (window->num_ops * sizeof(*build_baton.ops)); 179251881Speter 180251881Speter build_baton.num_ops = window->num_ops; 181251881Speter build_baton.src_ops = window->src_ops; 182251881Speter build_baton.ops_size = window->num_ops; 183362181Sdim build_baton.ops = apr_pmemdup(pool, window->ops, ops_size); 184251881Speter build_baton.new_data = 185251881Speter svn_stringbuf_create_from_string(window->new_data, pool); 186251881Speter 187251881Speter new_window = svn_txdelta__make_window(&build_baton, pool); 188251881Speter new_window->sview_offset = window->sview_offset; 189251881Speter new_window->sview_len = window->sview_len; 190251881Speter new_window->tview_len = window->tview_len; 191251881Speter return new_window; 192251881Speter} 193251881Speter 194251881Speter/* This is a private interlibrary compatibility wrapper. */ 195251881Spetersvn_txdelta_window_t * 196251881Spetersvn_txdelta__copy_window(const svn_txdelta_window_t *window, 197251881Speter apr_pool_t *pool); 198251881Spetersvn_txdelta_window_t * 199251881Spetersvn_txdelta__copy_window(const svn_txdelta_window_t *window, 200251881Speter apr_pool_t *pool) 201251881Speter{ 202251881Speter return svn_txdelta_window_dup(window, pool); 203251881Speter} 204251881Speter 205251881Speter 206251881Speter/* Insert a delta op into a delta window. */ 207251881Speter 208251881Spetervoid 209251881Spetersvn_txdelta__insert_op(svn_txdelta__ops_baton_t *build_baton, 210251881Speter enum svn_delta_action opcode, 211251881Speter apr_size_t offset, 212251881Speter apr_size_t length, 213251881Speter const char *new_data, 214251881Speter apr_pool_t *pool) 215251881Speter{ 216251881Speter svn_txdelta_op_t *op; 217251881Speter 218251881Speter /* Check if this op can be merged with the previous op. The delta 219251881Speter combiner sometimes generates such ops, and this is the obvious 220251881Speter place to make the check. */ 221251881Speter if (build_baton->num_ops > 0) 222251881Speter { 223251881Speter op = &build_baton->ops[build_baton->num_ops - 1]; 224251881Speter if (op->action_code == opcode 225251881Speter && (opcode == svn_txdelta_new 226251881Speter || op->offset + op->length == offset)) 227251881Speter { 228251881Speter op->length += length; 229251881Speter if (opcode == svn_txdelta_new) 230251881Speter svn_stringbuf_appendbytes(build_baton->new_data, 231251881Speter new_data, length); 232251881Speter return; 233251881Speter } 234251881Speter } 235251881Speter 236251881Speter /* Create space for the new op. */ 237251881Speter if (build_baton->num_ops == build_baton->ops_size) 238251881Speter { 239251881Speter svn_txdelta_op_t *const old_ops = build_baton->ops; 240251881Speter int const new_ops_size = (build_baton->ops_size == 0 241251881Speter ? 16 : 2 * build_baton->ops_size); 242251881Speter build_baton->ops = 243251881Speter apr_palloc(pool, new_ops_size * sizeof(*build_baton->ops)); 244251881Speter 245251881Speter /* Copy any existing ops into the new array */ 246251881Speter if (old_ops) 247251881Speter memcpy(build_baton->ops, old_ops, 248251881Speter build_baton->ops_size * sizeof(*build_baton->ops)); 249251881Speter build_baton->ops_size = new_ops_size; 250251881Speter } 251251881Speter 252251881Speter /* Insert the op. svn_delta_source and svn_delta_target are 253251881Speter just inserted. For svn_delta_new, the new data must be 254251881Speter copied into the window. */ 255251881Speter op = &build_baton->ops[build_baton->num_ops]; 256251881Speter switch (opcode) 257251881Speter { 258251881Speter case svn_txdelta_source: 259251881Speter ++build_baton->src_ops; 260251881Speter /*** FALLTHRU ***/ 261251881Speter case svn_txdelta_target: 262251881Speter op->action_code = opcode; 263251881Speter op->offset = offset; 264251881Speter op->length = length; 265251881Speter break; 266251881Speter case svn_txdelta_new: 267251881Speter op->action_code = opcode; 268251881Speter op->offset = build_baton->new_data->len; 269251881Speter op->length = length; 270251881Speter svn_stringbuf_appendbytes(build_baton->new_data, new_data, length); 271251881Speter break; 272251881Speter default: 273251881Speter assert(!"unknown delta op."); 274251881Speter } 275251881Speter 276251881Speter ++build_baton->num_ops; 277251881Speter} 278251881Speter 279251881Speterapr_size_t 280251881Spetersvn_txdelta__remove_copy(svn_txdelta__ops_baton_t *build_baton, 281251881Speter apr_size_t max_len) 282251881Speter{ 283251881Speter svn_txdelta_op_t *op; 284251881Speter apr_size_t len = 0; 285251881Speter 286251881Speter /* remove ops back to front */ 287251881Speter while (build_baton->num_ops > 0) 288251881Speter { 289251881Speter op = &build_baton->ops[build_baton->num_ops-1]; 290251881Speter 291251881Speter /* we can't modify svn_txdelta_target ops -> stop there */ 292251881Speter if (op->action_code == svn_txdelta_target) 293251881Speter break; 294251881Speter 295251881Speter /* handle the case that we cannot remove the op entirely */ 296251881Speter if (op->length + len > max_len) 297251881Speter { 298251881Speter /* truncate only insertions. Copies don't benefit 299251881Speter from being truncated. */ 300251881Speter if (op->action_code == svn_txdelta_new) 301251881Speter { 302251881Speter build_baton->new_data->len -= max_len - len; 303251881Speter op->length -= max_len - len; 304251881Speter len = max_len; 305251881Speter } 306251881Speter 307251881Speter break; 308251881Speter } 309251881Speter 310251881Speter /* drop the op entirely */ 311251881Speter if (op->action_code == svn_txdelta_new) 312251881Speter build_baton->new_data->len -= op->length; 313251881Speter 314251881Speter len += op->length; 315251881Speter --build_baton->num_ops; 316251881Speter } 317251881Speter 318251881Speter return len; 319251881Speter} 320251881Speter 321251881Speter 322251881Speter 323251881Speter/* Generic delta stream functions. */ 324251881Speter 325251881Spetersvn_txdelta_stream_t * 326251881Spetersvn_txdelta_stream_create(void *baton, 327251881Speter svn_txdelta_next_window_fn_t next_window, 328251881Speter svn_txdelta_md5_digest_fn_t md5_digest, 329251881Speter apr_pool_t *pool) 330251881Speter{ 331251881Speter svn_txdelta_stream_t *stream = apr_palloc(pool, sizeof(*stream)); 332251881Speter 333251881Speter stream->baton = baton; 334251881Speter stream->next_window = next_window; 335251881Speter stream->md5_digest = md5_digest; 336251881Speter 337251881Speter return stream; 338251881Speter} 339251881Speter 340251881Spetersvn_error_t * 341251881Spetersvn_txdelta_next_window(svn_txdelta_window_t **window, 342251881Speter svn_txdelta_stream_t *stream, 343251881Speter apr_pool_t *pool) 344251881Speter{ 345251881Speter return stream->next_window(window, stream->baton, pool); 346251881Speter} 347251881Speter 348251881Speterconst unsigned char * 349251881Spetersvn_txdelta_md5_digest(svn_txdelta_stream_t *stream) 350251881Speter{ 351251881Speter return stream->md5_digest(stream->baton); 352251881Speter} 353251881Speter 354251881Speter 355251881Speter 356251881Speterstatic svn_error_t * 357251881Spetertxdelta_next_window(svn_txdelta_window_t **window, 358251881Speter void *baton, 359251881Speter apr_pool_t *pool) 360251881Speter{ 361251881Speter struct txdelta_baton *b = baton; 362251881Speter apr_size_t source_len = SVN_DELTA_WINDOW_SIZE; 363251881Speter apr_size_t target_len = SVN_DELTA_WINDOW_SIZE; 364251881Speter 365251881Speter /* Read the source stream. */ 366251881Speter if (b->more_source) 367251881Speter { 368289180Speter SVN_ERR(svn_stream_read_full(b->source, b->buf, &source_len)); 369251881Speter b->more_source = (source_len == SVN_DELTA_WINDOW_SIZE); 370251881Speter } 371251881Speter else 372251881Speter source_len = 0; 373251881Speter 374251881Speter /* Read the target stream. */ 375289180Speter SVN_ERR(svn_stream_read_full(b->target, b->buf + source_len, &target_len)); 376251881Speter b->pos += source_len; 377251881Speter 378251881Speter if (target_len == 0) 379251881Speter { 380251881Speter /* No target data? We're done; return the final window. */ 381251881Speter if (b->context != NULL) 382251881Speter SVN_ERR(svn_checksum_final(&b->checksum, b->context, b->result_pool)); 383251881Speter 384251881Speter *window = NULL; 385251881Speter b->more = FALSE; 386251881Speter return SVN_NO_ERROR; 387251881Speter } 388251881Speter else if (b->context != NULL) 389251881Speter SVN_ERR(svn_checksum_update(b->context, b->buf + source_len, target_len)); 390251881Speter 391251881Speter *window = compute_window(b->buf, source_len, target_len, 392251881Speter b->pos - source_len, pool); 393251881Speter 394251881Speter /* That's it. */ 395251881Speter return SVN_NO_ERROR; 396251881Speter} 397251881Speter 398251881Speter 399251881Speterstatic const unsigned char * 400251881Spetertxdelta_md5_digest(void *baton) 401251881Speter{ 402251881Speter struct txdelta_baton *b = baton; 403251881Speter /* If there are more windows for this stream, the digest has not yet 404251881Speter been calculated. */ 405251881Speter if (b->more) 406251881Speter return NULL; 407251881Speter 408251881Speter /* If checksumming has not been activated, there will be no digest. */ 409251881Speter if (b->context == NULL) 410251881Speter return NULL; 411251881Speter 412251881Speter /* The checksum should be there. */ 413251881Speter return b->checksum->digest; 414251881Speter} 415251881Speter 416251881Speter 417251881Spetersvn_error_t * 418251881Spetersvn_txdelta_run(svn_stream_t *source, 419251881Speter svn_stream_t *target, 420251881Speter svn_txdelta_window_handler_t handler, 421251881Speter void *handler_baton, 422251881Speter svn_checksum_kind_t checksum_kind, 423251881Speter svn_checksum_t **checksum, 424251881Speter svn_cancel_func_t cancel_func, 425251881Speter void *cancel_baton, 426251881Speter apr_pool_t *result_pool, 427251881Speter apr_pool_t *scratch_pool) 428251881Speter{ 429251881Speter apr_pool_t *iterpool = svn_pool_create(scratch_pool); 430251881Speter struct txdelta_baton tb = { 0 }; 431251881Speter svn_txdelta_window_t *window; 432251881Speter 433251881Speter tb.source = source; 434251881Speter tb.target = target; 435251881Speter tb.more_source = TRUE; 436251881Speter tb.more = TRUE; 437251881Speter tb.pos = 0; 438251881Speter tb.buf = apr_palloc(scratch_pool, 2 * SVN_DELTA_WINDOW_SIZE); 439251881Speter tb.result_pool = result_pool; 440251881Speter 441251881Speter if (checksum != NULL) 442251881Speter tb.context = svn_checksum_ctx_create(checksum_kind, scratch_pool); 443251881Speter 444251881Speter do 445251881Speter { 446251881Speter /* free the window (if any) */ 447251881Speter svn_pool_clear(iterpool); 448251881Speter 449251881Speter /* read in a single delta window */ 450251881Speter SVN_ERR(txdelta_next_window(&window, &tb, iterpool)); 451251881Speter 452251881Speter /* shove it at the handler */ 453251881Speter SVN_ERR((*handler)(window, handler_baton)); 454251881Speter 455251881Speter if (cancel_func) 456251881Speter SVN_ERR(cancel_func(cancel_baton)); 457251881Speter } 458251881Speter while (window != NULL); 459251881Speter 460251881Speter svn_pool_destroy(iterpool); 461251881Speter 462251881Speter if (checksum != NULL) 463251881Speter *checksum = tb.checksum; /* should be there! */ 464251881Speter 465251881Speter return SVN_NO_ERROR; 466251881Speter} 467251881Speter 468251881Speter 469251881Spetervoid 470251881Spetersvn_txdelta2(svn_txdelta_stream_t **stream, 471251881Speter svn_stream_t *source, 472251881Speter svn_stream_t *target, 473251881Speter svn_boolean_t calculate_checksum, 474251881Speter apr_pool_t *pool) 475251881Speter{ 476251881Speter struct txdelta_baton *b = apr_pcalloc(pool, sizeof(*b)); 477251881Speter 478251881Speter b->source = source; 479251881Speter b->target = target; 480251881Speter b->more_source = TRUE; 481251881Speter b->more = TRUE; 482251881Speter b->buf = apr_palloc(pool, 2 * SVN_DELTA_WINDOW_SIZE); 483251881Speter b->context = calculate_checksum 484251881Speter ? svn_checksum_ctx_create(svn_checksum_md5, pool) 485251881Speter : NULL; 486251881Speter b->result_pool = pool; 487251881Speter 488251881Speter *stream = svn_txdelta_stream_create(b, txdelta_next_window, 489251881Speter txdelta_md5_digest, pool); 490251881Speter} 491251881Speter 492251881Spetervoid 493251881Spetersvn_txdelta(svn_txdelta_stream_t **stream, 494251881Speter svn_stream_t *source, 495251881Speter svn_stream_t *target, 496251881Speter apr_pool_t *pool) 497251881Speter{ 498251881Speter svn_txdelta2(stream, source, target, TRUE, pool); 499251881Speter} 500251881Speter 501251881Speter 502251881Speter 503251881Speter/* Functions for implementing a "target push" delta. */ 504251881Speter 505251881Speter/* This is the write handler for a target-push delta stream. It reads 506251881Speter * source data, buffers target data, and fires off delta windows when 507251881Speter * the target data buffer is full. */ 508251881Speterstatic svn_error_t * 509251881Spetertpush_write_handler(void *baton, const char *data, apr_size_t *len) 510251881Speter{ 511251881Speter struct tpush_baton *tb = baton; 512251881Speter apr_size_t chunk_len, data_len = *len; 513251881Speter apr_pool_t *pool = svn_pool_create(tb->pool); 514251881Speter svn_txdelta_window_t *window; 515251881Speter 516251881Speter while (data_len > 0) 517251881Speter { 518251881Speter svn_pool_clear(pool); 519251881Speter 520251881Speter /* Make sure we're all full up on source data, if possible. */ 521251881Speter if (tb->source_len == 0 && !tb->source_done) 522251881Speter { 523251881Speter tb->source_len = SVN_DELTA_WINDOW_SIZE; 524289180Speter SVN_ERR(svn_stream_read_full(tb->source, tb->buf, &tb->source_len)); 525251881Speter if (tb->source_len < SVN_DELTA_WINDOW_SIZE) 526251881Speter tb->source_done = TRUE; 527251881Speter } 528251881Speter 529251881Speter /* Copy in the target data, up to SVN_DELTA_WINDOW_SIZE. */ 530251881Speter chunk_len = SVN_DELTA_WINDOW_SIZE - tb->target_len; 531251881Speter if (chunk_len > data_len) 532251881Speter chunk_len = data_len; 533251881Speter memcpy(tb->buf + tb->source_len + tb->target_len, data, chunk_len); 534251881Speter data += chunk_len; 535251881Speter data_len -= chunk_len; 536251881Speter tb->target_len += chunk_len; 537251881Speter 538251881Speter /* If we're full of target data, compute and fire off a window. */ 539251881Speter if (tb->target_len == SVN_DELTA_WINDOW_SIZE) 540251881Speter { 541251881Speter window = compute_window(tb->buf, tb->source_len, tb->target_len, 542251881Speter tb->source_offset, pool); 543251881Speter SVN_ERR(tb->wh(window, tb->whb)); 544251881Speter tb->source_offset += tb->source_len; 545251881Speter tb->source_len = 0; 546251881Speter tb->target_len = 0; 547251881Speter } 548251881Speter } 549251881Speter 550251881Speter svn_pool_destroy(pool); 551251881Speter return SVN_NO_ERROR; 552251881Speter} 553251881Speter 554251881Speter 555251881Speter/* This is the close handler for a target-push delta stream. It sends 556251881Speter * a final window if there is any buffered target data, and then sends 557251881Speter * a NULL window signifying the end of the window stream. */ 558251881Speterstatic svn_error_t * 559251881Spetertpush_close_handler(void *baton) 560251881Speter{ 561251881Speter struct tpush_baton *tb = baton; 562251881Speter svn_txdelta_window_t *window; 563251881Speter 564251881Speter /* Send a final window if we have any residual target data. */ 565251881Speter if (tb->target_len > 0) 566251881Speter { 567251881Speter window = compute_window(tb->buf, tb->source_len, tb->target_len, 568251881Speter tb->source_offset, tb->pool); 569251881Speter SVN_ERR(tb->wh(window, tb->whb)); 570251881Speter } 571251881Speter 572251881Speter /* Send a final NULL window signifying the end. */ 573251881Speter return tb->wh(NULL, tb->whb); 574251881Speter} 575251881Speter 576251881Speter 577251881Spetersvn_stream_t * 578251881Spetersvn_txdelta_target_push(svn_txdelta_window_handler_t handler, 579251881Speter void *handler_baton, svn_stream_t *source, 580251881Speter apr_pool_t *pool) 581251881Speter{ 582251881Speter struct tpush_baton *tb; 583251881Speter svn_stream_t *stream; 584251881Speter 585251881Speter /* Initialize baton. */ 586251881Speter tb = apr_palloc(pool, sizeof(*tb)); 587251881Speter tb->source = source; 588251881Speter tb->wh = handler; 589251881Speter tb->whb = handler_baton; 590251881Speter tb->pool = pool; 591251881Speter tb->buf = apr_palloc(pool, 2 * SVN_DELTA_WINDOW_SIZE); 592251881Speter tb->source_offset = 0; 593251881Speter tb->source_len = 0; 594251881Speter tb->source_done = FALSE; 595251881Speter tb->target_len = 0; 596251881Speter 597251881Speter /* Create and return writable stream. */ 598251881Speter stream = svn_stream_create(tb, pool); 599251881Speter svn_stream_set_write(stream, tpush_write_handler); 600251881Speter svn_stream_set_close(stream, tpush_close_handler); 601251881Speter return stream; 602251881Speter} 603251881Speter 604251881Speter 605251881Speter 606251881Speter/* Functions for applying deltas. */ 607251881Speter 608251881Speter/* Ensure that BUF has enough space for VIEW_LEN bytes. */ 609251881Speterstatic APR_INLINE svn_error_t * 610251881Spetersize_buffer(char **buf, apr_size_t *buf_size, 611251881Speter apr_size_t view_len, apr_pool_t *pool) 612251881Speter{ 613251881Speter if (view_len > *buf_size) 614251881Speter { 615251881Speter *buf_size *= 2; 616251881Speter if (*buf_size < view_len) 617251881Speter *buf_size = view_len; 618251881Speter SVN_ERR_ASSERT(APR_ALIGN_DEFAULT(*buf_size) >= *buf_size); 619251881Speter *buf = apr_palloc(pool, *buf_size); 620251881Speter } 621251881Speter 622251881Speter return SVN_NO_ERROR; 623251881Speter} 624251881Speter 625251881Speter/* Copy LEN bytes from SOURCE to TARGET. Unlike memmove() or memcpy(), 626251881Speter * create repeating patterns if the source and target ranges overlap. 627251881Speter * Return a pointer to the first byte after the copied target range. */ 628251881Speterstatic APR_INLINE char * 629251881Speterpatterning_copy(char *target, const char *source, apr_size_t len) 630251881Speter{ 631289180Speter /* If the source and target overlap, repeat the overlapping pattern 632289180Speter in the target buffer. Always copy from the source buffer because 633289180Speter presumably it will be in the L1 cache after the first iteration 634289180Speter and doing this should avoid pipeline stalls due to write/read 635289180Speter dependencies. */ 636289180Speter const apr_size_t overlap = target - source; 637289180Speter while (len > overlap) 638289180Speter { 639289180Speter memcpy(target, source, overlap); 640289180Speter target += overlap; 641289180Speter len -= overlap; 642289180Speter } 643251881Speter 644289180Speter /* Copy any remaining source pattern. */ 645289180Speter if (len) 646251881Speter { 647289180Speter memcpy(target, source, len); 648289180Speter target += len; 649251881Speter } 650251881Speter 651251881Speter return target; 652251881Speter} 653251881Speter 654251881Spetervoid 655251881Spetersvn_txdelta_apply_instructions(svn_txdelta_window_t *window, 656251881Speter const char *sbuf, char *tbuf, 657251881Speter apr_size_t *tlen) 658251881Speter{ 659251881Speter const svn_txdelta_op_t *op; 660251881Speter apr_size_t tpos = 0; 661251881Speter 662289180Speter /* Nothing to do for empty buffers. 663289180Speter * This check allows for NULL TBUF in that case. */ 664289180Speter if (*tlen == 0) 665289180Speter return; 666289180Speter 667251881Speter for (op = window->ops; op < window->ops + window->num_ops; op++) 668251881Speter { 669251881Speter const apr_size_t buf_len = (op->length < *tlen - tpos 670251881Speter ? op->length : *tlen - tpos); 671251881Speter 672251881Speter /* Check some invariants common to all instructions. */ 673251881Speter assert(tpos + op->length <= window->tview_len); 674251881Speter 675251881Speter switch (op->action_code) 676251881Speter { 677251881Speter case svn_txdelta_source: 678251881Speter /* Copy from source area. */ 679251881Speter assert(sbuf); 680251881Speter assert(op->offset + op->length <= window->sview_len); 681289180Speter memcpy(tbuf + tpos, sbuf + op->offset, buf_len); 682251881Speter break; 683251881Speter 684251881Speter case svn_txdelta_target: 685251881Speter /* Copy from target area. We can't use memcpy() or the like 686251881Speter * since we need a specific semantics for overlapping copies: 687251881Speter * they must result in repeating patterns. 688251881Speter * Note that most copies won't have overlapping source and 689251881Speter * target ranges (they are just a result of self-compressed 690251881Speter * data) but a small percentage will. */ 691251881Speter assert(op->offset < tpos); 692251881Speter patterning_copy(tbuf + tpos, tbuf + op->offset, buf_len); 693251881Speter break; 694251881Speter 695251881Speter case svn_txdelta_new: 696251881Speter /* Copy from window new area. */ 697251881Speter assert(op->offset + op->length <= window->new_data->len); 698289180Speter memcpy(tbuf + tpos, 699289180Speter window->new_data->data + op->offset, 700289180Speter buf_len); 701251881Speter break; 702251881Speter 703251881Speter default: 704251881Speter assert(!"Invalid delta instruction code"); 705251881Speter } 706251881Speter 707251881Speter tpos += op->length; 708251881Speter if (tpos >= *tlen) 709251881Speter return; /* The buffer is full. */ 710251881Speter } 711251881Speter 712251881Speter /* Check that we produced the right amount of data. */ 713251881Speter assert(tpos == window->tview_len); 714251881Speter *tlen = tpos; 715251881Speter} 716251881Speter 717251881Speter/* Apply WINDOW to the streams given by APPL. */ 718251881Speterstatic svn_error_t * 719251881Speterapply_window(svn_txdelta_window_t *window, void *baton) 720251881Speter{ 721251881Speter struct apply_baton *ab = (struct apply_baton *) baton; 722251881Speter apr_size_t len; 723251881Speter 724251881Speter if (window == NULL) 725251881Speter { 726362181Sdim svn_error_t *err = SVN_NO_ERROR; 727362181Sdim 728251881Speter /* We're done; just clean up. */ 729251881Speter if (ab->result_digest) 730362181Sdim { 731362181Sdim svn_checksum_t *md5_checksum; 732251881Speter 733362181Sdim err = svn_checksum_final(&md5_checksum, ab->md5_context, ab->pool); 734362181Sdim if (!err) 735362181Sdim memcpy(ab->result_digest, md5_checksum->digest, 736362181Sdim svn_checksum_size(md5_checksum)); 737362181Sdim } 738362181Sdim 739362181Sdim err = svn_error_compose_create(err, svn_stream_close(ab->target)); 740251881Speter svn_pool_destroy(ab->pool); 741251881Speter 742251881Speter return err; 743251881Speter } 744251881Speter 745251881Speter /* Make sure the source view didn't slide backwards. */ 746251881Speter SVN_ERR_ASSERT(window->sview_len == 0 747251881Speter || (window->sview_offset >= ab->sbuf_offset 748251881Speter && (window->sview_offset + window->sview_len 749251881Speter >= ab->sbuf_offset + ab->sbuf_len))); 750251881Speter 751251881Speter /* Make sure there's enough room in the target buffer. */ 752251881Speter SVN_ERR(size_buffer(&ab->tbuf, &ab->tbuf_size, window->tview_len, ab->pool)); 753251881Speter 754251881Speter /* Prepare the source buffer for reading from the input stream. */ 755251881Speter if (window->sview_offset != ab->sbuf_offset 756251881Speter || window->sview_len > ab->sbuf_size) 757251881Speter { 758251881Speter char *old_sbuf = ab->sbuf; 759251881Speter 760251881Speter /* Make sure there's enough room. */ 761251881Speter SVN_ERR(size_buffer(&ab->sbuf, &ab->sbuf_size, window->sview_len, 762251881Speter ab->pool)); 763251881Speter 764251881Speter /* If the existing view overlaps with the new view, copy the 765251881Speter * overlap to the beginning of the new buffer. */ 766251881Speter if ( (apr_size_t)ab->sbuf_offset + ab->sbuf_len 767251881Speter > (apr_size_t)window->sview_offset) 768251881Speter { 769251881Speter apr_size_t start = 770251881Speter (apr_size_t)(window->sview_offset - ab->sbuf_offset); 771251881Speter memmove(ab->sbuf, old_sbuf + start, ab->sbuf_len - start); 772251881Speter ab->sbuf_len -= start; 773251881Speter } 774251881Speter else 775251881Speter ab->sbuf_len = 0; 776251881Speter ab->sbuf_offset = window->sview_offset; 777251881Speter } 778251881Speter 779251881Speter /* Read the remainder of the source view into the buffer. */ 780251881Speter if (ab->sbuf_len < window->sview_len) 781251881Speter { 782251881Speter len = window->sview_len - ab->sbuf_len; 783362181Sdim SVN_ERR(svn_stream_read_full(ab->source, ab->sbuf + ab->sbuf_len, &len)); 784362181Sdim if (len != window->sview_len - ab->sbuf_len) 785362181Sdim return svn_error_create(SVN_ERR_INCOMPLETE_DATA, NULL, 786362181Sdim "Delta source ended unexpectedly"); 787251881Speter ab->sbuf_len = window->sview_len; 788251881Speter } 789251881Speter 790251881Speter /* Apply the window instructions to the source view to generate 791251881Speter the target view. */ 792251881Speter len = window->tview_len; 793251881Speter svn_txdelta_apply_instructions(window, ab->sbuf, ab->tbuf, &len); 794251881Speter SVN_ERR_ASSERT(len == window->tview_len); 795251881Speter 796251881Speter /* Write out the output. */ 797251881Speter 798289180Speter /* Just update the context here. */ 799251881Speter if (ab->result_digest) 800362181Sdim SVN_ERR(svn_checksum_update(ab->md5_context, ab->tbuf, len)); 801251881Speter 802251881Speter return svn_stream_write(ab->target, ab->tbuf, &len); 803251881Speter} 804251881Speter 805251881Speter 806251881Spetervoid 807251881Spetersvn_txdelta_apply(svn_stream_t *source, 808251881Speter svn_stream_t *target, 809251881Speter unsigned char *result_digest, 810251881Speter const char *error_info, 811251881Speter apr_pool_t *pool, 812251881Speter svn_txdelta_window_handler_t *handler, 813251881Speter void **handler_baton) 814251881Speter{ 815251881Speter apr_pool_t *subpool = svn_pool_create(pool); 816251881Speter struct apply_baton *ab; 817251881Speter 818251881Speter ab = apr_palloc(subpool, sizeof(*ab)); 819251881Speter ab->source = source; 820251881Speter ab->target = target; 821251881Speter ab->pool = subpool; 822251881Speter ab->sbuf = NULL; 823251881Speter ab->sbuf_size = 0; 824251881Speter ab->sbuf_offset = 0; 825251881Speter ab->sbuf_len = 0; 826251881Speter ab->tbuf = NULL; 827251881Speter ab->tbuf_size = 0; 828251881Speter ab->result_digest = result_digest; 829251881Speter 830251881Speter if (result_digest) 831362181Sdim ab->md5_context = svn_checksum_ctx_create(svn_checksum_md5, subpool); 832251881Speter 833251881Speter if (error_info) 834251881Speter ab->error_info = apr_pstrdup(subpool, error_info); 835251881Speter else 836251881Speter ab->error_info = NULL; 837251881Speter 838251881Speter *handler = apply_window; 839251881Speter *handler_baton = ab; 840251881Speter} 841251881Speter 842251881Speter 843251881Speter 844251881Speter/* Convenience routines */ 845251881Speter 846251881Spetersvn_error_t * 847251881Spetersvn_txdelta_send_string(const svn_string_t *string, 848251881Speter svn_txdelta_window_handler_t handler, 849251881Speter void *handler_baton, 850251881Speter apr_pool_t *pool) 851251881Speter{ 852251881Speter svn_txdelta_window_t window = { 0 }; 853251881Speter svn_txdelta_op_t op; 854251881Speter 855251881Speter /* Build a single `new' op */ 856251881Speter op.action_code = svn_txdelta_new; 857251881Speter op.offset = 0; 858251881Speter op.length = string->len; 859251881Speter 860251881Speter /* Build a single window containing a ptr to the string. */ 861251881Speter window.tview_len = string->len; 862251881Speter window.num_ops = 1; 863251881Speter window.ops = &op; 864251881Speter window.new_data = string; 865251881Speter 866251881Speter /* Push the one window at the handler. */ 867251881Speter SVN_ERR((*handler)(&window, handler_baton)); 868251881Speter 869251881Speter /* Push a NULL at the handler, because we're done. */ 870251881Speter return (*handler)(NULL, handler_baton); 871251881Speter} 872251881Speter 873251881Spetersvn_error_t *svn_txdelta_send_stream(svn_stream_t *stream, 874251881Speter svn_txdelta_window_handler_t handler, 875251881Speter void *handler_baton, 876251881Speter unsigned char *digest, 877251881Speter apr_pool_t *pool) 878251881Speter{ 879251881Speter svn_txdelta_window_t delta_window = { 0 }; 880251881Speter svn_txdelta_op_t delta_op; 881251881Speter svn_string_t window_data; 882251881Speter char read_buf[SVN__STREAM_CHUNK_SIZE + 1]; 883251881Speter svn_checksum_ctx_t *md5_checksum_ctx; 884251881Speter 885251881Speter if (digest) 886251881Speter md5_checksum_ctx = svn_checksum_ctx_create(svn_checksum_md5, pool); 887251881Speter 888251881Speter while (1) 889251881Speter { 890251881Speter apr_size_t read_len = SVN__STREAM_CHUNK_SIZE; 891251881Speter 892289180Speter SVN_ERR(svn_stream_read_full(stream, read_buf, &read_len)); 893251881Speter if (read_len == 0) 894251881Speter break; 895251881Speter 896251881Speter window_data.data = read_buf; 897251881Speter window_data.len = read_len; 898251881Speter 899251881Speter delta_op.action_code = svn_txdelta_new; 900251881Speter delta_op.offset = 0; 901251881Speter delta_op.length = read_len; 902251881Speter 903251881Speter delta_window.tview_len = read_len; 904251881Speter delta_window.num_ops = 1; 905251881Speter delta_window.ops = &delta_op; 906251881Speter delta_window.new_data = &window_data; 907251881Speter 908251881Speter SVN_ERR(handler(&delta_window, handler_baton)); 909251881Speter 910251881Speter if (digest) 911251881Speter SVN_ERR(svn_checksum_update(md5_checksum_ctx, read_buf, read_len)); 912251881Speter 913251881Speter if (read_len < SVN__STREAM_CHUNK_SIZE) 914251881Speter break; 915251881Speter } 916251881Speter SVN_ERR(handler(NULL, handler_baton)); 917251881Speter 918251881Speter if (digest) 919251881Speter { 920251881Speter svn_checksum_t *md5_checksum; 921251881Speter 922251881Speter SVN_ERR(svn_checksum_final(&md5_checksum, md5_checksum_ctx, pool)); 923251881Speter memcpy(digest, md5_checksum->digest, APR_MD5_DIGESTSIZE); 924251881Speter } 925251881Speter 926251881Speter return SVN_NO_ERROR; 927251881Speter} 928251881Speter 929251881Spetersvn_error_t *svn_txdelta_send_txstream(svn_txdelta_stream_t *txstream, 930251881Speter svn_txdelta_window_handler_t handler, 931251881Speter void *handler_baton, 932251881Speter apr_pool_t *pool) 933251881Speter{ 934251881Speter svn_txdelta_window_t *window; 935251881Speter 936251881Speter /* create a pool just for the windows */ 937251881Speter apr_pool_t *wpool = svn_pool_create(pool); 938251881Speter 939251881Speter do 940251881Speter { 941251881Speter /* free the window (if any) */ 942251881Speter svn_pool_clear(wpool); 943251881Speter 944251881Speter /* read in a single delta window */ 945251881Speter SVN_ERR(svn_txdelta_next_window(&window, txstream, wpool)); 946251881Speter 947251881Speter /* shove it at the handler */ 948251881Speter SVN_ERR((*handler)(window, handler_baton)); 949251881Speter } 950251881Speter while (window != NULL); 951251881Speter 952251881Speter svn_pool_destroy(wpool); 953251881Speter 954251881Speter return SVN_NO_ERROR; 955251881Speter} 956251881Speter 957251881Spetersvn_error_t * 958251881Spetersvn_txdelta_send_contents(const unsigned char *contents, 959251881Speter apr_size_t len, 960251881Speter svn_txdelta_window_handler_t handler, 961251881Speter void *handler_baton, 962251881Speter apr_pool_t *pool) 963251881Speter{ 964251881Speter svn_string_t new_data; 965251881Speter svn_txdelta_op_t op = { svn_txdelta_new, 0, 0 }; 966251881Speter svn_txdelta_window_t window = { 0, 0, 0, 1, 0 }; 967251881Speter window.ops = &op; 968251881Speter window.new_data = &new_data; 969251881Speter 970251881Speter /* send CONTENT as a series of max-sized windows */ 971251881Speter while (len > 0) 972251881Speter { 973251881Speter /* stuff next chunk into the window */ 974251881Speter window.tview_len = len < SVN_DELTA_WINDOW_SIZE 975251881Speter ? len 976251881Speter : SVN_DELTA_WINDOW_SIZE; 977251881Speter op.length = window.tview_len; 978251881Speter new_data.len = window.tview_len; 979251881Speter new_data.data = (const char*)contents; 980251881Speter 981251881Speter /* update remaining */ 982251881Speter contents += window.tview_len; 983251881Speter len -= window.tview_len; 984251881Speter 985251881Speter /* shove it at the handler */ 986251881Speter SVN_ERR((*handler)(&window, handler_baton)); 987251881Speter } 988251881Speter 989251881Speter /* indicate end of stream */ 990251881Speter SVN_ERR((*handler)(NULL, handler_baton)); 991251881Speter 992251881Speter return SVN_NO_ERROR; 993251881Speter} 994251881Speter 995