nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * Copyright © 2010 Codethink Limited
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the licence, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
16 *
17 * Author: Ryan Lortie <desrt@desrt.ca>
18 */
19  
20 #include <string.h>
21 #include <glib.h>
22  
23 /*
24 * The string info map is an efficient data structure designed to be
25 * used with a small set of items. It is used by GSettings schemas for
26 * three purposes:
27 *
28 * 1) Implement <choices> with a list of valid strings
29 *
30 * 2) Implement <alias> by mapping one string to another
31 *
32 * 3) Implement enumerated types by mapping strings to integer values
33 * (and back).
34 *
35 * The map is made out of an array of uint32s. Each entry in the array
36 * is an integer value, followed by a specially formatted string value:
37 *
38 * The string starts with the byte 0xff or 0xfe, followed by the
39 * content of the string, followed by a nul byte, followed by
40 * additional nul bytes for padding, followed by a 0xff byte.
41 *
42 * Padding is added so that the entire formatted string takes up a
43 * multiple of 4 bytes, and not less than 8 bytes. The requirement
44 * for a string to take up 8 bytes is so that the scanner doesn't lose
45 * synch and mistake a string for an integer value.
46 *
47 * The first byte of the formatted string depends on if the integer is
48 * an enum value (0xff) or an alias (0xfe). If it is an alias then the
49 * number refers to the word offset within the info map at which the
50 * integer corresponding to the "target" value is stored.
51 *
52 * For example, consider the case of the string info map representing an
53 * enumerated type of 'foo' (value 1) and 'bar' (value 2) and 'baz'
54 * (alias for 'bar'). Note that string info maps are always little
55 * endian.
56 *
57 * x01 x00 x00 x00 xff 'f' 'o' 'o' x00 x00 x00 xff x02 x00 x00 x00
58 * xff 'b' 'a' 'r' x00 x00 x00 xff x03 x00 x00 x00 xfe 'b' 'a' 'z'
59 * x00 x00 x00 xff
60 *
61 *
62 * The operations that someone may want to perform with the map:
63 *
64 * - lookup if a string is valid (and not an alias)
65 * - lookup the integer value for a enum 'nick'
66 * - lookup the integer value for the target of an alias
67 * - lookup an alias and convert it to its target string
68 * - lookup the enum nick for a given value
69 *
70 * In order to lookup if a string is valid, it is padded on either side
71 * (as described) and scanned for in the array. For example, you might
72 * look for "foo":
73 *
74 * xff 'f' 'o' 'o' x00 x00 x00 xff
75 *
76 * In order to lookup the integer value for a nick, the string is padded
77 * on either side and scanned for in the array, as above. Instead of
78 * merely succeeding, we look at the integer value to the left of the
79 * match. This is the enum value.
80 *
81 * In order to lookup an alias and convert it to its target enum value,
82 * the string is padded on either side (as described, with 0xfe) and
83 * scanned for. For example, you might look for "baz":
84 *
85 * xfe 'b' 'a' 'z' x00 x00 x00 xff
86 *
87 * The integer immediately preceding the match then contains the offset
88 * of the integer value of the target. In our example, that's '3'.
89 * This index is dereferenced to find the enum value of '2'.
90 *
91 * To convert the alias to its target string, 5 bytes just need to be
92 * added past the start of the integer value to find the start of the
93 * string.
94 *
95 * To lookup the enum nick for a given value, the value is searched for
96 * in the array. To ensure that the value isn't matching the inside of a
97 * string, we must check that it is either the first item in the array or
98 * immediately preceded by the byte 0xff. It must also be immediately
99 * followed by the byte 0xff.
100 *
101 * Because strings always take up a minimum of 2 words, because 0xff or
102 * 0xfe never appear inside of a utf-8 string and because no two integer
103 * values ever appear in sequence, the only way we can have the
104 * sequence:
105 *
106 * xff __ __ __ __ xff (or 0xfe)
107 *
108 * is in the event of an integer nested between two strings.
109 *
110 * For implementation simplicity/efficiency, strings may not be more
111 * than 65 characters in length (ie: 17 32bit words after padding).
112 *
113 * In the event that we are doing <choices> (ie: not an enum type) then
114 * the value of each choice is set to zero and ignored.
115 */
116  
117 #define STRINFO_MAX_WORDS 17
118 G_GNUC_UNUSED static guint
119 strinfo_string_to_words (const gchar *string,
120 guint32 *words,
121 gboolean alias)
122 {
123 guint n_words;
124 gsize size;
125  
126 size = strlen (string);
127  
128 n_words = MAX (2, (size + 6) >> 2);
129  
130 if (n_words > STRINFO_MAX_WORDS)
131 return FALSE;
132  
133 words[0] = GUINT32_TO_LE (alias ? 0xfe : 0xff);
134 words[n_words - 1] = GUINT32_TO_BE (0xff);
135 memcpy (((gchar *) words) + 1, string, size + 1);
136  
137 return n_words;
138 }
139  
140 G_GNUC_UNUSED static gint
141 strinfo_scan (const guint32 *strinfo,
142 guint length,
143 const guint32 *words,
144 guint n_words)
145 {
146 guint i = 0;
147  
148 if (length < n_words)
149 return -1;
150  
151 while (i <= length - n_words)
152 {
153 guint j = 0;
154  
155 for (j = 0; j < n_words; j++)
156 if (strinfo[i + j] != words[j])
157 break;
158  
159 if (j == n_words)
160 return i; /* match */
161  
162 /* skip at least one word, continue */
163 i += j ? j : 1;
164 }
165  
166 return -1;
167 }
168  
169 G_GNUC_UNUSED static gint
170 strinfo_find_string (const guint32 *strinfo,
171 guint length,
172 const gchar *string,
173 gboolean alias)
174 {
175 guint32 words[STRINFO_MAX_WORDS];
176 guint n_words;
177  
178 if (length == 0)
179 return -1;
180  
181 n_words = strinfo_string_to_words (string, words, alias);
182  
183 return strinfo_scan (strinfo + 1, length - 1, words, n_words);
184 }
185  
186 G_GNUC_UNUSED static gint
187 strinfo_find_integer (const guint32 *strinfo,
188 guint length,
189 guint32 value)
190 {
191 guint i;
192  
193 for (i = 0; i < length; i++)
194 if (strinfo[i] == GUINT32_TO_LE (value))
195 {
196 const guchar *charinfo = (const guchar *) &strinfo[i];
197  
198 /* make sure it has 0xff on either side */
199 if ((i == 0 || charinfo[-1] == 0xff) && charinfo[4] == 0xff)
200 return i;
201 }
202  
203 return -1;
204 }
205  
206 G_GNUC_UNUSED static gboolean
207 strinfo_is_string_valid (const guint32 *strinfo,
208 guint length,
209 const gchar *string)
210 {
211 return strinfo_find_string (strinfo, length, string, FALSE) != -1;
212 }
213  
214 G_GNUC_UNUSED static gboolean
215 strinfo_enum_from_string (const guint32 *strinfo,
216 guint length,
217 const gchar *string,
218 guint *result)
219 {
220 gint index;
221  
222 index = strinfo_find_string (strinfo, length, string, FALSE);
223  
224 if (index < 0)
225 return FALSE;
226  
227 *result = GUINT32_FROM_LE (strinfo[index]);
228 return TRUE;
229 }
230  
231 G_GNUC_UNUSED static const gchar *
232 strinfo_string_from_enum (const guint32 *strinfo,
233 guint length,
234 guint value)
235 {
236 gint index;
237  
238 index = strinfo_find_integer (strinfo, length, value);
239  
240 if (index < 0)
241 return NULL;
242  
243 return 1 + (const gchar *) &strinfo[index + 1];
244 }
245  
246 G_GNUC_UNUSED static const gchar *
247 strinfo_string_from_alias (const guint32 *strinfo,
248 guint length,
249 const gchar *alias)
250 {
251 gint index;
252  
253 index = strinfo_find_string (strinfo, length, alias, TRUE);
254  
255 if (index < 0)
256 return NULL;
257  
258 return 1 + (const gchar *) &strinfo[GUINT32_TO_LE (strinfo[index]) + 1];
259 }
260  
261 G_GNUC_UNUSED static GVariant *
262 strinfo_enumerate (const guint32 *strinfo,
263 guint length)
264 {
265 GVariantBuilder builder;
266 const gchar *ptr, *end;
267  
268 ptr = (gpointer) strinfo;
269 end = ptr + 4 * length;
270  
271 ptr += 4;
272  
273 g_variant_builder_init (&builder, G_VARIANT_TYPE_STRING_ARRAY);
274  
275 while (ptr < end)
276 {
277 /* don't include aliases */
278 if (*ptr == '\xff')
279 g_variant_builder_add (&builder, "s", ptr + 1);
280  
281 /* find the end of this string */
282 ptr = memchr (ptr, '\xff', end - ptr);
283 g_assert (ptr != NULL);
284  
285 /* skip over the int to the next string */
286 ptr += 5;
287 }
288  
289 return g_variant_builder_end (&builder);
290 }
291  
292 G_GNUC_UNUSED static void
293 strinfo_builder_append_item (GString *builder,
294 const gchar *string,
295 guint value)
296 {
297 guint32 words[STRINFO_MAX_WORDS];
298 guint n_words;
299  
300 value = GUINT32_TO_LE (value);
301  
302 n_words = strinfo_string_to_words (string, words, FALSE);
303 g_string_append_len (builder, (void *) &value, sizeof value);
304 g_string_append_len (builder, (void *) words, 4 * n_words);
305 }
306  
307 G_GNUC_UNUSED static gboolean
308 strinfo_builder_append_alias (GString *builder,
309 const gchar *alias,
310 const gchar *target)
311 {
312 guint32 words[STRINFO_MAX_WORDS];
313 guint n_words;
314 guint value;
315 gint index;
316  
317 index = strinfo_find_string ((const guint32 *) builder->str,
318 builder->len / 4, target, FALSE);
319  
320 if (index == -1)
321 return FALSE;
322  
323 value = GUINT32_TO_LE (index);
324  
325 n_words = strinfo_string_to_words (alias, words, TRUE);
326 g_string_append_len (builder, (void *) &value, sizeof value);
327 g_string_append_len (builder, (void *) words, 4 * n_words);
328  
329 return TRUE;
330 }
331  
332 G_GNUC_UNUSED static gboolean
333 strinfo_builder_contains (GString *builder,
334 const gchar *string)
335 {
336 return strinfo_find_string ((const guint32 *) builder->str,
337 builder->len / 4, string, FALSE) != -1 ||
338 strinfo_find_string ((const guint32 *) builder->str,
339 builder->len / 4, string, TRUE) != -1;
340 }
341  
342 G_GNUC_UNUSED static gboolean
343 strinfo_builder_contains_value (GString *builder,
344 guint value)
345 {
346 return strinfo_string_from_enum ((const guint32 *) builder->str,
347 builder->len / 4, value) != NULL;
348 }