| // Copyright 2022 The Centipede Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // This library defines the concepts "fuzzing feature" and "feature domain". |
| // It is used by Centipede, and it can be used by fuzz runners to |
| // define their features in a way most friendly to Centipede. |
| // Fuzz runners do not have to use this file nor to obey the rules defined here. |
| // But using this file and following its rules is the simplest way if you want |
| // Centipede to understand the details about the features generated by the |
| // runner. |
| // |
| // This library must not depend on anything other than libc so that fuzz targets |
| // using it doesn't gain redundant coverage. For the same reason this library |
| // uses raw __builtin_trap instead of CHECKs. |
| // We make an exception for <algorithm> for std::sort/std::unique, |
| // since <algorithm> is very lightweight. |
| // This library is also header-only, with all functions defined as inline. |
| |
| #ifndef THIRD_PARTY_CENTIPEDE_HASHED_RING_BUFFER_H_ |
| #define THIRD_PARTY_CENTIPEDE_HASHED_RING_BUFFER_H_ |
| |
| // WARNING!!!: Be very careful with what STL headers or other dependencies you |
| // add here. This header needs to remain mostly bare-bones so that we can |
| // include it into runner. |
| #include <cstddef> |
| #include <cstdint> |
| |
| #include "./centipede/rolling_hash.h" |
| |
| namespace centipede { |
| |
| // Fixed-size ring buffer that maintains a 32-bit hash of its elements. |
| // Create objects of this type as zero-initialized globals or thread-locals. |
| // In a zero-initialized object all values and the hash are zero. |
| // `kSize` indicates the maximum possible size for the ring-buffer. |
| // The actual size is passed to Reset(). |
| template <size_t kSize> |
| class HashedRingBuffer { |
| public: |
| // Adds `new_item` and returns the new hash of the entire collection. |
| // Evicts an old item. |
| // Returns the new hash. |
| uint32_t push(size_t new_item) { |
| size_t new_pos = last_added_pos_ + 1; |
| if (new_pos >= size_) new_pos = 0; |
| size_t evicted_item = buffer_[new_pos]; |
| buffer_[new_pos] = new_item; |
| hash_.Update(new_item, evicted_item); |
| last_added_pos_ = new_pos; |
| return hash_.Hash(); |
| } |
| |
| // Returns the current hash. |
| uint32_t hash() const { return hash_.Hash(); } |
| |
| // Resets the current state, sets the ring buffer size to `size_` (<= kSize). |
| void Reset(size_t size) { |
| memset(this, 0, sizeof(*this)); |
| if (size > kSize) __builtin_trap(); // can't use CHECK in the runner. |
| size_ = size; |
| hash_.Reset(size); |
| } |
| |
| private: |
| size_t buffer_[kSize]; // All elements. |
| size_t last_added_pos_; // Position of the last added element. |
| size_t size_; // Real size of the ring buffer, <= kSize. |
| RollingHash hash_; |
| }; |
| |
| } // namespace centipede |
| |
| #endif // THIRD_PARTY_CENTIPEDE_HASHED_RING_BUFFER_H_ |