android-34/com/google/android/rappor/Encoder.java - platform/prebuilts/fullsdk/sources - Git at Google

 package com.google.android.rappor;

 // BEGIN android-changed: Removed guava dependency
 // import static com.google.common.base.Preconditions.checkArgument;
 //
 // import com.google.common.base.Verify;
 // END android-changed

 import java.nio.ByteBuffer;
 import java.nio.charset.StandardCharsets;
 import java.security.MessageDigest;
 import java.security.NoSuchAlgorithmException;
 import java.security.SecureRandom;
 import java.util.BitSet;
 // BEGIN android-changed
 import java.util.Random;
 // END android-changed

 // BEGIN android-changed: Remove javax
 // import javax.annotation.Nullable;
 // import javax.annotation.concurrent.GuardedBy;
 // END android-changed

 /**
  * Encodes reports using the RAPPOR differentially-private encoding algorithm.
  *
  * The RAPPOR algorithm is described at go/rappor and presented in detail at go/rappor-writeup.
  *
  * @author bonawitz@google.com Keith Bonawitz
  */
 // TODO(bonawitz): Make encoder and interface and make this a final class implementing it.
 // We can't just make this final now because there exist tests that need to Mock it.
 public class Encoder {
   /**
    * A non-decreasing version number.
    *
    * <p>The version number should increase any time the Encoder has a user-visible functional change
    * to any of encoding algorithms or the interpretation of the input parameters.
    */
   public static final long VERSION = 3;

   /**
    * Minimum length required for the user secret, in bytes.
    */
   public static final int MIN_USER_SECRET_BYTES = HmacDrbg.ENTROPY_INPUT_SIZE_BYTES;

   /**
    * Maximum number of bits in the RAPPOR-encoded report.
    *
    * Must be less than HmacDrbg.MAX_BYTES_TOTAL;
    */
   public static final int MAX_BITS = 4096;

   /**
    * Maximum number of Bloom filter hashes used for RAPPOR-encoded strings.
    *
    * <p>This is constrained in the current implementation by requiring 2 bytes from an MD5 value
    * (which is 16 bytes long) for each Bloom filter hash.
    */
   public static final int MAX_BLOOM_HASHES = 8;

   /**
    * Maximum number of cohorts supported.
    */
   public static final int MAX_COHORTS = 128;

   /**
    * First (and only) byte of HMAC_DRBG personalization strings used to generate the cohort number.
    */
   private static final byte HMAC_DRBG_TYPE_COHORT = 0x00;

   /**
    * First byte of HMAC_DRBG personalization strings used to generate the PRR response.
    */
   private static final byte HMAC_DRBG_TYPE_PRR = 0x01;

   /**
    * A unique identifier for this Encoder, represented in UTF-8.
    *
    * <p>The (userSecret, encoderId) pair identify a the logical memoization table used for RAPPOR's
    * Permanent Randomized Response stage.  Therefore, for any userSecret, each Encoder must have a
    * distinct identifier for Permanent Randomized Response to be effective.
    *
    * <p>In practice, "memoization" is achieved by generating deterministic pseudo-random bits using
    * HMAC_DRBG.  encoderIdBytes is used as part of the personalization string.
    */
   private final byte[] encoderIdBytes;

   /**
    * The RAPPOR "f" probability, on the range [0.0, 1.0].
    *
    * <p>This it the probability of replacing a bit from the input with a uniform random bit when
    * generating the permanent randomized response.
    *
    * <p>Setting probabilityF to 0 disables the PRR phase of RAPPOR.
    */
   private final double probabilityF;

   /**
    * The RAPPOR "p" probability, on the range [0.0, 1.0].
    *
    * <p>This is the probability of emitting a '1' bit in the instantaneous randomized response,
    * given that the corresponding bit in the permanent randomized response is '0'.
    *
    * <p>Setting probabilityP to 0.0 and probabilityQ to 1.0 disables the IRR phase of RAPPOR.
    */
   private final double probabilityP;

   /**
    * The RAPPOR "1" probability, on the range [0.0, 1.0].
    *
    * <p>This is the probability of emitting a 1 bit in the instantaneous randomized response, given
    * that the corresponding bit in the permanent randomized response is 1.
    *
    * <p>Setting probabilityP to 0.0 and probabilityQ to 1.0 disables the IRR phase of RAPPOR.
    */
   private final double probabilityQ;

   /**
    * The number of bits in the RAPPOR-encoded report.
    *
    * <p>Must satisfy 1 &lt;= numBits &lt;= MAX_BITS.
    *
    * <ul>
    * <li>For encodeOrdinal, requires 0 &lt;= ordinal &lt; numBits.
    * <li>For encodeString, uses a numBits-wide Bloom filter.
    * <li>For encodeBits, only the low-order numBits may be non-zero.
    * </ul>
    */
   private final int numBits;

   /**
    * The number of hash functions used forming the Bloom filter encoding of a string.
    *
    * <p>Must satisfy 1 &lt;= numBloomHashes &lt;= MAX_BLOOM_HASHES.
    */
   private final int numBloomHashes;

   /**
    * The number of cohorts used for cohort assignment.
    */
   private final int numCohorts;

   /**
    * The cohort this user is assigned to for Bloom filter string encoding.
    *
    * <p>This value is stable for a given (userSecret, numCohorts) pair.  Furthermore, if two
    * encoders use the same userSecret but have different numCohorts values, the cohort assignment
    * for the encoder with the smaller numCohorts value is a bitwise suffix of the cohort assignment
    * for the encoder with the larger numCohorts value.  It follows that, if you know maximum cohort
    * assignment across a set of encoders, and you know the numCohorts setting for each encoder, then
    * you can deduce the cohort assignment for each encoder by taking the bitwise-and of the max
    * cohort value and (numCohorts-1), noting that numCohorts is required to be a positive power of
    * 2.
    */
   private final int cohort;

   /**
    * A bitmask with 1 bits in all the positions where a RAPPOR-encoded report could have a 1 bit.
    *
    * <p>The bitmask has the lowest order numBits set to 1 and the rest 0.
    */
   private final BitSet inputMask;

   /**
    * SHA-256 utility class instance.
    *
    * <p>This object is stateful; access must be synchronized.  The reset method must be
    * called before each use.
    */
 // BEGIN android-changed: Remove javax
 //  @GuardedBy("this")
 // END android-changed
   private final MessageDigest sha256;

   /**
    * MD5 utility class instance.
    *
    * <p>This object is stateful; access must be synchronized.  The reset method must be
    * called before each use.
    */
 // BEGIN android-changed: Remove javax
 //  @GuardedBy("this")
 // END android-changed
   private final MessageDigest md5;

   /**
    * A SecureRandom instance, initialized with a cryptographically secure random seed.
    */
 // BEGIN android-changed
 //  private final SecureRandom random;
   private final Random random;
 // BEGIN android-changed

   /**
    * Entropy input for constructing HmacDrbg objects.
    */
   private final byte[] userSecret;

   /**
    * Constructs a new RAPPOR message encoder.
    *
    * @param userSecret Stable secret randomly selected for this user.  UserSecret must be at least
    *     MIN_USER_SECRET_BYTES bytes of high-quality entropy.  Changing the user secret clears the
    *     memoized cohort assignments and permanent randomized responses.  Be aware that resetting
    *     these memoizations has significant privacy risks -- consult documentation at go/rappor for
    *     more details.
    * @param encoderId Uniquely identifies this encoder.  Used to differentiate momoized
    *     cohort assignments and permanent randomized responses.
    * @param numBits The number of bits in the RAPPOR-encoded report.
    * @param probabilityF The RAPPOR "f" probability, on the range [0.0, 1.0].  This will be
    *     quantized to the nearest 1/128.
    * @param probabilityP The RAPPOR "p" probability, on the range [0.0, 1.0].
    * @param probabilityQ The RAPPOR "1" probability, on the range [0.0, 1.0].
    * @param numCohorts Number of cohorts into which the user pool is randomly segmented.
    * @param numBloomHashes The number of hash functions used forming the Bloom filter encoding of a
    *     string.
    */
   public Encoder(byte[] userSecret, String encoderId, int numBits,
                  double probabilityF, double probabilityP, double probabilityQ,
                  int numCohorts, int numBloomHashes) {
     this(
         null, // random
         null, // md5,
         null, // sha256,
         userSecret,
         encoderId,
         numBits,
         probabilityF,
         probabilityP,
         probabilityQ,
         numCohorts,
         numBloomHashes);
   }

   /**
    * Constructs a new RAPPOR message encoder, using constructor-style dependency injection.
    *
    * @param random A cryptographically secure random number generator, or null (in which case a
    *     new SecureRandom will be constructed).
    * @param md5 A configured MD5 hash algorithm, or null (in which case a new MessageDigest will be
    *     constructed).   Note: MessageDigest objects are stateful, and that state must not be
    *     modified while calls to the Encoder are active.
    * @param sha256 A configured SHA-256 hash algorithm, or null (in which case a new MessageDigest
    *     will be constructed).   Note: MessageDigest objects are stateful, and that state must not
    *     be modified while calls to the Encoder are active.
    * @param userSecret Stable secret randomly selected for this user.  UserSecret must be at least
    *     32 bytes of high-quality entropy.  Changing the user secret clears the memoized cohort
    *     assignments and permanent randomized responses.  Be aware that resetting these memoizations
    *     has significant privacy risks -- consult documentation at go/rappor for more details.
    * @param encoderId Uniquely identifies this encoder.  Used to differentiate momoized
    *     cohort assignments and permanent randomized responses.
    * @param numBits The number of bits in the RAPPOR-encoded report.
    * @param probabilityF The RAPPOR "f" probability, on the range [0.0, 1.0].  This will be
    *     quantized to the nearest 1/128.
    * @param probabilityP The RAPPOR "p" probability, on the range [0.0, 1.0].
    * @param probabilityQ The RAPPOR "1" probability, on the range [0.0, 1.0].
    * @param numCohorts Number of cohorts into which the user pool is randomly segmented.
    * @param numBloomHashes The number of hash functions used forming the Bloom filter encoding of a
    *     string.
    */
   public Encoder(
 // BEGIN android-changed: Remove javax
 //      @Nullable SecureRandom random,
 //      @Nullable MessageDigest md5,
 //      @Nullable MessageDigest sha256,
 //      SecureRandom random,
       Random random,
       MessageDigest md5,
       MessageDigest sha256,
 // END android-changed
       byte[] userSecret,
       String encoderId,
       int numBits,
       double probabilityF,
       double probabilityP,
       double probabilityQ,
       int numCohorts,
       int numBloomHashes) {
     if (md5 != null) {
       this.md5 = md5;
     } else {
       try {
         this.md5 = MessageDigest.getInstance("MD5");
       } catch (NoSuchAlgorithmException impossible) {
         // This should never happen.  Every implementation of the Java platform
         // is required to support MD5.
         throw new AssertionError(impossible);
       }
     }
     this.md5.reset();

     if (sha256 != null) {
       this.sha256 = sha256;
     } else {
       try {
         this.sha256 = MessageDigest.getInstance("SHA-256");
       } catch (NoSuchAlgorithmException impossible) {
         // This should never happen.  Every implementation of the Java platform
         // is required to support 256.
         throw new AssertionError(impossible);
       }
     }
     this.sha256.reset();

     this.encoderIdBytes = encoderId.getBytes(StandardCharsets.UTF_8);

     if (random != null) {
       this.random = random;
     } else {
       this.random = new SecureRandom();
     }

     // android-changed: Removed guava dependency
     // checkArgument(
     //     userSecret.length >= MIN_USER_SECRET_BYTES,
     //     "userSecret must be at least %s bytes of high-quality entropy.",
     //     MIN_USER_SECRET_BYTES);
     checkArgument(
         userSecret.length >= MIN_USER_SECRET_BYTES,
         "userSecret must be at least " + MIN_USER_SECRET_BYTES
             + " bytes of high-quality entropy.");
     this.userSecret = userSecret;

     checkArgument(
         probabilityF >= 0 && probabilityF <= 1, "probabilityF must be on range [0.0, 1.0]");
     this.probabilityF = Math.round(probabilityF * 128) / 128.0;

     checkArgument(
         probabilityP >= 0 && probabilityP <= 1, "probabilityP must be on range [0.0, 1.0]");
     this.probabilityP = probabilityP;

     checkArgument(
         probabilityQ >= 0 && probabilityQ <= 1, "probabilityQ must be on range [0.0, 1.0]");
     this.probabilityQ = probabilityQ;

     checkArgument(
         numBits >= 1 && numBits <= MAX_BITS, "numBits must be on range [1, " + MAX_BITS + "].");
     this.numBits = numBits;
     // Make a bitmask with the lowest-order numBits set to 1.
     this.inputMask = new BitSet(numBits);
     this.inputMask.set(0, numBits, true);

     checkArgument(
         numBloomHashes >= 1 && numBloomHashes <= numBits,
         "numBloomHashes must be on range [1, numBits).");
     this.numBloomHashes = numBloomHashes;

     checkArgument(
         numCohorts >= 1 && numCohorts <= MAX_COHORTS,
         "numCohorts must be on range [1, " + MAX_COHORTS + "].");

     // Assuming numCohorts >= 1:
     //
     // If numCohorts is a power of 2, then numCohorts has one bit set and numCohorts - 1 has only
     // the bits to the right of numCohorts's bit set.  The bitwise-and of these is 0.
     //
     // If numCohorts is not a power of 2, then numCohorts has at least two bits set.  It follows
     // subtracting one from numCohorts keeps the most significant bit set to 1, and thus the
     // bitwise-and has at least this non-zero bit.
     boolean numCohortsIsPowerOfTwo = (numCohorts & (numCohorts - 1)) == 0;
     checkArgument(numCohortsIsPowerOfTwo, "numCohorts must be a power of 2.");
     this.numCohorts = numCohorts;

     // cohortMasterAssignment depends only on the userSecret.
     HmacDrbg cohortDrbg = new HmacDrbg(userSecret, new byte[] {HMAC_DRBG_TYPE_COHORT});
     ByteBuffer cohortDrbgBytes = ByteBuffer.wrap(cohortDrbg.nextBytes(4));
     int cohortMasterAssignment = Math.abs(cohortDrbgBytes.getInt()) % MAX_COHORTS;
     this.cohort = cohortMasterAssignment & (numCohorts - 1);
   }

   public double getProbabilityF() {
     return probabilityF;
   }

   public double getProbabilityP() {
     return probabilityP;
   }

   public double getProbabilityQ() {
     return probabilityQ;
   }

   public int getNumBits() {
     return numBits;
   }

   public int getNumBloomHashes() {
     return numBloomHashes;
   }

   public int getNumCohorts() {
     return numCohorts;
   }

   public int getCohort() {
     return cohort;
   }

   /**
    * Returns the Encoder ID as a UTF-8 formatted string.
    */
   public String getEncoderId() {
     return new String(encoderIdBytes, StandardCharsets.UTF_8);
   }

   /**
    * Encodes a boolean into a RAPPOR report.
    *
    * <p>The boolean is 0 or 1, then encoded using permanent and instantaneous randomized response.
    *
    * <p>In most cases, numBits should be 1 when using this method.
    */
   public byte[] encodeBoolean(boolean bool) {
     BitSet input = new BitSet(numBits);
     input.set(0, bool);
     return encodeBits(input);
   }

   /**
    * Encodes an ordinal into a RAPPOR report.
    *
    * <p>The ordinal is represented using a 1-hot binary representation, then encoded using permanent
    * and instantaneous randomized response.
    *
    * @param ordinal A value on the range [0, numBits).
    */
   public byte[] encodeOrdinal(int ordinal) {
     checkArgument(
         ordinal >= 0 && ordinal < numBits, "Ordinal value must be in range [0, numBits).");
     BitSet input = new BitSet(numBits);
     input.set(ordinal, true);
     return encodeBits(input);
   }

   /**
    * Encodes a string into a RAPPOR report.
    *
    * <p>The string is represented using a Bloom filter with numBloomHashes hash functions, then
    * encoded using permanent and instantaneous randomized response.
    *
    * @param string An arbitrary string.
    */
   public byte[] encodeString(String string) {
     // Implements a Bloom filter by slicing a single MD5 hash into numBloomHashes bit indices.
     byte[] stringInUtf8 = string.getBytes(StandardCharsets.UTF_8);
     byte[] message =
         ByteBuffer.allocate(4 + stringInUtf8.length)
                   .putInt(cohort)
                   .put(stringInUtf8)
                   .array();

     byte[] digest;
     synchronized (this) {
       md5.reset();
       digest = md5.digest(message);
     }
     // android-changed: Removed guava dependency
     // Verify.verify(digest.length == 16);
     // Verify.verify(numBloomHashes <= digest.length / 2);
     verify(digest.length == 16);
     verify(numBloomHashes <= digest.length / 2);

     BitSet input = new BitSet(numBits);
     for (int i = 0; i < numBloomHashes; i++) {
       // Convert byte pairs to ints on [0, 65535].
       // Anding with 0xFF converts signed byte to unsigned int.
       int digestWord = (digest[i * 2] & 0xFF) * 256 + (digest[i * 2 + 1] & 0xFF);
       int chosenBit = digestWord % numBits;
       input.set(chosenBit, true);
     }

     return encodeBits(input);
   }

   /**
    * Encodes an arbitrary bitstring into a RAPPOR report.
    *
    * @param bits A bitstring in which only the least significant numBits bits may be 1.
    */
   public byte[] encodeBits(byte[] bits) {
     return encodeBits(BitSet.valueOf(bits));
   }

   /**
    * Encodes an arbitrary bitstring into a RAPPOR report.
    *
    * @param bits A bitstring in which only the least significant numBits bits may be 1.
    */
   private byte[] encodeBits(BitSet bits) {
     BitSet permanentRandomizedResponse = computePermanentRandomizedResponse(bits);
     BitSet encodedBitSet = computeInstantaneousRandomizedResponse(permanentRandomizedResponse);

     // BitSet.toByteArray only returns enough bytes to capture the most significant bit
     // that is set.  For example, a BitSet with no bits set could return a length-0 array.
     // In contrast, we guarantee that our output is sized according to numBits.
     byte[] encodedBytes = encodedBitSet.toByteArray();
     byte[] output = new byte[(numBits + 7) / 8];
     // android-changed: Removed guava dependency
     // Verify.verify(encodedBytes.length <= output.length);
     verify(encodedBytes.length <= output.length);
     System.arraycopy(
         encodedBytes, // src
         0, // srcPos
         output, // dest
         0, // destPos
         encodedBytes.length); // length
     return output;
   }

   /**
    * Returns the permanent randomized response for the given bits.
    *
    * <p>The response for a particular bits input is guaranteed to always be the same for any encoder
    * constructed with the same parameters (including the encoderId and the userSecret).
    */
   private BitSet computePermanentRandomizedResponse(BitSet bits) {
     // Ensures that the input only has bits set in the lowest
     BitSet masked = new BitSet();
     masked.or(bits);
     masked.andNot(inputMask);
     checkArgument(masked.isEmpty(), "Input bits had bits set past Encoder's numBits limit.");

     if (probabilityF == 0.0) {
       return bits;
     }

     // Builds a personalization string that contains both the encoderId and input value (bits),
     // and is no longer than HmacDrbg.MAX_PERSONALIZATION_STRING_LENGTH_BYTES.  The first byte
     // of the personalization string is always HMAC_DRBG_TYPE_PRR, to avoid collisions with the
     // cohort-generation personalization string.
     byte[] personalizationString;
     synchronized (this) {
       int personalizationStringLength =
           Math.min(HmacDrbg.MAX_PERSONALIZATION_STRING_LENGTH_BYTES, 1 + sha256.getDigestLength());
       personalizationString = new byte[personalizationStringLength];
       personalizationString[0] = HMAC_DRBG_TYPE_PRR;
       sha256.reset();
       sha256.update(encoderIdBytes);
       sha256.update(new byte[] {0});
       sha256.update(bits.toByteArray());
       byte[] digest = sha256.digest(personalizationString);
       System.arraycopy(digest, 0, personalizationString, 1, personalizationString.length - 1);
     }

     HmacDrbg drbg = new HmacDrbg(userSecret, personalizationString);
     byte[] pseudorandomStream = drbg.nextBytes(numBits);
     // android-changed: Removed guava dependency
     // Verify.verify(numBits <= pseudorandomStream.length);
     verify(numBits <= pseudorandomStream.length);

     int probabilityFTimes128 = (int) Math.round(probabilityF * 128);
     BitSet result = new BitSet(numBits);
     for (int i = 0; i < numBits; i++) {
       // Grabs a single byte from the pseudorandom stream.
       // Anding with 0xFF converts a signed byte to an unsigned integer.
       int pseudorandomByte = pseudorandomStream[i] & 0xFF;

       // Uses bits 1-7 to get a random number between 0 and 127.
       int uniform0to127 = pseudorandomByte >> 1;
       boolean shouldUseNoise = uniform0to127 < probabilityFTimes128;

       if (shouldUseNoise) {
         // Uses bit 0 as a flip of a fair coin.
         result.set(i, (pseudorandomByte & 0x01) > 0);
       } else {
         result.set(i, bits.get(i));
       }
     }
     return result;
   }

   /**
    * Returns the instantaneous randomized response for the given bits.
    *
    * <p>The instantaneous response is NOT memoized -- it is sampled randomly on
    * every invocation.
    */
   private BitSet computeInstantaneousRandomizedResponse(BitSet bits) {
     // Ensures that the input only has bits set in the lowest
     BitSet masked = new BitSet();
     masked.or(bits);
     masked.andNot(inputMask);
     checkArgument(masked.isEmpty(), "Input bits had bits set past Encoder's numBits limit.");

     if (probabilityP == 0.0 && probabilityQ == 1.0) {
       return bits;
     }

     BitSet response = new BitSet(numBits);
     for (int i = 0; i < numBits; i++) {
       boolean bit = bits.get(i);
       double probability = bit ? probabilityQ : probabilityP;
       boolean responseBit = random.nextFloat() < probability;
       response.set(i, responseBit);
     }
     return response;
   }

   // BEGIN android-changed: Added guava methods
   private static void checkArgument(boolean expression, Object errorMessage) {
     if (!expression) {
       throw new IllegalArgumentException(String.valueOf(errorMessage));
     }
   }

   private static void verify(boolean expression) {
     if (!expression) {
       throw new java.lang.IllegalStateException();
     }
   }
   // END android-changed
 }
	package com.google.android.rappor;

	// BEGIN android-changed: Removed guava dependency
	// import static com.google.common.base.Preconditions.checkArgument;
	//
	// import com.google.common.base.Verify;
	// END android-changed

	import java.nio.ByteBuffer;
	import java.nio.charset.StandardCharsets;
	import java.security.MessageDigest;
	import java.security.NoSuchAlgorithmException;
	import java.security.SecureRandom;
	import java.util.BitSet;
	// BEGIN android-changed
	import java.util.Random;
	// END android-changed

	// BEGIN android-changed: Remove javax
	// import javax.annotation.Nullable;
	// import javax.annotation.concurrent.GuardedBy;
	// END android-changed

	/**
	* Encodes reports using the RAPPOR differentially-private encoding algorithm.
	*
	* The RAPPOR algorithm is described at go/rappor and presented in detail at go/rappor-writeup.
	*
	* @author bonawitz@google.com Keith Bonawitz
	*/
	// TODO(bonawitz): Make encoder and interface and make this a final class implementing it.
	// We can't just make this final now because there exist tests that need to Mock it.
	public class Encoder {
	/**
	* A non-decreasing version number.
	*
	* <p>The version number should increase any time the Encoder has a user-visible functional change
	* to any of encoding algorithms or the interpretation of the input parameters.
	*/
	public static final long VERSION = 3;

	/**
	* Minimum length required for the user secret, in bytes.
	*/
	public static final int MIN_USER_SECRET_BYTES = HmacDrbg.ENTROPY_INPUT_SIZE_BYTES;

	/**
	* Maximum number of bits in the RAPPOR-encoded report.
	*
	* Must be less than HmacDrbg.MAX_BYTES_TOTAL;
	*/
	public static final int MAX_BITS = 4096;

	/**
	* Maximum number of Bloom filter hashes used for RAPPOR-encoded strings.
	*
	* <p>This is constrained in the current implementation by requiring 2 bytes from an MD5 value
	* (which is 16 bytes long) for each Bloom filter hash.
	*/
	public static final int MAX_BLOOM_HASHES = 8;

	/**
	* Maximum number of cohorts supported.
	*/
	public static final int MAX_COHORTS = 128;

	/**
	* First (and only) byte of HMAC_DRBG personalization strings used to generate the cohort number.
	*/
	private static final byte HMAC_DRBG_TYPE_COHORT = 0x00;

	/**
	* First byte of HMAC_DRBG personalization strings used to generate the PRR response.
	*/
	private static final byte HMAC_DRBG_TYPE_PRR = 0x01;

	/**
	* A unique identifier for this Encoder, represented in UTF-8.
	*
	* <p>The (userSecret, encoderId) pair identify a the logical memoization table used for RAPPOR's
	* Permanent Randomized Response stage. Therefore, for any userSecret, each Encoder must have a
	* distinct identifier for Permanent Randomized Response to be effective.
	*
	* <p>In practice, "memoization" is achieved by generating deterministic pseudo-random bits using
	* HMAC_DRBG. encoderIdBytes is used as part of the personalization string.
	*/
	private final byte[] encoderIdBytes;

	/**
	* The RAPPOR "f" probability, on the range [0.0, 1.0].
	*
	* <p>This it the probability of replacing a bit from the input with a uniform random bit when
	* generating the permanent randomized response.
	*
	* <p>Setting probabilityF to 0 disables the PRR phase of RAPPOR.
	*/
	private final double probabilityF;

	/**
	* The RAPPOR "p" probability, on the range [0.0, 1.0].
	*
	* <p>This is the probability of emitting a '1' bit in the instantaneous randomized response,
	* given that the corresponding bit in the permanent randomized response is '0'.
	*
	* <p>Setting probabilityP to 0.0 and probabilityQ to 1.0 disables the IRR phase of RAPPOR.
	*/
	private final double probabilityP;

	/**
	* The RAPPOR "1" probability, on the range [0.0, 1.0].
	*
	* <p>This is the probability of emitting a 1 bit in the instantaneous randomized response, given
	* that the corresponding bit in the permanent randomized response is 1.
	*
	* <p>Setting probabilityP to 0.0 and probabilityQ to 1.0 disables the IRR phase of RAPPOR.
	*/
	private final double probabilityQ;

	/**
	* The number of bits in the RAPPOR-encoded report.
	*
	* <p>Must satisfy 1 <= numBits <= MAX_BITS.
	*
	* <ul>
	* <li>For encodeOrdinal, requires 0 <= ordinal < numBits.
	* <li>For encodeString, uses a numBits-wide Bloom filter.
	* <li>For encodeBits, only the low-order numBits may be non-zero.
	* </ul>
	*/
	private final int numBits;

	/**
	* The number of hash functions used forming the Bloom filter encoding of a string.
	*
	* <p>Must satisfy 1 <= numBloomHashes <= MAX_BLOOM_HASHES.
	*/
	private final int numBloomHashes;

	/**
	* The number of cohorts used for cohort assignment.
	*/
	private final int numCohorts;

	/**
	* The cohort this user is assigned to for Bloom filter string encoding.
	*
	* <p>This value is stable for a given (userSecret, numCohorts) pair. Furthermore, if two
	* encoders use the same userSecret but have different numCohorts values, the cohort assignment
	* for the encoder with the smaller numCohorts value is a bitwise suffix of the cohort assignment
	* for the encoder with the larger numCohorts value. It follows that, if you know maximum cohort
	* assignment across a set of encoders, and you know the numCohorts setting for each encoder, then
	* you can deduce the cohort assignment for each encoder by taking the bitwise-and of the max
	* cohort value and (numCohorts-1), noting that numCohorts is required to be a positive power of
	* 2.
	*/
	private final int cohort;

	/**
	* A bitmask with 1 bits in all the positions where a RAPPOR-encoded report could have a 1 bit.
	*
	* <p>The bitmask has the lowest order numBits set to 1 and the rest 0.
	*/
	private final BitSet inputMask;

	/**
	* SHA-256 utility class instance.
	*
	* <p>This object is stateful; access must be synchronized. The reset method must be
	* called before each use.
	*/
	// BEGIN android-changed: Remove javax
	// @GuardedBy("this")
	// END android-changed
	private final MessageDigest sha256;

	/**
	* MD5 utility class instance.
	*
	* <p>This object is stateful; access must be synchronized. The reset method must be
	* called before each use.
	*/
	// BEGIN android-changed: Remove javax
	// @GuardedBy("this")
	// END android-changed
	private final MessageDigest md5;

	/**
	* A SecureRandom instance, initialized with a cryptographically secure random seed.
	*/
	// BEGIN android-changed
	// private final SecureRandom random;
	private final Random random;
	// BEGIN android-changed

	/**
	* Entropy input for constructing HmacDrbg objects.
	*/
	private final byte[] userSecret;

	/**
	* Constructs a new RAPPOR message encoder.
	*
	* @param userSecret Stable secret randomly selected for this user. UserSecret must be at least
	* MIN_USER_SECRET_BYTES bytes of high-quality entropy. Changing the user secret clears the
	* memoized cohort assignments and permanent randomized responses. Be aware that resetting
	* these memoizations has significant privacy risks -- consult documentation at go/rappor for
	* more details.
	* @param encoderId Uniquely identifies this encoder. Used to differentiate momoized
	* cohort assignments and permanent randomized responses.
	* @param numBits The number of bits in the RAPPOR-encoded report.
	* @param probabilityF The RAPPOR "f" probability, on the range [0.0, 1.0]. This will be
	* quantized to the nearest 1/128.
	* @param probabilityP The RAPPOR "p" probability, on the range [0.0, 1.0].
	* @param probabilityQ The RAPPOR "1" probability, on the range [0.0, 1.0].
	* @param numCohorts Number of cohorts into which the user pool is randomly segmented.
	* @param numBloomHashes The number of hash functions used forming the Bloom filter encoding of a
	* string.
	*/
	public Encoder(byte[] userSecret, String encoderId, int numBits,
	double probabilityF, double probabilityP, double probabilityQ,
	int numCohorts, int numBloomHashes) {
	this(
	null, // random
	null, // md5,
	null, // sha256,
	userSecret,
	encoderId,
	numBits,
	probabilityF,
	probabilityP,
	probabilityQ,
	numCohorts,
	numBloomHashes);
	}

	/**
	* Constructs a new RAPPOR message encoder, using constructor-style dependency injection.
	*
	* @param random A cryptographically secure random number generator, or null (in which case a
	* new SecureRandom will be constructed).
	* @param md5 A configured MD5 hash algorithm, or null (in which case a new MessageDigest will be
	* constructed). Note: MessageDigest objects are stateful, and that state must not be
	* modified while calls to the Encoder are active.
	* @param sha256 A configured SHA-256 hash algorithm, or null (in which case a new MessageDigest
	* will be constructed). Note: MessageDigest objects are stateful, and that state must not
	* be modified while calls to the Encoder are active.
	* @param userSecret Stable secret randomly selected for this user. UserSecret must be at least
	* 32 bytes of high-quality entropy. Changing the user secret clears the memoized cohort
	* assignments and permanent randomized responses. Be aware that resetting these memoizations
	* has significant privacy risks -- consult documentation at go/rappor for more details.
	* @param encoderId Uniquely identifies this encoder. Used to differentiate momoized
	* cohort assignments and permanent randomized responses.
	* @param numBits The number of bits in the RAPPOR-encoded report.
	* @param probabilityF The RAPPOR "f" probability, on the range [0.0, 1.0]. This will be
	* quantized to the nearest 1/128.
	* @param probabilityP The RAPPOR "p" probability, on the range [0.0, 1.0].
	* @param probabilityQ The RAPPOR "1" probability, on the range [0.0, 1.0].
	* @param numCohorts Number of cohorts into which the user pool is randomly segmented.
	* @param numBloomHashes The number of hash functions used forming the Bloom filter encoding of a
	* string.
	*/
	public Encoder(
	// BEGIN android-changed: Remove javax
	// @Nullable SecureRandom random,
	// @Nullable MessageDigest md5,
	// @Nullable MessageDigest sha256,
	// SecureRandom random,
	Random random,
	MessageDigest md5,
	MessageDigest sha256,
	// END android-changed
	byte[] userSecret,
	String encoderId,
	int numBits,
	double probabilityF,
	double probabilityP,
	double probabilityQ,
	int numCohorts,
	int numBloomHashes) {
	if (md5 != null) {
	this.md5 = md5;
	} else {
	try {
	this.md5 = MessageDigest.getInstance("MD5");
	} catch (NoSuchAlgorithmException impossible) {
	// This should never happen. Every implementation of the Java platform
	// is required to support MD5.
	throw new AssertionError(impossible);
	}
	}
	this.md5.reset();

	if (sha256 != null) {
	this.sha256 = sha256;
	} else {
	try {
	this.sha256 = MessageDigest.getInstance("SHA-256");
	} catch (NoSuchAlgorithmException impossible) {
	// This should never happen. Every implementation of the Java platform
	// is required to support 256.
	throw new AssertionError(impossible);
	}
	}
	this.sha256.reset();

	this.encoderIdBytes = encoderId.getBytes(StandardCharsets.UTF_8);

	if (random != null) {
	this.random = random;
	} else {
	this.random = new SecureRandom();
	}

	// android-changed: Removed guava dependency
	// checkArgument(
	// userSecret.length >= MIN_USER_SECRET_BYTES,
	// "userSecret must be at least %s bytes of high-quality entropy.",
	// MIN_USER_SECRET_BYTES);
	checkArgument(
	userSecret.length >= MIN_USER_SECRET_BYTES,
	"userSecret must be at least " + MIN_USER_SECRET_BYTES
	+ " bytes of high-quality entropy.");
	this.userSecret = userSecret;

	checkArgument(
	probabilityF >= 0 && probabilityF <= 1, "probabilityF must be on range [0.0, 1.0]");
	this.probabilityF = Math.round(probabilityF * 128) / 128.0;

	checkArgument(
	probabilityP >= 0 && probabilityP <= 1, "probabilityP must be on range [0.0, 1.0]");
	this.probabilityP = probabilityP;

	checkArgument(
	probabilityQ >= 0 && probabilityQ <= 1, "probabilityQ must be on range [0.0, 1.0]");
	this.probabilityQ = probabilityQ;

	checkArgument(
	numBits >= 1 && numBits <= MAX_BITS, "numBits must be on range [1, " + MAX_BITS + "].");
	this.numBits = numBits;
	// Make a bitmask with the lowest-order numBits set to 1.
	this.inputMask = new BitSet(numBits);
	this.inputMask.set(0, numBits, true);

	checkArgument(
	numBloomHashes >= 1 && numBloomHashes <= numBits,
	"numBloomHashes must be on range [1, numBits).");
	this.numBloomHashes = numBloomHashes;

	checkArgument(
	numCohorts >= 1 && numCohorts <= MAX_COHORTS,
	"numCohorts must be on range [1, " + MAX_COHORTS + "].");

	// Assuming numCohorts >= 1:
	//
	// If numCohorts is a power of 2, then numCohorts has one bit set and numCohorts - 1 has only
	// the bits to the right of numCohorts's bit set. The bitwise-and of these is 0.
	//
	// If numCohorts is not a power of 2, then numCohorts has at least two bits set. It follows
	// subtracting one from numCohorts keeps the most significant bit set to 1, and thus the
	// bitwise-and has at least this non-zero bit.
	boolean numCohortsIsPowerOfTwo = (numCohorts & (numCohorts - 1)) == 0;
	checkArgument(numCohortsIsPowerOfTwo, "numCohorts must be a power of 2.");
	this.numCohorts = numCohorts;

	// cohortMasterAssignment depends only on the userSecret.
	HmacDrbg cohortDrbg = new HmacDrbg(userSecret, new byte[] {HMAC_DRBG_TYPE_COHORT});
	ByteBuffer cohortDrbgBytes = ByteBuffer.wrap(cohortDrbg.nextBytes(4));
	int cohortMasterAssignment = Math.abs(cohortDrbgBytes.getInt()) % MAX_COHORTS;
	this.cohort = cohortMasterAssignment & (numCohorts - 1);
	}

	public double getProbabilityF() {
	return probabilityF;
	}

	public double getProbabilityP() {
	return probabilityP;
	}

	public double getProbabilityQ() {
	return probabilityQ;
	}

	public int getNumBits() {
	return numBits;
	}

	public int getNumBloomHashes() {
	return numBloomHashes;
	}

	public int getNumCohorts() {
	return numCohorts;
	}

	public int getCohort() {
	return cohort;
	}

	/**
	* Returns the Encoder ID as a UTF-8 formatted string.
	*/
	public String getEncoderId() {
	return new String(encoderIdBytes, StandardCharsets.UTF_8);
	}

	/**
	* Encodes a boolean into a RAPPOR report.
	*
	* <p>The boolean is 0 or 1, then encoded using permanent and instantaneous randomized response.
	*
	* <p>In most cases, numBits should be 1 when using this method.
	*/
	public byte[] encodeBoolean(boolean bool) {
	BitSet input = new BitSet(numBits);
	input.set(0, bool);
	return encodeBits(input);
	}

	/**
	* Encodes an ordinal into a RAPPOR report.
	*
	* <p>The ordinal is represented using a 1-hot binary representation, then encoded using permanent
	* and instantaneous randomized response.
	*
	* @param ordinal A value on the range [0, numBits).
	*/
	public byte[] encodeOrdinal(int ordinal) {
	checkArgument(
	ordinal >= 0 && ordinal < numBits, "Ordinal value must be in range [0, numBits).");
	BitSet input = new BitSet(numBits);
	input.set(ordinal, true);
	return encodeBits(input);
	}

	/**
	* Encodes a string into a RAPPOR report.
	*
	* <p>The string is represented using a Bloom filter with numBloomHashes hash functions, then
	* encoded using permanent and instantaneous randomized response.
	*
	* @param string An arbitrary string.
	*/
	public byte[] encodeString(String string) {
	// Implements a Bloom filter by slicing a single MD5 hash into numBloomHashes bit indices.
	byte[] stringInUtf8 = string.getBytes(StandardCharsets.UTF_8);
	byte[] message =
	ByteBuffer.allocate(4 + stringInUtf8.length)
	.putInt(cohort)
	.put(stringInUtf8)
	.array();

	byte[] digest;
	synchronized (this) {
	md5.reset();
	digest = md5.digest(message);
	}
	// android-changed: Removed guava dependency
	// Verify.verify(digest.length == 16);
	// Verify.verify(numBloomHashes <= digest.length / 2);
	verify(digest.length == 16);
	verify(numBloomHashes <= digest.length / 2);

	BitSet input = new BitSet(numBits);
	for (int i = 0; i < numBloomHashes; i++) {
	// Convert byte pairs to ints on [0, 65535].
	// Anding with 0xFF converts signed byte to unsigned int.
	int digestWord = (digest[i * 2] & 0xFF) * 256 + (digest[i * 2 + 1] & 0xFF);
	int chosenBit = digestWord % numBits;
	input.set(chosenBit, true);
	}

	return encodeBits(input);
	}

	/**
	* Encodes an arbitrary bitstring into a RAPPOR report.
	*
	* @param bits A bitstring in which only the least significant numBits bits may be 1.
	*/
	public byte[] encodeBits(byte[] bits) {
	return encodeBits(BitSet.valueOf(bits));
	}

	/**
	* Encodes an arbitrary bitstring into a RAPPOR report.
	*
	* @param bits A bitstring in which only the least significant numBits bits may be 1.
	*/
	private byte[] encodeBits(BitSet bits) {
	BitSet permanentRandomizedResponse = computePermanentRandomizedResponse(bits);
	BitSet encodedBitSet = computeInstantaneousRandomizedResponse(permanentRandomizedResponse);

	// BitSet.toByteArray only returns enough bytes to capture the most significant bit
	// that is set. For example, a BitSet with no bits set could return a length-0 array.
	// In contrast, we guarantee that our output is sized according to numBits.
	byte[] encodedBytes = encodedBitSet.toByteArray();
	byte[] output = new byte[(numBits + 7) / 8];
	// android-changed: Removed guava dependency
	// Verify.verify(encodedBytes.length <= output.length);
	verify(encodedBytes.length <= output.length);
	System.arraycopy(
	encodedBytes, // src
	0, // srcPos
	output, // dest
	0, // destPos
	encodedBytes.length); // length
	return output;
	}

	/**
	* Returns the permanent randomized response for the given bits.
	*
	* <p>The response for a particular bits input is guaranteed to always be the same for any encoder
	* constructed with the same parameters (including the encoderId and the userSecret).
	*/
	private BitSet computePermanentRandomizedResponse(BitSet bits) {
	// Ensures that the input only has bits set in the lowest
	BitSet masked = new BitSet();
	masked.or(bits);
	masked.andNot(inputMask);
	checkArgument(masked.isEmpty(), "Input bits had bits set past Encoder's numBits limit.");

	if (probabilityF == 0.0) {
	return bits;
	}

	// Builds a personalization string that contains both the encoderId and input value (bits),
	// and is no longer than HmacDrbg.MAX_PERSONALIZATION_STRING_LENGTH_BYTES. The first byte
	// of the personalization string is always HMAC_DRBG_TYPE_PRR, to avoid collisions with the
	// cohort-generation personalization string.
	byte[] personalizationString;
	synchronized (this) {
	int personalizationStringLength =
	Math.min(HmacDrbg.MAX_PERSONALIZATION_STRING_LENGTH_BYTES, 1 + sha256.getDigestLength());
	personalizationString = new byte[personalizationStringLength];
	personalizationString[0] = HMAC_DRBG_TYPE_PRR;
	sha256.reset();
	sha256.update(encoderIdBytes);
	sha256.update(new byte[] {0});
	sha256.update(bits.toByteArray());
	byte[] digest = sha256.digest(personalizationString);
	System.arraycopy(digest, 0, personalizationString, 1, personalizationString.length - 1);
	}

	HmacDrbg drbg = new HmacDrbg(userSecret, personalizationString);
	byte[] pseudorandomStream = drbg.nextBytes(numBits);
	// android-changed: Removed guava dependency
	// Verify.verify(numBits <= pseudorandomStream.length);
	verify(numBits <= pseudorandomStream.length);

	int probabilityFTimes128 = (int) Math.round(probabilityF * 128);
	BitSet result = new BitSet(numBits);
	for (int i = 0; i < numBits; i++) {
	// Grabs a single byte from the pseudorandom stream.
	// Anding with 0xFF converts a signed byte to an unsigned integer.
	int pseudorandomByte = pseudorandomStream[i] & 0xFF;

	// Uses bits 1-7 to get a random number between 0 and 127.
	int uniform0to127 = pseudorandomByte >> 1;
	boolean shouldUseNoise = uniform0to127 < probabilityFTimes128;

	if (shouldUseNoise) {
	// Uses bit 0 as a flip of a fair coin.
	result.set(i, (pseudorandomByte & 0x01) > 0);
	} else {
	result.set(i, bits.get(i));
	}
	}
	return result;
	}

	/**
	* Returns the instantaneous randomized response for the given bits.
	*
	* <p>The instantaneous response is NOT memoized -- it is sampled randomly on
	* every invocation.
	*/
	private BitSet computeInstantaneousRandomizedResponse(BitSet bits) {
	// Ensures that the input only has bits set in the lowest
	BitSet masked = new BitSet();
	masked.or(bits);
	masked.andNot(inputMask);
	checkArgument(masked.isEmpty(), "Input bits had bits set past Encoder's numBits limit.");

	if (probabilityP == 0.0 && probabilityQ == 1.0) {
	return bits;
	}

	BitSet response = new BitSet(numBits);
	for (int i = 0; i < numBits; i++) {
	boolean bit = bits.get(i);
	double probability = bit ? probabilityQ : probabilityP;
	boolean responseBit = random.nextFloat() < probability;
	response.set(i, responseBit);
	}
	return response;
	}

	// BEGIN android-changed: Added guava methods
	private static void checkArgument(boolean expression, Object errorMessage) {
	if (!expression) {
	throw new IllegalArgumentException(String.valueOf(errorMessage));
	}
	}

	private static void verify(boolean expression) {
	if (!expression) {
	throw new java.lang.IllegalStateException();
	}
	}
	// END android-changed
	}