OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "courgette/third_party/bsdiff/bsdiff_search.h" | 5 #include "courgette/third_party/bsdiff/bsdiff_search.h" |
6 | 6 |
7 #include <cstring> | 7 #include <cstring> |
8 #include <vector> | |
9 | 8 |
10 #include "base/macros.h" | 9 #include "base/macros.h" |
11 #include "courgette/third_party/bsdiff/qsufsort.h" | 10 #include "courgette/third_party/bsdiff/paged_array.h" |
| 11 #include "courgette/third_party/divsufsort/divsufsort.h" |
12 #include "testing/gtest/include/gtest/gtest.h" | 12 #include "testing/gtest/include/gtest/gtest.h" |
13 | 13 |
14 TEST(BSDiffSearchTest, Search) { | 14 TEST(BSDiffSearchTest, Search) { |
15 // Initialize main string and the suffix array. | 15 // Initialize main string and the suffix array. |
16 // Positions: 000000000011111111111222222222333333333344444 | 16 // Positions: 000000000011111111111222222222333333333344444 |
17 // 012345678901234567890123456789012345678901234 | 17 // 012345678901234567890123456789012345678901234 |
18 const char* str = "the quick brown fox jumps over the lazy dog."; | 18 const char* str = "the quick brown fox jumps over the lazy dog."; |
19 int size = static_cast<int>(::strlen(str)); | 19 int size = static_cast<int>(::strlen(str)); |
20 const unsigned char* buf = reinterpret_cast<const unsigned char*>(str); | 20 const unsigned char* buf = reinterpret_cast<const unsigned char*>(str); |
21 std::vector<int> I(size + 1); | 21 courgette::PagedArray<divsuf::saidx_t> I; |
22 std::vector<int> V(size + 1); | 22 ASSERT_TRUE(I.Allocate(size + 1)); |
23 qsuf::qsufsort<int*>(&I[0], &V[0], buf, size); | 23 divsuf::divsufsort_include_empty(buf, I.begin(), size); |
24 | 24 |
25 // Specific queries. | 25 // Specific queries. |
26 const struct { | 26 const struct { |
27 int exp_match_pos; // -1 means "don't care". | 27 int exp_match_pos; // -1 means "don't care". |
28 int exp_match_size; | 28 int exp_match_size; |
29 const char* query_str; | 29 const char* query_str; |
30 } test_cases[] = { | 30 } test_cases[] = { |
31 // Entire string: exact and unique. | 31 // Entire string: exact and unique. |
32 {0, 44, "the quick brown fox jumps over the lazy dog."}, | 32 {0, 44, "the quick brown fox jumps over the lazy dog."}, |
33 // Empty string: exact and non-unique. | 33 // Empty string: exact and non-unique. |
(...skipping 24 matching lines...) Expand all Loading... |
58 }; | 58 }; |
59 | 59 |
60 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { | 60 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { |
61 const auto& test_case = test_cases[idx]; | 61 const auto& test_case = test_cases[idx]; |
62 int query_size = static_cast<int>(::strlen(test_case.query_str)); | 62 int query_size = static_cast<int>(::strlen(test_case.query_str)); |
63 const unsigned char* query_buf = | 63 const unsigned char* query_buf = |
64 reinterpret_cast<const unsigned char*>(test_case.query_str); | 64 reinterpret_cast<const unsigned char*>(test_case.query_str); |
65 | 65 |
66 // Perform the search. | 66 // Perform the search. |
67 bsdiff::SearchResult match = | 67 bsdiff::SearchResult match = |
68 bsdiff::search(&I[0], buf, size, query_buf, query_size); | 68 bsdiff::search<courgette::PagedArray<divsuf::saidx_t>&>( |
| 69 I, buf, size, query_buf, query_size); |
69 | 70 |
70 // Check basic properties and match with expected values. | 71 // Check basic properties and match with expected values. |
71 EXPECT_GE(match.size, 0); | 72 EXPECT_GE(match.size, 0); |
72 EXPECT_LE(match.size, query_size); | 73 EXPECT_LE(match.size, query_size); |
73 if (match.size > 0) { | 74 if (match.size > 0) { |
74 EXPECT_GE(match.pos, 0); | 75 EXPECT_GE(match.pos, 0); |
75 EXPECT_LE(match.pos, size - match.size); | 76 EXPECT_LE(match.pos, size - match.size); |
76 EXPECT_EQ(0, ::memcmp(buf + match.pos, query_buf, match.size)); | 77 EXPECT_EQ(0, ::memcmp(buf + match.pos, query_buf, match.size)); |
77 } | 78 } |
78 if (test_case.exp_match_pos >= 0) { | 79 if (test_case.exp_match_pos >= 0) { |
(...skipping 14 matching lines...) Expand all Loading... |
93 "banana", | 94 "banana", |
94 "tobeornottobe", | 95 "tobeornottobe", |
95 "the quick brown fox jumps over the lazy dog.", | 96 "the quick brown fox jumps over the lazy dog.", |
96 "elephantelephantelephantelephantelephant", | 97 "elephantelephantelephantelephantelephant", |
97 "011010011001011010010110011010010", | 98 "011010011001011010010110011010010", |
98 }; | 99 }; |
99 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { | 100 for (size_t idx = 0; idx < arraysize(test_cases); ++idx) { |
100 int size = static_cast<int>(::strlen(test_cases[idx])); | 101 int size = static_cast<int>(::strlen(test_cases[idx])); |
101 const unsigned char* buf = | 102 const unsigned char* buf = |
102 reinterpret_cast<const unsigned char*>(test_cases[idx]); | 103 reinterpret_cast<const unsigned char*>(test_cases[idx]); |
103 std::vector<int> I(size + 1); | 104 courgette::PagedArray<divsuf::saidx_t> I; |
104 std::vector<int> V(size + 1); | 105 ASSERT_TRUE(I.Allocate(size + 1)); |
105 qsuf::qsufsort<int*>(&I[0], &V[0], buf, size); | 106 divsuf::divsufsort_include_empty(buf, I.begin(), size); |
106 | 107 |
107 // Test exact matches for every non-empty substring. | 108 // Test exact matches for every non-empty substring. |
108 for (int lo = 0; lo < size; ++lo) { | 109 for (int lo = 0; lo < size; ++lo) { |
109 for (int hi = lo + 1; hi <= size; ++hi) { | 110 for (int hi = lo + 1; hi <= size; ++hi) { |
110 std::string query(buf + lo, buf + hi); | 111 std::string query(buf + lo, buf + hi); |
111 int query_size = static_cast<int>(query.length()); | 112 int query_size = static_cast<int>(query.length()); |
112 ASSERT_EQ(query_size, hi - lo); | 113 ASSERT_EQ(query_size, hi - lo); |
113 const unsigned char* query_buf = | 114 const unsigned char* query_buf = |
114 reinterpret_cast<const unsigned char*>(query.c_str()); | 115 reinterpret_cast<const unsigned char*>(query.c_str()); |
115 bsdiff::SearchResult match = | 116 bsdiff::SearchResult match = |
116 bsdiff::search(&I[0], buf, size, query_buf, query_size); | 117 bsdiff::search<courgette::PagedArray<divsuf::saidx_t>&>( |
| 118 I, buf, size, query_buf, query_size); |
117 | 119 |
118 EXPECT_EQ(query_size, match.size); | 120 EXPECT_EQ(query_size, match.size); |
119 EXPECT_GE(match.pos, 0); | 121 EXPECT_GE(match.pos, 0); |
120 EXPECT_LE(match.pos, size - match.size); | 122 EXPECT_LE(match.pos, size - match.size); |
121 std::string suffix(buf + match.pos, buf + size); | 123 std::string suffix(buf + match.pos, buf + size); |
122 EXPECT_EQ(suffix.substr(0, query_size), query); | 124 EXPECT_EQ(suffix.substr(0, query_size), query); |
123 } | 125 } |
124 } | 126 } |
125 } | 127 } |
126 } | 128 } |
OLD | NEW |