1 #ifndef SWITCH_H__ 2 #define SWITCH_H__ 1 3 4 /*--------------------------------------------------------------------------- 5 * Data structures used mainly by the switch code generation. 6 * 7 *--------------------------------------------------------------------------- 8 * The switch() instruction is implemented using a highly efficient table 9 * lookup system. The code for the instruction is generated in two places 10 * (LPC compiler and lambda compiler), therefore some of the 'internal' 11 * datastructures need to be published here. 12 * 13 * The compiler makes sure that there is always a 'default' case 14 * and that all execution paths eventually execute a F_BREAK. 15 * 16 * The layout created by the LPC compiler is this: 17 * 18 * switch b1 a2 b2 [b3 [b4] ] 19 * instructions (sans the first byte 'i0')... 20 * l[] 21 * [c0 [c1]] 22 * a0 a1 i0 23 * v*n 24 * o*n 25 * [d0] 26 * 27 * b1 & 0x03 is 0, marking this switch statement as unaligned. 28 * Since for an efficient search the tables v*n and o*n must be 29 * 4-Byte aligned (TODO: on some machines 8-Byte), the interpreter 30 * will on first execution of such a switch align it (using 31 * closure:align_switch()) by arranging the bytes a0..a2 around 32 * the tables. The alignment can't be done at compilation time, 33 * because code generated after the switch may cause to move 34 * the switch code back- or forward. The aligned layout is this: 35 * 36 * switch b1 b2 [b3 [b4] ] 37 * instructions... 38 * l[] 39 * [c0 [c1]] <-- p0 = pc + offset 40 * a0.. 41 * v[] <-- tabstart 42 * o[] <-- end_tab = pc + offset + tablen 43 * ..a2 <-- p1 44 * [d0] 45 * 46 * b1 (bits 1..0) = len: the length in bytes needed to store 47 * 'offset', 'tablen', 'default offset', 'o*n' and the 48 * length of lookup tables for table ranges. 49 * b1 (bits 7..2) = tablen lo 50 * c0 = tablen mid (optional) 51 * c1 = tablen hi (optional) 52 * b2 = offset lo 53 * b3 = offset med (optional) 54 * b4 = offset hi (optional) 55 * a0, a1 = default-case offset lo and med in host byte order 56 * d0 = default-case offset hi (optional) 57 * a2 'type' (bits 0..4): start position for search (used to index 58 * a table with the real offsets) 59 * (bit 5) : 0: numeric switch , 1: string switch 60 * (bits 6..7): in an unaligned switch, the true value 61 * of <len> (b1, bits 1..0). 62 * l[]: range lookup table: each <len> bytes, network byte order 63 * (numeric switch only) 64 * v[]: case values, char* or p_int, host byte order 65 * o[]: case offsets : each <len> bytes, network byte order 66 * 67 * The case value table v[] holds (sorted numerically) all values 68 * appearing in the case statements, both singular values and range 69 * bounds. Range bound values (which are inclusive) always appear 70 * next to each other. 71 * 72 * The offset table o[] holds the associated offset with 73 * this interpretation: 74 * 75 * singular cases: jump destination offsets relative to pc. 76 * 77 * range cases: the 'offset' for the lower bound is 1, the 78 * offset for the upper bound gives the jump 79 * destination relative to pc. 80 * 81 * lookup ranges: the 'offset' for the lower bound is 0, the 82 * offset for the upper bound is an offset 83 * pointing into the lookup table. 84 * The real jump offset is then 85 * l[o[i] + <value> - lower-bound]. 86 * 87 * The lookup ranges are used for an efficient implementation of 88 * sparse ranges like 'case 0: case 2: case 5: ...'. 89 *--------------------------------------------------------------------------- 90 */ 91 92 #define ZERO_AS_STR_CASE_LABEL ((char *)&main) 93 /* This value is used to compile 'case 0' into switch on string types. 94 * We can't use the NULL pointer for this purpose, which is used when 95 * looking up a string that is not in the tabled string table and 96 * therefore must not be found. 97 * This value must not be misinterpreted as tabled string. 98 * If the string handling is changed, this value must be adapted. 99 */ 100 101 #define CASE_BLOCKING_FACTOR 256 /* must be >= 2 */ 102 /* case_list_entry_t's are allocated in blocks of this count. 103 */ 104 105 /* Bitmasks and -values for selected bytes in the switch statement: 106 */ 107 108 /* The B1 byte: */ 109 110 #define SWITCH_VALUELEN 0x03 /* Bitmask */ 111 /* The length in bytes needed to store 'offset', 'tablen', 112 * 'default offset', 'o*n' and the length of lookup tables for table 113 * ranges. 114 * If the value is 0, the switch is unaligned and the value is stored 115 * in SWITCH_TYPE_VALUELEN. 116 */ 117 118 #define SWITCH_TABLEN 0xfc /* Bitmask */ 119 #define SWITCH_TABLEN_SHIFT 2 /* Leftshift */ 120 /* The low bits of the table length. 121 */ 122 123 /* The TYPE byte: */ 124 125 #define SWITCH_START 0x1f /* Bitmask */ 126 /* Start position for search (used to index a table with the real offsets). 127 */ 128 129 #define SWITCH_TYPE 0x20 /* Bitflag */ 130 /* Flag: 0: numeric switch , 1: string switch 131 */ 132 133 #define SWITCH_TYPE_VALUELEN 0xc0 /* Bitmask */ 134 #define SWITCH_TYPE_VALUELEN_SHIFT 6 /* Leftshift */ 135 /* In an unaligned switch, the true value of SWITCH_VALUELEN. 136 */ 137 138 /* --- case_list_entry_t: description of one case value --- 139 */ 140 struct case_list_entry_s 141 { 142 case_list_entry_t *next; 143 p_int key; /* Numeric case value, or a shared string casted */ 144 p_int addr; 145 /* Offset of the associated code from the SWITCH+1. 146 * If 1: this and the next entry denote a range. 147 * If 0: this and the next entry denote a sparse lookup range. 148 * TODO: Make this selfcontained? 149 */ 150 p_int line; 151 /* Line number of the case. It's 0 for range ends. 152 */ 153 }; 154 155 /* --- case_state_t: compilation state of one switch() --- 156 */ 157 158 struct case_state_s 159 { 160 case_list_entry_t *free_block; 161 /* Currently used allocation block in the case_blocks list. 162 */ 163 case_list_entry_t *next_free; 164 /* First used entry in .free_block. The blocks are used 165 * from the end, and the first cl_entry is reserved to link 166 * the block list. 167 */ 168 case_list_entry_t *list0; 169 case_list_entry_t *list1; 170 /* Head and second element of the active case list. 171 * Both elements are in direct access to handle ranges (which are 172 * encoded using two entries). 173 */ 174 case_list_entry_t *zero; 175 case_state_t *previous; 176 /* The case_state of the surrounding switch(), when compiling 177 * a nested switch(). 178 */ 179 p_int default_addr; 180 char some_numeric_labels; 181 char no_string_labels; 182 }; 183 184 /* --- Variables (in closure.c) --- */ 185 extern case_state_t case_state; 186 187 /* TODO: Move all these functions, a generic code generator 188 * TODO:: and the execution function in its own file. 189 * Nice would be an oo approach using a opaque type and the 190 * functions: init(), add_case(), add_range(), generate(). 191 * An OO approach would also easily solve the problem that sequential 192 * top-level switch()s accumulate in their memory usage. 193 */ 194 195 /* --- Prototypes (in closure.c) --- */ 196 extern case_list_entry_t *new_case_entry(void); 197 extern void free_case_blocks(void); 198 extern void store_case_labels( p_int total_length 199 , p_int default_addr 200 , Bool numeric 201 , case_list_entry_t *zero 202 , bytecode_p (*get_space)(p_int) 203 , void (*move_instructions)(int, p_int) 204 , void (*cerror)(const char *) 205 , void (*cerrorl)(const char *, const char*, int, int) 206 ); 207 208 #endif /* SWITCH_H__ */ 209