- unsigned depth_remaining = max_search_depth;
- u32 hash;
- pos_t cur_node;
- const u8 *matchptr;
- pos_t *pending_lt_ptr, *pending_gt_ptr;
- unsigned best_lt_len, best_gt_len;
- unsigned len;
-
- if (unlikely(in_end - in_next < LZ_HASH3_REQUIRED_NBYTES + 1))
- return;
-
- hash = *next_hash;
- *next_hash = bt_matchfinder_hash_3_bytes(in_next + 1);
- cur_node = mf->hash_tab[hash];
- mf->hash_tab[hash] = in_next - in_begin;
- prefetch(&mf->hash_tab[*next_hash]);
-
- depth_remaining = max_search_depth;
- pending_lt_ptr = bt_left_child(mf, in_next - in_begin);
- pending_gt_ptr = bt_right_child(mf, in_next - in_begin);
- best_lt_len = 0;
- best_gt_len = 0;
- len = 0;
-
- if (!matchfinder_node_valid(cur_node)) {
- *pending_lt_ptr = MATCHFINDER_NULL;
- *pending_gt_ptr = MATCHFINDER_NULL;
- return;
- }
-
- for (;;) {
- matchptr = &in_begin[cur_node];
-
- if (matchptr[len] == in_next[len]) {
- len = lz_extend(in_next, matchptr, len + 1, nice_len);
- if (len == nice_len) {
- *pending_lt_ptr = *bt_left_child(mf, cur_node);
- *pending_gt_ptr = *bt_right_child(mf, cur_node);
- return;
- }
- }
-
- if (matchptr[len] < in_next[len]) {
- *pending_lt_ptr = cur_node;
- pending_lt_ptr = bt_right_child(mf, cur_node);
- cur_node = *pending_lt_ptr;
- best_lt_len = len;
- if (best_gt_len < len)
- len = best_gt_len;
- } else {
- *pending_gt_ptr = cur_node;
- pending_gt_ptr = bt_left_child(mf, cur_node);
- cur_node = *pending_gt_ptr;
- best_gt_len = len;
- if (best_lt_len < len)
- len = best_lt_len;
- }
-
- if (!matchfinder_node_valid(cur_node) || !--depth_remaining) {
- *pending_lt_ptr = MATCHFINDER_NULL;
- *pending_gt_ptr = MATCHFINDER_NULL;
- return;
- }
- }