#ifndef _GRAMMAR_H_ #define _GRAMMAR_H_ 1 #include #ifndef TRUE #define TRUE (0==0) #endif #ifndef FALSE #define FALSE (0!=0) #endif typedef int (*parsefn)(void); #define LARGEST_ALT 9 // Max number of phrases in any Alt: 0 (Reserved), 1:8 #define NEGATED_PHRASE (1U<<24U) #define GUARD_PHRASE (1U<<25U) #define WHITESPACE_ALLOWED (1U<<26U) #define GRAMMAR_TYPE_SHIFT 27U #define GRAMMAR_TYPE_MASK 31U #define BIP_TYPE (1U <<27U) #define PHRASE_TYPE (2U <<27U) #define SEMANTIC_TYPE (3U <<27U) #define KEYWORD_TYPE (4U <<27U) #define CHAR_TYPE (5U <<27U) #define UTF32CHAR_TYPE (6U <<27U) #define STRING_TYPE (7U <<27U) #define UTF32STRING_TYPE (8U <<27U) #define REGEXP_TYPE (9U <<27U) #define OPTION_TYPE (10U <<27U) #define COUNT_OF_ALTS (11U <<27U) #define COUNT_OF_PHRASES (12U <<27U) #define ALT_NUMBER (13U <<27U) #define INDEX_MASK 0x7FFFFFU // (We have room for types 1..31U) #define PhraseType(idx) ((((idx)>>27U)&31U)) #define BIP_BASE 0 #define PHRASE_BASE 1 #define SEMANTIC_BASE 24 #define AST_BASE 24 #define NUM_BIPS 1 #define NUM_SIMPLE_PHRASES 23 #define NUM_SEMANTIC_PHRASES 0 #define NUM_PHRASES (NUM_BIPS+NUM_SIMPLE_PHRASES+NUM_SEMANTIC_PHRASES) #define NUM_KEYWORDS 14 #define NUM_REGEXPS 7 #define NUM_GRAMMAR 131 #define B_EOF 0 #define P_empty 1 #define P_SS 2 #define P_array 3 #define P_opt_sign 4 #define P_number 5 #define P_boolean 6 #define P_value 7 #define P_rest_of_value_list 8 #define P_value_list 9 #define P_quote 10 #define P_char 11 #define P_chars 12 #define P_string 13 #define P_name 14 #define P_opt_exponent 15 #define P_float 16 #define P_integer 17 #define P_argument 18 #define P_rest_of_argument_list 19 #define P_opt_argument_list 20 #define P_instruction 21 #define P_instruction_list 22 #define P_opt_block 23 extern const int bip_map[NUM_BIPS]; extern const int sequential_phrase_no_to_grammar_index[NUM_SIMPLE_PHRASES]; extern const wchar_t *phrasename[NUM_BIPS+NUM_SIMPLE_PHRASES+NUM_SEMANTIC_PHRASES]; extern const wchar_t *semantic_phrasename[NUM_SEMANTIC_PHRASES]; extern const wchar_t *semantic_code[NUM_SEMANTIC_PHRASES]; extern const wchar_t *ast_code[NUM_SIMPLE_PHRASES]; extern const wchar_t *xcomment[NUM_PHRASES]; extern const wchar_t *keyword[NUM_KEYWORDS]; extern const wchar_t *regexps[NUM_REGEXPS]; extern const int gram[NUM_GRAMMAR]; #define G_empty 0 #define G_SS 3 #define G_array 7 #define G_opt_sign 12 #define G_number 17 #define G_boolean 24 #define G_value 31 #define G_rest_of_value_list 44 #define G_value_list 51 #define G_quote 55 #define G_char 58 #define G_chars 62 #define G_string 68 #define G_name 73 #define G_opt_exponent 76 #define G_float 83 #define G_integer 87 #define G_argument 90 #define G_rest_of_argument_list 97 #define G_opt_argument_list 104 #define G_instruction 110 #define G_instruction_list 118 #define G_opt_block 124 extern parsefn parsetime[NUM_SEMANTIC_PHRASES]; #ifndef SUPPRESS_DATA const wchar_t *phrasename[NUM_BIPS+NUM_SIMPLE_PHRASES+NUM_SEMANTIC_PHRASES] = { /*0+0*/ L"EOF" /*0*/, /*1+0*/ L"empty", /*1+1*/ L"SS", /*1+2*/ L"array", /*1+3*/ L"opt-sign", /*1+4*/ L"number", /*1+5*/ L"boolean", /*1+6*/ L"value", /*1+7*/ L"rest-of-value-list", /*1+8*/ L"value-list", /*1+9*/ L"quote", /*1+10*/ L"char", /*1+11*/ L"chars", /*1+12*/ L"string", /*1+13*/ L"name", /*1+14*/ L"opt-exponent", /*1+15*/ L"float", /*1+16*/ L"integer", /*1+17*/ L"argument", /*1+18*/ L"rest-of-argument-list", /*1+19*/ L"opt-argument-list", /*1+20*/ L"instruction", /*1+21*/ L"instruction-list", /*1+22*/ L"opt-block", }; const wchar_t *phrasename_c[NUM_BIPS+NUM_SIMPLE_PHRASES+NUM_SEMANTIC_PHRASES] = { /*0+0*/ L"EOF" /*0*/, /*1+0*/ L"empty", /*1+1*/ L"SS", /*1+2*/ L"array", /*1+3*/ L"opt_sign", /*1+4*/ L"number", /*1+5*/ L"boolean", /*1+6*/ L"value", /*1+7*/ L"rest_of_value_list", /*1+8*/ L"value_list", /*1+9*/ L"quote", /*1+10*/ L"char", /*1+11*/ L"chars", /*1+12*/ L"string", /*1+13*/ L"name", /*1+14*/ L"opt_exponent", /*1+15*/ L"float", /*1+16*/ L"integer", /*1+17*/ L"argument", /*1+18*/ L"rest_of_argument_list", /*1+19*/ L"opt_argument_list", /*1+20*/ L"instruction", /*1+21*/ L"instruction_list", /*1+22*/ L"opt_block", }; const int bip_map[NUM_BIPS] = { /*0*/ 0, }; const int sequential_phrase_no_to_grammar_index[NUM_SIMPLE_PHRASES] = { G_empty, /*0*/ G_SS, /*3*/ G_array, /*7*/ G_opt_sign, /*12*/ G_number, /*17*/ G_boolean, /*24*/ G_value, /*31*/ G_rest_of_value_list, /*44*/ G_value_list, /*51*/ G_quote, /*55*/ G_char, /*58*/ G_chars, /*62*/ G_string, /*68*/ G_name, /*73*/ G_opt_exponent, /*76*/ G_float, /*83*/ G_integer, /*87*/ G_argument, /*90*/ G_rest_of_argument_list, /*97*/ G_opt_argument_list, /*104*/ G_instruction, /*110*/ G_instruction_list, /*118*/ G_opt_block, /*124*/ }; const wchar_t *semantic_phrasename[NUM_SEMANTIC_PHRASES] = { }; const wchar_t *semantic_code[NUM_SEMANTIC_PHRASES] = { }; parsefn parsetime[NUM_SEMANTIC_PHRASES] = { }; // Comments are stored so that they can be re-inserted, should // we need to regenerate a grammar.g file from this header file. const wchar_t *xcomment[NUM_PHRASES] = { /* 0*/ NULL, /* 1*/ NULL, /* 2*/ NULL, /* 3*/ NULL, /* 4*/ NULL, /* 5*/ NULL, /* 6*/ NULL, /* 7*/ NULL, /* 8*/ NULL, /* 9*/ NULL, /* 10*/ NULL, /* 11*/ NULL, /* 12*/ NULL, /* 13*/ NULL, /* 14*/ NULL, /* 15*/ NULL, /* 16*/ NULL, /* 17*/ NULL, /* 18*/ NULL, /* 19*/ NULL, /* 20*/ NULL, /* 21*/ NULL, /* 22*/ NULL, /* 23*/ NULL, }; const wchar_t *ast_code[NUM_SIMPLE_PHRASES] = { /*empty*/ L"\n" " return -1;\n", /*SS*/ L"\n" " return T[1];\n", /*array*/ L"\n" " return AST_mktuple(AST_list, T[2]);\n", /*opt_sign*/ L"\n" " // returns AST_source_text containing <>\n" " if (alt != 0) return -1;\n" " return AST_mktuple(AST_source_text, T[1], -1); \n", /*number*/ L"\n" " // returns AST_source_text containing <>\n" " if (T[1] == -1) return T[2];\n" " {\n" " int sign;\n" " AST_detuple(T[1], AST_source_text, &sign, NULL);\n" " return AST_mktuple(AST_number, AST_mktuple(AST_source_text, sign, T[2]));\n" " }\n", /*boolean*/ L"\n" " return AST_mktuple(AST_boolean, AST_mktuple(AST_source_text, T[1], -1));\n", /*value*/ L"\n" " if (alt == 3) {\n" " fprintf(stdout, \"*** AN INSTRUCTION SHOULD NEVER BE FOUND AS A VALUE ***\\n\");\n" " fprintf(stderr, \"*** AN INSTRUCTION SHOULD NEVER BE FOUND AS A VALUE ***\\n\");\n" " }\n" " return T[1];\n", /*rest_of_value_list*/ L"\n" " // returns AST_list_element containing << value, next_value >>\n" " if (alt != 0) return -1;\n" " return AST_mktuple(AST_list_element, T[2], T[3]);\n", /*value_list*/ L"\n" " // returns AST_list_element containing << value, next_value >>\n" " return AST_mktuple(AST_list_element, T[1], T[2]);\n", /*quote*/ L"\n" " return -1;\n", /*char*/ L"\n" " // returns AST_source_text containing <>\n" " return AST_mktuple(AST_source_text, T[2], -1);\n", /*chars*/ L"\n" " // returns AST_source_text containing <>\n" " if (alt != 0) return -1;\n" " int text;\n" " AST_detuple(T[1], AST_source_text, &text, NULL);\n" " return AST_mktuple(AST_source_text, text, T[2]);\n", /*string*/ L"\n" " return AST_mktuple(AST_string, T[2]);\n", /*name*/ L"\n" " return AST_mktuple(AST_name, AST_mktuple(AST_source_text, T[1], -1));\n", /*opt_exponent*/ L"\n" " // returns AST_source_text containing <>\n" " if (alt != 0) return -1;\n" " if (T[2] == -1) {\n" " return AST_mktuple(AST_source_text, T[1], T[3]);\n" " } else {\n" " AST_detuple(T[2], AST_source_text, &text, NULL);\n" " if (text == -1) {\n" " return AST_mktuple(AST_source_text, T[1], T[3]);\n" " } else {\n" " return AST_mktuple(AST_source_text, T[1], AST_mktuple(AST_source_text, text, T[3]));\n" " }\n" " }\n", /*float*/ L"\n" " // returns AST_source_text containing <>\n" " return AST_mktuple(AST_source_text, T[1], T[2]);\n", /*integer*/ L"\n" " // returns AST_source_text containing <>\n" " return AST_mktuple(AST_source_text, T[1], -1);\n", /*argument*/ L"\n" " // returns AST_argument containing << name, value, next_arg >>\n" " if (alt == 0) return AST_mktuple(AST_argument, T[1], T[3], -1);\n" " return AST_mktuple(AST_argument, -1, T[1], -1);\n", /*rest_of_argument_list*/ L"\n" " // returns AST_argument containing << name, value, next_arg >>\n" " {\n" " int name, value;\n" " if (alt != 0) return -1;\n" " AST_detuple(T[2], AST_argument, &name, &value, NULL);\n" " return AST_mktuple(AST_argument, name, value, T[3]);\n" " }\n", /*opt_argument_list*/ L"\n" " // returns AST_argument containing << name, value, next_arg >>\n" " {\n" " int name, value;\n" " if (alt != 0) return -1;\n" " AST_detuple(T[1], AST_argument, &name, &value, NULL);\n" " return AST_mktuple(AST_argument, name, value, T[2]);\n" " }\n", /*instruction*/ L"\n" " // returns AST_instruction tuple containing <>\n" " // (I'll ignore any modifiers present for now.)\n" " return AST_mktuple(AST_instruction, T[2], T[4], T[6], -1);\n", /*instruction_list*/ L"\n" " // returns AST_instruction tuple containing <>\n" " {\n" " int name, args, block;\n" " if (alt != 0) return -1;\n" " AST_detuple(T[1], AST_instruction, &name, &args, &block, NULL);\n" " return AST_mktuple(AST_instruction, name, args, block, T[2]);\n" " }\n", /*opt_block*/ L"\n" " if (alt != 0) return -1;\n" " return T[2];\n", }; const wchar_t *keyword[NUM_KEYWORDS] = { /* 0*/ L"", /* 1*/ L"[", /* 2*/ L"]", /* 3*/ L"-", /* 4*/ L"true", /* 5*/ L"false", /* 6*/ L"undef", /* 7*/ L",", /* 8*/ L"=", /* 9*/ L"(", /* 10*/ L")", /* 11*/ L"{", /* 12*/ L"}", /* 13*/ L";", }; const wchar_t *regexps[NUM_REGEXPS] = { /*0*/ L"^\"", /*1*/ L"^.", /*2*/ L"^[A-Za-z\\$][A-Za-z0-9_]*", /*3*/ L"^[Ee]", /*4*/ L"^[0-9]*\\.[0-9][0-9]*", /*5*/ L"^[0-9][0-9]*", /*6*/ L"^[%#!*]*", }; const int gram[NUM_GRAMMAR /* 131 */] = { // P = ...; /* 0*/ COUNT_OF_ALTS | 0x000001, /* 1*/ COUNT_OF_PHRASES | 0x000001, /* 2*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000000, /* */ // P = ...; /* 3*/ COUNT_OF_ALTS | 0x000001, /* 4*/ COUNT_OF_PHRASES | 0x000002, /* 5*/ PHRASE_TYPE | G_instruction_list, /* 6*/ BIP_TYPE | WHITESPACE_ALLOWED | B_EOF, // P = ...; /* 7*/ COUNT_OF_ALTS | 0x000001, /* 8*/ COUNT_OF_PHRASES | 0x000003, /* 9*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000001, /* [ */ /* 10*/ PHRASE_TYPE | G_value_list, /* 11*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000002, /* ] */ // P = ...; /* 12*/ COUNT_OF_ALTS | 0x000002, /* 13*/ COUNT_OF_PHRASES | 0x000001, /* 14*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000003, /* - */ /* 15*/ COUNT_OF_PHRASES | 0x000001, /* 16*/ PHRASE_TYPE | G_empty, // P = ...; /* 17*/ COUNT_OF_ALTS | 0x000002, /* 18*/ COUNT_OF_PHRASES | 0x000002, /* 19*/ PHRASE_TYPE | G_opt_sign, /* 20*/ PHRASE_TYPE | G_float, /* 21*/ COUNT_OF_PHRASES | 0x000002, /* 22*/ PHRASE_TYPE | G_opt_sign, /* 23*/ PHRASE_TYPE | G_integer, // P = ...; /* 24*/ COUNT_OF_ALTS | 0x000003, /* 25*/ COUNT_OF_PHRASES | 0x000001, /* 26*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000004, /* true */ /* 27*/ COUNT_OF_PHRASES | 0x000001, /* 28*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000005, /* false */ /* 29*/ COUNT_OF_PHRASES | 0x000001, /* 30*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000006, /* undef */ // P = ...; /* 31*/ COUNT_OF_ALTS | 0x000006, /* 32*/ COUNT_OF_PHRASES | 0x000001, /* 33*/ PHRASE_TYPE | G_boolean, /* 34*/ COUNT_OF_PHRASES | 0x000001, /* 35*/ PHRASE_TYPE | G_array, /* 36*/ COUNT_OF_PHRASES | 0x000001, /* 37*/ PHRASE_TYPE | G_number, /* 38*/ COUNT_OF_PHRASES | 0x000001, /* 39*/ PHRASE_TYPE | G_instruction, /* 40*/ COUNT_OF_PHRASES | 0x000001, /* 41*/ PHRASE_TYPE | G_name, /* 42*/ COUNT_OF_PHRASES | 0x000001, /* 43*/ PHRASE_TYPE | G_string, // P = ...; /* 44*/ COUNT_OF_ALTS | 0x000002, /* 45*/ COUNT_OF_PHRASES | 0x000003, /* 46*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000007, /* , */ /* 47*/ PHRASE_TYPE | G_value, /* 48*/ PHRASE_TYPE | G_rest_of_value_list, /* 49*/ COUNT_OF_PHRASES | 0x000001, /* 50*/ PHRASE_TYPE | G_empty, // P = ...; /* 51*/ COUNT_OF_ALTS | 0x000001, /* 52*/ COUNT_OF_PHRASES | 0x000002, /* 53*/ PHRASE_TYPE | G_value, /* 54*/ PHRASE_TYPE | G_rest_of_value_list, // P = ...; /* 55*/ COUNT_OF_ALTS | 0x000001, /* 56*/ COUNT_OF_PHRASES | 0x000001, /* 57*/ REGEXP_TYPE | WHITESPACE_ALLOWED | 0x000000, /* ^\" */ // P = ...; /* 58*/ COUNT_OF_ALTS | 0x000001, /* 59*/ COUNT_OF_PHRASES | 0x000002, /* 60*/ PHRASE_TYPE | NEGATED_PHRASE | G_quote, /* 61*/ REGEXP_TYPE | WHITESPACE_ALLOWED | 0x000001, /* ^. */ // P = ...; /* 62*/ COUNT_OF_ALTS | 0x000002, /* 63*/ COUNT_OF_PHRASES | 0x000002, /* 64*/ PHRASE_TYPE | G_char, /* 65*/ PHRASE_TYPE | G_chars, /* 66*/ COUNT_OF_PHRASES | 0x000001, /* 67*/ PHRASE_TYPE | G_empty, // P = ...; /* 68*/ COUNT_OF_ALTS | 0x000001, /* 69*/ COUNT_OF_PHRASES | 0x000003, /* 70*/ PHRASE_TYPE | G_quote, /* 71*/ PHRASE_TYPE | G_chars, /* 72*/ PHRASE_TYPE | G_quote, // P = ...; /* 73*/ COUNT_OF_ALTS | 0x000001, /* 74*/ COUNT_OF_PHRASES | 0x000001, /* 75*/ REGEXP_TYPE | WHITESPACE_ALLOWED | 0x000002, /* ^[A-Za-z\\$][A-Za-z0-9_]* */ // P = ...; /* 76*/ COUNT_OF_ALTS | 0x000002, /* 77*/ COUNT_OF_PHRASES | 0x000003, /* 78*/ REGEXP_TYPE | WHITESPACE_ALLOWED | 0x000003, /* ^[Ee] */ /* 79*/ PHRASE_TYPE | G_opt_sign, /* 80*/ PHRASE_TYPE | G_integer, /* 81*/ COUNT_OF_PHRASES | 0x000001, /* 82*/ PHRASE_TYPE | G_empty, // P = ...; /* 83*/ COUNT_OF_ALTS | 0x000001, /* 84*/ COUNT_OF_PHRASES | 0x000002, /* 85*/ REGEXP_TYPE | WHITESPACE_ALLOWED | 0x000004, /* ^[0-9]*\\.[0-9][0-9]* */ /* 86*/ PHRASE_TYPE | G_opt_exponent, // P = ...; /* 87*/ COUNT_OF_ALTS | 0x000001, /* 88*/ COUNT_OF_PHRASES | 0x000001, /* 89*/ REGEXP_TYPE | WHITESPACE_ALLOWED | 0x000005, /* ^[0-9][0-9]* */ // P = ...; /* 90*/ COUNT_OF_ALTS | 0x000002, /* 91*/ COUNT_OF_PHRASES | 0x000003, /* 92*/ PHRASE_TYPE | G_name, /* 93*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000008, /* = */ /* 94*/ PHRASE_TYPE | G_value, /* 95*/ COUNT_OF_PHRASES | 0x000001, /* 96*/ PHRASE_TYPE | G_value, // P = ...; /* 97*/ COUNT_OF_ALTS | 0x000002, /* 98*/ COUNT_OF_PHRASES | 0x000003, /* 99*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000007, /* , */ /*100*/ PHRASE_TYPE | G_argument, /*101*/ PHRASE_TYPE | G_rest_of_argument_list, /*102*/ COUNT_OF_PHRASES | 0x000001, /*103*/ PHRASE_TYPE | G_empty, // P = ...; /*104*/ COUNT_OF_ALTS | 0x000002, /*105*/ COUNT_OF_PHRASES | 0x000002, /*106*/ PHRASE_TYPE | G_argument, /*107*/ PHRASE_TYPE | G_rest_of_argument_list, /*108*/ COUNT_OF_PHRASES | 0x000001, /*109*/ PHRASE_TYPE | G_empty, // P = ...; /*110*/ COUNT_OF_ALTS | 0x000001, /*111*/ COUNT_OF_PHRASES | 0x000006, /*112*/ REGEXP_TYPE | WHITESPACE_ALLOWED | 0x000006, /* ^[%#!*]* */ /*113*/ PHRASE_TYPE | G_name, /*114*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x000009, /* ( */ /*115*/ PHRASE_TYPE | G_opt_argument_list, /*116*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x00000a, /* ) */ /*117*/ PHRASE_TYPE | G_opt_block, // P = ...; /*118*/ COUNT_OF_ALTS | 0x000002, /*119*/ COUNT_OF_PHRASES | 0x000002, /*120*/ PHRASE_TYPE | G_instruction, /*121*/ PHRASE_TYPE | G_instruction_list, /*122*/ COUNT_OF_PHRASES | 0x000001, /*123*/ PHRASE_TYPE | G_empty, // P = ...; /*124*/ COUNT_OF_ALTS | 0x000002, /*125*/ COUNT_OF_PHRASES | 0x000003, /*126*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x00000b, /* { */ /*127*/ PHRASE_TYPE | G_instruction_list, /*128*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x00000c, /* } */ /*129*/ COUNT_OF_PHRASES | 0x000001, /*130*/ KEYWORD_TYPE | WHITESPACE_ALLOWED | 0x00000d, /* ; */ }; #ifdef INITCODE // This block contains C code that is inserted into the generated parser: // Note that in this code we use the common C convention of row-major format // for transformation matrices *internally*, e.g: // r_x u_x f_x 0 // r_y u_y f_y 0 // r_z u_z f_z 0 // t_x t_y t_z 1 // where r, u, and f represent the rotated basis vectors (right, up, forward) and t represents the translation vector. // This is different from OpenGL which uses column-major format, so any graphics // generated by this code should convert any transformation matrices appropriately. // Unfortunately it appears it is also different from OpenSCAD :-( ... // OpenSCAD: translate([t_x, t_y, t_z]) cube([1,1,1]); // maps to csg: // multmatrix([[1, 0, 0, t_x], [0, 1, 0, t_y], [0, 0, 1, t_z], [0, 0, 0, 1]]) { // cube(size = [1, 1, 1], center = false); // } // // i.e. // // [1, 0, 0, t_x], // [0, 1, 0, t_y], // [0, 0, 1, t_z], // [0, 0, 0, 1] // // So the code below swaps the axes in the load_matrix and print_matrix calls when // reading and printing matrices in the context of .csg files, but uses row_major format // *internally* to store the matrices and perform the calculations. #include #define PRECISION 0.001f float deg2rad(float deg) { return deg*(2*M_PI/360.0); } float rad2deg(float rad) { return rad*(360.0/(2*M_PI)); } // Transformation matrix: typedef float Mat4x4[4][4]; // Conflate two 4x4 matrices by multiplying them together void mat4x4_mul(Mat4x4 result, const Mat4x4 a, const Mat4x4 b) { Mat4x4 tmp; // be careful not to overwrite inputs during calculations for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) { tmp[i][j] = 0.0f; for (int k = 0; k < 4; k++) tmp[i][j] += a[i][k] * b[k][j]; } // Write out result at end in case it was aliasing one of the inputs for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) result[i][j] = tmp[i][j]; } // Interface functions to build a transformation matrix float fixzero(float num) { if (num >= -PRECISION && num <= PRECISION) return 0.0; else return num; } // Helper to print a matrix void sprint_matrix(char *target, const Mat4x4 m, char *sep) { sprintf(target, "[ [%0.2f, %0.2f, %0.2f, %0.2f]%s" "[%0.2f, %0.2f, %0.2f, %0.2f]%s" "[%0.2f, %0.2f, %0.2f, %0.2f]%s" "[%0.2f, %0.2f, %0.2f, %0.2f] ]", fixzero(m[0][0]),fixzero(m[0][1]),fixzero(m[0][2]),fixzero(m[0][3]), sep, fixzero(m[1][0]),fixzero(m[1][1]),fixzero(m[1][2]),fixzero(m[1][3]), sep, fixzero(m[2][0]),fixzero(m[2][1]),fixzero(m[2][2]),fixzero(m[2][3]), sep, fixzero(m[3][0]),fixzero(m[3][1]),fixzero(m[3][2]),fixzero(m[3][3]) ); } void print_matrix(FILE *f, const Mat4x4 m, char *sep) { char tmp[512]; sprint_matrix(tmp, m, sep); fprintf(f, "%s", tmp); } void load_matrix(Mat4x4 mat, float a, float b, float c, float d, float e, float f, float g, float h, float i, float j, float k, float l, float m, float n, float o, float p) { mat[0][0] = a; mat[0][1] = b; mat[0][2] = c; mat[0][3] = d; mat[1][0] = e; mat[1][1] = f; mat[1][2] = g; mat[1][3] = h; mat[2][0] = i; mat[2][1] = j; mat[2][2] = k; mat[2][3] = l; mat[3][0] = m; mat[3][1] = n; mat[3][2] = o; mat[3][3] = p; // printf("load_matrix("); print_matrix(stdout, mat, ", "); printf(")\n"); } // Utility to decompose a 4x4 matrix into translation, rotation, and scale void decompose_matrix(const Mat4x4 m, float *tx, float *ty, float *tz, float *rx, float *ry, float *rz, float *sx, float *sy, float *sz) { // Translation extraction *tx = m[0][3]; *ty = m[1][3]; *tz = m[2][3]; // Scale extraction *sx = sqrtf(m[0][0] * m[0][0] + m[1][0] * m[1][0] + m[2][0] * m[2][0]); *sy = sqrtf(m[0][1] * m[0][1] + m[1][1] * m[1][1] + m[2][1] * m[2][1]); *sz = sqrtf(m[0][2] * m[0][2] + m[1][2] * m[1][2] + m[2][2] * m[2][2]); // Rotation extraction (assuming no shearing and positive scales) // Normalize the rotation part of the matrix by dividing by scale Mat4x4 rotation_only_matrix; for (int i = 0; i < 3; i++) { rotation_only_matrix[i][0] = m[i][0] / *sx; rotation_only_matrix[i][1] = m[i][1] / *sy; rotation_only_matrix[i][2] = m[i][2] / *sz; } // Extract rotations using atan2 (assuming ZYX Euler angles for simplicity) *ry = asinf(-rotation_only_matrix[0][2]); // Pitch if (cosf(*ry) != 0) { *rx = atan2f(rotation_only_matrix[1][2], rotation_only_matrix[2][2]); // Roll *rz = atan2f(rotation_only_matrix[0][1], rotation_only_matrix[0][0]); // Yaw } else { // Gimbal lock case *rx = atan2f(-rotation_only_matrix[2][1], rotation_only_matrix[1][1]); *rz = 0.0f; // Can be anything, set to 0 for consistency } *rx = rad2deg(*rx); *ry = rad2deg(*ry); *rz = rad2deg(*rz); } #define BUILDING_CAST 1 // automatically-generated code will build the Concrete version of an AST #define BUILDING_AST 1 // Code we supply will override some of that to build a proper AST. extern int AST_root; // set up as the result of the top-level parse function in main(). // We extend the parser's default CAST with application-specific AST tuples: enum { // a missing value will be stored as -1. // next free slot after last P_* phrase - should not clash with anything: AST_boolean = AST_BASE, // << source_text: true || false || undef , literal integer: 1 || 0 || -1>> AST_number, // << source_text: number >> (could be integer or float) AST_name, // << source_text: name >> AST_string, // << source_text: string >> AST_value, // <> (determine which from type code of child) AST_list, // << list head >> AST_list_element, // << value, next_value >> AST_argument, // << name, value, next_arg >> AST_instruction, // <> AST_source_text, // <> AST_poolstring, // <> (Used to save text we generate internally) AST_LAST_OP }; // parallels the enum above. Used for debugging/diagnostic messages only. const char *ast_name[AST_LAST_OP-AST_BASE] = { "AST_boolean", "AST_number", "AST_name", "AST_string", "AST_value", "AST_list", "AST_list_element", "AST_argument", "AST_instruction", "AST_source_text", "AST_poolstring" }; static int str_to_pool(const char *str) { int result = Stringpool_nextfree; for (;;) { char ch = *str++; _Stringpool(Stringpool_nextfree++) = ch; if (ch == '\0') break; } return result; } static char *pool_to_str(int poolidx) { int len = 0; for (;;) { char ch = Stringpool(poolidx+len); if (ch == '\0') break; len += 1; } char *str = malloc(len+1); len = 0; for (;;) { char ch = Stringpool(poolidx+len); str[len] = ch; if (ch == '\0') break; len += 1; } return str; } // A support routine that makes creating AST tuples look a little more intuitive: static const int AST_end_marker = 0x81818181; #define AST_mktuple(c_op...) AST_mktuple_inner(__FILE__, __LINE__, c_op, AST_end_marker) int AST_mktuple_inner(const char *file, const int line, int AST_op, ...) { int t[LARGEST_ALT]; va_list ap; int i, count = 0; t[0] = 0; va_start(ap, AST_op); for (;;) { i = va_arg(ap, int); if (i == AST_end_marker) break; // Inserted by wrapper macro. Can't determine count otherwise. count += 1; if (count == LARGEST_ALT) { fprintf(stderr, "** Error: AST_mktuple is trying to create a tuple with more items than I can handle, in %s line %d\n", file, line); exit(1); } t[count] = i; } va_end(ap); return P_mktuple(AST_op, 0, count, t); } // Similarly, code to extract fields from an AST tuple. We could just access the fields // directly but this wrapper is cleaner and safer and less verbose: #define AST_detuple(astp...) AST_detuple_inner(__FILE__, __LINE__, astp, &AST_end_marker) void AST_detuple_inner(const char *file, const int line, int astp, int AST_op, int *ptrs, ...) { // The given AST_op has to match the stored one. The expected number of parameters has to match too. // However there is no specific check on the individual parameters. va_list ap; int count = 1; int *ptr; if (P_op(astp) != AST_op) { if (AST_op < AST_BASE) { fprintf(stderr, "AST_detuple at %s, line %d: params should be astp, AST_something...\n", file, line); } } if (ptrs) *ptrs = P_P(astp, count); va_start(ap, ptrs); for (;;) { ptr = va_arg(ap, int *); if (ptr == &AST_end_marker) break; // Inserted by wrapper macro. Can't determine count otherwise. count += 1; if (ptr) *ptr = P_P(astp, count); // NULL ptrs are skipped. //fprintf(stderr, "%p: P_P(%d,%d) = %d\n", ptr, astp, count, *ptr); } va_end(ap); if (P_count(astp) != count) { // *Extremely* useful test! fprintf(stderr, "? Warning: AST at %d has %d members, not the %d given as parameters to AST_detuple().\n" "(see %s, line %d)\n", astp, P_count(astp), count, file, line); } } void indent(int d) { while (d > 0) { fprintf(stdout, " "); d -= 1; } } void sprint_csg_inner(char *target, int P) { // appends to string. Caller should set the target string to "" before calling. if (P == -1) return; // avoid runtime error of "left shift of 15 by 28 places": int AST_type = (int)((unsigned int)P&(((unsigned int)AST_type_mask)<<(unsigned int)AST_type_shift)); int AST_index = P&AST_idx_mask; int op = AST(AST_index+1); int alt = AST(AST_index+2); int count = AST(AST_index+3); if (AST_type == AST_PHRASE) { // DEBUG CHANGED AST_PHRASE TO PHRASE_TYPE switch (op) { // These are the only ones we're really interested in... case AST_boolean: // << source_text: true || false || undef , literal integer: 1 || 0 || -1>> case AST_number: // << source_text: number >> (could be integer or float) case AST_name: // << source_text: name >> case AST_value: // <> (determine which from type code of child) sprint_csg_inner(target+strlen(target), P_P(P,1)); break; case AST_list: // << list head >> sprintf(target+strlen(target), "["); sprint_csg_inner(target+strlen(target), P_P(P,1)); sprintf(target+strlen(target), "]"); break; case AST_list_element: // << value, next_value >> sprint_csg_inner(target+strlen(target), P_P(P,1)); if (P_P(P,2) != -1) { sprintf(target+strlen(target), ", "); sprint_csg_inner(target+strlen(target), P_P(P,2)); } break; case AST_argument: // << name, value, next_arg >> if (P_P(P,1) != -1) { sprint_csg_inner(target+strlen(target), P_P(P,1)); sprintf(target+strlen(target), " = "); } sprint_csg_inner(target+strlen(target), P_P(P,2)); if (P_P(P,3) != -1) { sprintf(target+strlen(target), ", ");sprint_csg_inner(target+strlen(target), P_P(P,3)); } break; case AST_source_text: // <> sprint_csg_inner(target+strlen(target), P_P(P,1)); sprint_csg_inner(target+strlen(target), P_P(P,2)); break; case AST_poolstring: // <> sprintf(target+strlen(target), "%s", pool_to_str(P_P(P, 1))); break; default: // Use the default output code: for (int i = 1; i <= count; i++) sprint_csg_inner(target+strlen(target), SubPhraseIdx(P,i)); } } else if (AST_type == AST_ATOM_LIT/*ERAL*/) { for (int i = atom(AST_index).start; i < atom(AST_index).end; i++) sprintf(target+strlen(target), "%lc", source(i).ch); } } void sprint_csg(char *target, int P) { *target = '\0'; sprint_csg_inner(target, P); } int CompareAtom(char *s, int Literal) { static char t[128]; sprint_csg(t, Literal); return strcmp(s, t) == 0; } int single_item(int P) { if (P == -1) return FALSE; // avoid runtime error of "left shift of 15 by 28 places": int AST_type = (int)((unsigned int)P&(((unsigned int)AST_type_mask)<<(unsigned int)AST_type_shift)); int AST_index = P&AST_idx_mask; int op = AST(AST_index+1); if (AST_type == AST_PHRASE) { if (op == AST_instruction) { int name, args, block, next; AST_detuple(P, AST_instruction, &name, &args, &block, &next); if (next == -1) { return TRUE; } } } return FALSE; } // walk_csg does a tree walk of the parse tree and outputs the source text. // Rather than mix optimisations with the display code, we pre-process the // tree to optimise it and then pass that result to walk_csg. int optimised_csg(int P, int depth) { // modify the AST to remove redundant nodes. Links to unoptimised nodes are replaced by links to optimised nodes. if (P == -1) return P; // avoid runtime error of "left shift of 15 by 28 places": int AST_type = (int)((unsigned int)P&(((unsigned int)AST_type_mask)<<(unsigned int)AST_type_shift)); int AST_index = P&AST_idx_mask; int op = AST(AST_index+1); int alt = AST(AST_index+2); int count = AST(AST_index+3); if (AST_type == AST_PHRASE) { // DEBUG CHANGED AST_PHRASE TO PHRASE_TYPE switch (op) { case AST_instruction: // <> is the only type of item that will be optimised { int name, args, unoptimised_block, unoptimised_next; AST_detuple(P, AST_instruction, &name, &args, &unoptimised_block, &unoptimised_next); // optimise following nodes at this level first: if (// 2D primitives that do not contain a sub-block CompareAtom("polygon", name) || CompareAtom("circle", name) || CompareAtom("square", name) || CompareAtom("text", name) || CompareAtom("import", name) || CompareAtom("surface", name) || // 3D primitives that do not contain a sub-block CompareAtom("polyhedron", name) || CompareAtom("cube", name) || CompareAtom("cylinder", name) || CompareAtom("sphere", name)) { if (unoptimised_block != -1) { char atom[128]; sprint_csg(atom, name); fprintf(stderr, "? Warning: %s has an unexpected block attached to it!\n", atom); } return AST_mktuple(AST_instruction, name, args, -1, optimised_csg(unoptimised_next, depth)); // return with optimised 'next' contents only } if (CompareAtom("intersection", name)) { if (unoptimised_block == -1) return optimised_csg(unoptimised_next, depth); // empty. // first we get the block and then we iterate through the objects in that block looking for empty // sub-blocks. If there are any, the whole intersection returns empty. int item_in_intersection_block = unoptimised_block; do { int sub_name, sub_args, sub_block, sub_next; AST_detuple(item_in_intersection_block, AST_instruction, &sub_name, &sub_args, &sub_block, &sub_next); int optimised_sub_block = optimised_csg(sub_block, depth+1); if (optimised_sub_block == -1) { //fprintf(stderr, "! DEBUG: One of the block items in an intersection is empty so the whole intersection is empty\n"); return optimised_csg(unoptimised_next, depth); } item_in_intersection_block = sub_next; } while (item_in_intersection_block != -1); // There were no empty blocks, so perform the recursive optimisation of the block... return AST_mktuple(AST_instruction, name, args, optimised_csg(unoptimised_block, depth), optimised_csg(unoptimised_next, depth)); // return with optimised block & next contents } else if (CompareAtom("difference", name)) { if (unoptimised_block == -1) return optimised_csg(unoptimised_next, depth); // empty difference block int first_difference_block_name, first_difference_block_args, first_difference_block_block, first_difference_block_next; AST_detuple(unoptimised_block, AST_instruction, &first_difference_block_name, &first_difference_block_args, &first_difference_block_block, &first_difference_block_next); // If there is only one item in the sub-block, promote it to this level: if (/*single_item(unoptimised_block)*/first_difference_block_next == -1) { //fprintf(stderr, "! DEBUG: only one item in this difference block - replacing the difference block with that item...\n"); return AST_mktuple(AST_instruction, first_difference_block_name, first_difference_block_args, optimised_csg(first_difference_block_block, depth), optimised_csg(unoptimised_next, depth)); // return the block but with the 'next' that followed 'difference'... } else { // A normal block with multiple items. Optimise the contents of that block before returning the optimised difference block. return AST_mktuple(AST_instruction, name, args, optimised_csg(unoptimised_block, depth), optimised_csg(unoptimised_next, depth)); // return 'difference' block with contents and 'next' already optimised. } } // container nodes must have their contents recursively optimised before they can be optimised themselves. // remaining block types are not sensitive to contents of first item like the ones above, so it should be // safe at this point to optimise the entire block at this point: int block, next; block = optimised_csg(unoptimised_block, depth); next = optimised_csg(unoptimised_next, depth); // (deprecated modules 'glide' and 'subdiv' are not implemented.) // These operations all require an attached block parameter, and they can // be entirely removed if there is no sub-block remaining after optimizing. if (CompareAtom("render", name) || CompareAtom("color", name) || CompareAtom("resize", name) || CompareAtom("offset", name) || CompareAtom("minkowski", name) || CompareAtom("hull", name) || CompareAtom("projection", name) || CompareAtom("linear_extrude", name) || CompareAtom("rotate_extrude", name)){ if (block == -1) return next; // no sub-block. return AST_mktuple(AST_instruction, name, args, block, next); // return with optimised block & next contents } else if (CompareAtom("multmatrix", name)) { if (block == -1) return next; // no sub-block. // If the block from a multmatrix() call only contains another multmatrix() block, then // multiply the two matrices together and return that node (and its children) instead. if (single_item(block)) { int block_name, block_args, block_block, block_next; AST_detuple(block, AST_instruction, &block_name, &block_args, &block_block, &block_next); if (block_next != -1) { fprintf(stderr, "? Warning #2: block_next != -1\n"); } if (CompareAtom("multmatrix", block_name)) { char M1[512], M2[512]; int rc; Mat4x4 m1, m2, mult; float a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p; sprint_csg(M1, args); rc = sscanf(M1, "[ [ %f, %f, %f, %f], [ %f, %f, %f, %f], [ %f, %f, %f, %f], [ %f, %f, %f, %f] ]", &a, &b, &c, &d, &e, &f, &g, &h, &i, &j, &k, &l, &m, &n, &o, &p); if (rc != 16) { fprintf(stderr, "? Warning #1: scan of matrix '%s' returned %d items\n", M1, rc); } load_matrix(m1, a,b,c,d, e,f,g,h, i,j,k,l, m,n,o,p); sprint_csg(M2, block_args); rc = sscanf(M2, "[ [ %f, %f, %f, %f], [ %f, %f, %f, %f], [ %f, %f, %f, %f], [ %f, %f, %f, %f] ]", &a, &b, &c, &d, &e, &f, &g, &h, &i, &j, &k, &l, &m, &n, &o, &p); if (rc != 16) { fprintf(stderr, "? Warning #2: scan of matrix '%s' returned %d items\n", M2, rc); } load_matrix(m2, a,b,c,d, e,f,g,h, i,j,k,l, m,n,o,p); mat4x4_mul(mult, m1, m2); // fprintf(stdout, "/* Replace %s * %s by ", M1, M2); print_matrix(mult, ", "); fprintf(stdout, " */\n"); // Construct new node! Use 'next' from parent. Replace 'args' char mults[512]; sprint_matrix(mults, mult, ", "); int replacement_args = AST_mktuple(AST_poolstring, str_to_pool(mults)); return AST_mktuple(AST_instruction, block_name, replacement_args, block_block, next); } } return AST_mktuple(AST_instruction, name, args, block, next); // return with optimised block & next contents } else if (CompareAtom("group", name) || CompareAtom("union", name)) { if (block == -1) return next; // if contents of block are empty, this node is redundant. if (single_item(block)) { // now check for promotion of contents int block_name, block_args, block_block, block_next; AST_detuple(block, AST_instruction, &block_name, &block_args, &block_block, &block_next); if (block_next != -1) { fprintf(stderr, "? Warning #3: block_next != -1\n"); } return AST_mktuple(AST_instruction, block_name, block_args, block_block, next); } return AST_mktuple(AST_instruction, name, args, block, next); } else { char culprit[128]; sprint_csg(culprit, name); fprintf(stderr, "* Unknown object type '%s' in csg file\n", culprit); return P; // stop optimising here. Safer than passing back optimised contents with: // AST_mktuple(AST_instruction, name, args, block, next); } fprintf(stderr, "* Internal error: should not get here.\n"); exit(EXIT_FAILURE);// return P; } default: } } return P; // everything else is passed through as before. } void walk_csg_inner(int P, int depth) { if (P == -1) return; // avoid runtime error of "left shift of 15 by 28 places": int AST_type = (int)((unsigned int)P&(((unsigned int)AST_type_mask)<<(unsigned int)AST_type_shift)); int AST_index = P&AST_idx_mask; int op = AST(AST_index+1); int alt = AST(AST_index+2); int count = AST(AST_index+3); fflush(stdout); if (AST_type == AST_PHRASE) { // DEBUG CHANGED AST_PHRASE TO PHRASE_TYPE switch (op) { case AST_instruction: // <> { int name, args, block, next; AST_detuple(P, AST_instruction, &name, &args, &block, &next); if (// 2D primitives that do not take a block parameter CompareAtom("polygon", name) || CompareAtom("circle", name) || CompareAtom("square", name) || CompareAtom("text", name) || CompareAtom("import", name) || CompareAtom("surface", name) || // 3D primitives that do not take a block parameter CompareAtom("polyhedron", name) || CompareAtom("cube", name) || CompareAtom("cylinder", name) || CompareAtom("sphere", name)) { indent(depth); walk_csg_inner(name, depth); fprintf(stdout, " ("); walk_csg_inner(args, depth); fprintf(stdout, ")"); fprintf(stdout, ";\n"); } else { indent(depth); walk_csg_inner(name, depth); fprintf(stdout, " ("); walk_csg_inner(args, depth); fprintf(stdout, ")"); fprintf(stdout, " {"); if (block != -1) { fprintf(stdout, "\n"); walk_csg_inner(block, depth+1); indent(depth); } fprintf(stdout, "}\n"); } if (next != -1) walk_csg_inner(next, depth); break; } case AST_string: // << source_text: string >> fprintf(stdout, "\""); // TO DO: don't remove leading spaces from components of string. walk_csg_inner(P_P(P,1),depth); fprintf(stdout, "\""); break; case AST_boolean: // << source_text: true || false || undef , literal integer: 1 || 0 || -1>> case AST_number: // << source_text: number >> (could be integer or float) case AST_name: // << source_text: name >> case AST_value: // <> (determine which from type code of child) walk_csg_inner(P_P(P,1),depth); break; case AST_list: // << list head >> fprintf(stdout, "["); walk_csg_inner(P_P(P,1),depth); fprintf(stdout, "]"); break; case AST_list_element: // << value, next_value >> walk_csg_inner(P_P(P,1),depth); if (P_P(P,2) != -1) { fprintf(stdout, ", "); walk_csg_inner(P_P(P,2),depth); } break; case AST_argument: // << name, value, next_arg >> if (P_P(P,1) != -1) { walk_csg_inner(P_P(P,1),depth); fprintf(stdout, " = "); } walk_csg_inner(P_P(P,2),depth); if (P_P(P,3) != -1) { fprintf(stdout, ", ");walk_csg_inner(P_P(P,3),depth); } break; case AST_source_text: // <> walk_csg_inner(P_P(P,1),depth); walk_csg_inner(P_P(P,2),depth); break; case AST_poolstring: // <> fprintf(stdout, "%s", pool_to_str(P_P(P, 1))); break; default: // Use the default output code: for (int i = 1; i <= count; i++) walk_csg_inner(SubPhraseIdx(P,i), depth+1); } } else if (AST_type == AST_ATOM_LIT/*ERAL*/) { // Warning: BIPs might not have AST_BIP embedded in their results for P_mktuple() //PrintAtom(AST_index); // suppress leading spaces. TO DO: Be careful when it's a string constant being output. int i = atom(AST_index).start; for (;;) { if (i >= atom(AST_index).end) break; if (source(i).ch != ' ') break; i += 1; } for (;;) { if (i >= atom(AST_index).end) break; fprintf(stdout, "%lc", source(i).ch); i += 1; } } fflush(stdout); } void walk_csg(int P, int depth) { walk_csg_inner(optimised_csg(P, depth), depth); // Optimise the parse tree before walking it to output the source text. } #endif //INITCODE // B = 0; // E #endif // SUPPRESS_DATA #endif // _GRAMMAR_H_