diff options
Diffstat (limited to 'src/addrcache.h')
| -rw-r--r-- | src/addrcache.h | 217 |
1 files changed, 217 insertions, 0 deletions
diff --git a/src/addrcache.h b/src/addrcache.h new file mode 100644 index 0000000..0aea65d --- /dev/null +++ b/src/addrcache.h @@ -0,0 +1,217 @@ +// Copyright 2007 Google Inc. +// Author: Lincoln Smith +// +// Licensed 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. +// +// Classes to implement the Address Cache and Address Encoding +// algorithms described in sections 5.1 - 5.4 of RFC 3284 - +// The VCDIFF Generic Differencing and Compression Data Format. +// The RFC text can be found at http://www.faqs.org/rfcs/rfc3284.html + +#ifndef OPEN_VCDIFF_ADDRCACHE_H_ +#define OPEN_VCDIFF_ADDRCACHE_H_ + +#include <config.h> +#include <vector> +#include "vcdiff_defs.h" // VCDAddress + +namespace open_vcdiff { + +// Implements the "same" and "near" caches +// as described in RFC 3284, section 5. The "near" cache allows +// efficient reuse of one of the last four referenced addresses +// plus a small offset, and the "same" cache allows efficient reuse +// of an exact recent address distinguished by its lowest-order bits. +// +// NOT threadsafe. +// +class VCDiffAddressCache { + public: + // The default cache sizes specified in the RFC + static const int kDefaultNearCacheSize = 4; + static const int kDefaultSameCacheSize = 3; + + VCDiffAddressCache(int near_cache_size, int same_cache_size); + + // This version of the constructor uses the default values + // kDefaultNearCacheSize and kDefaultSameCacheSize. + VCDiffAddressCache(); + + // Initializes the object before use. This method must be called after + // constructing a VCDiffAddressCache/ object, before any other method may be + // called. This is because Init() validates near_cache_size_ and + // same_cache_size_ before initializing the same and near caches. After the + // object has been initialized and used, Init() can be called again to reset + // it to its initial state. + // + bool Init(); + + int near_cache_size() const { return near_cache_size_; } + + int same_cache_size() const { return same_cache_size_; } + + // Returns the first mode number that represents one of the NEAR modes. + // The number of NEAR modes is near_cache_size. Each NEAR mode refers to + // an element of the near_addresses_ array, where a recently-referenced + // address is stored. + // + static unsigned char FirstNearMode() { + return VCD_FIRST_NEAR_MODE; + } + + // Returns the first mode number that represents one of the SAME modes. + // The number of SAME modes is same_cache_size. Each SAME mode refers to + // a block of 256 elements of the same_addresses_ array; the lowest-order + // 8 bits of the address are used to find the element of this block that + // may match the desired address value. + // + unsigned char FirstSameMode() const { + return VCD_FIRST_NEAR_MODE + near_cache_size(); + } + + // Returns the maximum valid mode number, which happens to be + // the last SAME mode. + // + unsigned char LastMode() const { + return FirstSameMode() + same_cache_size() - 1; + } + + static unsigned char DefaultLastMode() { + return VCD_FIRST_NEAR_MODE + + kDefaultNearCacheSize + kDefaultSameCacheSize - 1; + } + + // See the definition of enum VCDiffModes in vcdiff_defs.h, + // as well as section 5.3 of the RFC, for a description of + // each address mode type (SELF, HERE, NEAR, and SAME). + static bool IsSelfMode(unsigned char mode) { + return mode == VCD_SELF_MODE; + } + + static bool IsHereMode(unsigned char mode) { + return mode == VCD_HERE_MODE; + } + + bool IsNearMode(unsigned char mode) const { + return (mode >= FirstNearMode()) && (mode < FirstSameMode()); + } + + bool IsSameMode(unsigned char mode) const { + return (mode >= FirstSameMode()) && (mode <= LastMode()); + } + + static VCDAddress DecodeSelfAddress(int32_t encoded_address) { + return encoded_address; + } + + static VCDAddress DecodeHereAddress(int32_t encoded_address, + VCDAddress here_address) { + return here_address - encoded_address; + } + + VCDAddress DecodeNearAddress(unsigned char mode, + int32_t encoded_address) const { + return NearAddress(mode - FirstNearMode()) + encoded_address; + } + + VCDAddress DecodeSameAddress(unsigned char mode, + unsigned char encoded_address) const { + return SameAddress(((mode - FirstSameMode()) * 256) + encoded_address); + } + + // Returns true if, when using the given mode, an encoded address + // should be written to the delta file as a variable-length integer; + // returns false if the encoded address should be written + // as a byte value (unsigned char). + bool WriteAddressAsVarintForMode(unsigned char mode) const { + return !IsSameMode(mode); + } + + // An accessor for an element of the near_addresses_ array. + // No bounds checking is performed; the caller must ensure that + // Init() has already been called, and that + // 0 <= pos < near_cache_size_ + // + VCDAddress NearAddress(int pos) const { + return near_addresses_[pos]; + } + + // An accessor for an element of the same_addresses_ array. + // No bounds checking is performed; the caller must ensure that + // Init() has already been called, and that + // 0 <= pos < (same_cache_size_ * 256) + // + VCDAddress SameAddress(int pos) const { + return same_addresses_[pos]; + } + + // This method will be called whenever an address is calculated for an + // encoded or decoded COPY instruction, and will update the contents + // of the SAME and NEAR caches. + // + void UpdateCache(VCDAddress address); + + // Determines the address mode that yields the most compact encoding + // of the given address value. The most compact encoding + // is found by looking for the numerically lowest encoded address. + // Sets *encoded_addr to the encoded representation of the address + // and returns the mode used. + // + // The caller should pass the return value to the method + // WriteAddressAsVarintForMode() to determine whether encoded_addr + // should be written to the delta file as a variable-length integer + // or as a byte (unsigned char). + // + unsigned char EncodeAddress(VCDAddress address, + VCDAddress here_address, + VCDAddress* encoded_addr); + + // Interprets the next value in the address_stream using the provided mode, + // which may need to access the SAME or NEAR address cache. Returns the + // decoded address, or one of the following values: + // RESULT_ERROR: An invalid address value was found in address_stream. + // RESULT_END_OF_DATA: The limit address_stream_end was reached before + // the address could be decoded. If more streamed data is expected, + // this means that the consumer should block and wait for more data + // before continuing to decode. If no more data is expected, this + // return value signals an error condition. + // + // If successful, *address_stream will be incremented past the decoded address + // position. If RESULT_ERROR or RESULT_END_OF_DATA is returned, + // then the value of *address_stream will not have changed. + // + VCDAddress DecodeAddress(VCDAddress here_address, + unsigned char mode, + const char** address_stream, + const char* address_stream_end); + + private: + // The number of addresses to be kept in the NEAR cache. + const int near_cache_size_; + // The number of 256-byte blocks to store in the SAME cache. + const int same_cache_size_; + // The next position in the NEAR cache to which an address will be written. + int next_slot_; + // NEAR cache contents + std::vector<VCDAddress> near_addresses_; + // SAME cache contents + std::vector<VCDAddress> same_addresses_; + + // Making these private avoids implicit copy constructor & assignment operator + VCDiffAddressCache(const VCDiffAddressCache&); // NOLINT + void operator=(const VCDiffAddressCache&); +}; + +} // namespace open_vcdiff + +#endif // OPEN_VCDIFF_ADDRCACHE_H_ |