| // Copyright 2023 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. |
| |
| #ifndef THIRD_PARTY_CENTIPEDE_ROLLING_HASH_H_ |
| #define THIRD_PARTY_CENTIPEDE_ROLLING_HASH_H_ |
| |
| #include <cstdint> |
| |
| #include "absl/base/const_init.h" |
| |
| namespace centipede { |
| |
| // Computes a rolling hash for a fixed-size window in a sequence of 32-bit ints. |
| // Inspired by https://en.wikipedia.org/wiki/Rolling_hash#Rabin_fingerprint. |
| // |
| // Objects of this class must be created as global or TLS. |
| // The typical non-test usage is to create on TLS. |
| // Which is why we pass `window_size` via a separate function. |
| // There is no CTOR, the objects are zero-initialized. |
| // We currently do not use a CTOR with absl::ConstInitType so that the objects |
| // can be declared as __thread. |
| // TODO(kcc): reconsider once we can use c++20; the current warning is |
| // error: constexpr constructor that does not initialize all members is a |
| // C++20 extension |
| class RollingHash { |
| public: |
| // Resets the object to use the specified window size. |
| void Reset(size_t window_size) { |
| hash_ = 0; |
| multiplier_power_window_size_ = 1; |
| for (size_t i = 0; i < window_size; ++i) { |
| multiplier_power_window_size_ *= kMultiplier; |
| } |
| } |
| |
| // Updates the hash by adding `add` and removing `remove`. |
| uint32_t Update(uint32_t hash, uint32_t add, uint32_t remove) const { |
| // Intermediate computations are done in 64-bit. |
| return hash * kMultiplier - remove * multiplier_power_window_size_ + add; |
| } |
| |
| void Update(uint32_t add, uint32_t remove) { |
| hash_ = Update(hash_, add, remove); |
| } |
| |
| // Returns the hash as a 32-bit int. |
| uint32_t Hash() const { return hash_; } |
| |
| // Test-only function to use as a slow but simple reference implementation. |
| // Adds `add` to `hash`. |
| static uint32_t TestOnlyUpdate(uint32_t hash, uint32_t add) { |
| return hash * kMultiplier + add; |
| } |
| |
| private: |
| // A prime number less than 2**32 (https://t5k.org/lists/2small/0bit.html). |
| static constexpr uint64_t kMultiplier = (1ULL << 32) - 267; |
| |
| uint32_t hash_; |
| uint64_t multiplier_power_window_size_; // kMultiplier ** window_size. |
| }; |
| |
| } // namespace centipede |
| |
| #endif // THIRD_PARTY_CENTIPEDE_ROLLING_HASH_H_ |