/*
* 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 <adt/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) {
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"); }
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] == (unsigned long) t->old_state)
&& (key[1] == (unsigned long) t->input));
}
static void trans_op_remove_callback(link_t *item)
{
}
/**
* @}
*/