/*
* 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:
*
* - lookup if a string is valid (and not an alias)
* - lookup the integer value for a enum 'nick'
* - lookup the integer value for the target of an alias
* - lookup an alias and convert it to its target string
* - lookup the enum nick for a given value
*
* In order to lookup 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 lookup 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 lookup 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 lookup 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;
}