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