1 /* packed_data.c : implement the packed binary stream data structure
3 * ====================================================================
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
12 * http://www.apache.org/licenses/LICENSE-2.0
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
20 * ====================================================================
23 #include <apr_tables.h>
25 #include "svn_string.h"
26 #include "svn_sorts.h"
27 #include "private/svn_string_private.h"
28 #include "private/svn_subr_private.h"
29 #include "private/svn_delta_private.h"
30 #include "private/svn_packed_data.h"
32 #include "svn_private_config.h"
36 /* Private int stream data referenced by svn_packed__int_stream_t.
38 typedef struct packed_int_private_t
40 /* First sub-stream, if any. NULL otherwise. */
41 svn_packed__int_stream_t *first_substream;
43 /* Last sub-stream, if any. NULL otherwise. */
44 svn_packed__int_stream_t *last_substream;
46 /* Current sub-stream to read from / write to, if any. NULL otherwise.
47 This will be initialized to FIRST_SUBSTREAM and then advanced in a
48 round-robin scheme after each number being read. */
49 svn_packed__int_stream_t *current_substream;
51 /* Number of sub-streams. */
52 apr_size_t substream_count;
54 /* Next (sibling) integer stream. If this is the last one, points to
55 the first in the list (i.e. this forms a ring list). Never NULL. */
56 svn_packed__int_stream_t *next;
58 /* 7b/8b encoded integer values (previously diff'ed and sign-handled,
59 if indicated by the flags below). The contents are disjoint from
60 the unparsed number buffer. May be NULL while not written to. */
61 svn_stringbuf_t *packed;
63 /* Initialized to 0. Latest value written to / read from PACKED.
64 Undefined if DIFF is FALSE. */
65 apr_uint64_t last_value;
67 /* Deltify data before storing it in PACKED. */
70 /* Numbers are likely to contain negative values with small absolutes.
71 If TRUE, store the signed bit in LSB before encoding. */
72 svn_boolean_t is_signed;
74 /* Number of integers in this stream. */
75 apr_size_t item_count;
77 /* TRUE for the last stream in a list of siblings. */
78 svn_boolean_t is_last;
80 /* Pool to use for allocations. */
82 } packed_int_private_t;
84 /* A byte sequence stream. Please note that NEXT is defined different
85 * from the NEXT member in integer streams.
87 struct svn_packed__byte_stream_t
89 /* First sub-stream, if any. NULL otherwise. */
90 svn_packed__byte_stream_t *first_substream;
92 /* Last sub-stream, if any. NULL otherwise. */
93 svn_packed__byte_stream_t *last_substream;
95 /* Next (sibling) byte sequence stream, if any. NULL otherwise. */
96 svn_packed__byte_stream_t *next;
98 /* Stream to store the sequence lengths. */
99 svn_packed__int_stream_t *lengths_stream;
101 /* It's index (relative to its parent). */
102 apr_size_t lengths_stream_index;
104 /* Concatenated byte sequences. */
105 svn_stringbuf_t *packed;
107 /* Pool to use for allocations. */
111 /* The serialization root object. It references the top-level streams.
113 struct svn_packed__data_root_t
115 /* First top-level integer stream, if any. NULL otherwise. */
116 svn_packed__int_stream_t *first_int_stream;
118 /* Last top-level integer stream, if any. NULL otherwise. */
119 svn_packed__int_stream_t *last_int_stream;
121 /* Number of top-level integer streams. */
122 apr_size_t int_stream_count;
124 /* First top-level byte sequence stream, if any. NULL otherwise. */
125 svn_packed__byte_stream_t *first_byte_stream;
127 /* Last top-level byte sequence stream, if any. NULL otherwise. */
128 svn_packed__byte_stream_t *last_byte_stream;
130 /* Number of top-level byte sequence streams. */
131 apr_size_t byte_stream_count;
133 /* Pool to use for allocations. */
139 svn_packed__data_root_t *
140 svn_packed__data_create_root(apr_pool_t *pool)
142 svn_packed__data_root_t *root = apr_pcalloc(pool, sizeof(*root));
148 svn_packed__int_stream_t *
149 svn_packed__create_int_stream(svn_packed__data_root_t *root,
151 svn_boolean_t signed_ints)
153 /* allocate and initialize the stream node */
154 packed_int_private_t *private_data
155 = apr_pcalloc(root->pool, sizeof(*private_data));
156 svn_packed__int_stream_t *stream
157 = apr_palloc(root->pool, sizeof(*stream));
159 private_data->diff = diff;
160 private_data->is_signed = signed_ints;
161 private_data->is_last = TRUE;
162 private_data->pool = root->pool;
164 stream->buffer_used = 0;
165 stream->private_data = private_data;
167 /* maintain the ring list */
168 if (root->last_int_stream)
170 packed_int_private_t *previous_private_data
171 = root->last_int_stream->private_data;
172 previous_private_data->next = stream;
173 previous_private_data->is_last = FALSE;
177 root->first_int_stream = stream;
180 root->last_int_stream = stream;
181 root->int_stream_count++;
186 svn_packed__int_stream_t *
187 svn_packed__create_int_substream(svn_packed__int_stream_t *parent,
189 svn_boolean_t signed_ints)
191 packed_int_private_t *parent_private = parent->private_data;
193 /* allocate and initialize the stream node */
194 packed_int_private_t *private_data
195 = apr_pcalloc(parent_private->pool, sizeof(*private_data));
196 svn_packed__int_stream_t *stream
197 = apr_palloc(parent_private->pool, sizeof(*stream));
199 private_data->diff = diff;
200 private_data->is_signed = signed_ints;
201 private_data->is_last = TRUE;
202 private_data->pool = parent_private->pool;
204 stream->buffer_used = 0;
205 stream->private_data = private_data;
207 /* maintain the ring list */
208 if (parent_private->last_substream)
210 packed_int_private_t *previous_private_data
211 = parent_private->last_substream->private_data;
212 previous_private_data->next = stream;
213 previous_private_data->is_last = FALSE;
217 parent_private->first_substream = stream;
218 parent_private->current_substream = stream;
221 parent_private->last_substream = stream;
222 parent_private->substream_count++;
223 private_data->next = parent_private->first_substream;
228 /* Returns a new top-level byte sequence stream for ROOT but does not
229 * initialize the LENGTH_STREAM member.
231 static svn_packed__byte_stream_t *
232 create_bytes_stream_body(svn_packed__data_root_t *root)
234 svn_packed__byte_stream_t *stream
235 = apr_pcalloc(root->pool, sizeof(*stream));
237 stream->packed = svn_stringbuf_create_empty(root->pool);
239 if (root->last_byte_stream)
240 root->last_byte_stream->next = stream;
242 root->first_byte_stream = stream;
244 root->last_byte_stream = stream;
245 root->byte_stream_count++;
250 svn_packed__byte_stream_t *
251 svn_packed__create_bytes_stream(svn_packed__data_root_t *root)
253 svn_packed__byte_stream_t *stream
254 = create_bytes_stream_body(root);
256 stream->lengths_stream_index = root->int_stream_count;
257 stream->lengths_stream = svn_packed__create_int_stream(root, FALSE, FALSE);
262 /* Write the 7b/8b representation of VALUE into BUFFER. BUFFER must
263 * provide at least 10 bytes space.
264 * Returns the first position behind the written data.
266 static unsigned char *
267 write_packed_uint_body(unsigned char *buffer, apr_uint64_t value)
269 while (value >= 0x80)
271 *(buffer++) = (unsigned char)((value % 0x80) + 0x80);
275 *(buffer++) = (unsigned char)value;
279 /* Return remapped VALUE.
281 * Due to sign conversion and diff underflow, values close to UINT64_MAX
282 * are almost as frequent as those close to 0. Remap them such that the
283 * MSB is stored in the LSB and the remainder stores the absolute distance
286 * This minimizes the absolute value to store in many scenarios.
287 * Hence, the variable-length representation on disk is shorter, too.
290 remap_uint(apr_uint64_t value)
292 return value & APR_UINT64_C(0x8000000000000000)
293 ? APR_UINT64_MAX - (2 * value)
297 /* Invert remap_uint. */
299 unmap_uint(apr_uint64_t value)
302 ? (APR_UINT64_MAX - value / 2)
306 /* Empty the unprocessed integer buffer in STREAM by either pushing the
307 * data to the sub-streams or writing to the packed data (in case there
308 * are no sub-streams).
311 data_flush_buffer(svn_packed__int_stream_t *stream)
313 packed_int_private_t *private_data = stream->private_data;
316 /* if we have sub-streams, push the data down to them */
317 if (private_data->current_substream)
318 for (i = 0; i < stream->buffer_used; ++i)
320 packed_int_private_t *current_private_data
321 = private_data->current_substream->private_data;
323 svn_packed__add_uint(private_data->current_substream,
325 private_data->current_substream = current_private_data->next;
329 /* pack the numbers into our local PACKED buffer */
331 /* temporary buffer, max 10 bytes required per 7b/8b encoded number */
332 unsigned char local_buffer[10 * SVN__PACKED_DATA_BUFFER_SIZE];
333 unsigned char *p = local_buffer;
335 /* if configured, deltify numbers before packing them.
336 Since delta may be negative, always use the 'signed' encoding. */
337 if (private_data->diff)
339 apr_uint64_t last_value = private_data->last_value;
340 for (i = 0; i < stream->buffer_used; ++i)
342 apr_uint64_t temp = stream->buffer[i];
343 stream->buffer[i] = remap_uint(temp - last_value);
347 private_data->last_value = last_value;
350 /* if configured and not already done by the deltification above,
351 transform to 'signed' encoding. Store the sign in the LSB and
352 the absolute value (-1 for negative values) in the remaining
354 if (!private_data->diff && private_data->is_signed)
355 for (i = 0; i < stream->buffer_used; ++i)
356 stream->buffer[i] = remap_uint(stream->buffer[i]);
358 /* auto-create packed data buffer. Give it some reasonable initial
359 size - just enough for a few tens of values. */
360 if (private_data->packed == NULL)
362 = svn_stringbuf_create_ensure(256, private_data->pool);
364 /* encode numbers into our temp buffer. */
365 for (i = 0; i < stream->buffer_used; ++i)
366 p = write_packed_uint_body(p, stream->buffer[i]);
368 /* append them to the final packed data */
369 svn_stringbuf_appendbytes(private_data->packed,
370 (char *)local_buffer,
374 /* maintain counters */
375 private_data->item_count += stream->buffer_used;
376 stream->buffer_used = 0;
380 svn_packed__add_uint(svn_packed__int_stream_t *stream,
383 stream->buffer[stream->buffer_used] = value;
384 if (++stream->buffer_used == SVN__PACKED_DATA_BUFFER_SIZE)
385 data_flush_buffer(stream);
389 svn_packed__add_int(svn_packed__int_stream_t *stream,
392 svn_packed__add_uint(stream, (apr_uint64_t)value);
396 svn_packed__add_bytes(svn_packed__byte_stream_t *stream,
400 svn_packed__add_uint(stream->lengths_stream, len);
401 svn_stringbuf_appendbytes(stream->packed, data, len);
404 /* Append the 7b/8b encoded representation of VALUE to PACKED.
407 write_packed_uint(svn_stringbuf_t* packed, apr_uint64_t value)
411 svn_stringbuf_appendbyte(packed, (char)value);
415 unsigned char buffer[10];
416 unsigned char *p = write_packed_uint_body(buffer, value);
418 svn_stringbuf_appendbytes(packed, (char *)buffer, p - buffer);
422 /* Recursively write the structure (config parameters, sub-streams, data
423 * sizes) of the STREAM and all its siblings to the TREE_STRUCT buffer.
426 write_int_stream_structure(svn_stringbuf_t* tree_struct,
427 svn_packed__int_stream_t* stream)
431 /* store config parameters and number of sub-streams in 1 number */
432 packed_int_private_t *private_data = stream->private_data;
433 write_packed_uint(tree_struct, (private_data->substream_count << 2)
434 + (private_data->diff ? 1 : 0)
435 + (private_data->is_signed ? 2 : 0));
437 /* store item count and length their of packed representation */
438 data_flush_buffer(stream);
440 write_packed_uint(tree_struct, private_data->item_count);
441 write_packed_uint(tree_struct, private_data->packed
442 ? private_data->packed->len
445 /* append all sub-stream structures */
446 write_int_stream_structure(tree_struct, private_data->first_substream);
448 /* continue with next sibling */
449 stream = private_data->is_last ? NULL : private_data->next;
453 /* Recursively write the structure (sub-streams, data sizes) of the STREAM
454 * and all its siblings to the TREE_STRUCT buffer.
457 write_byte_stream_structure(svn_stringbuf_t* tree_struct,
458 svn_packed__byte_stream_t* stream)
460 /* for this and all siblings */
461 for (; stream; stream = stream->next)
463 /* this stream's structure and size */
464 write_packed_uint(tree_struct, 0);
465 write_packed_uint(tree_struct, stream->lengths_stream_index);
466 write_packed_uint(tree_struct, stream->packed->len);
468 /* followed by all its sub-streams */
469 write_byte_stream_structure(tree_struct, stream->first_substream);
473 /* Write the 7b/8b encoded representation of VALUE to STREAM.
476 write_stream_uint(svn_stream_t *stream,
479 unsigned char buffer[10];
480 apr_size_t count = write_packed_uint_body(buffer, value) - buffer;
482 SVN_ERR(svn_stream_write(stream, (char *)buffer, &count));
487 /* Return the total size of all packed data in STREAM, its siblings and
488 * all sub-streams. To get an accurate value, flush all buffers prior to
489 * calling this function.
492 packed_int_stream_length(svn_packed__int_stream_t *stream)
494 packed_int_private_t *private_data = stream->private_data;
495 apr_size_t result = private_data->packed ? private_data->packed->len : 0;
497 stream = private_data->first_substream;
500 private_data = stream->private_data;
501 result += packed_int_stream_length(stream);
502 stream = private_data->is_last ? NULL : private_data->next;
508 /* Return the total size of all byte sequences data in STREAM, its siblings
509 * and all sub-streams.
512 packed_byte_stream_length(svn_packed__byte_stream_t *stream)
514 apr_size_t result = stream->packed->len;
516 for (stream = stream->first_substream; stream; stream = stream->next)
517 result += packed_byte_stream_length(stream);
522 /* Append all packed data in STREAM, its siblings and all sub-streams to
526 append_int_stream(svn_packed__int_stream_t *stream,
527 svn_stringbuf_t *combined)
529 packed_int_private_t *private_data = stream->private_data;
530 if (private_data->packed)
531 svn_stringbuf_appendstr(combined, private_data->packed);
533 stream = private_data->first_substream;
536 private_data = stream->private_data;
537 append_int_stream(stream, combined);
538 stream = private_data->is_last ? NULL : private_data->next;
542 /* Append all byte sequences in STREAM, its siblings and all sub-streams
546 append_byte_stream(svn_packed__byte_stream_t *stream,
547 svn_stringbuf_t *combined)
549 svn_stringbuf_appendstr(combined, stream->packed);
551 for (stream = stream->first_substream; stream; stream = stream->next)
552 append_byte_stream(stream, combined);
555 /* Take the binary data in UNCOMPRESSED, zip it into COMPRESSED and write
556 * it to STREAM. COMPRESSED simply acts as a re-usable memory buffer.
557 * Clear all buffers (COMPRESSED, UNCOMPRESSED) at the end of the function.
560 write_stream_data(svn_stream_t *stream,
561 svn_stringbuf_t *uncompressed,
562 svn_stringbuf_t *compressed)
564 SVN_ERR(svn__compress_zlib(uncompressed->data, uncompressed->len,
566 SVN_DELTA_COMPRESSION_LEVEL_DEFAULT));
568 SVN_ERR(write_stream_uint(stream, compressed->len));
569 SVN_ERR(svn_stream_write(stream, compressed->data, &compressed->len));
571 svn_stringbuf_setempty(uncompressed);
572 svn_stringbuf_setempty(compressed);
578 svn_packed__data_write(svn_stream_t *stream,
579 svn_packed__data_root_t *root,
580 apr_pool_t *scratch_pool)
582 svn_packed__int_stream_t *int_stream;
583 svn_packed__byte_stream_t *byte_stream;
585 /* re-usable data buffers */
586 svn_stringbuf_t *compressed
587 = svn_stringbuf_create_ensure(1024, scratch_pool);
588 svn_stringbuf_t *uncompressed
589 = svn_stringbuf_create_ensure(1024, scratch_pool);
591 /* write tree structure */
592 svn_stringbuf_t *tree_struct
593 = svn_stringbuf_create_ensure(127, scratch_pool);
595 write_packed_uint(tree_struct, root->int_stream_count);
596 write_int_stream_structure(tree_struct, root->first_int_stream);
598 write_packed_uint(tree_struct, root->byte_stream_count);
599 write_byte_stream_structure(tree_struct, root->first_byte_stream);
601 SVN_ERR(write_stream_uint(stream, tree_struct->len));
602 SVN_ERR(svn_stream_write(stream, tree_struct->data, &tree_struct->len));
604 /* flatten sub-streams, zip them and write them to disk */
606 for (int_stream = root->first_int_stream;
608 int_stream = ((packed_int_private_t*)int_stream->private_data)->next)
610 apr_size_t len = packed_int_stream_length(int_stream);
611 svn_stringbuf_ensure(uncompressed, len);
613 append_int_stream(int_stream, uncompressed);
614 SVN_ERR(write_stream_data(stream, uncompressed, compressed));
617 for (byte_stream = root->first_byte_stream;
619 byte_stream = byte_stream->next)
621 apr_size_t len = packed_byte_stream_length(byte_stream);
622 svn_stringbuf_ensure(uncompressed, len);
624 append_byte_stream(byte_stream, uncompressed);
625 SVN_ERR(write_stream_data(stream, uncompressed, compressed));
634 svn_packed__int_stream_t *
635 svn_packed__first_int_stream(svn_packed__data_root_t *root)
637 return root->first_int_stream;
640 svn_packed__byte_stream_t *
641 svn_packed__first_byte_stream(svn_packed__data_root_t *root)
643 return root->first_byte_stream;
646 svn_packed__int_stream_t *
647 svn_packed__next_int_stream(svn_packed__int_stream_t *stream)
649 packed_int_private_t *private_data = stream->private_data;
650 return private_data->is_last ? NULL : private_data->next;
653 svn_packed__byte_stream_t *
654 svn_packed__next_byte_stream(svn_packed__byte_stream_t *stream)
659 svn_packed__int_stream_t *
660 svn_packed__first_int_substream(svn_packed__int_stream_t *stream)
662 packed_int_private_t *private_data = stream->private_data;
663 return private_data->first_substream;
667 svn_packed__int_count(svn_packed__int_stream_t *stream)
669 packed_int_private_t *private_data = stream->private_data;
670 return private_data->item_count + stream->buffer_used;
674 svn_packed__byte_count(svn_packed__byte_stream_t *stream)
676 return stream->packed->len;
680 svn_packed__byte_block_count(svn_packed__byte_stream_t *stream)
682 return svn_packed__int_count(stream->lengths_stream);
685 /* Read one 7b/8b encoded value from *P and return it in *RESULT. Returns
686 * the first position after the parsed data.
688 * Overflows will be detected in the sense that it will end parsing the
689 * input but the result is undefined.
691 static unsigned char *
692 read_packed_uint_body(unsigned char *p, apr_uint64_t *result)
700 apr_uint64_t shift = 0;
701 apr_uint64_t value = 0;
704 value += (apr_uint64_t)(*p & 0x7f) << shift;
710 /* a definite overflow. Note, that numbers of 65 .. 70
711 bits will not be detected as an overflow as they don't
712 threaten to exceed the input buffer. */
718 *result = value + ((apr_uint64_t)*p << shift);
724 /* Read one 7b/8b encoded value from STREAM and return it in *RESULT.
726 * Overflows will be detected in the sense that it will end parsing the
727 * input but the result is undefined.
730 read_stream_uint(svn_stream_t *stream, apr_uint64_t *result)
732 apr_uint64_t shift = 0;
733 apr_uint64_t value = 0;
739 SVN_ERR(svn_stream_read_full(stream, (char *)&c, &len));
741 return svn_error_create(SVN_ERR_CORRUPT_PACKED_DATA, NULL,
742 _("Unexpected end of stream"));
744 value += (apr_uint64_t)(c & 0x7f) << shift;
747 return svn_error_create(SVN_ERR_CORRUPT_PACKED_DATA, NULL,
748 _("Integer representation too long"));
756 /* Extract and return the next integer from PACKED and make PACKED point
757 * to the next integer.
760 read_packed_uint(svn_stringbuf_t *packed)
762 apr_uint64_t result = 0;
763 unsigned char *p = (unsigned char *)packed->data;
764 apr_size_t read = read_packed_uint_body(p, &result) - p;
766 if (read > packed->len)
769 packed->data += read;
770 packed->blocksize -= read;
776 /* Ensure that STREAM contains at least one item in its buffer.
779 svn_packed__data_fill_buffer(svn_packed__int_stream_t *stream)
781 packed_int_private_t *private_data = stream->private_data;
783 apr_size_t end = MIN(SVN__PACKED_DATA_BUFFER_SIZE,
784 private_data->item_count);
786 /* in case, some user calls us explicitly without a good reason ... */
787 if (stream->buffer_used)
790 /* can we get data from the sub-streams or do we have to decode it from
791 our local packed container? */
792 if (private_data->current_substream)
793 for (i = end; i > 0; --i)
795 packed_int_private_t *current_private_data
796 = private_data->current_substream->private_data;
798 = svn_packed__get_uint(private_data->current_substream);
799 private_data->current_substream = current_private_data->next;
803 /* use this local buffer only if the packed data is shorter than this.
804 The goal is that read_packed_uint_body doesn't need check for
806 unsigned char local_buffer[10 * SVN__PACKED_DATA_BUFFER_SIZE];
808 unsigned char *start;
809 apr_size_t packed_read;
811 if (private_data->packed->len < sizeof(local_buffer))
813 apr_size_t trail = sizeof(local_buffer) - private_data->packed->len;
815 private_data->packed->data,
816 private_data->packed->len);
817 memset(local_buffer + private_data->packed->len, 0, MIN(trail, end));
822 p = (unsigned char *)private_data->packed->data;
826 for (i = end; i > 0; --i)
827 p = read_packed_uint_body(p, &stream->buffer[i-1]);
829 /* adjust remaining packed data buffer */
830 packed_read = p - start;
831 private_data->packed->data += packed_read;
832 private_data->packed->len -= packed_read;
833 private_data->packed->blocksize -= packed_read;
835 /* undeltify numbers, if configured */
836 if (private_data->diff)
838 apr_uint64_t last_value = private_data->last_value;
839 for (i = end; i > 0; --i)
841 last_value += unmap_uint(stream->buffer[i-1]);
842 stream->buffer[i-1] = last_value;
845 private_data->last_value = last_value;
848 /* handle signed values, if configured and not handled already */
849 if (!private_data->diff && private_data->is_signed)
850 for (i = 0; i < end; ++i)
851 stream->buffer[i] = unmap_uint(stream->buffer[i]);
854 stream->buffer_used = end;
855 private_data->item_count -= end;
859 svn_packed__get_uint(svn_packed__int_stream_t *stream)
861 if (stream->buffer_used == 0)
862 svn_packed__data_fill_buffer(stream);
864 return stream->buffer_used ? stream->buffer[--stream->buffer_used] : 0;
868 svn_packed__get_int(svn_packed__int_stream_t *stream)
870 return (apr_int64_t)svn_packed__get_uint(stream);
874 svn_packed__get_bytes(svn_packed__byte_stream_t *stream,
877 const char *result = stream->packed->data;
878 apr_size_t count = (apr_size_t)svn_packed__get_uint(stream->lengths_stream);
880 if (count > stream->packed->len)
881 count = stream->packed->len;
883 /* advance packed buffer */
884 stream->packed->data += count;
885 stream->packed->len -= count;
886 stream->packed->blocksize -= count;
892 /* Read the integer stream structure and recreate it in STREAM, including
893 * sub-streams, from TREE_STRUCT.
896 read_int_stream_structure(svn_stringbuf_t *tree_struct,
897 svn_packed__int_stream_t *stream)
899 packed_int_private_t *private_data = stream->private_data;
900 apr_uint64_t value = read_packed_uint(tree_struct);
901 apr_size_t substream_count;
904 /* extract local parameters */
905 private_data->diff = (value & 1) != 0;
906 private_data->is_signed = (value & 2) != 0;
907 substream_count = (apr_size_t)(value >> 2);
909 /* read item count & packed size; allocate packed data buffer */
910 private_data->item_count = (apr_size_t)read_packed_uint(tree_struct);
911 value = read_packed_uint(tree_struct);
914 private_data->packed = svn_stringbuf_create_ensure((apr_size_t)value,
916 private_data->packed->len = (apr_size_t)value;
919 /* add sub-streams and read their config, too */
920 for (i = 0; i < substream_count; ++i)
921 read_int_stream_structure(tree_struct,
922 svn_packed__create_int_substream(stream,
927 /* Read the integer stream structure and recreate it in STREAM, including
928 * sub-streams, from TREE_STRUCT. FIRST_INT_STREAM is the integer stream
929 * that would correspond to lengths_stream_index 0.
932 read_byte_stream_structure(svn_stringbuf_t *tree_struct,
933 svn_packed__byte_stream_t *stream,
934 svn_packed__int_stream_t *first_int_stream)
936 apr_size_t lengths_stream_index;
937 apr_size_t packed_size;
940 /* read parameters from the TREE_STRUCT buffer */
941 (void) (apr_size_t)read_packed_uint(tree_struct); /* discard first uint */
942 lengths_stream_index = (apr_size_t)read_packed_uint(tree_struct);
943 packed_size = (apr_size_t)read_packed_uint(tree_struct);
945 /* allocate byte sequence buffer size */
946 svn_stringbuf_ensure(stream->packed, packed_size);
947 stream->packed->len = packed_size;
949 /* navigate to the (already existing) lengths_stream */
950 stream->lengths_stream_index = lengths_stream_index;
951 stream->lengths_stream = first_int_stream;
952 for (i = 0; i < lengths_stream_index; ++i)
954 packed_int_private_t *length_private
955 = stream->lengths_stream->private_data;
956 stream->lengths_stream = length_private->next;
960 /* Read a compressed block from STREAM and uncompress it into UNCOMPRESSED.
961 * UNCOMPRESSED_LEN is the expected size of the stream. COMPRESSED is a
962 * re-used buffer for temporary data.
965 read_stream_data(svn_stream_t *stream,
966 apr_size_t uncompressed_len,
967 svn_stringbuf_t *uncompressed,
968 svn_stringbuf_t *compressed)
971 apr_size_t compressed_len;
973 SVN_ERR(read_stream_uint(stream, &len));
974 compressed_len = (apr_size_t)len;
976 svn_stringbuf_ensure(compressed, compressed_len);
977 compressed->len = compressed_len;
978 SVN_ERR(svn_stream_read_full(stream, compressed->data, &compressed->len));
979 compressed->data[compressed_len] = '\0';
981 SVN_ERR(svn__decompress_zlib(compressed->data, compressed->len,
982 uncompressed, uncompressed_len));
987 /* Read the packed contents from COMBINED, starting at *OFFSET and store
988 * it in STREAM. Update *OFFSET to point to the next stream's data and
989 * continue with the sub-streams.
992 unflatten_int_stream(svn_packed__int_stream_t *stream,
993 svn_stringbuf_t *combined,
996 packed_int_private_t *private_data = stream->private_data;
997 if (private_data->packed)
999 memcpy(private_data->packed->data,
1000 combined->data + *offset,
1001 private_data->packed->len);
1003 private_data->packed->data[private_data->packed->len] = '\0';
1004 *offset += private_data->packed->len;
1007 stream = private_data->first_substream;
1010 private_data = stream->private_data;
1011 unflatten_int_stream(stream, combined, offset);
1012 stream = private_data->is_last ? NULL : private_data->next;
1016 /* Read the packed contents from COMBINED, starting at *OFFSET and store
1017 * it in STREAM. Update *OFFSET to point to the next stream's data and
1018 * continue with the sub-streams.
1021 unflatten_byte_stream(svn_packed__byte_stream_t *stream,
1022 svn_stringbuf_t *combined,
1025 memcpy(stream->packed->data,
1026 combined->data + *offset,
1027 stream->packed->len);
1028 stream->packed->data[stream->packed->len] = '\0';
1030 *offset += stream->packed->len;
1031 for (stream = stream->first_substream; stream; stream = stream->next)
1032 unflatten_byte_stream(stream, combined, offset);
1036 svn_packed__data_read(svn_packed__data_root_t **root_p,
1037 svn_stream_t *stream,
1038 apr_pool_t *result_pool,
1039 apr_pool_t *scratch_pool)
1044 svn_packed__int_stream_t *int_stream;
1045 svn_packed__byte_stream_t *byte_stream;
1046 svn_packed__data_root_t *root = svn_packed__data_create_root(result_pool);
1048 svn_stringbuf_t *compressed
1049 = svn_stringbuf_create_ensure(1024, scratch_pool);
1050 svn_stringbuf_t *uncompressed
1051 = svn_stringbuf_create_ensure(1024, scratch_pool);
1053 /* read tree structure */
1055 apr_uint64_t tree_struct_size;
1056 svn_stringbuf_t *tree_struct;
1058 SVN_ERR(read_stream_uint(stream, &tree_struct_size));
1060 = svn_stringbuf_create_ensure((apr_size_t)tree_struct_size, scratch_pool);
1061 tree_struct->len = (apr_size_t)tree_struct_size;
1063 SVN_ERR(svn_stream_read_full(stream, tree_struct->data, &tree_struct->len));
1064 tree_struct->data[tree_struct->len] = '\0';
1066 /* reconstruct tree structure */
1068 count = read_packed_uint(tree_struct);
1069 for (i = 0; i < count; ++i)
1070 read_int_stream_structure(tree_struct,
1071 svn_packed__create_int_stream(root, FALSE,
1074 count = read_packed_uint(tree_struct);
1075 for (i = 0; i < count; ++i)
1076 read_byte_stream_structure(tree_struct,
1077 create_bytes_stream_body(root),
1078 root->first_int_stream);
1080 /* read sub-stream data from disk, unzip it and buffer it */
1082 for (int_stream = root->first_int_stream;
1084 int_stream = ((packed_int_private_t*)int_stream->private_data)->next)
1086 apr_size_t offset = 0;
1087 SVN_ERR(read_stream_data(stream,
1088 packed_int_stream_length(int_stream),
1089 uncompressed, compressed));
1090 unflatten_int_stream(int_stream, uncompressed, &offset);
1093 for (byte_stream = root->first_byte_stream;
1095 byte_stream = byte_stream->next)
1097 apr_size_t offset = 0;
1098 SVN_ERR(read_stream_data(stream,
1099 packed_byte_stream_length(byte_stream),
1100 uncompressed, compressed));
1101 unflatten_byte_stream(byte_stream, uncompressed, &offset);
1105 return SVN_NO_ERROR;