BlockHash { public void FindBestMatch(int hash_value, ByteBuffer target, Match best_match) { int match_counter = 0; for (int block_number = FirstMatchingBlock(hash_value, target.array(), target.arrayOffset() + target.position()); (block_number >= 0) && !(++match_counter > kMaxMatchesToCheck); block_number = NextMatchingBlock(block_number, target.array(), target.arrayOffset() + target.position())) { int source_match_offset = block_number * kBlockSize; final int source_match_end = source_match_offset + kBlockSize; int target_match_offset = target.position(); final int target_match_end = target_match_offset + kBlockSize; int match_size = kBlockSize; { final int limit_bytes_to_left = Math.min(source_match_offset, target_match_offset); final int matching_bytes_to_left = MatchingBytesToLeft( source_data, source_match_offset, target.array(), target.arrayOffset() + target_match_offset, limit_bytes_to_left); source_match_offset -= matching_bytes_to_left; target_match_offset -= matching_bytes_to_left; match_size += matching_bytes_to_left; } { final int source_bytes_to_right = source_data.limit() - source_match_end; final int target_bytes_to_right = target.limit() - target_match_end; final int limit_bytes_to_right = Math.min(source_bytes_to_right, target_bytes_to_right); match_size += MatchingBytesToRight( source_data, source_match_end, target.array(), target.arrayOffset() + target_match_end, limit_bytes_to_right); } best_match.ReplaceIfBetterMatch(match_size, source_match_offset + starting_offset, target_match_offset); } } BlockHash(byte[] source_data, int starting_offset, boolean populate_hash_table);  BlockHash(ByteBuffer source_data, int starting_offset, boolean populate_hash_table); static BlockHash CreateDictionaryHash(byte[] dictionary_data); static BlockHash CreateTargetHash(byte[] target_data, int dictionary_size); static BlockHash CreateTargetHash(ByteBuffer target_data, int dictionary_size); void AddOneIndexHash(int index, int hash_value); void AddAllBlocksThroughIndex(int end_index); void FindBestMatch(int hash_value, ByteBuffer target, Match best_match); void FindBestMatch(int hash_value, byte[] target_candidate, int target_candidate_start, byte[] target, int target_start, Match best_match); static final int kBlockSize; }
@Test public void FindBestMatch() { BlockHash dh_ = BlockHash.CreateDictionaryHash(sample_text); BlockHash.Match best_match = new BlockHash.Match(); dh_.FindBestMatch( (int) hashed_f, search_string, index_of_f_in_fearsome, search_string, 0, best_match); Assert.assertEquals(index_of_longest_match_ear_is_fear, best_match.source_offset()); Assert.assertEquals(index_of_second_e_in_what_we_hear, best_match.target_offset()); Assert.assertEquals(("ear is fear".getBytes(StandardCharsets.US_ASCII).length * kBlockSize) + (kBlockSize - 1), best_match.size()); }
@Test public void FindBestMatchWithStartingOffset() throws UnsupportedEncodingException { BlockHash th2 = new BlockHash(sample_text, 0x10000, true); BlockHash.Match best_match = new BlockHash.Match(); th2.FindBestMatch((int) hashed_f, search_string, index_of_f_in_fearsome, search_string, 0, best_match); Assert.assertEquals(0x10000 + (index_of_longest_match_ear_is_fear), best_match.source_offset()); Assert.assertEquals(index_of_second_e_in_what_we_hear, best_match.target_offset()); Assert.assertEquals(("ear is fear".getBytes(StandardCharsets.US_ASCII).length * kBlockSize) + (kBlockSize - 1), best_match.size()); }
@Test public void BestMatchWithManyMatches() { RollingHash rollingHash = new RollingHash(kBlockSize); BlockHash.Match best_match = new BlockHash.Match(); BlockHash many_matches_hash = new BlockHash(sample_text_many_matches, 0, true); long hash_value = rollingHash.Hash(search_string_many_matches, 0, search_string_many_matches.length); many_matches_hash.FindBestMatch((int) hash_value, search_string_many_matches, 0, search_string_many_matches, 0, best_match); Assert.assertEquals(index_of_ababc, best_match.source_offset()); Assert.assertEquals(0, best_match.target_offset()); Assert.assertEquals(search_string_many_matches.length, best_match.size()); }
@Test public void SearchStringFindsTooManyMatches() { final int kTestSize = 1 << 20; byte[] huge_dictionary = new byte[kTestSize]; Arrays.fill(huge_dictionary, (byte) 'Q'); BlockHash huge_bh = new BlockHash(huge_dictionary, 0, true); byte[] huge_target = new byte[kTestSize]; Arrays.fill(huge_target, (byte) 'Q'); long time = System.nanoTime(); BlockHash.Match best_match = new BlockHash.Match(); huge_bh.FindBestMatch((int) hashed_all_Qs, huge_target, (kTestSize / 2), huge_target, 0, best_match); time = System.nanoTime() - time; double elapsed_time_in_us = time / 1000.0; System.out.printf("Time to search for best match with 1M matches: %.3f μs\n", elapsed_time_in_us); Assert.assertTrue((kTestSize / 2) > best_match.source_offset()); Assert.assertTrue((kTestSize / 2) > best_match.target_offset()); Assert.assertTrue((kTestSize / 2) < best_match.size()); Assert.assertTrue(5000000 > elapsed_time_in_us); Assert.assertTrue(1000000 > elapsed_time_in_us); }