source: proto/parabix2/src/TagMatcher.hpp @ 1594

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

Updated TagMatcher?.hpp for IDISA.

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