| 0,0 → 1,288 |
|---|
| /* |
| * Copyright (c) 2009 Jiri Svoboda |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * - Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * - Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * - The name of the author may not be used to endorse or promote products |
| * derived from this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| /** |
| * @addtogroup kbdgen generic |
| * @ingroup kbd |
| * @{ |
| */ |
| /** @file |
| * @brief Generic scancode parser. |
| * |
| * The scancode parser is a simple finite state machine. It is described |
| * using sequences of input symbols (scancodes) and the corresponding output |
| * value (mods, key pair). When the parser recognizes a sequence, |
| * it outputs the value and restarts. If a transition is undefined, |
| * the parser restarts, too. |
| * |
| * Apart from precise values, GSP_DEFAULT allows to catch general cases. |
| * I.e. if we knew that after 0x1b 0x4f there always follow two more |
| * scancodes, we can define (0x1b, 0x4f, GSP_DEFAULT, GSP_DEFAULT, GSP_END) |
| * with null output. This will force the parser to read the entire sequence, |
| * not leaving garbage on the input if it does not recognize the specific |
| * sequence. |
| */ |
| |
| #include <gsp.h> |
| #include <libadt/hash_table.h> |
| #include <stdlib.h> |
| #include <stdio.h> |
| |
| #define TRANS_TABLE_CHAINS 256 |
| |
| /* |
| * Hash table operations for the transition function. |
| */ |
| |
| static hash_index_t trans_op_hash(unsigned long key[]); |
| static int trans_op_compare(unsigned long key[], hash_count_t keys, |
| link_t *item); |
| static void trans_op_remove_callback(link_t *item); |
| |
| static hash_table_operations_t trans_ops = { |
| .hash = trans_op_hash, |
| .compare = trans_op_compare, |
| .remove_callback = trans_op_remove_callback |
| }; |
| |
| static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input); |
| static void trans_insert(gsp_t *p, gsp_trans_t *t); |
| static gsp_trans_t *trans_new(void); |
| |
| /** Initialise scancode parser. */ |
| void gsp_init(gsp_t *p) |
| { |
| p->states = 1; |
| hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops); |
| } |
| |
| /** Insert a series of definitions into the parser. |
| * |
| * @param p The parser. |
| * @param defs Definition list. Each definition starts with two output values |
| * (mods, key) and continues with a sequence of input values |
| * terminated with GSP_END. The definition list is terminated |
| * with two zeroes (0, 0) for output values. |
| */ |
| int gsp_insert_defs(gsp_t *p, const int *defs) |
| { |
| unsigned mods, key; |
| const int *dp; |
| int rc; |
| |
| dp = defs; |
| |
| while (1) { |
| /* Read the output values. */ |
| mods = *dp++; |
| key = *dp++; |
| if (key == 0) break; |
| |
| /* Insert one sequence. */ |
| rc = gsp_insert_seq(p, dp, mods, key); |
| if (rc != 0) |
| return rc; |
| |
| /* Skip to the next definition. */ |
| while (*dp != GSP_END) |
| ++dp; |
| ++dp; |
| } |
| |
| return 0; |
| } |
| |
| /** Insert one sequence into the parser. |
| * |
| * @param p The parser. |
| * @param seq Sequence of input values terminated with GSP_END. |
| * @param mods Corresponsing output value. |
| * @param key Corresponsing output value. |
| */ |
| int gsp_insert_seq(gsp_t *p, const int *seq, unsigned mods, unsigned key) |
| { |
| int state; |
| gsp_trans_t *t; |
| |
| state = 0; |
| t = NULL; |
| |
| /* Input sequence must be non-empty. */ |
| if (*seq == GSP_END) |
| return -1; |
| |
| while (*(seq + 1) != GSP_END) { |
| t = trans_lookup(p, state, *seq); |
| if (t == NULL) { |
| /* Create new state. */ |
| t = trans_new(); |
| t->old_state = state; |
| t->input = *seq; |
| t->new_state = p->states++; |
| |
| t->out_mods = 0; |
| t->out_key = 0; |
| |
| trans_insert(p, t); |
| } |
| state = t->new_state; |
| ++seq; |
| } |
| |
| /* Process the last transition. */ |
| t = trans_lookup(p, state, *seq); |
| if (t != NULL) { |
| exit(1); |
| return -1; /* Conflicting definition. */ |
| } |
| |
| t = trans_new(); |
| t->old_state = state; |
| t->input = *seq; |
| t->new_state = 0; |
| |
| t->out_mods = mods; |
| t->out_key = key; |
| |
| trans_insert(p, t); |
| |
| return 0; |
| } |
| |
| /** Compute one parser step. |
| * |
| * Computes the next state and output values for a given state and input. |
| * This handles everything including restarts and default branches. |
| * |
| * @param p The parser. |
| * @param state Old state. |
| * @param input Input symbol (scancode). |
| * @param mods Output value (modifier). |
| * @param key Output value (key). |
| * @return New state. |
| */ |
| int gsp_step(gsp_t *p, int state, int input, unsigned *mods, unsigned *key) |
| { |
| gsp_trans_t *t; |
| |
| t = trans_lookup(p, state, input); |
| if (t == NULL) { |
| t = trans_lookup(p, state, GSP_DEFAULT); |
| } |
| |
| if (t == NULL) { |
| printf("gsp_step: not found\n"); |
| *mods = NULL; |
| *key = NULL; |
| return 0; |
| } |
| |
| *mods = t->out_mods; |
| *key = t->out_key; |
| return t->new_state; |
| } |
| |
| /** Transition function lookup. |
| * |
| * Returns the value of the transition function for the given state |
| * and input. Note that the transition must be specified precisely, |
| * to obtain the default branch use input = GSP_DEFAULT. |
| * |
| * @param p Parser. |
| * @param state Current state. |
| * @param input Input value. |
| * @return The transition or @c NULL if not defined. |
| */ |
| static gsp_trans_t *trans_lookup(gsp_t *p, int state, int input) |
| { |
| link_t *item; |
| unsigned long key[2]; |
| |
| key[0] = state; |
| key[1] = input; |
| |
| item = hash_table_find(&p->trans, key); |
| if (item == NULL) return NULL; |
| |
| return hash_table_get_instance(item, gsp_trans_t, link); |
| } |
| |
| /** Define a new transition. |
| * |
| * @param p The parser. |
| * @param t Transition with all fields defined. |
| */ |
| static void trans_insert(gsp_t *p, gsp_trans_t *t) |
| { |
| unsigned long key[2]; |
| |
| key[0] = t->old_state; |
| key[1] = t->input; |
| |
| hash_table_insert(&p->trans, &key, &t->link); |
| } |
| |
| /** Allocate transition structure. */ |
| static gsp_trans_t *trans_new(void) |
| { |
| gsp_trans_t *t; |
| |
| t = malloc(sizeof(gsp_trans_t)); |
| if (t == NULL) { |
| printf("Memory allocation failed.\n"); |
| exit(1); |
| } |
| |
| return t; |
| } |
| |
| /* |
| * Transition function hash table operations. |
| */ |
| |
| static hash_index_t trans_op_hash(unsigned long key[]) |
| { |
| return (key[0] * 17 + key[1]) % TRANS_TABLE_CHAINS; |
| } |
| |
| static int trans_op_compare(unsigned long key[], hash_count_t keys, |
| link_t *item) |
| { |
| gsp_trans_t *t; |
| |
| t = hash_table_get_instance(item, gsp_trans_t, link); |
| return (key[0] == t->old_state && key[1] == t->input); |
| } |
| |
| static void trans_op_remove_callback(link_t *item) |
| { |
| } |
| |
| /** |
| * @} |
| */ |