sdch/open-vcdiff/src/addrcache.h

// 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_