source: proto/xmlschema/src/TagMatcher.h @ 2234

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