1 /* $NetBSD: tables.c,v 1.3 2017/01/02 17:45:27 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.3 2017/01/02 17:45:27 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, int 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 out 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 = (flex_uint32_t) (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 = xstrdup(version_str);
97 th->th_name = xstrdup(name);
98 return 0;
99 }
100
101 /** Allocate and initialize a table data structure.
102 * @param td 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 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. */
yytbl_write_pad64(struct yytbl_writer * wr)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 wr the output stream
143 * @param th table header to be written
144 * @return -1 on error, or bytes written on success.
145 */
yytbl_hdr_fwrite(struct yytbl_writer * wr,const struct yytbl_hdr * th)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 = (int) 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 = (int) 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 wr the file writer
189 * @param td table data to be written
190 * @return -1 on error, or bytes written on success.
191 */
yytbl_data_fwrite(struct yytbl_writer * wr,struct yytbl_data * td)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, (flex_uint8_t) yytbl_data_geti (td, i));
220 break;
221 case sizeof (flex_int16_t):
222 rv = yytbl_write16 (wr, (flex_uint16_t) yytbl_data_geti (td, i));
223 break;
224 case sizeof (flex_int32_t):
225 rv = yytbl_write32 (wr, (flex_uint32_t) 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 != (12 + total_len * (int) 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, (flex_uint32_t) 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 -= (int) 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 */
yytbl_writen(struct yytbl_writer * wr,void * v,int len)270 int yytbl_writen (struct yytbl_writer *wr, void *v, int len)
271 {
272 int rv;
273
274 rv = (int) fwrite (v, 1, (size_t) 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 */
yytbl_write32(struct yytbl_writer * wr,flex_uint32_t v)286 int yytbl_write32 (struct yytbl_writer *wr, flex_uint32_t v)
287 {
288 flex_uint32_t vnet;
289 int bytes, rv;
290
291 vnet = htonl (v);
292 bytes = (int) sizeof (flex_uint32_t);
293 rv = (int) fwrite (&vnet, (size_t) 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 */
yytbl_write16(struct yytbl_writer * wr,flex_uint16_t v)305 int yytbl_write16 (struct yytbl_writer *wr, flex_uint16_t v)
306 {
307 flex_uint16_t vnet;
308 int bytes, rv;
309
310 vnet = htons (v);
311 bytes = (int) sizeof (flex_uint16_t);
312 rv = (int) fwrite (&vnet, (size_t) 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 */
yytbl_write8(struct yytbl_writer * wr,flex_uint8_t v)324 int yytbl_write8 (struct yytbl_writer *wr, flex_uint8_t v)
325 {
326 int bytes, rv;
327
328 bytes = (int) sizeof (flex_uint8_t);
329 rv = (int) fwrite (&v, (size_t) 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 */
yytbl_data_geti(const struct yytbl_data * tbl,int i)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 */
yytbl_data_seti(const struct yytbl_data * tbl,int i,flex_int32_t newval)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 */
min_int_size(struct yytbl_data * tbl)431 static size_t min_int_size (struct yytbl_data *tbl)
432 {
433 flex_int32_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 (max < n)
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 */
yytbl_data_compress(struct yytbl_data * tbl)464 void yytbl_data_compress (struct yytbl_data *tbl)
465 {
466 flex_int32_t i, total_len;
467 size_t newsz;
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 == YYTDFLAGS2BYTES (tbl->td_flags))
479 /* No change in this table needed. */
480 return;
481
482 if (newsz > 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 ((size_t) total_len, newsz);
489 newtbl.td_flags = (flex_uint16_t)
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