1c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Copyright 2008 Google Inc. 2c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Author: Lincoln Smith 3c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 4c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Licensed under the Apache License, Version 2.0 (the "License"); 5c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// you may not use this file except in compliance with the License. 6c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// You may obtain a copy of the License at 7c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 8c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// http://www.apache.org/licenses/LICENSE-2.0 9c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 10c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Unless required by applicable law or agreed to in writing, software 11c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// distributed under the License is distributed on an "AS IS" BASIS, 12c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// See the License for the specific language governing permissions and 14c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// limitations under the License. 15c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 16c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Classes to implement the Code Table 17c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// described in sections 5.5, 5.6 and 7 of 18c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// RFC 3284 - The VCDIFF Generic Differencing and Compression Data Format. 19c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The RFC text can be found at http://www.faqs.org/rfcs/rfc3284.html 20c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 21c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#ifndef OPEN_VCDIFF_CODETABLE_H_ 22c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define OPEN_VCDIFF_CODETABLE_H_ 23c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 24c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include <config.h> 25c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include <stdint.h> // uint16_t 26c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 27c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottnamespace open_vcdiff { 28c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 29c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// The instruction types from section 5.5 (mistakenly labeled 5.4) of the RFC. 30c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 31c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottenum VCDiffInstructionType { 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCD_NOOP = 0, 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCD_ADD = 1, 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCD_RUN = 2, 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCD_COPY = 3, 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCD_LAST_INSTRUCTION_TYPE = VCD_COPY, 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The following values are not true instruction types, but rather 38c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // special condition values for functions that return VCDiffInstructionType. 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCD_INSTRUCTION_ERROR = 4, 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott VCD_INSTRUCTION_END_OF_DATA = 5 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 43c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst char* VCDiffInstructionName(VCDiffInstructionType inst); 44c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 45c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// OpcodeOrNone: An opcode is a value between 0-255. There is not room 46c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// in a single byte to express all these values plus a "no opcode found" 47c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// value. So use a 16-bit integer to hold either an opcode or kNoOpcode. 48c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 49c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scotttypedef uint16_t OpcodeOrNone; 50c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottconst OpcodeOrNone kNoOpcode = 0x100; // outside the opcode range 0x00 - 0xFF 51c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 52c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// struct VCDiffCodeTableData: 53c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 54c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// A representation of the VCDiff code table as six 256-byte arrays 55c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// as described in Section 7 of RFC 3284. Each instruction code 56c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// can represent up to two delta instructions, which is why inst, 57c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// size, and mode each appear twice. Each of the two delta instructions 58c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// has the following three attributes: 59c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// * inst (NOOP, ADD, RUN, or COPY) 60c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// * size (0-255 bytes) of the data to be copied; if this value is zero, then 61c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// the size will be encoded separately from the instruction code, as a Varint 62c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// * mode (SELF, HERE, NEAR(n), or SAME(n)), only used for COPY instructions 63c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 64c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Every valid code table should contain AT LEAST the following instructions: 65c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// inst1=ADD size1=0 mode1=X inst2=NOOP size2=X mode2=X 66c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// inst1=RUN size1=0 mode1=X inst2=NOOP size2=X mode2=X 67c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// inst1=COPY size1=0 mode1=N inst2=NOOP size2=X mode2=X (for all N) 68c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// ... where X represents a "don't care" value which will not be read, 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// and N stands for every possible COPY mode between 0 and 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// ([same cache size] + [here cache size]) inclusive. 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// Without these instructions, it will be impossible to guarantee that 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// all ADD, RUN, and COPY encoding requests can be fulfilled. 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott// 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottstruct VCDiffCodeTableData { 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static const int kCodeTableSize = 256; 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static const VCDiffCodeTableData kDefaultCodeTableData; 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Validates that the data contained in the VCDiffCodeTableData structure 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // does not violate certain assumptions. Returns true if none of these 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // assumptions are violated, or false if an unexpected value is found. 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // This function should be called on any non-default code table that is 83c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // received as part of an encoded transmission. 84c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // max_mode is the maximum value for the mode of a COPY instruction; 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // this is equal to same_cache_size + near_cache_size + 1. 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bool Validate(unsigned char max_mode) const; 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // This version of Validate() assumes that the default address cache sizes 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // are being used, and calculates max_mode based on that assumption. 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott bool Validate() const; 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // The names of these elements are taken from RFC 3284 section 5.4 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // (Instruction Codes), which contains the following specification: 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Each instruction code entry contains six fields, each of which is a single 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // byte with an unsigned value: 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // +-----------------------------------------------+ 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // | inst1 | size1 | mode1 | inst2 | size2 | mode2 | 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // +-----------------------------------------------+ 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char inst1[kCodeTableSize]; // from enum VCDiffInstructionType 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char inst2[kCodeTableSize]; // from enum VCDiffInstructionType 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char size1[kCodeTableSize]; 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char size2[kCodeTableSize]; 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char mode1[kCodeTableSize]; // from enum VCDiffModes 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char mode2[kCodeTableSize]; // from enum VCDiffModes 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott private: 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // Single-letter abbreviations that make it easier to read 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott // the default code table data. 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static const VCDiffInstructionType N = VCD_NOOP; 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static const VCDiffInstructionType A = VCD_ADD; 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static const VCDiffInstructionType R = VCD_RUN; 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static const VCDiffInstructionType C = VCD_COPY; 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott static bool ValidateOpcode(int opcode, 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char inst, 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char size, 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char mode, 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned char max_mode, 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const char* first_or_second); 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott}; 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} // namespace open_vcdiff 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#endif // OPEN_VCDIFF_CODETABLE_H_ 128