| /* |
| * 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; |
| } |