1// Copyright 2008 Google Inc.
2// Author: Lincoln Smith
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8//      http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16#include <config.h>
17#include "vcdecoder_test.h"
18#include <string.h>  // strlen
19#include "checksum.h"
20#include "codetable.h"
21#include "testing.h"
22#include "varint_bigendian.h"
23#include "vcdiff_defs.h"
24
25namespace open_vcdiff {
26
27const char VCDiffDecoderTest::kStandardFileHeader[] = {
28    0xD6,  // 'V' | 0x80
29    0xC3,  // 'C' | 0x80
30    0xC4,  // 'D' | 0x80
31    0x00,  // Draft standard version number
32    0x00   // Hdr_Indicator: no custom code table, no compression
33  };
34
35const char VCDiffDecoderTest::kInterleavedFileHeader[] = {
36    0xD6,  // 'V' | 0x80
37    0xC3,  // 'C' | 0x80
38    0xC4,  // 'D' | 0x80
39    'S',   // SDCH version code
40    0x00   // Hdr_Indicator: no custom code table, no compression
41  };
42
43const char VCDiffDecoderTest::kDictionary[] =
44  "\"Just the place for a Snark!\" the Bellman cried,\n"
45  "As he landed his crew with care;\n"
46  "Supporting each man on the top of the tide\n"
47  "By a finger entwined in his hair.\n";
48
49const char VCDiffDecoderTest::kExpectedTarget[] =
50  "\"Just the place for a Snark! I have said it twice:\n"
51  "That alone should encourage the crew.\n"
52  "Just the place for a Snark! I have said it thrice:\n"
53  "What I tell you three times is true.\"\n";
54
55VCDiffDecoderTest::VCDiffDecoderTest() : fuzzer_(0), fuzzed_byte_position_(0) {
56  dictionary_ = kDictionary;
57  expected_target_ = kExpectedTarget;
58}
59
60void VCDiffDecoderTest::SetUp() {
61  InitializeDeltaFile();
62}
63
64void VCDiffDecoderTest::UseStandardFileHeader() {
65  delta_file_header_.assign(kStandardFileHeader,
66                            sizeof(kStandardFileHeader));
67}
68
69void VCDiffDecoderTest::UseInterleavedFileHeader() {
70  delta_file_header_.assign(kInterleavedFileHeader,
71                            sizeof(kInterleavedFileHeader));
72}
73
74void VCDiffDecoderTest::InitializeDeltaFile() {
75  delta_file_ = delta_file_header_ + delta_window_header_ + delta_window_body_;
76}
77
78char VCDiffDecoderTest::GetByteFromStringLength(const char* s,
79                                                int which_byte) {
80  char varint_buf[VarintBE<int32_t>::kMaxBytes];
81  VarintBE<int32_t>::Encode(static_cast<int32_t>(strlen(s)), varint_buf);
82  return varint_buf[which_byte];
83}
84
85void VCDiffDecoderTest::AddChecksum(VCDChecksum checksum) {
86  int32_t checksum_as_int32 = static_cast<int32_t>(checksum);
87  delta_window_header_[0] |= VCD_CHECKSUM;
88  VarintBE<int32_t>::AppendToString(checksum_as_int32, &delta_window_header_);
89  // Adjust delta window size to include checksum.
90  // This method wouldn't work if adding to the length caused the VarintBE
91  // value to spill over into another byte.  Luckily, this test data happens
92  // not to cause such an overflow.
93  delta_window_header_[4] += VarintBE<int32_t>::Length(checksum_as_int32);
94}
95
96void VCDiffDecoderTest::ComputeAndAddChecksum() {
97  AddChecksum(ComputeAdler32(expected_target_.data(),
98                             expected_target_.size()));
99}
100
101// Write the maximum expressible positive 32-bit VarintBE
102// (0x7FFFFFFF) at the given offset in the delta window.
103void VCDiffDecoderTest::WriteMaxVarintAtOffset(int offset,
104                                               int bytes_to_replace) {
105  static const char kMaxVarint[] = { 0x87, 0xFF, 0xFF, 0xFF, 0x7F };
106  delta_file_.replace(delta_file_header_.size() + offset,
107                      bytes_to_replace,
108                      kMaxVarint,
109                      sizeof(kMaxVarint));
110}
111
112// Write a negative 32-bit VarintBE (0x80000000) at the given offset
113// in the delta window.
114void VCDiffDecoderTest::WriteNegativeVarintAtOffset(int offset,
115                                                    int bytes_to_replace) {
116  static const char kNegativeVarint[] = { 0x88, 0x80, 0x80, 0x80, 0x00 };
117  delta_file_.replace(delta_file_header_.size() + offset,
118                      bytes_to_replace,
119                      kNegativeVarint,
120                      sizeof(kNegativeVarint));
121}
122
123// Write a VarintBE that has too many continuation bytes
124// at the given offset in the delta window.
125void VCDiffDecoderTest::WriteInvalidVarintAtOffset(int offset,
126                                                   int bytes_to_replace) {
127  static const char kInvalidVarint[] = { 0x87, 0xFF, 0xFF, 0xFF, 0xFF, 0x7F };
128  delta_file_.replace(delta_file_header_.size() + offset,
129                      bytes_to_replace,
130                      kInvalidVarint,
131                      sizeof(kInvalidVarint));
132}
133
134bool VCDiffDecoderTest::FuzzOneByteInDeltaFile() {
135  static const struct Fuzzer {
136    char _and;
137    char _or;
138    char _xor;
139  } fuzzers[] = {
140    { 0xff, 0x80, 0x00 },
141    { 0xff, 0xff, 0x00 },
142    { 0xff, 0x00, 0x80 },
143    { 0xff, 0x00, 0xff },
144    { 0xff, 0x01, 0x00 },
145    { 0x7f, 0x00, 0x00 },
146  };
147
148  for (; fuzzer_ < (sizeof(fuzzers) / sizeof(fuzzers[0])); ++fuzzer_) {
149    for (; fuzzed_byte_position_ < delta_file_.size();
150         ++fuzzed_byte_position_) {
151      char fuzzed_byte = (((delta_file_[fuzzed_byte_position_]
152                             & fuzzers[fuzzer_]._and)
153                             | fuzzers[fuzzer_]._or)
154                             ^ fuzzers[fuzzer_]._xor);
155      if (fuzzed_byte != delta_file_[fuzzed_byte_position_]) {
156        delta_file_[fuzzed_byte_position_] = fuzzed_byte;
157        ++fuzzed_byte_position_;
158        return true;
159      }
160    }
161    fuzzed_byte_position_ = 0;
162  }
163  return false;
164}
165
166const char VCDiffStandardDecoderTest::kWindowHeader[] = {
167    VCD_SOURCE,  // Win_Indicator: take source from dictionary
168    FirstByteOfStringLength(kDictionary),  // Source segment size
169    SecondByteOfStringLength(kDictionary),
170    0x00,  // Source segment position: start of dictionary
171    0x79,  // Length of the delta encoding
172    FirstByteOfStringLength(kExpectedTarget),  // Size of the target window
173    SecondByteOfStringLength(kExpectedTarget),
174    0x00,  // Delta_indicator (no compression)
175    0x64,  // length of data for ADDs and RUNs
176    0x0C,  // length of instructions section
177    0x03  // length of addresses for COPYs
178  };
179
180const char VCDiffStandardDecoderTest::kWindowBody[] = {
181    // Data for ADDs: 1st section (length 61)
182    ' ', 'I', ' ', 'h', 'a', 'v', 'e', ' ', 's', 'a', 'i', 'd', ' ',
183    'i', 't', ' ', 't', 'w', 'i', 'c', 'e', ':', '\n',
184    'T', 'h', 'a', 't', ' ',
185    'a', 'l', 'o', 'n', 'e', ' ', 's', 'h', 'o', 'u', 'l', 'd', ' ',
186    'e', 'n', 'c', 'o', 'u', 'r', 'a', 'g', 'e', ' ',
187    't', 'h', 'e', ' ', 'c', 'r', 'e', 'w', '.', '\n',
188    // Data for ADDs: 2nd section (length 2)
189    'h', 'r',
190    // Data for ADDs: 3rd section (length 9)
191    'W', 'h', 'a', 't', ' ',
192    'I', ' ', 't', 'e',
193    // Data for RUN: 4th section (length 1)
194    'l',
195    // Data for ADD: 4th section (length 27)
196    ' ', 'y', 'o', 'u', ' ',
197    't', 'h', 'r', 'e', 'e', ' ', 't', 'i', 'm', 'e', 's', ' ', 'i', 's', ' ',
198    't', 'r', 'u', 'e', '.', '\"', '\n',
199    // Instructions and sizes (length 13)
200    0x13,  // VCD_COPY mode VCD_SELF, size 0
201    0x1C,  // Size of COPY (28)
202    0x01,  // VCD_ADD size 0
203    0x3D,  // Size of ADD (61)
204    0x23,  // VCD_COPY mode VCD_HERE, size 0
205    0x2C,  // Size of COPY (44)
206    0xCB,  // VCD_ADD size 2 + VCD_COPY mode NEAR(1), size 5
207    0x0A,  // VCD_ADD size 9
208    0x00,  // VCD_RUN size 0
209    0x02,  // Size of RUN (2)
210    0x01,  // VCD_ADD size 0
211    0x1B,  // Size of ADD (27)
212    // Addresses for COPYs (length 3)
213    0x00,  // Start of dictionary
214    0x58,  // HERE mode address for 2nd copy (27+61 back from here_address)
215    0x2D   // NEAR(1) mode address for 2nd copy (45 after prior address)
216  };
217
218VCDiffStandardDecoderTest::VCDiffStandardDecoderTest() {
219  UseStandardFileHeader();
220  delta_window_header_.assign(kWindowHeader, sizeof(kWindowHeader));
221  delta_window_body_.assign(kWindowBody, sizeof(kWindowBody));
222}
223
224const char VCDiffInterleavedDecoderTest::kWindowHeader[] = {
225    VCD_SOURCE,  // Win_Indicator: take source from dictionary
226    FirstByteOfStringLength(kDictionary),  // Source segment size
227    SecondByteOfStringLength(kDictionary),
228    0x00,  // Source segment position: start of dictionary
229    0x79,  // Length of the delta encoding
230    FirstByteOfStringLength(kExpectedTarget),  // Size of the target window
231    SecondByteOfStringLength(kExpectedTarget),
232    0x00,  // Delta_indicator (no compression)
233    0x00,  // length of data for ADDs and RUNs (unused)
234    0x73,  // length of interleaved section
235    0x00  // length of addresses for COPYs (unused)
236  };
237
238const char VCDiffInterleavedDecoderTest::kWindowBody[] = {
239    0x13,  // VCD_COPY mode VCD_SELF, size 0
240    0x1C,  // Size of COPY (28)
241    0x00,  // Address of COPY: Start of dictionary
242    0x01,  // VCD_ADD size 0
243    0x3D,  // Size of ADD (61)
244    // Data for ADD (length 61)
245    ' ', 'I', ' ', 'h', 'a', 'v', 'e', ' ', 's', 'a', 'i', 'd', ' ',
246    'i', 't', ' ', 't', 'w', 'i', 'c', 'e', ':', '\n',
247    'T', 'h', 'a', 't', ' ',
248    'a', 'l', 'o', 'n', 'e', ' ', 's', 'h', 'o', 'u', 'l', 'd', ' ',
249    'e', 'n', 'c', 'o', 'u', 'r', 'a', 'g', 'e', ' ',
250    't', 'h', 'e', ' ', 'c', 'r', 'e', 'w', '.', '\n',
251    0x23,  // VCD_COPY mode VCD_HERE, size 0
252    0x2C,  // Size of COPY (44)
253    0x58,  // HERE mode address (27+61 back from here_address)
254    0xCB,  // VCD_ADD size 2 + VCD_COPY mode NEAR(1), size 5
255    // Data for ADDs: 2nd section (length 2)
256    'h', 'r',
257    0x2D,  // NEAR(1) mode address (45 after prior address)
258    0x0A,  // VCD_ADD size 9
259    // Data for ADDs: 3rd section (length 9)
260    'W', 'h', 'a', 't', ' ',
261    'I', ' ', 't', 'e',
262    0x00,  // VCD_RUN size 0
263    0x02,  // Size of RUN (2)
264    // Data for RUN: 4th section (length 1)
265    'l',
266    0x01,  // VCD_ADD size 0
267    0x1B,  // Size of ADD (27)
268    // Data for ADD: 4th section (length 27)
269    ' ', 'y', 'o', 'u', ' ',
270    't', 'h', 'r', 'e', 'e', ' ', 't', 'i', 'm', 'e', 's', ' ', 'i', 's', ' ',
271    't', 'r', 'u', 'e', '.', '\"', '\n'
272  };
273
274VCDiffInterleavedDecoderTest::VCDiffInterleavedDecoderTest() {
275  UseInterleavedFileHeader();
276  delta_window_header_.assign(kWindowHeader, sizeof(kWindowHeader));
277  delta_window_body_.assign(kWindowBody, sizeof(kWindowBody));
278}
279
280}  // namespace open_vcdiff
281