com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64Test.java

/*
 * 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);
    }
}