Branch data Line data Source code
1 : : /*
2 : : * Copyright © 2010 Codethink Limited
3 : : *
4 : : * SPDX-License-Identifier: LGPL-2.1-or-later
5 : : *
6 : : * This library is free software; you can redistribute it and/or
7 : : * modify it under the terms of the GNU Lesser General Public
8 : : * License as published by the Free Software Foundation; either
9 : : * version 2.1 of the License, or (at your option) any later version.
10 : : *
11 : : * This library is distributed in the hope that it will be useful,
12 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 : : * Lesser General Public License for more details.
15 : : *
16 : : * You should have received a copy of the GNU Lesser General Public
17 : : * License along with this library; if not, see <http://www.gnu.org/licenses/>.
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 : : * - look up if a string is valid (and not an alias)
67 : : * - look up the integer value for a enum 'nick'
68 : : * - look up the integer value for the target of an alias
69 : : * - look up an alias and convert it to its target string
70 : : * - look up the enum nick for a given value
71 : : *
72 : : * In order to look up 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 look up 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 look up 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 preceding 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 look up 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 preceded 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 : 468 : strinfo_string_to_words (const gchar *string,
122 : : guint32 *words,
123 : : gboolean alias)
124 : : {
125 : : guint n_words;
126 : : gsize size;
127 : :
128 : 468 : size = strlen (string);
129 : :
130 : 468 : n_words = MAX (2, (size + 6) >> 2);
131 : :
132 : 468 : if (n_words > STRINFO_MAX_WORDS)
133 : 0 : return FALSE;
134 : :
135 : 468 : words[0] = GUINT32_TO_LE (alias ? 0xfe : 0xff);
136 : 468 : words[n_words - 1] = GUINT32_TO_BE (0xff);
137 : 468 : memcpy (((gchar *) words) + 1, string, size + 1);
138 : :
139 : 468 : return n_words;
140 : : }
141 : :
142 : : G_GNUC_UNUSED static gint
143 : 327 : strinfo_scan (const guint32 *strinfo,
144 : : guint length,
145 : : const guint32 *words,
146 : : guint n_words)
147 : : {
148 : 327 : guint i = 0;
149 : :
150 : 327 : if (length < n_words)
151 : 4 : return -1;
152 : :
153 : 2619 : while (i <= length - n_words)
154 : : {
155 : 2371 : guint j = 0;
156 : :
157 : 2562 : for (j = 0; j < n_words; j++)
158 : 2487 : if (strinfo[i + j] != words[j])
159 : 2296 : break;
160 : :
161 : 2371 : if (j == n_words)
162 : 75 : return i; /* match */
163 : :
164 : : /* skip at least one word, continue */
165 : 2296 : i += j ? j : 1;
166 : : }
167 : :
168 : 248 : return -1;
169 : : }
170 : :
171 : : G_GNUC_UNUSED static gint
172 : 397 : strinfo_find_string (const guint32 *strinfo,
173 : : guint length,
174 : : const gchar *string,
175 : : gboolean alias)
176 : : {
177 : : guint32 words[STRINFO_MAX_WORDS];
178 : : guint n_words;
179 : :
180 : 397 : if (length == 0)
181 : 70 : return -1;
182 : :
183 : 327 : n_words = strinfo_string_to_words (string, words, alias);
184 : :
185 : 327 : return strinfo_scan (strinfo + 1, length - 1, words, n_words);
186 : : }
187 : :
188 : : G_GNUC_UNUSED static gint
189 : 105 : strinfo_find_integer (const guint32 *strinfo,
190 : : guint length,
191 : : guint32 value)
192 : : {
193 : : guint i;
194 : :
195 : 824 : for (i = 0; i < length; i++)
196 : 728 : if (strinfo[i] == GUINT32_TO_LE (value))
197 : : {
198 : 10 : const guchar *charinfo = (const guchar *) &strinfo[i];
199 : :
200 : : /* make sure it has 0xff on either side */
201 : 10 : if ((i == 0 || charinfo[-1] == 0xff) && charinfo[4] == 0xff)
202 : 9 : return i;
203 : : }
204 : :
205 : 96 : return -1;
206 : : }
207 : :
208 : : G_GNUC_UNUSED static gboolean
209 : 60 : strinfo_is_string_valid (const guint32 *strinfo,
210 : : guint length,
211 : : const gchar *string)
212 : : {
213 : 60 : return strinfo_find_string (strinfo, length, string, FALSE) != -1;
214 : : }
215 : :
216 : : G_GNUC_UNUSED static gboolean
217 : 12 : strinfo_enum_from_string (const guint32 *strinfo,
218 : : guint length,
219 : : const gchar *string,
220 : : guint *result)
221 : : {
222 : : gint index;
223 : :
224 : 12 : index = strinfo_find_string (strinfo, length, string, FALSE);
225 : :
226 : 12 : if (index < 0)
227 : 2 : return FALSE;
228 : :
229 : 10 : *result = GUINT32_FROM_LE (strinfo[index]);
230 : 10 : return TRUE;
231 : : }
232 : :
233 : : G_GNUC_UNUSED static const gchar *
234 : 105 : strinfo_string_from_enum (const guint32 *strinfo,
235 : : guint length,
236 : : guint value)
237 : : {
238 : : gint index;
239 : :
240 : 105 : index = strinfo_find_integer (strinfo, length, value);
241 : :
242 : 105 : if (index < 0)
243 : 96 : return NULL;
244 : :
245 : 9 : return 1 + (const gchar *) &strinfo[index + 1];
246 : : }
247 : :
248 : : G_GNUC_UNUSED static const gchar *
249 : 8 : strinfo_string_from_alias (const guint32 *strinfo,
250 : : guint length,
251 : : const gchar *alias)
252 : : {
253 : : gint index;
254 : :
255 : 8 : index = strinfo_find_string (strinfo, length, alias, TRUE);
256 : :
257 : 8 : if (index < 0)
258 : 3 : return NULL;
259 : :
260 : 5 : return 1 + (const gchar *) &strinfo[GUINT32_TO_LE (strinfo[index]) + 1];
261 : : }
262 : :
263 : : G_GNUC_UNUSED static GVariant *
264 : 2 : strinfo_enumerate (const guint32 *strinfo,
265 : : guint length)
266 : : {
267 : : GVariantBuilder builder;
268 : : const gchar *ptr, *end;
269 : :
270 : 2 : ptr = (gpointer) strinfo;
271 : 2 : end = ptr + 4 * length;
272 : :
273 : 2 : ptr += 4;
274 : :
275 : 2 : g_variant_builder_init_static (&builder, G_VARIANT_TYPE_STRING_ARRAY);
276 : :
277 : 20 : while (ptr < end)
278 : : {
279 : : /* don't include aliases */
280 : 18 : if (*ptr == '\xff')
281 : 8 : g_variant_builder_add (&builder, "s", ptr + 1);
282 : :
283 : : /* find the end of this string */
284 : 18 : ptr = memchr (ptr, '\xff', end - ptr);
285 : 18 : g_assert (ptr != NULL);
286 : :
287 : : /* skip over the int to the next string */
288 : 18 : ptr += 5;
289 : : }
290 : :
291 : 2 : return g_variant_builder_end (&builder);
292 : : }
293 : :
294 : : G_GNUC_UNUSED static void
295 : 128 : strinfo_builder_append_item (GString *builder,
296 : : const gchar *string,
297 : : guint value)
298 : : {
299 : : guint32 words[STRINFO_MAX_WORDS];
300 : : guint n_words;
301 : :
302 : 128 : value = GUINT32_TO_LE (value);
303 : :
304 : 128 : n_words = strinfo_string_to_words (string, words, FALSE);
305 : : g_string_append_len (builder, (void *) &value, sizeof value);
306 : 128 : g_string_append_len (builder, (void *) words, 4 * n_words);
307 : 128 : }
308 : :
309 : : G_GNUC_UNUSED static gboolean
310 : 16 : strinfo_builder_append_alias (GString *builder,
311 : : const gchar *alias,
312 : : const gchar *target)
313 : : {
314 : : guint32 words[STRINFO_MAX_WORDS];
315 : : guint n_words;
316 : : guint value;
317 : : gint index;
318 : :
319 : 16 : index = strinfo_find_string ((const guint32 *) builder->str,
320 : 16 : builder->len / 4, target, FALSE);
321 : :
322 : 16 : if (index == -1)
323 : 3 : return FALSE;
324 : :
325 : 13 : value = GUINT32_TO_LE (index);
326 : :
327 : 13 : n_words = strinfo_string_to_words (alias, words, TRUE);
328 : : g_string_append_len (builder, (void *) &value, sizeof value);
329 : 13 : g_string_append_len (builder, (void *) words, 4 * n_words);
330 : :
331 : 13 : return TRUE;
332 : : }
333 : :
334 : : G_GNUC_UNUSED static gboolean
335 : 152 : strinfo_builder_contains (GString *builder,
336 : : const gchar *string)
337 : : {
338 : 152 : return strinfo_find_string ((const guint32 *) builder->str,
339 : 301 : builder->len / 4, string, FALSE) != -1 ||
340 : 149 : strinfo_find_string ((const guint32 *) builder->str,
341 : 149 : builder->len / 4, string, TRUE) != -1;
342 : : }
343 : :
344 : : G_GNUC_UNUSED static gboolean
345 : 95 : strinfo_builder_contains_value (GString *builder,
346 : : guint value)
347 : : {
348 : 95 : return strinfo_string_from_enum ((const guint32 *) builder->str,
349 : 95 : builder->len / 4, value) != NULL;
350 : : }
|
