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
ByteWithPayloadByteWithPayload27 ByteWithPayload(std::uint8_t k) : key(k), payload(0) { }
ByteWithPayloadByteWithPayload28 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 {
operatorByteWithPayload::key_less39 bool operator()(ByteWithPayload const& x, ByteWithPayload const& y) const
40 { return x.key < y.key; }
41 };
42
43 struct payload_less {
operatorByteWithPayload::payload_less44 bool operator()(ByteWithPayload const& x, ByteWithPayload const& y) const
45 { return x.payload < y.payload; }
46 };
47
48 struct total_less {
operatorByteWithPayload::total_less49 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
swapByteWithPayload54 friend void swap(ByteWithPayload& lhs, ByteWithPayload& rhs) {
55 std::swap(lhs.key, rhs.key);
56 std::swap(lhs.payload, 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>
fast_is_permutation(Iter1 first1,Iter1 last1,Iter2 first2)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>
fast_is_permutation(Iter1 first1,Iter1 last1,Iter2 first2)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
main(int,char **)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(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