xref: /NextBSD/contrib/subversion/subversion/libsvn_subr/packed_data.c (revision 84d351007654069f9643c8e4b4802a7f5f08ee42)

/* packed_data.c : implement the packed binary stream data structure
 *
 * ====================================================================
 *    Licensed to the Apache Software Foundation (ASF) under one
 *    or more contributor license agreements.  See the NOTICE file
 *    distributed with this work for additional information
 *    regarding copyright ownership.  The ASF licenses this file
 *    to you under the Apache License, Version 2.0 (the
 *    "License"); you may not use this file except in compliance
 *    with the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *    Unless required by applicable law or agreed to in writing,
 *    software distributed under the License is distributed on an
 *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 *    KIND, either express or implied.  See the License for the
 *    specific language governing permissions and limitations
 *    under the License.
 * ====================================================================
 */

#include <apr_tables.h>

#include "svn_string.h"
#include "svn_sorts.h"
#include "private/svn_string_private.h"
#include "private/svn_subr_private.h"
#include "private/svn_delta_private.h"
#include "private/svn_packed_data.h"

#include "svn_private_config.h"



/* Private int stream data referenced by svn_packed__int_stream_t.
 */
typedef struct packed_int_private_t
{
  /* First sub-stream, if any.  NULL otherwise. */
  svn_packed__int_stream_t *first_substream;

  /* Last sub-stream, if any.  NULL otherwise. */
  svn_packed__int_stream_t *last_substream;

  /* Current sub-stream to read from / write to, if any.  NULL otherwise.
     This will be initialized to FIRST_SUBSTREAM and then advanced in a
     round-robin scheme after each number being read. */
  svn_packed__int_stream_t *current_substream;

  /* Number of sub-streams. */
  apr_size_t substream_count;

  /* Next (sibling) integer stream.  If this is the last one, points to
     the first in the list (i.e. this forms a ring list).  Never NULL. */
  svn_packed__int_stream_t *next;

  /* 7b/8b encoded integer values (previously diff'ed and sign-handled,
     if indicated by the flags below).  The contents are disjoint from
     the unparsed number buffer.  May be NULL while not written to. */
  svn_stringbuf_t *packed;

  /* Initialized to 0.  Latest value written to / read from PACKED.
     Undefined if DIFF is FALSE. */
  apr_uint64_t last_value;

  /* Deltify data before storing it in PACKED. */
  svn_boolean_t diff;

  /* Numbers are likely to contain negative values with small absolutes.
     If TRUE, store the signed bit in LSB before encoding. */
  svn_boolean_t is_signed;

  /* Number of integers in this stream. */
  apr_size_t item_count;

  /* TRUE for the last stream in a list of siblings. */
  svn_boolean_t is_last;

  /* Pool to use for allocations. */
  apr_pool_t *pool;
} packed_int_private_t;

/* A byte sequence stream.  Please note that NEXT is defined different
 * from the NEXT member in integer streams.
 */
struct svn_packed__byte_stream_t
{
  /* First sub-stream, if any.  NULL otherwise. */
  svn_packed__byte_stream_t *first_substream;

  /* Last sub-stream, if any.  NULL otherwise. */
  svn_packed__byte_stream_t *last_substream;

  /* Next (sibling) byte sequence stream, if any.  NULL otherwise. */
  svn_packed__byte_stream_t *next;

  /* Stream to store the sequence lengths. */
  svn_packed__int_stream_t *lengths_stream;

  /* It's index (relative to its parent). */
  apr_size_t lengths_stream_index;

  /* Concatenated byte sequences. */
  svn_stringbuf_t *packed;

  /* Pool to use for allocations. */
  apr_pool_t *pool;
};

/* The serialization root object.  It references the top-level streams.
 */
struct svn_packed__data_root_t
{
  /* First top-level integer stream, if any.  NULL otherwise. */
  svn_packed__int_stream_t *first_int_stream;

  /* Last top-level integer stream, if any.  NULL otherwise. */
  svn_packed__int_stream_t *last_int_stream;

  /* Number of top-level integer streams. */
  apr_size_t int_stream_count;

  /* First top-level byte sequence stream, if any.  NULL otherwise. */
  svn_packed__byte_stream_t *first_byte_stream;

  /* Last top-level byte sequence stream, if any.  NULL otherwise. */
  svn_packed__byte_stream_t *last_byte_stream;

  /* Number of top-level byte sequence streams. */
  apr_size_t byte_stream_count;

  /* Pool to use for allocations. */
  apr_pool_t *pool;
};

/* Write access. */

svn_packed__data_root_t *
svn_packed__data_create_root(apr_pool_t *pool)
{
  svn_packed__data_root_t *root = apr_pcalloc(pool, sizeof(*root));
  root->pool = pool;

  return root;
}

svn_packed__int_stream_t *
svn_packed__create_int_stream(svn_packed__data_root_t *root,
                              svn_boolean_t diff,
                              svn_boolean_t signed_ints)
{
  /* allocate and initialize the stream node */
  packed_int_private_t *private_data
    = apr_pcalloc(root->pool, sizeof(*private_data));
  svn_packed__int_stream_t *stream
    = apr_palloc(root->pool, sizeof(*stream));

  private_data->diff = diff;
  private_data->is_signed = signed_ints;
  private_data->is_last = TRUE;
  private_data->pool = root->pool;

  stream->buffer_used = 0;
  stream->private_data = private_data;

  /* maintain the ring list */
  if (root->last_int_stream)
    {
      packed_int_private_t *previous_private_data
        = root->last_int_stream->private_data;
      previous_private_data->next = stream;
      previous_private_data->is_last = FALSE;
    }
  else
    {
      root->first_int_stream = stream;
    }

  root->last_int_stream = stream;
  root->int_stream_count++;

  return stream;
}

svn_packed__int_stream_t *
svn_packed__create_int_substream(svn_packed__int_stream_t *parent,
                                 svn_boolean_t diff,
                                 svn_boolean_t signed_ints)
{
  packed_int_private_t *parent_private = parent->private_data;

  /* allocate and initialize the stream node */
  packed_int_private_t *private_data
    = apr_pcalloc(parent_private->pool, sizeof(*private_data));
  svn_packed__int_stream_t *stream
    = apr_palloc(parent_private->pool, sizeof(*stream));

  private_data->diff = diff;
  private_data->is_signed = signed_ints;
  private_data->is_last = TRUE;
  private_data->pool = parent_private->pool;

  stream->buffer_used = 0;
  stream->private_data = private_data;

  /* maintain the ring list */
  if (parent_private->last_substream)
    {
      packed_int_private_t *previous_private_data
        = parent_private->last_substream->private_data;
      previous_private_data->next = stream;
      previous_private_data->is_last = FALSE;
    }
  else
    {
      parent_private->first_substream = stream;
      parent_private->current_substream = stream;
    }

  parent_private->last_substream = stream;
  parent_private->substream_count++;
  private_data->next = parent_private->first_substream;

  return stream;
}

/* Returns a new top-level byte sequence stream for ROOT but does not
 * initialize the LENGTH_STREAM member.
 */
static svn_packed__byte_stream_t *
create_bytes_stream_body(svn_packed__data_root_t *root)
{
  svn_packed__byte_stream_t *stream
    = apr_pcalloc(root->pool, sizeof(*stream));

  stream->packed = svn_stringbuf_create_empty(root->pool);

  if (root->last_byte_stream)
    root->last_byte_stream->next = stream;
  else
    root->first_byte_stream = stream;

  root->last_byte_stream = stream;
  root->byte_stream_count++;

  return stream;
}

svn_packed__byte_stream_t *
svn_packed__create_bytes_stream(svn_packed__data_root_t *root)
{
  svn_packed__byte_stream_t *stream
    = create_bytes_stream_body(root);

  stream->lengths_stream_index = root->int_stream_count;
  stream->lengths_stream = svn_packed__create_int_stream(root, FALSE, FALSE);

  return stream;
}

/* Write the 7b/8b representation of VALUE into BUFFER.  BUFFER must
 * provide at least 10 bytes space.
 * Returns the first position behind the written data.
 */
static unsigned char *
write_packed_uint_body(unsigned char *buffer, apr_uint64_t value)
{
  while (value >= 0x80)
    {
      *(buffer++) = (unsigned char)((value % 0x80) + 0x80);
      value /= 0x80;
    }

  *(buffer++) = (unsigned char)value;
  return buffer;
}

/* Return remapped VALUE.
 *
 * Due to sign conversion and diff underflow, values close to UINT64_MAX
 * are almost as frequent as those close to 0.  Remap them such that the
 * MSB is stored in the LSB and the remainder stores the absolute distance
 * to 0.
 *
 * This minimizes the absolute value to store in many scenarios.
 * Hence, the variable-length representation on disk is shorter, too.
 */
static apr_uint64_t
remap_uint(apr_uint64_t value)
{
  return value & APR_UINT64_C(0x8000000000000000)
       ? APR_UINT64_MAX - (2 * value)
       : 2 * value;
}

/* Invert remap_uint. */
static apr_uint64_t
unmap_uint(apr_uint64_t value)
{
  return value & 1
       ? (APR_UINT64_MAX - value / 2)
       : value / 2;
}

/* Empty the unprocessed integer buffer in STREAM by either pushing the
 * data to the sub-streams or writing to the packed data (in case there
 * are no sub-streams).
 */
static void
svn_packed__data_flush_buffer(svn_packed__int_stream_t *stream)
{
  packed_int_private_t *private_data = stream->private_data;
  apr_size_t i;

  /* if we have sub-streams, push the data down to them */
  if (private_data->current_substream)
    for (i = 0; i < stream->buffer_used; ++i)
      {
        packed_int_private_t *current_private_data
          = private_data->current_substream->private_data;

        svn_packed__add_uint(private_data->current_substream,
                             stream->buffer[i]);
        private_data->current_substream = current_private_data->next;
      }
  else
    {
      /* pack the numbers into our local PACKED buffer */

      /* temporary buffer, max 10 bytes required per 7b/8b encoded number */
      unsigned char local_buffer[10 * SVN__PACKED_DATA_BUFFER_SIZE];
      unsigned char *p = local_buffer;

      /* if configured, deltify numbers before packing them.
         Since delta may be negative, always use the 'signed' encoding. */
      if (private_data->diff)
        {
          apr_uint64_t last_value = private_data->last_value;
          for (i = 0; i < stream->buffer_used; ++i)
            {
              apr_uint64_t temp = stream->buffer[i];
              stream->buffer[i] = remap_uint(temp - last_value);
              last_value = temp;
            }

          private_data->last_value = last_value;
        }

      /* if configured and not already done by the deltification above,
         transform to 'signed' encoding.  Store the sign in the LSB and
         the absolute value (-1 for negative values) in the remaining
         63 bits. */
      if (!private_data->diff && private_data->is_signed)
        for (i = 0; i < stream->buffer_used; ++i)
          stream->buffer[i] = remap_uint(stream->buffer[i]);

      /* auto-create packed data buffer.  Give it some reasonable initial
         size - just enough for a few tens of values. */
      if (private_data->packed == NULL)
        private_data->packed
          = svn_stringbuf_create_ensure(256, private_data->pool);

      /* encode numbers into our temp buffer. */
      for (i = 0; i < stream->buffer_used; ++i)
        p = write_packed_uint_body(p, stream->buffer[i]);

      /* append them to the final packed data */
      svn_stringbuf_appendbytes(private_data->packed,
                                (char *)local_buffer,
                                p - local_buffer);
    }

  /* maintain counters */
  private_data->item_count += stream->buffer_used;
  stream->buffer_used = 0;
}

void
svn_packed__add_uint(svn_packed__int_stream_t *stream,
                     apr_uint64_t value)
{
  stream->buffer[stream->buffer_used] = value;
  if (++stream->buffer_used == SVN__PACKED_DATA_BUFFER_SIZE)
    svn_packed__data_flush_buffer(stream);
}

void
svn_packed__add_int(svn_packed__int_stream_t *stream,
                    apr_int64_t value)
{
  svn_packed__add_uint(stream, (apr_uint64_t)value);
}

void
svn_packed__add_bytes(svn_packed__byte_stream_t *stream,
                      const char *data,
                      apr_size_t len)
{
  svn_packed__add_uint(stream->lengths_stream, len);
  svn_stringbuf_appendbytes(stream->packed, data, len);
}

/* Append the 7b/8b encoded representation of VALUE to PACKED.
 */
static void
write_packed_uint(svn_stringbuf_t* packed, apr_uint64_t value)
{
  if (value < 0x80)
    {
      svn_stringbuf_appendbyte(packed, (char)value);
    }
  else
    {
      unsigned char buffer[10];
      unsigned char *p = write_packed_uint_body(buffer, value);

      svn_stringbuf_appendbytes(packed, (char *)buffer, p - buffer);
    }
}

/* Recursively write the structure (config parameters, sub-streams, data
 * sizes) of the STREAM and all its siblings to the TREE_STRUCT buffer.
 */
static void
write_int_stream_structure(svn_stringbuf_t* tree_struct,
                           svn_packed__int_stream_t* stream)
{
  while (stream)
    {
      /* store config parameters and number of sub-streams in 1 number */
      packed_int_private_t *private_data = stream->private_data;
      write_packed_uint(tree_struct, (private_data->substream_count << 2)
                                   + (private_data->diff ? 1 : 0)
                                   + (private_data->is_signed ? 2 : 0));

      /* store item count and length their of packed representation */
      svn_packed__data_flush_buffer(stream);

      write_packed_uint(tree_struct, private_data->item_count);
      write_packed_uint(tree_struct, private_data->packed
                                   ? private_data->packed->len
                                   : 0);

      /* append all sub-stream structures */
      write_int_stream_structure(tree_struct, private_data->first_substream);

      /* continue with next sibling */
      stream = private_data->is_last ? NULL : private_data->next;
    }
}

/* Recursively write the structure (sub-streams, data sizes) of the STREAM
 * and all its siblings to the TREE_STRUCT buffer.
 */
static void
write_byte_stream_structure(svn_stringbuf_t* tree_struct,
                            svn_packed__byte_stream_t* stream)
{
  /* for this and all siblings */
  for (; stream; stream = stream->next)
    {
      /* this stream's structure and size */
      write_packed_uint(tree_struct, 0);
      write_packed_uint(tree_struct, stream->lengths_stream_index);
      write_packed_uint(tree_struct, stream->packed->len);

      /* followed by all its sub-streams */
      write_byte_stream_structure(tree_struct, stream->first_substream);
    }
}

/* Write the 7b/8b encoded representation of VALUE to STREAM.
 */
static svn_error_t *
write_stream_uint(svn_stream_t *stream,
                  apr_uint64_t value)
{
  unsigned char buffer[10];
  apr_size_t count = write_packed_uint_body(buffer, value) - buffer;

  SVN_ERR(svn_stream_write(stream, (char *)buffer, &count));

  return SVN_NO_ERROR;
}

/* Return the total size of all packed data in STREAM, its siblings and
 * all sub-streams.  To get an accurate value, flush all buffers prior to
 * calling this function.
 */
static apr_size_t
packed_int_stream_length(svn_packed__int_stream_t *stream)
{
  packed_int_private_t *private_data = stream->private_data;
  apr_size_t result = private_data->packed ? private_data->packed->len : 0;

  stream = private_data->first_substream;
  while (stream)
    {
      private_data = stream->private_data;
      result += packed_int_stream_length(stream);
      stream = private_data->is_last ? NULL : private_data->next;
    }

  return result;
}

/* Return the total size of all byte sequences data in STREAM, its siblings
 * and all sub-streams.
 */
static apr_size_t
packed_byte_stream_length(svn_packed__byte_stream_t *stream)
{
  apr_size_t result = stream->packed->len;

  for (stream = stream->first_substream; stream; stream = stream->next)
    result += packed_byte_stream_length(stream);

  return result;
}

/* Append all packed data in STREAM, its siblings and all sub-streams to
 * COMBINED.
 */
static void
append_int_stream(svn_packed__int_stream_t *stream,
                  svn_stringbuf_t *combined)
{
  packed_int_private_t *private_data = stream->private_data;
  if (private_data->packed)
    svn_stringbuf_appendstr(combined, private_data->packed);

  stream = private_data->first_substream;
  while (stream)
    {
      private_data = stream->private_data;
      append_int_stream(stream, combined);
      stream = private_data->is_last ? NULL : private_data->next;
    }
}

/* Append all byte sequences in STREAM, its siblings and all sub-streams
 * to COMBINED.
 */
static void
append_byte_stream(svn_packed__byte_stream_t *stream,
                   svn_stringbuf_t *combined)
{
  svn_stringbuf_appendstr(combined, stream->packed);

  for (stream = stream->first_substream; stream; stream = stream->next)
    append_byte_stream(stream, combined);
}

/* Take the binary data in UNCOMPRESSED, zip it into COMPRESSED and write
 * it to STREAM.  COMPRESSED simply acts as a re-usable memory buffer.
 * Clear all buffers (COMPRESSED, UNCOMPRESSED) at the end of the function.
 */
static svn_error_t *
write_stream_data(svn_stream_t *stream,
                  svn_stringbuf_t *uncompressed,
                  svn_stringbuf_t *compressed)
{
  SVN_ERR(svn__compress(uncompressed,
                        compressed,
                        SVN_DELTA_COMPRESSION_LEVEL_DEFAULT));

  SVN_ERR(write_stream_uint(stream, compressed->len));
  SVN_ERR(svn_stream_write(stream, compressed->data, &compressed->len));

  svn_stringbuf_setempty(uncompressed);
  svn_stringbuf_setempty(compressed);

  return SVN_NO_ERROR;
}

svn_error_t *
svn_packed__data_write(svn_stream_t *stream,
                       svn_packed__data_root_t *root,
                       apr_pool_t *scratch_pool)
{
  svn_packed__int_stream_t *int_stream;
  svn_packed__byte_stream_t *byte_stream;

  /* re-usable data buffers */
  svn_stringbuf_t *compressed
    = svn_stringbuf_create_ensure(1024, scratch_pool);
  svn_stringbuf_t *uncompressed
    = svn_stringbuf_create_ensure(1024, scratch_pool);

  /* write tree structure */
  svn_stringbuf_t *tree_struct
    = svn_stringbuf_create_ensure(127, scratch_pool);

  write_packed_uint(tree_struct, root->int_stream_count);
  write_int_stream_structure(tree_struct, root->first_int_stream);

  write_packed_uint(tree_struct, root->byte_stream_count);
  write_byte_stream_structure(tree_struct, root->first_byte_stream);

  SVN_ERR(write_stream_uint(stream, tree_struct->len));
  SVN_ERR(svn_stream_write(stream, tree_struct->data, &tree_struct->len));

  /* flatten sub-streams, zip them and write them to disk */

  for (int_stream = root->first_int_stream;
       int_stream;
       int_stream = ((packed_int_private_t*)int_stream->private_data)->next)
    {
      apr_size_t len = packed_int_stream_length(int_stream);
      svn_stringbuf_ensure(uncompressed, len);

      append_int_stream(int_stream, uncompressed);
      SVN_ERR(write_stream_data(stream, uncompressed, compressed));
    }

  for (byte_stream = root->first_byte_stream;
       byte_stream;
       byte_stream = byte_stream->next)
    {
      apr_size_t len = packed_byte_stream_length(byte_stream);
      svn_stringbuf_ensure(uncompressed, len);

      append_byte_stream(byte_stream, uncompressed);
      SVN_ERR(write_stream_data(stream, uncompressed, compressed));
    }

  return SVN_NO_ERROR;
}


/* Read access. */

svn_packed__int_stream_t *
svn_packed__first_int_stream(svn_packed__data_root_t *root)
{
  return root->first_int_stream;
}

svn_packed__byte_stream_t *
svn_packed__first_byte_stream(svn_packed__data_root_t *root)
{
  return root->first_byte_stream;
}

svn_packed__int_stream_t *
svn_packed__next_int_stream(svn_packed__int_stream_t *stream)
{
  packed_int_private_t *private_data = stream->private_data;
  return private_data->is_last ? NULL : private_data->next;
}

svn_packed__byte_stream_t *
svn_packed__next_byte_stream(svn_packed__byte_stream_t *stream)
{
  return stream->next;
}

svn_packed__int_stream_t *
svn_packed__first_int_substream(svn_packed__int_stream_t *stream)
{
  packed_int_private_t *private_data = stream->private_data;
  return private_data->first_substream;
}

apr_size_t
svn_packed__int_count(svn_packed__int_stream_t *stream)
{
  packed_int_private_t *private_data = stream->private_data;
  return private_data->item_count + stream->buffer_used;
}

apr_size_t
svn_packed__byte_count(svn_packed__byte_stream_t *stream)
{
  return stream->packed->len;
}

/* Read one 7b/8b encoded value from *P and return it in *RESULT.  Returns
 * the first position after the parsed data.
 *
 * Overflows will be detected in the sense that it will end parsing the
 * input but the result is undefined.
 */
static unsigned char *
read_packed_uint_body(unsigned char *p, apr_uint64_t *result)
{
  if (*p < 0x80)
    {
      *result = *p;
    }
  else
    {
      apr_uint64_t shift = 0;
      apr_uint64_t value = 0;
      while (*p >= 0x80)
        {
          value += (apr_uint64_t)(*p & 0x7f) << shift;
          ++p;

          shift += 7;
          if (shift > 64)
            {
              /* a definite overflow.  Note, that numbers of 65 .. 70
                 bits will not be detected as an overflow as they don't
                 threaten to exceed the input buffer. */
              *result = 0;
              return p;
            }
        }

      *result = value + ((apr_uint64_t)*p << shift);
    }

  return ++p;
}

/* Read one 7b/8b encoded value from STREAM and return it in *RESULT.
 *
 * Overflows will be detected in the sense that it will end parsing the
 * input but the result is undefined.
 */
static svn_error_t *
read_stream_uint(svn_stream_t *stream, apr_uint64_t *result)
{
  apr_uint64_t shift = 0;
  apr_uint64_t value = 0;
  unsigned char c;

  do
    {
      apr_size_t len = 1;
      SVN_ERR(svn_stream_read_full(stream, (char *)&c, &len));
      if (len != 1)
        return svn_error_create(SVN_ERR_CORRUPT_PACKED_DATA, NULL,
                                _("Unexpected end of stream"));

      value += (apr_uint64_t)(c & 0x7f) << shift;
      shift += 7;
      if (shift > 64)
        return svn_error_create(SVN_ERR_CORRUPT_PACKED_DATA, NULL,
                                _("Integer representation too long"));
    }
  while (c >= 0x80);

  *result = value;
  return SVN_NO_ERROR;
}

/* Extract and return the next integer from PACKED and make PACKED point
 * to the next integer.
 */
static apr_uint64_t
read_packed_uint(svn_stringbuf_t *packed)
{
  apr_uint64_t result = 0;
  unsigned char *p = (unsigned char *)packed->data;
  apr_size_t read = read_packed_uint_body(p, &result) - p;

  if (read > packed->len)
    read = packed->len;

  packed->data += read;
  packed->blocksize -= read;
  packed->len -= read;

  return result;
}

/* Ensure that STREAM contains at least one item in its buffer.
 */
static void
svn_packed__data_fill_buffer(svn_packed__int_stream_t *stream)
{
  packed_int_private_t *private_data = stream->private_data;
  apr_size_t i;
  apr_size_t end = MIN(SVN__PACKED_DATA_BUFFER_SIZE,
                       private_data->item_count);

  /* in case, some user calls us explicitly without a good reason ... */
  if (stream->buffer_used)
    return;

  /* can we get data from the sub-streams or do we have to decode it from
     our local packed container? */
  if (private_data->current_substream)
    for (i = end; i > 0; --i)
      {
        packed_int_private_t *current_private_data
          = private_data->current_substream->private_data;
        stream->buffer[i-1]
          = svn_packed__get_uint(private_data->current_substream);
        private_data->current_substream = current_private_data->next;
      }
  else
    {
      /* use this local buffer only if the packed data is shorter than this.
         The goal is that read_packed_uint_body doesn't need check for
         overflows. */
      unsigned char local_buffer[10 * SVN__PACKED_DATA_BUFFER_SIZE];
      unsigned char *p;
      unsigned char *start;
      apr_size_t packed_read;

      if (private_data->packed->len < sizeof(local_buffer))
        {
          apr_size_t trail = sizeof(local_buffer) - private_data->packed->len;
          memcpy(local_buffer,
                 private_data->packed->data,
                 private_data->packed->len);
          memset(local_buffer + private_data->packed->len, 0, MIN(trail, end));

          p = local_buffer;
        }
      else
        p = (unsigned char *)private_data->packed->data;

      /* unpack numbers */
      start = p;
      for (i = end; i > 0; --i)
        p = read_packed_uint_body(p, &stream->buffer[i-1]);

      /* adjust remaining packed data buffer */
      packed_read = p - start;
      private_data->packed->data += packed_read;
      private_data->packed->len -= packed_read;
      private_data->packed->blocksize -= packed_read;

      /* undeltify numbers, if configured */
      if (private_data->diff)
        {
          apr_uint64_t last_value = private_data->last_value;
          for (i = end; i > 0; --i)
            {
              last_value += unmap_uint(stream->buffer[i-1]);
              stream->buffer[i-1] = last_value;
            }

          private_data->last_value = last_value;
        }

      /* handle signed values, if configured and not handled already */
      if (!private_data->diff && private_data->is_signed)
        for (i = 0; i < end; ++i)
          stream->buffer[i] = unmap_uint(stream->buffer[i]);
    }

  stream->buffer_used = end;
  private_data->item_count -= end;
}

apr_uint64_t
svn_packed__get_uint(svn_packed__int_stream_t *stream)
{
  if (stream->buffer_used == 0)
    svn_packed__data_fill_buffer(stream);

  return stream->buffer_used ? stream->buffer[--stream->buffer_used] : 0;
}

apr_int64_t
svn_packed__get_int(svn_packed__int_stream_t *stream)
{
  return (apr_int64_t)svn_packed__get_uint(stream);
}

const char *
svn_packed__get_bytes(svn_packed__byte_stream_t *stream,
                      apr_size_t *len)
{
  const char *result = stream->packed->data;
  apr_size_t count = (apr_size_t)svn_packed__get_uint(stream->lengths_stream);

  if (count > stream->packed->len)
    count = stream->packed->len;

  /* advance packed buffer */
  stream->packed->data += count;
  stream->packed->len -= count;
  stream->packed->blocksize -= count;

  *len = count;
  return result;
}

/* Read the integer stream structure and recreate it in STREAM, including
 * sub-streams, from TREE_STRUCT.
 */
static void
read_int_stream_structure(svn_stringbuf_t *tree_struct,
                          svn_packed__int_stream_t *stream)
{
  packed_int_private_t *private_data = stream->private_data;
  apr_uint64_t value = read_packed_uint(tree_struct);
  apr_size_t substream_count;
  apr_size_t i;

  /* extract local parameters */
  private_data->diff = (value & 1) != 0;
  private_data->is_signed = (value & 2) != 0;
  substream_count = (apr_size_t)(value >> 2);

  /* read item count & packed size; allocate packed data buffer */
  private_data->item_count = (apr_size_t)read_packed_uint(tree_struct);
  value = read_packed_uint(tree_struct);
  if (value)
    {
      private_data->packed = svn_stringbuf_create_ensure((apr_size_t)value,
                                                         private_data->pool);
      private_data->packed->len = (apr_size_t)value;
    }

  /* add sub-streams and read their config, too */
  for (i = 0; i < substream_count; ++i)
    read_int_stream_structure(tree_struct,
                              svn_packed__create_int_substream(stream,
                                                               FALSE,
                                                               FALSE));
}

/* Read the integer stream structure and recreate it in STREAM, including
 * sub-streams, from TREE_STRUCT.  FIRST_INT_STREAM is the integer stream
 * that would correspond to lengths_stream_index 0.
 */
static void
read_byte_stream_structure(svn_stringbuf_t *tree_struct,
                           svn_packed__byte_stream_t *stream,
                           svn_packed__int_stream_t *first_int_stream)
{
  apr_size_t lengths_stream_index;
  apr_size_t packed_size;
  apr_size_t i;

  /* read parameters from the TREE_STRUCT buffer */
  (void) (apr_size_t)read_packed_uint(tree_struct); /* discard first uint */
  lengths_stream_index = (apr_size_t)read_packed_uint(tree_struct);
  packed_size = (apr_size_t)read_packed_uint(tree_struct);

  /* allocate byte sequence buffer size */
  svn_stringbuf_ensure(stream->packed, packed_size);
  stream->packed->len = packed_size;

  /* navigate to the (already existing) lengths_stream */
  stream->lengths_stream_index = lengths_stream_index;
  stream->lengths_stream = first_int_stream;
  for (i = 0; i < lengths_stream_index; ++i)
    {
      packed_int_private_t *length_private
        = stream->lengths_stream->private_data;
      stream->lengths_stream = length_private->next;
    }
}

/* Read a compressed block from STREAM and uncompress it into UNCOMPRESSED.
 * UNCOMPRESSED_LEN is the expected size of the stream.  COMPRESSED is a
 * re-used buffer for temporary data.
 */
static svn_error_t *
read_stream_data(svn_stream_t *stream,
                 apr_size_t uncompressed_len,
                 svn_stringbuf_t *uncompressed,
                 svn_stringbuf_t *compressed)
{
  apr_uint64_t len;
  apr_size_t compressed_len;

  SVN_ERR(read_stream_uint(stream, &len));
  compressed_len = (apr_size_t)len;

  svn_stringbuf_ensure(compressed, compressed_len);
  compressed->len = compressed_len;
  SVN_ERR(svn_stream_read_full(stream, compressed->data, &compressed->len));
  compressed->data[compressed_len] = '\0';

  SVN_ERR(svn__decompress(compressed, uncompressed, uncompressed_len));

  return SVN_NO_ERROR;
}

/* Read the packed contents from COMBINED, starting at *OFFSET and store
 * it in STREAM.  Update *OFFSET to point to the next stream's data and
 * continue with the sub-streams.
 */
static void
unflatten_int_stream(svn_packed__int_stream_t *stream,
                     svn_stringbuf_t *combined,
                     apr_size_t *offset)
{
  packed_int_private_t *private_data = stream->private_data;
  if (private_data->packed)
    {
      memcpy(private_data->packed->data,
             combined->data + *offset,
             private_data->packed->len);

      private_data->packed->data[private_data->packed->len] = '\0';
      *offset += private_data->packed->len;
    }

  stream = private_data->first_substream;
  while (stream)
    {
      private_data = stream->private_data;
      unflatten_int_stream(stream, combined, offset);
      stream = private_data->is_last ? NULL : private_data->next;
    }
}

/* Read the packed contents from COMBINED, starting at *OFFSET and store
 * it in STREAM.  Update *OFFSET to point to the next stream's data and
 * continue with the sub-streams.
 */
static void
unflatten_byte_stream(svn_packed__byte_stream_t *stream,
                      svn_stringbuf_t *combined,
                      apr_size_t *offset)
{
  memcpy(stream->packed->data,
         combined->data + *offset,
         stream->packed->len);
  stream->packed->data[stream->packed->len] = '\0';

  *offset += stream->packed->len;
  for (stream = stream->first_substream; stream; stream = stream->next)
    unflatten_byte_stream(stream, combined, offset);
}

svn_error_t *
svn_packed__data_read(svn_packed__data_root_t **root_p,
                      svn_stream_t *stream,
                      apr_pool_t *result_pool,
                      apr_pool_t *scratch_pool)
{
  apr_uint64_t i;
  apr_uint64_t count;

  svn_packed__int_stream_t *int_stream;
  svn_packed__byte_stream_t *byte_stream;
  svn_packed__data_root_t *root = svn_packed__data_create_root(result_pool);

  svn_stringbuf_t *compressed
    = svn_stringbuf_create_ensure(1024, scratch_pool);
  svn_stringbuf_t *uncompressed
    = svn_stringbuf_create_ensure(1024, scratch_pool);

  /* read tree structure */

  apr_uint64_t tree_struct_size;
  svn_stringbuf_t *tree_struct;

  SVN_ERR(read_stream_uint(stream, &tree_struct_size));
  tree_struct
    = svn_stringbuf_create_ensure((apr_size_t)tree_struct_size, scratch_pool);
  tree_struct->len = (apr_size_t)tree_struct_size;

  SVN_ERR(svn_stream_read_full(stream, tree_struct->data, &tree_struct->len));
  tree_struct->data[tree_struct->len] = '\0';

  /* reconstruct tree structure */

  count = read_packed_uint(tree_struct);
  for (i = 0; i < count; ++i)
    read_int_stream_structure(tree_struct,
                              svn_packed__create_int_stream(root, FALSE,
                                                                 FALSE));

  count = read_packed_uint(tree_struct);
  for (i = 0; i < count; ++i)
    read_byte_stream_structure(tree_struct,
                               create_bytes_stream_body(root),
                               root->first_int_stream);

  /* read sub-stream data from disk, unzip it and buffer it */

  for (int_stream = root->first_int_stream;
       int_stream;
       int_stream = ((packed_int_private_t*)int_stream->private_data)->next)
    {
      apr_size_t offset = 0;
      SVN_ERR(read_stream_data(stream,
                               packed_int_stream_length(int_stream),
                               uncompressed, compressed));
      unflatten_int_stream(int_stream, uncompressed, &offset);
    }

  for (byte_stream = root->first_byte_stream;
       byte_stream;
       byte_stream = byte_stream->next)
    {
      apr_size_t offset = 0;
      SVN_ERR(read_stream_data(stream,
                               packed_byte_stream_length(byte_stream),
                               uncompressed, compressed));
      unflatten_byte_stream(byte_stream, uncompressed, &offset);
    }

  *root_p = root;
  return SVN_NO_ERROR;
}