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