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

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

tag stack storing positions instead of strings

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