tables.c

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