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