Annotation of src/usr.bin/lex/tables.c, Revision 1.1
1.1 ! tedu 1: /* $OpenBSD$ */
! 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:
! 57: int yytbl_write32 (struct yytbl_writer *wr, flex_uint32_t v);
! 58: int yytbl_write16 (struct yytbl_writer *wr, flex_uint16_t v);
! 59: int yytbl_write8 (struct yytbl_writer *wr, flex_uint8_t v);
! 60: int yytbl_writen (struct yytbl_writer *wr, void *v, flex_int32_t len);
! 61: static flex_int32_t yytbl_data_geti (const struct yytbl_data *tbl, int i);
! 62: /* XXX Not used
! 63: static flex_int32_t yytbl_data_getijk (const struct yytbl_data *tbl, int i,
! 64: int j, int k);
! 65: */
! 66:
! 67:
! 68: /** Initialize the table writer.
! 69: * @param wr an uninitialized writer
! 70: * @param the output file
! 71: * @return 0 on success
! 72: */
! 73: int 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: */
! 85: int 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: */
! 105: int 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: */
! 118: int 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. */
! 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 out 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 = 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: */
! 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, 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: */
! 270: int 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: */
! 286: int 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: */
! 305: int 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: */
! 324: int 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: /* 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_uint32_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 (n > max)
! 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, newsz, total_len;
! 467: struct yytbl_data newtbl;
! 468:
! 469: yytbl_data_init (&newtbl, tbl->td_id);
! 470: newtbl.td_hilen = tbl->td_hilen;
! 471: newtbl.td_lolen = tbl->td_lolen;
! 472: newtbl.td_flags = tbl->td_flags;
! 473:
! 474: newsz = min_int_size (tbl);
! 475:
! 476:
! 477: if (newsz == (int) YYTDFLAGS2BYTES (tbl->td_flags))
! 478: /* No change in this table needed. */
! 479: return;
! 480:
! 481: if (newsz > (int) YYTDFLAGS2BYTES (tbl->td_flags)) {
! 482: flex_die (_("detected negative compression"));
! 483: return;
! 484: }
! 485:
! 486: total_len = yytbl_calc_total_len (tbl);
! 487: newtbl.td_data = calloc (total_len, newsz);
! 488: newtbl.td_flags =
! 489: TFLAGS_CLRDATA (newtbl.td_flags) | BYTES2TFLAG (newsz);
! 490:
! 491: for (i = 0; i < total_len; i++) {
! 492: flex_int32_t g;
! 493:
! 494: g = yytbl_data_geti (tbl, i);
! 495: yytbl_data_seti (&newtbl, i, g);
! 496: }
! 497:
! 498:
! 499: /* Now copy over the old table */
! 500: free (tbl->td_data);
! 501: *tbl = newtbl;
! 502: }
! 503:
! 504: /* vim:set noexpandtab cindent tabstop=8 softtabstop=0 shiftwidth=8 textwidth=0: */