lib/fstrcmp.c

   1 /* Functions to make fuzzy comparisons between strings
   2    Copyright (C) 1988-1989, 1992-1993, 1995, 2001-2003, 2006, 2008-2020 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 <https://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 void
  77 fstrcmp_free_resources (void)
  78 {
  79   ptrdiff_t *buffer;
  80
  81   gl_once (keys_init_once, keys_init);
  82   buffer = gl_tls_get (buffer_key);
  83   if (buffer != NULL)
  84     {
  85       gl_tls_set (buffer_key, NULL);
  86       gl_tls_set (bufmax_key, (void *) (uintptr_t) 0);
  87       free (buffer);
  88     }
  89 }
  90
  91
  92 /* In the code below, branch probabilities were measured by Ralf Wildenhues,
  93    by running "msgmerge LL.po coreutils.pot" with msgmerge 0.18 for many
  94    values of LL.  The probability indicates that the condition evaluates
  95    to true; whether that leads to a branch or a non-branch in the code,
  96    depends on the compiler's reordering of basic blocks.  */
  97
  98
  99 double
 100 fstrcmp_bounded (const char *string1, const char *string2, double lower_bound)
 101 {
 102   struct context ctxt;
 103   size_t xvec_length = strlen (string1);
 104   size_t yvec_length = strlen (string2);
 105   size_t length_sum = xvec_length + yvec_length;
 106   ptrdiff_t i;
 107
 108   ptrdiff_t fdiag_len;
 109   ptrdiff_t *buffer;
 110   uintptr_t bufmax;
 111
 112   /* short-circuit obvious comparisons */
 113   if (xvec_length == 0 || yvec_length == 0) /* Prob: 1% */
 114     return length_sum == 0;
 115
 116   if (! (xvec_length <= length_sum
 117          && length_sum <= MIN (UINTPTR_MAX, PTRDIFF_MAX) - 3))
 118     xalloc_die ();
 119
 120   if (lower_bound > 0)
 121     {
 122       /* Compute a quick upper bound.
 123          Each edit is an insertion or deletion of an element, hence modifies
 124          the length of the sequence by at most 1.
 125          Therefore, when starting from a sequence X and ending at a sequence Y,
 126          with N edits,  | yvec_length - xvec_length | <= N.  (Proof by
 127          induction over N.)
 128          So, at the end, we will have
 129            edit_count >= | xvec_length - yvec_length |.
 130          and hence
 131            result
 132              = (xvec_length + yvec_length - edit_count)
 133                / (xvec_length + yvec_length)
 134              <= (xvec_length + yvec_length - | yvec_length - xvec_length |)
 135                 / (xvec_length + yvec_length)
 136              = 2 * min (xvec_length, yvec_length) / (xvec_length + yvec_length).
 137        */
 138       ptrdiff_t length_min = MIN (xvec_length, yvec_length);
 139       volatile double upper_bound = 2.0 * length_min / length_sum;
 140
 141       if (upper_bound < lower_bound) /* Prob: 74% */
 142         /* Return an arbitrary value < LOWER_BOUND.  */
 143         return 0.0;
 144
 145 #if CHAR_BIT <= 8
 146       /* When X and Y are both small, avoid the overhead of setting up an
 147          array of size 256.  */
 148       if (length_sum >= 20) /* Prob: 99% */
 149         {
 150           /* Compute a less quick upper bound.
 151              Each edit is an insertion or deletion of a character, hence
 152              modifies the occurrence count of a character by 1 and leaves the
 153              other occurrence counts unchanged.
 154              Therefore, when starting from a sequence X and ending at a
 155              sequence Y, and denoting the occurrence count of C in X with
 156              OCC (X, C), with N edits,
 157                sum_C | OCC (X, C) - OCC (Y, C) | <= N.
 158              (Proof by induction over N.)
 159              So, at the end, we will have
 160                edit_count >= sum_C | OCC (X, C) - OCC (Y, C) |,
 161              and hence
 162                result
 163                  = (xvec_length + yvec_length - edit_count)
 164                    / (xvec_length + yvec_length)
 165                  <= (xvec_length + yvec_length - sum_C | OCC(X,C) - OCC(Y,C) |)
 166                     / (xvec_length + yvec_length).
 167            */
 168           ptrdiff_t occ_diff[UCHAR_MAX + 1]; /* array C -> OCC(X,C) - OCC(Y,C) */
 169           ptrdiff_t sum;
 170           double dsum;
 171
 172           /* Determine the occurrence counts in X.  */
 173           memset (occ_diff, 0, sizeof (occ_diff));
 174           for (i = xvec_length - 1; i >= 0; i--)
 175             occ_diff[(unsigned char) string1[i]]++;
 176           /* Subtract the occurrence counts in Y.  */
 177           for (i = yvec_length - 1; i >= 0; i--)
 178             occ_diff[(unsigned char) string2[i]]--;
 179           /* Sum up the absolute values.  */
 180           sum = 0;
 181           for (i = 0; i <= UCHAR_MAX; i++)
 182             {
 183               ptrdiff_t d = occ_diff[i];
 184               sum += (d >= 0 ? d : -d);
 185             }
 186
 187           dsum = sum;
 188           upper_bound = 1.0 - dsum / length_sum;
 189
 190           if (upper_bound < lower_bound) /* Prob: 66% */
 191             /* Return an arbitrary value < LOWER_BOUND.  */
 192             return 0.0;
 193         }
 194 #endif
 195     }
 196
 197   /* set the info for each string.  */
 198   ctxt.xvec = string1;
 199   ctxt.yvec = string2;
 200
 201   /* Set TOO_EXPENSIVE to be approximate square root of input size,
 202      bounded below by 4096.  */
 203   ctxt.too_expensive = 1;
 204   for (i = xvec_length + yvec_length; i != 0; i >>= 2)
 205     ctxt.too_expensive <<= 1;
 206   if (ctxt.too_expensive < 4096)
 207     ctxt.too_expensive = 4096;
 208
 209   /* Allocate memory for fdiag and bdiag from a thread-local pool.  */
 210   fdiag_len = length_sum + 3;
 211   gl_once (keys_init_once, keys_init);
 212   buffer = gl_tls_get (buffer_key);
 213   bufmax = (uintptr_t) gl_tls_get (bufmax_key);
 214   if (fdiag_len > bufmax)
 215     {
 216       /* Need more memory.  */
 217       bufmax = 2 * bufmax;
 218       if (fdiag_len > bufmax)
 219         bufmax = fdiag_len;
 220       /* Calling xrealloc would be a waste: buffer's contents does not need
 221          to be preserved.  */
 222       free (buffer);
 223       buffer = xnmalloc (bufmax, 2 * sizeof *buffer);
 224       gl_tls_set (buffer_key, buffer);
 225       gl_tls_set (bufmax_key, (void *) (uintptr_t) bufmax);
 226     }
 227   ctxt.fdiag = buffer + yvec_length + 1;
 228   ctxt.bdiag = ctxt.fdiag + fdiag_len;
 229
 230   /* The edit_count is only ever increased.  The computation can be aborted
 231      when
 232        (xvec_length + yvec_length - edit_count) / (xvec_length + yvec_length)
 233        < lower_bound,
 234      or equivalently
 235        edit_count > (xvec_length + yvec_length) * (1 - lower_bound)
 236      or equivalently
 237        edit_count > floor((xvec_length + yvec_length) * (1 - lower_bound)).
 238      We need to add an epsilon inside the floor(...) argument, to neutralize
 239      rounding errors.  */
 240   ctxt.edit_count_limit =
 241     (lower_bound < 1.0
 242      ? (ptrdiff_t) (length_sum * (1.0 - lower_bound + 0.000001))
 243      : 0);
 244
 245   /* Now do the main comparison algorithm */
 246   ctxt.edit_count = - ctxt.edit_count_limit;
 247   if (compareseq (0, xvec_length, 0, yvec_length, 0, &ctxt)) /* Prob: 98% */
 248     /* The edit_count passed the limit.  Hence the result would be
 249        < lower_bound.  We can return any value < lower_bound instead.  */
 250     return 0.0;
 251   ctxt.edit_count += ctxt.edit_count_limit;
 252
 253   /* The result is
 254         ((number of chars in common) / (average length of the strings)).
 255      The numerator is
 256         = xvec_length - (number of calls to NOTE_DELETE)
 257         = yvec_length - (number of calls to NOTE_INSERT)
 258         = 1/2 * (xvec_length + yvec_length - (number of edits)).
 259      This is admittedly biased towards finding that the strings are
 260      similar, however it does produce meaningful results.  */
 261   return ((double) (xvec_length + yvec_length - ctxt.edit_count)
 262           / (xvec_length + yvec_length));
 263 }