content: /*
   * Copyright (C) 2018 The Android Open Source Project
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *      http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  package com.android.server.backup.encryption.chunking.cdc;
  
  import static com.google.common.truth.Truth.assertThat;
  
  import static java.nio.charset.StandardCharsets.UTF_8;
  
  import android.platform.test.annotations.Presubmit;
  
  import com.google.common.collect.ImmutableList;
  import com.google.common.collect.ImmutableSet;
  
  import org.junit.Test;
  import org.junit.runner.RunWith;
  import org.robolectric.RobolectricTestRunner;
  
  /** Tests for {@link RabinFingerprint64}. */
  @RunWith(RobolectricTestRunner.class)
  @Presubmit
  public class RabinFingerprint64Test {
      private static final int WINDOW_SIZE = 31;
      private static final ImmutableList<String> TEST_STRINGS =
              ImmutableList.of(
                      "ervHTtChYXO6eXivYqThlyyzqkbRaOR",
                      "IxaVunH9ZC3qneWfhj1GkBH4ys9CYqz",
                      "wZRVjlE1p976icCFPX9pibk4PEBvjSH",
                      "pHIVaT8x8If9D6s9croksgNmJpmGYWI");
  
      private final RabinFingerprint64 mRabinFingerprint64 = new RabinFingerprint64();
  
      /**
       * No matter where in the input buffer a string occurs, {@link
       * RabinFingerprint64#computeFingerprint64(byte, byte, long)} should return the same
       * fingerprint.
       */
      @Test
      public void computeFingerprint64_forSameWindow_returnsSameFingerprint() {
          long fingerprint1 =
                  computeFingerprintAtPosition(getBytes(TEST_STRINGS.get(0)), WINDOW_SIZE - 1);
          long fingerprint2 =
                  computeFingerprintAtPosition(
                          getBytes(TEST_STRINGS.get(1), TEST_STRINGS.get(0)), WINDOW_SIZE * 2 - 1);
          long fingerprint3 =
                  computeFingerprintAtPosition(
                          getBytes(TEST_STRINGS.get(2), TEST_STRINGS.get(3), TEST_STRINGS.get(0)),
                          WINDOW_SIZE * 3 - 1);
          String stub = "abc";
          long fingerprint4 =
                  computeFingerprintAtPosition(
                          getBytes(stub, TEST_STRINGS.get(0)), WINDOW_SIZE + stub.length() - 1);
  
          // Assert that all fingerprints are exactly the same
          assertThat(ImmutableSet.of(fingerprint1, fingerprint2, fingerprint3, fingerprint4))
                  .hasSize(1);
      }
  
      /** The computed fingerprint should be different for different inputs. */
      @Test
      public void computeFingerprint64_withDifferentInput_returnsDifferentFingerprint() {
          long fingerprint1 = computeFingerprintOf(TEST_STRINGS.get(0));
          long fingerprint2 = computeFingerprintOf(TEST_STRINGS.get(1));
          long fingerprint3 = computeFingerprintOf(TEST_STRINGS.get(2));
          long fingerprint4 = computeFingerprintOf(TEST_STRINGS.get(3));
  
          assertThat(ImmutableList.of(fingerprint1, fingerprint2, fingerprint3, fingerprint4))
                  .containsNoDuplicates();
      }
  
      /**
       * An input with the same characters in a different order should return a different fingerprint.
       */
      @Test
      public void computeFingerprint64_withSameInputInDifferentOrder_returnsDifferentFingerprint() {
          long fingerprint1 = computeFingerprintOf("abcdefghijklmnopqrstuvwxyz12345");
          long fingerprint2 = computeFingerprintOf("54321zyxwvutsrqponmlkjihgfedcba");
          long fingerprint3 = computeFingerprintOf("4bcdefghijklmnopqrstuvwxyz123a5");
          long fingerprint4 = computeFingerprintOf("bacdefghijklmnopqrstuvwxyz12345");
  
          assertThat(ImmutableList.of(fingerprint1, fingerprint2, fingerprint3, fingerprint4))
                  .containsNoDuplicates();
      }
  
      /** UTF-8 bytes of all the given strings in order. */
      private byte[] getBytes(String... strings) {
          StringBuilder sb = new StringBuilder();
          for (String s : strings) {
              sb.append(s);
          }
          return sb.toString().getBytes(UTF_8);
      }
  
      /**
       * The Rabin fingerprint of a window of bytes ending at {@code position} in the {@code bytes}
       * array.
       */
      private long computeFingerprintAtPosition(byte[] bytes, int position) {
          assertThat(position).isAtMost(bytes.length - 1);
          long fingerprint = 0;
          for (int i = 0; i <= position; i++) {
              byte outChar;
              if (i >= WINDOW_SIZE) {
                  outChar = bytes[i - WINDOW_SIZE];
              } else {
                  outChar = (byte) 0;
              }
              fingerprint =
                      mRabinFingerprint64.computeFingerprint64(
                              /*inChar=*/ bytes[i], outChar, fingerprint);
          }
          return fingerprint;
      }
  
      private long computeFingerprintOf(String s) {
          assertThat(s.length()).isEqualTo(WINDOW_SIZE);
          return computeFingerprintAtPosition(s.getBytes(UTF_8), WINDOW_SIZE - 1);
      }
  }
  