source: proto/SymbolTable/symtab_hash_template.cpp @ 1228

Last change on this file since 1228 was 1228, checked in by vla24, 8 years ago

Integrated symbol table with xmlwf. There are various implementations for the symbol table, please read /proto/SymbolTable/README_SymbolTable for more information.

File size: 14.8 KB
Line 
1#include <stdio.h>
2#include <stdlib.h>
3#include <errno.h>
4#include <sys/types.h>
5#include <sys/stat.h>
6#include <../lib_simd.h>
7#include <hash_symbol_table.h>
8
9#include <queue>
10#include <string>
11
12#define DEBUG 0
13#define BLOCK_SIZE (sizeof(SIMD_type) * 8)
14#define SEGMENT_BLOCKS 12
15#define BUFFER_SIZE (BLOCK_SIZE * SEGMENT_BLOCKS)
16#define OVERLAP_BUFSIZE 2*(sizeof(SIMD_type))
17
18typedef long ScanBlock;
19typedef SIMD_type BytePack;
20typedef SIMD_type BitBlock;
21
22using namespace std;
23
24#include <../carryQ.h>
25#include <xmldecl.h>
26#include <xml_error.c>
27#include <xmldecl.c>
28#include <namechars.h>
29
30#include <../perflib/perfsec.h>
31#include <../s2p.h>
32
33#include <TagMatcher.h>
34#include <LineColTracker.h>
35
36#ifdef BUFFER_PROFILING
37        BOM_Table * parser_timer;
38
39#elif CODE_CLOCKER
40        #define NUM_EVENTS 1
41        int Events[NUM_EVENTS] = {PAPI_TOT_CYC};
42        //int Events[NUM_EVENTS] = {PAPI_L2_DCM};
43        //int Events[NUM_EVENTS] = {PAPI_TOT_CYC, PAPI_BR_MSP};
44        int cal_size = 20;
45        CC * parser_timer = new CC(Events,NUM_EVENTS,cal_size);
46#else
47        void * parser_timer;
48#endif
49
50int block_base=0;
51int buffer_base=0;
52int buffer_last;
53char * source;
54LineColTracker tracker;
55TagMatcher matcher;
56BitBlock EOF_mask = simd_const_1(1);
57
58queue <size_t> elem_starts_buf;
59queue <size_t> elem_ends_buf;
60vector <int> gids;
61HashSymbolTable symbol_table;
62
63static inline int StreamScan(ScanBlock * stream, int blk_count, int ProcessPos(int)) {
64        int blk;
65        int block_pos = 0;
66        for (blk = 0; blk < blk_count; blk++) {
67                ScanBlock s = stream[blk];
68                while(s) {
69                        int code = (ProcessPos(cfzl(s) + block_pos));
70                        if (code) return code;
71                        s = s & (s-1);  // clear rightmost bit.
72                }
73                block_pos += 8 * sizeof(ScanBlock);
74        }
75        return 0;
76}
77
78
79static inline void ReportError(const char * error_msg, int error_pos_in_block) {
80  int error_line, error_column;
81  tracker.get_Line_and_Column(error_pos_in_block, error_line, error_column);
82  fprintf(stderr, "%s at line %i, column %i\n", error_msg, error_line, error_column);
83}
84
85static inline int ElemStrt_check(int pos) {
86        int block_pos = block_base + pos;
87        elem_starts_buf.push(buffer_base + block_pos);
88        return 0;
89}
90
91static inline int ElemEnd_check(int pos) {
92        int block_pos = block_base + pos;
93        elem_ends_buf.push(buffer_base + block_pos);
94        return 0;
95}
96
97static inline int NameStrt_check(int pos) {
98        int block_pos = block_base + pos;
99        if(XML_10_UTF8_NameStrt_bytes((unsigned char*)&source[block_pos]) == 0){
100              ReportError("name start error", pos);
101              exit(-1);
102        }
103        return 0;
104}
105
106static inline int Name_check(int pos) {
107        int block_pos = block_base + pos;
108        if(XML_10_UTF8_NameChar_bytes((unsigned char*)&source[block_pos]) == 0){
109              ReportError("name error", pos);
110              exit(-1);
111        }
112        return 0;
113}
114
115static inline int PIName_check(int pos) {
116        int block_pos = block_base + pos;
117        int file_pos = block_pos+buffer_base;
118        printf ("%s:%i\n",__FUNCTION__,pos);
119        if (at_XxMmLll<ASCII>((unsigned char*)&source[block_pos]) && (source[block_pos+3]=='?' || source[block_pos+3]<= ' ')) {
120              // "<?xml" legal at start of file.
121              if ((file_pos == 2) && at_XmlDecl_start<ASCII>((unsigned char*)&source[0])) return 0;
122              ReportError("[Xx][Mm][Ll] illegal as PI name", pos);
123              exit(-1);
124        }
125        return 0;
126}
127
128static inline int CD_check(int pos) {
129        int block_pos = block_base + pos;
130        if (!at_CDATA1<ASCII>((unsigned char*)&source[block_pos])){
131              ReportError("CDATA error", pos);
132              exit(-1);
133        }
134        return 0;
135}
136
137static inline int GenRef_check(int pos) {
138        int block_pos = block_base + pos;
139        unsigned char* s = (unsigned char*)&source[block_pos];
140        if (!(at_Ref_gt<ASCII>(s)||at_Ref_lt<ASCII>(s)||at_Ref_amp<ASCII>(s)||at_Ref_quot<ASCII>(s)||at_Ref_apos<ASCII>(s))){
141              ReportError("Undefined reference", pos);
142              exit(-1);
143        }
144        return 0;
145}
146
147static inline int HexRef_check(int pos) {
148        int block_pos = block_base + pos;
149        unsigned char* s = (unsigned char*)&source[block_pos];
150        int ch_val = 0;
151        while(at_HexDigit<ASCII>(s)){
152          ch_val = HexVal<ASCII>(s[0]) + (ch_val<<4);
153          if (ch_val> 0x10FFFF ){
154            ReportError("Illegal character reference", pos);
155            exit(-1);
156          }
157          s++;
158        }
159        if ((ch_val == 0x0) || ((ch_val | 0x7FF) == 0xDFFF)|| ((ch_val | 0x1) == 0xFFFF)){
160          ReportError("Illegal character reference", pos);
161          exit(-1);
162        }
163        else if (((ch_val < 0x20) && (ch_val != 0x9) && (ch_val != 0xD) && (ch_val != 0xA))){
164          ReportError("Illegal XML 1.0 character reference", pos);
165          exit(-1);
166        }
167        return 0;
168}
169
170static inline int DecRef_check(int pos) {
171        int block_pos = block_base + pos;
172        unsigned char* s = (unsigned char*)&source[block_pos];
173        int ch_val = 0;
174        while(at_HexDigit<ASCII>(s)){
175          ch_val = DigitVal<ASCII>(s[0]) + ch_val*10;
176          if (ch_val> 0x10FFFF ){
177            ReportError("Illegal character reference", pos);
178            exit(-1);
179          }
180          s++;
181        }
182        if ((ch_val == 0x0) || ((ch_val | 0x7FF) == 0xDFFF)|| ((ch_val | 0x1) == 0xFFFF)){
183          ReportError("Illegal character reference", pos);
184          exit(-1);
185        }
186        else if (((ch_val < 0x20) && (ch_val != 0x9) && (ch_val != 0xD) && (ch_val != 0xA))){
187          ReportError("Illegal XML 1.0 character reference", pos);
188          exit(-1);
189        }
190        return 0;
191}
192
193static inline int AttRef_check(int pos) {
194        int block_pos = block_base + pos;
195        unsigned char* s = (unsigned char*)&source[block_pos];
196        int ch_val = 0;
197        if(s[0]=='#'){
198          s++;
199          if(s[0]=='x' || s[0]=='X'){
200            s++;
201            while(at_HexDigit<ASCII>(s)){
202              ch_val = HexVal<ASCII>(s[0]) + (ch_val<<4);
203              s++;
204            }
205          }
206          else{
207            while(at_HexDigit<ASCII>(s)){
208              ch_val = DigitVal<ASCII>(s[0]) + ch_val*10;
209              s++;
210            }
211          }
212          if (ch_val==60){
213            ReportError("Attribute values contain '<' characters after reference expansion", pos);
214            exit(-1);
215          }
216        }
217        else if(at_Ref_lt<ASCII>(s)){
218          ReportError("Attribute values contain '<' characters after reference expansion", pos);
219          exit(-1);
220        }
221        return 0;
222}
223
224
225
226@global
227
228static inline void s2p_do_block(BytePack U8[], Basis_bits & basis_bits) {
229  s2p(U8[0], U8[1], U8[2], U8[3], U8[4], U8[5], U8[6], U8[7],
230        basis_bits.bit_0, basis_bits.bit_1, basis_bits.bit_2, basis_bits.bit_3, basis_bits.bit_4, basis_bits.bit_5, basis_bits.bit_6, basis_bits.bit_7);
231}
232
233static inline void s2p_do_final_block(BytePack U8[], Basis_bits & basis_bits, BitBlock EOF_mask) {
234  s2p_do_block(U8, basis_bits);
235  basis_bits.bit_0 = simd_and(basis_bits.bit_0, EOF_mask);
236  basis_bits.bit_1 = simd_and(basis_bits.bit_1, EOF_mask);
237  basis_bits.bit_2 = simd_and(basis_bits.bit_2, EOF_mask);
238  basis_bits.bit_3 = simd_and(basis_bits.bit_3, EOF_mask);
239  basis_bits.bit_4 = simd_and(basis_bits.bit_4, EOF_mask);
240  basis_bits.bit_5 = simd_and(basis_bits.bit_5, EOF_mask);
241  basis_bits.bit_6 = simd_and(basis_bits.bit_6, EOF_mask);
242  basis_bits.bit_7 = simd_and(basis_bits.bit_7, EOF_mask);
243}
244
245static inline void do_symbol_table_lookup()
246{
247    while( !elem_starts_buf.empty() && !elem_ends_buf.empty() )
248    {
249        int start = elem_starts_buf.front();
250        int end = elem_ends_buf.front();
251        elem_starts_buf.pop();
252        elem_ends_buf.pop();
253        int length = end - start;
254
255        int gid = -1;
256
257
258        //lookup or insert to symbol table
259#if DEBUG
260        char* symbol = new char[length+1];
261        strncpy ( symbol, source + start - buffer_base, length );
262        symbol[length] ='\0';
263        printf ("start: %i[%i] | end: %i[%i] | length: %i | symbol: %s\n", start, start-buffer_base, end, end-buffer_base, length, symbol );
264
265        delete symbol; symbol = 0;
266#endif
267
268        gid = symbol_table.Lookup_or_Insert_Name(source + start - buffer_base, length);
269        gids.push_back(gid);
270    }
271}
272
273static inline void postprocess_do_block(Lex & lex, CtCDPI_Callouts & ctCDPI_Callouts, Ref_Callouts & ref_Callouts, Check_streams & check_streams, Tag_Callouts & tag_Callouts, int chars_avail){
274
275    //NOTE: We are NOT handling the case for an extremely long symbol name (length > 1541).
276    //      TagMatcher will crash if we feed a long symbol name.
277    //      Sample file: test/long_sym_name.xml
278
279            tracker.StoreNewlines(lex.LF);
280
281            if ( bitblock_has_bit(tag_Callouts.ElemName_starts))
282            {
283                StreamScan((ScanBlock *) &tag_Callouts.ElemName_starts, sizeof(BitBlock)/sizeof(ScanBlock), ElemStrt_check);
284            }
285
286            if ( bitblock_has_bit(tag_Callouts.ElemName_ends) )
287            {
288                StreamScan((ScanBlock *) &tag_Callouts.ElemName_ends, sizeof(BitBlock)/sizeof(ScanBlock), ElemEnd_check);
289            }
290
291            do_symbol_table_lookup();
292
293                if (bitblock_has_bit(simd_or(check_streams.non_ascii_name_starts, check_streams.non_ascii_names))) {
294                  StreamScan((ScanBlock *) &check_streams.non_ascii_name_starts, sizeof(BitBlock)/sizeof(ScanBlock), NameStrt_check);
295                  StreamScan((ScanBlock *) &check_streams.non_ascii_names, sizeof(BitBlock)/sizeof(ScanBlock), Name_check);
296                }
297
298                if (bitblock_has_bit(ctCDPI_Callouts.PI_name_starts)){
299                  StreamScan((ScanBlock *) &ctCDPI_Callouts.PI_name_starts, sizeof(BitBlock)/sizeof(ScanBlock), PIName_check);
300                }
301
302                if (bitblock_has_bit(ctCDPI_Callouts.CD_starts)){
303                  StreamScan((ScanBlock *) &ctCDPI_Callouts.CD_starts, sizeof(BitBlock)/sizeof(ScanBlock), CD_check);
304                }
305
306                if (bitblock_has_bit(ref_Callouts.GenRef_starts)){
307                  StreamScan((ScanBlock *) &ref_Callouts.GenRef_starts, sizeof(BitBlock)/sizeof(ScanBlock), GenRef_check);
308                }
309
310                if (bitblock_has_bit(ref_Callouts.DecRef_starts)){
311                  StreamScan((ScanBlock *) &ref_Callouts.DecRef_starts, sizeof(BitBlock)/sizeof(ScanBlock), DecRef_check);
312                }
313
314                if (bitblock_has_bit(ref_Callouts.HexRef_starts)){
315                  StreamScan((ScanBlock *) &ref_Callouts.HexRef_starts, sizeof(BitBlock)/sizeof(ScanBlock), HexRef_check);
316                }
317
318                if (bitblock_has_bit(check_streams.att_refs)){
319                  StreamScan((ScanBlock *) &check_streams.att_refs, sizeof(BitBlock)/sizeof(ScanBlock), AttRef_check);
320                }
321
322                if (bitblock_has_bit(check_streams.error_mask)) {
323                  int errpos = count_forward_zeroes(check_streams.error_mask);
324                  ReportError("error found", errpos);
325              exit(-1);
326                }
327
328                matcher.store_streams(check_streams.tag_marks, check_streams.name_follows, check_streams.misc_mask, chars_avail);
329                tracker.AdvanceBlock();
330}
331
332static inline void print_GIDS()
333{
334    int span_count = gids.size();
335    for(int i=0;i<span_count;i++) {
336             cout << gids[i] << " ";
337    }
338    cout << endl;
339}
340
341void do_process(FILE *infile, FILE *outfile) {
342
343@decl
344
345  int buf_pos = 0;
346  int block_pos = 0;
347  int errpos = 0;
348  int chars_avail = 0;
349  int check_pos = 0;
350  int chars_read = 0;
351  BytePack buf[(BUFFER_SIZE+BLOCK_SIZE+OVERLAP_BUFSIZE*2)/sizeof(SIMD_type)];
352
353  char * srcbuf = ((char *) buf) + OVERLAP_BUFSIZE;
354  buffer_base = buf_pos;
355  source = srcbuf;
356  chars_read = fread((void *)srcbuf, 1, BUFFER_SIZE + OVERLAP_BUFSIZE, infile);
357  chars_avail = chars_read;
358  if (chars_avail > BUFFER_SIZE) chars_avail = BUFFER_SIZE;
359
360  matcher.setSrc(srcbuf);
361
362  if(chars_read<4){
363    fprintf(stderr,"File is too short. Not well formed.\n");
364    exit(-1);
365  }
366
367  Entity_Info * e = new Entity_Info;
368  e->AnalyzeSignature((unsigned char *)srcbuf);
369
370  if (e->code_unit_base == ASCII) {
371
372    XML_Decl_Parser<ASCII> decl_parser((unsigned char *)srcbuf);
373
374    decl_parser.ReadXMLInfo(*e);
375
376    if (e->code_unit_size != SingleByte || (e->has_encoding_decl && (!at_UTF_8(e->encoding)))){
377        fprintf(stderr,"Sorry, this xmlwf demo only works for UTF-8.\n");
378        exit(-1);
379    }
380  }
381  else {
382    fprintf(stderr,"Sorry, this xmlwf demo does not process EBCDIC.\n");
383        exit(-1);
384  }
385
386  if (e->content_start != 0) {
387        memmove(&srcbuf[0], &srcbuf[e->content_start], chars_read - e->content_start);
388        buf_pos = e->content_start;
389        buffer_base = buf_pos;
390        if (chars_avail == BUFFER_SIZE) {
391                chars_read = chars_read - e->content_start +
392                             fread(&srcbuf[chars_read-e->content_start], 1, e->content_start, infile);
393                chars_avail = chars_read;
394                if (chars_avail > BUFFER_SIZE) chars_avail = BUFFER_SIZE;
395        }
396        else {
397          chars_read -=e->content_start;
398          chars_avail -=e->content_start;
399        }
400  }
401
402@stream_stmts
403
404/* Full Buffers */
405    int block_segment_num = 0;
406    while (chars_avail == BUFFER_SIZE) {
407      PERF_SEC_START(parser_timer);
408      for (int blk = 0; blk < SEGMENT_BLOCKS; blk++) {
409          block_base = blk*BLOCK_SIZE;
410          s2p_do_block((BytePack *) &srcbuf[block_base], basis_bits);
411          @block_stmts
412          postprocess_do_block(lex, ctCDPI_Callouts, ref_Callouts, check_streams, tag_Callouts, chars_avail);
413      }
414
415      matcher.StreamScan(chars_avail);
416      matcher.Advance_buffer();
417      tracker.Advance_buffer();
418      PERF_SEC_END(parser_timer, chars_avail);
419           
420      int bytes_left = chars_read - chars_avail;
421      memmove(buf, &srcbuf[BUFFER_SIZE - OVERLAP_BUFSIZE], bytes_left + OVERLAP_BUFSIZE);
422      chars_read = fread(&srcbuf[bytes_left],1, BUFFER_SIZE + OVERLAP_BUFSIZE - bytes_left, infile) + bytes_left;
423      chars_avail = chars_read;
424      if (chars_avail > BUFFER_SIZE) chars_avail = BUFFER_SIZE;
425      buf_pos += chars_avail;
426      buffer_base = buf_pos;
427      block_segment_num++;
428    }
429/* Final Partial Buffer */
430    PERF_SEC_START(parser_timer);
431
432    block_pos = 0;
433    int remaining = chars_avail;
434/* Full Blocks */
435    while (remaining >= BLOCK_SIZE) {
436          block_base = block_pos;
437          s2p_do_block((BytePack *) &srcbuf[block_pos], basis_bits);
438          @block_stmts
439          postprocess_do_block(lex, ctCDPI_Callouts, ref_Callouts, check_streams, tag_Callouts, chars_avail);
440          block_pos += BLOCK_SIZE;
441          remaining -= BLOCK_SIZE;
442    }
443    block_base = block_pos;
444    if (remaining > 0 || @any_carry) {
445          EOF_mask = sisd_srl(simd_const_1(1),sisd_from_int(BLOCK_SIZE-remaining));
446          s2p_do_final_block((BytePack *) &srcbuf[block_pos], basis_bits, EOF_mask);
447          @final_block_stmts
448          postprocess_do_block(lex, ctCDPI_Callouts, ref_Callouts, check_streams, tag_Callouts, chars_avail);
449    }
450    buf_pos += chars_avail;
451    buffer_base = buf_pos;
452
453    matcher.StreamScan(chars_avail);
454    matcher.Advance_buffer();
455    tracker.Advance_buffer();
456
457    PERF_SEC_END(parser_timer, chars_avail);
458    if (matcher.depth != 0) {
459      fprintf(stderr, "tag matching error (depth %i) at position %i\n", matcher.depth, buffer_base);
460      exit(-1);
461    }
462
463//      print_GIDS();
464}
465
466
467
468int
469main(int argc, char * argv[]) {
470        char * infilename, * outfilename;
471        FILE *infile, *outfile;
472        struct stat fileinfo;
473
474        if (argc < 2) {
475                printf("Usage: %s <filename> [<outputfile>]\n", argv[0]);
476                exit(-1);
477        }
478
479        infilename = argv[1];
480        stat(infilename, &fileinfo);
481        infile = fopen(infilename, "rb");
482        if (!infile) {
483                fprintf(stderr, "Error: cannot open %s for input.\n", infilename);
484                exit(-1);
485        }
486
487        if (argc < 3) outfile = stdout;
488        else {
489                outfilename = argv[2];
490                outfile = fopen(outfilename, "wb");
491                if (!outfile) {
492                        fprintf(stderr, "Error: cannot open %s for writing.\n", outfilename);
493                        exit(-1);
494                }
495        }
496
497//      PERF_SEC_BIND(1);
498
499        PERF_SEC_INIT(parser_timer);
500
501        do_process(infile, outfile);
502
503        PERF_SEC_DUMP(parser_timer);
504
505        PERF_SEC_DESTROY(parser_timer);
506
507        fclose(infile);
508        fclose(outfile);
509
510        printf ("Done procressing\n");
511        return(0);
512}
Note: See TracBrowser for help on using the repository browser.