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

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

fixed empty tag matching

File size: 4.8 KB
Line 
1
2#define MAX_DEPTH 100
3#include <algorithm>
4#include <iostream>
5using namespace std;
6
7class tag_matcher {
8  public:
9  SIMD_type tagMarks[BUFFER_SIZE/BLOCK_SIZE];
10  int stream_index;
11  char * srcbuf;
12  int depth;
13  SIMD_type tag_stack[MAX_DEPTH]; 
14  int tag_lgth_stack[MAX_DEPTH];
15  SIMD_type tagNameFollows[BUFFER_SIZE/BLOCK_SIZE+1]; // 1 extra block for sentinel
16  int buf_base;
17  enum TagMatchState {InStartTag, InEndTag, Clear} state; 
18  int inTagpos;
19  int rem_lgth;
20 
21  tag_matcher(char * src);
22  ~tag_matcher(); 
23  int StreamScan(int chars_avail);
24  void store_streams(SIMD_type tagMark, SIMD_type tagNameFollow);
25  int tag_match(int pos);
26  int calc_match_len(SIMD_type * s, char * c, int lgth);
27  void Advance_buffer();
28};
29
30int tag_matcher::calc_match_len(SIMD_type * s, char * c, int lgth){
31    int matchlen = 0; 
32    int i=0;
33    while (lgth > 16) {
34      /* full 16 byte match */
35      if (simd_all_eq_8(s[i], sisd_load_unaligned((SIMD_type*)&c[i*sizeof(SIMD_type)]))) {
36        lgth -= sizeof(SIMD_type);
37        matchlen += sizeof(SIMD_type);
38        i++;
39      }
40      else {
41        return -1;
42      }
43    }
44    matchlen += cfzl(~_mm_movemask_epi8(simd_eq_8(s[i], sisd_load_unaligned((SIMD_type*)&c[i*sizeof(SIMD_type)])))); 
45    return matchlen;
46}
47
48int tag_matcher:: tag_match(int pos) {
49        int lgth;
50        int matchlen;
51        int i;
52        int to_match;
53        int new_depth;
54//      printf("%c\n",srcbuf[pos]);
55        if(srcbuf[pos]=='/' ){
56          pos++;
57          depth--;
58          if (depth<0)
59            return pos;
60          lgth = tag_lgth_stack[depth];
61          to_match = min(lgth,BUFFER_SIZE - pos);
62          depth -= ((lgth-1)/16);
63          matchlen = calc_match_len(&tag_stack[depth], &srcbuf[pos], to_match);
64          if (matchlen > lgth) return 0;
65          else if ((matchlen == lgth) && ((srcbuf[pos+matchlen] == '>') ||(srcbuf[pos+matchlen] <= ' '))) return 0;
66          else if (pos + matchlen >= BUFFER_SIZE) {
67            inTagpos = matchlen;
68            rem_lgth = lgth-matchlen;
69            state = InEndTag;
70          }
71          else {
72              fprintf(stderr,"tag name mismatch at position = %i\n",buf_base+pos);
73              exit(-1);
74          }
75        }
76        else if(srcbuf[pos]=='>'){       
77          depth--;
78          lgth = tag_lgth_stack[depth];
79          depth -= ((lgth-1)/16);
80        }
81        else {
82         
83          int end_pos = bitstream_scan(tagNameFollows,pos);
84          int lgth = end_pos-pos;
85          new_depth = depth + (lgth+15)/16;
86          if(new_depth<MAX_DEPTH){         
87            int d = depth;
88            lgth = min(lgth, BUFFER_SIZE - pos);
89            for (i = 0; i < (lgth-1)/16; i++) {
90              tag_stack[d] = sisd_load_unaligned((SIMD_type*)&srcbuf[pos+i*sizeof(SIMD_type)]);
91              d++;
92            }
93
94            tag_stack[d] = sisd_load_unaligned((SIMD_type*)&srcbuf[pos+i*sizeof(SIMD_type)]);   
95           
96            if(end_pos<BUFFER_SIZE){
97              depth = new_depth;
98              tag_lgth_stack[depth-1] = lgth;
99            }
100            else{
101              state = InStartTag;
102              inTagpos = BUFFER_SIZE - pos;
103            } 
104          }
105          else{
106            fprintf(stderr,"Max nesting depth exceeded at position =%i. depth = %i\n",buf_base+pos, depth);
107            exit(-1);
108          }
109        }
110        return 0;
111}
112
113
114int tag_matcher::StreamScan(int chars_avail) {
115 
116        int blk;
117        int blk_counts = (chars_avail-1)/(sizeof(ScanBlock)*8)+1;
118        int block_pos = 0;
119       
120        for (blk = 0; blk < blk_counts; blk++) {
121                ScanBlock s = ((ScanBlock*)tagMarks)[blk];
122                while(s) {
123                        int code = (tag_match(cfzl(s) + block_pos));
124                        if (code) return code;
125                        s = s & (s-1);  // clear rightmost bit.
126                }
127                block_pos += 8 * sizeof(ScanBlock);
128        }
129
130        return 0;
131} 
132
133void tag_matcher::store_streams(SIMD_type tagMark, SIMD_type tagNameFollow){
134 
135  SIMD_type tag_tmp_stack[MAX_DEPTH];
136  tagMarks[stream_index] = tagMark;
137  tagNameFollows[stream_index] = tagNameFollow;
138  stream_index++;
139  if(stream_index==1){
140    if(state == InStartTag) {     
141      state = Clear;
142      int remain_lgth = bitstream_scan(tagNameFollows,0);
143      int lgth = inTagpos + remain_lgth;
144//       new_depth = depth + (lgth+15)/16;
145      char * tag_stack_ptr = (char *) &tag_stack[depth];
146      memcpy((void*)&tag_stack_ptr[inTagpos],(void*)srcbuf,remain_lgth);
147      depth = depth + (lgth+15)/16;
148      tag_lgth_stack[depth-1] = lgth;
149    }
150    else if (state == InEndTag) {
151     
152      char * tag_stack_ptr = (char *) &tag_stack[depth];
153      for(int i=0;i<=rem_lgth/16;i++)
154        tag_tmp_stack[i] = sisd_load_unaligned((SIMD_type*)&tag_stack_ptr[inTagpos]);
155      int matchlen = calc_match_len(tag_tmp_stack, srcbuf, rem_lgth);
156      state = Clear;
157      if (matchlen > rem_lgth) return ;
158      else if ((matchlen == rem_lgth) && ((srcbuf[matchlen] == '>') ||(srcbuf[matchlen] <= ' '))) return;
159      else {
160          fprintf(stderr,"tag name mismatch at position = %i\n",buf_base);
161          exit(-1);
162      }
163    }
164  } 
165}
166
167tag_matcher::tag_matcher(char * src){
168  stream_index = 0;
169  depth = 0;
170  srcbuf = src;
171  buf_base = 0;
172  state = Clear;
173  tagNameFollows[BUFFER_SIZE/BLOCK_SIZE]=simd_const_1(1);  //sentinel
174}
175
176tag_matcher::~tag_matcher(){
177 
178}
179
180void tag_matcher::Advance_buffer(){
181  buf_base += BUFFER_SIZE;
182  stream_index=0;
183}
Note: See TracBrowser for help on using the repository browser.