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