Subversion Repositories HelenOS

Rev

Rev 4346 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  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 <adt/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] == (unsigned long) t->old_state)
  280.         && (key[1] == (unsigned long) t->input));
  281. }
  282.  
  283. static void trans_op_remove_callback(link_t *item)
  284. {
  285. }
  286.  
  287. /**
  288.  * @}
  289.  */
  290.