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 58int yytbl_write32 (struct yytbl_writer *wr, flex_uint32_t v); 59int yytbl_write16 (struct yytbl_writer *wr, flex_uint16_t v); 60int yytbl_write8 (struct yytbl_writer *wr, flex_uint8_t v); 61int yytbl_writen (struct yytbl_writer *wr, void *v, int len); 62static flex_int32_t yytbl_data_geti (const struct yytbl_data *tbl, int i); 63/* XXX Not used 64static 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 */ 74int 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 */ 86int 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 */ 106int 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 */ 119int 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. */ 128static 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 */ 146int 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 */ 192int 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 */ 270int 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 */ 286int 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 */ 305int 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 */ 324int 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 */ 346static 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 */ 382static 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 */ 406static 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 */ 431static 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 */ 464void 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