test_class.file: feya/libraries/archive_diff/diff.generator/src/test/java/com/google/archivepatcher/generator/bsdiff/BsDiffTest.java
test_class.identifier: BsDiffTest
test_case.body: @Test
    public void searchForMatch() throws Exception {
      String[] testCases = {
        "a",
        "aa",
        "az",
        "za",
        "aaaaa",
        "CACAO",
        "banana",
        "tobeornottobe",
        "the quick brown fox jumps over the lazy dog.",
        "elephantelephantelephantelephantelephant",
        "011010011001011010010110011010010",
      };
      for (String testCase : testCases) {
        int size = testCase.length();
        byte[] bytes = testCase.getBytes(StandardCharsets.US_ASCII);
        RandomAccessObject input = new RandomAccessObject.RandomAccessByteArrayObject(bytes);
        RandomAccessObject suffixArray =
            new DivSuffixSorter(new RandomAccessObjectFactory.RandomAccessByteArrayObjectFactory())
                .suffixSort(input);
  
        // Test exact matches for every non-empty substring.
        for (int lo = 0; lo < size; ++lo) {
          for (int hi = lo + 1; hi <= size; ++hi) {
            byte[] query = Arrays.copyOfRange(bytes, lo, hi);
            int querySize = query.length;
            Assert.assertEquals(querySize, hi - lo);
            RandomAccessObject queryBuf = new RandomAccessObject.RandomAccessByteArrayObject(query);
  
            BsDiff.Match match = BsDiff.searchForMatch(suffixArray, input, queryBuf, 0, 0, size);
  
            Assert.assertEquals(querySize, match.length);
            Assert.assertTrue(match.start >= 0);
            Assert.assertTrue(match.start <= size - match.length);
            byte[] suffix = Arrays.copyOfRange(bytes, match.start, match.start + match.length);
            Assert.assertArrayEquals(query, suffix);
          }
        }
      }
    }
test_case.class_method_signature: BsDiffTest.searchForMatch()
test_case.full_signature: @Test public void searchForMatch()
test_case.identifier: searchForMatch
test_case.invocations: length getBytes suffixSort copyOfRange assertEquals searchForMatch assertEquals assertTrue assertTrue copyOfRange assertArrayEquals
test_case.modifiers: @Test public
test_case.parameters: ()
test_case.return: void
test_case.signature: void searchForMatch()
focal_class.file: feya/libraries/archive_diff/diff.generator/src/main/java/com/google/archivepatcher/generator/bsdiff/BsDiff.java
focal_class.identifier: BsDiff
focal_class.class_method_signature: BsDiff.lengthOfMatch(
        final RandomAccessObject oldData,
        final int oldStart,
        final RandomAccessObject newData,
        final int newStart)
focal_class.full_signature: static int lengthOfMatch(
        final RandomAccessObject oldData,
        final int oldStart,
        final RandomAccessObject newData,
        final int newStart)
focal_class.identifier: lengthOfMatch
focal_class.modifiers: static
focal_class.parameters: (
        final RandomAccessObject oldData,
        final int oldStart,
        final RandomAccessObject newData,
        final int newStart)
focal_class.return: int
focal_class.signature: int lengthOfMatch(
        final RandomAccessObject oldData,
        final int oldStart,
        final RandomAccessObject newData,
        final int newStart)
focal_class.class_method_signature: BsDiff.searchForMatchBaseCase(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_class.full_signature: static Match searchForMatchBaseCase(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_class.identifier: searchForMatchBaseCase
focal_class.modifiers: static
focal_class.parameters: (
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_class.return: Match
focal_class.signature: Match searchForMatchBaseCase(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_class.class_method_signature: BsDiff.searchForMatch(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_class.full_signature: static Match searchForMatch(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_class.identifier: searchForMatch
focal_class.modifiers: static
focal_class.parameters: (
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_class.return: Match
focal_class.signature: Match searchForMatch(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_method.body: static Match searchForMatch(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
        throws IOException {
      if (oldDataRangeStartB - oldDataRangeStartA < 2) {
        return searchForMatchBaseCase(
            groupArray, oldData, newData, newStart, oldDataRangeStartA, oldDataRangeStartB);
      }
  
      // Cut range in half and search again
      final int rangeLength = oldDataRangeStartB - oldDataRangeStartA;
      final int pivot = oldDataRangeStartA + (rangeLength / 2);
      groupArray.seekToIntAligned(pivot);
      final int groupArrayPivot = groupArray.readInt();
      if (BsUtil.lexicographicalCompare(
              oldData,
              groupArrayPivot,
              (int) oldData.length() - groupArrayPivot,
              newData,
              newStart,
              (int) newData.length() - newStart)
          < 0) {
        return searchForMatch(groupArray, oldData, newData, newStart, pivot, oldDataRangeStartB);
      }
      return searchForMatch(groupArray, oldData, newData, newStart, oldDataRangeStartA, pivot);
    }
focal_method.class_method_signature: BsDiff.searchForMatch(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_method.full_signature: static Match searchForMatch(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_method.identifier: searchForMatch
focal_method.invocations: searchForMatchBaseCase seekToIntAligned readInt lexicographicalCompare length length searchForMatch searchForMatch
focal_method.modifiers: static
focal_method.parameters: (
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)
focal_method.return: Match
focal_method.signature: Match searchForMatch(
        final RandomAccessObject groupArray,
        final RandomAccessObject oldData,
        final RandomAccessObject newData,
        final int newStart,
        final int oldDataRangeStartA,
        final int oldDataRangeStartB)