lib/fstrcmp.c

   1 /* Functions to make fuzzy comparisons between strings
   2    Copyright (C) 1988-1989, 1992-1993, 1995, 2001-2003, 2006, 2008-2016 Free
   3    Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  17
  18
  19 #include <config.h>
  20
  21 /* Specification.  */
  22 #include "fstrcmp.h"
  23
  24 #include <string.h>
  25 #include <stdbool.h>
  26 #include <stddef.h>
  27 #include <stdio.h>
  28 #include <stdint.h>
  29 #include <stdlib.h>
  30 #include <limits.h>
  31
  32 #include "glthread/lock.h"
  33 #include "glthread/tls.h"
  34 #include "minmax.h"
  35 #include "xalloc.h"
  36
  37
  38 #define ELEMENT char
  39 #define EQUAL(x,y) ((x) == (y))
  40 #define OFFSET ptrdiff_t
  41 #define EXTRA_CONTEXT_FIELDS \
  42   /* The number of edits beyond which the computation can be aborted. */ \
  43   ptrdiff_t edit_count_limit; \
  44   /* The number of edits (= number of elements inserted, plus the number of \
  45      elements deleted), temporarily minus edit_count_limit. */ \
  46   ptrdiff_t edit_count;
  47 #define NOTE_DELETE(ctxt, xoff) ctxt->edit_count++
  48 #define NOTE_INSERT(ctxt, yoff) ctxt->edit_count++
  49 #define EARLY_ABORT(ctxt) ctxt->edit_count > 0
  50 /* We don't need USE_HEURISTIC, since it is unlikely in typical uses of
  51    fstrcmp().  */
  52 #include "diffseq.h"
  53
  54
  55 /* Because fstrcmp is typically called multiple times, attempt to minimize
  56    the number of memory allocations performed.  Thus, let a call reuse the
  57    memory already allocated by the previous call, if it is sufficient.
  58    To make it multithread-safe, without need for a lock that protects the
  59    already allocated memory, store the allocated memory per thread.  Free
  60    it only when the thread exits.  */
  61
  62 static gl_tls_key_t buffer_key; /* TLS key for a 'ptrdiff_t *' */
  63 static gl_tls_key_t bufmax_key; /* TLS key for a 'uintptr_t' */
  64
  65 static void
  66 keys_init (void)
  67 {
  68   gl_tls_key_init (buffer_key, free);
  69   gl_tls_key_init (bufmax_key, NULL);
  70   /* The per-thread initial values are NULL and 0, respectively.  */
  71 }
  72
  73 /* Ensure that keys_init is called once only.  */
  74 gl_once_define(static, keys_init_once)
  75
  76
  77 /* In the code below, branch probabilities were measured by Ralf Wildenhues,
  78    by running "msgmerge LL.po coreutils.pot" with msgmerge 0.18 for many
  79    values of LL.  The probability indicates that the condition evaluates
  80    to true; whether that leads to a branch or a non-branch in the code,
  81    depends on the compiler's reordering of basic blocks.  */
  82
  83
  84 double
  85 fstrcmp_bounded (const char *string1, const char *string2, double lower_bound)
  86 {
  87   struct context ctxt;
  88   size_t xvec_length = strlen (string1);
  89   size_t yvec_length = strlen (string2);
  90   size_t length_sum = xvec_length + yvec_length;
  91   ptrdiff_t i;
  92
  93   ptrdiff_t fdiag_len;
  94   ptrdiff_t *buffer;
  95   uintptr_t bufmax;
  96
  97   /* short-circuit obvious comparisons */
  98   if (xvec_length == 0 || yvec_length == 0) /* Prob: 1% */
  99     return length_sum == 0;
 100
 101   if (! (xvec_length <= length_sum
 102          && length_sum <= MIN (UINTPTR_MAX, PTRDIFF_MAX) - 3))
 103     xalloc_die ();
 104
 105   if (lower_bound > 0)
 106     {
 107       /* Compute a quick upper bound.
 108          Each edit is an insertion or deletion of an element, hence modifies
 109          the length of the sequence by at most 1.
 110          Therefore, when starting from a sequence X and ending at a sequence Y,
 111          with N edits,  | yvec_length - xvec_length | <= N.  (Proof by
 112          induction over N.)
 113          So, at the end, we will have
 114            edit_count >= | xvec_length - yvec_length |.
 115          and hence
 116            result
 117              = (xvec_length + yvec_length - edit_count)
 118                / (xvec_length + yvec_length)
 119              <= (xvec_length + yvec_length - | yvec_length - xvec_length |)
 120                 / (xvec_length + yvec_length)
 121              = 2 * min (xvec_length, yvec_length) / (xvec_length + yvec_length).
 122        */
 123       ptrdiff_t length_min = MIN (xvec_length, yvec_length);
 124       volatile double upper_bound = 2.0 * length_min / length_sum;
 125
 126       if (upper_bound < lower_bound) /* Prob: 74% */
 127         /* Return an arbitrary value < LOWER_BOUND.  */
 128         return 0.0;
 129
 130 #if CHAR_BIT <= 8
 131       /* When X and Y are both small, avoid the overhead of setting up an
 132          array of size 256.  */
 133       if (length_sum >= 20) /* Prob: 99% */
 134         {
 135           /* Compute a less quick upper bound.
 136              Each edit is an insertion or deletion of a character, hence
 137              modifies the occurrence count of a character by 1 and leaves the
 138              other occurrence counts unchanged.
 139              Therefore, when starting from a sequence X and ending at a
 140              sequence Y, and denoting the occurrence count of C in X with
 141              OCC (X, C), with N edits,
 142                sum_C | OCC (X, C) - OCC (Y, C) | <= N.
 143              (Proof by induction over N.)
 144              So, at the end, we will have
 145                edit_count >= sum_C | OCC (X, C) - OCC (Y, C) |,
 146              and hence
 147                result
 148                  = (xvec_length + yvec_length - edit_count)
 149                    / (xvec_length + yvec_length)
 150                  <= (xvec_length + yvec_length - sum_C | OCC(X,C) - OCC(Y,C) |)
 151                     / (xvec_length + yvec_length).
 152            */
 153           ptrdiff_t occ_diff[UCHAR_MAX + 1]; /* array C -> OCC(X,C) - OCC(Y,C) */
 154           ptrdiff_t sum;
 155           double dsum;
 156
 157           /* Determine the occurrence counts in X.  */
 158           memset (occ_diff, 0, sizeof (occ_diff));
 159           for (i = xvec_length - 1; i >= 0; i--)
 160             occ_diff[(unsigned char) string1[i]]++;
 161           /* Subtract the occurrence counts in Y.  */
 162           for (i = yvec_length - 1; i >= 0; i--)
 163             occ_diff[(unsigned char) string2[i]]--;
 164           /* Sum up the absolute values.  */
 165           sum = 0;
 166           for (i = 0; i <= UCHAR_MAX; i++)
 167             {
 168               ptrdiff_t d = occ_diff[i];
 169               sum += (d >= 0 ? d : -d);
 170             }
 171
 172           dsum = sum;
 173           upper_bound = 1.0 - dsum / length_sum;
 174
 175           if (upper_bound < lower_bound) /* Prob: 66% */
 176             /* Return an arbitrary value < LOWER_BOUND.  */
 177             return 0.0;
 178         }
 179 #endif
 180     }
 181
 182   /* set the info for each string.  */
 183   ctxt.xvec = string1;
 184   ctxt.yvec = string2;
 185
 186   /* Allocate memory for fdiag and bdiag from a thread-local pool.  */
 187   fdiag_len = length_sum + 3;
 188   gl_once (keys_init_once, keys_init);
 189   buffer = gl_tls_get (buffer_key);
 190   bufmax = (uintptr_t) gl_tls_get (bufmax_key);
 191   if (fdiag_len > bufmax)
 192     {
 193       /* Need more memory.  */
 194       bufmax = 2 * bufmax;
 195       if (fdiag_len > bufmax)
 196         bufmax = fdiag_len;
 197       /* Calling xrealloc would be a waste: buffer's contents does not need
 198          to be preserved.  */
 199       free (buffer);
 200       buffer = xnmalloc (bufmax, 2 * sizeof *buffer);
 201       gl_tls_set (buffer_key, buffer);
 202       gl_tls_set (bufmax_key, (void *) (uintptr_t) bufmax);
 203     }
 204   ctxt.fdiag = buffer + yvec_length + 1;
 205   ctxt.bdiag = ctxt.fdiag + fdiag_len;
 206
 207   /* The edit_count is only ever increased.  The computation can be aborted
 208      when
 209        (xvec_length + yvec_length - edit_count) / (xvec_length + yvec_length)
 210        < lower_bound,
 211      or equivalently
 212        edit_count > (xvec_length + yvec_length) * (1 - lower_bound)
 213      or equivalently
 214        edit_count > floor((xvec_length + yvec_length) * (1 - lower_bound)).
 215      We need to add an epsilon inside the floor(...) argument, to neutralize
 216      rounding errors.  */
 217   ctxt.edit_count_limit =
 218     (lower_bound < 1.0
 219      ? (ptrdiff_t) (length_sum * (1.0 - lower_bound + 0.000001))
 220      : 0);
 221
 222   /* Now do the main comparison algorithm */
 223   ctxt.edit_count = - ctxt.edit_count_limit;
 224   if (compareseq (0, xvec_length, 0, yvec_length, &ctxt)) /* Prob: 98% */
 225     /* The edit_count passed the limit.  Hence the result would be
 226        < lower_bound.  We can return any value < lower_bound instead.  */
 227     return 0.0;
 228   ctxt.edit_count += ctxt.edit_count_limit;
 229
 230   /* The result is
 231         ((number of chars in common) / (average length of the strings)).
 232      The numerator is
 233         = xvec_length - (number of calls to NOTE_DELETE)
 234         = yvec_length - (number of calls to NOTE_INSERT)
 235         = 1/2 * (xvec_length + yvec_length - (number of edits)).
 236      This is admittedly biased towards finding that the strings are
 237      similar, however it does produce meaningful results.  */
 238   return ((double) (xvec_length + yvec_length - ctxt.edit_count)
 239           / (xvec_length + yvec_length));
 240 }