|
Packit |
ae235b |
/*
|
|
Packit |
ae235b |
* Copyright © 2010 Codethink Limited
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* This library is free software; you can redistribute it and/or
|
|
Packit |
ae235b |
* modify it under the terms of the GNU Lesser General Public
|
|
Packit |
ae235b |
* License as published by the Free Software Foundation; either
|
|
Packit |
ae235b |
* version 2.1 of the License, or (at your option) any later version.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* This library is distributed in the hope that it will be useful,
|
|
Packit |
ae235b |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit |
ae235b |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
|
Packit |
ae235b |
* Lesser General Public License for more details.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* You should have received a copy of the GNU Lesser General Public
|
|
Packit |
ae235b |
* License along with this library; if not, see <http://www.gnu.org/licenses/>.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* Author: Ryan Lortie <desrt@desrt.ca>
|
|
Packit |
ae235b |
*/
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
#include <string.h>
|
|
Packit |
ae235b |
#include <glib.h>
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
/*
|
|
Packit |
ae235b |
* The string info map is an efficient data structure designed to be
|
|
Packit |
ae235b |
* used with a small set of items. It is used by GSettings schemas for
|
|
Packit |
ae235b |
* three purposes:
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* 1) Implement <choices> with a list of valid strings
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* 2) Implement <alias> by mapping one string to another
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* 3) Implement enumerated types by mapping strings to integer values
|
|
Packit |
ae235b |
* (and back).
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* The map is made out of an array of uint32s. Each entry in the array
|
|
Packit |
ae235b |
* is an integer value, followed by a specially formatted string value:
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* The string starts with the byte 0xff or 0xfe, followed by the
|
|
Packit |
ae235b |
* content of the string, followed by a nul byte, followed by
|
|
Packit |
ae235b |
* additional nul bytes for padding, followed by a 0xff byte.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* Padding is added so that the entire formatted string takes up a
|
|
Packit |
ae235b |
* multiple of 4 bytes, and not less than 8 bytes. The requirement
|
|
Packit |
ae235b |
* for a string to take up 8 bytes is so that the scanner doesn't lose
|
|
Packit |
ae235b |
* synch and mistake a string for an integer value.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* The first byte of the formatted string depends on if the integer is
|
|
Packit |
ae235b |
* an enum value (0xff) or an alias (0xfe). If it is an alias then the
|
|
Packit |
ae235b |
* number refers to the word offset within the info map at which the
|
|
Packit |
ae235b |
* integer corresponding to the "target" value is stored.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* For example, consider the case of the string info map representing an
|
|
Packit |
ae235b |
* enumerated type of 'foo' (value 1) and 'bar' (value 2) and 'baz'
|
|
Packit |
ae235b |
* (alias for 'bar'). Note that string info maps are always little
|
|
Packit |
ae235b |
* endian.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* x01 x00 x00 x00 xff 'f' 'o' 'o' x00 x00 x00 xff x02 x00 x00 x00
|
|
Packit |
ae235b |
* xff 'b' 'a' 'r' x00 x00 x00 xff x03 x00 x00 x00 xfe 'b' 'a' 'z'
|
|
Packit |
ae235b |
* x00 x00 x00 xff
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* The operations that someone may want to perform with the map:
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* - lookup if a string is valid (and not an alias)
|
|
Packit |
ae235b |
* - lookup the integer value for a enum 'nick'
|
|
Packit |
ae235b |
* - lookup the integer value for the target of an alias
|
|
Packit |
ae235b |
* - lookup an alias and convert it to its target string
|
|
Packit |
ae235b |
* - lookup the enum nick for a given value
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* In order to lookup if a string is valid, it is padded on either side
|
|
Packit |
ae235b |
* (as described) and scanned for in the array. For example, you might
|
|
Packit |
ae235b |
* look for "foo":
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* xff 'f' 'o' 'o' x00 x00 x00 xff
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* In order to lookup the integer value for a nick, the string is padded
|
|
Packit |
ae235b |
* on either side and scanned for in the array, as above. Instead of
|
|
Packit |
ae235b |
* merely succeeding, we look at the integer value to the left of the
|
|
Packit |
ae235b |
* match. This is the enum value.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* In order to lookup an alias and convert it to its target enum value,
|
|
Packit |
ae235b |
* the string is padded on either side (as described, with 0xfe) and
|
|
Packit |
ae235b |
* scanned for. For example, you might look for "baz":
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* xfe 'b' 'a' 'z' x00 x00 x00 xff
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* The integer immediately preceding the match then contains the offset
|
|
Packit |
ae235b |
* of the integer value of the target. In our example, that's '3'.
|
|
Packit |
ae235b |
* This index is dereferenced to find the enum value of '2'.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* To convert the alias to its target string, 5 bytes just need to be
|
|
Packit |
ae235b |
* added past the start of the integer value to find the start of the
|
|
Packit |
ae235b |
* string.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* To lookup the enum nick for a given value, the value is searched for
|
|
Packit |
ae235b |
* in the array. To ensure that the value isn't matching the inside of a
|
|
Packit |
ae235b |
* string, we must check that it is either the first item in the array or
|
|
Packit |
ae235b |
* immediately preceded by the byte 0xff. It must also be immediately
|
|
Packit |
ae235b |
* followed by the byte 0xff.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* Because strings always take up a minimum of 2 words, because 0xff or
|
|
Packit |
ae235b |
* 0xfe never appear inside of a utf-8 string and because no two integer
|
|
Packit |
ae235b |
* values ever appear in sequence, the only way we can have the
|
|
Packit |
ae235b |
* sequence:
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* xff __ __ __ __ xff (or 0xfe)
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* is in the event of an integer nested between two strings.
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* For implementation simplicity/efficiency, strings may not be more
|
|
Packit |
ae235b |
* than 65 characters in length (ie: 17 32bit words after padding).
|
|
Packit |
ae235b |
*
|
|
Packit |
ae235b |
* In the event that we are doing <choices> (ie: not an enum type) then
|
|
Packit |
ae235b |
* the value of each choice is set to zero and ignored.
|
|
Packit |
ae235b |
*/
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
#define STRINFO_MAX_WORDS 17
|
|
Packit |
ae235b |
G_GNUC_UNUSED static guint
|
|
Packit |
ae235b |
strinfo_string_to_words (const gchar *string,
|
|
Packit |
ae235b |
guint32 *words,
|
|
Packit |
ae235b |
gboolean alias)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
guint n_words;
|
|
Packit |
ae235b |
gsize size;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
size = strlen (string);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
n_words = MAX (2, (size + 6) >> 2);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
if (n_words > STRINFO_MAX_WORDS)
|
|
Packit |
ae235b |
return FALSE;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
words[0] = GUINT32_TO_LE (alias ? 0xfe : 0xff);
|
|
Packit |
ae235b |
words[n_words - 1] = GUINT32_TO_BE (0xff);
|
|
Packit |
ae235b |
memcpy (((gchar *) words) + 1, string, size + 1);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
return n_words;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static gint
|
|
Packit |
ae235b |
strinfo_scan (const guint32 *strinfo,
|
|
Packit |
ae235b |
guint length,
|
|
Packit |
ae235b |
const guint32 *words,
|
|
Packit |
ae235b |
guint n_words)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
guint i = 0;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
if (length < n_words)
|
|
Packit |
ae235b |
return -1;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
while (i <= length - n_words)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
guint j = 0;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
for (j = 0; j < n_words; j++)
|
|
Packit |
ae235b |
if (strinfo[i + j] != words[j])
|
|
Packit |
ae235b |
break;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
if (j == n_words)
|
|
Packit |
ae235b |
return i; /* match */
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
/* skip at least one word, continue */
|
|
Packit |
ae235b |
i += j ? j : 1;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
return -1;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static gint
|
|
Packit |
ae235b |
strinfo_find_string (const guint32 *strinfo,
|
|
Packit |
ae235b |
guint length,
|
|
Packit |
ae235b |
const gchar *string,
|
|
Packit |
ae235b |
gboolean alias)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
guint32 words[STRINFO_MAX_WORDS];
|
|
Packit |
ae235b |
guint n_words;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
if (length == 0)
|
|
Packit |
ae235b |
return -1;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
n_words = strinfo_string_to_words (string, words, alias);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
return strinfo_scan (strinfo + 1, length - 1, words, n_words);
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static gint
|
|
Packit |
ae235b |
strinfo_find_integer (const guint32 *strinfo,
|
|
Packit |
ae235b |
guint length,
|
|
Packit |
ae235b |
guint32 value)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
guint i;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
for (i = 0; i < length; i++)
|
|
Packit |
ae235b |
if (strinfo[i] == GUINT32_TO_LE (value))
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
const guchar *charinfo = (const guchar *) &strinfo[i];
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
/* make sure it has 0xff on either side */
|
|
Packit |
ae235b |
if ((i == 0 || charinfo[-1] == 0xff) && charinfo[4] == 0xff)
|
|
Packit |
ae235b |
return i;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
return -1;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static gboolean
|
|
Packit |
ae235b |
strinfo_is_string_valid (const guint32 *strinfo,
|
|
Packit |
ae235b |
guint length,
|
|
Packit |
ae235b |
const gchar *string)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
return strinfo_find_string (strinfo, length, string, FALSE) != -1;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static gboolean
|
|
Packit |
ae235b |
strinfo_enum_from_string (const guint32 *strinfo,
|
|
Packit |
ae235b |
guint length,
|
|
Packit |
ae235b |
const gchar *string,
|
|
Packit |
ae235b |
guint *result)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
gint index;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
index = strinfo_find_string (strinfo, length, string, FALSE);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
if (index < 0)
|
|
Packit |
ae235b |
return FALSE;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
*result = GUINT32_FROM_LE (strinfo[index]);
|
|
Packit |
ae235b |
return TRUE;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static const gchar *
|
|
Packit |
ae235b |
strinfo_string_from_enum (const guint32 *strinfo,
|
|
Packit |
ae235b |
guint length,
|
|
Packit |
ae235b |
guint value)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
gint index;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
index = strinfo_find_integer (strinfo, length, value);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
if (index < 0)
|
|
Packit |
ae235b |
return NULL;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
return 1 + (const gchar *) &strinfo[index + 1];
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static const gchar *
|
|
Packit |
ae235b |
strinfo_string_from_alias (const guint32 *strinfo,
|
|
Packit |
ae235b |
guint length,
|
|
Packit |
ae235b |
const gchar *alias)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
gint index;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
index = strinfo_find_string (strinfo, length, alias, TRUE);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
if (index < 0)
|
|
Packit |
ae235b |
return NULL;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
return 1 + (const gchar *) &strinfo[GUINT32_TO_LE (strinfo[index]) + 1];
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static GVariant *
|
|
Packit |
ae235b |
strinfo_enumerate (const guint32 *strinfo,
|
|
Packit |
ae235b |
guint length)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
GVariantBuilder builder;
|
|
Packit |
ae235b |
const gchar *ptr, *end;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
ptr = (gpointer) strinfo;
|
|
Packit |
ae235b |
end = ptr + 4 * length;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
ptr += 4;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
g_variant_builder_init (&builder, G_VARIANT_TYPE_STRING_ARRAY);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
while (ptr < end)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
/* don't include aliases */
|
|
Packit |
ae235b |
if (*ptr == '\xff')
|
|
Packit |
ae235b |
g_variant_builder_add (&builder, "s", ptr + 1);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
/* find the end of this string */
|
|
Packit |
ae235b |
ptr = memchr (ptr, '\xff', end - ptr);
|
|
Packit |
ae235b |
g_assert (ptr != NULL);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
/* skip over the int to the next string */
|
|
Packit |
ae235b |
ptr += 5;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
return g_variant_builder_end (&builder);
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static void
|
|
Packit |
ae235b |
strinfo_builder_append_item (GString *builder,
|
|
Packit |
ae235b |
const gchar *string,
|
|
Packit |
ae235b |
guint value)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
guint32 words[STRINFO_MAX_WORDS];
|
|
Packit |
ae235b |
guint n_words;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
value = GUINT32_TO_LE (value);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
n_words = strinfo_string_to_words (string, words, FALSE);
|
|
Packit |
ae235b |
g_string_append_len (builder, (void *) &value, sizeof value);
|
|
Packit |
ae235b |
g_string_append_len (builder, (void *) words, 4 * n_words);
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static gboolean
|
|
Packit |
ae235b |
strinfo_builder_append_alias (GString *builder,
|
|
Packit |
ae235b |
const gchar *alias,
|
|
Packit |
ae235b |
const gchar *target)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
guint32 words[STRINFO_MAX_WORDS];
|
|
Packit |
ae235b |
guint n_words;
|
|
Packit |
ae235b |
guint value;
|
|
Packit |
ae235b |
gint index;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
index = strinfo_find_string ((const guint32 *) builder->str,
|
|
Packit |
ae235b |
builder->len / 4, target, FALSE);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
if (index == -1)
|
|
Packit |
ae235b |
return FALSE;
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
value = GUINT32_TO_LE (index);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
n_words = strinfo_string_to_words (alias, words, TRUE);
|
|
Packit |
ae235b |
g_string_append_len (builder, (void *) &value, sizeof value);
|
|
Packit |
ae235b |
g_string_append_len (builder, (void *) words, 4 * n_words);
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
return TRUE;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static gboolean
|
|
Packit |
ae235b |
strinfo_builder_contains (GString *builder,
|
|
Packit |
ae235b |
const gchar *string)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
return strinfo_find_string ((const guint32 *) builder->str,
|
|
Packit |
ae235b |
builder->len / 4, string, FALSE) != -1 ||
|
|
Packit |
ae235b |
strinfo_find_string ((const guint32 *) builder->str,
|
|
Packit |
ae235b |
builder->len / 4, string, TRUE) != -1;
|
|
Packit |
ae235b |
}
|
|
Packit |
ae235b |
|
|
Packit |
ae235b |
G_GNUC_UNUSED static gboolean
|
|
Packit |
ae235b |
strinfo_builder_contains_value (GString *builder,
|
|
Packit |
ae235b |
guint value)
|
|
Packit |
ae235b |
{
|
|
Packit |
ae235b |
return strinfo_string_from_enum ((const guint32 *) builder->str,
|
|
Packit |
ae235b |
builder->len / 4, value) != NULL;
|
|
Packit |
ae235b |
}
|