1 /* $NetBSD: tables.c,v 1.2 2016/01/09 17:38:57 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.2 2016/01/09 17:38:57 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, flex_int32_t 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 = 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 = copy_string (version_str); 97 th->th_name = copy_string (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 if (td->td_data) 122 free (td->td_data); 123 td->td_data = 0; 124 free (td); 125 return 0; 126 } 127 128 /** Write enough padding to bring the file pointer to a 64-bit boundary. */ 129 static int yytbl_write_pad64 (struct yytbl_writer *wr) 130 { 131 int pad, bwritten = 0; 132 133 pad = yypad64 (wr->total_written); 134 while (pad-- > 0) 135 if (yytbl_write8 (wr, 0) < 0) 136 return -1; 137 else 138 bwritten++; 139 return bwritten; 140 } 141 142 /** write the header. 143 * @param wr the output stream 144 * @param th table header to be written 145 * @return -1 on error, or bytes written on success. 146 */ 147 int yytbl_hdr_fwrite (struct yytbl_writer *wr, const struct yytbl_hdr *th) 148 { 149 int sz, rv; 150 int bwritten = 0; 151 152 if (yytbl_write32 (wr, th->th_magic) < 0 153 || yytbl_write32 (wr, th->th_hsize) < 0) 154 flex_die (_("th_magic|th_hsize write32 failed")); 155 bwritten += 8; 156 157 if (fgetpos (wr->out, &(wr->th_ssize_pos)) != 0) 158 flex_die (_("fgetpos failed")); 159 160 if (yytbl_write32 (wr, th->th_ssize) < 0 161 || yytbl_write16 (wr, th->th_flags) < 0) 162 flex_die (_("th_ssize|th_flags write failed")); 163 bwritten += 6; 164 165 sz = strlen (th->th_version) + 1; 166 if ((rv = yytbl_writen (wr, th->th_version, sz)) != sz) 167 flex_die (_("th_version writen failed")); 168 bwritten += rv; 169 170 sz = strlen (th->th_name) + 1; 171 if ((rv = yytbl_writen (wr, th->th_name, sz)) != sz) 172 flex_die (_("th_name writen failed")); 173 bwritten += rv; 174 175 /* add padding */ 176 if ((rv = yytbl_write_pad64 (wr)) < 0) 177 flex_die (_("pad64 failed")); 178 bwritten += rv; 179 180 /* Sanity check */ 181 if (bwritten != (int) th->th_hsize) 182 flex_die (_("pad64 failed")); 183 184 return bwritten; 185 } 186 187 188 /** Write this table. 189 * @param wr the file writer 190 * @param td table data to be written 191 * @return -1 on error, or bytes written on success. 192 */ 193 int yytbl_data_fwrite (struct yytbl_writer *wr, struct yytbl_data *td) 194 { 195 int rv; 196 flex_int32_t bwritten = 0; 197 flex_int32_t i, total_len; 198 fpos_t pos; 199 200 if ((rv = yytbl_write16 (wr, td->td_id)) < 0) 201 return -1; 202 bwritten += rv; 203 204 if ((rv = yytbl_write16 (wr, td->td_flags)) < 0) 205 return -1; 206 bwritten += rv; 207 208 if ((rv = yytbl_write32 (wr, td->td_hilen)) < 0) 209 return -1; 210 bwritten += rv; 211 212 if ((rv = yytbl_write32 (wr, td->td_lolen)) < 0) 213 return -1; 214 bwritten += rv; 215 216 total_len = yytbl_calc_total_len (td); 217 for (i = 0; i < total_len; i++) { 218 switch (YYTDFLAGS2BYTES (td->td_flags)) { 219 case sizeof (flex_int8_t): 220 rv = yytbl_write8 (wr, yytbl_data_geti (td, i)); 221 break; 222 case sizeof (flex_int16_t): 223 rv = yytbl_write16 (wr, yytbl_data_geti (td, i)); 224 break; 225 case sizeof (flex_int32_t): 226 rv = yytbl_write32 (wr, yytbl_data_geti (td, i)); 227 break; 228 default: 229 flex_die (_("invalid td_flags detected")); 230 } 231 if (rv < 0) { 232 flex_die (_("error while writing tables")); 233 return -1; 234 } 235 bwritten += rv; 236 } 237 238 /* Sanity check */ 239 if (bwritten != (int) (12 + total_len * YYTDFLAGS2BYTES (td->td_flags))) { 240 flex_die (_("insanity detected")); 241 return -1; 242 } 243 244 /* add padding */ 245 if ((rv = yytbl_write_pad64 (wr)) < 0) { 246 flex_die (_("pad64 failed")); 247 return -1; 248 } 249 bwritten += rv; 250 251 /* Now go back and update the th_hsize member */ 252 if (fgetpos (wr->out, &pos) != 0 253 || fsetpos (wr->out, &(wr->th_ssize_pos)) != 0 254 || yytbl_write32 (wr, wr->total_written) < 0 255 || fsetpos (wr->out, &pos)) { 256 flex_die (_("get|set|fwrite32 failed")); 257 return -1; 258 } 259 else 260 /* Don't count the int we just wrote. */ 261 wr->total_written -= sizeof (flex_int32_t); 262 return bwritten; 263 } 264 265 /** Write n bytes. 266 * @param wr the table writer 267 * @param v data to be written 268 * @param len number of bytes 269 * @return -1 on error. number of bytes written on success. 270 */ 271 int yytbl_writen (struct yytbl_writer *wr, void *v, flex_int32_t len) 272 { 273 int rv; 274 275 rv = fwrite (v, 1, len, wr->out); 276 if (rv != len) 277 return -1; 278 wr->total_written += len; 279 return len; 280 } 281 282 /** Write four bytes in network byte order 283 * @param wr the table writer 284 * @param v a dword in host byte order 285 * @return -1 on error. number of bytes written on success. 286 */ 287 int yytbl_write32 (struct yytbl_writer *wr, flex_uint32_t v) 288 { 289 flex_uint32_t vnet; 290 size_t bytes, rv; 291 292 vnet = htonl (v); 293 bytes = sizeof (flex_uint32_t); 294 rv = fwrite (&vnet, bytes, 1, wr->out); 295 if (rv != 1) 296 return -1; 297 wr->total_written += bytes; 298 return bytes; 299 } 300 301 /** Write two bytes in network byte order. 302 * @param wr the table writer 303 * @param v a word in host byte order 304 * @return -1 on error. number of bytes written on success. 305 */ 306 int yytbl_write16 (struct yytbl_writer *wr, flex_uint16_t v) 307 { 308 flex_uint16_t vnet; 309 size_t bytes, rv; 310 311 vnet = htons (v); 312 bytes = sizeof (flex_uint16_t); 313 rv = fwrite (&vnet, bytes, 1, wr->out); 314 if (rv != 1) 315 return -1; 316 wr->total_written += bytes; 317 return bytes; 318 } 319 320 /** Write a byte. 321 * @param wr the table writer 322 * @param v the value to be written 323 * @return -1 on error. number of bytes written on success. 324 */ 325 int yytbl_write8 (struct yytbl_writer *wr, flex_uint8_t v) 326 { 327 size_t bytes, rv; 328 329 bytes = sizeof (flex_uint8_t); 330 rv = fwrite (&v, bytes, 1, wr->out); 331 if (rv != 1) 332 return -1; 333 wr->total_written += bytes; 334 return bytes; 335 } 336 337 338 /* XXX Not Used */ 339 #if 0 340 /** Extract data element [i][j] from array data tables. 341 * @param tbl data table 342 * @param i index into higher dimension array. i should be zero for one-dimensional arrays. 343 * @param j index into lower dimension array. 344 * @param k index into struct, must be 0 or 1. Only valid for YYTD_ID_TRANSITION table 345 * @return data[i][j + k] 346 */ 347 static flex_int32_t yytbl_data_getijk (const struct yytbl_data *tbl, int i, 348 int j, int k) 349 { 350 flex_int32_t lo; 351 352 k %= 2; 353 lo = tbl->td_lolen; 354 355 switch (YYTDFLAGS2BYTES (tbl->td_flags)) { 356 case sizeof (flex_int8_t): 357 return ((flex_int8_t *) (tbl->td_data))[(i * lo + j) * (k + 1) + 358 k]; 359 case sizeof (flex_int16_t): 360 return ((flex_int16_t *) (tbl->td_data))[(i * lo + j) * (k + 361 1) + 362 k]; 363 case sizeof (flex_int32_t): 364 return ((flex_int32_t *) (tbl->td_data))[(i * lo + j) * (k + 365 1) + 366 k]; 367 default: 368 flex_die (_("invalid td_flags detected")); 369 break; 370 } 371 372 return 0; 373 } 374 #endif /* Not used */ 375 376 /** Extract data element [i] from array data tables treated as a single flat array of integers. 377 * Be careful for 2-dimensional arrays or for YYTD_ID_TRANSITION, which is an array 378 * of structs. 379 * @param tbl data table 380 * @param i index into array. 381 * @return data[i] 382 */ 383 static flex_int32_t yytbl_data_geti (const struct yytbl_data *tbl, int i) 384 { 385 386 switch (YYTDFLAGS2BYTES (tbl->td_flags)) { 387 case sizeof (flex_int8_t): 388 return ((flex_int8_t *) (tbl->td_data))[i]; 389 case sizeof (flex_int16_t): 390 return ((flex_int16_t *) (tbl->td_data))[i]; 391 case sizeof (flex_int32_t): 392 return ((flex_int32_t *) (tbl->td_data))[i]; 393 default: 394 flex_die (_("invalid td_flags detected")); 395 break; 396 } 397 return 0; 398 } 399 400 /** Set data element [i] in array data tables treated as a single flat array of integers. 401 * Be careful for 2-dimensional arrays or for YYTD_ID_TRANSITION, which is an array 402 * of structs. 403 * @param tbl data table 404 * @param i index into array. 405 * @param newval new value for data[i] 406 */ 407 static void yytbl_data_seti (const struct yytbl_data *tbl, int i, 408 flex_int32_t newval) 409 { 410 411 switch (YYTDFLAGS2BYTES (tbl->td_flags)) { 412 case sizeof (flex_int8_t): 413 ((flex_int8_t *) (tbl->td_data))[i] = (flex_int8_t) newval; 414 break; 415 case sizeof (flex_int16_t): 416 ((flex_int16_t *) (tbl->td_data))[i] = (flex_int16_t) newval; 417 break; 418 case sizeof (flex_int32_t): 419 ((flex_int32_t *) (tbl->td_data))[i] = (flex_int32_t) newval; 420 break; 421 default: 422 flex_die (_("invalid td_flags detected")); 423 break; 424 } 425 } 426 427 /** Calculate the number of bytes needed to hold the largest 428 * absolute value in this data array. 429 * @param tbl the data table 430 * @return sizeof(n) where n in {flex_int8_t, flex_int16_t, flex_int32_t} 431 */ 432 static size_t min_int_size (struct yytbl_data *tbl) 433 { 434 flex_uint32_t i, total_len; 435 flex_int32_t max = 0; 436 437 total_len = yytbl_calc_total_len (tbl); 438 439 for (i = 0; i < total_len; i++) { 440 flex_int32_t n; 441 442 n = abs (yytbl_data_geti (tbl, i)); 443 444 if (n > max) 445 max = n; 446 } 447 448 if (max <= INT8_MAX) 449 return sizeof (flex_int8_t); 450 else if (max <= INT16_MAX) 451 return sizeof (flex_int16_t); 452 else 453 return sizeof (flex_int32_t); 454 } 455 456 /** Transform data to smallest possible of (int32, int16, int8). 457 * For example, we may have generated an int32 array due to user options 458 * (e.g., %option align), but if the maximum value in that array 459 * is 80 (for example), then we can serialize it with only 1 byte per int. 460 * This is NOT the same as compressed DFA tables. We're just trying 461 * to save storage space here. 462 * 463 * @param tbl the table to be compressed 464 */ 465 void yytbl_data_compress (struct yytbl_data *tbl) 466 { 467 flex_int32_t i, newsz, total_len; 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 == (int) YYTDFLAGS2BYTES (tbl->td_flags)) 479 /* No change in this table needed. */ 480 return; 481 482 if (newsz > (int) 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 (total_len, newsz); 489 newtbl.td_flags = 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