source: proto/parabix2/src/TagMatcher.h @ 1496

Last change on this file since 1496 was 1445, checked in by ksherdy, 8 years ago

Modularize pablo_template.cpp.

File size: 8.2 KB
Line 
1#define MAX_DEPTH 100
2#include <algorithm>
3#include <iostream>
4#include <string.h>
5using namespace std;
6
7#define MAX_DEPTH 100
8#define MAX_ATTS 100
9
10struct attribute{
11  char * start;
12  int lgth;
13};
14
15class TagMatcher {
16  public:
17  SIMD_type tagMarks[BUFFER_SIZE/BLOCK_SIZE];
18  SIMD_type miscMarks[BUFFER_SIZE/BLOCK_SIZE];
19  char tags_buf[BUFFER_SIZE];
20  int tags_buf_cur;
21  int stream_index;
22  char * srcbuf;
23  int depth;
24  int inTagPos;
25  int finalStartPos;
26  char* tag_stack[MAX_DEPTH];
27  int tag_lgth_stack[MAX_DEPTH];
28  SIMD_type NameFollows[BUFFER_SIZE/BLOCK_SIZE+1]; // 1 extra block for sentinel
29  int buf_base;
30  enum TagMatchState {InStartTag, InEndTag, InAttName, Clear} state;
31  enum TagMatchMode {StartOfFile, InFile} mode;
32  struct attribute Attr[MAX_ATTS];
33  struct attribute InAtt;
34  int att_index;
35  int InFinalEndTag;
36
37  TagMatcher();
38  ~TagMatcher();
39  void setSrc(char * src);
40  int StreamScan(int chars_avail);
41  void store_streams(SIMD_type tagMark, SIMD_type NameFollow, SIMD_type miscMarks, int chars_avail);
42  int tag_match(int pos, int chars_avail);
43  void Advance_buffer();
44  int does_match(char * s1, char * s2, int lgth);
45  int lookup_or_insert(char*s, int lgth);
46};
47
48int TagMatcher::lookup_or_insert(char* s, int lgth){
49  for(int i=0; i< att_index; i++)
50    if(lgth == Attr[i].lgth &&  does_match(s,Attr[i].start,lgth))
51      return 1;
52
53  Attr[att_index].start = s;
54  Attr[att_index].lgth = lgth;
55  att_index++;
56  return 0;
57}
58
59int TagMatcher::does_match(char * s1, char * s2, int lgth){
60    int matchlen = 0;
61    int i=0;
62    while (lgth > sizeof(SIMD_type)) {
63      /* full 16 byte match */
64      if (simd_all_eq_8(sisd_load_unaligned((SIMD_type*)&s1[i]), sisd_load_unaligned((SIMD_type*)&s2[i]))) {
65                lgth -= sizeof(SIMD_type);
66                i +=sizeof(SIMD_type);
67      }
68      else {
69                return 0;
70      }
71    }
72    if (lgth > cfzl(~_mm_movemask_epi8(simd_eq_8(sisd_load_unaligned((SIMD_type*)&s1[i]),
73                                                  sisd_load_unaligned((SIMD_type*)&s2[i])))))
74      return 0;
75    else return 1;
76}
77
78
79int TagMatcher:: tag_match(int pos, int chars_avail) {
80        int rt_val=0;
81//      end tag
82        if(srcbuf[pos]=='/' ){
83          pos++;
84          depth--;
85          if (depth<0)
86            return pos;
87          int lgth = tag_lgth_stack[depth];
88
89          if (does_match(tag_stack[depth],&srcbuf[pos],lgth) && ((srcbuf[pos+lgth] == '>') ||(srcbuf[pos+lgth] <= ' '))) rt_val=0;
90          else if (pos + lgth >= BUFFER_SIZE + OVERLAP_BUFSIZE) {
91            state = InEndTag;
92            inTagPos = BUFFER_SIZE - pos;
93            rt_val=0;
94          }
95          else {
96//            cout << "end tag is " << string(&srcbuf[pos],tag_lgth_stack[depth]) << endl ;
97//            cout << "start tag is " << string(tag_stack[depth],tag_lgth_stack[depth]) << endl ;
98              fprintf(stderr,"tag name mismatch at position = %i\n",buf_base+pos);
99              exit(-1);
100          }
101
102          if (depth == 0){
103            while(srcbuf[pos]!='>'){
104              pos++;
105              if(pos>=chars_avail){
106                InFinalEndTag = 1;
107                return 0;
108              }
109            }
110            pos = bitstream_scan(miscMarks,pos+1);
111            if(pos!=chars_avail){
112              fprintf(stderr,"illegal content after root element at position = %i\n",buf_base+pos);
113              exit(-1);
114            }
115          }
116          return rt_val;
117        }
118//      empty tag
119        else if(srcbuf[pos]=='>'){
120          depth--;
121          if (depth == 0){
122            while(srcbuf[pos]!='>')
123              pos++;
124            pos = bitstream_scan(miscMarks,pos+1);
125
126            if(pos!=chars_avail){
127              fprintf(stderr,"illegal content after root element at position = %i\n",buf_base+pos);
128              exit(-1);
129            }
130          }
131        }
132//      start tag
133        else if(srcbuf[pos-1]=='<'){
134          att_index = 0;
135          if(depth<MAX_DEPTH){
136            int end_pos = bitstream_scan(NameFollows,pos);
137            tag_lgth_stack[depth] = end_pos-pos;
138            tag_stack[depth] = &srcbuf[pos];
139            if(end_pos<BUFFER_SIZE){
140              depth++;
141            }
142            else{
143              state = InStartTag;
144              finalStartPos = pos;
145            }
146          }
147          else{
148            fprintf(stderr,"Max nesting depth exceeded at position =%i. depth = %i\n",buf_base+pos, depth);
149            exit(-1);
150          }
151        }
152//      attribute
153        else{
154          int end_pos = bitstream_scan(NameFollows,pos);
155          if(end_pos<BUFFER_SIZE){
156            if(lookup_or_insert(&srcbuf[pos], end_pos-pos)){
157              fprintf(stderr,"Attribute name is not unique at position =%i.\n",buf_base+pos);
158              exit(-1);
159            }
160          }
161          else{
162            state = InAttName;
163            InAtt.start = &srcbuf[pos];
164            InAtt.lgth = BUFFER_SIZE-pos;
165          }
166        }
167        return 0;
168}
169
170
171int TagMatcher::StreamScan(int chars_avail) {
172
173        int blk;
174        int blk_counts = (chars_avail+sizeof(ScanBlock)*8-1)/(sizeof(ScanBlock)*8);
175        int block_pos = 0;
176
177        if(mode == StartOfFile){
178          int pos = bitstream_scan(miscMarks,0);
179          if (pos==chars_avail){
180            fprintf(stderr,"no element at position =%i.\n",buf_base+pos);
181            exit(-1);
182          }
183          if(srcbuf[pos-1]!='<'|| srcbuf[pos]=='!'||srcbuf[pos]=='/'){
184#ifdef DUMP
185print_bit_block("srcbuf", sisd_load_unaligned((BitBlock *) srcbuf));
186#endif
187            fprintf(stderr,"illegal content before root element at position =%i.\n",buf_base+pos);
188            exit(-1);
189          }
190          mode = InFile;
191        }
192        for (blk = 0; blk < blk_counts; blk++) {
193                ScanBlock s = ((ScanBlock*)tagMarks)[blk];
194                while(s) {
195                        int code = tag_match(cfzl(s) + block_pos, chars_avail);
196                        if (code) return code;
197                        s = s & (s-1);  // clear rightmost bit.
198                }
199                block_pos += 8 * sizeof(ScanBlock);
200        }
201
202        return 0;
203}
204
205void TagMatcher::store_streams(SIMD_type tagMark, SIMD_type NameFollow, SIMD_type miscMark, int chars_avail){
206#ifdef DUMP
207print_bit_block("tagMark", tagMark);
208print_bit_block("NameFollow", NameFollow);
209print_bit_block("miscMark", miscMark);
210printf("chars_avail = %i\n", chars_avail);
211printf("stream_index = %i\n", stream_index);
212#endif
213  tagMarks[stream_index] = tagMark;
214  miscMarks[stream_index] = simd_not(miscMark);
215  NameFollows[stream_index] = NameFollow;
216  stream_index++;
217  if(stream_index==1){
218
219    if (InFinalEndTag == 1){
220      int pos = -1;
221      while(srcbuf[pos]!='>'){
222        pos++;
223        if(pos>=chars_avail){
224          InFinalEndTag = 1;
225          return;
226        }
227      }
228      pos = bitstream_scan(miscMarks,pos+1);
229#ifdef DUMP
230print_bit_block("miscMarks[0]", miscMarks[0]);
231printf("pos = %i\n", pos);
232#endif
233      if(pos!=chars_avail){
234        fprintf(stderr,"illegal content after root element at position = %i\n",buf_base+pos);
235        exit(-1);
236      }
237    }
238
239    if(state == InStartTag) {
240      state = Clear;
241      int remain_lgth = bitstream_scan(NameFollows,0);
242      memcpy(&tags_buf[tags_buf_cur],srcbuf,remain_lgth);
243      tag_lgth_stack[depth] += remain_lgth;
244      depth++;
245    }
246    else if (state == InEndTag) {
247      state = Clear;
248      int lgth = tag_lgth_stack[depth];
249      if (does_match(tag_stack[depth]+inTagPos,srcbuf,lgth-inTagPos) && ((srcbuf[lgth-inTagPos] == '>') ||(srcbuf[lgth-inTagPos] <= ' '))) return ;
250      else {
251          fprintf(stderr,"tag name mismatch at position = %i\n",buf_base);
252          exit(-1);
253      }
254    }
255    else if (state == InAttName) {
256      state = Clear;
257      int remain_lgth = bitstream_scan(NameFollows,0);
258      memcpy(&tags_buf[tags_buf_cur],srcbuf,remain_lgth);
259      if(lookup_or_insert(InAtt.start, InAtt.lgth+remain_lgth)){
260              fprintf(stderr,"Attribute name is not unique at position =%i.\n",buf_base);
261              exit(-1);
262      }
263    }
264  }
265}
266
267TagMatcher::TagMatcher(){
268  stream_index = 0;
269  depth = 0;
270  buf_base = 0;
271  state = Clear;
272  mode = StartOfFile;
273  InFinalEndTag = 0;
274  NameFollows[BUFFER_SIZE/BLOCK_SIZE]=simd_const_1(1);  //sentinel
275}
276
277TagMatcher::~TagMatcher(){
278
279}
280
281void TagMatcher::setSrc(char * src){
282  srcbuf = src;
283}
284
285void TagMatcher::Advance_buffer(){
286  buf_base += BUFFER_SIZE;
287  stream_index=0;
288  tags_buf_cur = 0;
289  att_index = 0;
290  for(int i=0; i< depth; i++){
291    if(&tags_buf[tags_buf_cur]!=tag_stack[i])
292      memcpy(&tags_buf[tags_buf_cur],tag_stack[i],tag_lgth_stack[i]);
293    tag_stack[i] = &tags_buf[tags_buf_cur];
294    tags_buf_cur += tag_lgth_stack[i];
295  }
296  if(state == InStartTag) {
297      memcpy(&tags_buf[tags_buf_cur],&srcbuf[finalStartPos],tag_lgth_stack[depth]);
298      tag_stack[depth] = &tags_buf[tags_buf_cur];
299      tags_buf_cur += tag_lgth_stack[depth];
300  }
301  else if(state == InEndTag) {
302     memcpy(&tags_buf[tags_buf_cur],tag_stack[depth],tag_lgth_stack[depth]);
303    tag_stack[depth] = &tags_buf[tags_buf_cur];
304    tags_buf_cur += tag_lgth_stack[depth];
305  }
306  else if(state == InAttName) {
307      memcpy(&tags_buf[tags_buf_cur],InAtt.start,InAtt.lgth);
308      InAtt.start = &tags_buf[tags_buf_cur];
309      tags_buf_cur += InAtt.lgth;
310  }
311  srcbuf[-1] = srcbuf[BUFFER_SIZE-1];
312}
313
Note: See TracBrowser for help on using the repository browser.