source: proto/parabix2/src/TagMatcher_avx.h @ 1496

Last change on this file since 1496 was 972, checked in by cameron, 8 years ago

AVX version with separate files/template.

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