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