1/* $NetBSD: tables.c,v 1.2 2009/10/26 04:27:15 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 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 57int yytbl_write32 (struct yytbl_writer *wr, flex_uint32_t v); 58int yytbl_write16 (struct yytbl_writer *wr, flex_uint16_t v); 59int yytbl_write8 (struct yytbl_writer *wr, flex_uint8_t v); 60int yytbl_writen (struct yytbl_writer *wr, void *v, flex_int32_t len); 61static flex_int32_t yytbl_data_geti (const struct yytbl_data *tbl, int i); 62#ifdef notdef 63static flex_int32_t yytbl_data_getijk (const struct yytbl_data *tbl, int i, 64 int j, int k); 65#endif 66 67 68/** Initialize the table writer. 69 * @param wr an uninitialized writer 70 * @param the output file 71 * @return 0 on success 72 */ 73int 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 */ 85int 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 */ 105int 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 */ 118int yytbl_data_destroy (struct yytbl_data *td) 119{ 120 if (td->td_data) 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 out 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 = 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 = 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 out 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, yytbl_data_geti (td, i)); 220 break; 221 case sizeof (flex_int16_t): 222 rv = yytbl_write16 (wr, yytbl_data_geti (td, i)); 223 break; 224 case sizeof (flex_int32_t): 225 rv = yytbl_write32 (wr, 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 != (int) (12 + total_len * 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, 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 -= 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, flex_int32_t len) 271{ 272 int rv; 273 274 rv = fwrite (v, 1, 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 size_t bytes, rv; 290 291 vnet = htonl (v); 292 bytes = sizeof (flex_uint32_t); 293 rv = fwrite (&vnet, 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 size_t bytes, rv; 309 310 vnet = htons (v); 311 bytes = sizeof (flex_uint16_t); 312 rv = fwrite (&vnet, 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 size_t bytes, rv; 327 328 bytes = sizeof (flex_uint8_t); 329 rv = fwrite (&v, bytes, 1, wr->out); 330 if (rv != 1) 331 return -1; 332 wr->total_written += bytes; 333 return bytes; 334} 335 336 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 */ 344#ifdef notdef 345static 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 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 */ 381static 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 */ 405static 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 */ 430static 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 */ 463void 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 503/* vim:set noexpandtab cindent tabstop=8 softtabstop=0 shiftwidth=8 textwidth=0: */ 504