Annotation of src/usr.bin/lex/tables.c, Revision 1.2
1.2 ! tedu 1: /* $OpenBSD: tables.c,v 1.1 2015/11/19 19:43:40 tedu Exp $ */
1.1 tedu 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: }