15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2011 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Streams classes. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// These memory-resident streams are used for serializing data into a sequential 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// region of memory. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Streams are divided into SourceStreams for reading and SinkStreams for 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// writing. Streams are aggregated into Sets which allows several streams to be 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// used at once. Example: we can write A1, B1, A2, B2 but achieve the memory 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// layout A1 A2 B1 B2 by writing 'A's to one stream and 'B's to another. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The aggregated streams are important to Courgette's compression efficiency, 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// we use it to cluster similar kinds of data which helps to generate longer 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// common subsequences and repeated sequences. 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "courgette/streams.h" 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <memory.h> 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/logging.h" 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace courgette { 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Update this version number if the serialization format of a StreamSet 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// changes. 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static const unsigned int kStreamsSerializationFormatVersion = 20090218; 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is a cut down Varint implementation, implementing only what we use for 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// streams. 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Varint { 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Maximum lengths of varint encoding of uint32 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kMax32 = 5; 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Parses a Varint32 encoded value from |source| and stores it in |output|, 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and returns a pointer to the following byte. Returns NULL if a valid 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // varint value was not found before |limit|. 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const uint8* Parse32WithLimit(const uint8* source, const uint8* limit, 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32* output); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Writes the Varint32 encoded representation of |value| to buffer 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // |destination|. |destination| must have sufficient length to hold kMax32 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // bytes. Returns a pointer to the byte just past the last encoded byte. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static uint8* Encode32(uint8* destination, uint32 value); 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Parses a Varint32 encoded unsigned number from |source|. The Varint32 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// encoding is a little-endian sequence of bytes containing base-128 digits, 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// with the high order bit set to indicate if there are more digits. 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// For each byte, we mask out the digit and 'or' it into the right place in the 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// result. 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The digit loop is unrolled for performance. It usually exits after the first 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// one or two digits. 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const uint8* Varint::Parse32WithLimit(const uint8* source, 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8* limit, 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32* output) { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 digit, result; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (source >= limit) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) digit = *(source++); 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result = digit & 127; 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (digit < 128) { 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *output = result; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return source; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (source >= limit) 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) digit = *(source++); 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result |= (digit & 127) << 7; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (digit < 128) { 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *output = result; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return source; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (source >= limit) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) digit = *(source++); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result |= (digit & 127) << 14; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (digit < 128) { 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *output = result; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return source; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (source >= limit) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) digit = *(source++); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result |= (digit & 127) << 21; 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (digit < 128) { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *output = result; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return source; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (source >= limit) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) digit = *(source++); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result |= (digit & 127) << 28; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (digit < 128) { 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *output = result; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return source; 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; // Value is too long to be a Varint32. 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Write the base-128 digits in little-endian order. All except the last digit 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// have the high bit set to indicate more digits. 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)inline uint8* Varint::Encode32(uint8* destination, uint32 value) { 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (value >= 128) { 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *(destination++) = value | 128; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value = value >> 7; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *(destination++) = value; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return destination; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SourceStream::Init(const SinkStream& sink) { 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Init(sink.Buffer(), sink.Length()); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStream::Read(void* destination, size_t count) { 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (current_ + count > end_) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(destination, current_, count); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_ += count; 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStream::ReadVarint32(uint32* output_value) { 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8* after = Varint::Parse32WithLimit(current_, end_, output_value); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!after) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_ = after; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStream::ReadVarint32Signed(int32* output_value) { 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Signed numbers are encoded as unsigned numbers so that numbers nearer zero 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // have shorter varint encoding. 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 0000xxxx encoded as 000xxxx0. 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1111xxxx encoded as 000yyyy1 where yyyy is complement of xxxx. 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 unsigned_value; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!ReadVarint32(&unsigned_value)) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (unsigned_value & 1) 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *output_value = ~static_cast<int32>(unsigned_value >> 1); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *output_value = (unsigned_value >> 1); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStream::ShareSubstream(size_t offset, size_t length, 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SourceStream* substream) { 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (offset > Remaining()) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (length > Remaining() - offset) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) substream->Init(current_ + offset, length); 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStream::ReadSubstream(size_t length, SourceStream* substream) { 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!ShareSubstream(0, length, substream)) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_ += length; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStream::Skip(size_t byte_count) { 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (current_ + byte_count > end_) 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) current_ += byte_count; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)CheckBool SinkStream::Write(const void* data, size_t byte_count) { 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return buffer_.append(static_cast<const char*>(data), byte_count); 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)CheckBool SinkStream::WriteVarint32(uint32 value) { 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8 buffer[Varint::kMax32]; 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8* end = Varint::Encode32(buffer, value); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Write(buffer, end - buffer); 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)CheckBool SinkStream::WriteVarint32Signed(int32 value) { 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Encode signed numbers so that numbers nearer zero have shorter 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // varint encoding. 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 0000xxxx encoded as 000xxxx0. 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1111xxxx encoded as 000yyyy1 where yyyy is complement of xxxx. 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool ret; 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value < 0) 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = WriteVarint32(~value * 2 + 1); 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = WriteVarint32(value * 2); 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ret; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)CheckBool SinkStream::WriteSizeVarint32(size_t value) { 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 narrowed_value = static_cast<uint32>(value); 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // On 32-bit, the compiler should figure out this test always fails. 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LOG_ASSERT(value == narrowed_value); 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return WriteVarint32(narrowed_value); 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)CheckBool SinkStream::Append(SinkStream* other) { 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool ret = Write(other->buffer_.data(), other->buffer_.size()); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ret) 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) other->Retire(); 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ret; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SinkStream::Retire() { 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) buffer_.clear(); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//////////////////////////////////////////////////////////////////////////////// 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SourceStreamSet::SourceStreamSet() 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : count_(kMaxStreams) { 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SourceStreamSet::~SourceStreamSet() { 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Initializes from |source|. 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The stream set for N streams is serialized as a header 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// <version><N><length1><length2>...<lengthN> 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// followed by the stream contents 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// <bytes1><bytes2>...<bytesN> 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStreamSet::Init(const void* source, size_t byte_count) { 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8* start = static_cast<const uint8*>(source); 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8* end = start + byte_count; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int version; 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const uint8* finger = Varint::Parse32WithLimit(start, end, &version); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (finger == NULL) 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (version != kStreamsSerializationFormatVersion) 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int count; 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) finger = Varint::Parse32WithLimit(finger, end, &count); 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (finger == NULL) 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (count > kMaxStreams) 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count_ = count; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int lengths[kMaxStreams]; 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t accumulated_length = 0; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < count_; ++i) { 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) finger = Varint::Parse32WithLimit(finger, end, &lengths[i]); 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (finger == NULL) 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) accumulated_length += lengths[i]; 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remaining bytes should add up to sum of lengths. 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (static_cast<size_t>(end - finger) != accumulated_length) 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) accumulated_length = finger - start; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < count_; ++i) { 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stream(i)->Init(start + accumulated_length, lengths[i]); 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) accumulated_length += lengths[i]; 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStreamSet::Init(SourceStream* source) { 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(sra): consume the rest of |source|. 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Init(source->Buffer(), source->Remaining()); 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStreamSet::ReadSet(SourceStreamSet* set) { 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 stream_count = 0; 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SourceStream* control_stream = this->stream(0); 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!control_stream->ReadVarint32(&stream_count)) 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 lengths[kMaxStreams] = {}; // i.e. all zero. 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < stream_count; ++i) { 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!control_stream->ReadVarint32(&lengths[i])) 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < stream_count; ++i) { 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!this->stream(i)->ReadSubstream(lengths[i], set->stream(i))) 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool SourceStreamSet::Empty() const { 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < count_; ++i) { 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (streams_[i].Remaining() != 0) 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//////////////////////////////////////////////////////////////////////////////// 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SinkStreamSet::SinkStreamSet() 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : count_(kMaxStreams) { 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SinkStreamSet::~SinkStreamSet() { 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SinkStreamSet::Init(size_t stream_index_limit) { 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count_ = stream_index_limit; 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The header for a stream set for N streams is serialized as 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// <version><N><length1><length2>...<lengthN> 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)CheckBool SinkStreamSet::CopyHeaderTo(SinkStream* header) { 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool ret = header->WriteVarint32(kStreamsSerializationFormatVersion); 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ret) { 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = header->WriteSizeVarint32(count_); 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; ret && i < count_; ++i) { 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = header->WriteSizeVarint32(stream(i)->Length()); 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ret; 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Writes |this| to |combined_stream|. See SourceStreamSet::Init for the layout 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// of the stream metadata and contents. 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)CheckBool SinkStreamSet::CopyTo(SinkStream *combined_stream) { 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream header; 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool ret = CopyHeaderTo(&header); 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!ret) 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ret; 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Reserve the correct amount of storage. 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t length = header.Length(); 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < count_; ++i) { 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) length += stream(i)->Length(); 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = combined_stream->Reserve(length); 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ret) { 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = combined_stream->Append(&header); 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; ret && i < count_; ++i) { 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = combined_stream->Append(stream(i)); 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ret; 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)CheckBool SinkStreamSet::WriteSet(SinkStreamSet* set) { 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint32 lengths[kMaxStreams]; 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 'stream_count' includes all non-empty streams and all empty stream numbered 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // lower than a non-empty stream. 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t stream_count = 0; 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; i < kMaxStreams; ++i) { 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* stream = set->stream(i); 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) lengths[i] = static_cast<uint32>(stream->Length()); 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (lengths[i] > 0) 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stream_count = i + 1; 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SinkStream* control_stream = this->stream(0); 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool ret = control_stream->WriteSizeVarint32(stream_count); 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; ret && i < stream_count; ++i) { 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = control_stream->WriteSizeVarint32(lengths[i]); 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (size_t i = 0; ret && i < stream_count; ++i) { 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ret = this->stream(i)->Append(set->stream(i)); 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return ret; 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 391