1 // (C) Copyright Marshall Clow 2018
2 // Use, modification and distribution are subject to the
3 // Boost Software License, Version 1.0. (See accompanying file
4 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6 #include <iterator> // for std::distance
7 #include <cassert> // for assert
8
9 #include <boost/algorithm/minmax_element.hpp>
10 #include <boost/algorithm/cxx11/none_of.hpp>
11
12 // Fuzzing tests for:
13 //
14 // template <class ForwardIterator>
15 // std::pair<ForwardIterator,ForwardIterator>
16 // first_min_first_max_element(ForwardIterator first, ForwardIterator last);
17 //
18 // template <class ForwardIterator, class BinaryPredicate>
19 // std::pair<ForwardIterator,ForwardIterator>
20 // first_min_first_max_element(ForwardIterator first, ForwardIterator last,
21 // BinaryPredicate comp);
22 //
23 // identical signatures for:
24 // first_min_last_max_element
25 // last_min_first_max_element
26 // last_min_last_max_element
27
greater(uint8_t lhs,uint8_t rhs)28 bool greater(uint8_t lhs, uint8_t rhs) { return lhs > rhs; }
29
LLVMFuzzerTestOneInput(const uint8_t * data,size_t sz)30 extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t sz) {
31 typedef std::pair<const uint8_t *, const uint8_t *> result_t;
32 const uint8_t * const dend = data + sz;
33 if (sz == 0) return 0; // we need at least one element
34
35 {
36 // Find the min and max
37 result_t resultff = boost::first_min_first_max_element(data, dend);
38 result_t resultfl = boost::first_min_last_max_element (data, dend);
39 result_t resultlf = boost::last_min_first_max_element (data, dend);
40 result_t resultll = boost::last_min_last_max_element (data, dend);
41
42 // The iterators have to be in the sequence - and not at the end!
43 assert(std::distance(data, resultff.first) < sz);
44 assert(std::distance(data, resultff.second) < sz);
45 assert(std::distance(data, resultfl.first) < sz);
46 assert(std::distance(data, resultfl.second) < sz);
47 assert(std::distance(data, resultlf.first) < sz);
48 assert(std::distance(data, resultlf.second) < sz);
49 assert(std::distance(data, resultll.first) < sz);
50 assert(std::distance(data, resultll.second) < sz);
51
52 // the minimum element can't be bigger than the max element
53
54 // Did we find the same min value and max value?
55 uint8_t min_value = *resultff.first;
56 uint8_t max_value = *resultff.second;
57 assert(min_value <= max_value);
58
59 // Each variant should have found the same min/max values
60 assert(*resultff.first == min_value);
61 assert(*resultfl.first == min_value);
62 assert(*resultlf.first == min_value);
63 assert(*resultll.first == min_value);
64
65 assert(*resultff.second == max_value);
66 assert(*resultfl.second == max_value);
67 assert(*resultlf.second == max_value);
68 assert(*resultll.second == max_value);
69
70 // None of the elements in the sequence can be less than the min, nor greater than the max
71 for (size_t i = 0; i < sz; ++i) {
72 assert(min_value <= data[i]);
73 assert(data[i] <= max_value);
74 }
75
76 // Make sure we returned the "right" first and last element
77 assert(boost::algorithm::none_of_equal(data, resultff.first, min_value));
78 assert(boost::algorithm::none_of_equal(data, resultfl.first, min_value));
79 assert(boost::algorithm::none_of_equal(resultlf.first + 1, dend, min_value));
80 assert(boost::algorithm::none_of_equal(resultll.first + 1, dend, min_value));
81
82 assert(boost::algorithm::none_of_equal(data, resultff.second, max_value));
83 assert(boost::algorithm::none_of_equal(resultfl.second + 1, dend, max_value));
84 assert(boost::algorithm::none_of_equal(data, resultlf.second, max_value));
85 assert(boost::algorithm::none_of_equal(resultll.second + 1, dend, max_value));
86 }
87
88 {
89 // Find the min and max
90 result_t resultff = boost::first_min_first_max_element(data, dend, greater);
91 result_t resultfl = boost::first_min_last_max_element (data, dend, greater);
92 result_t resultlf = boost::last_min_first_max_element (data, dend, greater);
93 result_t resultll = boost::last_min_last_max_element (data, dend, greater);
94
95 // The iterators have to be in the sequence - and not at the end!
96 assert(std::distance(data, resultff.first) < sz);
97 assert(std::distance(data, resultff.second) < sz);
98 assert(std::distance(data, resultfl.first) < sz);
99 assert(std::distance(data, resultfl.second) < sz);
100 assert(std::distance(data, resultlf.first) < sz);
101 assert(std::distance(data, resultlf.second) < sz);
102 assert(std::distance(data, resultll.first) < sz);
103 assert(std::distance(data, resultll.second) < sz);
104
105 // the minimum element can't be bigger than the max element
106 uint8_t min_value = *resultff.first;
107 uint8_t max_value = *resultff.second;
108
109 assert (!greater(max_value, min_value));
110
111 // Each variant should have found the same min/max values
112 assert(*resultff.first == min_value);
113 assert(*resultfl.first == min_value);
114 assert(*resultlf.first == min_value);
115 assert(*resultll.first == min_value);
116
117 assert(*resultff.second == max_value);
118 assert(*resultfl.second == max_value);
119 assert(*resultlf.second == max_value);
120 assert(*resultll.second == max_value);
121
122 // None of the elements in the sequence can be less than the min, nor greater than the max
123 for (size_t i = 0; i < sz; ++i) {
124 assert(!greater(data[i], min_value));
125 assert(!greater(max_value, data[i]));
126 }
127
128 // We returned the first min element, and the first max element
129 assert(boost::algorithm::none_of_equal(data, resultff.first, min_value));
130 assert(boost::algorithm::none_of_equal(data, resultfl.first, min_value));
131 assert(boost::algorithm::none_of_equal(resultlf.first + 1, dend, min_value));
132 assert(boost::algorithm::none_of_equal(resultll.first + 1, dend, min_value));
133
134 assert(boost::algorithm::none_of_equal(data, resultff.second, max_value));
135 assert(boost::algorithm::none_of_equal(resultfl.second + 1, dend, max_value));
136 assert(boost::algorithm::none_of_equal(data, resultlf.second, max_value));
137 assert(boost::algorithm::none_of_equal(resultll.second + 1, dend, max_value));
138 }
139
140 return 0;
141 }
142