Identificación de respuestas a comandos AT en ISR. Intérprete de comandos.

Gestionar un módulo GSM por comandos AT, recibir, buscar e interpretar tanto las respuestas a comandos como las no solicitadas (URC) no es una cuestión menor si se requiere una solución eficiente, robusta y flexible.
Sabiendo que cada comando AT tiene por resultado un conjunto posible de respuestas y que estas se representan por cadenas de caracteres codificadas en ASCII, en principio, el software que las recibe tiene por objetivo identificarlas de acuerdo al comando enviado, sin olvidar la detección de aquellas no solicitadas, aún cuando aguarda la respuesta a un comando enviado. También se lo conoce como intérprete de comandos AT.
La intención del presente artículo es proponer una solución a esta problemática, siguiendo las ideas de la publicación Administración de módulos GSM en sistemas reactivos, basada en la estructura de datos tipo árbol y los autómatas finitos, también conocidas como máquinas de estados finitas.

Patrones

De acuerdo con la norma ITU-T V.250 - Serial asynchronous automatic dialling and control, el DCE (en este caso módulo GSM) puede emitir dos tipos de respuesta: de texto de información y de código de resultado. Las respuestas de texto de información consisten en tres partes: un encabezamiento, texto y un epílogo, [encabezamiento][texto][epílogo]. Generalmente, los caracteres transmitidos para el encabezamiento y el epílogo son <CR><LF> o "\r\n".
Mientras que los códigos de resultado consisten en tres partes: un encabezamiento, el texto de resultado, y un epílogo. Nuevamente, los caracteres transmitidos para el encabezamiento y el epílogo suelen ser  <CR><LF> o "\r\n". El texto de resultado puede transmitirse como un número o como una cadena, a elección del usuario.
Hay tres tipos de códigos de resultado: final, intermedio y no solicitado.

• Código de resultado final indica la compleción de una acción íntegra del DCE y que se está en disposición de aceptar nuevas instrucciones o comandos del DTE. Ejemplos: OK, ERROR, BUSY, etc.
• Código de resultado intermedio es un informe del progreso de una acción del DCE. CONNECT es uno de ellos.
• Códigos de resultado no solicitado tales como RING indican que se ha producido un evento no asociado directamente con la emisión de una instrucción del DTE.

No siempre las respuestas a comandos AT son constantes, como OK, ERROR o RING, en ciertos casos transportan información que puede ser variable en un formato definido por el comando enviado, por ejemplo "\r\nOK\r\n\r\n<value>\r\n", donde <value> es un valor numérico de 1 a 3 dígitos decimales,  "\r\nOK\r\n\r\n<id>", donde <id> es una cadena de caracteres, o "\r\nCONNECTr\n<data>\r\n", donde <data> es un conjunto de datos numéricos.

Por lo tanto, respecto del software receptor que identifica respuestas conviene denominarlas patrones.

Mecanismo de recepción

El software que identifica y/o busca los patrones podría:

1. Ejecutarse en contexto de interrupción, específicamente ISR de recepción, con lo cual la identificación o búsqueda progresa a medida que ingresan caracteres desde el módulo, podría decirse que la búsqueda es "on-line".
2. Almacenar en ISR los caracteres recibidos, para luego realizar la búsqueda fuera de interrupción, con lo cual las restricciones de ejecución son menos exigentes que la anterior.
3. Ser una combinación de las anteriores, en la cual, la ISR sólo identifica cadenas válidas, determinando su inicio y fin (encabezamiento y epílogo), para luego notificar al algoritmo que comience la búsqueda directamente sobre la cadena válida recibida.
4. otras.

Las soluciones presentadas requieren conocer, antes de comenzar la búsqueda, el conjunto de cadenas a esperar de acuerdo con el comando enviado y los URC disponibles.

Búsqueda de patrones
 

En base al ítem 1) y lo expuesto en el artículo Administración de módulos GSM en sistemas reactivos se pretende diseñar e implementar un mecanismo, incluyendo el algoritmo de búsqueda de patrones, que  cumpla con las siguientes premisas:

1. la búsqueda se realiza "on-line", es decir, esta progresa a medida que ingresan caracteres desde el módulo de comunicaciones en contexto de interrupción.
2. conoce el conjunto de respuestas a esperar, en función del comando enviado,
3. identifica los URC, 
4. la búsqueda se realiza sobre cadenas codificadas en ASCII,
5. permite buscar cadenas con formato y argumentos (patrones).
6. los patrones de búsqueda se especifican en tiempo de compilación, 
7. la entrada de patrones debe ser intuitiva, visualmente clara y flexible,
8. los patrones deben ubicarse en ROM,
9. no requiere preprocesamiento de la cadena de entrada,
10. posee un mecanismo sencillo de notificación al encontrar un patrón.

Uno de los mayores desafíos es lograr una búsqueda "on-line" eficiente, evitando el uso de búsquedas lineales por el método de la fuerza bruta consistiendo básicamente en buscar los patrones esperados en el buffer de recepción mediante el uso de funciones como strcmp(). 

Para lograr una búsqueda más eficiente, el artículo se focaliza en un estructura de datos de tipo árbol, la cual permite arreglar los patrones en un diagrama como muestra la Fig. 1:

Figura 1 - Arbol de recepción

La siguiente lista muestra los patrones que representa el árbol:

1. "ring\r\n"
2. "at\r\nok\r\n"
3. "at\r\nerror\r\n" 
4. "at\r\n..."
5. "atdt<n>\r\nok\r\n"
6. "atdt<n>\r\nerror\r\n"
7. "atdt<n>\r\nno carrier\r\n" 
8. "atdt<n>\r\nbusy\r\n" 
9. "atdt<n>\r\n..." 

Por definición: un árbol es una estructura de datos que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, llamado raíz. Por otro lado, un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

De la Fig. 1, cada rama representa un patrón, que comienza desde el nodo root y se extiende hasta un nodo hoja, coloreados en negro, por lo tanto, el patrón desde (1) a (2) representa la cadena "ring\r\n".

El algoritmo de búsqueda consiste en comparar el caracter recibido con los esperados por el nodo actual, y determinar así el siguiente nodo. Por ejemplo, el nodo (4) espera los caracteres 'e' y 'o', si el caracter recibido no coincide con ninguno de estos, entonces la búsqueda falló y el árbol vuelve a su raíz. Si por el contrario, se recibe 'e' el algoritmo toma la rama izquierda, y si recibe 'o', toma la derecha, estableciendo un nuevo nodo, diferente al root. Resumiendo:

• mientras el caracter recibido pertenezca a los esperado por el nodo, la búsqueda continúa, caso contrario vuelve al root,
• la búsqueda termina con éxito, si se encuentra el nodo hoja, aquellos coloreados en negro, en cuyo caso vuelve al root,
• la búsqueda se realiza en cada caracter recibido desde ISR, lo que implica unas pocas comparaciones de caracteres para determinar el próximo nodo. Esto demuestra la eficiencia del método,
• el funcionamiento se resume al de un autómata finito, en donde el alfabeto de entrada se forma por los caracteres enviados por el módulo, los estados por los nodos y las transiciones por el enlace entre estos,
• cuando la búsqueda se realiza con éxito, el mecanismo notifica que ha sido recibido el patrón en cuestión, el cual se forma desde nodo root al nodo hoja.

Por otro lado, para que el algoritmo identifique el comando enviado y con esto los patrones a esperar, el método requiere habilitar el eco de comandos (ATE1). Con lo cual, estando en el nodo root y habiendo enviado un comando al módulo, el algoritmo primero recibe el eco y con este determina el conjunto de respuestas que espera. Sin embargo, si esta característica no se necesita, el eco puede desactivarse (ATE0) y el árbol debe armarse acordemente.

Nodo transparente

En la Fig. 1, el nodo coloreado con rojo representa un nodo con una característica especial: si el caracter recibido no coincide con los esperados no transita al nodo root como lo hace el resto, por el contrario, permanece en este hasta que arribe el caracter esperado, en (5) el nodo no cambia hasta que reciba '\r', esto permite obviar la cadena de números variable que posee el comando ATDT.
Por lo tanto, sin el nodo transparente, cada envío del comando ATDT requeriría conocer el número discado para poder determinar el patrón de búsqueda. Los nodos transparentes son básicamente "comodines", los cuales se utilizan para busqueda de patrones con datos variables.

Simplificando el árbol

Observando la Fig. 1 puede simplificarse la representación de patrones, agrupando los nodos que se encuentren desde uno que tenga más de un hijo hasta un nodo hoja, descendiendo en la jerarquía, por ejemplo, desde (1) hasta (2): "ring\r\n", desde (1) hasta (3): "at", de (3) hasta (4): "\r\n", etc. Lo mismo ocurre con un nodo del tipo transparente, agrupando desde (3) hasta (5): "dt"y luego de (5) hasta (6): "\r\n". Ahora el árbol se representa como muestra la Fig. 2. En este la representación de patrones es más clara y sencilla.

Figura 2 - Arbol de recepción simplificado

Respecto al funcionamiento, ahora el algoritmo transita a un nuevo nodo (manteniendo la búsqueda) si el caracter ingresado es el último caracter de la cadena esperada. Por ejemplo, estando en root si ingresa el caracter 'r' el algoritmo adopta la rama izquierda hacia (2), mientras que si ingresa 'a' adopta la rama derecha hacia (3). Habiendo adoptado una rama, es decir, habiendo comenzado una nueva búsqueda, por ejemplo, sobre la rama izquierda, el patrón esperado es la cadena "ring\r\n", como ya ingresó el caracter 'r' espera el caracter 'i', luego el 'n', el 'g', el '\r', y por último el '\n', en cuyo caso la búsqueda termina con éxito. Si el caracter ingresado no coincide con el esperado, la búsqueda falla y termina volviendo a root. La Fig. 3 resume el proceso de búsqueda con dos ejemplos, el primero es el URC RING y el segundo corresponde con el comando ATDT:

Figura 3 - Proceso de búsqueda

El segundo ejemplo, muestra el comportamiento del nodo transparente, el cual transita hacia el nodo (6) si y sólo si recibe el caracter '\r'.

Implementación del algoritmo
 
El diagrama de la Fig. 4 modela el comportamiento del algoritmo mediante un autómata finito.

Figura 4 - Autómata del algoritmo

donde:

1. Existen dos estados, Idle y  InSearch, de los cuales el primero es el estado inicial.
2. Al inicializar el autómata, establece su nodo actual como root.
3. En estado Idle, con cada caracter recibido c se verifica si pertenece a alguno de los patrones asociados al root, mediante searchPatt() y se invoca a la callback asociada al nodo actual, pasándole como parámetro el caracter c, mediante deliver(). Si c pertenece a uno de los patrones, se verifica si la búsqueda está completa, si es así notifica y vuelve a root, de lo contrario continúa la búsqueda, estableciendo el próximo caracter a esperar y transitando al estado InSearch. Si no encuentra coincidencia, la búsqueda se descarta, llamando a notMatch().
4. En estado InSearch, con cada caracter recibido se verifica si pertenece al patrón en búsqueda mediante isInPatt() y se invoca a la callback asociada al nodo actual, mediante deliver(). Si c pertenece al patrón actual, se verifica si la búsqueda está completa mediante isMatch(), si es así notifica y vuelve a root, llamando a match(), caso contrario, establece el próximo caracter a esperar por medio de incPatt(). Si no encuentra coincidencia y c difiere del esperado la búsqueda se descarta llamando a notMatch(), pero si c es igual al anterior la búsqueda aún se mantiene, por medio de la llamada a isEqual().

Ejemplo práctico

La Fig. 5 muestra el árbol anterior pero con los nodos identificados y algunas simplificaciones adicionales.

Figura 5 - Arbol de patrones

Ahora, el árbol anterior se representa mediante las estructuras de datos almacenadas en ROM. Puede observarse que estas permanecen ocultas mediante macros, para evitar recordar su nombre y tipo, favoreciendo la claridad y legibilidad del programa.

 

/*
 *   Root node.
 */
SSP_CREATE_NORMAL_NODE(root);
SSP_CREATE_BR_TABLE(root)
   SSPBR("ring\r\n",     incCall, &root),
   SSPBR("at",           NULL,    &at  ),
SSP_END_BR_TABLE

/*
 *   AT node.
 */
SSP_CREATE_NORMAL_NODE(at);
SSP_CREATE_BR_TABLE(at)
   SSPBR("dt",            NULL,     &atdt),
   SSPBR("\r\nok\r\n",    cmdOk,    &root),
   SSPBR("\r\nerror\r\n", cmdError, &root),
SSP_END_BR_TABLE

/*
 *   ATDT node.
 */
SSP_CREATE_TRN_NODE(atdt, NULL);
SSP_CREATE_BR_TABLE(atdt)
   SSPBR("ok\r\n",         cmdOk,           &root),
   SSPBR("\r\nerror\r\n",  cmdError,        &root),
   SSPBR("no carrier\r\n", cmdErrNocarrier, &root),
   SSPBR("busy\r\n",       cmdErrBusy,      &root),
SSP_END_BR_TABLE

donde:

   (4) La macro SSP_CREATE_NORMAL_NODE() declara un nodo del tipo normal, es decir, no es transparente.
   (5) Cada nodo tiene asociado una tabla en donde se especifican los enlaces a sus nodos hijos. A su vez, cada uno de estos tiene asociado el patrón, una función de callback, y el próximo nodo. En caso de identificar el patrón en cuestión, si está disponible se ejecuta la función de callback, la cual generalmente notifica la detección del patrón y luego el árbol cambia de nodo según se indica. Este cambio puede corresponderse con la idea de esperar un nuevo patrón o bien terminar la búsqueda volviendo a root.
    (6) La macro SSPBR() representa un enlace del nodo root, en donde "ring\r\n" es el patrón a buscar. Si el algoritmo lo detecta, llama a la función incCall(), la cual notifica la ocurrencia y vuelve al nodo root.
    (7) Si se encuentra el patrón "at" el árbol cambia al nodo at.
    (8) La macro SSP_END_BR_TABLE indica el final de la tabla de enlaces.
  (23) La macro SSP_CREATE_TRN_NODE() declara un nodo del tipo transparente, el primer argumento de la macro es el nombre del nodo atdt, mientras que el segundo es el nombre de una función de callback, la cual se invoca con cada caracter recibido, en este caso no se utiliza.

En funcionamiento

La puesta en marcha del método es realmente sencilla. Primeramente es necesario invocar la función ssp_init(const SSP_NNORM_T *root) antes de ejecutar el algoritmo, la cual recibe como parámetro el nombre del nodo raíz del árbol, en el ejemplo presentado root. Y por último, desde ISR de recepción se agrega la llamada a función ssp_doSearch(unsigned char c) pasándole como parámetro los caracteres ingresados desde UART.

Detalles de implementación

A continuación se incluyen las estructuras de datos subyacentes que sostienen el método.

typedef void (*SSPTrnAction)(unsigned char c);
typedef void (*SSPBranchAction)(unsigned char pos);

/**
 *  \brief
 *  Maintains the basic information of a node.
 */
typedef struct SSPBase SSPBase;
struct SSPBase
{
    /**
     *  \brief
     *  Type of node.
     * Contains the type of a particular node and can have the following 
     * values:
     *
     * - \b SSP_NNORM: normal node.
     * - \b SSP_NTRN:  transparent node.
     */
    unsigned char type;

    /**
     *  \brief
     * Points to node's branch table.
     */
    const struct SSPBranch *branchTbl;

    /**
     *  \brief
     * Node name.
     * String terminated in '\\0' that represents the name of node. It's 
     * generally used for debugging.
     */
    char *name;
};

/**
 *  \brief
 *  Describes the tree branch or node transition.
 */
typedef struct SSPBranch SSPBranch;
struct SSPBranch
{
    /**
     *  \brief
     *  Pattern to search.
     *  String terminated in '\\0'.
     */
    unsigned char *patt;

    /**
     *  \brief
     *  Points to action function.
     *  This function is invoked when the pattern is found.
     */
    SSPBranchAction branchAction;

    /**
     *  \brief
     *  Points to target node.
     */
    const SSPBase *target;
};

typedef struct SSPNodeNormal SSPNodeNormal;
struct SSPNodeNormal
{
    /**
     *  \brief
     * Maintains the basic information of node.
     */
    SSPBase base;
};

typedef struct SSPNodeTrn SSPNodeTrn;
struct SSPNodeTrn
{
    /**
     *  \brief
     * Maintains the basic information of node.
     */
    SSPBase base;

    /**
     *  \brief
     *  Points to action function.
     *  This function is invoked on arriving a input character.
     */
    SSPTrnAction trnAction;
};

Debido a la simplicidad del diagrama de estados, el autómata se implementa mediante un simple switch-case con algunas sentencias if-else.

SSPResult 
ssp_doSearch(unsigned char c)
{
    int r;

    switch (state)
    {
        case SSP_IDLE:
            r = ssp_searchPatt(c);
            ssp_deliver(c);

            if (r == SSP_FOUND)
            {
                pos = 0;
                ssp_incPatt();
                if (ssp_isMatch())
                {
                    ssp_match();
                }
                else
                {
                    ssp_initSearch();
                }
            }
            else
            {
                ssp_notMatch();
            }
            break;
        case SSP_INSEARCH:
            ssp_deliver(c);

            if (ssp_isInPatt(c))
            {
                ++pos;
                ssp_incPatt();
                if (ssp_isMatch())
                {
                    ssp_match();
                }
                else
                {
                    result = SSP_SEARCH_CONTINUES;
                }
            }
            else if (!ssp_isEqual(c))
            {
                ssp_notMatch();
            }
            else
            {
                result = SSP_DUPLICATED_CHAR;
            }
            break;
        default:
            break;
    }
    return result;
}

Conclusiones

El método descripto permite identificar tanto las respuestas a comandos AT como los URC en contexto de interrupción, sin utilizar las técnicas convencionales basadas en búsquedas lineales. El algoritmo en cuestión se ejecuta progresivamente en ISR, a medida que ingresan los caracteres desde el módulo de comunicaciones GSM, GPS, dial-up u otro. Para que este sea eficiente en términos de ejecución y ocupación de memoria, utiliza tanto la estructura de datos tipo árbol como los conceptos de autómatas finitos. No obstante, el método no sólo se focaliza en su velocidad sino también en que la búsqueda e identificación radique exclusivamente en la construcción del árbol de patrones, olvidando así la codificación de la misma cada vez que se requiere una nueva entrada. Por otra parte, dada la generalización del algoritmo, puede ser útil en diversas aplicaciones.

Referencias

[1] RKH, “RKH Sourceforge download site,”, http://sourceforge.net/projects/rkh-reactivesys/, August 7, 2010.
[2] Mark A. Weiss, "Data Structures and Algorithm Analysis in C," (Second Edition), Addison-Wesley, 1997.
[3] ITU-T V.250 - Serial asynchronous automatic dialling and control, ITU-T, 2003.

Por razones de simplicidad, el artículo no incluye el código fuente completo del algoritmo. Aunque puede solicitarse por medio de e-mail.