diff options
Diffstat (limited to 'subversion/libsvn_subr/packed_data.c')
| -rw-r--r-- | subversion/libsvn_subr/packed_data.c | 1099 |
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; +} |