1 /*
2  * Copyright (C) 2018 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.server.backup.encryption.chunking.cdc;
18 
19 import static com.android.internal.util.Preconditions.checkArgument;
20 
21 import com.android.server.backup.encryption.chunking.cdc.ContentDefinedChunker.BreakpointPredicate;
22 
23 /**
24  * Function to determine whether a 64-bit fingerprint ought to be a chunk breakpoint.
25  *
26  * <p>This works by checking whether there are at least n leading zeros in the fingerprint. n is
27  * calculated to on average cause a breakpoint after a given number of trials (provided in the
28  * constructor). This allows us to choose a number of trials that gives a desired average chunk
29  * size. This works because the fingerprint is pseudo-randomly distributed.
30  */
31 public class IsChunkBreakpoint implements BreakpointPredicate {
32     private final int mLeadingZeros;
33     private final long mBitmask;
34 
35     /**
36      * A new instance that causes a breakpoint after a given number of trials on average.
37      *
38      * @param averageNumberOfTrialsUntilBreakpoint The number of trials after which on average to
39      *     create a new chunk. If this is not a power of 2, some precision is sacrificed (i.e., on
40      *     average, breaks will actually happen after the nearest power of 2 to the average number
41      *     of trials passed in).
42      */
IsChunkBreakpoint(long averageNumberOfTrialsUntilBreakpoint)43     public IsChunkBreakpoint(long averageNumberOfTrialsUntilBreakpoint) {
44         checkArgument(
45                 averageNumberOfTrialsUntilBreakpoint >= 0,
46                 "Average number of trials must be non-negative");
47 
48         // Want n leading zeros after t trials.
49         // P(leading zeros = n) = 1/2^n
50         // Expected num trials to get n leading zeros = 1/2^-n
51         // t = 1/2^-n
52         // n = log2(t)
53         mLeadingZeros = (int) Math.round(log2(averageNumberOfTrialsUntilBreakpoint));
54         mBitmask = ~(~0L >>> mLeadingZeros);
55     }
56 
57     /**
58      * Returns {@code true} if {@code fingerprint} indicates that there should be a chunk
59      * breakpoint.
60      */
61     @Override
isBreakpoint(long fingerprint)62     public boolean isBreakpoint(long fingerprint) {
63         return (fingerprint & mBitmask) == 0;
64     }
65 
66     /** Returns the number of leading zeros in the fingerprint that causes a breakpoint. */
getLeadingZeros()67     public int getLeadingZeros() {
68         return mLeadingZeros;
69     }
70 
71     /**
72      * Calculates log base 2 of x. Not the most efficient possible implementation, but it's simple,
73      * obviously correct, and is only invoked on object construction.
74      */
log2(double x)75     private static double log2(double x) {
76         return Math.log(x) / Math.log(2);
77     }
78 }
79