| 121 | // Creates a binary patch. |
| 122 | template <typename OldReader, typename NewReader, typename PatchSink> |
| 123 | BSDiffStatus CreateBinaryPatch(OldReader & old_reader, |
| 124 | NewReader & new_reader, |
| 125 | PatchSink & patch_sink) { |
| 126 | ReaderSource<OldReader> old_source(old_reader); |
| 127 | ReaderSource<NewReader> new_source(new_reader); |
| 128 | |
| 129 | auto initial_patch_sink_pos = patch_sink.Pos(); |
| 130 | |
| 131 | base::Timer bsdiff_timer; |
| 132 | |
| 133 | CHECK_GREATER_OR_EQUAL(kNumStreams, 6, ()); |
| 134 | std::array<MemStream, kNumStreams> mem_streams; |
| 135 | auto & control_stream_copy_counts = mem_streams[0]; |
| 136 | auto & control_stream_extra_counts = mem_streams[1]; |
| 137 | auto & control_stream_seeks = mem_streams[2]; |
| 138 | auto & diff_skips = mem_streams[3]; |
| 139 | auto & diff_bytes = mem_streams[4]; |
| 140 | auto & extra_bytes = mem_streams[5]; |
| 141 | |
| 142 | const int old_size = static_cast<int>(old_source.Size()); |
| 143 | std::vector<uint8_t> old_buf(old_size); |
| 144 | old_source.Read(old_buf.data(), old_buf.size()); |
| 145 | const uint8_t * old = old_buf.data(); |
| 146 | |
| 147 | std::vector<divsuf::saidx_t> suffix_array(old_size + 1); |
| 148 | base::Timer suf_sort_timer; |
| 149 | divsuf::saint_t result = divsuf::divsufsort_include_empty(old, suffix_array.data(), old_size); |
| 150 | LOG(LINFO, ("Done divsufsort", suf_sort_timer.ElapsedSeconds())); |
| 151 | if (result != 0) |
| 152 | return UNEXPECTED_ERROR; |
| 153 | |
| 154 | const int new_size = static_cast<int>(new_source.Size()); |
| 155 | std::vector<uint8_t> new_buf(new_size); |
| 156 | new_source.Read(new_buf.data(), new_buf.size()); |
| 157 | const uint8_t * newbuf = new_buf.data(); |
| 158 | |
| 159 | int control_length = 0; |
| 160 | int diff_bytes_length = 0; |
| 161 | int diff_bytes_nonzero = 0; |
| 162 | int extra_bytes_length = 0; |
| 163 | |
| 164 | // The patch format is a sequence of triples <copy,extra,seek> where 'copy' is |
| 165 | // the number of bytes to copy from the old file (possibly with mistakes), |
| 166 | // 'extra' is the number of bytes to copy from a stream of fresh bytes, and |
| 167 | // 'seek' is an offset to move to the position to copy for the next triple. |
| 168 | // |
| 169 | // The invariant at the top of this loop is that we are committed to emitting |
| 170 | // a triple for the part of |newbuf| surrounding a 'seed' match near |
| 171 | // |lastscan|. We are searching for a second match that will be the 'seed' of |
| 172 | // the next triple. As we scan through |newbuf|, one of four things can |
| 173 | // happen at the current position |scan|: |
| 174 | // |
| 175 | // 1. We find a nice match that appears to be consistent with the current |
| 176 | // seed. Continue scanning. It is likely that this match will become |
| 177 | // part of the 'copy'. |
| 178 | // |
| 179 | // 2. We find match which does much better than extending the current seed |
| 180 | // old match. Emit a triple for the current seed and take this match as |
no test coverage detected