gio/strinfo.c

   1 /*
   2  * Copyright © 2010 Codethink Limited
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the licence, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  *
  19  * Author: Ryan Lortie <desrt@desrt.ca>
  20  */
  21
  22 #include <string.h>
  23 #include <glib.h>
  24
  25 /**
  26  * The string info map is an efficient data structure designed to be
  27  * used with a small set of items.  It is used by GSettings schemas for
  28  * three purposes:
  29  *
  30  *  1) Implement <choices> with a list of valid strings
  31  *
  32  *  2) Implement <alias> by mapping one string to another
  33  *
  34  *  3) Implement enumerated types by mapping strings to integer values
  35  *     (and back).
  36  *
  37  * The map is made out of an array of uint32s.  Each entry in the array
  38  * is an integer value, followed by a specially formatted string value:
  39  *
  40  *   The string starts with the byte 0xff or 0xfe, followed by the
  41  *   content of the string, followed by a nul byte, followed by
  42  *   additional nul bytes for padding, followed by a 0xff byte.
  43  *
  44  *   Padding is added so that the entire formatted string takes up a
  45  *   multiple of 4 bytes, and not less than 8 bytes.  The requirement
  46  *   for a string to take up 8 bytes is so that the scanner doesn't lose
  47  *   synch and mistake a string for an integer value.
  48  *
  49  * The first byte of the formatted string depends on if the integer is
  50  * an enum value (0xff) or an alias (0xfe).  If it is an alias then the
  51  * number refers to the word offset within the info map at which the
  52  * integer corresponding to the "target" value is stored.
  53  *
  54  * For example, consider the case of the string info map representing an
  55  * enumerated type of 'foo' (value 1) and 'bar' (value 2) and 'baz'
  56  * (alias for 'bar').  Note that string info maps are always little
  57  * endian.
  58  *
  59  * x01 x00 x00 x00   xff 'f' 'o' 'o'   x00 x00 x00 xff   x02 x00 x00 x00
  60  * xff 'b' 'a' 'r'   x00 x00 x00 xff   x03 x00 x00 x00   xfe 'b' 'a' 'z'
  61  * x00 x00 x00 xff
  62  *
  63  *
  64  * The operations that someone may want to perform with the map:
  65  *
  66  *   - lookup if a string is valid (and not an alias)
  67  *   - lookup the integer value for a enum 'nick'
  68  *   - lookup the integer value for the target of an alias
  69  *   - lookup an alias and convert it to its target string
  70  *   - lookup the enum nick for a given value
  71  *
  72  * In order to lookup if a string is valid, it is padded on either side
  73  * (as described) and scanned for in the array.  For example, you might
  74  * look for "foo":
  75  *
  76  *                   xff 'f' 'o' 'o'   x00 x00 x00 xff
  77  *
  78  * In order to lookup the integer value for a nick, the string is padded
  79  * on either side and scanned for in the array, as above.  Instead of
  80  * merely succeeding, we look at the integer value to the left of the
  81  * match.  This is the enum value.
  82  *
  83  * In order to lookup an alias and convert it to its target enum value,
  84  * the string is padded on either side (as described, with 0xfe) and
  85  * scanned for.  For example, you might look for "baz":
  86  *
  87  *                   xfe 'b' 'a' 'z'  x00 x00 x00 xff
  88  *
  89  * The integer immediately preceeding the match then contains the offset
  90  * of the integer value of the target.  In our example, that's '3'.
  91  * This index is dereferenced to find the enum value of '2'.
  92  *
  93  * To convert the alias to its target string, 5 bytes just need to be
  94  * added past the start of the integer value to find the start of the
  95  * string.
  96  *
  97  * To lookup the enum nick for a given value, the value is searched for
  98  * in the array.  To ensure that the value isn't matching the inside of a
  99  * string, we must check that it is either the first item in the array or
 100  * immediately preceeded by the byte 0xff.  It must also be immediately
 101  * followed by the byte 0xff.
 102  *
 103  * Because strings always take up a minimum of 2 words, because 0xff or
 104  * 0xfe never appear inside of a utf-8 string and because no two integer
 105  * values ever appear in sequence, the only way we can have the
 106  * sequence:
 107  *
 108  *     xff __ __ __ __ xff (or 0xfe)
 109  *
 110  * is in the event of an integer nested between two strings.
 111  *
 112  * For implementation simplicity/efficiency, strings may not be more
 113  * than 65 characters in length (ie: 17 32bit words after padding).
 114  *
 115  * In the event that we are doing <choices> (ie: not an enum type) then
 116  * the value of each choice is set to zero and ignored.
 117  */
 118
 119 #define STRINFO_MAX_WORDS   17
 120 G_GNUC_UNUSED static guint
 121 strinfo_string_to_words (const gchar *string,
 122                          guint32     *words,
 123                          gboolean     alias)
 124 {
 125   guint n_words;
 126   gsize size;
 127
 128   size = strlen (string);
 129
 130   n_words = MAX (2, (size + 6) >> 2);
 131
 132   if (n_words > STRINFO_MAX_WORDS)
 133     return FALSE;
 134
 135   words[0] = GUINT32_TO_LE (alias ? 0xfe : 0xff);
 136   words[n_words - 1] = GUINT32_TO_BE (0xff);
 137   memcpy (((gchar *) words) + 1, string, size + 1);
 138
 139   return n_words;
 140 }
 141
 142 G_GNUC_UNUSED static gint
 143 strinfo_scan (const guint32 *strinfo,
 144               guint          length,
 145               const guint32 *words,
 146               guint          n_words)
 147 {
 148   guint i = 0;
 149
 150   while (i <= length - n_words)
 151     {
 152       guint j = 0;
 153
 154       for (j = 0; j < n_words; j++)
 155         if (strinfo[i + j] != words[j])
 156           break;
 157
 158       if (j == n_words)
 159         return i;   /* match */
 160
 161       /* skip at least one word, continue */
 162       i += j ? j : 1;
 163     }
 164
 165   return -1;
 166 }
 167
 168 G_GNUC_UNUSED static gint
 169 strinfo_find_string (const guint32 *strinfo,
 170                      guint          length,
 171                      const gchar   *string,
 172                      gboolean       alias)
 173 {
 174   guint32 words[STRINFO_MAX_WORDS];
 175   guint n_words;
 176
 177   if (length == 0)
 178     return -1;
 179
 180   n_words = strinfo_string_to_words (string, words, alias);
 181
 182   return strinfo_scan (strinfo + 1, length - 1, words, n_words);
 183 }
 184
 185 G_GNUC_UNUSED static gint
 186 strinfo_find_integer (const guint32 *strinfo,
 187                       guint          length,
 188                       guint32        value)
 189 {
 190   guint i;
 191
 192   for (i = 0; i < length; i++)
 193     if (strinfo[i] == value)
 194       {
 195         const guchar *charinfo = (const guchar *) &strinfo[i];
 196
 197         /* make sure it has 0xff on either side */
 198         if ((i == 0 || charinfo[-1] == 0xff) && charinfo[4] == 0xff)
 199           return i;
 200       }
 201
 202   return -1;
 203 }
 204
 205 G_GNUC_UNUSED static gboolean
 206 strinfo_is_string_valid (const guint32 *strinfo,
 207                          guint          length,
 208                          const gchar   *string)
 209 {
 210   return strinfo_find_string (strinfo, length, string, FALSE) != -1;
 211 }
 212
 213 G_GNUC_UNUSED static gboolean
 214 strinfo_enum_from_string (const guint32 *strinfo,
 215                           guint          length,
 216                           const gchar   *string,
 217                           guint         *result)
 218 {
 219   gint index;
 220
 221   index = strinfo_find_string (strinfo, length, string, FALSE);
 222
 223   if (index < 0)
 224     return FALSE;
 225
 226   *result = strinfo[index];
 227   return TRUE;
 228 }
 229
 230 G_GNUC_UNUSED static const gchar *
 231 strinfo_string_from_enum (const guint32 *strinfo,
 232                           guint          length,
 233                           guint          value)
 234 {
 235   gint index;
 236
 237   index = strinfo_find_integer (strinfo, length, value);
 238
 239   if (index < 0)
 240     return NULL;
 241
 242   return 1 + (const gchar *) &strinfo[index + 1];
 243 }
 244
 245 G_GNUC_UNUSED static const gchar *
 246 strinfo_string_from_alias (const guint32 *strinfo,
 247                            guint          length,
 248                            const gchar   *alias)
 249 {
 250   gint index;
 251
 252   index = strinfo_find_string (strinfo, length, alias, TRUE);
 253
 254   if (index < 0)
 255     return NULL;
 256
 257   return 1 + (const gchar *) &strinfo[GUINT32_TO_LE (strinfo[index]) + 1];
 258 }
 259
 260 G_GNUC_UNUSED static void
 261 strinfo_builder_append_item (GString     *builder,
 262                              const gchar *string,
 263                              guint        value)
 264 {
 265   guint32 words[STRINFO_MAX_WORDS];
 266   guint n_words;
 267
 268   value = GUINT32_TO_LE (value);
 269
 270   n_words = strinfo_string_to_words (string, words, FALSE);
 271   g_string_append_len (builder, (void *) &value, sizeof value);
 272   g_string_append_len (builder, (void *) words, 4 * n_words);
 273 }
 274
 275 G_GNUC_UNUSED static gboolean
 276 strinfo_builder_append_alias (GString     *builder,
 277                               const gchar *alias,
 278                               const gchar *target)
 279 {
 280   guint32 words[STRINFO_MAX_WORDS];
 281   guint n_words;
 282   guint value;
 283   gint index;
 284
 285   index = strinfo_find_string ((const guint32 *) builder->str,
 286                                builder->len / 4, target, FALSE);
 287
 288   if (index == -1)
 289     return FALSE;
 290
 291   value = GUINT32_TO_LE (index);
 292
 293   n_words = strinfo_string_to_words (alias, words, TRUE);
 294   g_string_append_len (builder, (void *) &value, sizeof value);
 295   g_string_append_len (builder, (void *) words, 4 * n_words);
 296
 297   return TRUE;
 298 }
 299
 300 G_GNUC_UNUSED static gboolean
 301 strinfo_builder_contains (GString     *builder,
 302                           const gchar *string)
 303 {
 304   return strinfo_find_string ((const guint32 *) builder->str,
 305                               builder->len / 4, string, FALSE) != -1 ||
 306          strinfo_find_string ((const guint32 *) builder->str,
 307                               builder->len / 4, string, FALSE) != -1;
 308 }