| 4470 | } |
| 4471 | |
| 4472 | void Pattern::gen_predict_match_start(std::set<DFA::State*>& states, std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >& first_hashes) |
| 4473 | { |
| 4474 | for (std::set<DFA::State*>::iterator it = states.begin(); it != states.end(); ++it) |
| 4475 | { |
| 4476 | DFA::State *state = *it; |
| 4477 | for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) |
| 4478 | { |
| 4479 | DFA::State *next_state = edge.state(); |
| 4480 | // ignore states before the cut, since we don't use them for bitap and hashing |
| 4481 | if (lbk_ > 0 && next_state->first > 0 && next_state->first <= cut_) |
| 4482 | continue; |
| 4483 | bool next_accept = edge.next_accepting(); |
| 4484 | Char lo = edge.lo(); |
| 4485 | Char hi = edge.hi(); |
| 4486 | DBGLOG("PM start %p: %u~%u %s", state, lo, hi, next_accept ? "accept" : ""); |
| 4487 | first_hashes[next_state].first.insert(lo, hi); |
| 4488 | Pred pma_mask = ~(1 << (8 * sizeof(Pred) - 2)); |
| 4489 | if (next_accept) |
| 4490 | pma_mask &= ~(1 << (8 * sizeof(Pred) - 1)); |
| 4491 | for (Char ch = lo; ch <= hi; ++ch) |
| 4492 | { |
| 4493 | bit_[ch] &= ~1; |
| 4494 | pma_[ch] &= pma_mask; |
| 4495 | } |
| 4496 | // this is the first and last state to populate bitap |
| 4497 | if (min_ <= 1) |
| 4498 | { |
| 4499 | if (next_accept) |
| 4500 | { |
| 4501 | // last tap_[] when accepting is hashed with all 256 possible next characters |
| 4502 | DBGLOG("tap %u~%u as accepting", lo, hi); |
| 4503 | for (Char last_ch = lo; last_ch <= hi; ++last_ch) |
| 4504 | for (Char ch = (last_ch & ((1 << 6) - 1)); ch < Const::BTAP; ch += (1 << 6)) |
| 4505 | tap_[ch] &= ~1; |
| 4506 | } |
| 4507 | else |
| 4508 | { |
| 4509 | // hash all characters on edges from this state, to improve prediction accuracy |
| 4510 | for (DFA::MetaEdgesClosure next_edge(next_state); !next_edge.done(); ++next_edge) |
| 4511 | { |
| 4512 | Char next_lo = next_edge.lo(); |
| 4513 | Char next_hi = next_edge.hi(); |
| 4514 | DBGLOG("tap %u~%u with %u~%u", lo, hi, next_lo, next_hi); |
| 4515 | for (Char next_ch = (next_lo << 6); next_ch <= (next_hi << 6); next_ch += (1 << 6)) |
| 4516 | for (Char ch = lo; ch <= hi; ++ch) |
| 4517 | tap_[(ch ^ next_ch) & (Const::BTAP - 1)] &= ~1; |
| 4518 | } |
| 4519 | } |
| 4520 | } |
| 4521 | DBGLOG("0 bitap %u..%u -> %p", lo, hi, next_state); |
| 4522 | } |
| 4523 | } |
| 4524 | // ranges are the same characters for the start state |
| 4525 | for (std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >::iterator it = first_hashes.begin(); it != first_hashes.end(); ++it) |
| 4526 | it->second.second = it->second.first; |
| 4527 | } |
| 4528 | |
| 4529 | void Pattern::gen_predict_match_transitions(uint16_t level, DFA::State *state, const std::pair<ORanges<Hash>,ORanges<Char> >& previous, std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >& level_hashes, bool& saturated) |