Home | History | Annotate | Download | only in src 
      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 
     25 namespace open_vcdiff {
     26 
     27 const 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 
     35 const 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 
     43 const 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 
     49 const 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 
     55 VCDiffDecoderTest::VCDiffDecoderTest() : fuzzer_(0), fuzzed_byte_position_(0) {
     56   dictionary_ = kDictionary;
     57   expected_target_ = kExpectedTarget;
     58 }
     59 
     60 void VCDiffDecoderTest::SetUp() {
     61   InitializeDeltaFile();
     62 }
     63 
     64 void VCDiffDecoderTest::UseStandardFileHeader() {
     65   delta_file_header_.assign(kStandardFileHeader,
     66                             sizeof(kStandardFileHeader));
     67 }
     68 
     69 void VCDiffDecoderTest::UseInterleavedFileHeader() {
     70   delta_file_header_.assign(kInterleavedFileHeader,
     71                             sizeof(kInterleavedFileHeader));
     72 }
     73 
     74 void VCDiffDecoderTest::InitializeDeltaFile() {
     75   delta_file_ = delta_file_header_ + delta_window_header_ + delta_window_body_;
     76 }
     77 
     78 char 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 
     85 void 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 
     96 void 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.
    103 void 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.
    114 void 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.
    125 void 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 
    134 bool 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 
    166 const 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 
    180 const 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 
    218 VCDiffStandardDecoderTest::VCDiffStandardDecoderTest() {
    219   UseStandardFileHeader();
    220   delta_window_header_.assign(kWindowHeader, sizeof(kWindowHeader));
    221   delta_window_body_.assign(kWindowBody, sizeof(kWindowBody));
    222 }
    223 
    224 const 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 
    238 const 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 
    274 VCDiffInterleavedDecoderTest::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