1 // Copyright 2017 The Chromium OS Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "bsdiff/suffix_array_index.h" 6 7 #include <limits> 8 #include <vector> 9 10 #include <divsufsort.h> 11 #include <divsufsort64.h> 12 13 #include "bsdiff/logging.h" 14 15 namespace { 16 17 // libdivsufsort C++ overloaded functions used to allow calling the right 18 // implementation based on the pointer size. 19 int CallDivSufSort(const uint8_t* text, saidx_t* sa, size_t n) { 20 return divsufsort(text, sa, n); 21 } 22 int CallDivSufSort(const uint8_t* text, saidx64_t* sa, size_t n) { 23 return divsufsort64(text, sa, n); 24 } 25 26 saidx_t CallSaSearch(const uint8_t* text, 27 size_t text_size, 28 const uint8_t* pattern, 29 size_t pattern_size, 30 const saidx_t* sa, 31 size_t sa_size, 32 saidx_t* left) { 33 return sa_search(text, text_size, pattern, pattern_size, sa, sa_size, left); 34 } 35 saidx64_t CallSaSearch(const uint8_t* text, 36 size_t text_size, 37 const uint8_t* pattern, 38 size_t pattern_size, 39 const saidx64_t* sa, 40 size_t sa_size, 41 saidx64_t* left) { 42 return sa_search64(text, text_size, pattern, pattern_size, sa, sa_size, left); 43 } 44 45 } // namespace 46 47 namespace bsdiff { 48 49 // The SAIDX template type must be either saidx_t or saidx64_t, which will 50 // depend on the maximum size of the input text needed. 51 template <typename SAIDX> 52 class SuffixArrayIndex : public SuffixArrayIndexInterface { 53 public: 54 SuffixArrayIndex() = default; 55 56 // Initialize and construct the suffix array of the |text| string of length 57 // |n|. The memory pointed by |text| must be kept alive. Returns whether the 58 // construction succeeded. 59 bool Init(const uint8_t* text, size_t n); 60 61 // SuffixArrayIndexInterface overrides. 62 void SearchPrefix(const uint8_t* target, 63 size_t length, 64 size_t* out_length, 65 uint64_t* out_pos) const override; 66 67 private: 68 const uint8_t* text_{nullptr}; // Owned by the caller. 69 size_t n_{0}; 70 71 std::vector<SAIDX> sa_; 72 }; 73 74 template <typename SAIDX> 75 bool SuffixArrayIndex<SAIDX>::Init(const uint8_t* text, size_t n) { 76 if (!sa_.empty()) { 77 // Already initialized. 78 LOG(ERROR) << "SuffixArray already initialized"; 79 return false; 80 } 81 if (static_cast<uint64_t>(n) > 82 static_cast<uint64_t>(std::numeric_limits<SAIDX>::max())) { 83 LOG(ERROR) << "Input too big (" << n << ") for this implementation"; 84 return false; 85 } 86 text_ = text; 87 n_ = n; 88 sa_.resize(n + 1); 89 90 if (n > 0 && CallDivSufSort(text_, sa_.data(), n) != 0) { 91 LOG(ERROR) << "divsufsrot() failed"; 92 return false; 93 } 94 95 return true; 96 } 97 98 template <typename SAIDX> 99 void SuffixArrayIndex<SAIDX>::SearchPrefix(const uint8_t* target, 100 size_t length, 101 size_t* out_length, 102 uint64_t* out_pos) const { 103 SAIDX suf_left; 104 SAIDX count = 105 CallSaSearch(text_, n_, target, length, sa_.data(), n_, &suf_left); 106 if (count > 0) { 107 // This is the simple case where we found the whole |target| string was 108 // found. 109 *out_pos = sa_[suf_left]; 110 *out_length = length; 111 return; 112 } 113 // In this case, |suf_left| points to the first suffix array position such 114 // that the suffix at that position is lexicographically larger than |target|. 115 // We only need to check whether the previous entry or the current entry is a 116 // longer match. 117 size_t prev_suffix_len = 0; 118 if (suf_left > 0) { 119 const size_t prev_max_len = 120 std::min(n_ - static_cast<size_t>(sa_[suf_left - 1]), length); 121 const uint8_t* prev_suffix = text_ + sa_[suf_left - 1]; 122 prev_suffix_len = 123 std::mismatch(target, target + prev_max_len, prev_suffix).first - 124 target; 125 } 126 127 size_t next_suffix_len = 0; 128 if (static_cast<size_t>(suf_left) < n_) { 129 const uint8_t* next_suffix = text_ + sa_[suf_left]; 130 const size_t next_max_len = 131 std::min(n_ - static_cast<size_t>(sa_[suf_left]), length); 132 next_suffix_len = 133 std::mismatch(target, target + next_max_len, next_suffix).first - 134 target; 135 } 136 137 *out_length = std::max(next_suffix_len, prev_suffix_len); 138 if (!*out_length) { 139 *out_pos = 0; 140 } else if (next_suffix_len >= prev_suffix_len) { 141 *out_pos = sa_[suf_left]; 142 } else { 143 *out_pos = sa_[suf_left - 1]; 144 } 145 } 146 147 std::unique_ptr<SuffixArrayIndexInterface> CreateSuffixArrayIndex( 148 const uint8_t* text, 149 size_t n) { 150 // The maximum supported size when using the suffix array based on the 32-bit 151 // saidx_t type. We limit this to something a bit smaller (16 bytes smaller) 152 // than the maximum representable number so references like "n + 1" are don't 153 // overflow. 154 const size_t kMaxSaidxSize = std::numeric_limits<saidx_t>::max() - 16; 155 std::unique_ptr<SuffixArrayIndexInterface> ret; 156 157 if (n > kMaxSaidxSize) { 158 SuffixArrayIndex<saidx64_t>* sa_ptr = new SuffixArrayIndex<saidx64_t>(); 159 ret.reset(sa_ptr); 160 if (!sa_ptr->Init(text, n)) 161 return nullptr; 162 } else { 163 SuffixArrayIndex<saidx_t>* sa_ptr = new SuffixArrayIndex<saidx_t>(); 164 ret.reset(sa_ptr); 165 if (!sa_ptr->Init(text, n)) 166 return nullptr; 167 } 168 return ret; 169 } 170 171 172 } // namespace bsdiff 173
