| 1 |
#include <limits.h> |
| 2 |
#include <stdlib.h> |
| 3 |
#include <string.h> |
| 4 |
|
| 5 |
#include "fuzzer.h" |
| 6 |
|
| 7 |
/** |
| 8 |
* fuzzer_get_fuzzy_score: |
| 9 |
* @text: the text to compare to |
| 10 |
* @pattern: the text being used to search |
| 11 |
* @max_distance: the maximum distance between the strings to still be considered equal |
| 12 |
* |
| 13 |
* Fuzzily matches two strings using the Fuzzy Bitap Algorithm. |
| 14 |
* |
| 15 |
* The algorithm tells whether a given text contains a substring |
| 16 |
* which is "approximately equal" to a given pattern, where approximate |
| 17 |
* equality is defined in terms of Levenshtein distance. |
| 18 |
* |
| 19 |
* The algorithm begins by precomputing a set of bitmasks containing one |
| 20 |
* bit for each element of the pattern. Then it is able to do most of the |
| 21 |
* work with bitwise operations, which are extremely fast. |
| 22 |
* |
| 23 |
* Adapted from here: https://www.programmingalgorithms.com/algorithm/fuzzy-bitap-algorithm/ |
| 24 |
* |
| 25 |
* Return value: a score based on the closeness of the texts |
| 26 |
*/ |
| 27 |
gint fuzzer_get_fuzzy_score(const gchar* text, const gchar* pattern, gint max_distance) { |
| 28 |
gint result = -1; |
| 29 |
gint pattern_length; |
| 30 |
guint64* bit_array = NULL; |
| 31 |
guint64 pattern_mask[CHAR_MAX + 1]; |
| 32 |
gint i, d; |
| 33 |
|
| 34 |
g_return_val_if_fail(text != NULL, -1); |
| 35 |
g_return_val_if_fail(pattern != NULL, -1); |
| 36 |
|
| 37 |
pattern_length = strlen(pattern); |
| 38 |
|
| 39 |
if (g_strcmp0(pattern, "") == 0) return 0; // Pattern is empty |
| 40 |
if (pattern_length > 31) return -1; // Error: pattern too long |
| 41 |
|
| 42 |
/* Initialize the bit array */ |
| 43 |
bit_array = (guint64*) malloc((max_distance + 1) * sizeof(*bit_array)); |
| 44 |
for (i = 0; i <= max_distance; ++i) bit_array[i] = ~1; |
| 45 |
|
| 46 |
/* Initialize the pattern masks */ |
| 47 |
for (i = 0; i <= 127; ++i) pattern_mask[i] = ~0; |
| 48 |
|
| 49 |
for (i = 0; i < pattern_length; ++i) pattern_mask[pattern[i]] &= ~(1UL << i); |
| 50 |
|
| 51 |
/* Calculating the score */ |
| 52 |
|
| 53 |
for (i = 0; text[i] != '\0'; ++i) { |
| 54 |
/* Update the bit arrays */ |
| 55 |
guint64 old_Rd1 = bit_array[0]; |
| 56 |
|
| 57 |
bit_array[0] |= pattern_mask[text[i]]; |
| 58 |
bit_array[0] <<= 1; |
| 59 |
|
| 60 |
for (d = 1; d <= max_distance; ++d) { |
| 61 |
guint64 tmp = bit_array[d]; |
| 62 |
|
| 63 |
/* Only look for substitutions */ |
| 64 |
bit_array[d] = (old_Rd1 & (bit_array[d] | pattern_mask[text[i]])) << 1; |
| 65 |
old_Rd1 = tmp; |
| 66 |
} |
| 67 |
|
| 68 |
if (0 == (bit_array[max_distance] & (1UL << pattern_length))) { |
| 69 |
result = (i - pattern_length) + 1; |
| 70 |
break; |
| 71 |
} |
| 72 |
} |
| 73 |
|
| 74 |
g_free(bit_array); |
| 75 |
|
| 76 |
return result; |
| 77 |
} |