gio/strinfo.c - manifest_repos/glib - Git at Google

 /*
  * Copyright © 2010 Codethink Limited
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2.1 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  *
  * Author: Ryan Lortie <desrt@desrt.ca>
  */

 #include <string.h>
 #include <glib.h>

 /*
  * The string info map is an efficient data structure designed to be
  * used with a small set of items.  It is used by GSettings schemas for
  * three purposes:
  *
  *  1) Implement <choices> with a list of valid strings
  *
  *  2) Implement <alias> by mapping one string to another
  *
  *  3) Implement enumerated types by mapping strings to integer values
  *     (and back).
  *
  * The map is made out of an array of uint32s.  Each entry in the array
  * is an integer value, followed by a specially formatted string value:
  *
  *   The string starts with the byte 0xff or 0xfe, followed by the
  *   content of the string, followed by a nul byte, followed by
  *   additional nul bytes for padding, followed by a 0xff byte.
  *
  *   Padding is added so that the entire formatted string takes up a
  *   multiple of 4 bytes, and not less than 8 bytes.  The requirement
  *   for a string to take up 8 bytes is so that the scanner doesn't lose
  *   synch and mistake a string for an integer value.
  *
  * The first byte of the formatted string depends on if the integer is
  * an enum value (0xff) or an alias (0xfe).  If it is an alias then the
  * number refers to the word offset within the info map at which the
  * integer corresponding to the "target" value is stored.
  *
  * For example, consider the case of the string info map representing an
  * enumerated type of 'foo' (value 1) and 'bar' (value 2) and 'baz'
  * (alias for 'bar').  Note that string info maps are always little
  * endian.
  *
  * x01 x00 x00 x00   xff 'f' 'o' 'o'   x00 x00 x00 xff   x02 x00 x00 x00
  * xff 'b' 'a' 'r'   x00 x00 x00 xff   x03 x00 x00 x00   xfe 'b' 'a' 'z'
  * x00 x00 x00 xff
  *
  *
  * The operations that someone may want to perform with the map:
  *
  *   - look up if a string is valid (and not an alias)
  *   - look up the integer value for a enum 'nick'
  *   - look up the integer value for the target of an alias
  *   - look up an alias and convert it to its target string
  *   - look up the enum nick for a given value
  *
  * In order to look up if a string is valid, it is padded on either side
  * (as described) and scanned for in the array.  For example, you might
  * look for "foo":
  *
  *                   xff 'f' 'o' 'o'   x00 x00 x00 xff
  *
  * In order to look up the integer value for a nick, the string is padded
  * on either side and scanned for in the array, as above.  Instead of
  * merely succeeding, we look at the integer value to the left of the
  * match.  This is the enum value.
  *
  * In order to look up an alias and convert it to its target enum value,
  * the string is padded on either side (as described, with 0xfe) and
  * scanned for.  For example, you might look for "baz":
  *
  *                   xfe 'b' 'a' 'z'  x00 x00 x00 xff
  *
  * The integer immediately preceding the match then contains the offset
  * of the integer value of the target.  In our example, that's '3'.
  * This index is dereferenced to find the enum value of '2'.
  *
  * To convert the alias to its target string, 5 bytes just need to be
  * added past the start of the integer value to find the start of the
  * string.
  *
  * To look up the enum nick for a given value, the value is searched for
  * in the array.  To ensure that the value isn't matching the inside of a
  * string, we must check that it is either the first item in the array or
  * immediately preceded by the byte 0xff.  It must also be immediately
  * followed by the byte 0xff.
  *
  * Because strings always take up a minimum of 2 words, because 0xff or
  * 0xfe never appear inside of a utf-8 string and because no two integer
  * values ever appear in sequence, the only way we can have the
  * sequence:
  *
  *     xff __ __ __ __ xff (or 0xfe)
  *
  * is in the event of an integer nested between two strings.
  *
  * For implementation simplicity/efficiency, strings may not be more
  * than 65 characters in length (ie: 17 32bit words after padding).
  *
  * In the event that we are doing <choices> (ie: not an enum type) then
  * the value of each choice is set to zero and ignored.
  */

 #define STRINFO_MAX_WORDS   17
 G_GNUC_UNUSED static guint
 strinfo_string_to_words (const gchar *string,
                          guint32     *words,
                          gboolean     alias)
 {
   guint n_words;
   gsize size;

   size = strlen (string);

   n_words = MAX (2, (size + 6) >> 2);

   if (n_words > STRINFO_MAX_WORDS)
     return FALSE;

   words[0] = GUINT32_TO_LE (alias ? 0xfe : 0xff);
   words[n_words - 1] = GUINT32_TO_BE (0xff);
   memcpy (((gchar *) words) + 1, string, size + 1);

   return n_words;
 }

 G_GNUC_UNUSED static gint
 strinfo_scan (const guint32 *strinfo,
               guint          length,
               const guint32 *words,
               guint          n_words)
 {
   guint i = 0;

   if (length < n_words)
     return -1;

   while (i <= length - n_words)
     {
       guint j = 0;

       for (j = 0; j < n_words; j++)
         if (strinfo[i + j] != words[j])
           break;

       if (j == n_words)
         return i;   /* match */

       /* skip at least one word, continue */
       i += j ? j : 1;
     }

   return -1;
 }

 G_GNUC_UNUSED static gint
 strinfo_find_string (const guint32 *strinfo,
                      guint          length,
                      const gchar   *string,
                      gboolean       alias)
 {
   guint32 words[STRINFO_MAX_WORDS];
   guint n_words;

   if (length == 0)
     return -1;

   n_words = strinfo_string_to_words (string, words, alias);

   return strinfo_scan (strinfo + 1, length - 1, words, n_words);
 }

 G_GNUC_UNUSED static gint
 strinfo_find_integer (const guint32 *strinfo,
                       guint          length,
                       guint32        value)
 {
   guint i;

   for (i = 0; i < length; i++)
     if (strinfo[i] == GUINT32_TO_LE (value))
       {
         const guchar *charinfo = (const guchar *) &strinfo[i];

         /* make sure it has 0xff on either side */
         if ((i == 0 || charinfo[-1] == 0xff) && charinfo[4] == 0xff)
           return i;
       }

   return -1;
 }

 G_GNUC_UNUSED static gboolean
 strinfo_is_string_valid (const guint32 *strinfo,
                          guint          length,
                          const gchar   *string)
 {
   return strinfo_find_string (strinfo, length, string, FALSE) != -1;
 }

 G_GNUC_UNUSED static gboolean
 strinfo_enum_from_string (const guint32 *strinfo,
                           guint          length,
                           const gchar   *string,
                           guint         *result)
 {
   gint index;

   index = strinfo_find_string (strinfo, length, string, FALSE);

   if (index < 0)
     return FALSE;

   *result = GUINT32_FROM_LE (strinfo[index]);
   return TRUE;
 }

 G_GNUC_UNUSED static const gchar *
 strinfo_string_from_enum (const guint32 *strinfo,
                           guint          length,
                           guint          value)
 {
   gint index;

   index = strinfo_find_integer (strinfo, length, value);

   if (index < 0)
     return NULL;

   return 1 + (const gchar *) &strinfo[index + 1];
 }

 G_GNUC_UNUSED static const gchar *
 strinfo_string_from_alias (const guint32 *strinfo,
                            guint          length,
                            const gchar   *alias)
 {
   gint index;

   index = strinfo_find_string (strinfo, length, alias, TRUE);

   if (index < 0)
     return NULL;

   return 1 + (const gchar *) &strinfo[GUINT32_TO_LE (strinfo[index]) + 1];
 }

 G_GNUC_UNUSED static GVariant *
 strinfo_enumerate (const guint32 *strinfo,
                    guint          length)
 {
   GVariantBuilder builder;
   const gchar *ptr, *end;

   ptr = (gpointer) strinfo;
   end = ptr + 4 * length;

   ptr += 4;

   g_variant_builder_init (&builder, G_VARIANT_TYPE_STRING_ARRAY);

   while (ptr < end)
     {
       /* don't include aliases */
       if (*ptr == '\xff')
         g_variant_builder_add (&builder, "s", ptr + 1);

       /* find the end of this string */
       ptr = memchr (ptr, '\xff', end - ptr);
       g_assert (ptr != NULL);

       /* skip over the int to the next string */
       ptr += 5;
     }

   return g_variant_builder_end (&builder);
 }

 G_GNUC_UNUSED static void
 strinfo_builder_append_item (GString     *builder,
                              const gchar *string,
                              guint        value)
 {
   guint32 words[STRINFO_MAX_WORDS];
   guint n_words;

   value = GUINT32_TO_LE (value);

   n_words = strinfo_string_to_words (string, words, FALSE);
   g_string_append_len (builder, (void *) &value, sizeof value);
   g_string_append_len (builder, (void *) words, 4 * n_words);
 }

 G_GNUC_UNUSED static gboolean
 strinfo_builder_append_alias (GString     *builder,
                               const gchar *alias,
                               const gchar *target)
 {
   guint32 words[STRINFO_MAX_WORDS];
   guint n_words;
   guint value;
   gint index;

   index = strinfo_find_string ((const guint32 *) builder->str,
                                builder->len / 4, target, FALSE);

   if (index == -1)
     return FALSE;

   value = GUINT32_TO_LE (index);

   n_words = strinfo_string_to_words (alias, words, TRUE);
   g_string_append_len (builder, (void *) &value, sizeof value);
   g_string_append_len (builder, (void *) words, 4 * n_words);

   return TRUE;
 }

 G_GNUC_UNUSED static gboolean
 strinfo_builder_contains (GString     *builder,
                           const gchar *string)
 {
   return strinfo_find_string ((const guint32 *) builder->str,
                               builder->len / 4, string, FALSE) != -1 ||
          strinfo_find_string ((const guint32 *) builder->str,
                               builder->len / 4, string, TRUE) != -1;
 }

 G_GNUC_UNUSED static gboolean
 strinfo_builder_contains_value (GString *builder,
                                 guint    value)
 {
   return strinfo_string_from_enum ((const guint32 *) builder->str,
                                    builder->len / 4, value) != NULL;
 }
	/*
	* Copyright © 2010 Codethink Limited
	*
	* This library is free software; you can redistribute it and/or
	* modify it under the terms of the GNU Lesser General Public
	* License as published by the Free Software Foundation; either
	* version 2.1 of the License, or (at your option) any later version.
	*
	* This library is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	* Lesser General Public License for more details.
	*
	* You should have received a copy of the GNU Lesser General Public
	* License along with this library; if not, see <http://www.gnu.org/licenses/>.
	*
	* Author: Ryan Lortie <desrt@desrt.ca>
	*/

	#include <string.h>
	#include <glib.h>

	/*
	* The string info map is an efficient data structure designed to be
	* used with a small set of items. It is used by GSettings schemas for
	* three purposes:
	*
	* 1) Implement <choices> with a list of valid strings
	*
	* 2) Implement <alias> by mapping one string to another
	*
	* 3) Implement enumerated types by mapping strings to integer values
	* (and back).
	*
	* The map is made out of an array of uint32s. Each entry in the array
	* is an integer value, followed by a specially formatted string value:
	*
	* The string starts with the byte 0xff or 0xfe, followed by the
	* content of the string, followed by a nul byte, followed by
	* additional nul bytes for padding, followed by a 0xff byte.
	*
	* Padding is added so that the entire formatted string takes up a
	* multiple of 4 bytes, and not less than 8 bytes. The requirement
	* for a string to take up 8 bytes is so that the scanner doesn't lose
	* synch and mistake a string for an integer value.
	*
	* The first byte of the formatted string depends on if the integer is
	* an enum value (0xff) or an alias (0xfe). If it is an alias then the
	* number refers to the word offset within the info map at which the
	* integer corresponding to the "target" value is stored.
	*
	* For example, consider the case of the string info map representing an
	* enumerated type of 'foo' (value 1) and 'bar' (value 2) and 'baz'
	* (alias for 'bar'). Note that string info maps are always little
	* endian.
	*
	* x01 x00 x00 x00 xff 'f' 'o' 'o' x00 x00 x00 xff x02 x00 x00 x00
	* xff 'b' 'a' 'r' x00 x00 x00 xff x03 x00 x00 x00 xfe 'b' 'a' 'z'
	* x00 x00 x00 xff
	*
	*
	* The operations that someone may want to perform with the map:
	*
	* - look up if a string is valid (and not an alias)
	* - look up the integer value for a enum 'nick'
	* - look up the integer value for the target of an alias
	* - look up an alias and convert it to its target string
	* - look up the enum nick for a given value
	*
	* In order to look up if a string is valid, it is padded on either side
	* (as described) and scanned for in the array. For example, you might
	* look for "foo":
	*
	* xff 'f' 'o' 'o' x00 x00 x00 xff
	*
	* In order to look up the integer value for a nick, the string is padded
	* on either side and scanned for in the array, as above. Instead of
	* merely succeeding, we look at the integer value to the left of the
	* match. This is the enum value.
	*
	* In order to look up an alias and convert it to its target enum value,
	* the string is padded on either side (as described, with 0xfe) and
	* scanned for. For example, you might look for "baz":
	*
	* xfe 'b' 'a' 'z' x00 x00 x00 xff
	*
	* The integer immediately preceding the match then contains the offset
	* of the integer value of the target. In our example, that's '3'.
	* This index is dereferenced to find the enum value of '2'.
	*
	* To convert the alias to its target string, 5 bytes just need to be
	* added past the start of the integer value to find the start of the
	* string.
	*
	* To look up the enum nick for a given value, the value is searched for
	* in the array. To ensure that the value isn't matching the inside of a
	* string, we must check that it is either the first item in the array or
	* immediately preceded by the byte 0xff. It must also be immediately
	* followed by the byte 0xff.
	*
	* Because strings always take up a minimum of 2 words, because 0xff or
	* 0xfe never appear inside of a utf-8 string and because no two integer
	* values ever appear in sequence, the only way we can have the
	* sequence:
	*
	* xff __ __ __ __ xff (or 0xfe)
	*
	* is in the event of an integer nested between two strings.
	*
	* For implementation simplicity/efficiency, strings may not be more
	* than 65 characters in length (ie: 17 32bit words after padding).
	*
	* In the event that we are doing <choices> (ie: not an enum type) then
	* the value of each choice is set to zero and ignored.
	*/

	#define STRINFO_MAX_WORDS 17
	G_GNUC_UNUSED static guint
	strinfo_string_to_words (const gchar *string,
	guint32 *words,
	gboolean alias)
	{
	guint n_words;
	gsize size;

	size = strlen (string);

	n_words = MAX (2, (size + 6) >> 2);

	if (n_words > STRINFO_MAX_WORDS)
	return FALSE;

	words[0] = GUINT32_TO_LE (alias ? 0xfe : 0xff);
	words[n_words - 1] = GUINT32_TO_BE (0xff);
	memcpy (((gchar *) words) + 1, string, size + 1);

	return n_words;
	}

	G_GNUC_UNUSED static gint
	strinfo_scan (const guint32 *strinfo,
	guint length,
	const guint32 *words,
	guint n_words)
	{
	guint i = 0;

	if (length < n_words)
	return -1;

	while (i <= length - n_words)
	{
	guint j = 0;

	for (j = 0; j < n_words; j++)
	if (strinfo[i + j] != words[j])
	break;

	if (j == n_words)
	return i; /* match */

	/* skip at least one word, continue */
	i += j ? j : 1;
	}

	return -1;
	}

	G_GNUC_UNUSED static gint
	strinfo_find_string (const guint32 *strinfo,
	guint length,
	const gchar *string,
	gboolean alias)
	{
	guint32 words[STRINFO_MAX_WORDS];
	guint n_words;

	if (length == 0)
	return -1;

	n_words = strinfo_string_to_words (string, words, alias);

	return strinfo_scan (strinfo + 1, length - 1, words, n_words);
	}

	G_GNUC_UNUSED static gint
	strinfo_find_integer (const guint32 *strinfo,
	guint length,
	guint32 value)
	{
	guint i;

	for (i = 0; i < length; i++)
	if (strinfo[i] == GUINT32_TO_LE (value))
	{
	const guchar charinfo = (const guchar ) &strinfo[i];

	/* make sure it has 0xff on either side */
	if ((i == 0 \|\| charinfo[-1] == 0xff) && charinfo[4] == 0xff)
	return i;
	}

	return -1;
	}

	G_GNUC_UNUSED static gboolean
	strinfo_is_string_valid (const guint32 *strinfo,
	guint length,
	const gchar *string)
	{
	return strinfo_find_string (strinfo, length, string, FALSE) != -1;
	}

	G_GNUC_UNUSED static gboolean
	strinfo_enum_from_string (const guint32 *strinfo,
	guint length,
	const gchar *string,
	guint *result)
	{
	gint index;

	index = strinfo_find_string (strinfo, length, string, FALSE);

	if (index < 0)
	return FALSE;

	*result = GUINT32_FROM_LE (strinfo[index]);
	return TRUE;
	}

	G_GNUC_UNUSED static const gchar *
	strinfo_string_from_enum (const guint32 *strinfo,
	guint length,
	guint value)
	{
	gint index;

	index = strinfo_find_integer (strinfo, length, value);

	if (index < 0)
	return NULL;

	return 1 + (const gchar *) &strinfo[index + 1];
	}

	G_GNUC_UNUSED static const gchar *
	strinfo_string_from_alias (const guint32 *strinfo,
	guint length,
	const gchar *alias)
	{
	gint index;

	index = strinfo_find_string (strinfo, length, alias, TRUE);

	if (index < 0)
	return NULL;

	return 1 + (const gchar *) &strinfo[GUINT32_TO_LE (strinfo[index]) + 1];
	}

	G_GNUC_UNUSED static GVariant *
	strinfo_enumerate (const guint32 *strinfo,
	guint length)
	{
	GVariantBuilder builder;
	const gchar ptr, end;

	ptr = (gpointer) strinfo;
	end = ptr + 4 * length;

	ptr += 4;

	g_variant_builder_init (&builder, G_VARIANT_TYPE_STRING_ARRAY);

	while (ptr < end)
	{
	/* don't include aliases */
	if (*ptr == '\xff')
	g_variant_builder_add (&builder, "s", ptr + 1);

	/* find the end of this string */
	ptr = memchr (ptr, '\xff', end - ptr);
	g_assert (ptr != NULL);

	/* skip over the int to the next string */
	ptr += 5;
	}

	return g_variant_builder_end (&builder);
	}

	G_GNUC_UNUSED static void
	strinfo_builder_append_item (GString *builder,
	const gchar *string,
	guint value)
	{
	guint32 words[STRINFO_MAX_WORDS];
	guint n_words;

	value = GUINT32_TO_LE (value);

	n_words = strinfo_string_to_words (string, words, FALSE);
	g_string_append_len (builder, (void *) &value, sizeof value);
	g_string_append_len (builder, (void ) words, 4 n_words);
	}

	G_GNUC_UNUSED static gboolean
	strinfo_builder_append_alias (GString *builder,
	const gchar *alias,
	const gchar *target)
	{
	guint32 words[STRINFO_MAX_WORDS];
	guint n_words;
	guint value;
	gint index;

	index = strinfo_find_string ((const guint32 *) builder->str,
	builder->len / 4, target, FALSE);

	if (index == -1)
	return FALSE;

	value = GUINT32_TO_LE (index);

	n_words = strinfo_string_to_words (alias, words, TRUE);
	g_string_append_len (builder, (void *) &value, sizeof value);
	g_string_append_len (builder, (void ) words, 4 n_words);

	return TRUE;
	}

	G_GNUC_UNUSED static gboolean
	strinfo_builder_contains (GString *builder,
	const gchar *string)
	{
	return strinfo_find_string ((const guint32 *) builder->str,
	builder->len / 4, string, FALSE) != -1 \|\|
	strinfo_find_string ((const guint32 *) builder->str,
	builder->len / 4, string, TRUE) != -1;
	}

	G_GNUC_UNUSED static gboolean
	strinfo_builder_contains_value (GString *builder,
	guint value)
	{
	return strinfo_string_from_enum ((const guint32 *) builder->str,
	builder->len / 4, value) != NULL;
	}