source: vendor/flex/2.5.33/tables.c

Last change on this file was 3031, checked in by bird, 18 years ago

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