diff options
Diffstat (limited to 'mesalib/src/mesa/shader/grammar')
| -rw-r--r-- | mesalib/src/mesa/shader/grammar/grammar.c | 3178 | ||||
| -rw-r--r-- | mesalib/src/mesa/shader/grammar/grammar.h | 103 | ||||
| -rw-r--r-- | mesalib/src/mesa/shader/grammar/grammar_crt.c | 64 | ||||
| -rw-r--r-- | mesalib/src/mesa/shader/grammar/grammar_crt.h | 20 | ||||
| -rw-r--r-- | mesalib/src/mesa/shader/grammar/grammar_mesa.c | 87 | ||||
| -rw-r--r-- | mesalib/src/mesa/shader/grammar/grammar_mesa.h | 43 | ||||
| -rw-r--r-- | mesalib/src/mesa/shader/grammar/grammar_syn.h | 202 |
7 files changed, 3697 insertions, 0 deletions
diff --git a/mesalib/src/mesa/shader/grammar/grammar.c b/mesalib/src/mesa/shader/grammar/grammar.c new file mode 100644 index 000000000..a9775961d --- /dev/null +++ b/mesalib/src/mesa/shader/grammar/grammar.c @@ -0,0 +1,3178 @@ +/* + * Mesa 3-D graphics library + * Version: 6.6 + * + * Copyright (C) 1999-2006 Brian Paul All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN + * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * \file grammar.c + * syntax parsing engine + * \author Michal Krol + */ + +#ifndef GRAMMAR_PORT_BUILD +#error Do not build this file directly, build your grammar_XXX.c instead, which includes this file +#endif + +/* +*/ + +/* + INTRODUCTION + ------------ + + The task is to check the syntax of an input string. Input string is a stream of ASCII + characters terminated with a null-character ('\0'). Checking it using C language is + difficult and hard to implement without bugs. It is hard to maintain and make changes when + the syntax changes. + + This is because of a high redundancy of the C code. Large blocks of code are duplicated with + only small changes. Even use of macros does not solve the problem because macros cannot + erase the complexity of the problem. + + The resolution is to create a new language that will be highly oriented to our task. Once + we describe a particular syntax, we are done. We can then focus on the code that implements + the language. The size and complexity of it is relatively small than the code that directly + checks the syntax. + + First, we must implement our new language. Here, the language is implemented in C, but it + could also be implemented in any other language. The code is listed below. We must take + a good care that it is bug free. This is simple because the code is simple and clean. + + Next, we must describe the syntax of our new language in itself. Once created and checked + manually that it is correct, we can use it to check another scripts. + + Note that our new language loading code does not have to check the syntax. It is because we + assume that the script describing itself is correct, and other scripts can be syntactically + checked by the former script. The loading code must only do semantic checking which leads us to + simple resolving references. + + THE LANGUAGE + ------------ + + Here I will describe the syntax of the new language (further called "Synek"). It is mainly a + sequence of declarations terminated by a semicolon. The declaration consists of a symbol, + which is an identifier, and its definition. A definition is in turn a sequence of specifiers + connected with ".and" or ".or" operator. These operators cannot be mixed together in a one + definition. Specifier can be a symbol, string, character, character range or a special + keyword ".true" or ".false". + + On the very beginning of the script there is a declaration of a root symbol and is in the form: + .syntax <root_symbol>; + The <root_symbol> must be on of the symbols in declaration sequence. The syntax is correct if + the root symbol evaluates to true. A symbol evaluates to true if the definition associated with + the symbol evaluates to true. Definition evaluation depends on the operator used to connect + specifiers in the definition. If ".and" operator is used, definition evaluates to true if and + only if all the specifiers evaluate to true. If ".or" operator is used, definition evalutes to + true if any of the specifiers evaluates to true. If definition contains only one specifier, + it is evaluated as if it was connected with ".true" keyword by ".and" operator. + + If specifier is a ".true" keyword, it always evaluates to true. + + If specifier is a ".false" keyword, it always evaluates to false. Specifier evaluates to false + when it does not evaluate to true. + + Character range specifier is in the form: + '<first_character>' - '<second_character>' + If specifier is a character range, it evaluates to true if character in the stream is greater + or equal to <first_character> and less or equal to <second_character>. In that situation + the stream pointer is advanced to point to next character in the stream. All C-style escape + sequences are supported although trigraph sequences are not. The comparisions are performed + on 8-bit unsigned integers. + + Character specifier is in the form: + '<single_character>' + It evaluates to true if the following character range specifier evaluates to true: + '<single_character>' - '<single_character>' + + String specifier is in the form: + "<string>" + Let N be the number of characters in <string>. Let <string>[i] designate i-th character in + <string>. Then the string specifier evaluates to true if and only if for i in the range [0, N) + the following character specifier evaluates to true: + '<string>[i]' + If <string>[i] is a quotation mark, '<string>[i]' is replaced with '\<string>[i]'. + + Symbol specifier can be optionally preceded by a ".loop" keyword in the form: + .loop <symbol> (1) + where <symbol> is defined as follows: + <symbol> <definition>; (2) + Construction (1) is replaced by the following code: + <symbol$1> + and declaration (2) is replaced by the following: + <symbol$1> <symbol$2> .or .true; + <symbol$2> <symbol> .and <symbol$1>; + <symbol> <definition>; + + Synek supports also a register mechanizm. User can, in its SYN file, declare a number of + registers that can be accessed in the syn body. Each reg has its name and a default value. + The register is one byte wide. The C code can change the default value by calling + grammar_set_reg8() with grammar id, register name and a new value. As we know, each rule is + a sequence of specifiers joined with .and or .or operator. And now each specifier can be + prefixed with a condition expression in a form ".if (<reg_name> <operator> <hex_literal>)" + where <operator> can be == or !=. If the condition evaluates to false, the specifier + evaluates to .false. Otherwise it evalutes to the specifier. + + ESCAPE SEQUENCES + ---------------- + + Synek supports all escape sequences in character specifiers. The mapping table is listed below. + All occurences of the characters in the first column are replaced with the corresponding + character in the second column. + + Escape sequence Represents + ------------------------------------------------------------------------------------------------ + \a Bell (alert) + \b Backspace + \f Formfeed + \n New line + \r Carriage return + \t Horizontal tab + \v Vertical tab + \' Single quotation mark + \" Double quotation mark + \\ Backslash + \? Literal question mark + \ooo ASCII character in octal notation + \xhhh ASCII character in hexadecimal notation + ------------------------------------------------------------------------------------------------ + + RAISING ERRORS + -------------- + + Any specifier can be followed by a special construction that is executed when the specifier + evaluates to false. The construction is in the form: + .error <ERROR_TEXT> + <ERROR_TEXT> is an identifier declared earlier by error text declaration. The declaration is + in the form: + .errtext <ERROR_TEXT> "<error_desc>" + When specifier evaluates to false and this construction is present, parsing is stopped + immediately and <error_desc> is returned as a result of parsing. The error position is also + returned and it is meant as an offset from the beggining of the stream to the character that + was valid so far. Example: + + (**** syntax script ****) + + .syntax program; + .errtext MISSING_SEMICOLON "missing ';'" + program declaration .and .loop space .and ';' .error MISSING_SEMICOLON .and + .loop space .and '\0'; + declaration "declare" .and .loop space .and identifier; + space ' '; + + (**** sample code ****) + + declare foo , + + In the example above checking the sample code will result in error message "missing ';'" and + error position 12. The sample code is not correct. Note the presence of '\0' specifier to + assure that there is no code after semicolon - only spaces. + <error_desc> can optionally contain identifier surrounded by dollar signs $. In such a case, + the identifier and dollar signs are replaced by a string retrieved by invoking symbol with + the identifier name. The starting position is the error position. The lenght of the resulting + string is the position after invoking the symbol. + + PRODUCTION + ---------- + + Synek not only checks the syntax but it can also produce (emit) bytes associated with specifiers + that evaluate to true. That is, every specifier and optional error construction can be followed + by a number of emit constructions that are in the form: + .emit <parameter> + <paramater> can be a HEX number, identifier, a star * or a dollar $. HEX number is preceded by + 0x or 0X. If <parameter> is an identifier, it must be earlier declared by emit code declaration + in the form: + .emtcode <identifier> <hex_number> + + When given specifier evaluates to true, all emits associated with the specifier are output + in order they were declared. A star means that last-read character should be output instead + of constant value. Example: + + (**** syntax script ****) + + .syntax foobar; + .emtcode WORD_FOO 0x01 + .emtcode WORD_BAR 0x02 + foobar FOO .emit WORD_FOO .or BAR .emit WORD_BAR .or .true .emit 0x00; + FOO "foo" .and SPACE; + BAR "bar" .and SPACE; + SPACE ' ' .or '\0'; + + (**** sample text 1 ****) + + foo + + (**** sample text 2 ****) + + foobar + + For both samples the result will be one-element array. For first sample text it will be + value 1, for second - 0. Note that every text will be accepted because of presence of + .true as an alternative. + + Another example: + + (**** syntax script ****) + + .syntax declaration; + .emtcode VARIABLE 0x01 + declaration "declare" .and .loop space .and + identifier .emit VARIABLE .and (1) + .true .emit 0x00 .and (2) + .loop space .and ';'; + space ' ' .or '\t'; + identifier .loop id_char .emit *; (3) + id_char 'a'-'z' .or 'A'-'Z' .or '_'; + + (**** sample code ****) + + declare fubar; + + In specifier (1) symbol <identifier> is followed by .emit VARIABLE. If it evaluates to + true, VARIABLE constant and then production of the symbol is output. Specifier (2) is used + to terminate the string with null to signal when the string ends. Specifier (3) outputs + all characters that make declared identifier. The result of sample code will be the + following array: + { 1, 'f', 'u', 'b', 'a', 'r', 0 } + + If .emit is followed by dollar $, it means that current position should be output. Current + position is a 32-bit unsigned integer distance from the very beginning of the parsed string to + first character consumed by the specifier associated with the .emit instruction. Current + position is stored in the output buffer in Little-Endian convention (the lowest byte comes + first). +*/ + +#include <stdio.h> + +static void mem_free (void **); + +/* + internal error messages +*/ +static const byte *OUT_OF_MEMORY = (byte *) "internal error 1001: out of physical memory"; +static const byte *UNRESOLVED_REFERENCE = (byte *) "internal error 1002: unresolved reference '$'"; +static const byte *INVALID_GRAMMAR_ID = (byte *) "internal error 1003: invalid grammar object"; +static const byte *INVALID_REGISTER_NAME = (byte *) "internal error 1004: invalid register name: '$'"; +/*static const byte *DUPLICATE_IDENTIFIER = (byte *) "internal error 1005: identifier '$' already defined";*/ +static const byte *UNREFERENCED_IDENTIFIER =(byte *) "internal error 1006: unreferenced identifier '$'"; + +static const byte *error_message = NULL; /* points to one of the error messages above */ +static byte *error_param = NULL; /* this is inserted into error_message in place of $ */ +static int error_position = -1; + +static byte *unknown = (byte *) "???"; + +static void clear_last_error (void) +{ + /* reset error message */ + error_message = NULL; + + /* free error parameter - if error_param is a "???" don't free it - it's static */ + if (error_param != unknown) + mem_free ((void **) (void *) &error_param); + else + error_param = NULL; + + /* reset error position */ + error_position = -1; +} + +static void set_last_error (const byte *msg, byte *param, int pos) +{ + /* error message can be set only once */ + if (error_message != NULL) + { + mem_free ((void **) (void *) ¶m); + return; + } + + error_message = msg; + + /* if param is NULL, set error_param to unknown ("???") */ + /* note: do not try to strdup the "???" - it may be that we are here because of */ + /* out of memory error so strdup can fail */ + if (param != NULL) + error_param = param; + else + error_param = unknown; + + error_position = pos; +} + +/* + memory management routines +*/ +static void *mem_alloc (size_t size) +{ + void *ptr = grammar_alloc_malloc (size); + if (ptr == NULL) + set_last_error (OUT_OF_MEMORY, NULL, -1); + return ptr; +} + +static void *mem_copy (void *dst, const void *src, size_t size) +{ + return grammar_memory_copy (dst, src, size); +} + +static void mem_free (void **ptr) +{ + grammar_alloc_free (*ptr); + *ptr = NULL; +} + +static void *mem_realloc (void *ptr, size_t old_size, size_t new_size) +{ + void *ptr2 = grammar_alloc_realloc (ptr, old_size, new_size); + if (ptr2 == NULL) + set_last_error (OUT_OF_MEMORY, NULL, -1); + return ptr2; +} + +static byte *str_copy_n (byte *dst, const byte *src, size_t max_len) +{ + return grammar_string_copy_n (dst, src, max_len); +} + +static byte *str_duplicate (const byte *str) +{ + byte *new_str = grammar_string_duplicate (str); + if (new_str == NULL) + set_last_error (OUT_OF_MEMORY, NULL, -1); + return new_str; +} + +static int str_equal (const byte *str1, const byte *str2) +{ + return grammar_string_compare (str1, str2) == 0; +} + +static int str_equal_n (const byte *str1, const byte *str2, unsigned int n) +{ + return grammar_string_compare_n (str1, str2, n) == 0; +} + +static int +str_length (const byte *str) +{ + return (int) (grammar_string_length (str)); +} + +/* + useful macros +*/ +#define GRAMMAR_IMPLEMENT_LIST_APPEND(_Ty)\ + static void _Ty##_append (_Ty **x, _Ty *nx) {\ + while (*x) x = &(**x).next;\ + *x = nx;\ + } + +/* + string to byte map typedef +*/ +typedef struct map_byte_ +{ + byte *key; + byte data; + struct map_byte_ *next; +} map_byte; + +static void map_byte_create (map_byte **ma) +{ + *ma = (map_byte *) mem_alloc (sizeof (map_byte)); + if (*ma) + { + (**ma).key = NULL; + (**ma).data = '\0'; + (**ma).next = NULL; + } +} + +static void map_byte_destroy (map_byte **ma) +{ + if (*ma) + { + map_byte_destroy (&(**ma).next); + mem_free ((void **) &(**ma).key); + mem_free ((void **) ma); + } +} + +GRAMMAR_IMPLEMENT_LIST_APPEND(map_byte) + +/* + searches the map for the specified key, + returns pointer to the element with the specified key if it exists + returns NULL otherwise +*/ +static map_byte *map_byte_locate (map_byte **ma, const byte *key) +{ + while (*ma) + { + if (str_equal ((**ma).key, key)) + return *ma; + + ma = &(**ma).next; + } + + set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); + return NULL; +} + +/* + searches the map for specified key, + if the key is matched, *data is filled with data associated with the key, + returns 0 if the key is matched, + returns 1 otherwise +*/ +static int map_byte_find (map_byte **ma, const byte *key, byte *data) +{ + map_byte *found = map_byte_locate (ma, key); + if (found != NULL) + { + *data = found->data; + + return 0; + } + + return 1; +} + +/* + regbyte context typedef + + Each regbyte consists of its name and a default value. These are static and created at + grammar script compile-time, for example the following line: + .regbyte vertex_blend 0x00 + adds a new regbyte named "vertex_blend" to the static list and initializes it to 0. + When the script is executed, this regbyte can be accessed by name for read and write. When a + particular regbyte is written, a new regbyte_ctx entry is added to the top of the regbyte_ctx + stack. The new entry contains information abot which regbyte it references and its new value. + When a given regbyte is accessed for read, the stack is searched top-down to find an + entry that references the regbyte. The first matching entry is used to return the current + value it holds. If no entry is found, the default value is returned. +*/ +typedef struct regbyte_ctx_ +{ + map_byte *m_regbyte; + byte m_current_value; + struct regbyte_ctx_ *m_prev; +} regbyte_ctx; + +static void regbyte_ctx_create (regbyte_ctx **re) +{ + *re = (regbyte_ctx *) mem_alloc (sizeof (regbyte_ctx)); + if (*re) + { + (**re).m_regbyte = NULL; + (**re).m_prev = NULL; + } +} + +static void regbyte_ctx_destroy (regbyte_ctx **re) +{ + if (*re) + { + mem_free ((void **) re); + } +} + +static byte regbyte_ctx_extract (regbyte_ctx **re, map_byte *reg) +{ + /* first lookup in the register stack */ + while (*re != NULL) + { + if ((**re).m_regbyte == reg) + return (**re).m_current_value; + + re = &(**re).m_prev; + } + + /* if not found - return the default value */ + return reg->data; +} + +/* + emit type typedef +*/ +typedef enum emit_type_ +{ + et_byte, /* explicit number */ + et_stream, /* eaten character */ + et_position /* current position */ +} emit_type; + +/* + emit destination typedef +*/ +typedef enum emit_dest_ +{ + ed_output, /* write to the output buffer */ + ed_regbyte /* write a particular regbyte */ +} emit_dest; + +/* + emit typedef +*/ +typedef struct emit_ +{ + emit_dest m_emit_dest; + emit_type m_emit_type; /* ed_output */ + byte m_byte; /* et_byte */ + map_byte *m_regbyte; /* ed_regbyte */ + byte *m_regname; /* ed_regbyte - temporary */ + struct emit_ *m_next; +} emit; + +static void emit_create (emit **em) +{ + *em = (emit *) mem_alloc (sizeof (emit)); + if (*em) + { + (**em).m_emit_dest = ed_output; + (**em).m_emit_type = et_byte; + (**em).m_byte = '\0'; + (**em).m_regbyte = NULL; + (**em).m_regname = NULL; + (**em).m_next = NULL; + } +} + +static void emit_destroy (emit **em) +{ + if (*em) + { + emit_destroy (&(**em).m_next); + mem_free ((void **) &(**em).m_regname); + mem_free ((void **) em); + } +} + +static unsigned int emit_size (emit *_E) +{ + unsigned int n = 0; + + while (_E != NULL) + { + if (_E->m_emit_dest == ed_output) + { + if (_E->m_emit_type == et_position) + n += 4; /* position is a 32-bit unsigned integer */ + else + n++; + } + _E = _E->m_next; + } + + return n; +} + +static int emit_push (emit *_E, byte *_P, byte c, unsigned int _Pos, regbyte_ctx **_Ctx) +{ + while (_E != NULL) + { + if (_E->m_emit_dest == ed_output) + { + if (_E->m_emit_type == et_byte) + *_P++ = _E->m_byte; + else if (_E->m_emit_type == et_stream) + *_P++ = c; + else /* _Em->type == et_position */ + { + *_P++ = (byte) (_Pos); + *_P++ = (byte) (_Pos >> 8); + *_P++ = (byte) (_Pos >> 16); + *_P++ = (byte) (_Pos >> 24); + } + } + else + { + regbyte_ctx *new_rbc; + regbyte_ctx_create (&new_rbc); + if (new_rbc == NULL) + return 1; + + new_rbc->m_prev = *_Ctx; + new_rbc->m_regbyte = _E->m_regbyte; + *_Ctx = new_rbc; + + if (_E->m_emit_type == et_byte) + new_rbc->m_current_value = _E->m_byte; + else if (_E->m_emit_type == et_stream) + new_rbc->m_current_value = c; + } + + _E = _E->m_next; + } + + return 0; +} + +/* + error typedef +*/ +typedef struct error_ +{ + byte *m_text; + byte *m_token_name; + struct rule_ *m_token; +} error; + +static void error_create (error **er) +{ + *er = (error *) mem_alloc (sizeof (error)); + if (*er) + { + (**er).m_text = NULL; + (**er).m_token_name = NULL; + (**er).m_token = NULL; + } +} + +static void error_destroy (error **er) +{ + if (*er) + { + mem_free ((void **) &(**er).m_text); + mem_free ((void **) &(**er).m_token_name); + mem_free ((void **) er); + } +} + +struct dict_; + +static byte * +error_get_token (error *, struct dict_ *, const byte *, int); + +/* + condition operand type typedef +*/ +typedef enum cond_oper_type_ +{ + cot_byte, /* constant 8-bit unsigned integer */ + cot_regbyte /* pointer to byte register containing the current value */ +} cond_oper_type; + +/* + condition operand typedef +*/ +typedef struct cond_oper_ +{ + cond_oper_type m_type; + byte m_byte; /* cot_byte */ + map_byte *m_regbyte; /* cot_regbyte */ + byte *m_regname; /* cot_regbyte - temporary */ +} cond_oper; + +/* + condition type typedef +*/ +typedef enum cond_type_ +{ + ct_equal, + ct_not_equal +} cond_type; + +/* + condition typedef +*/ +typedef struct cond_ +{ + cond_type m_type; + cond_oper m_operands[2]; +} cond; + +static void cond_create (cond **co) +{ + *co = (cond *) mem_alloc (sizeof (cond)); + if (*co) + { + (**co).m_operands[0].m_regname = NULL; + (**co).m_operands[1].m_regname = NULL; + } +} + +static void cond_destroy (cond **co) +{ + if (*co) + { + mem_free ((void **) &(**co).m_operands[0].m_regname); + mem_free ((void **) &(**co).m_operands[1].m_regname); + mem_free ((void **) co); + } +} + +/* + specifier type typedef +*/ +typedef enum spec_type_ +{ + st_false, + st_true, + st_byte, + st_byte_range, + st_string, + st_identifier, + st_identifier_loop, + st_debug +} spec_type; + +/* + specifier typedef +*/ +typedef struct spec_ +{ + spec_type m_spec_type; + byte m_byte[2]; /* st_byte, st_byte_range */ + byte *m_string; /* st_string */ + struct rule_ *m_rule; /* st_identifier, st_identifier_loop */ + emit *m_emits; + error *m_errtext; + cond *m_cond; + struct spec_ *next; +} spec; + +static void spec_create (spec **sp) +{ + *sp = (spec *) mem_alloc (sizeof (spec)); + if (*sp) + { + (**sp).m_spec_type = st_false; + (**sp).m_byte[0] = '\0'; + (**sp).m_byte[1] = '\0'; + (**sp).m_string = NULL; + (**sp).m_rule = NULL; + (**sp).m_emits = NULL; + (**sp).m_errtext = NULL; + (**sp).m_cond = NULL; + (**sp).next = NULL; + } +} + +static void spec_destroy (spec **sp) +{ + if (*sp) + { + spec_destroy (&(**sp).next); + emit_destroy (&(**sp).m_emits); + error_destroy (&(**sp).m_errtext); + mem_free ((void **) &(**sp).m_string); + cond_destroy (&(**sp).m_cond); + mem_free ((void **) sp); + } +} + +GRAMMAR_IMPLEMENT_LIST_APPEND(spec) + +/* + operator typedef +*/ +typedef enum oper_ +{ + op_none, + op_and, + op_or +} oper; + +/* + rule typedef +*/ +typedef struct rule_ +{ + oper m_oper; + spec *m_specs; + struct rule_ *next; + int m_referenced; +} rule; + +static void rule_create (rule **ru) +{ + *ru = (rule *) mem_alloc (sizeof (rule)); + if (*ru) + { + (**ru).m_oper = op_none; + (**ru).m_specs = NULL; + (**ru).next = NULL; + (**ru).m_referenced = 0; + } +} + +static void rule_destroy (rule **ru) +{ + if (*ru) + { + rule_destroy (&(**ru).next); + spec_destroy (&(**ru).m_specs); + mem_free ((void **) ru); + } +} + +GRAMMAR_IMPLEMENT_LIST_APPEND(rule) + +/* + returns unique grammar id +*/ +static grammar next_valid_grammar_id (void) +{ + static grammar id = 0; + + return ++id; +} + +/* + dictionary typedef +*/ +typedef struct dict_ +{ + rule *m_rulez; + rule *m_syntax; + rule *m_string; + map_byte *m_regbytes; + grammar m_id; + struct dict_ *next; +} dict; + +static void dict_create (dict **di) +{ + *di = (dict *) mem_alloc (sizeof (dict)); + if (*di) + { + (**di).m_rulez = NULL; + (**di).m_syntax = NULL; + (**di).m_string = NULL; + (**di).m_regbytes = NULL; + (**di).m_id = next_valid_grammar_id (); + (**di).next = NULL; + } +} + +static void dict_destroy (dict **di) +{ + if (*di) + { + rule_destroy (&(**di).m_rulez); + map_byte_destroy (&(**di).m_regbytes); + mem_free ((void **) di); + } +} + +GRAMMAR_IMPLEMENT_LIST_APPEND(dict) + +static void dict_find (dict **di, grammar key, dict **data) +{ + while (*di) + { + if ((**di).m_id == key) + { + *data = *di; + return; + } + + di = &(**di).next; + } + + *data = NULL; +} + +static dict *g_dicts = NULL; + +/* + byte array typedef +*/ +typedef struct barray_ +{ + byte *data; + unsigned int len; +} barray; + +static void barray_create (barray **ba) +{ + *ba = (barray *) mem_alloc (sizeof (barray)); + if (*ba) + { + (**ba).data = NULL; + (**ba).len = 0; + } +} + +static void barray_destroy (barray **ba) +{ + if (*ba) + { + mem_free ((void **) &(**ba).data); + mem_free ((void **) ba); + } +} + +/* + reallocates byte array to requested size, + returns 0 on success, + returns 1 otherwise +*/ +static int barray_resize (barray **ba, unsigned int nlen) +{ + byte *new_pointer; + + if (nlen == 0) + { + mem_free ((void **) &(**ba).data); + (**ba).data = NULL; + (**ba).len = 0; + + return 0; + } + else + { + new_pointer = (byte *) mem_realloc ((**ba).data, (**ba).len * sizeof (byte), + nlen * sizeof (byte)); + if (new_pointer) + { + (**ba).data = new_pointer; + (**ba).len = nlen; + + return 0; + } + } + + return 1; +} + +/* + adds byte array pointed by *nb to the end of array pointed by *ba, + returns 0 on success, + returns 1 otherwise +*/ +static int barray_append (barray **ba, barray **nb) +{ + const unsigned int len = (**ba).len; + + if (barray_resize (ba, (**ba).len + (**nb).len)) + return 1; + + mem_copy ((**ba).data + len, (**nb).data, (**nb).len); + + return 0; +} + +/* + adds emit chain pointed by em to the end of array pointed by *ba, + returns 0 on success, + returns 1 otherwise +*/ +static int barray_push (barray **ba, emit *em, byte c, unsigned int pos, regbyte_ctx **rbc) +{ + unsigned int count = emit_size (em); + + if (barray_resize (ba, (**ba).len + count)) + return 1; + + return emit_push (em, (**ba).data + ((**ba).len - count), c, pos, rbc); +} + +/* + byte pool typedef +*/ +typedef struct bytepool_ +{ + byte *_F; + unsigned int _Siz; +} bytepool; + +static void bytepool_destroy (bytepool **by) +{ + if (*by != NULL) + { + mem_free ((void **) &(**by)._F); + mem_free ((void **) by); + } +} + +static void bytepool_create (bytepool **by, int len) +{ + *by = (bytepool *) (mem_alloc (sizeof (bytepool))); + if (*by != NULL) + { + (**by)._F = (byte *) (mem_alloc (sizeof (byte) * len)); + (**by)._Siz = len; + + if ((**by)._F == NULL) + bytepool_destroy (by); + } +} + +static int bytepool_reserve (bytepool *by, unsigned int n) +{ + byte *_P; + + if (n <= by->_Siz) + return 0; + + /* byte pool can only grow and at least by doubling its size */ + n = n >= by->_Siz * 2 ? n : by->_Siz * 2; + + /* reallocate the memory and adjust pointers to the new memory location */ + _P = (byte *) (mem_realloc (by->_F, sizeof (byte) * by->_Siz, sizeof (byte) * n)); + if (_P != NULL) + { + by->_F = _P; + by->_Siz = n; + return 0; + } + + return 1; +} + +/* + string to string map typedef +*/ +typedef struct map_str_ +{ + byte *key; + byte *data; + struct map_str_ *next; +} map_str; + +static void map_str_create (map_str **ma) +{ + *ma = (map_str *) mem_alloc (sizeof (map_str)); + if (*ma) + { + (**ma).key = NULL; + (**ma).data = NULL; + (**ma).next = NULL; + } +} + +static void map_str_destroy (map_str **ma) +{ + if (*ma) + { + map_str_destroy (&(**ma).next); + mem_free ((void **) &(**ma).key); + mem_free ((void **) &(**ma).data); + mem_free ((void **) ma); + } +} + +GRAMMAR_IMPLEMENT_LIST_APPEND(map_str) + +/* + searches the map for specified key, + if the key is matched, *data is filled with data associated with the key, + returns 0 if the key is matched, + returns 1 otherwise +*/ +static int map_str_find (map_str **ma, const byte *key, byte **data) +{ + while (*ma) + { + if (str_equal ((**ma).key, key)) + { + *data = str_duplicate ((**ma).data); + if (*data == NULL) + return 1; + + return 0; + } + + ma = &(**ma).next; + } + + set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); + return 1; +} + +/* + string to rule map typedef +*/ +typedef struct map_rule_ +{ + byte *key; + rule *data; + struct map_rule_ *next; +} map_rule; + +static void map_rule_create (map_rule **ma) +{ + *ma = (map_rule *) mem_alloc (sizeof (map_rule)); + if (*ma) + { + (**ma).key = NULL; + (**ma).data = NULL; + (**ma).next = NULL; + } +} + +static void map_rule_destroy (map_rule **ma) +{ + if (*ma) + { + map_rule_destroy (&(**ma).next); + mem_free ((void **) &(**ma).key); + mem_free ((void **) ma); + } +} + +GRAMMAR_IMPLEMENT_LIST_APPEND(map_rule) + +/* + searches the map for specified key, + if the key is matched, *data is filled with data associated with the key, + returns 0 if the is matched, + returns 1 otherwise +*/ +static int map_rule_find (map_rule **ma, const byte *key, rule **data) +{ + while (*ma) + { + if (str_equal ((**ma).key, key)) + { + *data = (**ma).data; + + return 0; + } + + ma = &(**ma).next; + } + + set_last_error (UNRESOLVED_REFERENCE, str_duplicate (key), -1); + return 1; +} + +/* + returns 1 if given character is a white space, + returns 0 otherwise +*/ +static int is_space (byte c) +{ + return c == ' ' || c == '\t' || c == '\n' || c == '\r'; +} + +/* + advances text pointer by 1 if character pointed by *text is a space, + returns 1 if a space has been eaten, + returns 0 otherwise +*/ +static int eat_space (const byte **text) +{ + if (is_space (**text)) + { + (*text)++; + + return 1; + } + + return 0; +} + +/* + returns 1 if text points to C-style comment start string, + returns 0 otherwise +*/ +static int is_comment_start (const byte *text) +{ + return text[0] == '/' && text[1] == '*'; +} + +/* + advances text pointer to first character after C-style comment block - if any, + returns 1 if C-style comment block has been encountered and eaten, + returns 0 otherwise +*/ +static int eat_comment (const byte **text) +{ + if (is_comment_start (*text)) + { + /* *text points to comment block - skip two characters to enter comment body */ + *text += 2; + /* skip any character except consecutive '*' and '/' */ + while (!((*text)[0] == '*' && (*text)[1] == '/')) + (*text)++; + /* skip those two terminating characters */ + *text += 2; + + return 1; + } + + return 0; +} + +/* + advances text pointer to first character that is neither space nor C-style comment block +*/ +static void eat_spaces (const byte **text) +{ + while (eat_space (text) || eat_comment (text)) + ; +} + +/* + resizes string pointed by *ptr to successfully add character c to the end of the string, + returns 0 on success, + returns 1 otherwise +*/ +static int string_grow (byte **ptr, unsigned int *len, byte c) +{ + /* reallocate the string in 16-byte increments */ + if ((*len & 0x0F) == 0x0F || *ptr == NULL) + { + byte *tmp = (byte *) mem_realloc (*ptr, ((*len + 1) & ~0x0F) * sizeof (byte), + ((*len + 1 + 0x10) & ~0x0F) * sizeof (byte)); + if (tmp == NULL) + return 1; + + *ptr = tmp; + } + + if (c) + { + /* append given character */ + (*ptr)[*len] = c; + (*len)++; + } + (*ptr)[*len] = '\0'; + + return 0; +} + +/* + returns 1 if given character is a valid identifier character a-z, A-Z, 0-9 or _ + returns 0 otherwise +*/ +static int is_identifier (byte c) +{ + return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9') || c == '_'; +} + +/* + copies characters from *text to *id until non-identifier character is encountered, + assumes that *id points to NULL object - caller is responsible for later freeing the string, + text pointer is advanced to point past the copied identifier, + returns 0 if identifier was successfully copied, + returns 1 otherwise +*/ +static int get_identifier (const byte **text, byte **id) +{ + const byte *t = *text; + byte *p = NULL; + unsigned int len = 0; + + if (string_grow (&p, &len, '\0')) + return 1; + + /* loop while next character in buffer is valid for identifiers */ + while (is_identifier (*t)) + { + if (string_grow (&p, &len, *t++)) + { + mem_free ((void **) (void *) &p); + return 1; + } + } + + *text = t; + *id = p; + + return 0; +} + +/* + converts sequence of DEC digits pointed by *text until non-DEC digit is encountered, + advances text pointer past the converted sequence, + returns the converted value +*/ +static unsigned int dec_convert (const byte **text) +{ + unsigned int value = 0; + + while (**text >= '0' && **text <= '9') + { + value = value * 10 + **text - '0'; + (*text)++; + } + + return value; +} + +/* + returns 1 if given character is HEX digit 0-9, A-F or a-f, + returns 0 otherwise +*/ +static int is_hex (byte c) +{ + return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'F') || (c >= 'a' && c <= 'f'); +} + +/* + returns value of passed character as if it was HEX digit +*/ +static unsigned int hex2dec (byte c) +{ + if (c >= '0' && c <= '9') + return c - '0'; + if (c >= 'A' && c <= 'F') + return c - 'A' + 10; + return c - 'a' + 10; +} + +/* + converts sequence of HEX digits pointed by *text until non-HEX digit is encountered, + advances text pointer past the converted sequence, + returns the converted value +*/ +static unsigned int hex_convert (const byte **text) +{ + unsigned int value = 0; + + while (is_hex (**text)) + { + value = value * 0x10 + hex2dec (**text); + (*text)++; + } + + return value; +} + +/* + returns 1 if given character is OCT digit 0-7, + returns 0 otherwise +*/ +static int is_oct (byte c) +{ + return c >= '0' && c <= '7'; +} + +/* + returns value of passed character as if it was OCT digit +*/ +static int oct2dec (byte c) +{ + return c - '0'; +} + +static byte get_escape_sequence (const byte **text) +{ + int value = 0; + + /* skip '\' character */ + (*text)++; + + switch (*(*text)++) + { + case '\'': + return '\''; + case '"': + return '\"'; + case '?': + return '\?'; + case '\\': + return '\\'; + case 'a': + return '\a'; + case 'b': + return '\b'; + case 'f': + return '\f'; + case 'n': + return '\n'; + case 'r': + return '\r'; + case 't': + return '\t'; + case 'v': + return '\v'; + case 'x': + return (byte) hex_convert (text); + } + + (*text)--; + if (is_oct (**text)) + { + value = oct2dec (*(*text)++); + if (is_oct (**text)) + { + value = value * 010 + oct2dec (*(*text)++); + if (is_oct (**text)) + value = value * 010 + oct2dec (*(*text)++); + } + } + + return (byte) value; +} + +/* + copies characters from *text to *str until " or ' character is encountered, + assumes that *str points to NULL object - caller is responsible for later freeing the string, + assumes that *text points to " or ' character that starts the string, + text pointer is advanced to point past the " or ' character, + returns 0 if string was successfully copied, + returns 1 otherwise +*/ +static int get_string (const byte **text, byte **str) +{ + const byte *t = *text; + byte *p = NULL; + unsigned int len = 0; + byte term_char; + + if (string_grow (&p, &len, '\0')) + return 1; + + /* read " or ' character that starts the string */ + term_char = *t++; + /* while next character is not the terminating character */ + while (*t && *t != term_char) + { + byte c; + + if (*t == '\\') + c = get_escape_sequence (&t); + else + c = *t++; + + if (string_grow (&p, &len, c)) + { + mem_free ((void **) (void *) &p); + return 1; + } + } + /* skip " or ' character that ends the string */ + t++; + + *text = t; + *str = p; + return 0; +} + +/* + gets emit code, the syntax is: + ".emtcode" " " <symbol> " " (("0x" | "0X") <hex_value>) | <dec_value> | <character> + assumes that *text already points to <symbol>, + returns 0 if emit code is successfully read, + returns 1 otherwise +*/ +static int get_emtcode (const byte **text, map_byte **ma) +{ + const byte *t = *text; + map_byte *m = NULL; + + map_byte_create (&m); + if (m == NULL) + return 1; + + if (get_identifier (&t, &m->key)) + { + map_byte_destroy (&m); + return 1; + } + eat_spaces (&t); + + if (*t == '\'') + { + byte *c; + + if (get_string (&t, &c)) + { + map_byte_destroy (&m); + return 1; + } + + m->data = (byte) c[0]; + mem_free ((void **) (void *) &c); + } + else if (t[0] == '0' && (t[1] == 'x' || t[1] == 'X')) + { + /* skip HEX "0x" or "0X" prefix */ + t += 2; + m->data = (byte) hex_convert (&t); + } + else + { + m->data = (byte) dec_convert (&t); + } + + eat_spaces (&t); + + *text = t; + *ma = m; + return 0; +} + +/* + gets regbyte declaration, the syntax is: + ".regbyte" " " <symbol> " " (("0x" | "0X") <hex_value>) | <dec_value> | <character> + assumes that *text already points to <symbol>, + returns 0 if regbyte is successfully read, + returns 1 otherwise +*/ +static int get_regbyte (const byte **text, map_byte **ma) +{ + /* pass it to the emtcode parser as it has the same syntax starting at <symbol> */ + return get_emtcode (text, ma); +} + +/* + returns 0 on success, + returns 1 otherwise +*/ +static int get_errtext (const byte **text, map_str **ma) +{ + const byte *t = *text; + map_str *m = NULL; + + map_str_create (&m); + if (m == NULL) + return 1; + + if (get_identifier (&t, &m->key)) + { + map_str_destroy (&m); + return 1; + } + eat_spaces (&t); + + if (get_string (&t, &m->data)) + { + map_str_destroy (&m); + return 1; + } + eat_spaces (&t); + + *text = t; + *ma = m; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int get_error (const byte **text, error **er, map_str *maps) +{ + const byte *t = *text; + byte *temp = NULL; + + if (*t != '.') + return 0; + + t++; + if (get_identifier (&t, &temp)) + return 1; + eat_spaces (&t); + + if (!str_equal ((byte *) "error", temp)) + { + mem_free ((void **) (void *) &temp); + return 0; + } + + mem_free ((void **) (void *) &temp); + + error_create (er); + if (*er == NULL) + return 1; + + if (*t == '\"') + { + if (get_string (&t, &(**er).m_text)) + { + error_destroy (er); + return 1; + } + eat_spaces (&t); + } + else + { + if (get_identifier (&t, &temp)) + { + error_destroy (er); + return 1; + } + eat_spaces (&t); + + if (map_str_find (&maps, temp, &(**er).m_text)) + { + mem_free ((void **) (void *) &temp); + error_destroy (er); + return 1; + } + + mem_free ((void **) (void *) &temp); + } + + /* try to extract "token" from "...$token$..." */ + { + byte *processed = NULL; + unsigned int len = 0; + int i = 0; + + if (string_grow (&processed, &len, '\0')) + { + error_destroy (er); + return 1; + } + + while (i < str_length ((**er).m_text)) + { + /* check if the dollar sign is repeated - if so skip it */ + if ((**er).m_text[i] == '$' && (**er).m_text[i + 1] == '$') + { + if (string_grow (&processed, &len, '$')) + { + mem_free ((void **) (void *) &processed); + error_destroy (er); + return 1; + } + + i += 2; + } + else if ((**er).m_text[i] != '$') + { + if (string_grow (&processed, &len, (**er).m_text[i])) + { + mem_free ((void **) (void *) &processed); + error_destroy (er); + return 1; + } + + i++; + } + else + { + if (string_grow (&processed, &len, '$')) + { + mem_free ((void **) (void *) &processed); + error_destroy (er); + return 1; + } + + { + /* length of token being extracted */ + unsigned int tlen = 0; + + if (string_grow (&(**er).m_token_name, &tlen, '\0')) + { + mem_free ((void **) (void *) &processed); + error_destroy (er); + return 1; + } + + /* skip the dollar sign */ + i++; + + while ((**er).m_text[i] != '$') + { + if (string_grow (&(**er).m_token_name, &tlen, (**er).m_text[i])) + { + mem_free ((void **) (void *) &processed); + error_destroy (er); + return 1; + } + + i++; + } + + /* skip the dollar sign */ + i++; + } + } + } + + mem_free ((void **) &(**er).m_text); + (**er).m_text = processed; + } + + *text = t; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int get_emits (const byte **text, emit **em, map_byte *mapb) +{ + const byte *t = *text; + byte *temp = NULL; + emit *e = NULL; + emit_dest dest; + + if (*t != '.') + return 0; + + t++; + if (get_identifier (&t, &temp)) + return 1; + eat_spaces (&t); + + /* .emit */ + if (str_equal ((byte *) "emit", temp)) + dest = ed_output; + /* .load */ + else if (str_equal ((byte *) "load", temp)) + dest = ed_regbyte; + else + { + mem_free ((void **) (void *) &temp); + return 0; + } + + mem_free ((void **) (void *) &temp); + + emit_create (&e); + if (e == NULL) + return 1; + + e->m_emit_dest = dest; + + if (dest == ed_regbyte) + { + if (get_identifier (&t, &e->m_regname)) + { + emit_destroy (&e); + return 1; + } + eat_spaces (&t); + } + + /* 0xNN */ + if (*t == '0' && (t[1] == 'x' || t[1] == 'X')) + { + t += 2; + e->m_byte = (byte) hex_convert (&t); + + e->m_emit_type = et_byte; + } + /* NNN */ + else if (*t >= '0' && *t <= '9') + { + e->m_byte = (byte) dec_convert (&t); + + e->m_emit_type = et_byte; + } + /* * */ + else if (*t == '*') + { + t++; + + e->m_emit_type = et_stream; + } + /* $ */ + else if (*t == '$') + { + t++; + + e->m_emit_type = et_position; + } + /* 'c' */ + else if (*t == '\'') + { + if (get_string (&t, &temp)) + { + emit_destroy (&e); + return 1; + } + e->m_byte = (byte) temp[0]; + + mem_free ((void **) (void *) &temp); + + e->m_emit_type = et_byte; + } + else + { + if (get_identifier (&t, &temp)) + { + emit_destroy (&e); + return 1; + } + + if (map_byte_find (&mapb, temp, &e->m_byte)) + { + mem_free ((void **) (void *) &temp); + emit_destroy (&e); + return 1; + } + + mem_free ((void **) (void *) &temp); + + e->m_emit_type = et_byte; + } + + eat_spaces (&t); + + if (get_emits (&t, &e->m_next, mapb)) + { + emit_destroy (&e); + return 1; + } + + *text = t; + *em = e; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int get_spec (const byte **text, spec **sp, map_str *maps, map_byte *mapb) +{ + const byte *t = *text; + spec *s = NULL; + + spec_create (&s); + if (s == NULL) + return 1; + + /* first - read optional .if statement */ + if (*t == '.') + { + const byte *u = t; + byte *keyword = NULL; + + /* skip the dot */ + u++; + + if (get_identifier (&u, &keyword)) + { + spec_destroy (&s); + return 1; + } + + /* .if */ + if (str_equal ((byte *) "if", keyword)) + { + cond_create (&s->m_cond); + if (s->m_cond == NULL) + { + spec_destroy (&s); + return 1; + } + + /* skip the left paren */ + eat_spaces (&u); + u++; + + /* get the left operand */ + eat_spaces (&u); + if (get_identifier (&u, &s->m_cond->m_operands[0].m_regname)) + { + spec_destroy (&s); + return 1; + } + s->m_cond->m_operands[0].m_type = cot_regbyte; + + /* get the operator (!= or ==) */ + eat_spaces (&u); + if (*u == '!') + s->m_cond->m_type = ct_not_equal; + else + s->m_cond->m_type = ct_equal; + u += 2; + eat_spaces (&u); + + if (u[0] == '0' && (u[1] == 'x' || u[1] == 'X')) + { + /* skip the 0x prefix */ + u += 2; + + /* get the right operand */ + s->m_cond->m_operands[1].m_byte = hex_convert (&u); + s->m_cond->m_operands[1].m_type = cot_byte; + } + else /*if (*u >= '0' && *u <= '9')*/ + { + /* get the right operand */ + s->m_cond->m_operands[1].m_byte = dec_convert (&u); + s->m_cond->m_operands[1].m_type = cot_byte; + } + + /* skip the right paren */ + eat_spaces (&u); + u++; + + eat_spaces (&u); + + t = u; + } + + mem_free ((void **) (void *) &keyword); + } + + if (*t == '\'') + { + byte *temp = NULL; + + if (get_string (&t, &temp)) + { + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + if (*t == '-') + { + byte *temp2 = NULL; + + /* skip the '-' character */ + t++; + eat_spaces (&t); + + if (get_string (&t, &temp2)) + { + mem_free ((void **) (void *) &temp); + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + s->m_spec_type = st_byte_range; + s->m_byte[0] = *temp; + s->m_byte[1] = *temp2; + + mem_free ((void **) (void *) &temp2); + } + else + { + s->m_spec_type = st_byte; + *s->m_byte = *temp; + } + + mem_free ((void **) (void *) &temp); + } + else if (*t == '"') + { + if (get_string (&t, &s->m_string)) + { + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + s->m_spec_type = st_string; + } + else if (*t == '.') + { + byte *keyword = NULL; + + /* skip the dot */ + t++; + + if (get_identifier (&t, &keyword)) + { + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + /* .true */ + if (str_equal ((byte *) "true", keyword)) + { + s->m_spec_type = st_true; + } + /* .false */ + else if (str_equal ((byte *) "false", keyword)) + { + s->m_spec_type = st_false; + } + /* .debug */ + else if (str_equal ((byte *) "debug", keyword)) + { + s->m_spec_type = st_debug; + } + /* .loop */ + else if (str_equal ((byte *) "loop", keyword)) + { + if (get_identifier (&t, &s->m_string)) + { + mem_free ((void **) (void *) &keyword); + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + s->m_spec_type = st_identifier_loop; + } + mem_free ((void **) (void *) &keyword); + } + else + { + if (get_identifier (&t, &s->m_string)) + { + spec_destroy (&s); + return 1; + } + eat_spaces (&t); + + s->m_spec_type = st_identifier; + } + + if (get_error (&t, &s->m_errtext, maps)) + { + spec_destroy (&s); + return 1; + } + + if (get_emits (&t, &s->m_emits, mapb)) + { + spec_destroy (&s); + return 1; + } + + *text = t; + *sp = s; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int get_rule (const byte **text, rule **ru, map_str *maps, map_byte *mapb) +{ + const byte *t = *text; + rule *r = NULL; + + rule_create (&r); + if (r == NULL) + return 1; + + if (get_spec (&t, &r->m_specs, maps, mapb)) + { + rule_destroy (&r); + return 1; + } + + while (*t != ';') + { + byte *op = NULL; + spec *sp = NULL; + + /* skip the dot that precedes "and" or "or" */ + t++; + + /* read "and" or "or" keyword */ + if (get_identifier (&t, &op)) + { + rule_destroy (&r); + return 1; + } + eat_spaces (&t); + + if (r->m_oper == op_none) + { + /* .and */ + if (str_equal ((byte *) "and", op)) + r->m_oper = op_and; + /* .or */ + else + r->m_oper = op_or; + } + + mem_free ((void **) (void *) &op); + + if (get_spec (&t, &sp, maps, mapb)) + { + rule_destroy (&r); + return 1; + } + + spec_append (&r->m_specs, sp); + } + + /* skip the semicolon */ + t++; + eat_spaces (&t); + + *text = t; + *ru = r; + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int update_dependency (map_rule *mapr, byte *symbol, rule **ru) +{ + if (map_rule_find (&mapr, symbol, ru)) + return 1; + + (**ru).m_referenced = 1; + + return 0; +} + +/* + returns 0 on success, + returns 1 otherwise, +*/ +static int update_dependencies (dict *di, map_rule *mapr, byte **syntax_symbol, + byte **string_symbol, map_byte *regbytes) +{ + rule *rulez = di->m_rulez; + + /* update dependecies for the root and lexer symbols */ + if (update_dependency (mapr, *syntax_symbol, &di->m_syntax) || + (*string_symbol != NULL && update_dependency (mapr, *string_symbol, &di->m_string))) + return 1; + + mem_free ((void **) syntax_symbol); + mem_free ((void **) string_symbol); + + /* update dependecies for the rest of the rules */ + while (rulez) + { + spec *sp = rulez->m_specs; + + /* iterate through all the specifiers */ + while (sp) + { + /* update dependency for identifier */ + if (sp->m_spec_type == st_identifier || sp->m_spec_type == st_identifier_loop) + { + if (update_dependency (mapr, sp->m_string, &sp->m_rule)) + return 1; + + mem_free ((void **) &sp->m_string); + } + + /* some errtexts reference to a rule */ + if (sp->m_errtext && sp->m_errtext->m_token_name) + { + if (update_dependency (mapr, sp->m_errtext->m_token_name, &sp->m_errtext->m_token)) + return 1; + + mem_free ((void **) &sp->m_errtext->m_token_name); + } + + /* update dependency for condition */ + if (sp->m_cond) + { + int i; + for (i = 0; i < 2; i++) + if (sp->m_cond->m_operands[i].m_type == cot_regbyte) + { + sp->m_cond->m_operands[i].m_regbyte = map_byte_locate (®bytes, + sp->m_cond->m_operands[i].m_regname); + + if (sp->m_cond->m_operands[i].m_regbyte == NULL) + return 1; + + mem_free ((void **) &sp->m_cond->m_operands[i].m_regname); + } + } + + /* update dependency for all .load instructions */ + if (sp->m_emits) + { + emit *em = sp->m_emits; + while (em != NULL) + { + if (em->m_emit_dest == ed_regbyte) + { + em->m_regbyte = map_byte_locate (®bytes, em->m_regname); + + if (em->m_regbyte == NULL) + return 1; + + mem_free ((void **) &em->m_regname); + } + + em = em->m_next; + } + } + + sp = sp->next; + } + + rulez = rulez->next; + } + + /* check for unreferenced symbols */ + rulez = di->m_rulez; + while (rulez != NULL) + { + if (!rulez->m_referenced) + { + map_rule *ma = mapr; + while (ma) + { + if (ma->data == rulez) + { + set_last_error (UNREFERENCED_IDENTIFIER, str_duplicate (ma->key), -1); + return 1; + } + ma = ma->next; + } + } + rulez = rulez->next; + } + + return 0; +} + +static int satisfies_condition (cond *co, regbyte_ctx *ctx) +{ + byte values[2]; + int i; + + if (co == NULL) + return 1; + + for (i = 0; i < 2; i++) + switch (co->m_operands[i].m_type) + { + case cot_byte: + values[i] = co->m_operands[i].m_byte; + break; + case cot_regbyte: + values[i] = regbyte_ctx_extract (&ctx, co->m_operands[i].m_regbyte); + break; + } + + switch (co->m_type) + { + case ct_equal: + return values[0] == values[1]; + case ct_not_equal: + return values[0] != values[1]; + } + + return 0; +} + +static void free_regbyte_ctx_stack (regbyte_ctx *top, regbyte_ctx *limit) +{ + while (top != limit) + { + regbyte_ctx *rbc = top->m_prev; + regbyte_ctx_destroy (&top); + top = rbc; + } +} + +typedef enum match_result_ +{ + mr_not_matched, /* the examined string does not match */ + mr_matched, /* the examined string matches */ + mr_error_raised, /* mr_not_matched + error has been raised */ + mr_dont_emit, /* used by identifier loops only */ + mr_internal_error /* an internal error has occured such as out of memory */ +} match_result; + +/* + * This function does the main job. It parses the text and generates output data. + */ +static match_result +match (dict *di, const byte *text, int *index, rule *ru, barray **ba, int filtering_string, + regbyte_ctx **rbc) +{ + int ind = *index; + match_result status = mr_not_matched; + spec *sp = ru->m_specs; + regbyte_ctx *ctx = *rbc; + + /* for every specifier in the rule */ + while (sp) + { + int i, len, save_ind = ind; + barray *array = NULL; + + if (satisfies_condition (sp->m_cond, ctx)) + { + switch (sp->m_spec_type) + { + case st_identifier: + barray_create (&array); + if (array == NULL) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + status = match (di, text, &ind, sp->m_rule, &array, filtering_string, &ctx); + + if (status == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + break; + case st_string: + len = str_length (sp->m_string); + + /* prefilter the stream */ + if (!filtering_string && di->m_string) + { + barray *ba; + int filter_index = 0; + match_result result; + regbyte_ctx *null_ctx = NULL; + + barray_create (&ba); + if (ba == NULL) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + result = match (di, text + ind, &filter_index, di->m_string, &ba, 1, &null_ctx); + + if (result == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&ba); + return mr_internal_error; + } + + if (result != mr_matched) + { + barray_destroy (&ba); + status = mr_not_matched; + break; + } + + barray_destroy (&ba); + + if (filter_index != len || !str_equal_n (sp->m_string, text + ind, len)) + { + status = mr_not_matched; + break; + } + + status = mr_matched; + ind += len; + } + else + { + status = mr_matched; + for (i = 0; status == mr_matched && i < len; i++) + if (text[ind + i] != sp->m_string[i]) + status = mr_not_matched; + + if (status == mr_matched) + ind += len; + } + break; + case st_byte: + status = text[ind] == *sp->m_byte ? mr_matched : mr_not_matched; + if (status == mr_matched) + ind++; + break; + case st_byte_range: + status = (text[ind] >= sp->m_byte[0] && text[ind] <= sp->m_byte[1]) ? + mr_matched : mr_not_matched; + if (status == mr_matched) + ind++; + break; + case st_true: + status = mr_matched; + break; + case st_false: + status = mr_not_matched; + break; + case st_debug: + status = ru->m_oper == op_and ? mr_matched : mr_not_matched; + break; + case st_identifier_loop: + barray_create (&array); + if (array == NULL) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + status = mr_dont_emit; + for (;;) + { + match_result result; + + save_ind = ind; + result = match (di, text, &ind, sp->m_rule, &array, filtering_string, &ctx); + + if (result == mr_error_raised) + { + status = result; + break; + } + else if (result == mr_matched) + { + if (barray_push (ba, sp->m_emits, text[ind - 1], save_ind, &ctx) || + barray_append (ba, &array)) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + barray_destroy (&array); + barray_create (&array); + if (array == NULL) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + } + else if (result == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + else + break; + } + break; + } + } + else + { + status = mr_not_matched; + } + + if (status == mr_error_raised) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + + return mr_error_raised; + } + + if (ru->m_oper == op_and && status != mr_matched && status != mr_dont_emit) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + + if (sp->m_errtext) + { + set_last_error (sp->m_errtext->m_text, error_get_token (sp->m_errtext, di, text, + ind), ind); + + return mr_error_raised; + } + + return mr_not_matched; + } + + if (status == mr_matched) + { + if (sp->m_emits) + if (barray_push (ba, sp->m_emits, text[ind - 1], save_ind, &ctx)) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + + if (array) + if (barray_append (ba, &array)) + { + free_regbyte_ctx_stack (ctx, *rbc); + barray_destroy (&array); + return mr_internal_error; + } + } + + barray_destroy (&array); + + /* if the rule operator is a logical or, we pick up the first matching specifier */ + if (ru->m_oper == op_or && (status == mr_matched || status == mr_dont_emit)) + { + *index = ind; + *rbc = ctx; + return mr_matched; + } + + sp = sp->next; + } + + /* everything went fine - all specifiers match up */ + if (ru->m_oper == op_and && (status == mr_matched || status == mr_dont_emit)) + { + *index = ind; + *rbc = ctx; + return mr_matched; + } + + free_regbyte_ctx_stack (ctx, *rbc); + return mr_not_matched; +} + +static match_result +fast_match (dict *di, const byte *text, int *index, rule *ru, int *_PP, bytepool *_BP, + int filtering_string, regbyte_ctx **rbc) +{ + int ind = *index; + int _P = filtering_string ? 0 : *_PP; + int _P2; + match_result status = mr_not_matched; + spec *sp = ru->m_specs; + regbyte_ctx *ctx = *rbc; + + /* for every specifier in the rule */ + while (sp) + { + int i, len, save_ind = ind; + + _P2 = _P + (sp->m_emits ? emit_size (sp->m_emits) : 0); + if (bytepool_reserve (_BP, _P2)) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + if (satisfies_condition (sp->m_cond, ctx)) + { + switch (sp->m_spec_type) + { + case st_identifier: + status = fast_match (di, text, &ind, sp->m_rule, &_P2, _BP, filtering_string, &ctx); + + if (status == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + break; + case st_string: + len = str_length (sp->m_string); + + /* prefilter the stream */ + if (!filtering_string && di->m_string) + { + int filter_index = 0; + match_result result; + regbyte_ctx *null_ctx = NULL; + + result = fast_match (di, text + ind, &filter_index, di->m_string, NULL, _BP, 1, &null_ctx); + + if (result == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + if (result != mr_matched) + { + status = mr_not_matched; + break; + } + + if (filter_index != len || !str_equal_n (sp->m_string, text + ind, len)) + { + status = mr_not_matched; + break; + } + + status = mr_matched; + ind += len; + } + else + { + status = mr_matched; + for (i = 0; status == mr_matched && i < len; i++) + if (text[ind + i] != sp->m_string[i]) + status = mr_not_matched; + + if (status == mr_matched) + ind += len; + } + break; + case st_byte: + status = text[ind] == *sp->m_byte ? mr_matched : mr_not_matched; + if (status == mr_matched) + ind++; + break; + case st_byte_range: + status = (text[ind] >= sp->m_byte[0] && text[ind] <= sp->m_byte[1]) ? + mr_matched : mr_not_matched; + if (status == mr_matched) + ind++; + break; + case st_true: + status = mr_matched; + break; + case st_false: + status = mr_not_matched; + break; + case st_debug: + status = ru->m_oper == op_and ? mr_matched : mr_not_matched; + break; + case st_identifier_loop: + status = mr_dont_emit; + for (;;) + { + match_result result; + + save_ind = ind; + result = fast_match (di, text, &ind, sp->m_rule, &_P2, _BP, filtering_string, &ctx); + + if (result == mr_error_raised) + { + status = result; + break; + } + else if (result == mr_matched) + { + if (!filtering_string) + { + if (sp->m_emits != NULL) + { + if (emit_push (sp->m_emits, _BP->_F + _P, text[ind - 1], save_ind, &ctx)) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + } + + _P = _P2; + _P2 += sp->m_emits ? emit_size (sp->m_emits) : 0; + if (bytepool_reserve (_BP, _P2)) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + } + } + else if (result == mr_internal_error) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + else + break; + } + break; + } + } + else + { + status = mr_not_matched; + } + + if (status == mr_error_raised) + { + free_regbyte_ctx_stack (ctx, *rbc); + + return mr_error_raised; + } + + if (ru->m_oper == op_and && status != mr_matched && status != mr_dont_emit) + { + free_regbyte_ctx_stack (ctx, *rbc); + + if (sp->m_errtext) + { + set_last_error (sp->m_errtext->m_text, error_get_token (sp->m_errtext, di, text, + ind), ind); + + return mr_error_raised; + } + + return mr_not_matched; + } + + if (status == mr_matched) + { + if (sp->m_emits != NULL) { + const byte ch = (ind <= 0) ? 0 : text[ind - 1]; + if (emit_push (sp->m_emits, _BP->_F + _P, ch, save_ind, &ctx)) + { + free_regbyte_ctx_stack (ctx, *rbc); + return mr_internal_error; + } + + } + _P = _P2; + } + + /* if the rule operator is a logical or, we pick up the first matching specifier */ + if (ru->m_oper == op_or && (status == mr_matched || status == mr_dont_emit)) + { + *index = ind; + *rbc = ctx; + if (!filtering_string) + *_PP = _P; + return mr_matched; + } + + sp = sp->next; + } + + /* everything went fine - all specifiers match up */ + if (ru->m_oper == op_and && (status == mr_matched || status == mr_dont_emit)) + { + *index = ind; + *rbc = ctx; + if (!filtering_string) + *_PP = _P; + return mr_matched; + } + + free_regbyte_ctx_stack (ctx, *rbc); + return mr_not_matched; +} + +static byte * +error_get_token (error *er, dict *di, const byte *text, int ind) +{ + byte *str = NULL; + + if (er->m_token) + { + barray *ba; + int filter_index = 0; + regbyte_ctx *ctx = NULL; + + barray_create (&ba); + if (ba != NULL) + { + if (match (di, text + ind, &filter_index, er->m_token, &ba, 0, &ctx) == mr_matched && + filter_index) + { + str = (byte *) mem_alloc (filter_index + 1); + if (str != NULL) + { + str_copy_n (str, text + ind, filter_index); + str[filter_index] = '\0'; + } + } + barray_destroy (&ba); + } + } + + return str; +} + +typedef struct grammar_load_state_ +{ + dict *di; + byte *syntax_symbol; + byte *string_symbol; + map_str *maps; + map_byte *mapb; + map_rule *mapr; +} grammar_load_state; + +static void grammar_load_state_create (grammar_load_state **gr) +{ + *gr = (grammar_load_state *) mem_alloc (sizeof (grammar_load_state)); + if (*gr) + { + (**gr).di = NULL; + (**gr).syntax_symbol = NULL; + (**gr).string_symbol = NULL; + (**gr).maps = NULL; + (**gr).mapb = NULL; + (**gr).mapr = NULL; + } +} + +static void grammar_load_state_destroy (grammar_load_state **gr) +{ + if (*gr) + { + dict_destroy (&(**gr).di); + mem_free ((void **) &(**gr).syntax_symbol); + mem_free ((void **) &(**gr).string_symbol); + map_str_destroy (&(**gr).maps); + map_byte_destroy (&(**gr).mapb); + map_rule_destroy (&(**gr).mapr); + mem_free ((void **) gr); + } +} + + +static void error_msg(int line, const char *msg) +{ + fprintf(stderr, "Error in grammar_load_from_text() at line %d: %s\n", line, msg); +} + + +/* + the API +*/ +grammar grammar_load_from_text (const byte *text) +{ + grammar_load_state *g = NULL; + grammar id = 0; + + clear_last_error (); + + grammar_load_state_create (&g); + if (g == NULL) { + error_msg(__LINE__, ""); + return 0; + } + + dict_create (&g->di); + if (g->di == NULL) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + + eat_spaces (&text); + + /* skip ".syntax" keyword */ + text += 7; + eat_spaces (&text); + + /* retrieve root symbol */ + if (get_identifier (&text, &g->syntax_symbol)) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + eat_spaces (&text); + + /* skip semicolon */ + text++; + eat_spaces (&text); + + while (*text) + { + byte *symbol = NULL; + int is_dot = *text == '.'; + + if (is_dot) + text++; + + if (get_identifier (&text, &symbol)) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + eat_spaces (&text); + + /* .emtcode */ + if (is_dot && str_equal (symbol, (byte *) "emtcode")) + { + map_byte *ma = NULL; + + mem_free ((void **) (void *) &symbol); + + if (get_emtcode (&text, &ma)) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + + map_byte_append (&g->mapb, ma); + } + /* .regbyte */ + else if (is_dot && str_equal (symbol, (byte *) "regbyte")) + { + map_byte *ma = NULL; + + mem_free ((void **) (void *) &symbol); + + if (get_regbyte (&text, &ma)) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + + map_byte_append (&g->di->m_regbytes, ma); + } + /* .errtext */ + else if (is_dot && str_equal (symbol, (byte *) "errtext")) + { + map_str *ma = NULL; + + mem_free ((void **) (void *) &symbol); + + if (get_errtext (&text, &ma)) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + + map_str_append (&g->maps, ma); + } + /* .string */ + else if (is_dot && str_equal (symbol, (byte *) "string")) + { + mem_free ((void **) (void *) &symbol); + + if (g->di->m_string != NULL) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + + if (get_identifier (&text, &g->string_symbol)) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + + /* skip semicolon */ + eat_spaces (&text); + text++; + eat_spaces (&text); + } + else + { + rule *ru = NULL; + map_rule *ma = NULL; + + if (get_rule (&text, &ru, g->maps, g->mapb)) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + + rule_append (&g->di->m_rulez, ru); + + /* if a rule consist of only one specifier, give it an ".and" operator */ + if (ru->m_oper == op_none) + ru->m_oper = op_and; + + map_rule_create (&ma); + if (ma == NULL) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, ""); + return 0; + } + + ma->key = symbol; + ma->data = ru; + map_rule_append (&g->mapr, ma); + } + } + + if (update_dependencies (g->di, g->mapr, &g->syntax_symbol, &g->string_symbol, + g->di->m_regbytes)) + { + grammar_load_state_destroy (&g); + error_msg(__LINE__, "update_dependencies() failed"); + return 0; + } + + dict_append (&g_dicts, g->di); + id = g->di->m_id; + g->di = NULL; + + grammar_load_state_destroy (&g); + + return id; +} + +int grammar_set_reg8 (grammar id, const byte *name, byte value) +{ + dict *di = NULL; + map_byte *reg = NULL; + + clear_last_error (); + + dict_find (&g_dicts, id, &di); + if (di == NULL) + { + set_last_error (INVALID_GRAMMAR_ID, NULL, -1); + return 0; + } + + reg = map_byte_locate (&di->m_regbytes, name); + if (reg == NULL) + { + set_last_error (INVALID_REGISTER_NAME, str_duplicate (name), -1); + return 0; + } + + reg->data = value; + return 1; +} + +/* + internal checking function used by both grammar_check and grammar_fast_check functions +*/ +static int _grammar_check (grammar id, const byte *text, byte **prod, unsigned int *size, + unsigned int estimate_prod_size, int use_fast_path) +{ + dict *di = NULL; + int index = 0; + + clear_last_error (); + + dict_find (&g_dicts, id, &di); + if (di == NULL) + { + set_last_error (INVALID_GRAMMAR_ID, NULL, -1); + return 0; + } + + *prod = NULL; + *size = 0; + + if (use_fast_path) + { + regbyte_ctx *rbc = NULL; + bytepool *bp = NULL; + int _P = 0; + + bytepool_create (&bp, estimate_prod_size); + if (bp == NULL) + return 0; + + if (fast_match (di, text, &index, di->m_syntax, &_P, bp, 0, &rbc) != mr_matched) + { + bytepool_destroy (&bp); + free_regbyte_ctx_stack (rbc, NULL); + return 0; + } + + free_regbyte_ctx_stack (rbc, NULL); + + *prod = bp->_F; + *size = _P; + bp->_F = NULL; + bytepool_destroy (&bp); + } + else + { + regbyte_ctx *rbc = NULL; + barray *ba = NULL; + + barray_create (&ba); + if (ba == NULL) + return 0; + + if (match (di, text, &index, di->m_syntax, &ba, 0, &rbc) != mr_matched) + { + barray_destroy (&ba); + free_regbyte_ctx_stack (rbc, NULL); + return 0; + } + + free_regbyte_ctx_stack (rbc, NULL); + + *prod = (byte *) mem_alloc (ba->len * sizeof (byte)); + if (*prod == NULL) + { + barray_destroy (&ba); + return 0; + } + + mem_copy (*prod, ba->data, ba->len * sizeof (byte)); + *size = ba->len; + barray_destroy (&ba); + } + + return 1; +} + +int grammar_check (grammar id, const byte *text, byte **prod, unsigned int *size) +{ + return _grammar_check (id, text, prod, size, 0, 0); +} + +int grammar_fast_check (grammar id, const byte *text, byte **prod, unsigned int *size, + unsigned int estimate_prod_size) +{ + return _grammar_check (id, text, prod, size, estimate_prod_size, 1); +} + +int grammar_destroy (grammar id) +{ + dict **di = &g_dicts; + + clear_last_error (); + + while (*di != NULL) + { + if ((**di).m_id == id) + { + dict *tmp = *di; + *di = (**di).next; + dict_destroy (&tmp); + return 1; + } + + di = &(**di).next; + } + + set_last_error (INVALID_GRAMMAR_ID, NULL, -1); + return 0; +} + +static void append_character (const char x, byte *text, int *dots_made, int *len, int size) +{ + if (*dots_made == 0) + { + if (*len < size - 1) + { + text[(*len)++] = x; + text[*len] = '\0'; + } + else + { + int i; + for (i = 0; i < 3; i++) + if (--(*len) >= 0) + text[*len] = '.'; + *dots_made = 1; + } + } +} + +void grammar_get_last_error (byte *text, unsigned int size, int *pos) +{ + int len = 0, dots_made = 0; + const byte *p = error_message; + + *text = '\0'; + + if (p) + { + while (*p) + { + if (*p == '$') + { + const byte *r = error_param; + + while (*r) + { + append_character (*r++, text, &dots_made, &len, (int) size); + } + + p++; + } + else + { + append_character (*p++, text, &dots_made, &len, size); + } + } + } + + *pos = error_position; +} diff --git a/mesalib/src/mesa/shader/grammar/grammar.h b/mesalib/src/mesa/shader/grammar/grammar.h new file mode 100644 index 000000000..591e38aef --- /dev/null +++ b/mesalib/src/mesa/shader/grammar/grammar.h @@ -0,0 +1,103 @@ +/* + * Mesa 3-D graphics library + * Version: 6.2 + * + * Copyright (C) 1999-2004 Brian Paul All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN + * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef GRAMMAR_H +#define GRAMMAR_H + + +#ifndef GRAMMAR_PORT_INCLUDE +#error Do not include this file directly, include your grammar_XXX.h instead +#endif + + +#ifdef __cplusplus +extern "C" { +#endif + +void grammar_alloc_free (void *); +void *grammar_alloc_malloc (size_t); +void *grammar_alloc_realloc (void *, size_t, size_t); +void *grammar_memory_copy (void *, const void *, size_t); +int grammar_string_compare (const byte *, const byte *); +int grammar_string_compare_n (const byte *, const byte *, size_t); +byte *grammar_string_copy (byte *, const byte *); +byte *grammar_string_copy_n (byte *, const byte *, size_t); +byte *grammar_string_duplicate (const byte *); +unsigned int grammar_string_length (const byte *); + +/* + loads grammar script from null-terminated ASCII <text> + returns unique grammar id to grammar object + returns 0 if an error occurs (call grammar_get_last_error to retrieve the error text) +*/ +grammar grammar_load_from_text (const byte *text); + +/* + sets a new <value> to a register <name> for grammar <id> + returns 0 on error (call grammar_get_last_error to retrieve the error text) + returns 1 on success +*/ +int grammar_set_reg8 (grammar id, const byte *name, byte value); + +/* + this function is obsolete, use only for debugging purposes + + checks if a null-terminated <text> matches given grammar <id> + returns 0 on error (call grammar_get_last_error to retrieve the error text) + returns 1 on success, the <prod> points to newly allocated buffer with production and <size> + is filled with the production size + call grammar_alloc_free to free the memory block pointed by <prod> +*/ +int grammar_check (grammar id, const byte *text, byte **prod, unsigned int *size); + +/* + does the same what grammar_check does but much more (approx. 4 times) faster + use this function instead of grammar_check + <estimate_prod_size> is a hint - the initial production buffer size will be of this size, + but if more room is needed it will be safely resized; set it to 0x1000 or so +*/ +int grammar_fast_check (grammar id, const byte *text, byte **prod, unsigned int *size, + unsigned int estimate_prod_size); + +/* + destroys grammar object identified by <id> + returns 0 on error (call grammar_get_last_error to retrieve the error text) + returns 1 on success +*/ +int grammar_destroy (grammar id); + +/* + retrieves last grammar error reported either by grammar_load_from_text, grammar_check + or grammar_destroy + the user allocated <text> buffer receives error description, <pos> points to error position, + <size> is the size of the text buffer to fill in - it must be at least 4 bytes long, +*/ +void grammar_get_last_error (byte *text, unsigned int size, int *pos); + +#ifdef __cplusplus +} +#endif + +#endif + diff --git a/mesalib/src/mesa/shader/grammar/grammar_crt.c b/mesalib/src/mesa/shader/grammar/grammar_crt.c new file mode 100644 index 000000000..d2c95d1c8 --- /dev/null +++ b/mesalib/src/mesa/shader/grammar/grammar_crt.c @@ -0,0 +1,64 @@ +#include "grammar_crt.h" + +#define GRAMMAR_PORT_BUILD 1 +#include "grammar.c" +#undef GRAMMAR_PORT_BUILD + + +void grammar_alloc_free (void *ptr) +{ + free (ptr); +} + +void *grammar_alloc_malloc (size_t size) +{ + return malloc (size); +} + +void *grammar_alloc_realloc (void *ptr, size_t old_size, size_t size) +{ + return realloc (ptr, size); +} + +void *grammar_memory_copy (void *dst, const void * src, size_t size) +{ + return memcpy (dst, src, size); +} + +int grammar_string_compare (const byte *str1, const byte *str2) +{ + return strcmp ((const char *) str1, (const char *) str2); +} + +int grammar_string_compare_n (const byte *str1, const byte *str2, size_t n) +{ + return strncmp ((const char *) str1, (const char *) str2, n); +} + +byte *grammar_string_copy (byte *dst, const byte *src) +{ + return (byte *) strcpy ((char *) dst, (const char *) src); +} + +byte *grammar_string_copy_n (byte *dst, const byte *src, size_t n) +{ + return (byte *) strncpy ((char *) dst, (const char *) src, n); +} + +unsigned int grammar_string_length (const byte *str) +{ + return strlen ((const char *) str); +} + +byte *grammar_string_duplicate (const byte *src) +{ + const unsigned int size = grammar_string_length (src); + byte *str = grammar_alloc_malloc (size + 1); + if (str != NULL) + { + grammar_memory_copy (str, src, size); + str[size] = '\0'; + } + return str; +} + diff --git a/mesalib/src/mesa/shader/grammar/grammar_crt.h b/mesalib/src/mesa/shader/grammar/grammar_crt.h new file mode 100644 index 000000000..492711e96 --- /dev/null +++ b/mesalib/src/mesa/shader/grammar/grammar_crt.h @@ -0,0 +1,20 @@ +#ifndef GRAMMAR_CRT_H +#define GRAMMAR_CRT_H + + +#include <stdlib.h> +#include <malloc.h> +#include <string.h> + + +typedef unsigned long grammar; +typedef unsigned char byte; + + +#define GRAMMAR_PORT_INCLUDE 1 +#include "grammar.h" +#undef GRAMMAR_PORT_INCLUDE + + +#endif + diff --git a/mesalib/src/mesa/shader/grammar/grammar_mesa.c b/mesalib/src/mesa/shader/grammar/grammar_mesa.c new file mode 100644 index 000000000..eb962505b --- /dev/null +++ b/mesalib/src/mesa/shader/grammar/grammar_mesa.c @@ -0,0 +1,87 @@ +/* + * Mesa 3-D graphics library + * Version: 6.1 + * + * Copyright (C) 1999-2004 Brian Paul All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN + * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +/** + * \file grammar_mesa.c + * mesa3d port to syntax parsing engine + * \author Michal Krol + */ + +#include "grammar_mesa.h" + +#define GRAMMAR_PORT_BUILD 1 +#include "grammar.c" +#undef GRAMMAR_PORT_BUILD + + +void grammar_alloc_free (void *ptr) +{ + _mesa_free (ptr); +} + +void *grammar_alloc_malloc (size_t size) +{ + return _mesa_malloc (size); +} + +void *grammar_alloc_realloc (void *ptr, size_t old_size, size_t size) +{ + return _mesa_realloc (ptr, old_size, size); +} + +void *grammar_memory_copy (void *dst, const void * src, size_t size) +{ + return _mesa_memcpy (dst, src, size); +} + +int grammar_string_compare (const byte *str1, const byte *str2) +{ + return _mesa_strcmp ((const char *) str1, (const char *) str2); +} + +int grammar_string_compare_n (const byte *str1, const byte *str2, size_t n) +{ + return _mesa_strncmp ((const char *) str1, (const char *) str2, n); +} + +byte *grammar_string_copy (byte *dst, const byte *src) +{ + return (byte *) _mesa_strcpy ((char *) dst, (const char *) src); +} + +byte *grammar_string_copy_n (byte *dst, const byte *src, size_t n) +{ + return (byte *) _mesa_strncpy ((char *) dst, (const char *) src, n); +} + +byte *grammar_string_duplicate (const byte *src) +{ + return (byte *) _mesa_strdup ((const char *) src); +} + +unsigned int grammar_string_length (const byte *str) +{ + return (unsigned int)_mesa_strlen ((const char *) str); +} + diff --git a/mesalib/src/mesa/shader/grammar/grammar_mesa.h b/mesalib/src/mesa/shader/grammar/grammar_mesa.h new file mode 100644 index 000000000..6c92c5812 --- /dev/null +++ b/mesalib/src/mesa/shader/grammar/grammar_mesa.h @@ -0,0 +1,43 @@ +/* + * Mesa 3-D graphics library + * Version: 6.1 + * + * Copyright (C) 1999-2004 Brian Paul All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN + * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef GRAMMAR_MESA_H +#define GRAMMAR_MESA_H + + +#include "main/imports.h" +/* NOTE: include Mesa 3-D specific headers here */ + + +typedef GLuint grammar; +typedef GLubyte byte; + + +#define GRAMMAR_PORT_INCLUDE 1 +#include "grammar.h" +#undef GRAMMAR_PORT_INCLUDE + + +#endif + diff --git a/mesalib/src/mesa/shader/grammar/grammar_syn.h b/mesalib/src/mesa/shader/grammar/grammar_syn.h new file mode 100644 index 000000000..840a1ab62 --- /dev/null +++ b/mesalib/src/mesa/shader/grammar/grammar_syn.h @@ -0,0 +1,202 @@ +".syntax grammar;\n" +".emtcode DECLARATION_END 0\n" +".emtcode DECLARATION_EMITCODE 1\n" +".emtcode DECLARATION_ERRORTEXT 2\n" +".emtcode DECLARATION_REGBYTE 3\n" +".emtcode DECLARATION_LEXER 4\n" +".emtcode DECLARATION_RULE 5\n" +".emtcode SPECIFIER_END 0\n" +".emtcode SPECIFIER_AND_TAG 1\n" +".emtcode SPECIFIER_OR_TAG 2\n" +".emtcode SPECIFIER_CHARACTER_RANGE 3\n" +".emtcode SPECIFIER_CHARACTER 4\n" +".emtcode SPECIFIER_STRING 5\n" +".emtcode SPECIFIER_IDENTIFIER 6\n" +".emtcode SPECIFIER_TRUE 7\n" +".emtcode SPECIFIER_FALSE 8\n" +".emtcode SPECIFIER_DEBUG 9\n" +".emtcode IDENTIFIER_SIMPLE 0\n" +".emtcode IDENTIFIER_LOOP 1\n" +".emtcode ERROR_NOT_PRESENT 0\n" +".emtcode ERROR_PRESENT 1\n" +".emtcode EMIT_NULL 0\n" +".emtcode EMIT_INTEGER 1\n" +".emtcode EMIT_IDENTIFIER 2\n" +".emtcode EMIT_CHARACTER 3\n" +".emtcode EMIT_LAST_CHARACTER 4\n" +".emtcode EMIT_CURRENT_POSITION 5\n" +".errtext INVALID_GRAMMAR \"internal error 2001: invalid grammar script\"\n" +".errtext SYNTAX_EXPECTED \"internal error 2002: '.syntax' keyword expected\"\n" +".errtext IDENTIFIER_EXPECTED \"internal error 2003: identifier expected\"\n" +".errtext MISSING_SEMICOLON \"internal error 2004: missing ';'\"\n" +".errtext INTEGER_EXPECTED \"internal error 2005: integer value expected\"\n" +".errtext STRING_EXPECTED \"internal error 2006: string expected\"\n" +"grammar\n" +" grammar_1 .error INVALID_GRAMMAR;\n" +"grammar_1\n" +" optional_space .and \".syntax\" .error SYNTAX_EXPECTED .and space .and identifier .and\n" +" semicolon .and declaration_list .and optional_space .and '\\0' .emit DECLARATION_END;\n" +"optional_space\n" +" space .or .true;\n" +"space\n" +" single_space .and .loop single_space;\n" +"single_space\n" +" white_char .or comment_block;\n" +"white_char\n" +" ' ' .or '\\t' .or '\\n' .or '\\r';\n" +"comment_block\n" +" '/' .and '*' .and comment_rest;\n" +"comment_rest\n" +" .loop comment_char_no_star .and comment_rest_1;\n" +"comment_rest_1\n" +" comment_end .or comment_rest_2;\n" +"comment_rest_2\n" +" '*' .and comment_rest;\n" +"comment_char_no_star\n" +" '\\x2B'-'\\xFF' .or '\\x01'-'\\x29';\n" +"comment_end\n" +" '*' .and '/';\n" +"identifier\n" +" identifier_ne .error IDENTIFIER_EXPECTED;\n" +"identifier_ne\n" +" first_idchar .emit * .and .loop follow_idchar .emit * .and .true .emit '\\0';\n" +"first_idchar\n" +" 'a'-'z' .or 'A'-'Z' .or '_';\n" +"follow_idchar\n" +" first_idchar .or digit_dec;\n" +"digit_dec\n" +" '0'-'9';\n" +"semicolon\n" +" optional_space .and ';' .error MISSING_SEMICOLON .and optional_space;\n" +"declaration_list\n" +" declaration .and .loop declaration;\n" +"declaration\n" +" emitcode_definition .emit DECLARATION_EMITCODE .or\n" +" errortext_definition .emit DECLARATION_ERRORTEXT .or\n" +" regbyte_definition .emit DECLARATION_REGBYTE .or\n" +" lexer_definition .emit DECLARATION_LEXER .or\n" +" rule_definition .emit DECLARATION_RULE;\n" +"emitcode_definition\n" +" \".emtcode\" .and space .and identifier .and space .and integer .and space_or_null;\n" +"integer\n" +" integer_ne .error INTEGER_EXPECTED;\n" +"integer_ne\n" +" hex_integer .emit 0x10 .or dec_integer .emit 10;\n" +"hex_integer\n" +" hex_prefix .and digit_hex .emit * .and .loop digit_hex .emit * .and .true .emit '\\0';\n" +"hex_prefix\n" +" '0' .and hex_prefix_1;\n" +"hex_prefix_1\n" +" 'x' .or 'X';\n" +"digit_hex\n" +" '0'-'9' .or 'a'-'f' .or 'A'-'F';\n" +"dec_integer\n" +" digit_dec .emit * .and .loop digit_dec .emit * .and .true .emit '\\0';\n" +"space_or_null\n" +" space .or '\\0';\n" +"errortext_definition\n" +" \".errtext\" .and space .and identifier .and space .and string .and space_or_null;\n" +"string\n" +" string_ne .error STRING_EXPECTED;\n" +"string_ne\n" +" '\"' .and .loop string_char_double_quotes .and '\"' .emit '\\0';\n" +"string_char_double_quotes\n" +" escape_sequence .or string_char .emit * .or '\\'' .emit *;\n" +"string_char\n" +" '\\x5D'-'\\xFF' .or '\\x28'-'\\x5B' .or '\\x23'-'\\x26' .or '\\x0E'-'\\x21' .or '\\x0B'-'\\x0C' .or\n" +" '\\x01'-'\\x09';\n" +"escape_sequence\n" +" '\\\\' .emit * .and escape_code;\n" +"escape_code\n" +" simple_escape_code .emit * .or hex_escape_code .or oct_escape_code;\n" +"simple_escape_code\n" +" '\\'' .or '\"' .or '?' .or '\\\\' .or 'a' .or 'b' .or 'f' .or 'n' .or 'r' .or 't' .or 'v';\n" +"hex_escape_code\n" +" 'x' .emit * .and digit_hex .emit * .and .loop digit_hex .emit *;\n" +"oct_escape_code\n" +" digit_oct .emit * .and optional_digit_oct .and optional_digit_oct;\n" +"digit_oct\n" +" '0'-'7';\n" +"optional_digit_oct\n" +" digit_oct .emit * .or .true;\n" +"regbyte_definition\n" +" \".regbyte\" .and space .and identifier .and space .and integer .and space_or_null;\n" +"lexer_definition\n" +" \".string\" .and space .and identifier .and semicolon;\n" +"rule_definition\n" +" identifier_ne .and space .and definition;\n" +"definition\n" +" specifier .and optional_specifiers_and_or .and semicolon .emit SPECIFIER_END;\n" +"optional_specifiers_and_or\n" +" and_specifiers .emit SPECIFIER_AND_TAG .or or_specifiers .emit SPECIFIER_OR_TAG .or .true;\n" +"specifier\n" +" specifier_condition .and optional_space .and specifier_rule;\n" +"specifier_condition\n" +" specifier_condition_1 .or .true;\n" +"specifier_condition_1\n" +" \".if\" .and optional_space .and '(' .and optional_space .and left_operand .and operator .and\n" +" right_operand .and optional_space .and ')';\n" +"left_operand\n" +" identifier;\n" +"operator\n" +" operator_1 .or operator_2;\n" +"operator_1\n" +" optional_space .and '!' .and '=' .and optional_space;\n" +"operator_2\n" +" optional_space .and '=' .and '=' .and optional_space;\n" +"right_operand\n" +" integer;\n" +"specifier_rule\n" +" specifier_rule_1 .and optional_error .and .loop emit .and .true .emit EMIT_NULL;\n" +"specifier_rule_1\n" +" character_range .emit SPECIFIER_CHARACTER_RANGE .or\n" +" character .emit SPECIFIER_CHARACTER .or\n" +" string_ne .emit SPECIFIER_STRING .or\n" +" \".true\" .emit SPECIFIER_TRUE .or\n" +" \".false\" .emit SPECIFIER_FALSE .or\n" +" \".debug\" .emit SPECIFIER_DEBUG .or\n" +" advanced_identifier .emit SPECIFIER_IDENTIFIER;\n" +"character\n" +" '\\'' .and string_char_single_quotes .and '\\'' .emit '\\0';\n" +"string_char_single_quotes\n" +" escape_sequence .or string_char .emit * .or '\"' .emit *;\n" +"character_range\n" +" character .and optional_space .and '-' .and optional_space .and character;\n" +"advanced_identifier\n" +" optional_loop .and identifier;\n" +"optional_loop\n" +" optional_loop_1 .emit IDENTIFIER_LOOP .or .true .emit IDENTIFIER_SIMPLE;\n" +"optional_loop_1\n" +" \".loop\" .and space;\n" +"optional_error\n" +" error .emit ERROR_PRESENT .or .true .emit ERROR_NOT_PRESENT;\n" +"error\n" +" space .and \".error\" .and space .and identifier;\n" +"emit\n" +" emit_output .or emit_regbyte;\n" +"emit_output\n" +" space .and \".emit\" .and space .and emit_param;\n" +"emit_param\n" +" integer_ne .emit EMIT_INTEGER .or\n" +" identifier_ne .emit EMIT_IDENTIFIER .or\n" +" character .emit EMIT_CHARACTER .or\n" +" '*' .emit EMIT_LAST_CHARACTER .or\n" +" '$' .emit EMIT_CURRENT_POSITION;\n" +"emit_regbyte\n" +" space .and \".load\" .and space .and identifier .and space .and emit_param;\n" +"and_specifiers\n" +" and_specifier .and .loop and_specifier;\n" +"or_specifiers\n" +" or_specifier .and .loop or_specifier;\n" +"and_specifier\n" +" space .and \".and\" .and space .and specifier;\n" +"or_specifier\n" +" space .and \".or\" .and space .and specifier;\n" +".string __string_filter;\n" +"__string_filter\n" +" __first_identifier_char .and .loop __next_identifier_char;\n" +"__first_identifier_char\n" +" 'a'-'z' .or 'A'-'Z' .or '_' .or '.';\n" +"__next_identifier_char\n" +" 'a'-'z' .or 'A'-'Z' .or '_' .or '0'-'9';\n" +"" |