#include "levenshtein.h" #include #include #include /* * This function implements the Damerau-Levenshtein algorithm to * calculate a distance between strings. * * Basically, it says how many letters need to be swapped, substituted, * deleted from, or added to string1, at least, to get string2. * * The idea is to build a distance matrix for the substrings of both * strings. To avoid a large space complexity, only the last three rows * are kept in memory (if swaps had the same or higher cost as one deletion * plus one insertion, only two rows would be needed). * * At any stage, "i + 1" denotes the length of the current substring of * string1 that the distance is calculated for. * * row2 holds the current row, row1 the previous row (i.e. for the substring * of string1 of length "i"), and row0 the row before that. * * In other words, at the start of the big loop, row2[j + 1] contains the * Damerau-Levenshtein distance between the substring of string1 of length * "i" and the substring of string2 of length "j + 1". * * All the big loop does is determine the partial minimum-cost paths. * * It does so by calculating the costs of the path ending in characters * i (in string1) and j (in string2), respectively, given that the last * operation is a substition, a swap, a deletion, or an insertion. * * This implementation allows the costs to be weighted: * * - w (as in "sWap") * - s (as in "Substitution") * - a (for insertion, AKA "Add") * - d (as in "Deletion") * * Note that this algorithm calculates a distance _iff_ d == a. */ int levenshtein(const char *string1, const char *string2, int w, int s, int a, int d) { int len1 = strlen(string1), len2 = strlen(string2); int *row0 = malloc(sizeof(int) * (len2 + 1)); int *row1 = malloc(sizeof(int) * (len2 + 1)); int *row2 = malloc(sizeof(int) * (len2 + 1)); int i, j; for (j = 0; j <= len2; j++) row1[j] = j * a; for (i = 0; i < len1; i++) { int *dummy; row2[0] = (i + 1) * d; for (j = 0; j < len2; j++) { /* substitution */ row2[j + 1] = row1[j] + s * (string1[i] != string2[j]); /* swap */ if (i > 0 && j > 0 && string1[i - 1] == string2[j] && string1[i] == string2[j - 1] && row2[j + 1] > row0[j - 1] + w) row2[j + 1] = row0[j - 1] + w; /* deletion */ if (row2[j + 1] > row1[j + 1] + d) row2[j + 1] = row1[j + 1] + d; /* insertion */ if (row2[j + 1] > row2[j] + a) row2[j + 1] = row2[j] + a; } dummy = row0; row0 = row1; row1 = row2; row2 = dummy; } i = row1[len2]; free(row0); free(row1); free(row2); return i; } tion value='committer'>committer

path: root/sound/usb/proc.h

diff options

author	Benjamin Herrenschmidt <benh@kernel.crashing.org>	2017-02-03 17:10:28 +1100
committer	Michael Ellerman <mpe@ellerman.id.au>	2017-02-08 23:36:29 +1100
commit	d7df2443cd5f67fc6ee7c05a88e4996e8177f91b (patch)
tree	098a7c0ca4fceb8a65cb1f693c9d71990388933d /sound/usb/proc.h
parent	a0615a16f7d0ceb5804d295203c302d496d8ee91 (diff)

powerpc/mm: Fix spurrious segfaults on radix with autonuma

When autonuma (Automatic NUMA balancing) marks a PTE inaccessible it clears all the protection bits but leave the PTE valid. With the Radix MMU, an attempt at executing from such a PTE will take a fault with bit 35 of SRR1 set "SRR1_ISI_N_OR_G". It is thus incorrect to treat all such faults as errors. We should pass them to handle_mm_fault() for autonuma to deal with. The case of pages that are really not executable is handled by the existing test for VM_EXEC further down. That leaves us with catching the kernel attempts at executing user pages. We can catch that earlier, even before we do find_vma. It is never valid on powerpc for the kernel to take an exec fault to begin with. So fold that test with the existing test for the kernel faulting on kernel addresses to bail out early. Fixes: 1d18ad026844 ("powerpc/mm: Detect instruction fetch denied and report") Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org> Reviewed-by: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com> Acked-by: Balbir Singh <bsingharora@gmail.com> Signed-off-by: Michael Ellerman <mpe@ellerman.id.au>

Diffstat (limited to 'sound/usb/proc.h')