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