Subversion Repositories HelenOS

/*

 * 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) {

        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] == (unsigned long) t->old_state)

        && (key[1] == (unsigned long) t->input));

}

static void trans_op_remove_callback(link_t *item)

{

}

/**

 * @}

 */