contrib/subversion/subversion/libsvn_delta/svndiff.c

   1 /*
   2  * svndiff.c -- Encoding and decoding svndiff-format deltas.
   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 #include "svn_delta.h"
  28 #include "svn_io.h"
  29 #include "delta.h"
  30 #include "svn_pools.h"
  31 #include "svn_private_config.h"
  32
  33 #include "private/svn_error_private.h"
  34 #include "private/svn_delta_private.h"
  35 #include "private/svn_subr_private.h"
  36 #include "private/svn_string_private.h"
  37 #include "private/svn_dep_compat.h"
  38
  39 static const char SVNDIFF_V0[] = { 'S', 'V', 'N', 0 };
  40 static const char SVNDIFF_V1[] = { 'S', 'V', 'N', 1 };
  41 static const char SVNDIFF_V2[] = { 'S', 'V', 'N', 2 };
  42
  43 #define SVNDIFF_HEADER_SIZE (sizeof(SVNDIFF_V0))
  44
  45 static const char *
  46 get_svndiff_header(int version)
  47 {
  48   if (version == 2)
  49     return SVNDIFF_V2;
  50   else if (version == 1)
  51     return SVNDIFF_V1;
  52   else
  53     return SVNDIFF_V0;
  54 }
  55
  56 /* ----- Text delta to svndiff ----- */
  57
  58 /* We make one of these and get it passed back to us in calls to the
  59    window handler.  We only use it to record the write function and
  60    baton passed to svn_txdelta_to_svndiff3().  */
  61 struct encoder_baton {
  62   svn_stream_t *output;
  63   svn_boolean_t header_done;
  64   int version;
  65   int compression_level;
  66   /* Pool for temporary allocations, will be cleared periodically. */
  67   apr_pool_t *scratch_pool;
  68 };
  69
  70 /* This is at least as big as the largest size for a single instruction. */
  71 #define MAX_INSTRUCTION_LEN (2*SVN__MAX_ENCODED_UINT_LEN+1)
  72 /* This is at least as big as the largest possible instructions
  73    section: in theory, the instructions could be SVN_DELTA_WINDOW_SIZE
  74    1-byte copy-from-source instructions (though this is very unlikely). */
  75 #define MAX_INSTRUCTION_SECTION_LEN (SVN_DELTA_WINDOW_SIZE*MAX_INSTRUCTION_LEN)
  76
  77
  78 /* Append an encoded integer to a string.  */
  79 static void
  80 append_encoded_int(svn_stringbuf_t *header, svn_filesize_t val)
  81 {
  82   unsigned char buf[SVN__MAX_ENCODED_UINT_LEN], *p;
  83
  84   SVN_ERR_ASSERT_NO_RETURN(val >= 0);
  85   p = svn__encode_uint(buf, (apr_uint64_t)val);
  86   svn_stringbuf_appendbytes(header, (const char *)buf, p - buf);
  87 }
  88
  89 static svn_error_t *
  90 send_simple_insertion_window(svn_txdelta_window_t *window,
  91                              struct encoder_baton *eb)
  92 {
  93   unsigned char headers[SVNDIFF_HEADER_SIZE + 5 * SVN__MAX_ENCODED_UINT_LEN
  94                           + MAX_INSTRUCTION_LEN];
  95   unsigned char ibuf[MAX_INSTRUCTION_LEN];
  96   unsigned char *header_current;
  97   apr_size_t header_len;
  98   apr_size_t ip_len, i;
  99   apr_size_t len = window->new_data->len;
 100
 101   /* there is only one target copy op. It must span the whole window */
 102   assert(window->ops[0].action_code == svn_txdelta_new);
 103   assert(window->ops[0].length == window->tview_len);
 104   assert(window->ops[0].offset == 0);
 105
 106   /* write stream header if necessary */
 107   if (!eb->header_done)
 108     {
 109       eb->header_done = TRUE;
 110       memcpy(headers, get_svndiff_header(eb->version), SVNDIFF_HEADER_SIZE);
 111       header_current = headers + SVNDIFF_HEADER_SIZE;
 112     }
 113   else
 114     {
 115       header_current = headers;
 116     }
 117
 118   /* Encode the action code and length.  */
 119   if (window->tview_len >> 6 == 0)
 120     {
 121       ibuf[0] = (unsigned char)(window->tview_len + (0x2 << 6));
 122       ip_len = 1;
 123     }
 124   else
 125     {
 126       ibuf[0] = (0x2 << 6);
 127       ip_len = svn__encode_uint(ibuf + 1, window->tview_len) - ibuf;
 128     }
 129
 130   /* encode the window header.  Please note that the source window may
 131    * have content despite not being used for deltification. */
 132   header_current = svn__encode_uint(header_current,
 133                                     (apr_uint64_t)window->sview_offset);
 134   header_current = svn__encode_uint(header_current, window->sview_len);
 135   header_current = svn__encode_uint(header_current, window->tview_len);
 136   header_current[0] = (unsigned char)ip_len;  /* 1 instruction */
 137   header_current = svn__encode_uint(&header_current[1], len);
 138
 139   /* append instructions (1 to a handful of bytes) */
 140   for (i = 0; i < ip_len; ++i)
 141     header_current[i] = ibuf[i];
 142
 143   header_len = header_current - headers + ip_len;
 144
 145   /* Write out the window.  */
 146   SVN_ERR(svn_stream_write(eb->output, (const char *)headers, &header_len));
 147   if (len)
 148     SVN_ERR(svn_stream_write(eb->output, window->new_data->data, &len));
 149
 150   return SVN_NO_ERROR;
 151 }
 152
 153 /* Encodes delta window WINDOW to svndiff-format.
 154    The svndiff version is VERSION. COMPRESSION_LEVEL is the
 155    compression level to use.
 156    Returned values will be allocated in POOL or refer to *WINDOW
 157    fields. */
 158 static svn_error_t *
 159 encode_window(svn_stringbuf_t **instructions_p,
 160               svn_stringbuf_t **header_p,
 161               const svn_string_t **newdata_p,
 162               svn_txdelta_window_t *window,
 163               int version,
 164               int compression_level,
 165               apr_pool_t *pool)
 166 {
 167   svn_stringbuf_t *instructions;
 168   svn_stringbuf_t *header;
 169   const svn_string_t *newdata;
 170   unsigned char ibuf[MAX_INSTRUCTION_LEN], *ip;
 171   const svn_txdelta_op_t *op;
 172
 173   /* create the necessary data buffers */
 174   instructions = svn_stringbuf_create_empty(pool);
 175   header = svn_stringbuf_create_empty(pool);
 176
 177   /* Encode the instructions.  */
 178   for (op = window->ops; op < window->ops + window->num_ops; op++)
 179     {
 180       /* Encode the action code and length.  */
 181       ip = ibuf;
 182       switch (op->action_code)
 183         {
 184         case svn_txdelta_source: *ip = 0; break;
 185         case svn_txdelta_target: *ip = (0x1 << 6); break;
 186         case svn_txdelta_new:    *ip = (0x2 << 6); break;
 187         }
 188       if (op->length >> 6 == 0)
 189         *ip++ |= (unsigned char)op->length;
 190       else
 191         ip = svn__encode_uint(ip + 1, op->length);
 192       if (op->action_code != svn_txdelta_new)
 193         ip = svn__encode_uint(ip, op->offset);
 194       svn_stringbuf_appendbytes(instructions, (const char *)ibuf, ip - ibuf);
 195     }
 196
 197   /* Encode the header.  */
 198   append_encoded_int(header, window->sview_offset);
 199   append_encoded_int(header, window->sview_len);
 200   append_encoded_int(header, window->tview_len);
 201   if (version == 2)
 202     {
 203       svn_stringbuf_t *compressed_instructions;
 204       compressed_instructions = svn_stringbuf_create_empty(pool);
 205       SVN_ERR(svn__compress_lz4(instructions->data, instructions->len,
 206                                 compressed_instructions));
 207       instructions = compressed_instructions;
 208     }
 209   else if (version == 1)
 210     {
 211       svn_stringbuf_t *compressed_instructions;
 212       compressed_instructions = svn_stringbuf_create_empty(pool);
 213       SVN_ERR(svn__compress_zlib(instructions->data, instructions->len,
 214                                  compressed_instructions, compression_level));
 215       instructions = compressed_instructions;
 216     }
 217   append_encoded_int(header, instructions->len);
 218
 219   /* Encode the data. */
 220   if (version == 2)
 221     {
 222       svn_stringbuf_t *compressed = svn_stringbuf_create_empty(pool);
 223
 224       SVN_ERR(svn__compress_lz4(window->new_data->data, window->new_data->len,
 225                                 compressed));
 226       newdata = svn_stringbuf__morph_into_string(compressed);
 227     }
 228   else if (version == 1)
 229     {
 230       svn_stringbuf_t *compressed = svn_stringbuf_create_empty(pool);
 231
 232       SVN_ERR(svn__compress_zlib(window->new_data->data, window->new_data->len,
 233                                  compressed, compression_level));
 234       newdata = svn_stringbuf__morph_into_string(compressed);
 235     }
 236   else
 237     newdata = window->new_data;
 238
 239   append_encoded_int(header, newdata->len);
 240
 241   *instructions_p = instructions;
 242   *header_p = header;
 243   *newdata_p = newdata;
 244
 245   return SVN_NO_ERROR;
 246 }
 247
 248 /* Note: When changing things here, check the related comment in
 249    the svn_txdelta_to_svndiff_stream() function.  */
 250 static svn_error_t *
 251 window_handler(svn_txdelta_window_t *window, void *baton)
 252 {
 253   struct encoder_baton *eb = baton;
 254   apr_size_t len;
 255   svn_stringbuf_t *instructions;
 256   svn_stringbuf_t *header;
 257   const svn_string_t *newdata;
 258
 259   /* use specialized code if there is no source */
 260   if (window && !window->src_ops && window->num_ops == 1 && !eb->version)
 261     return svn_error_trace(send_simple_insertion_window(window, eb));
 262
 263   /* Make sure we write the header.  */
 264   if (!eb->header_done)
 265     {
 266       len = SVNDIFF_HEADER_SIZE;
 267       SVN_ERR(svn_stream_write(eb->output, get_svndiff_header(eb->version),
 268                                &len));
 269       eb->header_done = TRUE;
 270     }
 271
 272   if (window == NULL)
 273     {
 274       /* We're done; clean up. */
 275       SVN_ERR(svn_stream_close(eb->output));
 276
 277       svn_pool_destroy(eb->scratch_pool);
 278
 279       return SVN_NO_ERROR;
 280     }
 281
 282   svn_pool_clear(eb->scratch_pool);
 283
 284   SVN_ERR(encode_window(&instructions, &header, &newdata, window,
 285                         eb->version, eb->compression_level,
 286                         eb->scratch_pool));
 287
 288   /* Write out the window.  */
 289   len = header->len;
 290   SVN_ERR(svn_stream_write(eb->output, header->data, &len));
 291   if (instructions->len > 0)
 292     {
 293       len = instructions->len;
 294       SVN_ERR(svn_stream_write(eb->output, instructions->data, &len));
 295     }
 296   if (newdata->len > 0)
 297     {
 298       len = newdata->len;
 299       SVN_ERR(svn_stream_write(eb->output, newdata->data, &len));
 300     }
 301
 302   return SVN_NO_ERROR;
 303 }
 304
 305 void
 306 svn_txdelta_to_svndiff3(svn_txdelta_window_handler_t *handler,
 307                         void **handler_baton,
 308                         svn_stream_t *output,
 309                         int svndiff_version,
 310                         int compression_level,
 311                         apr_pool_t *pool)
 312 {
 313   struct encoder_baton *eb;
 314
 315   eb = apr_palloc(pool, sizeof(*eb));
 316   eb->output = output;
 317   eb->header_done = FALSE;
 318   eb->scratch_pool = svn_pool_create(pool);
 319   eb->version = svndiff_version;
 320   eb->compression_level = compression_level;
 321
 322   *handler = window_handler;
 323   *handler_baton = eb;
 324 }
 325
 326 void
 327 svn_txdelta_to_svndiff2(svn_txdelta_window_handler_t *handler,
 328                         void **handler_baton,
 329                         svn_stream_t *output,
 330                         int svndiff_version,
 331                         apr_pool_t *pool)
 332 {
 333   svn_txdelta_to_svndiff3(handler, handler_baton, output, svndiff_version,
 334                           SVN_DELTA_COMPRESSION_LEVEL_DEFAULT, pool);
 335 }
 336
 337 void
 338 svn_txdelta_to_svndiff(svn_stream_t *output,
 339                        apr_pool_t *pool,
 340                        svn_txdelta_window_handler_t *handler,
 341                        void **handler_baton)
 342 {
 343   svn_txdelta_to_svndiff3(handler, handler_baton, output, 0,
 344                           SVN_DELTA_COMPRESSION_LEVEL_DEFAULT, pool);
 345 }
 346
 347 \f
 348 /* ----- svndiff to text delta ----- */
 349
 350 /* An svndiff parser object.  */
 351 struct decode_baton
 352 {
 353   /* Once the svndiff parser has enough data buffered to create a
 354      "window", it passes this window to the caller's consumer routine.  */
 355   svn_txdelta_window_handler_t consumer_func;
 356   void *consumer_baton;
 357
 358   /* Pool to create subpools from; each developing window will be a
 359      subpool.  */
 360   apr_pool_t *pool;
 361
 362   /* The current subpool which contains our current window-buffer.  */
 363   apr_pool_t *subpool;
 364
 365   /* The actual svndiff data buffer, living within subpool.  */
 366   svn_stringbuf_t *buffer;
 367
 368   /* The offset and size of the last source view, so that we can check
 369      to make sure the next one isn't sliding backwards.  */
 370   svn_filesize_t last_sview_offset;
 371   apr_size_t last_sview_len;
 372
 373   /* We have to discard four bytes at the beginning for the header.
 374      This field keeps track of how many of those bytes we have read.  */
 375   apr_size_t header_bytes;
 376
 377   /* Do we want an error to occur when we close the stream that
 378      indicates we didn't send the whole svndiff data?  If you plan to
 379      not transmit the whole svndiff data stream, you will want this to
 380      be FALSE. */
 381   svn_boolean_t error_on_early_close;
 382
 383   /* svndiff version in use by delta.  */
 384   unsigned char version;
 385
 386   /* Length of parsed delta window header. 0 if window is not parsed yet. */
 387   apr_size_t window_header_len;
 388
 389   /* Five integer fields of parsed delta window header. Valid only if
 390      WINDOW_HEADER_LEN > 0 */
 391   svn_filesize_t  sview_offset;
 392   apr_size_t sview_len;
 393   apr_size_t tview_len;
 394   apr_size_t inslen;
 395   apr_size_t newlen;
 396 };
 397
 398
 399 /* Wrapper aroung svn__deencode_uint taking a file size as *VAL. */
 400 static const unsigned char *
 401 decode_file_offset(svn_filesize_t *val,
 402                    const unsigned char *p,
 403                    const unsigned char *end)
 404 {
 405   apr_uint64_t temp = 0;
 406   const unsigned char *result = svn__decode_uint(&temp, p, end);
 407   *val = (svn_filesize_t)temp;
 408
 409   return result;
 410 }
 411
 412 /* Same as above, only decode into a size variable. */
 413 static const unsigned char *
 414 decode_size(apr_size_t *val,
 415             const unsigned char *p,
 416             const unsigned char *end)
 417 {
 418   apr_uint64_t temp = 0;
 419   const unsigned char *result = svn__decode_uint(&temp, p, end);
 420   if (temp > APR_SIZE_MAX)
 421     return NULL;
 422
 423   *val = (apr_size_t)temp;
 424   return result;
 425 }
 426
 427 /* Decode an instruction into OP, returning a pointer to the text
 428    after the instruction.  Note that if the action code is
 429    svn_txdelta_new, the offset field of *OP will not be set.  */
 430 static const unsigned char *
 431 decode_instruction(svn_txdelta_op_t *op,
 432                    const unsigned char *p,
 433                    const unsigned char *end)
 434 {
 435   apr_size_t c;
 436   apr_size_t action;
 437
 438   if (p == end)
 439     return NULL;
 440
 441   /* We need this more than once */
 442   c = *p++;
 443
 444   /* Decode the instruction selector.  */
 445   action = (c >> 6) & 0x3;
 446   if (action >= 0x3)
 447       return NULL;
 448
 449   /* This relies on enum svn_delta_action values to match and never to be
 450      redefined. */
 451   op->action_code = (enum svn_delta_action)(action);
 452
 453   /* Decode the length and offset.  */
 454   op->length = c & 0x3f;
 455   if (op->length == 0)
 456     {
 457       p = decode_size(&op->length, p, end);
 458       if (p == NULL)
 459         return NULL;
 460     }
 461   if (action != svn_txdelta_new)
 462     {
 463       p = decode_size(&op->offset, p, end);
 464       if (p == NULL)
 465         return NULL;
 466     }
 467
 468   return p;
 469 }
 470
 471 /* Count the instructions in the range [P..END-1] and make sure they
 472    are valid for the given window lengths.  Return an error if the
 473    instructions are invalid; otherwise set *NINST to the number of
 474    instructions.  */
 475 static svn_error_t *
 476 count_and_verify_instructions(int *ninst,
 477                               const unsigned char *p,
 478                               const unsigned char *end,
 479                               apr_size_t sview_len,
 480                               apr_size_t tview_len,
 481                               apr_size_t new_len)
 482 {
 483   int n = 0;
 484   svn_txdelta_op_t op;
 485   apr_size_t tpos = 0, npos = 0;
 486
 487   while (p < end)
 488     {
 489       p = decode_instruction(&op, p, end);
 490
 491       /* Detect any malformed operations from the instruction stream. */
 492       if (p == NULL)
 493         return svn_error_createf
 494           (SVN_ERR_SVNDIFF_INVALID_OPS, NULL,
 495            _("Invalid diff stream: insn %d cannot be decoded"), n);
 496       else if (op.length == 0)
 497         return svn_error_createf
 498           (SVN_ERR_SVNDIFF_INVALID_OPS, NULL,
 499            _("Invalid diff stream: insn %d has length zero"), n);
 500       else if (op.length > tview_len - tpos)
 501         return svn_error_createf
 502           (SVN_ERR_SVNDIFF_INVALID_OPS, NULL,
 503            _("Invalid diff stream: insn %d overflows the target view"), n);
 504
 505       switch (op.action_code)
 506         {
 507         case svn_txdelta_source:
 508           if (op.length > sview_len - op.offset ||
 509               op.offset > sview_len)
 510             return svn_error_createf
 511               (SVN_ERR_SVNDIFF_INVALID_OPS, NULL,
 512                _("Invalid diff stream: "
 513                  "[src] insn %d overflows the source view"), n);
 514           break;
 515         case svn_txdelta_target:
 516           if (op.offset >= tpos)
 517             return svn_error_createf
 518               (SVN_ERR_SVNDIFF_INVALID_OPS, NULL,
 519                _("Invalid diff stream: "
 520                  "[tgt] insn %d starts beyond the target view position"), n);
 521           break;
 522         case svn_txdelta_new:
 523           if (op.length > new_len - npos)
 524             return svn_error_createf
 525               (SVN_ERR_SVNDIFF_INVALID_OPS, NULL,
 526                _("Invalid diff stream: "
 527                  "[new] insn %d overflows the new data section"), n);
 528           npos += op.length;
 529           break;
 530         }
 531       tpos += op.length;
 532       n++;
 533     }
 534   if (tpos != tview_len)
 535     return svn_error_create(SVN_ERR_SVNDIFF_INVALID_OPS, NULL,
 536                             _("Delta does not fill the target window"));
 537   if (npos != new_len)
 538     return svn_error_create(SVN_ERR_SVNDIFF_INVALID_OPS, NULL,
 539                             _("Delta does not contain enough new data"));
 540
 541   *ninst = n;
 542   return SVN_NO_ERROR;
 543 }
 544
 545 /* Given the five integer fields of a window header and a pointer to
 546    the remainder of the window contents, fill in a delta window
 547    structure *WINDOW.  New allocations will be performed in POOL;
 548    the new_data field of *WINDOW will refer directly to memory pointed
 549    to by DATA. */
 550 static svn_error_t *
 551 decode_window(svn_txdelta_window_t *window, svn_filesize_t sview_offset,
 552               apr_size_t sview_len, apr_size_t tview_len, apr_size_t inslen,
 553               apr_size_t newlen, const unsigned char *data, apr_pool_t *pool,
 554               unsigned int version)
 555 {
 556   const unsigned char *insend;
 557   int ninst;
 558   apr_size_t npos;
 559   svn_txdelta_op_t *ops, *op;
 560   svn_string_t *new_data;
 561
 562   window->sview_offset = sview_offset;
 563   window->sview_len = sview_len;
 564   window->tview_len = tview_len;
 565
 566   insend = data + inslen;
 567
 568   if (version == 2)
 569     {
 570       svn_stringbuf_t *instout = svn_stringbuf_create_empty(pool);
 571       svn_stringbuf_t *ndout = svn_stringbuf_create_empty(pool);
 572
 573       SVN_ERR(svn__decompress_lz4(insend, newlen, ndout,
 574                                   SVN_DELTA_WINDOW_SIZE));
 575       SVN_ERR(svn__decompress_lz4(data, insend - data, instout,
 576                                   MAX_INSTRUCTION_SECTION_LEN));
 577
 578       newlen = ndout->len;
 579       data = (unsigned char *)instout->data;
 580       insend = (unsigned char *)instout->data + instout->len;
 581
 582       new_data = svn_stringbuf__morph_into_string(ndout);
 583     }
 584   else if (version == 1)
 585     {
 586       svn_stringbuf_t *instout = svn_stringbuf_create_empty(pool);
 587       svn_stringbuf_t *ndout = svn_stringbuf_create_empty(pool);
 588
 589       SVN_ERR(svn__decompress_zlib(insend, newlen, ndout,
 590                                    SVN_DELTA_WINDOW_SIZE));
 591       SVN_ERR(svn__decompress_zlib(data, insend - data, instout,
 592                                    MAX_INSTRUCTION_SECTION_LEN));
 593
 594       newlen = ndout->len;
 595       data = (unsigned char *)instout->data;
 596       insend = (unsigned char *)instout->data + instout->len;
 597
 598       new_data = svn_stringbuf__morph_into_string(ndout);
 599     }
 600   else
 601     {
 602       /* Copy the data because an svn_string_t must have the invariant
 603          data[len]=='\0'. */
 604       new_data = svn_string_ncreate((const char*)insend, newlen, pool);
 605     }
 606
 607   /* Count the instructions and make sure they are all valid.  */
 608   SVN_ERR(count_and_verify_instructions(&ninst, data, insend,
 609                                         sview_len, tview_len, newlen));
 610
 611   /* Allocate a buffer for the instructions and decode them. */
 612   ops = apr_palloc(pool, ninst * sizeof(*ops));
 613   npos = 0;
 614   window->src_ops = 0;
 615   for (op = ops; op < ops + ninst; op++)
 616     {
 617       data = decode_instruction(op, data, insend);
 618       if (op->action_code == svn_txdelta_source)
 619         ++window->src_ops;
 620       else if (op->action_code == svn_txdelta_new)
 621         {
 622           op->offset = npos;
 623           npos += op->length;
 624         }
 625     }
 626   SVN_ERR_ASSERT(data == insend);
 627
 628   window->ops = ops;
 629   window->num_ops = ninst;
 630   window->new_data = new_data;
 631
 632   return SVN_NO_ERROR;
 633 }
 634
 635 static svn_error_t *
 636 write_handler(void *baton,
 637               const char *buffer,
 638               apr_size_t *len)
 639 {
 640   struct decode_baton *db = (struct decode_baton *) baton;
 641   const unsigned char *p, *end;
 642   apr_size_t buflen = *len;
 643
 644   /* Chew up four bytes at the beginning for the header.  */
 645   if (db->header_bytes < SVNDIFF_HEADER_SIZE)
 646     {
 647       apr_size_t nheader = SVNDIFF_HEADER_SIZE - db->header_bytes;
 648       if (nheader > buflen)
 649         nheader = buflen;
 650       if (memcmp(buffer, SVNDIFF_V0 + db->header_bytes, nheader) == 0)
 651         db->version = 0;
 652       else if (memcmp(buffer, SVNDIFF_V1 + db->header_bytes, nheader) == 0)
 653         db->version = 1;
 654       else if (memcmp(buffer, SVNDIFF_V2 + db->header_bytes, nheader) == 0)
 655         db->version = 2;
 656       else
 657         return svn_error_create(SVN_ERR_SVNDIFF_INVALID_HEADER, NULL,
 658                                 _("Svndiff has invalid header"));
 659       buflen -= nheader;
 660       buffer += nheader;
 661       db->header_bytes += nheader;
 662     }
 663
 664   /* Concatenate the old with the new.  */
 665   svn_stringbuf_appendbytes(db->buffer, buffer, buflen);
 666
 667   /* We have a buffer of svndiff data that might be good for:
 668
 669      a) an integral number of windows' worth of data - this is a
 670         trivial case.  Make windows from our data and ship them off.
 671
 672      b) a non-integral number of windows' worth of data - we shall
 673         consume the integral portion of the window data, and then
 674         somewhere in the following loop the decoding of the svndiff
 675         data will run out of stuff to decode, and will simply return
 676         SVN_NO_ERROR, anxiously awaiting more data.
 677   */
 678
 679   while (1)
 680     {
 681       svn_txdelta_window_t window;
 682
 683       /* Read the header, if we have enough bytes for that.  */
 684       p = (const unsigned char *) db->buffer->data;
 685       end = (const unsigned char *) db->buffer->data + db->buffer->len;
 686
 687       if (db->window_header_len == 0)
 688         {
 689           svn_filesize_t sview_offset;
 690           apr_size_t sview_len, tview_len, inslen, newlen;
 691           const unsigned char *hdr_start = p;
 692
 693           p = decode_file_offset(&sview_offset, p, end);
 694           if (p == NULL)
 695               break;
 696
 697           p = decode_size(&sview_len, p, end);
 698           if (p == NULL)
 699               break;
 700
 701           p = decode_size(&tview_len, p, end);
 702           if (p == NULL)
 703               break;
 704
 705           p = decode_size(&inslen, p, end);
 706           if (p == NULL)
 707               break;
 708
 709           p = decode_size(&newlen, p, end);
 710           if (p == NULL)
 711               break;
 712
 713           if (tview_len > SVN_DELTA_WINDOW_SIZE ||
 714               sview_len > SVN_DELTA_WINDOW_SIZE ||
 715               /* for svndiff1, newlen includes the original length */
 716               newlen > SVN_DELTA_WINDOW_SIZE + SVN__MAX_ENCODED_UINT_LEN ||
 717               inslen > MAX_INSTRUCTION_SECTION_LEN)
 718             return svn_error_create(
 719                      SVN_ERR_SVNDIFF_CORRUPT_WINDOW, NULL,
 720                      _("Svndiff contains a too-large window"));
 721
 722           /* Check for integer overflow.  */
 723           if (sview_offset < 0 || inslen + newlen < inslen
 724               || sview_len + tview_len < sview_len
 725               || (apr_size_t)sview_offset + sview_len < (apr_size_t)sview_offset)
 726             return svn_error_create(
 727                       SVN_ERR_SVNDIFF_CORRUPT_WINDOW, NULL,
 728                       _("Svndiff contains corrupt window header"));
 729
 730           /* Check for source windows which slide backwards.  */
 731           if (sview_len > 0
 732               && (sview_offset < db->last_sview_offset
 733                   || (sview_offset + sview_len
 734                       < db->last_sview_offset + db->last_sview_len)))
 735             return svn_error_create(
 736                      SVN_ERR_SVNDIFF_BACKWARD_VIEW, NULL,
 737                      _("Svndiff has backwards-sliding source views"));
 738
 739           /* Remember parsed window header. */
 740           db->window_header_len = p - hdr_start;
 741           db->sview_offset = sview_offset;
 742           db->sview_len = sview_len;
 743           db->tview_len = tview_len;
 744           db->inslen = inslen;
 745           db->newlen = newlen;
 746         }
 747       else
 748         {
 749           /* Skip already parsed window header. */
 750           p += db->window_header_len;
 751         }
 752
 753       /* Wait for more data if we don't have enough bytes for the
 754          whole window. */
 755       if ((apr_size_t) (end - p) < db->inslen + db->newlen)
 756         return SVN_NO_ERROR;
 757
 758       /* Decode the window and send it off. */
 759       SVN_ERR(decode_window(&window, db->sview_offset, db->sview_len,
 760                             db->tview_len, db->inslen, db->newlen, p,
 761                             db->subpool, db->version));
 762       SVN_ERR(db->consumer_func(&window, db->consumer_baton));
 763
 764       p += db->inslen + db->newlen;
 765
 766       /* Remove processed data from the buffer.  */
 767       svn_stringbuf_remove(db->buffer, 0, db->buffer->len - (end - p));
 768
 769       /* Reset window header length. */
 770       db->window_header_len = 0;
 771
 772       /* Remember the offset and length of the source view for next time.  */
 773       db->last_sview_offset = db->sview_offset;
 774       db->last_sview_len = db->sview_len;
 775
 776       /* Clear subpool. */
 777       svn_pool_clear(db->subpool);
 778     }
 779
 780   /* At this point we processed all integral windows and DB->BUFFER is empty
 781      or contains partially read window header.
 782      Check that unprocessed data is not larger than theoretical maximum
 783      window header size. */
 784   if (db->buffer->len > 5 * SVN__MAX_ENCODED_UINT_LEN)
 785     return svn_error_create(SVN_ERR_SVNDIFF_CORRUPT_WINDOW, NULL,
 786                             _("Svndiff contains a too-large window header"));
 787
 788   return SVN_NO_ERROR;
 789 }
 790
 791 /* Minimal svn_stream_t write handler, doing nothing */
 792 static svn_error_t *
 793 noop_write_handler(void *baton,
 794                    const char *buffer,
 795                    apr_size_t *len)
 796 {
 797   return SVN_NO_ERROR;
 798 }
 799
 800 static svn_error_t *
 801 close_handler(void *baton)
 802 {
 803   struct decode_baton *db = (struct decode_baton *) baton;
 804   svn_error_t *err;
 805
 806   /* Make sure that we're at a plausible end of stream, returning an
 807      error if we are expected to do so.  */
 808   if ((db->error_on_early_close)
 809       && (db->header_bytes < 4 || db->buffer->len != 0))
 810     return svn_error_create(SVN_ERR_SVNDIFF_UNEXPECTED_END, NULL,
 811                             _("Unexpected end of svndiff input"));
 812
 813   /* Tell the window consumer that we're done, and clean up.  */
 814   err = db->consumer_func(NULL, db->consumer_baton);
 815   svn_pool_destroy(db->pool);
 816   return err;
 817 }
 818
 819
 820 svn_stream_t *
 821 svn_txdelta_parse_svndiff(svn_txdelta_window_handler_t handler,
 822                           void *handler_baton,
 823                           svn_boolean_t error_on_early_close,
 824                           apr_pool_t *pool)
 825 {
 826   svn_stream_t *stream;
 827
 828   if (handler != svn_delta_noop_window_handler)
 829     {
 830       apr_pool_t *subpool = svn_pool_create(pool);
 831       struct decode_baton *db = apr_palloc(pool, sizeof(*db));
 832
 833       db->consumer_func = handler;
 834       db->consumer_baton = handler_baton;
 835       db->pool = subpool;
 836       db->subpool = svn_pool_create(subpool);
 837       db->buffer = svn_stringbuf_create_empty(db->pool);
 838       db->last_sview_offset = 0;
 839       db->last_sview_len = 0;
 840       db->header_bytes = 0;
 841       db->error_on_early_close = error_on_early_close;
 842       db->window_header_len = 0;
 843       stream = svn_stream_create(db, pool);
 844
 845       svn_stream_set_write(stream, write_handler);
 846       svn_stream_set_close(stream, close_handler);
 847     }
 848   else
 849     {
 850       /* And else we just ignore everything as efficiently as we can.
 851          by only hooking a no-op handler */
 852       stream = svn_stream_create(NULL, pool);
 853       svn_stream_set_write(stream, noop_write_handler);
 854     }
 855   return stream;
 856 }
 857
 858
 859 /* Routines for reading one svndiff window at a time. */
 860
 861 /* Read one byte from STREAM into *BYTE. */
 862 static svn_error_t *
 863 read_one_byte(unsigned char *byte, svn_stream_t *stream)
 864 {
 865   char c;
 866   apr_size_t len = 1;
 867
 868   SVN_ERR(svn_stream_read_full(stream, &c, &len));
 869   if (len == 0)
 870     return svn_error_create(SVN_ERR_SVNDIFF_UNEXPECTED_END, NULL,
 871                             _("Unexpected end of svndiff input"));
 872   *byte = (unsigned char) c;
 873   return SVN_NO_ERROR;
 874 }
 875
 876 /* Read and decode one integer from STREAM into *SIZE.
 877    Increment *BYTE_COUNTER by the number of chars we have read. */
 878 static svn_error_t *
 879 read_one_size(apr_size_t *size,
 880               apr_size_t *byte_counter,
 881               svn_stream_t *stream)
 882 {
 883   unsigned char c;
 884
 885   *size = 0;
 886   while (1)
 887     {
 888       SVN_ERR(read_one_byte(&c, stream));
 889       ++*byte_counter;
 890       *size = (*size << 7) | (c & 0x7f);
 891       if (!(c & 0x80))
 892         break;
 893     }
 894   return SVN_NO_ERROR;
 895 }
 896
 897 /* Read a window header from STREAM and check it for integer overflow. */
 898 static svn_error_t *
 899 read_window_header(svn_stream_t *stream, svn_filesize_t *sview_offset,
 900                    apr_size_t *sview_len, apr_size_t *tview_len,
 901                    apr_size_t *inslen, apr_size_t *newlen,
 902                    apr_size_t *header_len)
 903 {
 904   unsigned char c;
 905
 906   /* Read the source view offset by hand, since it's not an apr_size_t. */
 907   *header_len = 0;
 908   *sview_offset = 0;
 909   while (1)
 910     {
 911       SVN_ERR(read_one_byte(&c, stream));
 912       ++*header_len;
 913       *sview_offset = (*sview_offset << 7) | (c & 0x7f);
 914       if (!(c & 0x80))
 915         break;
 916     }
 917
 918   /* Read the four size fields. */
 919   SVN_ERR(read_one_size(sview_len, header_len, stream));
 920   SVN_ERR(read_one_size(tview_len, header_len, stream));
 921   SVN_ERR(read_one_size(inslen, header_len, stream));
 922   SVN_ERR(read_one_size(newlen, header_len, stream));
 923
 924   if (*tview_len > SVN_DELTA_WINDOW_SIZE ||
 925       *sview_len > SVN_DELTA_WINDOW_SIZE ||
 926       /* for svndiff1, newlen includes the original length */
 927       *newlen > SVN_DELTA_WINDOW_SIZE + SVN__MAX_ENCODED_UINT_LEN ||
 928       *inslen > MAX_INSTRUCTION_SECTION_LEN)
 929     return svn_error_create(SVN_ERR_SVNDIFF_CORRUPT_WINDOW, NULL,
 930                             _("Svndiff contains a too-large window"));
 931
 932   /* Check for integer overflow.  */
 933   if (*sview_offset < 0 || *inslen + *newlen < *inslen
 934       || *sview_len + *tview_len < *sview_len
 935       || (apr_size_t)*sview_offset + *sview_len < (apr_size_t)*sview_offset)
 936     return svn_error_create(SVN_ERR_SVNDIFF_CORRUPT_WINDOW, NULL,
 937                             _("Svndiff contains corrupt window header"));
 938
 939   return SVN_NO_ERROR;
 940 }
 941
 942 svn_error_t *
 943 svn_txdelta_read_svndiff_window(svn_txdelta_window_t **window,
 944                                 svn_stream_t *stream,
 945                                 int svndiff_version,
 946                                 apr_pool_t *pool)
 947 {
 948   svn_filesize_t sview_offset;
 949   apr_size_t sview_len, tview_len, inslen, newlen, len, header_len;
 950   unsigned char *buf;
 951
 952   SVN_ERR(read_window_header(stream, &sview_offset, &sview_len, &tview_len,
 953                              &inslen, &newlen, &header_len));
 954   len = inslen + newlen;
 955   buf = apr_palloc(pool, len);
 956   SVN_ERR(svn_stream_read_full(stream, (char*)buf, &len));
 957   if (len < inslen + newlen)
 958     return svn_error_create(SVN_ERR_SVNDIFF_UNEXPECTED_END, NULL,
 959                             _("Unexpected end of svndiff input"));
 960   *window = apr_palloc(pool, sizeof(**window));
 961   return decode_window(*window, sview_offset, sview_len, tview_len, inslen,
 962                        newlen, buf, pool, svndiff_version);
 963 }
 964
 965
 966 svn_error_t *
 967 svn_txdelta_skip_svndiff_window(apr_file_t *file,
 968                                 int svndiff_version,
 969                                 apr_pool_t *pool)
 970 {
 971   svn_stream_t *stream = svn_stream_from_aprfile2(file, TRUE, pool);
 972   svn_filesize_t sview_offset;
 973   apr_size_t sview_len, tview_len, inslen, newlen, header_len;
 974   apr_off_t offset;
 975
 976   SVN_ERR(read_window_header(stream, &sview_offset, &sview_len, &tview_len,
 977                              &inslen, &newlen, &header_len));
 978
 979   offset = inslen + newlen;
 980   return svn_io_file_seek(file, APR_CUR, &offset, pool);
 981 }
 982
 983 svn_error_t *
 984 svn_txdelta__read_raw_window_len(apr_size_t *window_len,
 985                                  svn_stream_t *stream,
 986                                  apr_pool_t *pool)
 987 {
 988   svn_filesize_t sview_offset;
 989   apr_size_t sview_len, tview_len, inslen, newlen, header_len;
 990
 991   SVN_ERR(read_window_header(stream, &sview_offset, &sview_len, &tview_len,
 992                              &inslen, &newlen, &header_len));
 993
 994   *window_len = inslen + newlen + header_len;
 995   return SVN_NO_ERROR;
 996 }
 997
 998 typedef struct svndiff_stream_baton_t
 999 {
1000   apr_pool_t *scratch_pool;
1001   svn_txdelta_stream_t *txstream;
1002   svn_txdelta_window_handler_t handler;
1003   void *handler_baton;
1004   svn_stringbuf_t *window_buffer;
1005   apr_size_t read_pos;
1006   svn_boolean_t hit_eof;
1007 } svndiff_stream_baton_t;
1008
1009 static svn_error_t *
1010 svndiff_stream_write_fn(void *baton, const char *data, apr_size_t *len)
1011 {
1012   svndiff_stream_baton_t *b = baton;
1013
1014   /* The memory usage here is limited, as this buffer doesn't grow
1015      beyond the (header size + max window size in svndiff format).
1016      See the comment in svn_txdelta_to_svndiff_stream().  */
1017   svn_stringbuf_appendbytes(b->window_buffer, data, *len);
1018
1019   return SVN_NO_ERROR;
1020 }
1021
1022 static svn_error_t *
1023 svndiff_stream_read_fn(void *baton, char *buffer, apr_size_t *len)
1024 {
1025   svndiff_stream_baton_t *b = baton;
1026   apr_size_t left = *len;
1027   apr_size_t read = 0;
1028
1029   while (left)
1030     {
1031       apr_size_t chunk_size;
1032
1033       if (b->read_pos == b->window_buffer->len && !b->hit_eof)
1034         {
1035           svn_txdelta_window_t *window;
1036
1037           svn_pool_clear(b->scratch_pool);
1038           svn_stringbuf_setempty(b->window_buffer);
1039           SVN_ERR(svn_txdelta_next_window(&window, b->txstream,
1040                                           b->scratch_pool));
1041           SVN_ERR(b->handler(window, b->handler_baton));
1042           b->read_pos = 0;
1043
1044           if (!window)
1045             b->hit_eof = TRUE;
1046         }
1047
1048       if (left > b->window_buffer->len - b->read_pos)
1049         chunk_size = b->window_buffer->len - b->read_pos;
1050       else
1051         chunk_size = left;
1052
1053       if (!chunk_size)
1054           break;
1055
1056       memcpy(buffer, b->window_buffer->data + b->read_pos, chunk_size);
1057       b->read_pos += chunk_size;
1058       buffer += chunk_size;
1059       read += chunk_size;
1060       left -= chunk_size;
1061     }
1062
1063   *len = read;
1064   return SVN_NO_ERROR;
1065 }
1066
1067 svn_stream_t *
1068 svn_txdelta_to_svndiff_stream(svn_txdelta_stream_t *txstream,
1069                               int svndiff_version,
1070                               int compression_level,
1071                               apr_pool_t *pool)
1072 {
1073   svndiff_stream_baton_t *baton;
1074   svn_stream_t *push_stream;
1075   svn_stream_t *pull_stream;
1076
1077   baton = apr_pcalloc(pool, sizeof(*baton));
1078   baton->scratch_pool = svn_pool_create(pool);
1079   baton->txstream = txstream;
1080   baton->window_buffer = svn_stringbuf_create_empty(pool);
1081   baton->hit_eof = FALSE;
1082   baton->read_pos = 0;
1083
1084   push_stream = svn_stream_create(baton, pool);
1085   svn_stream_set_write(push_stream, svndiff_stream_write_fn);
1086
1087   /* We rely on the implementation detail of the svn_txdelta_to_svndiff3()
1088      function, namely, on how the window_handler() function behaves.
1089      As long as it writes one svndiff window at a time to the target
1090      stream, the memory usage of this function (in other words, how
1091      much data can be accumulated in the internal 'window_buffer')
1092      is limited.  */
1093   svn_txdelta_to_svndiff3(&baton->handler, &baton->handler_baton,
1094                           push_stream, svndiff_version,
1095                           compression_level, pool);
1096
1097   pull_stream = svn_stream_create(baton, pool);
1098   svn_stream_set_read2(pull_stream, NULL, svndiff_stream_read_fn);
1099
1100   return pull_stream;
1101 }