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

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

Removed cfzl.

File size: 8.5 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
80        scanword_t temp = ~hsimd128<8>::signmask(simd<8>::eq(bitblock::load_unaligned((BitBlock*)&s1[i]),
81                                                  bitblock::load_unaligned((BitBlock*)&s2[i])));
82
83        if(temp > 0) {
84        if (lgth > scan_forward_zeroes(temp)){
85                return 0;
86                }
87        }
88    else {
89                return 1;
90        }
91}
92
93
94int TagMatcher:: tag_match(int pos, int chars_avail) {
95        int rt_val=0;
96//      end tag
97        if(srcbuf[pos]=='/' ){
98          pos++;
99          depth--;
100          if (depth<0)
101            return pos;
102          int lgth = tag_lgth_stack[depth];
103
104          if (does_match(tag_stack[depth],&srcbuf[pos],lgth) && ((srcbuf[pos+lgth] == '>') ||(srcbuf[pos+lgth] <= ' '))) rt_val=0;
105          else if (pos + lgth >= BUFFER_SIZE + OVERLAP_BUFSIZE) {
106            state = InEndTag;
107            inTagPos = BUFFER_SIZE - pos;
108            rt_val=0;
109          }
110          else {
111//            cout << "end tag is " << string(&srcbuf[pos],tag_lgth_stack[depth]) << endl ;
112//            cout << "start tag is " << string(tag_stack[depth],tag_lgth_stack[depth]) << endl ;
113              fprintf(stderr,"tag name mismatch at position = %i\n",buf_base+pos);
114              exit(-1);
115          }
116
117          if (depth == 0){
118            while(srcbuf[pos]!='>'){
119              pos++;
120              if(pos>=chars_avail){
121                InFinalEndTag = 1;
122                return 0;
123              }
124            }
125            pos = bitstream_scan(miscMarks,pos+1);
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          return rt_val;
132        }
133//      empty tag
134        else if(srcbuf[pos]=='>'){
135          depth--;
136          if (depth == 0){
137            while(srcbuf[pos]!='>')
138              pos++;
139            pos = bitstream_scan(miscMarks,pos+1);
140
141            if(pos!=chars_avail){
142              fprintf(stderr,"illegal content after root element at position = %i\n",buf_base+pos);
143              exit(-1);
144            }
145          }
146        }
147//      start tag
148        else if(srcbuf[pos-1]=='<'){
149          att_index = 0;
150          if(depth<MAX_DEPTH){
151            int end_pos = bitstream_scan(NameFollows,pos);
152            tag_lgth_stack[depth] = end_pos-pos;
153            tag_stack[depth] = &srcbuf[pos];
154            if(end_pos<BUFFER_SIZE){
155              depth++;
156            }
157            else{
158              state = InStartTag;
159              finalStartPos = pos;
160            }
161          }
162          else{
163            fprintf(stderr,"Max nesting depth exceeded at position =%i. depth = %i\n",buf_base+pos, depth);
164            exit(-1);
165          }
166        }
167//      attribute
168        else{
169          int end_pos = bitstream_scan(NameFollows,pos);
170          if(end_pos<BUFFER_SIZE){
171            if(lookup_or_insert(&srcbuf[pos], end_pos-pos)){
172              fprintf(stderr,"Attribute name is not unique at position =%i.\n",buf_base+pos);
173              exit(-1);
174            }
175          }
176          else{
177            state = InAttName;
178            InAtt.start = &srcbuf[pos];
179            InAtt.lgth = BUFFER_SIZE-pos;
180          }
181        }
182        return 0;
183}
184
185
186int TagMatcher::StreamScan(int chars_avail) {
187
188        int blk;
189        int blk_counts = (chars_avail+sizeof(scanword_t)*8-1)/(sizeof(scanword_t)*8);
190        int block_pos = 0;
191
192        if(mode == StartOfFile){
193          int pos = bitstream_scan(miscMarks,0);
194          if (pos==chars_avail){
195            fprintf(stderr,"no element at position =%i.\n",buf_base+pos);
196            exit(-1);
197          }
198          if(srcbuf[pos-1]!='<'|| srcbuf[pos]=='!'||srcbuf[pos]=='/'){
199#ifdef DUMP
200print_register<BitBlock>("srcbuf", bitblock::load_unaligned((BitBlock *) srcbuf));
201#endif
202            fprintf(stderr,"illegal content before root element at position =%i.\n",buf_base+pos);
203            exit(-1);
204          }
205          mode = InFile;
206        }
207        for (blk = 0; blk < blk_counts; blk++) {
208                scanword_t s = ((scanword_t*)tagMarks)[blk];
209                while(s) {
210                        int code = tag_match(scan_forward_zeroes(s) + block_pos, chars_avail);
211                        if (code) return code;
212                        s = s & (s-1);  // clear rightmost bit.
213                }
214                block_pos += 8 * sizeof(scanword_t);
215        }
216
217        return 0;
218}
219
220void TagMatcher::store_streams(BitBlock tagMark, BitBlock NameFollow, BitBlock miscMark, int chars_avail){
221#ifdef DUMP
222print_register<BitBlock>("tagMark", tagMark);
223print_register<BitBlock>("NameFollow", NameFollow);
224print_register<BitBlock>("miscMark", miscMark);
225printf("chars_avail = %i\n", chars_avail);
226printf("stream_index = %i\n", stream_index);
227#endif
228  tagMarks[stream_index] = tagMark;
229  miscMarks[stream_index] = simd_not(miscMark);
230  NameFollows[stream_index] = NameFollow;
231  stream_index++;
232  if(stream_index==1){
233
234    if (InFinalEndTag == 1){
235      int pos = -1;
236      while(srcbuf[pos]!='>'){
237        pos++;
238        if(pos>=chars_avail){
239          InFinalEndTag = 1;
240          return;
241        }
242      }
243      pos = bitstream_scan(miscMarks,pos+1);
244#ifdef DUMP
245print_register<BitBlock>("miscMarks[0]", miscMarks[0]);
246printf("pos = %i\n", pos);
247#endif
248      if(pos!=chars_avail){
249        fprintf(stderr,"illegal content after root element at position = %i\n",buf_base+pos);
250        exit(-1);
251      }
252    }
253
254    if(state == InStartTag) {
255      state = Clear;
256      int remain_lgth = bitstream_scan(NameFollows,0);
257      memcpy(&tags_buf[tags_buf_cur],srcbuf,remain_lgth);
258      tag_lgth_stack[depth] += remain_lgth;
259      depth++;
260    }
261    else if (state == InEndTag) {
262      state = Clear;
263      int lgth = tag_lgth_stack[depth];
264      if (does_match(tag_stack[depth]+inTagPos,srcbuf,lgth-inTagPos) && ((srcbuf[lgth-inTagPos] == '>') ||(srcbuf[lgth-inTagPos] <= ' '))) return ;
265      else {
266          fprintf(stderr,"tag name mismatch at position = %i\n",buf_base);
267          exit(-1);
268      }
269    }
270    else if (state == InAttName) {
271      state = Clear;
272      int remain_lgth = bitstream_scan(NameFollows,0);
273      memcpy(&tags_buf[tags_buf_cur],srcbuf,remain_lgth);
274      if(lookup_or_insert(InAtt.start, InAtt.lgth+remain_lgth)){
275              fprintf(stderr,"Attribute name is not unique at position =%i.\n",buf_base);
276              exit(-1);
277      }
278    }
279  }
280}
281
282TagMatcher::TagMatcher(){
283  stream_index = 0;
284  depth = 0;
285  buf_base = 0;
286  state = Clear;
287  mode = StartOfFile;
288  InFinalEndTag = 0;
289  NameFollows[BUFFER_SIZE/BLOCK_SIZE]=simd<1>::constant<1>();// TODO - verify simd_const_1(1);  //sentinel
290}
291
292
293
294TagMatcher::~TagMatcher(){
295
296}
297
298void TagMatcher::setSrc(char * src){
299  srcbuf = src;
300}
301
302void TagMatcher::Advance_buffer(){
303  buf_base += BUFFER_SIZE;
304  stream_index=0;
305  tags_buf_cur = 0;
306  att_index = 0;
307  for(int i=0; i< depth; i++){
308    if(&tags_buf[tags_buf_cur]!=tag_stack[i])
309      memcpy(&tags_buf[tags_buf_cur],tag_stack[i],tag_lgth_stack[i]);
310    tag_stack[i] = &tags_buf[tags_buf_cur];
311    tags_buf_cur += tag_lgth_stack[i];
312  }
313  if(state == InStartTag) {
314      memcpy(&tags_buf[tags_buf_cur],&srcbuf[finalStartPos],tag_lgth_stack[depth]);
315      tag_stack[depth] = &tags_buf[tags_buf_cur];
316      tags_buf_cur += tag_lgth_stack[depth];
317  }
318  else if(state == InEndTag) {
319     memcpy(&tags_buf[tags_buf_cur],tag_stack[depth],tag_lgth_stack[depth]);
320    tag_stack[depth] = &tags_buf[tags_buf_cur];
321    tags_buf_cur += tag_lgth_stack[depth];
322  }
323  else if(state == InAttName) {
324      memcpy(&tags_buf[tags_buf_cur],InAtt.start,InAtt.lgth);
325      InAtt.start = &tags_buf[tags_buf_cur];
326      tags_buf_cur += InAtt.lgth;
327  }
328  srcbuf[-1] = srcbuf[BUFFER_SIZE-1];
329}
330
331#endif /* TAGMATCHER_HPP_ */
Note: See TracBrowser for help on using the repository browser.