1 | /* |
2 | * Copyright 2012-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #pragma once |
18 | |
19 | #include <folly/Fingerprint.h> |
20 | #include <folly/Range.h> |
21 | #include <folly/detail/FingerprintPolynomial.h> |
22 | |
23 | namespace folly { |
24 | namespace detail { |
25 | |
26 | /** |
27 | * Slow, one-bit-at-a-time implementation of the Rabin fingerprint. |
28 | * |
29 | * This is useful as a reference implementation to test the Broder optimization |
30 | * for correctness in the unittest; it's probably too slow for any real use. |
31 | */ |
32 | template <int BITS> |
33 | class SlowFingerprint { |
34 | public: |
35 | SlowFingerprint() : poly_(FingerprintTable<BITS>::poly) { |
36 | // Use the same starting value as Fingerprint, (1 << (BITS-1)) |
37 | fp_.addXk(BITS - 1); |
38 | } |
39 | |
40 | SlowFingerprint& update8(uint8_t v) { |
41 | updateLSB(v, 8); |
42 | return *this; |
43 | } |
44 | |
45 | SlowFingerprint& update32(uint32_t v) { |
46 | updateLSB(v, 32); |
47 | return *this; |
48 | } |
49 | |
50 | SlowFingerprint& update64(uint64_t v) { |
51 | updateLSB(v, 64); |
52 | return *this; |
53 | } |
54 | |
55 | SlowFingerprint& update(const folly::StringPiece str) { |
56 | const char* p = str.start(); |
57 | for (int i = str.size(); i != 0; p++, i--) { |
58 | update8(static_cast<uint8_t>(*p)); |
59 | } |
60 | return *this; |
61 | } |
62 | |
63 | void write(uint64_t* out) const { |
64 | for (int i = 0; i < fp_.size(); ++i) { |
65 | out[i] = fp_.get(i); |
66 | } |
67 | } |
68 | |
69 | private: |
70 | void updateBit(bool bit) { |
71 | fp_.mulXmod(poly_); |
72 | if (bit) { |
73 | fp_.addXk(0); |
74 | } |
75 | } |
76 | |
77 | void updateLSB(uint64_t val, int bits) { |
78 | val <<= (64 - bits); |
79 | for (; bits != 0; --bits) { |
80 | updateBit(val & (1ULL << 63)); |
81 | val <<= 1; |
82 | } |
83 | } |
84 | |
85 | const FingerprintPolynomial<BITS - 1> poly_; |
86 | FingerprintPolynomial<BITS - 1> fp_; |
87 | }; |
88 | |
89 | } // namespace detail |
90 | } // namespace folly |
91 | |