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

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

boolean does_match function instead of cal_match_len

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