Debian Codegraph @

src/appindexer/fuzzer/fuzzer.c

raw
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 }