com/android/server/backup/encryption/chunking/cdc/RabinFingerprint64.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;

/** Helper to calculate a 64-bit Rabin fingerprint over a 31-byte window. */
public class RabinFingerprint64 {
    private static final long DEFAULT_IRREDUCIBLE_POLYNOMIAL_64 = 0x000000000000001BL;
    private static final int POLYNOMIAL_DEGREE = 64;
    private static final int SLIDING_WINDOW_SIZE_BYTES = 31;

    private final long mPoly64;
    // Auxiliary tables to speed up the computation of Rabin fingerprints.
    private final long[] mTableFP64 = new long[256];
    private final long[] mTableOutByte = new long[256];

    /**
     * Constructs a new instance over the given irreducible 64-degree polynomial. It is up to the
     * caller to determine that the polynomial is irreducible. If it is not the fingerprinting will
     * not behave as expected.
     *
     * @param poly64 The polynomial.
     */
    public RabinFingerprint64(long poly64) {
        mPoly64 = poly64;
    }

    /** Constructs a new instance using {@code x^64 + x^4 + x + 1} as the irreducible polynomial. */
    public RabinFingerprint64() {
        this(DEFAULT_IRREDUCIBLE_POLYNOMIAL_64);
        computeFingerprintTables64();
        computeFingerprintTables64Windowed();
    }

    /**
     * Computes the fingerprint for the new sliding window given the fingerprint of the previous
     * sliding window, the byte sliding in, and the byte sliding out.
     *
     * @param inChar The new char coming into the sliding window.
     * @param outChar The left most char sliding out of the window.
     * @param fingerPrint Fingerprint for previous window.
     * @return New fingerprint for the new sliding window.
     */
    public long computeFingerprint64(byte inChar, byte outChar, long fingerPrint) {
        return (fingerPrint << 8)
                ^ (inChar & 0xFF)
                ^ mTableFP64[(int) (fingerPrint >>> 56)]
                ^ mTableOutByte[outChar & 0xFF];
    }

    /** Compute auxiliary tables to speed up the fingerprint computation. */
    private void computeFingerprintTables64() {
        long[] degreesRes64 = new long[POLYNOMIAL_DEGREE];
        degreesRes64[0] = mPoly64;
        for (int i = 1; i < POLYNOMIAL_DEGREE; i++) {
            if ((degreesRes64[i - 1] & (1L << 63)) == 0) {
                degreesRes64[i] = degreesRes64[i - 1] << 1;
            } else {
                degreesRes64[i] = (degreesRes64[i - 1] << 1) ^ mPoly64;
            }
        }
        for (int i = 0; i < 256; i++) {
            int currIndex = i;
            for (int j = 0; (currIndex > 0) && (j < 8); j++) {
                if ((currIndex & 0x1) == 1) {
                    mTableFP64[i] ^= degreesRes64[j];
                }
                currIndex >>>= 1;
            }
        }
    }

    /**
     * Compute auxiliary table {@code mTableOutByte} to facilitate the computing of fingerprints for
     * sliding windows. This table is to take care of the effect on the fingerprint when the
     * leftmost byte in the window slides out.
     */
    private void computeFingerprintTables64Windowed() {
        // Auxiliary array degsRes64[8] defined by: <code>degsRes64[i] = x^(8 *
        // SLIDING_WINDOW_SIZE_BYTES + i) mod this.mPoly64.</code>
        long[] degsRes64 = new long[8];
        degsRes64[0] = mPoly64;
        for (int i = 65; i < 8 * (SLIDING_WINDOW_SIZE_BYTES + 1); i++) {
            if ((degsRes64[(i - 1) % 8] & (1L << 63)) == 0) {
                degsRes64[i % 8] = degsRes64[(i - 1) % 8] << 1;
            } else {
                degsRes64[i % 8] = (degsRes64[(i - 1) % 8] << 1) ^ mPoly64;
            }
        }
        for (int i = 0; i < 256; i++) {
            int currIndex = i;
            for (int j = 0; (currIndex > 0) && (j < 8); j++) {
                if ((currIndex & 0x1) == 1) {
                    mTableOutByte[i] ^= degsRes64[j];
                }
                currIndex >>>= 1;
            }
        }
    }
}