RapidFuzz
Loading...
Searching...
No Matches
Jaro_impl.hpp
1/* SPDX-License-Identifier: MIT */
2/* Copyright © 2022-present Max Bachmann */
3
4#include <cstddef>
5#include <cstdint>
6#include <rapidfuzz/details/PatternMatchVector.hpp>
7#include <rapidfuzz/details/common.hpp>
8#include <rapidfuzz/details/distance.hpp>
9#include <rapidfuzz/details/intrinsics.hpp>
10#include <vector>
11
12namespace rapidfuzz {
13namespace detail {
14
15struct FlaggedCharsWord {
16 uint64_t P_flag;
17 uint64_t T_flag;
18};
19
20struct FlaggedCharsMultiword {
21 std::vector<uint64_t> P_flag;
22 std::vector<uint64_t> T_flag;
23};
24
25struct SearchBoundMask {
26 size_t words = 0;
27 size_t empty_words = 0;
28 uint64_t last_mask = 0;
29 uint64_t first_mask = 0;
30};
31
32static inline double jaro_calculate_similarity(size_t P_len, size_t T_len, size_t CommonChars,
33 size_t Transpositions)
34{
35 Transpositions /= 2;
36 double Sim = 0;
37 Sim += static_cast<double>(CommonChars) / static_cast<double>(P_len);
38 Sim += static_cast<double>(CommonChars) / static_cast<double>(T_len);
39 Sim += (static_cast<double>(CommonChars) - static_cast<double>(Transpositions)) /
40 static_cast<double>(CommonChars);
41 return Sim / 3.0;
42}
43
47static inline bool jaro_length_filter(size_t P_len, size_t T_len, double score_cutoff)
48{
49 if (!T_len || !P_len) return false;
50
51 double min_len = static_cast<double>(std::min(P_len, T_len));
52 double Sim = min_len / static_cast<double>(P_len) + min_len / static_cast<double>(T_len) + 1.0;
53 Sim /= 3.0;
54 return Sim >= score_cutoff;
55}
56
60static inline bool jaro_common_char_filter(size_t P_len, size_t T_len, size_t CommonChars,
61 double score_cutoff)
62{
63 if (!CommonChars) return false;
64
65 double Sim = 0;
66 Sim += static_cast<double>(CommonChars) / static_cast<double>(P_len);
67 Sim += static_cast<double>(CommonChars) / static_cast<double>(T_len);
68 Sim += 1.0;
69 Sim /= 3.0;
70 return Sim >= score_cutoff;
71}
72
73static inline size_t count_common_chars(const FlaggedCharsWord& flagged)
74{
75 return popcount(flagged.P_flag);
76}
77
78static inline size_t count_common_chars(const FlaggedCharsMultiword& flagged)
79{
80 size_t CommonChars = 0;
81 if (flagged.P_flag.size() < flagged.T_flag.size()) {
82 for (uint64_t flag : flagged.P_flag) {
83 CommonChars += popcount(flag);
84 }
85 }
86 else {
87 for (uint64_t flag : flagged.T_flag) {
88 CommonChars += popcount(flag);
89 }
90 }
91 return CommonChars;
92}
93
94template <typename PM_Vec, typename InputIt1, typename InputIt2>
95static inline FlaggedCharsWord flag_similar_characters_word(const PM_Vec& PM,
96#ifdef NDEBUG
97 const Range<InputIt1>&,
98#else
99 const Range<InputIt1>& P,
100#endif
101 const Range<InputIt2>& T, size_t Bound)
102{
103 assert(P.size() <= 64);
104 assert(T.size() <= 64);
105 assert(Bound > P.size() || P.size() - Bound <= T.size());
106
107 FlaggedCharsWord flagged = {0, 0};
108
109 uint64_t BoundMask = bit_mask_lsb<uint64_t>(Bound + 1);
110
111 size_t j = 0;
112 auto T_iter = T.begin();
113 for (; j < std::min(Bound, T.size()); ++j, ++T_iter) {
114 uint64_t PM_j = PM.get(0, *T_iter) & BoundMask & (~flagged.P_flag);
115
116 flagged.P_flag |= blsi(PM_j);
117 flagged.T_flag |= static_cast<uint64_t>(PM_j != 0) << j;
118
119 BoundMask = (BoundMask << 1) | 1;
120 }
121
122 for (; j < T.size(); ++j, ++T_iter) {
123 uint64_t PM_j = PM.get(0, *T_iter) & BoundMask & (~flagged.P_flag);
124
125 flagged.P_flag |= blsi(PM_j);
126 flagged.T_flag |= static_cast<uint64_t>(PM_j != 0) << j;
127
128 BoundMask <<= 1;
129 }
130
131 return flagged;
132}
133
134template <typename CharT>
135static inline void flag_similar_characters_step(const BlockPatternMatchVector& PM, CharT T_j,
136 FlaggedCharsMultiword& flagged, size_t j,
137 SearchBoundMask BoundMask)
138{
139 size_t j_word = j / 64;
140 size_t j_pos = j % 64;
141 size_t word = BoundMask.empty_words;
142 size_t last_word = word + BoundMask.words;
143
144 if (BoundMask.words == 1) {
145 uint64_t PM_j =
146 PM.get(word, T_j) & BoundMask.last_mask & BoundMask.first_mask & (~flagged.P_flag[word]);
147
148 flagged.P_flag[word] |= blsi(PM_j);
149 flagged.T_flag[j_word] |= static_cast<uint64_t>(PM_j != 0) << j_pos;
150 return;
151 }
152
153 if (BoundMask.first_mask) {
154 uint64_t PM_j = PM.get(word, T_j) & BoundMask.first_mask & (~flagged.P_flag[word]);
155
156 if (PM_j) {
157 flagged.P_flag[word] |= blsi(PM_j);
158 flagged.T_flag[j_word] |= 1ull << j_pos;
159 return;
160 }
161 word++;
162 }
163
164 /* unroll for better performance on long sequences when access is fast */
165 if (T_j >= 0 && T_j < 256) {
166 for (; word + 3 < last_word - 1; word += 4) {
167 uint64_t PM_j[4];
168 unroll<size_t, 4>([&](size_t i) {
169 PM_j[i] = PM.get(word + i, static_cast<uint8_t>(T_j)) & (~flagged.P_flag[word + i]);
170 });
171
172 if (PM_j[0]) {
173 flagged.P_flag[word] |= blsi(PM_j[0]);
174 flagged.T_flag[j_word] |= 1ull << j_pos;
175 return;
176 }
177 if (PM_j[1]) {
178 flagged.P_flag[word + 1] |= blsi(PM_j[1]);
179 flagged.T_flag[j_word] |= 1ull << j_pos;
180 return;
181 }
182 if (PM_j[2]) {
183 flagged.P_flag[word + 2] |= blsi(PM_j[2]);
184 flagged.T_flag[j_word] |= 1ull << j_pos;
185 return;
186 }
187 if (PM_j[3]) {
188 flagged.P_flag[word + 3] |= blsi(PM_j[3]);
189 flagged.T_flag[j_word] |= 1ull << j_pos;
190 return;
191 }
192 }
193 }
194
195 for (; word < last_word - 1; ++word) {
196 uint64_t PM_j = PM.get(word, T_j) & (~flagged.P_flag[word]);
197
198 if (PM_j) {
199 flagged.P_flag[word] |= blsi(PM_j);
200 flagged.T_flag[j_word] |= 1ull << j_pos;
201 return;
202 }
203 }
204
205 if (BoundMask.last_mask) {
206 uint64_t PM_j = PM.get(word, T_j) & BoundMask.last_mask & (~flagged.P_flag[word]);
207
208 flagged.P_flag[word] |= blsi(PM_j);
209 flagged.T_flag[j_word] |= static_cast<uint64_t>(PM_j != 0) << j_pos;
210 }
211}
212
213template <typename InputIt1, typename InputIt2>
214static inline FlaggedCharsMultiword flag_similar_characters_block(const BlockPatternMatchVector& PM,
215 const Range<InputIt1>& P,
216 const Range<InputIt2>& T, size_t Bound)
217{
218 assert(P.size() > 64 || T.size() > 64);
219 assert(Bound > P.size() || P.size() - Bound <= T.size());
220 assert(Bound >= 31);
221
222 FlaggedCharsMultiword flagged;
223 flagged.T_flag.resize(ceil_div(T.size(), 64));
224 flagged.P_flag.resize(ceil_div(P.size(), 64));
225
226 SearchBoundMask BoundMask;
227 size_t start_range = std::min(Bound + 1, P.size());
228 BoundMask.words = 1 + start_range / 64;
229 BoundMask.empty_words = 0;
230 BoundMask.last_mask = (1ull << (start_range % 64)) - 1;
231 BoundMask.first_mask = ~UINT64_C(0);
232
233 auto T_iter = T.begin();
234 for (size_t j = 0; j < T.size(); ++j, ++T_iter) {
235 flag_similar_characters_step(PM, *T_iter, flagged, j, BoundMask);
236
237 if (j + Bound + 1 < P.size()) {
238 BoundMask.last_mask = (BoundMask.last_mask << 1) | 1;
239 if (j + Bound + 2 < P.size() && BoundMask.last_mask == ~UINT64_C(0)) {
240 BoundMask.last_mask = 0;
241 BoundMask.words++;
242 }
243 }
244
245 if (j >= Bound) {
246 BoundMask.first_mask <<= 1;
247 if (BoundMask.first_mask == 0) {
248 BoundMask.first_mask = ~UINT64_C(0);
249 BoundMask.words--;
250 BoundMask.empty_words++;
251 }
252 }
253 }
254
255 return flagged;
256}
257
258template <typename PM_Vec, typename InputIt1>
259static inline size_t count_transpositions_word(const PM_Vec& PM, const Range<InputIt1>& T,
260 const FlaggedCharsWord& flagged)
261{
262 uint64_t P_flag = flagged.P_flag;
263 uint64_t T_flag = flagged.T_flag;
264
265 size_t Transpositions = 0;
266 while (T_flag) {
267 uint64_t PatternFlagMask = blsi(P_flag);
268
269 Transpositions += !(PM.get(0, T[countr_zero(T_flag)]) & PatternFlagMask);
270
271 T_flag = blsr(T_flag);
272 P_flag ^= PatternFlagMask;
273 }
274
275 return Transpositions;
276}
277
278template <typename InputIt1>
279static inline size_t count_transpositions_block(const BlockPatternMatchVector& PM, const Range<InputIt1>& T,
280 const FlaggedCharsMultiword& flagged, size_t FlaggedChars)
281{
282 size_t TextWord = 0;
283 size_t PatternWord = 0;
284 uint64_t T_flag = flagged.T_flag[TextWord];
285 uint64_t P_flag = flagged.P_flag[PatternWord];
286
287 auto T_first = T.begin();
288 size_t Transpositions = 0;
289 while (FlaggedChars) {
290 while (!T_flag) {
291 TextWord++;
292 T_first += 64;
293 T_flag = flagged.T_flag[TextWord];
294 }
295
296 while (T_flag) {
297 while (!P_flag) {
298 PatternWord++;
299 P_flag = flagged.P_flag[PatternWord];
300 }
301
302 uint64_t PatternFlagMask = blsi(P_flag);
303
304 Transpositions += !(PM.get(PatternWord, T_first[static_cast<ptrdiff_t>(countr_zero(T_flag))]) &
305 PatternFlagMask);
306
307 T_flag = blsr(T_flag);
308 P_flag ^= PatternFlagMask;
309
310 FlaggedChars--;
311 }
312 }
313
314 return Transpositions;
315}
316
317// todo cleanup the split between jaro_bounds
321static inline size_t jaro_bounds(size_t P_len, size_t T_len)
322{
323 /* since jaro uses a sliding window some parts of T/P might never be in
324 * range an can be removed ahead of time
325 */
326 size_t Bound = (T_len > P_len) ? T_len : P_len;
327 Bound /= 2;
328 if (Bound > 0) Bound--;
329
330 return Bound;
331}
332
336template <typename InputIt1, typename InputIt2>
337static inline size_t jaro_bounds(Range<InputIt1>& P, Range<InputIt2>& T)
338{
339 size_t P_len = P.size();
340 size_t T_len = T.size();
341
342 // this is currently an early exit condition
343 // if this is changed handle this below, so Bound is never below 0
344 assert(P_len != 0 || T_len != 0);
345
346 /* since jaro uses a sliding window some parts of T/P might never be in
347 * range an can be removed ahead of time
348 */
349 size_t Bound = 0;
350 if (T_len > P_len) {
351 Bound = T_len / 2 - 1;
352 if (T_len > P_len + Bound) T.remove_suffix(T_len - (P_len + Bound));
353 }
354 else {
355 Bound = P_len / 2 - 1;
356 if (P_len > T_len + Bound) P.remove_suffix(P_len - (T_len + Bound));
357 }
358 return Bound;
359}
360
361template <typename InputIt1, typename InputIt2>
362static inline double jaro_similarity(Range<InputIt1> P, Range<InputIt2> T, double score_cutoff)
363{
364 size_t P_len = P.size();
365 size_t T_len = T.size();
366
367 if (score_cutoff > 1.0) return 0.0;
368
369 if (!P_len && !T_len) return 1.0;
370
371 /* filter out based on the length difference between the two strings */
372 if (!jaro_length_filter(P_len, T_len, score_cutoff)) return 0.0;
373
374 if (P_len == 1 && T_len == 1) return static_cast<double>(P.front() == T.front());
375
376 size_t Bound = jaro_bounds(P, T);
377
378 /* common prefix never includes Transpositions */
379 size_t CommonChars = remove_common_prefix(P, T);
380 size_t Transpositions = 0;
381
382 if (P.empty() || T.empty()) {
383 /* already has correct number of common chars and transpositions */
384 }
385 else if (P.size() <= 64 && T.size() <= 64) {
386 PatternMatchVector PM(P);
387 auto flagged = flag_similar_characters_word(PM, P, T, Bound);
388 CommonChars += count_common_chars(flagged);
389
390 if (!jaro_common_char_filter(P_len, T_len, CommonChars, score_cutoff)) return 0.0;
391
392 Transpositions = count_transpositions_word(PM, T, flagged);
393 }
394 else {
395 BlockPatternMatchVector PM(P);
396 auto flagged = flag_similar_characters_block(PM, P, T, Bound);
397 size_t FlaggedChars = count_common_chars(flagged);
398 CommonChars += FlaggedChars;
399
400 if (!jaro_common_char_filter(P_len, T_len, CommonChars, score_cutoff)) return 0.0;
401
402 Transpositions = count_transpositions_block(PM, T, flagged, FlaggedChars);
403 }
404
405 double Sim = jaro_calculate_similarity(P_len, T_len, CommonChars, Transpositions);
406 return (Sim >= score_cutoff) ? Sim : 0;
407}
408
409template <typename InputIt1, typename InputIt2>
410static inline double jaro_similarity(const BlockPatternMatchVector& PM, Range<InputIt1> P, Range<InputIt2> T,
411 double score_cutoff)
412{
413 size_t P_len = P.size();
414 size_t T_len = T.size();
415
416 if (score_cutoff > 1.0) return 0.0;
417
418 if (!P_len && !T_len) return 1.0;
419
420 /* filter out based on the length difference between the two strings */
421 if (!jaro_length_filter(P_len, T_len, score_cutoff)) return 0.0;
422
423 if (P_len == 1 && T_len == 1) return static_cast<double>(P[0] == T[0]);
424
425 size_t Bound = jaro_bounds(P, T);
426
427 /* common prefix never includes Transpositions */
428 size_t CommonChars = 0;
429 size_t Transpositions = 0;
430
431 if (P.empty() || T.empty()) {
432 /* already has correct number of common chars and transpositions */
433 }
434 else if (P.size() <= 64 && T.size() <= 64) {
435 auto flagged = flag_similar_characters_word(PM, P, T, Bound);
436 CommonChars += count_common_chars(flagged);
437
438 if (!jaro_common_char_filter(P_len, T_len, CommonChars, score_cutoff)) return 0.0;
439
440 Transpositions = count_transpositions_word(PM, T, flagged);
441 }
442 else {
443 auto flagged = flag_similar_characters_block(PM, P, T, Bound);
444 size_t FlaggedChars = count_common_chars(flagged);
445 CommonChars += FlaggedChars;
446
447 if (!jaro_common_char_filter(P_len, T_len, CommonChars, score_cutoff)) return 0.0;
448
449 Transpositions = count_transpositions_block(PM, T, flagged, FlaggedChars);
450 }
451
452 double Sim = jaro_calculate_similarity(P_len, T_len, CommonChars, Transpositions);
453 return (Sim >= score_cutoff) ? Sim : 0;
454}
455
456#ifdef RAPIDFUZZ_SIMD
457
458template <typename VecType>
459struct JaroSimilaritySimdBounds {
460 size_t maxBound = 0;
461 VecType boundMaskSize;
462 VecType boundMask;
463};
464
465template <typename VecType, typename InputIt, int _lto_hack = RAPIDFUZZ_LTO_HACK>
466static inline auto jaro_similarity_prepare_bound_short_s2(const VecType* s1_lengths, Range<InputIt>& s2)
467# ifdef RAPIDFUZZ_AVX2
468 -> JaroSimilaritySimdBounds<simd_avx2::native_simd<VecType>>
469# else
470 -> JaroSimilaritySimdBounds<simd_sse2::native_simd<VecType>>
471# endif
472{
473# ifdef RAPIDFUZZ_AVX2
474 using namespace simd_avx2;
475# else
476 using namespace simd_sse2;
477# endif
478
479# ifndef RAPIDFUZZ_AVX2
480 static constexpr size_t alignment = native_simd<VecType>::alignment;
481# endif
482 static constexpr size_t vec_width = native_simd<VecType>::size;
483 assert(s2.size() <= sizeof(VecType) * 8);
484
485 JaroSimilaritySimdBounds<native_simd<VecType>> bounds;
486
487 VecType maxLen = 0;
488 // todo permutate + max to find maxLen
489 // side-note: we know only the first 8 bit are actually used
490 for (size_t i = 0; i < vec_width; ++i)
491 if (s1_lengths[i] > maxLen) maxLen = s1_lengths[i];
492
493# ifdef RAPIDFUZZ_AVX2
494 native_simd<VecType> zero(VecType(0));
495 native_simd<VecType> one(1);
496
497 native_simd<VecType> s1_lengths_simd(reinterpret_cast<const uint64_t*>(s1_lengths));
498 native_simd<VecType> s2_length_simd(static_cast<VecType>(s2.size()));
499
500 // we always know that the number does not exceed 64, so we can operate on smaller vectors if this
501 // proves to be faster
502 native_simd<VecType> boundSizes = max8(s1_lengths_simd, s2_length_simd) >> 1; // divide by two
503 // todo there could be faster options since comparisions can be relatively expensive for some vector sizes
504 boundSizes -= (boundSizes > zero) & one;
505
506 // this can never overflow even when using larger vectors for shifting here, since in the worst case of
507 // 8bit vectors this shifts by (8/2-1)*2=6 bits todo << 1 performs unneeded masking here sllv is pretty
508 // expensive for 8 / 16 bit since it has to be emulated maybe there is a better solution
509 bounds.boundMaskSize = sllv(one, boundSizes << 1) - one;
510 bounds.boundMask = sllv(one, boundSizes + one) - one;
511
512 bounds.maxBound = (s2.size() > maxLen) ? s2.size() : maxLen;
513 bounds.maxBound /= 2;
514 if (bounds.maxBound > 0) bounds.maxBound--;
515# else
516 alignas(alignment) std::array<VecType, vec_width> boundMaskSize_;
517 alignas(alignment) std::array<VecType, vec_width> boundMask_;
518
519 // todo try to find a simd implementation for sse2
520 for (size_t i = 0; i < vec_width; ++i) {
521 size_t Bound = jaro_bounds(static_cast<size_t>(s1_lengths[i]), s2.size());
522
523 if (Bound > bounds.maxBound) bounds.maxBound = Bound;
524
525 boundMaskSize_[i] = bit_mask_lsb<VecType>(2 * Bound);
526 boundMask_[i] = bit_mask_lsb<VecType>(Bound + 1);
527 }
528
529 bounds.boundMaskSize = native_simd<VecType>(reinterpret_cast<uint64_t*>(boundMaskSize_.data()));
530 bounds.boundMask = native_simd<VecType>(reinterpret_cast<uint64_t*>(boundMask_.data()));
531# endif
532
533 size_t lastRelevantChar = static_cast<size_t>(maxLen) + bounds.maxBound;
534 if (s2.size() > lastRelevantChar) s2.remove_suffix(s2.size() - lastRelevantChar);
535
536 return bounds;
537}
538
539template <typename VecType, typename InputIt, int _lto_hack = RAPIDFUZZ_LTO_HACK>
540static inline auto jaro_similarity_prepare_bound_long_s2(const VecType* s1_lengths, Range<InputIt>& s2)
541# ifdef RAPIDFUZZ_AVX2
542 -> JaroSimilaritySimdBounds<simd_avx2::native_simd<VecType>>
543# else
544 -> JaroSimilaritySimdBounds<simd_sse2::native_simd<VecType>>
545# endif
546{
547# ifdef RAPIDFUZZ_AVX2
548 using namespace simd_avx2;
549# else
550 using namespace simd_sse2;
551# endif
552
553 static constexpr size_t vec_width = native_simd<VecType>::size;
554 assert(s2.size() > sizeof(VecType) * 8);
555
556 JaroSimilaritySimdBounds<native_simd<VecType>> bounds;
557
558 VecType maxLen = 0;
559 // todo permutate + max to find maxLen
560 // side-note: we know only the first 8 bit are actually used
561 for (size_t i = 0; i < vec_width; ++i)
562 if (s1_lengths[i] > maxLen) maxLen = s1_lengths[i];
563
564 bounds.maxBound = s2.size() / 2 - 1;
565 bounds.boundMaskSize = native_simd<VecType>(bit_mask_lsb<VecType>(2 * bounds.maxBound));
566 bounds.boundMask = native_simd<VecType>(bit_mask_lsb<VecType>(bounds.maxBound + 1));
567
568 size_t lastRelevantChar = static_cast<size_t>(maxLen) + bounds.maxBound;
569 if (s2.size() > lastRelevantChar) s2.remove_suffix(s2.size() - lastRelevantChar);
570
571 return bounds;
572}
573
574template <typename VecType, typename InputIt, int _lto_hack = RAPIDFUZZ_LTO_HACK>
575static inline void
576jaro_similarity_simd_long_s2(Range<double*> scores, const detail::BlockPatternMatchVector& block,
577 VecType* s1_lengths, Range<InputIt> s2, double score_cutoff) noexcept
578{
579# ifdef RAPIDFUZZ_AVX2
580 using namespace simd_avx2;
581# else
582 using namespace simd_sse2;
583# endif
584
585 static constexpr size_t alignment = native_simd<VecType>::alignment;
586 static constexpr size_t vec_width = native_simd<VecType>::size;
587 static constexpr size_t vecs = native_simd<uint64_t>::size;
588 assert(block.size() % vecs == 0);
589 assert(s2.size() > sizeof(VecType) * 8);
590
591 struct AlignedAlloc {
592 AlignedAlloc(size_t size) : memory(rf_aligned_alloc(native_simd<VecType>::alignment, size))
593 {}
594
595 ~AlignedAlloc()
596 {
597 rf_aligned_free(memory);
598 }
599
600 void* memory = nullptr;
601 };
602
603 native_simd<VecType> zero(VecType(0));
604 native_simd<VecType> one(1);
605 size_t result_index = 0;
606
607 size_t s2_block_count = detail::ceil_div(s2.size(), sizeof(VecType) * 8);
608 AlignedAlloc memory(2 * s2_block_count * sizeof(native_simd<VecType>));
609
610 native_simd<VecType>* T_flag = static_cast<native_simd<VecType>*>(memory.memory);
611 // reuse the same memory since counter is only required in the first half of the algorithm while
612 // T_flags is required in the second half
613 native_simd<VecType>* counter = static_cast<native_simd<VecType>*>(memory.memory) + s2_block_count;
614 VecType* T_flags = static_cast<VecType*>(memory.memory) + s2_block_count * vec_width;
615
616 for (size_t cur_vec = 0; cur_vec < block.size(); cur_vec += vecs) {
617 auto s2_cur = s2;
618 auto bounds = jaro_similarity_prepare_bound_long_s2(s1_lengths + result_index, s2_cur);
619
620 native_simd<VecType> P_flag(VecType(0));
621
622 std::fill(T_flag, T_flag + detail::ceil_div(s2_cur.size(), sizeof(VecType) * 8),
623 native_simd<VecType>(VecType(0)));
624 std::fill(counter, counter + detail::ceil_div(s2_cur.size(), sizeof(VecType) * 8),
625 native_simd<VecType>(VecType(1)));
626
627 // In case s2 is longer than all of the elements in s1_lengths boundMaskSize
628 // might have all bits set and therefor the condition ((boundMask <= boundMaskSize) & one)
629 // would incorrectly always set the first bit to 1.
630 // this is solved by splitting the loop into two parts where after this boundary is reached
631 // the first bit inside boundMask is no longer set
632 size_t j = 0;
633 for (; j < std::min(bounds.maxBound, s2_cur.size()); ++j) {
634 alignas(alignment) std::array<uint64_t, vecs> stored;
635 unroll<size_t, vecs>([&](size_t i) { stored[i] = block.get(cur_vec + i, s2_cur[j]); });
636 native_simd<VecType> X(stored.data());
637 native_simd<VecType> PM_j = andnot(X & bounds.boundMask, P_flag);
638
639 P_flag |= blsi(PM_j);
640 size_t T_word_index = j / (sizeof(VecType) * 8);
641 T_flag[T_word_index] |= andnot(counter[T_word_index], (PM_j == zero));
642
643 counter[T_word_index] = counter[T_word_index] << 1;
644 bounds.boundMask = (bounds.boundMask << 1) | ((bounds.boundMask <= bounds.boundMaskSize) & one);
645 }
646
647 for (; j < s2_cur.size(); ++j) {
648 alignas(alignment) std::array<uint64_t, vecs> stored;
649 unroll<size_t, vecs>([&](size_t i) { stored[i] = block.get(cur_vec + i, s2_cur[j]); });
650 native_simd<VecType> X(stored.data());
651 native_simd<VecType> PM_j = andnot(X & bounds.boundMask, P_flag);
652
653 P_flag |= blsi(PM_j);
654 size_t T_word_index = j / (sizeof(VecType) * 8);
655 T_flag[T_word_index] |= andnot(counter[T_word_index], (PM_j == zero));
656
657 counter[T_word_index] = counter[T_word_index] << 1;
658 bounds.boundMask = bounds.boundMask << 1;
659 }
660
661 auto counts = popcount(P_flag);
662 alignas(alignment) std::array<VecType, vec_width> P_flags;
663 P_flag.store(P_flags.data());
664
665 for (size_t i = 0; i < detail::ceil_div(s2_cur.size(), sizeof(VecType) * 8); ++i)
666 T_flag[i].store(T_flags + i * vec_width);
667
668 for (size_t i = 0; i < vec_width; ++i) {
669 size_t CommonChars = static_cast<size_t>(counts[i]);
670 if (!jaro_common_char_filter(static_cast<size_t>(s1_lengths[result_index]), s2.size(),
671 CommonChars, score_cutoff))
672 {
673 scores[result_index] = 0.0;
674 result_index++;
675 continue;
676 }
677
678 VecType P_flag_cur = P_flags[i];
679 size_t Transpositions = 0;
680
681 static constexpr size_t vecs_per_word = vec_width / vecs;
682 size_t cur_block = i / vecs_per_word;
683 size_t offset = sizeof(VecType) * 8 * (i % vecs_per_word);
684
685 {
686 size_t T_word_index = 0;
687 VecType T_flag_cur = T_flags[T_word_index * vec_width + i];
688 while (P_flag_cur) {
689 while (!T_flag_cur) {
690 ++T_word_index;
691 T_flag_cur = T_flags[T_word_index * vec_width + i];
692 }
693
694 VecType PatternFlagMask = blsi(P_flag_cur);
695
696 uint64_t PM_j =
697 block.get(cur_vec + cur_block,
698 s2[countr_zero(T_flag_cur) + T_word_index * sizeof(VecType) * 8]);
699 Transpositions += !(PM_j & (static_cast<uint64_t>(PatternFlagMask) << offset));
700
701 T_flag_cur = blsr(T_flag_cur);
702 P_flag_cur ^= PatternFlagMask;
703 }
704 }
705
706 double Sim = jaro_calculate_similarity(static_cast<size_t>(s1_lengths[result_index]), s2.size(),
707 CommonChars, Transpositions);
708
709 scores[result_index] = (Sim >= score_cutoff) ? Sim : 0;
710 result_index++;
711 }
712 }
713}
714
715template <typename VecType, typename InputIt, int _lto_hack = RAPIDFUZZ_LTO_HACK>
716static inline void
717jaro_similarity_simd_short_s2(Range<double*> scores, const detail::BlockPatternMatchVector& block,
718 VecType* s1_lengths, Range<InputIt> s2, double score_cutoff) noexcept
719{
720# ifdef RAPIDFUZZ_AVX2
721 using namespace simd_avx2;
722# else
723 using namespace simd_sse2;
724# endif
725
726 static constexpr size_t alignment = native_simd<VecType>::alignment;
727 static constexpr size_t vec_width = native_simd<VecType>::size;
728 static constexpr size_t vecs = native_simd<uint64_t>::size;
729 assert(block.size() % vecs == 0);
730 assert(s2.size() <= sizeof(VecType) * 8);
731
732 native_simd<VecType> zero(VecType(0));
733 native_simd<VecType> one(1);
734 size_t result_index = 0;
735
736 for (size_t cur_vec = 0; cur_vec < block.size(); cur_vec += vecs) {
737 auto s2_cur = s2;
738 auto bounds = jaro_similarity_prepare_bound_short_s2(s1_lengths + result_index, s2_cur);
739
740 native_simd<VecType> P_flag(VecType(0));
741 native_simd<VecType> T_flag(VecType(0));
742 native_simd<VecType> counter(VecType(1));
743
744 // In case s2 is longer than all of the elements in s1_lengths boundMaskSize
745 // might have all bits set and therefor the condition ((boundMask <= boundMaskSize) & one)
746 // would incorrectly always set the first bit to 1.
747 // this is solved by splitting the loop into two parts where after this boundary is reached
748 // the first bit inside boundMask is no longer set
749 size_t j = 0;
750 for (; j < std::min(bounds.maxBound, s2_cur.size()); ++j) {
751 alignas(alignment) std::array<uint64_t, vecs> stored;
752 unroll<size_t, vecs>([&](size_t i) { stored[i] = block.get(cur_vec + i, s2_cur[j]); });
753 native_simd<VecType> X(stored.data());
754 native_simd<VecType> PM_j = andnot(X & bounds.boundMask, P_flag);
755
756 P_flag |= blsi(PM_j);
757 T_flag |= andnot(counter, (PM_j == zero));
758
759 counter = counter << 1;
760 bounds.boundMask = (bounds.boundMask << 1) | ((bounds.boundMask <= bounds.boundMaskSize) & one);
761 }
762
763 for (; j < s2_cur.size(); ++j) {
764 alignas(alignment) std::array<uint64_t, vecs> stored;
765 unroll<size_t, vecs>([&](size_t i) { stored[i] = block.get(cur_vec + i, s2_cur[j]); });
766 native_simd<VecType> X(stored.data());
767 native_simd<VecType> PM_j = andnot(X & bounds.boundMask, P_flag);
768
769 P_flag |= blsi(PM_j);
770 T_flag |= andnot(counter, (PM_j == zero));
771
772 counter = counter << 1;
773 bounds.boundMask = bounds.boundMask << 1;
774 }
775
776 auto counts = popcount(P_flag);
777 alignas(alignment) std::array<VecType, vec_width> P_flags;
778 P_flag.store(P_flags.data());
779 alignas(alignment) std::array<VecType, vec_width> T_flags;
780 T_flag.store(T_flags.data());
781 for (size_t i = 0; i < vec_width; ++i) {
782 size_t CommonChars = static_cast<size_t>(counts[i]);
783 if (!jaro_common_char_filter(static_cast<size_t>(s1_lengths[result_index]), s2.size(),
784 CommonChars, score_cutoff))
785 {
786 scores[result_index] = 0.0;
787 result_index++;
788 continue;
789 }
790
791 VecType P_flag_cur = P_flags[i];
792 VecType T_flag_cur = T_flags[i];
793 size_t Transpositions = 0;
794
795 static constexpr size_t vecs_per_word = vec_width / vecs;
796 size_t cur_block = i / vecs_per_word;
797 size_t offset = sizeof(VecType) * 8 * (i % vecs_per_word);
798 while (P_flag_cur) {
799 VecType PatternFlagMask = blsi(P_flag_cur);
800
801 uint64_t PM_j = block.get(cur_vec + cur_block, s2[countr_zero(T_flag_cur)]);
802 Transpositions += !(PM_j & (static_cast<uint64_t>(PatternFlagMask) << offset));
803
804 T_flag_cur = blsr(T_flag_cur);
805 P_flag_cur ^= PatternFlagMask;
806 }
807
808 double Sim = jaro_calculate_similarity(static_cast<size_t>(s1_lengths[result_index]), s2.size(),
809 CommonChars, Transpositions);
810
811 scores[result_index] = (Sim >= score_cutoff) ? Sim : 0;
812 result_index++;
813 }
814 }
815}
816
817template <typename VecType, typename InputIt, int _lto_hack = RAPIDFUZZ_LTO_HACK>
818static inline void jaro_similarity_simd(Range<double*> scores, const detail::BlockPatternMatchVector& block,
819 VecType* s1_lengths, size_t s1_lengths_size, const Range<InputIt>& s2,
820 double score_cutoff) noexcept
821{
822 if (score_cutoff > 1.0) {
823 for (size_t i = 0; i < s1_lengths_size; i++)
824 scores[i] = 0.0;
825
826 return;
827 }
828
829 if (s2.empty()) {
830 for (size_t i = 0; i < s1_lengths_size; i++)
831 scores[i] = s1_lengths[i] ? 0.0 : 1.0;
832
833 return;
834 }
835
836 if (s2.size() > sizeof(VecType) * 8)
837 return jaro_similarity_simd_long_s2(scores, block, s1_lengths, s2, score_cutoff);
838 else
839 return jaro_similarity_simd_short_s2(scores, block, s1_lengths, s2, score_cutoff);
840}
841
842#endif /* RAPIDFUZZ_SIMD */
843
844class Jaro : public SimilarityBase<Jaro, double, 0, 1> {
845 friend SimilarityBase<Jaro, double, 0, 1>;
846 friend NormalizedMetricBase<Jaro>;
847
848 template <typename InputIt1, typename InputIt2>
849 static double maximum(const Range<InputIt1>&, const Range<InputIt2>&) noexcept
850 {
851 return 1.0;
852 }
853
854 template <typename InputIt1, typename InputIt2>
855 static double _similarity(const Range<InputIt1>& s1, const Range<InputIt2>& s2, double score_cutoff,
856 double)
857 {
858 return jaro_similarity(s1, s2, score_cutoff);
859 }
860};
861
862} // namespace detail
863} // namespace rapidfuzz
Generated by doxygen 1.9.8