source: proto/parabix2/src/tag_matcher.cpp @ 595

Last change on this file since 595 was 595, checked in by lindanl, 9 years ago

fixed tag matching error at buffer boundary

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