contrib/flex/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 /* XXX Not used
  61 static flex_int32_t yytbl_data_getijk (const struct yytbl_data *tbl, int i,
  62                                   int j, int k);
  63  */
  64
  65
  66 /** Initialize the table writer.
  67  *  @param wr an uninitialized writer
  68  *  @param the output file
  69  *  @return 0 on success
  70  */
  71 int yytbl_writer_init (struct yytbl_writer *wr, FILE * out)
  72 {
  73         wr->out = out;
  74         wr->total_written = 0;
  75         return 0;
  76 }
  77
  78 /** Initialize a table header.
  79  *  @param th  The uninitialized structure
  80  *  @param version_str the  version string
  81  *  @param name the name of this table set
  82  */
  83 int yytbl_hdr_init (struct yytbl_hdr *th, const char *version_str,
  84                     const char *name)
  85 {
  86         memset (th, 0, sizeof (struct yytbl_hdr));
  87
  88         th->th_magic = YYTBL_MAGIC;
  89         th->th_hsize = 14 + strlen (version_str) + 1 + strlen (name) + 1;
  90         th->th_hsize += yypad64 (th->th_hsize);
  91         th->th_ssize = 0;       // Not known at this point.
  92         th->th_flags = 0;
  93         th->th_version = copy_string (version_str);
  94         th->th_name = copy_string (name);
  95         return 0;
  96 }
  97
  98 /** Allocate and initialize a table data structure.
  99  *  @param tbl a pointer to an uninitialized table
 100  *  @param id  the table identifier
 101  *  @return 0 on success
 102  */
 103 int yytbl_data_init (struct yytbl_data *td, enum yytbl_id id)
 104 {
 105
 106         memset (td, 0, sizeof (struct yytbl_data));
 107         td->td_id = id;
 108         td->td_flags = YYTD_DATA32;
 109         return 0;
 110 }
 111
 112 /** Clean up table and data array.
 113  *  @param td will be destroyed
 114  *  @return 0 on success
 115  */
 116 int yytbl_data_destroy (struct yytbl_data *td)
 117 {
 118         if (td->td_data)
 119                 free (td->td_data);
 120         td->td_data = 0;
 121         free (td);
 122         return 0;
 123 }
 124
 125 /** Write enough padding to bring the file pointer to a 64-bit boundary. */
 126 static int yytbl_write_pad64 (struct yytbl_writer *wr)
 127 {
 128         int     pad, bwritten = 0;
 129
 130         pad = yypad64 (wr->total_written);
 131         while (pad-- > 0)
 132                 if (yytbl_write8 (wr, 0) < 0)
 133                         return -1;
 134                 else
 135                         bwritten++;
 136         return bwritten;
 137 }
 138
 139 /** write the header.
 140  *  @param out the output stream
 141  *  @param th table header to be written
 142  *  @return -1 on error, or bytes written on success.
 143  */
 144 int yytbl_hdr_fwrite (struct yytbl_writer *wr, const struct yytbl_hdr *th)
 145 {
 146         int  sz, rv;
 147         int     bwritten = 0;
 148
 149         if (yytbl_write32 (wr, th->th_magic) < 0
 150             || yytbl_write32 (wr, th->th_hsize) < 0)
 151                 flex_die (_("th_magic|th_hsize write32 failed"));
 152         bwritten += 8;
 153
 154         if (fgetpos (wr->out, &(wr->th_ssize_pos)) != 0)
 155                 flex_die (_("fgetpos failed"));
 156
 157         if (yytbl_write32 (wr, th->th_ssize) < 0
 158             || yytbl_write16 (wr, th->th_flags) < 0)
 159                 flex_die (_("th_ssize|th_flags write failed"));
 160         bwritten += 6;
 161
 162         sz = strlen (th->th_version) + 1;
 163         if ((rv = yytbl_writen (wr, th->th_version, sz)) != sz)
 164                 flex_die (_("th_version writen failed"));
 165         bwritten += rv;
 166
 167         sz = strlen (th->th_name) + 1;
 168         if ((rv = yytbl_writen (wr, th->th_name, sz)) != sz)
 169                 flex_die (_("th_name writen failed"));
 170         bwritten += rv;
 171
 172         /* add padding */
 173         if ((rv = yytbl_write_pad64 (wr)) < 0)
 174                 flex_die (_("pad64 failed"));
 175         bwritten += rv;
 176
 177         /* Sanity check */
 178         if (bwritten != (int) th->th_hsize)
 179                 flex_die (_("pad64 failed"));
 180
 181         return bwritten;
 182 }
 183
 184
 185 /** Write this table.
 186  *  @param out the file writer
 187  *  @param td table data to be written
 188  *  @return -1 on error, or bytes written on success.
 189  */
 190 int yytbl_data_fwrite (struct yytbl_writer *wr, struct yytbl_data *td)
 191 {
 192         int  rv;
 193         flex_int32_t bwritten = 0;
 194         flex_int32_t i, total_len;
 195         fpos_t  pos;
 196
 197         if ((rv = yytbl_write16 (wr, td->td_id)) < 0)
 198                 return -1;
 199         bwritten += rv;
 200
 201         if ((rv = yytbl_write16 (wr, td->td_flags)) < 0)
 202                 return -1;
 203         bwritten += rv;
 204
 205         if ((rv = yytbl_write32 (wr, td->td_hilen)) < 0)
 206                 return -1;
 207         bwritten += rv;
 208
 209         if ((rv = yytbl_write32 (wr, td->td_lolen)) < 0)
 210                 return -1;
 211         bwritten += rv;
 212
 213         total_len = yytbl_calc_total_len (td);
 214         for (i = 0; i < total_len; i++) {
 215                 switch (YYTDFLAGS2BYTES (td->td_flags)) {
 216                 case sizeof (flex_int8_t):
 217                         rv = yytbl_write8 (wr, yytbl_data_geti (td, i));
 218                         break;
 219                 case sizeof (flex_int16_t):
 220                         rv = yytbl_write16 (wr, yytbl_data_geti (td, i));
 221                         break;
 222                 case sizeof (flex_int32_t):
 223                         rv = yytbl_write32 (wr, yytbl_data_geti (td, i));
 224                         break;
 225                 default:
 226                         flex_die (_("invalid td_flags detected"));
 227                 }
 228                 if (rv < 0) {
 229                         flex_die (_("error while writing tables"));
 230                         return -1;
 231                 }
 232                 bwritten += rv;
 233         }
 234
 235         /* Sanity check */
 236         if (bwritten != (int) (12 + total_len * YYTDFLAGS2BYTES (td->td_flags))) {
 237                 flex_die (_("insanity detected"));
 238                 return -1;
 239         }
 240
 241         /* add padding */
 242         if ((rv = yytbl_write_pad64 (wr)) < 0) {
 243                 flex_die (_("pad64 failed"));
 244                 return -1;
 245         }
 246         bwritten += rv;
 247
 248         /* Now go back and update the th_hsize member */
 249         if (fgetpos (wr->out, &pos) != 0
 250             || fsetpos (wr->out, &(wr->th_ssize_pos)) != 0
 251             || yytbl_write32 (wr, wr->total_written) < 0
 252             || fsetpos (wr->out, &pos)) {
 253                 flex_die (_("get|set|fwrite32 failed"));
 254                 return -1;
 255         }
 256         else
 257                 /* Don't count the int we just wrote. */
 258                 wr->total_written -= sizeof (flex_int32_t);
 259         return bwritten;
 260 }
 261
 262 /** Write n bytes.
 263  *  @param  wr   the table writer
 264  *  @param  v    data to be written
 265  *  @param  len  number of bytes
 266  *  @return  -1 on error. number of bytes written on success.
 267  */
 268 int yytbl_writen (struct yytbl_writer *wr, void *v, flex_int32_t len)
 269 {
 270         int  rv;
 271
 272         rv = fwrite (v, 1, len, wr->out);
 273         if (rv != len)
 274                 return -1;
 275         wr->total_written += len;
 276         return len;
 277 }
 278
 279 /** Write four bytes in network byte order
 280  *  @param  wr  the table writer
 281  *  @param  v    a dword in host byte order
 282  *  @return  -1 on error. number of bytes written on success.
 283  */
 284 int yytbl_write32 (struct yytbl_writer *wr, flex_uint32_t v)
 285 {
 286         flex_uint32_t vnet;
 287         size_t  bytes, rv;
 288
 289         vnet = htonl (v);
 290         bytes = sizeof (flex_uint32_t);
 291         rv = fwrite (&vnet, bytes, 1, wr->out);
 292         if (rv != 1)
 293                 return -1;
 294         wr->total_written += bytes;
 295         return bytes;
 296 }
 297
 298 /** Write two bytes in network byte order.
 299  *  @param  wr  the table writer
 300  *  @param  v    a word in host byte order
 301  *  @return  -1 on error. number of bytes written on success.
 302  */
 303 int yytbl_write16 (struct yytbl_writer *wr, flex_uint16_t v)
 304 {
 305         flex_uint16_t vnet;
 306         size_t  bytes, rv;
 307
 308         vnet = htons (v);
 309         bytes = sizeof (flex_uint16_t);
 310         rv = fwrite (&vnet, bytes, 1, wr->out);
 311         if (rv != 1)
 312                 return -1;
 313         wr->total_written += bytes;
 314         return bytes;
 315 }
 316
 317 /** Write a byte.
 318  *  @param  wr  the table writer
 319  *  @param  v    the value to be written
 320  *  @return  -1 on error. number of bytes written on success.
 321  */
 322 int yytbl_write8 (struct yytbl_writer *wr, flex_uint8_t v)
 323 {
 324         size_t  bytes, rv;
 325
 326         bytes = sizeof (flex_uint8_t);
 327         rv = fwrite (&v, bytes, 1, wr->out);
 328         if (rv != 1)
 329                 return -1;
 330         wr->total_written += bytes;
 331         return bytes;
 332 }
 333
 334
 335 /* XXX Not Used */
 336 #if 0
 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 static flex_int32_t yytbl_data_getijk (const struct yytbl_data *tbl, int i,
 345                                   int j, int k)
 346 {
 347         flex_int32_t lo;
 348
 349         k %= 2;
 350         lo = tbl->td_lolen;
 351
 352         switch (YYTDFLAGS2BYTES (tbl->td_flags)) {
 353         case sizeof (flex_int8_t):
 354                 return ((flex_int8_t *) (tbl->td_data))[(i * lo + j) * (k + 1) +
 355                                                    k];
 356         case sizeof (flex_int16_t):
 357                 return ((flex_int16_t *) (tbl->td_data))[(i * lo + j) * (k +
 358                                                                     1) +
 359                                                     k];
 360         case sizeof (flex_int32_t):
 361                 return ((flex_int32_t *) (tbl->td_data))[(i * lo + j) * (k +
 362                                                                     1) +
 363                                                     k];
 364         default:
 365                 flex_die (_("invalid td_flags detected"));
 366                 break;
 367         }
 368
 369         return 0;
 370 }
 371 #endif /* Not used */
 372
 373 /** Extract data element [i] from array data tables treated as a single flat array of integers.
 374  * Be careful for 2-dimensional arrays or for YYTD_ID_TRANSITION, which is an array
 375  * of structs.
 376  * @param tbl data table
 377  * @param i index into array.
 378  * @return data[i]
 379  */
 380 static flex_int32_t yytbl_data_geti (const struct yytbl_data *tbl, int i)
 381 {
 382
 383         switch (YYTDFLAGS2BYTES (tbl->td_flags)) {
 384         case sizeof (flex_int8_t):
 385                 return ((flex_int8_t *) (tbl->td_data))[i];
 386         case sizeof (flex_int16_t):
 387                 return ((flex_int16_t *) (tbl->td_data))[i];
 388         case sizeof (flex_int32_t):
 389                 return ((flex_int32_t *) (tbl->td_data))[i];
 390         default:
 391                 flex_die (_("invalid td_flags detected"));
 392                 break;
 393         }
 394         return 0;
 395 }
 396
 397 /** Set data element [i] in array data tables treated as a single flat array of integers.
 398  * Be careful for 2-dimensional arrays or for YYTD_ID_TRANSITION, which is an array
 399  * of structs.
 400  * @param tbl data table
 401  * @param i index into array.
 402  * @param newval new value for data[i]
 403  */
 404 static void yytbl_data_seti (const struct yytbl_data *tbl, int i,
 405                              flex_int32_t newval)
 406 {
 407
 408         switch (YYTDFLAGS2BYTES (tbl->td_flags)) {
 409         case sizeof (flex_int8_t):
 410                 ((flex_int8_t *) (tbl->td_data))[i] = (flex_int8_t) newval;
 411                 break;
 412         case sizeof (flex_int16_t):
 413                 ((flex_int16_t *) (tbl->td_data))[i] = (flex_int16_t) newval;
 414                 break;
 415         case sizeof (flex_int32_t):
 416                 ((flex_int32_t *) (tbl->td_data))[i] = (flex_int32_t) newval;
 417                 break;
 418         default:
 419                 flex_die (_("invalid td_flags detected"));
 420                 break;
 421         }
 422 }
 423
 424 /** Calculate the number of bytes  needed to hold the largest
 425  *  absolute value in this data array.
 426  *  @param tbl  the data table
 427  *  @return sizeof(n) where n in {flex_int8_t, flex_int16_t, flex_int32_t}
 428  */
 429 static size_t min_int_size (struct yytbl_data *tbl)
 430 {
 431         flex_uint32_t i, total_len;
 432         flex_int32_t max = 0;
 433
 434         total_len = yytbl_calc_total_len (tbl);
 435
 436         for (i = 0; i < total_len; i++) {
 437                 flex_int32_t n;
 438
 439                 n = abs (yytbl_data_geti (tbl, i));
 440
 441                 if (n > max)
 442                         max = n;
 443         }
 444
 445         if (max <= INT8_MAX)
 446                 return sizeof (flex_int8_t);
 447         else if (max <= INT16_MAX)
 448                 return sizeof (flex_int16_t);
 449         else
 450                 return sizeof (flex_int32_t);
 451 }
 452
 453 /** Transform data to smallest possible of (int32, int16, int8).
 454  * For example, we may have generated an int32 array due to user options
 455  * (e.g., %option align), but if the maximum value in that array
 456  * is 80 (for example), then we can serialize it with only 1 byte per int.
 457  * This is NOT the same as compressed DFA tables. We're just trying
 458  * to save storage space here.
 459  *
 460  * @param tbl the table to be compressed
 461  */
 462 void yytbl_data_compress (struct yytbl_data *tbl)
 463 {
 464         flex_int32_t i, newsz, total_len;
 465         struct yytbl_data newtbl;
 466
 467         yytbl_data_init (&newtbl, tbl->td_id);
 468         newtbl.td_hilen = tbl->td_hilen;
 469         newtbl.td_lolen = tbl->td_lolen;
 470         newtbl.td_flags = tbl->td_flags;
 471
 472         newsz = min_int_size (tbl);
 473
 474
 475         if (newsz == (int) YYTDFLAGS2BYTES (tbl->td_flags))
 476                 /* No change in this table needed. */
 477                 return;
 478
 479         if (newsz > (int) YYTDFLAGS2BYTES (tbl->td_flags)) {
 480                 flex_die (_("detected negative compression"));
 481                 return;
 482         }
 483
 484         total_len = yytbl_calc_total_len (tbl);
 485         newtbl.td_data = calloc (total_len, newsz);
 486         newtbl.td_flags =
 487                 TFLAGS_CLRDATA (newtbl.td_flags) | BYTES2TFLAG (newsz);
 488
 489         for (i = 0; i < total_len; i++) {
 490                 flex_int32_t g;
 491
 492                 g = yytbl_data_geti (tbl, i);
 493                 yytbl_data_seti (&newtbl, i, g);
 494         }
 495
 496
 497         /* Now copy over the old table */
 498         free (tbl->td_data);
 499         *tbl = newtbl;
 500 }
 501
 502 /* vim:set noexpandtab cindent tabstop=8 softtabstop=0 shiftwidth=8 textwidth=0: */