1 // Copyright (c) 2021 Google Inc.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "test/fuzzers/random_generator.h"
16
17 #include <algorithm>
18 #include <array>
19 #include <cassert>
20
21 namespace spvtools {
22 namespace fuzzers {
23
24 namespace {
25 /// Generate integer from uniform distribution
26 /// @tparam I - integer type
27 /// @param engine - random number engine to use
28 /// @param lower - Lower bound of integer generated
29 /// @param upper - Upper bound of integer generated
30 /// @returns i, where lower <= i < upper
31 template <typename I>
RandomUInt(std::mt19937_64 * engine,I lower,I upper)32 I RandomUInt(std::mt19937_64* engine, I lower, I upper) {
33 assert(lower < upper && "|lower| must be stictly less than |upper|");
34 return std::uniform_int_distribution<I>(lower, upper - 1)(*engine);
35 }
36
37 /// Helper for obtaining a seed bias value for HashCombine with a bit-width
38 /// dependent on the size of size_t.
39 template <int SIZE_OF_SIZE_T>
40 struct HashCombineOffset {};
41 /// Specialization of HashCombineOffset for size_t == 4.
42 template <>
43 struct HashCombineOffset<4> {
44 /// @returns the seed bias value for HashCombine()
valuespvtools::fuzzers::__anon9fd93a7f0111::HashCombineOffset45 static constexpr inline uint32_t value() {
46 return 0x9e3779b9; // Fractional portion of Golden Ratio, suggested by
47 // Linux Kernel and Knuth's Art of Computer Programming
48 }
49 };
50 /// Specialization of HashCombineOffset for size_t == 8.
51 template <>
52 struct HashCombineOffset<8> {
53 /// @returns the seed bias value for HashCombine()
valuespvtools::fuzzers::__anon9fd93a7f0111::HashCombineOffset54 static constexpr inline uint64_t value() {
55 return 0x9e3779b97f4a7c16; // Fractional portion of Golden Ratio, suggested
56 // by Linux Kernel and Knuth's Art of Computer
57 // Programming
58 }
59 };
60
61 /// HashCombine "hashes" together an existing hash and hashable values.
62 template <typename T>
HashCombine(size_t * hash,const T & value)63 void HashCombine(size_t* hash, const T& value) {
64 constexpr size_t offset = HashCombineOffset<sizeof(size_t)>::value();
65 *hash ^= std::hash<T>()(value) + offset + (*hash << 6) + (*hash >> 2);
66 }
67
68 /// Calculate the hash for the contents of a C-style data buffer
69 /// @param data - pointer to buffer to be hashed
70 /// @param size - number of elements in buffer
71 /// @returns hash of the data in the buffer
HashBuffer(const uint8_t * data,const size_t size)72 size_t HashBuffer(const uint8_t* data, const size_t size) {
73 size_t hash =
74 static_cast<size_t>(0xCA8945571519E991); // seed with an arbitrary prime
75 HashCombine(&hash, size);
76 for (size_t i = 0; i < size; i++) {
77 HashCombine(&hash, data[i]);
78 }
79 return hash;
80 }
81
82 } // namespace
83
RandomGenerator(uint64_t seed)84 RandomGenerator::RandomGenerator(uint64_t seed) : engine_(seed) {}
85
RandomGenerator(const uint8_t * data,size_t size)86 RandomGenerator::RandomGenerator(const uint8_t* data, size_t size) {
87 RandomGenerator(RandomGenerator::CalculateSeed(data, size));
88 }
89
GetTargetEnv()90 spv_target_env RandomGenerator::GetTargetEnv() {
91 spv_target_env result;
92
93 // Need to check that the generated value isn't for a deprecated target env.
94 do {
95 result = static_cast<spv_target_env>(
96 RandomUInt(&engine_, 0u, static_cast<unsigned int>(SPV_ENV_MAX)));
97 } while (!spvIsValidEnv(result));
98
99 return result;
100 }
101
GetUInt32(uint32_t lower,uint32_t upper)102 uint32_t RandomGenerator::GetUInt32(uint32_t lower, uint32_t upper) {
103 return RandomUInt(&engine_, lower, upper);
104 }
105
GetUInt32(uint32_t bound)106 uint32_t RandomGenerator::GetUInt32(uint32_t bound) {
107 assert(bound > 0 && "|bound| must be greater than 0");
108 return RandomUInt(&engine_, 0u, bound);
109 }
110
CalculateSeed(const uint8_t * data,size_t size)111 uint64_t RandomGenerator::CalculateSeed(const uint8_t* data, size_t size) {
112 assert(data != nullptr && "|data| must be !nullptr");
113
114 // Number of bytes we want to skip at the start of data for the hash.
115 // Fewer bytes may be skipped when `size` is small.
116 // Has lower precedence than kHashDesiredMinBytes.
117 static const int64_t kHashDesiredLeadingSkipBytes = 5;
118 // Minimum number of bytes we want to use in the hash.
119 // Used for short buffers.
120 static const int64_t kHashDesiredMinBytes = 4;
121 // Maximum number of bytes we want to use in the hash.
122 static const int64_t kHashDesiredMaxBytes = 32;
123 int64_t size_i64 = static_cast<int64_t>(size);
124 int64_t hash_begin_i64 =
125 std::min(kHashDesiredLeadingSkipBytes,
126 std::max<int64_t>(size_i64 - kHashDesiredMinBytes, 0));
127 int64_t hash_end_i64 =
128 std::min(hash_begin_i64 + kHashDesiredMaxBytes, size_i64);
129 size_t hash_begin = static_cast<size_t>(hash_begin_i64);
130 size_t hash_size = static_cast<size_t>(hash_end_i64) - hash_begin;
131 return HashBuffer(data + hash_begin, hash_size);
132 }
133
134 } // namespace fuzzers
135 } // namespace spvtools
136