subversion-1.9.7HEADsubversion-1.9.7master

1 files changed, 1099 insertions, 0 deletions

diff --git a/subversion/libsvn_subr/packed_data.c b/subversion/libsvn_subr/packed_data.c
new file mode 100644
index 0000000..27651ff
--- /dev/null
+++ b/subversion/libsvn_subr/packed_data.c
@@ -0,0 +1,1099 @@
+/* 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;
+}