Subversion Repositories HelenOS

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
4377 svoboda 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  kbd
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 <gsp.h>
52
#include <libadt/hash_table.h>
53
#include <stdlib.h>
54
#include <stdio.h>
55
 
56
#define TRANS_TABLE_CHAINS 256
57
 
58
/*
59
 * Hash table operations for the transition function.
60
 */
61
 
62
static hash_index_t trans_op_hash(unsigned long key[]);
63
static int trans_op_compare(unsigned long key[], hash_count_t keys,
64
    link_t *item);
65
static void trans_op_remove_callback(link_t *item);
66
 
67
static hash_table_operations_t trans_ops = {
68
    .hash = trans_op_hash,
69
    .compare = trans_op_compare,
70
    .remove_callback = trans_op_remove_callback
71
};
72
 
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);
75
static gsp_trans_t *trans_new(void);
76
 
77
/** Initialise scancode parser. */
78
void gsp_init(gsp_t *p)
79
{
80
    p->states = 1;
81
    hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops);
82
}
83
 
84
/** Insert a series of definitions into the parser.
85
 *
86
 * @param p The parser.
87
 * @param defs  Definition list. Each definition starts with two output values
88
 *      (mods, key) and continues with a sequence of input values
89
 *      terminated with GSP_END. The definition list is terminated
90
 *      with two zeroes (0, 0) for output values.
91
 */
92
int gsp_insert_defs(gsp_t *p, const int *defs)
93
{
94
    unsigned mods, key;
95
    const int *dp;
96
    int rc;
97
 
98
    dp = defs;
99
 
100
    while (1) {
101
        /* Read the output values. */
102
        mods = *dp++;
103
        key = *dp++;
104
        if (key == 0) break;
105
 
106
        /* Insert one sequence. */     
107
        rc = gsp_insert_seq(p, dp, mods, key);
108
        if (rc != 0)
109
            return rc;
110
 
111
        /* Skip to the next definition. */
112
        while (*dp != GSP_END)
113
            ++dp;
114
        ++dp;
115
    }
116
 
117
    return 0;
118
}
119
 
120
/** Insert one sequence into the parser.
121
 *
122
 * @param p The parser.
123
 * @param seq   Sequence of input values terminated with GSP_END.
124
 * @param mods  Corresponsing output value.
125
 * @param key   Corresponsing output value.
126
 */
127
int gsp_insert_seq(gsp_t *p, const int *seq, unsigned mods, unsigned key)
128
{
129
    int state;
130
    gsp_trans_t *t;
131
 
132
    state = 0;
133
    t = NULL;
134
 
135
    /* Input sequence must be non-empty. */
136
    if (*seq == GSP_END)
137
        return -1;
138
 
139
    while (*(seq + 1) != GSP_END) {
140
        t = trans_lookup(p, state, *seq);
141
        if (t == NULL) {
142
            /* Create new state. */
143
            t = trans_new();
144
            t->old_state = state;
145
            t->input = *seq;
146
            t->new_state = p->states++;
147
 
148
            t->out_mods = 0;
149
            t->out_key = 0;
150
 
151
            trans_insert(p, t);
152
        }
153
        state = t->new_state;
154
        ++seq;
155
    }
156
 
157
    /* Process the last transition. */
158
    t = trans_lookup(p, state, *seq);
159
    if (t != NULL) {
160
        exit(1);
161
        return -1;  /* Conflicting definition. */
162
    }
163
 
164
    t = trans_new();
165
    t->old_state = state;
166
    t->input = *seq;
167
    t->new_state = 0;
168
 
169
    t->out_mods = mods;
170
    t->out_key = key;
171
 
172
    trans_insert(p, t);
173
 
174
    return 0;
175
}
176
 
177
/** Compute one parser step.
178
 *
179
 * Computes the next state and output values for a given state and input.
180
 * This handles everything including restarts and default branches.
181
 *
182
 * @param p     The parser.
183
 * @param state     Old state.
184
 * @param input     Input symbol (scancode).
185
 * @param mods      Output value (modifier).
186
 * @param key       Output value (key).
187
 * @return      New state.
188
 */
189
int gsp_step(gsp_t *p, int state, int input, unsigned *mods, unsigned *key)
190
{
191
    gsp_trans_t *t;
192
 
193
    t = trans_lookup(p, state, input);
194
    if (t == NULL) {
195
        t = trans_lookup(p, state, GSP_DEFAULT);
196
    }
197
 
198
    if (t == NULL) {
199
        printf("gsp_step: not found\n");
200
        *mods = NULL;
201
        *key = NULL;
202
        return 0;
203
    }
204
 
205
    *mods = t->out_mods;
206
    *key = t->out_key;
207
    return t->new_state;
208
}
209
 
210
/** Transition function lookup.
211
 *
212
 * Returns the value of the transition function for the given state
213
 * and input. Note that the transition must be specified precisely,
214
 * to obtain the default branch use input = GSP_DEFAULT.
215
 *
216
 * @param p     Parser.
217
 * @param state     Current state.
218
 * @param input     Input value.
219
 * @return      The transition or @c NULL if not defined.
220
 */
221
static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input)
222
{
223
    link_t *item;
224
    unsigned long key[2];
225
 
226
    key[0] = state;
227
    key[1] = input;
228
 
229
    item = hash_table_find(&p->trans, key);
230
    if (item == NULL) return NULL;
231
 
232
    return hash_table_get_instance(item, gsp_trans_t, link);
233
}
234
 
235
/** Define a new transition.
236
 *
237
 * @param p The parser.
238
 * @param t Transition with all fields defined.
239
 */
240
static void trans_insert(gsp_t *p, gsp_trans_t *t)
241
{
242
    unsigned long key[2];
243
 
244
    key[0] = t->old_state;
245
    key[1] = t->input;
246
 
247
    hash_table_insert(&p->trans, &key, &t->link);
248
}
249
 
250
/** Allocate transition structure. */
251
static gsp_trans_t *trans_new(void)
252
{
253
    gsp_trans_t *t;
254
 
255
    t = malloc(sizeof(gsp_trans_t));
256
    if (t == NULL) {
257
        printf("Memory allocation failed.\n");
258
        exit(1);
259
    }
260
 
261
    return t;
262
}
263
 
264
/*
265
 * Transition function hash table operations.
266
 */
267
 
268
static hash_index_t trans_op_hash(unsigned long key[])
269
{
270
    return (key[0] * 17 + key[1]) % TRANS_TABLE_CHAINS;
271
}
272
 
273
static int trans_op_compare(unsigned long key[], hash_count_t keys,
274
    link_t *item)
275
{
276
    gsp_trans_t *t;
277
 
278
    t = hash_table_get_instance(item, gsp_trans_t, link);
279
    return (key[0] == t->old_state && key[1] == t->input);
280
}
281
 
282
static void trans_op_remove_callback(link_t *item)
283
{
284
}
285
 
286
/**
287
 * @}
288
 */