1 /* $OpenBSD: tables.c,v 1.3 2015/12/11 00:08:43 mmcc Exp $ */ 2 3 /* tables.c - tables serialization code 4 * 5 * Copyright (c) 1990 The Regents of the University of California. 6 * All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Vern Paxson. 10 * 11 * The United States Government has rights in this work pursuant 12 * to contract no. DE-AC03-76SF00098 between the United States 13 * Department of Energy and the University of California. 14 * 15 * This file is part of flex. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 21 * 1. Redistributions of source code must retain the above copyright 22 * notice, this list of conditions and the following disclaimer. 23 * 2. Redistributions in binary form must reproduce the above copyright 24 * notice, this list of conditions and the following disclaimer in the 25 * documentation and/or other materials provided with the distribution. 26 * 27 * Neither the name of the University nor the names of its contributors 28 * may be used to endorse or promote products derived from this software 29 * without specific prior written permission. 30 * 31 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 32 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 33 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 34 * PURPOSE. 35 */ 36 37 38 #include "flexdef.h" 39 #include "tables.h" 40 41 /** Convert size_t to t_flag. 42 * @param n in {1,2,4} 43 * @return YYTD_DATA*. 44 */ 45 #define BYTES2TFLAG(n)\ 46 (((n) == sizeof(flex_int8_t))\ 47 ? YYTD_DATA8\ 48 :(((n)== sizeof(flex_int16_t))\ 49 ? YYTD_DATA16\ 50 : YYTD_DATA32)) 51 52 /** Clear YYTD_DATA* bit flags 53 * @return the flag with the YYTD_DATA* bits cleared 54 */ 55 #define TFLAGS_CLRDATA(flg) ((flg) & ~(YYTD_DATA8 | YYTD_DATA16 | YYTD_DATA32)) 56 57 int yytbl_write32 (struct yytbl_writer *wr, flex_uint32_t v); 58 int yytbl_write16 (struct yytbl_writer *wr, flex_uint16_t v); 59 int yytbl_write8 (struct yytbl_writer *wr, flex_uint8_t v); 60 int yytbl_writen (struct yytbl_writer *wr, void *v, flex_int32_t len); 61 static flex_int32_t yytbl_data_geti (const struct yytbl_data *tbl, int i); 62 /* XXX Not used 63 static flex_int32_t yytbl_data_getijk (const struct yytbl_data *tbl, int i, 64 int j, int k); 65 */ 66 67 68 /** Initialize the table writer. 69 * @param wr an uninitialized writer 70 * @param the output file 71 * @return 0 on success 72 */ 73 int yytbl_writer_init (struct yytbl_writer *wr, FILE * out) 74 { 75 wr->out = out; 76 wr->total_written = 0; 77 return 0; 78 } 79 80 /** Initialize a table header. 81 * @param th The uninitialized structure 82 * @param version_str the version string 83 * @param name the name of this table set 84 */ 85 int yytbl_hdr_init (struct yytbl_hdr *th, const char *version_str, 86 const char *name) 87 { 88 memset (th, 0, sizeof (struct yytbl_hdr)); 89 90 th->th_magic = YYTBL_MAGIC; 91 th->th_hsize = 14 + strlen (version_str) + 1 + strlen (name) + 1; 92 th->th_hsize += yypad64 (th->th_hsize); 93 th->th_ssize = 0; // Not known at this point. 94 th->th_flags = 0; 95 th->th_version = copy_string (version_str); 96 th->th_name = copy_string (name); 97 return 0; 98 } 99 100 /** Allocate and initialize a table data structure. 101 * @param tbl a pointer to an uninitialized table 102 * @param id the table identifier 103 * @return 0 on success 104 */ 105 int yytbl_data_init (struct yytbl_data *td, enum yytbl_id id) 106 { 107 108 memset (td, 0, sizeof (struct yytbl_data)); 109 td->td_id = id; 110 td->td_flags = YYTD_DATA32; 111 return 0; 112 } 113 114 /** Clean up table and data array. 115 * @param td will be destroyed 116 * @return 0 on success 117 */ 118 int yytbl_data_destroy (struct yytbl_data *td) 119 { 120 free(td->td_data); 121 td->td_data = 0; 122 free (td); 123 return 0; 124 } 125 126 /** Write enough padding to bring the file pointer to a 64-bit boundary. */ 127 static int yytbl_write_pad64 (struct yytbl_writer *wr) 128 { 129 int pad, bwritten = 0; 130 131 pad = yypad64 (wr->total_written); 132 while (pad-- > 0) 133 if (yytbl_write8 (wr, 0) < 0) 134 return -1; 135 else 136 bwritten++; 137 return bwritten; 138 } 139 140 /** write the header. 141 * @param out the output stream 142 * @param th table header to be written 143 * @return -1 on error, or bytes written on success. 144 */ 145 int yytbl_hdr_fwrite (struct yytbl_writer *wr, const struct yytbl_hdr *th) 146 { 147 int sz, rv; 148 int bwritten = 0; 149 150 if (yytbl_write32 (wr, th->th_magic) < 0 151 || yytbl_write32 (wr, th->th_hsize) < 0) 152 flex_die (_("th_magic|th_hsize write32 failed")); 153 bwritten += 8; 154 155 if (fgetpos (wr->out, &(wr->th_ssize_pos)) != 0) 156 flex_die (_("fgetpos failed")); 157 158 if (yytbl_write32 (wr, th->th_ssize) < 0 159 || yytbl_write16 (wr, th->th_flags) < 0) 160 flex_die (_("th_ssize|th_flags write failed")); 161 bwritten += 6; 162 163 sz = strlen (th->th_version) + 1; 164 if ((rv = yytbl_writen (wr, th->th_version, sz)) != sz) 165 flex_die (_("th_version writen failed")); 166 bwritten += rv; 167 168 sz = strlen (th->th_name) + 1; 169 if ((rv = yytbl_writen (wr, th->th_name, sz)) != sz) 170 flex_die (_("th_name writen failed")); 171 bwritten += rv; 172 173 /* add padding */ 174 if ((rv = yytbl_write_pad64 (wr)) < 0) 175 flex_die (_("pad64 failed")); 176 bwritten += rv; 177 178 /* Sanity check */ 179 if (bwritten != (int) th->th_hsize) 180 flex_die (_("pad64 failed")); 181 182 return bwritten; 183 } 184 185 186 /** Write this table. 187 * @param out the file writer 188 * @param td table data to be written 189 * @return -1 on error, or bytes written on success. 190 */ 191 int yytbl_data_fwrite (struct yytbl_writer *wr, struct yytbl_data *td) 192 { 193 int rv; 194 flex_int32_t bwritten = 0; 195 flex_int32_t i, total_len; 196 fpos_t pos; 197 198 if ((rv = yytbl_write16 (wr, td->td_id)) < 0) 199 return -1; 200 bwritten += rv; 201 202 if ((rv = yytbl_write16 (wr, td->td_flags)) < 0) 203 return -1; 204 bwritten += rv; 205 206 if ((rv = yytbl_write32 (wr, td->td_hilen)) < 0) 207 return -1; 208 bwritten += rv; 209 210 if ((rv = yytbl_write32 (wr, td->td_lolen)) < 0) 211 return -1; 212 bwritten += rv; 213 214 total_len = yytbl_calc_total_len (td); 215 for (i = 0; i < total_len; i++) { 216 switch (YYTDFLAGS2BYTES (td->td_flags)) { 217 case sizeof (flex_int8_t): 218 rv = yytbl_write8 (wr, yytbl_data_geti (td, i)); 219 break; 220 case sizeof (flex_int16_t): 221 rv = yytbl_write16 (wr, yytbl_data_geti (td, i)); 222 break; 223 case sizeof (flex_int32_t): 224 rv = yytbl_write32 (wr, yytbl_data_geti (td, i)); 225 break; 226 default: 227 flex_die (_("invalid td_flags detected")); 228 } 229 if (rv < 0) { 230 flex_die (_("error while writing tables")); 231 return -1; 232 } 233 bwritten += rv; 234 } 235 236 /* Sanity check */ 237 if (bwritten != (int) (12 + total_len * YYTDFLAGS2BYTES (td->td_flags))) { 238 flex_die (_("insanity detected")); 239 return -1; 240 } 241 242 /* add padding */ 243 if ((rv = yytbl_write_pad64 (wr)) < 0) { 244 flex_die (_("pad64 failed")); 245 return -1; 246 } 247 bwritten += rv; 248 249 /* Now go back and update the th_hsize member */ 250 if (fgetpos (wr->out, &pos) != 0 251 || fsetpos (wr->out, &(wr->th_ssize_pos)) != 0 252 || yytbl_write32 (wr, wr->total_written) < 0 253 || fsetpos (wr->out, &pos)) { 254 flex_die (_("get|set|fwrite32 failed")); 255 return -1; 256 } 257 else 258 /* Don't count the int we just wrote. */ 259 wr->total_written -= sizeof (flex_int32_t); 260 return bwritten; 261 } 262 263 /** Write n bytes. 264 * @param wr the table writer 265 * @param v data to be written 266 * @param len number of bytes 267 * @return -1 on error. number of bytes written on success. 268 */ 269 int yytbl_writen (struct yytbl_writer *wr, void *v, flex_int32_t len) 270 { 271 int rv; 272 273 rv = fwrite (v, 1, len, wr->out); 274 if (rv != len) 275 return -1; 276 wr->total_written += len; 277 return len; 278 } 279 280 /** Write four bytes in network byte order 281 * @param wr the table writer 282 * @param v a dword in host byte order 283 * @return -1 on error. number of bytes written on success. 284 */ 285 int yytbl_write32 (struct yytbl_writer *wr, flex_uint32_t v) 286 { 287 flex_uint32_t vnet; 288 size_t bytes, rv; 289 290 vnet = htonl (v); 291 bytes = sizeof (flex_uint32_t); 292 rv = fwrite (&vnet, bytes, 1, wr->out); 293 if (rv != 1) 294 return -1; 295 wr->total_written += bytes; 296 return bytes; 297 } 298 299 /** Write two bytes in network byte order. 300 * @param wr the table writer 301 * @param v a word in host byte order 302 * @return -1 on error. number of bytes written on success. 303 */ 304 int yytbl_write16 (struct yytbl_writer *wr, flex_uint16_t v) 305 { 306 flex_uint16_t vnet; 307 size_t bytes, rv; 308 309 vnet = htons (v); 310 bytes = sizeof (flex_uint16_t); 311 rv = fwrite (&vnet, bytes, 1, wr->out); 312 if (rv != 1) 313 return -1; 314 wr->total_written += bytes; 315 return bytes; 316 } 317 318 /** Write a byte. 319 * @param wr the table writer 320 * @param v the value to be written 321 * @return -1 on error. number of bytes written on success. 322 */ 323 int yytbl_write8 (struct yytbl_writer *wr, flex_uint8_t v) 324 { 325 size_t bytes, rv; 326 327 bytes = sizeof (flex_uint8_t); 328 rv = fwrite (&v, bytes, 1, wr->out); 329 if (rv != 1) 330 return -1; 331 wr->total_written += bytes; 332 return bytes; 333 } 334 335 336 /* XXX Not Used */ 337 #if 0 338 /** Extract data element [i][j] from array data tables. 339 * @param tbl data table 340 * @param i index into higher dimension array. i should be zero for one-dimensional arrays. 341 * @param j index into lower dimension array. 342 * @param k index into struct, must be 0 or 1. Only valid for YYTD_ID_TRANSITION table 343 * @return data[i][j + k] 344 */ 345 static flex_int32_t yytbl_data_getijk (const struct yytbl_data *tbl, int i, 346 int j, int k) 347 { 348 flex_int32_t lo; 349 350 k %= 2; 351 lo = tbl->td_lolen; 352 353 switch (YYTDFLAGS2BYTES (tbl->td_flags)) { 354 case sizeof (flex_int8_t): 355 return ((flex_int8_t *) (tbl->td_data))[(i * lo + j) * (k + 1) + 356 k]; 357 case sizeof (flex_int16_t): 358 return ((flex_int16_t *) (tbl->td_data))[(i * lo + j) * (k + 359 1) + 360 k]; 361 case sizeof (flex_int32_t): 362 return ((flex_int32_t *) (tbl->td_data))[(i * lo + j) * (k + 363 1) + 364 k]; 365 default: 366 flex_die (_("invalid td_flags detected")); 367 break; 368 } 369 370 return 0; 371 } 372 #endif /* Not used */ 373 374 /** Extract data element [i] from array data tables treated as a single flat array of integers. 375 * Be careful for 2-dimensional arrays or for YYTD_ID_TRANSITION, which is an array 376 * of structs. 377 * @param tbl data table 378 * @param i index into array. 379 * @return data[i] 380 */ 381 static flex_int32_t yytbl_data_geti (const struct yytbl_data *tbl, int i) 382 { 383 384 switch (YYTDFLAGS2BYTES (tbl->td_flags)) { 385 case sizeof (flex_int8_t): 386 return ((flex_int8_t *) (tbl->td_data))[i]; 387 case sizeof (flex_int16_t): 388 return ((flex_int16_t *) (tbl->td_data))[i]; 389 case sizeof (flex_int32_t): 390 return ((flex_int32_t *) (tbl->td_data))[i]; 391 default: 392 flex_die (_("invalid td_flags detected")); 393 break; 394 } 395 return 0; 396 } 397 398 /** Set data element [i] in array data tables treated as a single flat array of integers. 399 * Be careful for 2-dimensional arrays or for YYTD_ID_TRANSITION, which is an array 400 * of structs. 401 * @param tbl data table 402 * @param i index into array. 403 * @param newval new value for data[i] 404 */ 405 static void yytbl_data_seti (const struct yytbl_data *tbl, int i, 406 flex_int32_t newval) 407 { 408 409 switch (YYTDFLAGS2BYTES (tbl->td_flags)) { 410 case sizeof (flex_int8_t): 411 ((flex_int8_t *) (tbl->td_data))[i] = (flex_int8_t) newval; 412 break; 413 case sizeof (flex_int16_t): 414 ((flex_int16_t *) (tbl->td_data))[i] = (flex_int16_t) newval; 415 break; 416 case sizeof (flex_int32_t): 417 ((flex_int32_t *) (tbl->td_data))[i] = (flex_int32_t) newval; 418 break; 419 default: 420 flex_die (_("invalid td_flags detected")); 421 break; 422 } 423 } 424 425 /** Calculate the number of bytes needed to hold the largest 426 * absolute value in this data array. 427 * @param tbl the data table 428 * @return sizeof(n) where n in {flex_int8_t, flex_int16_t, flex_int32_t} 429 */ 430 static size_t min_int_size (struct yytbl_data *tbl) 431 { 432 flex_uint32_t i, total_len; 433 flex_int32_t max = 0; 434 435 total_len = yytbl_calc_total_len (tbl); 436 437 for (i = 0; i < total_len; i++) { 438 flex_int32_t n; 439 440 n = abs (yytbl_data_geti (tbl, i)); 441 442 if (n > max) 443 max = n; 444 } 445 446 if (max <= INT8_MAX) 447 return sizeof (flex_int8_t); 448 else if (max <= INT16_MAX) 449 return sizeof (flex_int16_t); 450 else 451 return sizeof (flex_int32_t); 452 } 453 454 /** Transform data to smallest possible of (int32, int16, int8). 455 * For example, we may have generated an int32 array due to user options 456 * (e.g., %option align), but if the maximum value in that array 457 * is 80 (for example), then we can serialize it with only 1 byte per int. 458 * This is NOT the same as compressed DFA tables. We're just trying 459 * to save storage space here. 460 * 461 * @param tbl the table to be compressed 462 */ 463 void yytbl_data_compress (struct yytbl_data *tbl) 464 { 465 flex_int32_t i, newsz, total_len; 466 struct yytbl_data newtbl; 467 468 yytbl_data_init (&newtbl, tbl->td_id); 469 newtbl.td_hilen = tbl->td_hilen; 470 newtbl.td_lolen = tbl->td_lolen; 471 newtbl.td_flags = tbl->td_flags; 472 473 newsz = min_int_size (tbl); 474 475 476 if (newsz == (int) YYTDFLAGS2BYTES (tbl->td_flags)) 477 /* No change in this table needed. */ 478 return; 479 480 if (newsz > (int) YYTDFLAGS2BYTES (tbl->td_flags)) { 481 flex_die (_("detected negative compression")); 482 return; 483 } 484 485 total_len = yytbl_calc_total_len (tbl); 486 newtbl.td_data = calloc (total_len, newsz); 487 newtbl.td_flags = 488 TFLAGS_CLRDATA (newtbl.td_flags) | BYTES2TFLAG (newsz); 489 490 for (i = 0; i < total_len; i++) { 491 flex_int32_t g; 492 493 g = yytbl_data_geti (tbl, i); 494 yytbl_data_seti (&newtbl, i, g); 495 } 496 497 498 /* Now copy over the old table */ 499 free (tbl->td_data); 500 *tbl = newtbl; 501 } 502