| 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) |
| 4530 | { |
| 4531 | for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) |
| 4532 | { |
| 4533 | DFA::State *next_state = edge.state(); |
| 4534 | // ignore states before the cut, since we don't use them for bitap and hashing |
| 4535 | if (lbk_ > 0 && next_state->first > 0 && next_state->first <= cut_) |
| 4536 | continue; |
| 4537 | // previous level hashes are completely saturated, or highly saturated after 4 levels, then next hashes will be saturated too |
| 4538 | bool next_saturated = saturated || (previous.first.size() == 1 && previous.first.lo() == 0 && previous.first.hi() == Const::HASH - 1); |
| 4539 | // next state is accepting (closed over metas) |
| 4540 | bool next_accept = edge.next_accepting(); |
| 4541 | std::pair<ORanges<Hash>,ORanges<Char> > *next_hashes = (level + 1 < Const::BITS && !next_accept) ? &level_hashes[next_state] : NULL; |
| 4542 | Char lo = edge.lo(); |
| 4543 | Char hi = edge.hi(); |
| 4544 | DBGLOG("PM level %hu %p: %u~%u %s%s", level, state, lo, hi, next_accept ? "accept " : "", next_hashes ? "nexthashes" : ""); |
| 4545 | if (level < min_) |
| 4546 | { |
| 4547 | // populate bit array |
| 4548 | Bitap mask = ~(1 << level); |
| 4549 | for (Char ch = lo; ch <= hi; ++ch) |
| 4550 | bit_[ch] &= mask; |
| 4551 | DBGLOG("%hu bitap %p: %u..%u -> %p", level, state, lo, hi, next_state); |
| 4552 | // update tap_[] bitap hashed pairs at previous level using previous character ranges |
| 4553 | mask >>= 1; |
| 4554 | for (ORanges<Char>::iterator prev_range = previous.second.begin(); prev_range != previous.second.end(); ++prev_range) |
| 4555 | { |
| 4556 | Char prev_lo = prev_range->first; |
| 4557 | Char prev_hi = prev_range->second; |
| 4558 | DBGLOG("tap %u~%u with %u~%u", prev_lo, prev_hi-1, lo, hi); |
| 4559 | for (Char ch = (lo << 6); ch <= (hi << 6); ch += (1 << 6)) |
| 4560 | for (Char prev_ch = prev_lo; prev_ch < prev_hi; ++prev_ch) |
| 4561 | tap_[(prev_ch ^ ch) & (Const::BTAP - 1)] &= mask; |
| 4562 | } |
| 4563 | if (level + 1 < min_) |
| 4564 | { |
| 4565 | // pass character range for bitap to the next state |
| 4566 | if (next_hashes != NULL) |
| 4567 | next_hashes->second.insert(lo, hi); |
| 4568 | } |
| 4569 | else |
| 4570 | { |
| 4571 | // this is the last state to populate bitap |
| 4572 | mask = ~(1 << level); |
| 4573 | if (next_accept) |
| 4574 | { |
| 4575 | // last tap_[] when accepting is hashed with all 256 possible next characters |
| 4576 | DBGLOG("tap %u~%u as accepting", lo, hi); |
| 4577 | for (Char last_ch = lo; last_ch <= hi; ++last_ch) |
| 4578 | for (Char ch = (last_ch & ((1 << 6) - 1)); ch < Const::BTAP; ch += (1 << 6)) |
| 4579 | tap_[ch] &= mask; |
| 4580 | } |
| 4581 | else |
| 4582 | { |
| 4583 | // hash all characters on edges from this state, to improve prediction accuracy |
| 4584 | for (DFA::MetaEdgesClosure next_edge(next_state); !next_edge.done(); ++next_edge) |
| 4585 | { |
| 4586 | Char next_lo = next_edge.lo(); |