source: mainline/uspace/srv/hid/input/gsp.c@ 901b302

ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 901b302 was 5e801dc, checked in by GitHub <noreply@…>, 6 years ago

Indicate and enforce constness of hash table key in certain functions (#158)

The assumption here is that modifying key in the hash/equal functions in something completely unexpected, and not something you would ever want to do intentionally, so it makes sense to disallow it entirely to get that extra level of checking.

  • Property mode set to 100644
File size: 7.0 KB
Line 
1/*
2 * Copyright (c) 2009 Jiri Svoboda
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/**
30 * @addtogroup kbdgen generic
31 * @ingroup input
32 * @{
33 */
34/** @file
35 * @brief Generic scancode parser.
36 *
37 * The scancode parser is a simple finite state machine. It is described
38 * using sequences of input symbols (scancodes) and the corresponding output
39 * value (mods, key pair). When the parser recognizes a sequence,
40 * it outputs the value and restarts. If a transition is undefined,
41 * the parser restarts, too.
42 *
43 * Apart from precise values, GSP_DEFAULT allows to catch general cases.
44 * I.e. if we knew that after 0x1b 0x4f there always follow two more
45 * scancodes, we can define (0x1b, 0x4f, GSP_DEFAULT, GSP_DEFAULT, GSP_END)
46 * with null output. This will force the parser to read the entire sequence,
47 * not leaving garbage on the input if it does not recognize the specific
48 * sequence.
49 */
50
51#include <adt/hash_table.h>
52#include <adt/hash.h>
53#include <stdbool.h>
54#include <stdlib.h>
55#include <stdio.h>
56#include "gsp.h"
57
58/*
59 * Transition function hash table operations.
60 */
61typedef struct {
62 int old_state;
63 int input;
64} trans_key_t;
65
66static size_t trans_key_hash(const void *key)
67{
68 const trans_key_t *trans_key = key;
69 return hash_combine(trans_key->input, trans_key->old_state);
70}
71
72static size_t trans_hash(const ht_link_t *item)
73{
74 gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link);
75 return hash_combine(t->input, t->old_state);
76}
77
78static bool trans_key_equal(const void *key, const ht_link_t *item)
79{
80 const trans_key_t *trans_key = key;
81 gsp_trans_t *t = hash_table_get_inst(item, gsp_trans_t, link);
82
83 return trans_key->input == t->input && trans_key->old_state == t->old_state;
84}
85
86static hash_table_ops_t trans_ops = {
87 .hash = trans_hash,
88 .key_hash = trans_key_hash,
89 .key_equal = trans_key_equal,
90 .equal = NULL,
91 .remove_callback = NULL
92};
93
94static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input);
95static void trans_insert(gsp_t *p, gsp_trans_t *t);
96static gsp_trans_t *trans_new(void);
97
98/** Initialize scancode parser. */
99void gsp_init(gsp_t *p)
100{
101 p->states = 1;
102 hash_table_create(&p->trans, 0, 0, &trans_ops);
103}
104
105/** Insert a series of definitions into the parser.
106 *
107 * @param p The parser.
108 * @param defs Definition list. Each definition starts with two output values
109 * (mods, key) and continues with a sequence of input values
110 * terminated with GSP_END. The definition list is terminated
111 * with two zeroes (0, 0) for output values.
112 */
113int gsp_insert_defs(gsp_t *p, const int *defs)
114{
115 unsigned mods, key;
116 const int *dp;
117 int rc;
118
119 dp = defs;
120
121 while (true) {
122 /* Read the output values. */
123 mods = *dp++;
124 key = *dp++;
125 if (key == 0)
126 break;
127
128 /* Insert one sequence. */
129 rc = gsp_insert_seq(p, dp, mods, key);
130 if (rc != 0)
131 return rc;
132
133 /* Skip to the next definition. */
134 while (*dp != GSP_END)
135 ++dp;
136 ++dp;
137 }
138
139 return 0;
140}
141
142/** Insert one sequence into the parser.
143 *
144 * @param p The parser.
145 * @param seq Sequence of input values terminated with GSP_END.
146 * @param mods Corresponsing output value.
147 * @param key Corresponsing output value.
148 */
149int gsp_insert_seq(gsp_t *p, const int *seq, unsigned mods, unsigned key)
150{
151 int state;
152 gsp_trans_t *t;
153
154 state = 0;
155 t = NULL;
156
157 /* Input sequence must be non-empty. */
158 if (*seq == GSP_END)
159 return -1;
160
161 while (*(seq + 1) != GSP_END) {
162 t = trans_lookup(p, state, *seq);
163 if (t == NULL) {
164 /* Create new state. */
165 t = trans_new();
166 t->old_state = state;
167 t->input = *seq;
168 t->new_state = p->states++;
169
170 t->out_mods = 0;
171 t->out_key = 0;
172
173 trans_insert(p, t);
174 }
175 state = t->new_state;
176 ++seq;
177 }
178
179 /* Process the last transition. */
180 t = trans_lookup(p, state, *seq);
181 if (t != NULL) {
182 exit(1);
183 return -1; /* Conflicting definition. */
184 }
185
186 t = trans_new();
187 t->old_state = state;
188 t->input = *seq;
189 t->new_state = 0;
190
191 t->out_mods = mods;
192 t->out_key = key;
193
194 trans_insert(p, t);
195
196 return 0;
197}
198
199/** Compute one parser step.
200 *
201 * Computes the next state and output values for a given state and input.
202 * This handles everything including restarts and default branches.
203 *
204 * @param p The parser.
205 * @param state Old state.
206 * @param input Input symbol (scancode).
207 * @param mods Output value (modifier).
208 * @param key Output value (key).
209 * @return New state.
210 */
211int gsp_step(gsp_t *p, int state, int input, unsigned *mods, unsigned *key)
212{
213 gsp_trans_t *t;
214
215 t = trans_lookup(p, state, input);
216 if (t == NULL) {
217 t = trans_lookup(p, state, GSP_DEFAULT);
218 }
219
220 if (t == NULL) {
221 printf("gsp_step: not found, state=%d, input=0x%x\n",
222 state, input);
223 *mods = 0;
224 *key = 0;
225 return 0;
226 }
227
228 *mods = t->out_mods;
229 *key = t->out_key;
230
231 return t->new_state;
232}
233
234/** Transition function lookup.
235 *
236 * Returns the value of the transition function for the given state
237 * and input. Note that the transition must be specified precisely,
238 * to obtain the default branch use input = GSP_DEFAULT.
239 *
240 * @param p Parser.
241 * @param state Current state.
242 * @param input Input value.
243 * @return The transition or @c NULL if not defined.
244 */
245static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input)
246{
247 ht_link_t *item;
248
249 trans_key_t key = {
250 .input = input,
251 .old_state = state
252 };
253
254 item = hash_table_find(&p->trans, &key);
255 if (item == NULL)
256 return NULL;
257
258 return hash_table_get_inst(item, gsp_trans_t, link);
259}
260
261/** Define a new transition.
262 *
263 * @param p The parser.
264 * @param t Transition with all fields defined.
265 */
266static void trans_insert(gsp_t *p, gsp_trans_t *t)
267{
268 hash_table_insert(&p->trans, &t->link);
269}
270
271/** Allocate transition structure. */
272static gsp_trans_t *trans_new(void)
273{
274 gsp_trans_t *t;
275
276 t = malloc(sizeof(gsp_trans_t));
277 if (t == NULL) {
278 printf("Memory allocation failed.\n");
279 exit(1);
280 }
281
282 return t;
283}
284
285/**
286 * @}
287 */
Note: See TracBrowser for help on using the repository browser.