1 | //===----------------------------------------------------------------------===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | |
9 | #ifndef TEST_LIBCXX_FUZZING_FUZZ_H |
10 | #define TEST_LIBCXX_FUZZING_FUZZ_H |
11 | |
12 | #include <cassert> |
13 | #include <cstddef> |
14 | #include <cstdint> |
15 | #include <cstring> // std::strlen |
16 | #include <iterator> |
17 | #include <type_traits> |
18 | #include <utility> // std::swap |
19 | |
20 | |
21 | // This is a struct we can use to test the stable_XXX algorithms. |
22 | // Perform the operation on the key, then check the order of the payload. |
23 | struct ByteWithPayload { |
24 | std::uint8_t key; |
25 | std::size_t payload; |
26 | |
27 | ByteWithPayload(std::uint8_t k) : key(k), payload(0) { } |
28 | ByteWithPayload(std::uint8_t k, std::size_t p) : key(k), payload(p) { } |
29 | |
30 | friend bool operator==(ByteWithPayload const& x, ByteWithPayload const& y) { |
31 | return x.key == y.key && x.payload == y.payload; |
32 | } |
33 | |
34 | friend bool operator!=(ByteWithPayload const& x, ByteWithPayload const& y) { |
35 | return !(x == y); |
36 | } |
37 | |
38 | struct key_less { |
39 | bool operator()(ByteWithPayload const& x, ByteWithPayload const& y) const |
40 | { return x.key < y.key; } |
41 | }; |
42 | |
43 | struct payload_less { |
44 | bool operator()(ByteWithPayload const& x, ByteWithPayload const& y) const |
45 | { return x.payload < y.payload; } |
46 | }; |
47 | |
48 | struct total_less { |
49 | bool operator()(ByteWithPayload const& x, ByteWithPayload const& y) const { |
50 | return x.key == y.key ? x.payload < y.payload : x.key < y.key; |
51 | } |
52 | }; |
53 | |
54 | friend void swap(ByteWithPayload& lhs, ByteWithPayload& rhs) { |
55 | std::swap(a&: lhs.key, b&: rhs.key); |
56 | std::swap(a&: lhs.payload, b&: rhs.payload); |
57 | } |
58 | }; |
59 | |
60 | // Faster version of std::is_permutation |
61 | // |
62 | // Builds a set of buckets for each of the key values, and sums all the payloads. |
63 | // Not 100% perfect, but _way_ faster. |
64 | template <typename Iter1, typename Iter2, typename = typename std::enable_if< |
65 | std::is_same<typename std::iterator_traits<Iter1>::value_type, ByteWithPayload>::value && |
66 | std::is_same<typename std::iterator_traits<Iter2>::value_type, ByteWithPayload>::value |
67 | >::type> |
68 | bool fast_is_permutation(Iter1 first1, Iter1 last1, Iter2 first2) { |
69 | std::size_t xBuckets[256] = {0}; |
70 | std::size_t xPayloads[256] = {0}; |
71 | std::size_t yBuckets[256] = {0}; |
72 | std::size_t yPayloads[256] = {0}; |
73 | |
74 | for (; first1 != last1; ++first1, ++first2) { |
75 | xBuckets[first1->key]++; |
76 | xPayloads[first1->key] += first1->payload; |
77 | |
78 | yBuckets[first2->key]++; |
79 | yPayloads[first2->key] += first2->payload; |
80 | } |
81 | |
82 | for (std::size_t i = 0; i < 256; ++i) { |
83 | if (xBuckets[i] != yBuckets[i]) |
84 | return false; |
85 | if (xPayloads[i] != yPayloads[i]) |
86 | return false; |
87 | } |
88 | |
89 | return true; |
90 | } |
91 | |
92 | template <typename Iter1, typename Iter2, typename = void, typename = typename std::enable_if< |
93 | std::is_same<typename std::iterator_traits<Iter1>::value_type, std::uint8_t>::value && |
94 | std::is_same<typename std::iterator_traits<Iter2>::value_type, std::uint8_t>::value |
95 | >::type> |
96 | bool fast_is_permutation(Iter1 first1, Iter1 last1, Iter2 first2) { |
97 | std::size_t xBuckets[256] = {0}; |
98 | std::size_t yBuckets[256] = {0}; |
99 | |
100 | for (; first1 != last1; ++first1, ++first2) { |
101 | xBuckets[*first1]++; |
102 | yBuckets[*first2]++; |
103 | } |
104 | |
105 | for (std::size_t i = 0; i < 256; ++i) |
106 | if (xBuckets[i] != yBuckets[i]) |
107 | return false; |
108 | |
109 | return true; |
110 | } |
111 | |
112 | // When running inside OSS-Fuzz, we link against a fuzzing library that defines |
113 | // main() and calls LLVMFuzzerTestOneInput. |
114 | // |
115 | // Otherwise, when e.g. running the Lit tests, we define main() to run fuzzing |
116 | // tests on a few inputs. |
117 | #if !defined(LIBCPP_OSS_FUZZ) |
118 | extern "C" int LLVMFuzzerTestOneInput(const std::uint8_t*, std::size_t); |
119 | |
120 | int main(int, char**) { |
121 | const char* test_cases[] = { |
122 | "" , |
123 | "s" , |
124 | "bac" , |
125 | "bacasf" , |
126 | "lkajseravea" , |
127 | "adsfkajdsfjkas;lnc441324513,34535r34525234" , |
128 | "b*c" , |
129 | "ba?sf" , |
130 | "lka*ea" , |
131 | "adsf*kas;lnc441[0-9]1r34525234" |
132 | }; |
133 | |
134 | for (const char* tc : test_cases) { |
135 | const std::size_t size = std::strlen(s: tc); |
136 | const std::uint8_t* data = reinterpret_cast<const std::uint8_t*>(tc); |
137 | int result = LLVMFuzzerTestOneInput(data, size); |
138 | assert(result == 0); |
139 | } |
140 | |
141 | return 0; |
142 | } |
143 | #endif // !LIBCPP_OSS_FUZZ |
144 | |
145 | #endif // TEST_LIBCXX_FUZZING_FUZZ_H |
146 | |