Merge changes I6d3584f3,Ifdaada39
* changes:
Fix SntpClient 2036 issue (2/2)
Fix SntpClient 2036 issue (1/2)
diff --git a/core/java/android/net/SntpClient.java b/core/java/android/net/SntpClient.java
index f6852e6..0eb4cf3 100644
--- a/core/java/android/net/SntpClient.java
+++ b/core/java/android/net/SntpClient.java
@@ -17,16 +17,26 @@
package android.net;
import android.compat.annotation.UnsupportedAppUsage;
+import android.net.sntp.Duration64;
+import android.net.sntp.Timestamp64;
import android.os.SystemClock;
import android.util.Log;
+import android.util.Slog;
+import com.android.internal.annotations.VisibleForTesting;
import com.android.internal.util.TrafficStatsConstants;
import java.net.DatagramPacket;
import java.net.DatagramSocket;
import java.net.InetAddress;
import java.net.UnknownHostException;
-import java.util.Arrays;
+import java.security.NoSuchAlgorithmException;
+import java.security.SecureRandom;
+import java.time.Duration;
+import java.time.Instant;
+import java.util.Objects;
+import java.util.Random;
+import java.util.function.Supplier;
/**
* {@hide}
@@ -60,17 +70,21 @@
private static final int NTP_STRATUM_DEATH = 0;
private static final int NTP_STRATUM_MAX = 15;
- // Number of seconds between Jan 1, 1900 and Jan 1, 1970
- // 70 years plus 17 leap days
- private static final long OFFSET_1900_TO_1970 = ((365L * 70L) + 17L) * 24L * 60L * 60L;
+ // The source of the current system clock time, replaceable for testing.
+ private final Supplier<Instant> mSystemTimeSupplier;
- // system time computed from NTP server response
+ private final Random mRandom;
+
+ // The last offset calculated from an NTP server response
+ private long mClockOffset;
+
+ // The last system time computed from an NTP server response
private long mNtpTime;
- // value of SystemClock.elapsedRealtime() corresponding to mNtpTime
+ // The value of SystemClock.elapsedRealtime() corresponding to mNtpTime / mClockOffset
private long mNtpTimeReference;
- // round trip time in milliseconds
+ // The round trip (network) time in milliseconds
private long mRoundTripTime;
private static class InvalidServerReplyException extends Exception {
@@ -81,6 +95,13 @@
@UnsupportedAppUsage
public SntpClient() {
+ this(Instant::now, defaultRandom());
+ }
+
+ @VisibleForTesting
+ public SntpClient(Supplier<Instant> systemTimeSupplier, Random random) {
+ mSystemTimeSupplier = Objects.requireNonNull(systemTimeSupplier);
+ mRandom = Objects.requireNonNull(random);
}
/**
@@ -126,9 +147,13 @@
buffer[0] = NTP_MODE_CLIENT | (NTP_VERSION << 3);
// get current time and write it to the request packet
- final long requestTime = System.currentTimeMillis();
+ final Instant requestTime = mSystemTimeSupplier.get();
+ final Timestamp64 requestTimestamp = Timestamp64.fromInstant(requestTime);
+
+ final Timestamp64 randomizedRequestTimestamp =
+ requestTimestamp.randomizeSubMillis(mRandom);
final long requestTicks = SystemClock.elapsedRealtime();
- writeTimeStamp(buffer, TRANSMIT_TIME_OFFSET, requestTime);
+ writeTimeStamp(buffer, TRANSMIT_TIME_OFFSET, randomizedRequestTimestamp);
socket.send(request);
@@ -136,42 +161,44 @@
DatagramPacket response = new DatagramPacket(buffer, buffer.length);
socket.receive(response);
final long responseTicks = SystemClock.elapsedRealtime();
- final long responseTime = requestTime + (responseTicks - requestTicks);
+ final Instant responseTime = requestTime.plusMillis(responseTicks - requestTicks);
+ final Timestamp64 responseTimestamp = Timestamp64.fromInstant(responseTime);
// extract the results
final byte leap = (byte) ((buffer[0] >> 6) & 0x3);
final byte mode = (byte) (buffer[0] & 0x7);
final int stratum = (int) (buffer[1] & 0xff);
- final long originateTime = readTimeStamp(buffer, ORIGINATE_TIME_OFFSET);
- final long receiveTime = readTimeStamp(buffer, RECEIVE_TIME_OFFSET);
- final long transmitTime = readTimeStamp(buffer, TRANSMIT_TIME_OFFSET);
- final long referenceTime = readTimeStamp(buffer, REFERENCE_TIME_OFFSET);
+ final Timestamp64 referenceTimestamp = readTimeStamp(buffer, REFERENCE_TIME_OFFSET);
+ final Timestamp64 originateTimestamp = readTimeStamp(buffer, ORIGINATE_TIME_OFFSET);
+ final Timestamp64 receiveTimestamp = readTimeStamp(buffer, RECEIVE_TIME_OFFSET);
+ final Timestamp64 transmitTimestamp = readTimeStamp(buffer, TRANSMIT_TIME_OFFSET);
/* Do validation according to RFC */
- // TODO: validate originateTime == requestTime.
- checkValidServerReply(leap, mode, stratum, transmitTime, referenceTime);
+ checkValidServerReply(leap, mode, stratum, transmitTimestamp, referenceTimestamp,
+ randomizedRequestTimestamp, originateTimestamp);
- long roundTripTime = responseTicks - requestTicks - (transmitTime - receiveTime);
- // receiveTime = originateTime + transit + skew
- // responseTime = transmitTime + transit - skew
- // clockOffset = ((receiveTime - originateTime) + (transmitTime - responseTime))/2
- // = ((originateTime + transit + skew - originateTime) +
- // (transmitTime - (transmitTime + transit - skew)))/2
- // = ((transit + skew) + (transmitTime - transmitTime - transit + skew))/2
- // = (transit + skew - transit + skew)/2
- // = (2 * skew)/2 = skew
- long clockOffset = ((receiveTime - originateTime) + (transmitTime - responseTime))/2;
- EventLogTags.writeNtpSuccess(address.toString(), roundTripTime, clockOffset);
+ long totalTransactionDurationMillis = responseTicks - requestTicks;
+ long serverDurationMillis =
+ Duration64.between(receiveTimestamp, transmitTimestamp).toDuration().toMillis();
+ long roundTripTimeMillis = totalTransactionDurationMillis - serverDurationMillis;
+
+ Duration clockOffsetDuration = calculateClockOffset(requestTimestamp,
+ receiveTimestamp, transmitTimestamp, responseTimestamp);
+ long clockOffsetMillis = clockOffsetDuration.toMillis();
+
+ EventLogTags.writeNtpSuccess(
+ address.toString(), roundTripTimeMillis, clockOffsetMillis);
if (DBG) {
- Log.d(TAG, "round trip: " + roundTripTime + "ms, " +
- "clock offset: " + clockOffset + "ms");
+ Log.d(TAG, "round trip: " + roundTripTimeMillis + "ms, "
+ + "clock offset: " + clockOffsetMillis + "ms");
}
// save our results - use the times on this side of the network latency
// (response rather than request time)
- mNtpTime = responseTime + clockOffset;
+ mClockOffset = clockOffsetMillis;
+ mNtpTime = responseTime.plus(clockOffsetDuration).toEpochMilli();
mNtpTimeReference = responseTicks;
- mRoundTripTime = roundTripTime;
+ mRoundTripTime = roundTripTimeMillis;
} catch (Exception e) {
EventLogTags.writeNtpFailure(address.toString(), e.toString());
if (DBG) Log.d(TAG, "request time failed: " + e);
@@ -186,6 +213,28 @@
return true;
}
+ /** Performs the NTP clock offset calculation. */
+ @VisibleForTesting
+ public static Duration calculateClockOffset(Timestamp64 clientRequestTimestamp,
+ Timestamp64 serverReceiveTimestamp, Timestamp64 serverTransmitTimestamp,
+ Timestamp64 clientResponseTimestamp) {
+ // According to RFC4330:
+ // t is the system clock offset (the adjustment we are trying to find)
+ // t = ((T2 - T1) + (T3 - T4)) / 2
+ //
+ // Which is:
+ // t = (([server]receiveTimestamp - [client]requestTimestamp)
+ // + ([server]transmitTimestamp - [client]responseTimestamp)) / 2
+ //
+ // See the NTP spec and tests: the numeric types used are deliberate:
+ // + Duration64.between() uses 64-bit arithmetic (32-bit for the seconds).
+ // + plus() / dividedBy() use Duration, which isn't the double precision floating point
+ // used in NTPv4, but is good enough.
+ return Duration64.between(clientRequestTimestamp, serverReceiveTimestamp)
+ .plus(Duration64.between(clientResponseTimestamp, serverTransmitTimestamp))
+ .dividedBy(2);
+ }
+
@Deprecated
@UnsupportedAppUsage
public boolean requestTime(String host, int timeout) {
@@ -194,6 +243,14 @@
}
/**
+ * Returns the offset calculated to apply to the client clock to arrive at {@link #getNtpTime()}
+ */
+ @VisibleForTesting
+ public long getClockOffset() {
+ return mClockOffset;
+ }
+
+ /**
* Returns the time computed from the NTP transaction.
*
* @return time value computed from NTP server response.
@@ -225,8 +282,9 @@
}
private static void checkValidServerReply(
- byte leap, byte mode, int stratum, long transmitTime, long referenceTime)
- throws InvalidServerReplyException {
+ byte leap, byte mode, int stratum, Timestamp64 transmitTimestamp,
+ Timestamp64 referenceTimestamp, Timestamp64 randomizedRequestTimestamp,
+ Timestamp64 originateTimestamp) throws InvalidServerReplyException {
if (leap == NTP_LEAP_NOSYNC) {
throw new InvalidServerReplyException("unsynchronized server");
}
@@ -236,73 +294,68 @@
if ((stratum == NTP_STRATUM_DEATH) || (stratum > NTP_STRATUM_MAX)) {
throw new InvalidServerReplyException("untrusted stratum: " + stratum);
}
- if (transmitTime == 0) {
- throw new InvalidServerReplyException("zero transmitTime");
+ if (!randomizedRequestTimestamp.equals(originateTimestamp)) {
+ throw new InvalidServerReplyException(
+ "originateTimestamp != randomizedRequestTimestamp");
}
- if (referenceTime == 0) {
- throw new InvalidServerReplyException("zero reference timestamp");
+ if (transmitTimestamp.equals(Timestamp64.ZERO)) {
+ throw new InvalidServerReplyException("zero transmitTimestamp");
+ }
+ if (referenceTimestamp.equals(Timestamp64.ZERO)) {
+ throw new InvalidServerReplyException("zero referenceTimestamp");
}
}
/**
* Reads an unsigned 32 bit big endian number from the given offset in the buffer.
*/
- private long read32(byte[] buffer, int offset) {
- byte b0 = buffer[offset];
- byte b1 = buffer[offset+1];
- byte b2 = buffer[offset+2];
- byte b3 = buffer[offset+3];
+ private long readUnsigned32(byte[] buffer, int offset) {
+ int i0 = buffer[offset++] & 0xFF;
+ int i1 = buffer[offset++] & 0xFF;
+ int i2 = buffer[offset++] & 0xFF;
+ int i3 = buffer[offset] & 0xFF;
- // convert signed bytes to unsigned values
- int i0 = ((b0 & 0x80) == 0x80 ? (b0 & 0x7F) + 0x80 : b0);
- int i1 = ((b1 & 0x80) == 0x80 ? (b1 & 0x7F) + 0x80 : b1);
- int i2 = ((b2 & 0x80) == 0x80 ? (b2 & 0x7F) + 0x80 : b2);
- int i3 = ((b3 & 0x80) == 0x80 ? (b3 & 0x7F) + 0x80 : b3);
-
- return ((long)i0 << 24) + ((long)i1 << 16) + ((long)i2 << 8) + (long)i3;
+ int bits = (i0 << 24) | (i1 << 16) | (i2 << 8) | i3;
+ return bits & 0xFFFF_FFFFL;
}
/**
- * Reads the NTP time stamp at the given offset in the buffer and returns
- * it as a system time (milliseconds since January 1, 1970).
+ * Reads the NTP time stamp from the given offset in the buffer.
*/
- private long readTimeStamp(byte[] buffer, int offset) {
- long seconds = read32(buffer, offset);
- long fraction = read32(buffer, offset + 4);
- // Special case: zero means zero.
- if (seconds == 0 && fraction == 0) {
- return 0;
- }
- return ((seconds - OFFSET_1900_TO_1970) * 1000) + ((fraction * 1000L) / 0x100000000L);
+ private Timestamp64 readTimeStamp(byte[] buffer, int offset) {
+ long seconds = readUnsigned32(buffer, offset);
+ int fractionBits = (int) readUnsigned32(buffer, offset + 4);
+ return Timestamp64.fromComponents(seconds, fractionBits);
}
/**
- * Writes system time (milliseconds since January 1, 1970) as an NTP time stamp
- * at the given offset in the buffer.
+ * Writes the NTP time stamp at the given offset in the buffer.
*/
- private void writeTimeStamp(byte[] buffer, int offset, long time) {
- // Special case: zero means zero.
- if (time == 0) {
- Arrays.fill(buffer, offset, offset + 8, (byte) 0x00);
- return;
- }
-
- long seconds = time / 1000L;
- long milliseconds = time - seconds * 1000L;
- seconds += OFFSET_1900_TO_1970;
-
+ private void writeTimeStamp(byte[] buffer, int offset, Timestamp64 timestamp) {
+ long seconds = timestamp.getEraSeconds();
// write seconds in big endian format
- buffer[offset++] = (byte)(seconds >> 24);
- buffer[offset++] = (byte)(seconds >> 16);
- buffer[offset++] = (byte)(seconds >> 8);
- buffer[offset++] = (byte)(seconds >> 0);
+ buffer[offset++] = (byte) (seconds >>> 24);
+ buffer[offset++] = (byte) (seconds >>> 16);
+ buffer[offset++] = (byte) (seconds >>> 8);
+ buffer[offset++] = (byte) (seconds);
- long fraction = milliseconds * 0x100000000L / 1000L;
+ int fractionBits = timestamp.getFractionBits();
// write fraction in big endian format
- buffer[offset++] = (byte)(fraction >> 24);
- buffer[offset++] = (byte)(fraction >> 16);
- buffer[offset++] = (byte)(fraction >> 8);
- // low order bits should be random data
- buffer[offset++] = (byte)(Math.random() * 255.0);
+ buffer[offset++] = (byte) (fractionBits >>> 24);
+ buffer[offset++] = (byte) (fractionBits >>> 16);
+ buffer[offset++] = (byte) (fractionBits >>> 8);
+ buffer[offset] = (byte) (fractionBits);
+ }
+
+ private static Random defaultRandom() {
+ Random random;
+ try {
+ random = SecureRandom.getInstanceStrong();
+ } catch (NoSuchAlgorithmException e) {
+ // This should never happen.
+ Slog.wtf(TAG, "Unable to access SecureRandom", e);
+ random = new Random(System.currentTimeMillis());
+ }
+ return random;
}
}
diff --git a/core/java/android/net/sntp/Duration64.java b/core/java/android/net/sntp/Duration64.java
new file mode 100644
index 0000000..939b289
--- /dev/null
+++ b/core/java/android/net/sntp/Duration64.java
@@ -0,0 +1,141 @@
+/*
+ * Copyright (C) 2021 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 android.net.sntp;
+
+import java.time.Duration;
+
+/**
+ * A type similar to {@link Timestamp64} but used when calculating the difference between two
+ * timestamps. As such, it is a signed type, but still uses 64-bits in total and so can only
+ * represent half the magnitude of {@link Timestamp64}.
+ *
+ * <p>See <a href="https://www.eecis.udel.edu/~mills/time.html">4. Time Difference Calculations</a>.
+ *
+ * @hide
+ */
+public class Duration64 {
+
+ public static final Duration64 ZERO = new Duration64(0);
+ private final long mBits;
+
+ private Duration64(long bits) {
+ this.mBits = bits;
+ }
+
+ /**
+ * Returns the difference between two 64-bit NTP timestamps as a {@link Duration64}, as
+ * described in the NTP spec. The times represented by the timestamps have to be within {@link
+ * Timestamp64#MAX_SECONDS_IN_ERA} (~68 years) of each other for the calculation to produce a
+ * correct answer.
+ */
+ public static Duration64 between(Timestamp64 startInclusive, Timestamp64 endExclusive) {
+ long oneBits = (startInclusive.getEraSeconds() << 32)
+ | (startInclusive.getFractionBits() & 0xFFFF_FFFFL);
+ long twoBits = (endExclusive.getEraSeconds() << 32)
+ | (endExclusive.getFractionBits() & 0xFFFF_FFFFL);
+ long resultBits = twoBits - oneBits;
+ return new Duration64(resultBits);
+ }
+
+ /**
+ * Add two {@link Duration64} instances together. This performs the calculation in {@link
+ * Duration} and returns a {@link Duration} to increase the magnitude of accepted arguments,
+ * since {@link Duration64} only supports signed 32-bit seconds. The use of {@link Duration}
+ * limits precision to nanoseconds.
+ */
+ public Duration plus(Duration64 other) {
+ // From https://www.eecis.udel.edu/~mills/time.html:
+ // "The offset and delay calculations require sums and differences of these raw timestamp
+ // differences that can span no more than from 34 years in the future to 34 years in the
+ // past without overflow. This is a fundamental limitation in 64-bit integer calculations.
+ //
+ // In the NTPv4 reference implementation, all calculations involving offset and delay values
+ // use 64-bit floating double arithmetic, with the exception of raw timestamp subtraction,
+ // as mentioned above. The raw timestamp differences are then converted to 64-bit floating
+ // double format without loss of precision or chance of overflow in subsequent
+ // calculations."
+ //
+ // Here, we use Duration instead, which provides sufficient range, but loses precision below
+ // nanos.
+ return this.toDuration().plus(other.toDuration());
+ }
+
+ /**
+ * Returns a {@link Duration64} equivalent of the supplied duration, if the magnitude can be
+ * represented. Because {@link Duration64} uses a fixed point type for sub-second values it
+ * cannot represent all nanosecond values precisely and so the conversion can be lossy.
+ *
+ * @throws IllegalArgumentException if the supplied duration is too big to be represented
+ */
+ public static Duration64 fromDuration(Duration duration) {
+ long seconds = duration.getSeconds();
+ if (seconds < Integer.MIN_VALUE || seconds > Integer.MAX_VALUE) {
+ throw new IllegalArgumentException();
+ }
+ long bits = (seconds << 32)
+ | (Timestamp64.nanosToFractionBits(duration.getNano()) & 0xFFFF_FFFFL);
+ return new Duration64(bits);
+ }
+
+ /**
+ * Returns a {@link Duration} equivalent of this duration. Because {@link Duration64} uses a
+ * fixed point type for sub-second values it can values smaller than nanosecond precision and so
+ * the conversion can be lossy.
+ */
+ public Duration toDuration() {
+ int seconds = getSeconds();
+ int nanos = getNanos();
+ return Duration.ofSeconds(seconds, nanos);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ Duration64 that = (Duration64) o;
+ return mBits == that.mBits;
+ }
+
+ @Override
+ public int hashCode() {
+ return java.util.Objects.hash(mBits);
+ }
+
+ @Override
+ public String toString() {
+ Duration duration = toDuration();
+ return Long.toHexString(mBits)
+ + "(" + duration.getSeconds() + "s " + duration.getNano() + "ns)";
+ }
+
+ /**
+ * Returns the <em>signed</em> seconds in this duration.
+ */
+ public int getSeconds() {
+ return (int) (mBits >> 32);
+ }
+
+ /**
+ * Returns the <em>unsigned</em> nanoseconds in this duration (truncated).
+ */
+ public int getNanos() {
+ return Timestamp64.fractionBitsToNanos((int) (mBits & 0xFFFF_FFFFL));
+ }
+}
diff --git a/core/java/android/net/sntp/Timestamp64.java b/core/java/android/net/sntp/Timestamp64.java
new file mode 100644
index 0000000..81a3310
--- /dev/null
+++ b/core/java/android/net/sntp/Timestamp64.java
@@ -0,0 +1,186 @@
+/*
+ * Copyright (C) 2021 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 android.net.sntp;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import java.time.Instant;
+import java.util.Objects;
+import java.util.Random;
+
+/**
+ * The 64-bit type ("timestamp") that NTP uses to represent a point in time. It only holds the
+ * lowest 32-bits of the number of seconds since 1900-01-01 00:00:00. Consequently, to turn an
+ * instance into an unambiguous point in time the era number must be known. Era zero runs from
+ * 1900-01-01 00:00:00 to a date in 2036.
+ *
+ * It stores sub-second values using a 32-bit fixed point type, so it can resolve values smaller
+ * than a nanosecond, but is imprecise (i.e. it truncates).
+ *
+ * See also <a href=https://www.eecis.udel.edu/~mills/y2k.html>NTP docs</a>.
+ *
+ * @hide
+ */
+public final class Timestamp64 {
+
+ public static final Timestamp64 ZERO = fromComponents(0, 0);
+ static final int SUB_MILLIS_BITS_TO_RANDOMIZE = 32 - 10;
+
+ // Number of seconds between Jan 1, 1900 and Jan 1, 1970
+ // 70 years plus 17 leap days
+ static final long OFFSET_1900_TO_1970 = ((365L * 70L) + 17L) * 24L * 60L * 60L;
+ static final long MAX_SECONDS_IN_ERA = 0xFFFF_FFFFL;
+ static final long SECONDS_IN_ERA = MAX_SECONDS_IN_ERA + 1;
+
+ static final int NANOS_PER_SECOND = 1_000_000_000;
+
+ /** Creates a {@link Timestamp64} from the seconds and fraction components. */
+ public static Timestamp64 fromComponents(long eraSeconds, int fractionBits) {
+ return new Timestamp64(eraSeconds, fractionBits);
+ }
+
+ /** Creates a {@link Timestamp64} by decoding a string in the form "e4dc720c.4d4fc9eb". */
+ public static Timestamp64 fromString(String string) {
+ final int requiredLength = 17;
+ if (string.length() != requiredLength || string.charAt(8) != '.') {
+ throw new IllegalArgumentException(string);
+ }
+ String eraSecondsString = string.substring(0, 8);
+ String fractionString = string.substring(9);
+ long eraSeconds = Long.parseLong(eraSecondsString, 16);
+
+ // Use parseLong() because the type is unsigned. Integer.parseInt() will reject 0x70000000
+ // or above as being out of range.
+ long fractionBitsAsLong = Long.parseLong(fractionString, 16);
+ if (fractionBitsAsLong < 0 || fractionBitsAsLong > 0xFFFFFFFFL) {
+ throw new IllegalArgumentException("Invalid fractionBits:" + fractionString);
+ }
+ return new Timestamp64(eraSeconds, (int) fractionBitsAsLong);
+ }
+
+ /**
+ * Converts an {@link Instant} into a {@link Timestamp64}. This is lossy: Timestamp64 only
+ * contains the number of seconds in a given era, but the era is not stored. Also, sub-second
+ * values are not stored precisely.
+ */
+ public static Timestamp64 fromInstant(Instant instant) {
+ long ntpEraSeconds = instant.getEpochSecond() + OFFSET_1900_TO_1970;
+ if (ntpEraSeconds < 0) {
+ ntpEraSeconds = SECONDS_IN_ERA - (-ntpEraSeconds % SECONDS_IN_ERA);
+ }
+ ntpEraSeconds %= SECONDS_IN_ERA;
+
+ long nanos = instant.getNano();
+ int fractionBits = nanosToFractionBits(nanos);
+
+ return new Timestamp64(ntpEraSeconds, fractionBits);
+ }
+
+ private final long mEraSeconds;
+ private final int mFractionBits;
+
+ private Timestamp64(long eraSeconds, int fractionBits) {
+ if (eraSeconds < 0 || eraSeconds > MAX_SECONDS_IN_ERA) {
+ throw new IllegalArgumentException(
+ "Invalid parameters. seconds=" + eraSeconds + ", fraction=" + fractionBits);
+ }
+ this.mEraSeconds = eraSeconds;
+ this.mFractionBits = fractionBits;
+ }
+
+ /** Returns the number of seconds in the NTP era. */
+ public long getEraSeconds() {
+ return mEraSeconds;
+ }
+
+ /** Returns the fraction of a second as 32-bit, unsigned fixed-point bits. */
+ public int getFractionBits() {
+ return mFractionBits;
+ }
+
+ @Override
+ public String toString() {
+ return String.format("%08x.%08x", mEraSeconds, mFractionBits);
+ }
+
+ /** Returns the instant represented by this value in the specified NTP era. */
+ public Instant toInstant(int ntpEra) {
+ long secondsSinceEpoch = mEraSeconds - OFFSET_1900_TO_1970;
+ secondsSinceEpoch += ntpEra * SECONDS_IN_ERA;
+
+ int nanos = fractionBitsToNanos(mFractionBits);
+ return Instant.ofEpochSecond(secondsSinceEpoch, nanos);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ Timestamp64 that = (Timestamp64) o;
+ return mEraSeconds == that.mEraSeconds && mFractionBits == that.mFractionBits;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hash(mEraSeconds, mFractionBits);
+ }
+
+ static int fractionBitsToNanos(int fractionBits) {
+ long fractionBitsLong = fractionBits & 0xFFFF_FFFFL;
+ return (int) ((fractionBitsLong * NANOS_PER_SECOND) >>> 32);
+ }
+
+ static int nanosToFractionBits(long nanos) {
+ if (nanos > NANOS_PER_SECOND) {
+ throw new IllegalArgumentException();
+ }
+ return (int) ((nanos << 32) / NANOS_PER_SECOND);
+ }
+
+ /**
+ * Randomizes the fraction bits that represent sub-millisecond values. i.e. the randomization
+ * won't change the number of milliseconds represented after truncation. This is used to
+ * implement the part of the NTP spec that calls for clients with millisecond accuracy clocks
+ * to send randomized LSB values rather than zeros.
+ */
+ public Timestamp64 randomizeSubMillis(Random random) {
+ int randomizedFractionBits =
+ randomizeLowestBits(random, this.mFractionBits, SUB_MILLIS_BITS_TO_RANDOMIZE);
+ return new Timestamp64(mEraSeconds, randomizedFractionBits);
+ }
+
+ /**
+ * Randomizes the specified number of LSBs in {@code value} by using replacement bits from
+ * {@code Random.getNextInt()}.
+ */
+ @VisibleForTesting
+ public static int randomizeLowestBits(Random random, int value, int bitsToRandomize) {
+ if (bitsToRandomize < 1 || bitsToRandomize >= Integer.SIZE) {
+ // There's no point in randomizing all bits or none of the bits.
+ throw new IllegalArgumentException(Integer.toString(bitsToRandomize));
+ }
+
+ int upperBitMask = 0xFFFF_FFFF << bitsToRandomize;
+ int lowerBitMask = ~upperBitMask;
+
+ int randomValue = random.nextInt();
+ return (value & upperBitMask) | (randomValue & lowerBitMask);
+ }
+}
diff --git a/core/tests/coretests/src/android/net/SntpClientTest.java b/core/tests/coretests/src/android/net/SntpClientTest.java
index bf9978c..b400b9b 100644
--- a/core/tests/coretests/src/android/net/SntpClientTest.java
+++ b/core/tests/coretests/src/android/net/SntpClientTest.java
@@ -22,7 +22,10 @@
import static org.mockito.Mockito.CALLS_REAL_METHODS;
import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
+import android.net.sntp.Duration64;
+import android.net.sntp.Timestamp64;
import android.util.Log;
import androidx.test.runner.AndroidJUnit4;
@@ -38,7 +41,13 @@
import java.net.DatagramSocket;
import java.net.InetAddress;
import java.net.SocketException;
+import java.time.Duration;
+import java.time.Instant;
+import java.time.LocalDateTime;
+import java.time.ZoneOffset;
import java.util.Arrays;
+import java.util.Random;
+import java.util.function.Supplier;
@RunWith(AndroidJUnit4.class)
public class SntpClientTest {
@@ -54,41 +63,232 @@
//
// Server, Leap indicator: (0), Stratum 2 (secondary reference), poll 6 (64s), precision -20
// Root Delay: 0.005447, Root dispersion: 0.002716, Reference-ID: 221.253.71.41
- // Reference Timestamp: 3653932102.507969856 (2015/10/15 14:08:22)
- // Originator Timestamp: 3653932113.576327741 (2015/10/15 14:08:33)
- // Receive Timestamp: 3653932113.581012725 (2015/10/15 14:08:33)
- // Transmit Timestamp: 3653932113.581012725 (2015/10/15 14:08:33)
+ // Reference Timestamp:
+ // d9ca9446.820a5000 / ERA0: 2015-10-15 21:08:22 UTC / ERA1: 2151-11-22 03:36:38 UTC
+ // Originator Timestamp:
+ // d9ca9451.938a3771 / ERA0: 2015-10-15 21:08:33 UTC / ERA1: 2151-11-22 03:36:49 UTC
+ // Receive Timestamp:
+ // d9ca9451.94bd3fff / ERA0: 2015-10-15 21:08:33 UTC / ERA1: 2151-11-22 03:36:49 UTC
+ // Transmit Timestamp:
+ // d9ca9451.94bd4001 / ERA0: 2015-10-15 21:08:33 UTC / ERA1: 2151-11-22 03:36:49 UTC
+ //
// Originator - Receive Timestamp: +0.004684958
// Originator - Transmit Timestamp: +0.004684958
- private static final String WORKING_VERSION4 =
- "240206ec" +
- "00000165" +
- "000000b2" +
- "ddfd4729" +
- "d9ca9446820a5000" +
- "d9ca9451938a3771" +
- "d9ca945194bd3fff" +
- "d9ca945194bd4001";
+ private static final String LATE_ERA_RESPONSE =
+ "240206ec"
+ + "00000165"
+ + "000000b2"
+ + "ddfd4729"
+ + "d9ca9446820a5000"
+ + "d9ca9451938a3771"
+ + "d9ca945194bd3fff"
+ + "d9ca945194bd4001";
+
+ /** This is the actual UTC time in the server if it is in ERA0 */
+ private static final Instant LATE_ERA0_SERVER_TIME =
+ calculateIdealServerTime("d9ca9451.94bd3fff", "d9ca9451.94bd4001", 0);
+
+ /**
+ * This is the Unix epoch time matches the originate timestamp from {@link #LATE_ERA_RESPONSE}
+ * when interpreted as an ERA0 timestamp.
+ */
+ private static final Instant LATE_ERA0_REQUEST_TIME =
+ Timestamp64.fromString("d9ca9451.938a3771").toInstant(0);
+
+ // A tweaked version of the ERA0 response to represent an ERA 1 response.
+ //
+ // Server, Leap indicator: (0), Stratum 2 (secondary reference), poll 6 (64s), precision -20
+ // Root Delay: 0.005447, Root dispersion: 0.002716, Reference-ID: 221.253.71.41
+ // Reference Timestamp:
+ // 1db2d246.820a5000 / ERA0: 1915-10-16 21:08:22 UTC / ERA1: 2051-11-22 03:36:38 UTC
+ // Originate Timestamp:
+ // 1db2d251.938a3771 / ERA0: 1915-10-16 21:08:33 UTC / ERA1: 2051-11-22 03:36:49 UTC
+ // Receive Timestamp:
+ // 1db2d251.94bd3fff / ERA0: 1915-10-16 21:08:33 UTC / ERA1: 2051-11-22 03:36:49 UTC
+ // Transmit Timestamp:
+ // 1db2d251.94bd4001 / ERA0: 1915-10-16 21:08:33 UTC / ERA1: 2051-11-22 03:36:49 UTC
+ //
+ // Originate - Receive Timestamp: +0.004684958
+ // Originate - Transmit Timestamp: +0.004684958
+ private static final String EARLY_ERA_RESPONSE =
+ "240206ec"
+ + "00000165"
+ + "000000b2"
+ + "ddfd4729"
+ + "1db2d246820a5000"
+ + "1db2d251938a3771"
+ + "1db2d25194bd3fff"
+ + "1db2d25194bd4001";
+
+ /** This is the actual UTC time in the server if it is in ERA0 */
+ private static final Instant EARLY_ERA1_SERVER_TIME =
+ calculateIdealServerTime("1db2d251.94bd3fff", "1db2d251.94bd4001", 1);
+
+ /**
+ * This is the Unix epoch time matches the originate timestamp from {@link #EARLY_ERA_RESPONSE}
+ * when interpreted as an ERA1 timestamp.
+ */
+ private static final Instant EARLY_ERA1_REQUEST_TIME =
+ Timestamp64.fromString("1db2d251.938a3771").toInstant(1);
private SntpTestServer mServer;
private SntpClient mClient;
private Network mNetwork;
+ private Supplier<Instant> mSystemTimeSupplier;
+ private Random mRandom;
+ @SuppressWarnings("unchecked")
@Before
public void setUp() throws Exception {
+ mServer = new SntpTestServer();
+
// A mock network has NETID_UNSET, which allows the test to run, with a loopback server,
// even w/o external networking.
mNetwork = mock(Network.class, CALLS_REAL_METHODS);
- mServer = new SntpTestServer();
- mClient = new SntpClient();
+ mRandom = mock(Random.class);
+
+ mSystemTimeSupplier = mock(Supplier.class);
+ // Returning zero means the "randomized" bottom bits of the clients transmit timestamp /
+ // server's originate timestamp will be zeros.
+ when(mRandom.nextInt()).thenReturn(0);
+ mClient = new SntpClient(mSystemTimeSupplier, mRandom);
}
+ /** Tests when the client and server are in ERA0. b/199481251. */
@Test
- public void testBasicWorkingSntpClientQuery() throws Exception {
- mServer.setServerReply(HexEncoding.decode(WORKING_VERSION4.toCharArray(), false));
+ public void testRequestTime_era0ClientEra0RServer() throws Exception {
+ when(mSystemTimeSupplier.get()).thenReturn(LATE_ERA0_REQUEST_TIME);
+
+ mServer.setServerReply(HexEncoding.decode(LATE_ERA_RESPONSE.toCharArray(), false));
assertTrue(mClient.requestTime(mServer.getAddress(), mServer.getPort(), 500, mNetwork));
assertEquals(1, mServer.numRequestsReceived());
assertEquals(1, mServer.numRepliesSent());
+
+ checkRequestTimeCalcs(LATE_ERA0_REQUEST_TIME, LATE_ERA0_SERVER_TIME, mClient);
+ }
+
+ /** Tests when the client is behind the server and in the previous ERA. b/199481251. */
+ @Test
+ public void testRequestTime_era0ClientEra1Server() throws Exception {
+ when(mSystemTimeSupplier.get()).thenReturn(LATE_ERA0_REQUEST_TIME);
+
+ mServer.setServerReply(HexEncoding.decode(EARLY_ERA_RESPONSE.toCharArray(), false));
+ assertTrue(mClient.requestTime(mServer.getAddress(), mServer.getPort(), 500, mNetwork));
+ assertEquals(1, mServer.numRequestsReceived());
+ assertEquals(1, mServer.numRepliesSent());
+
+ checkRequestTimeCalcs(LATE_ERA0_REQUEST_TIME, EARLY_ERA1_SERVER_TIME, mClient);
+
+ }
+
+ /** Tests when the client is ahead of the server and in the next ERA. b/199481251. */
+ @Test
+ public void testRequestTime_era1ClientEra0Server() throws Exception {
+ when(mSystemTimeSupplier.get()).thenReturn(EARLY_ERA1_REQUEST_TIME);
+
+ mServer.setServerReply(HexEncoding.decode(LATE_ERA_RESPONSE.toCharArray(), false));
+ assertTrue(mClient.requestTime(mServer.getAddress(), mServer.getPort(), 500, mNetwork));
+ assertEquals(1, mServer.numRequestsReceived());
+ assertEquals(1, mServer.numRepliesSent());
+
+ checkRequestTimeCalcs(EARLY_ERA1_REQUEST_TIME, LATE_ERA0_SERVER_TIME, mClient);
+ }
+
+ /** Tests when the client and server are in ERA1. b/199481251. */
+ @Test
+ public void testRequestTime_era1ClientEra1Server() throws Exception {
+ when(mSystemTimeSupplier.get()).thenReturn(EARLY_ERA1_REQUEST_TIME);
+
+ mServer.setServerReply(HexEncoding.decode(EARLY_ERA_RESPONSE.toCharArray(), false));
+ assertTrue(mClient.requestTime(mServer.getAddress(), mServer.getPort(), 500, mNetwork));
+ assertEquals(1, mServer.numRequestsReceived());
+ assertEquals(1, mServer.numRepliesSent());
+
+ checkRequestTimeCalcs(EARLY_ERA1_REQUEST_TIME, EARLY_ERA1_SERVER_TIME, mClient);
+ }
+
+ private static void checkRequestTimeCalcs(
+ Instant clientTime, Instant serverTime, SntpClient client) {
+ // The tests don't attempt to control the elapsed time tracking, which influences the
+ // round trip time (i.e. time spent in due to the network), but they control everything
+ // else, so assertions are allowed some slop and round trip time just has to be >= 0.
+ assertTrue("getRoundTripTime()=" + client.getRoundTripTime(),
+ client.getRoundTripTime() >= 0);
+
+ // Calculate the ideal offset if nothing took any time.
+ long expectedOffset = serverTime.toEpochMilli() - clientTime.toEpochMilli();
+ long allowedSlop = (client.getRoundTripTime() / 2) + 1; // +1 to allow for truncation loss.
+ assertNearlyEquals(expectedOffset, client.getClockOffset(), allowedSlop);
+ assertNearlyEquals(clientTime.toEpochMilli() + expectedOffset,
+ client.getNtpTime(), allowedSlop);
+ }
+
+ /**
+ * Unit tests for the low-level offset calculations. More targeted / easier to write than the
+ * end-to-end tests above that simulate the server. b/199481251.
+ */
+ @Test
+ public void testCalculateClockOffset() {
+ Instant era0Time1 = utcInstant(2021, 10, 5, 2, 2, 2, 2);
+ // Confirm what happens when the client and server are completely in sync.
+ checkCalculateClockOffset(era0Time1, era0Time1);
+
+ Instant era0Time2 = utcInstant(2021, 10, 6, 1, 1, 1, 1);
+ checkCalculateClockOffset(era0Time1, era0Time2);
+ checkCalculateClockOffset(era0Time2, era0Time1);
+
+ Instant era1Time1 = utcInstant(2061, 10, 5, 2, 2, 2, 2);
+ checkCalculateClockOffset(era1Time1, era1Time1);
+
+ Instant era1Time2 = utcInstant(2061, 10, 6, 1, 1, 1, 1);
+ checkCalculateClockOffset(era1Time1, era1Time2);
+ checkCalculateClockOffset(era1Time2, era1Time1);
+
+ // Cross-era calcs (requires they are still within 68 years of each other).
+ checkCalculateClockOffset(era0Time1, era1Time1);
+ checkCalculateClockOffset(era1Time1, era0Time1);
+ }
+
+ private void checkCalculateClockOffset(Instant clientTime, Instant serverTime) {
+ // The expected (ideal) offset is the difference between the client and server clocks. NTP
+ // assumes delays are symmetric, i.e. that the server time is between server
+ // receive/transmit time, client time is between request/response time, and send networking
+ // delay == receive networking delay.
+ Duration expectedOffset = Duration.between(clientTime, serverTime);
+
+ // Try simulating various round trip delays, including zero.
+ for (long totalElapsedTimeMillis : Arrays.asList(0, 20, 200, 2000, 20000)) {
+ // Simulate that a 10% of the elapsed time is due to time spent in the server, the rest
+ // is network / client processing time.
+ long simulatedServerElapsedTimeMillis = totalElapsedTimeMillis / 10;
+ long simulatedClientElapsedTimeMillis = totalElapsedTimeMillis;
+
+ // Create some symmetrical timestamps.
+ Timestamp64 clientRequestTimestamp = Timestamp64.fromInstant(
+ clientTime.minusMillis(simulatedClientElapsedTimeMillis / 2));
+ Timestamp64 clientResponseTimestamp = Timestamp64.fromInstant(
+ clientTime.plusMillis(simulatedClientElapsedTimeMillis / 2));
+ Timestamp64 serverReceiveTimestamp = Timestamp64.fromInstant(
+ serverTime.minusMillis(simulatedServerElapsedTimeMillis / 2));
+ Timestamp64 serverTransmitTimestamp = Timestamp64.fromInstant(
+ serverTime.plusMillis(simulatedServerElapsedTimeMillis / 2));
+
+ Duration actualOffset = SntpClient.calculateClockOffset(
+ clientRequestTimestamp, serverReceiveTimestamp,
+ serverTransmitTimestamp, clientResponseTimestamp);
+
+ // We allow up to 1ms variation because NTP types are lossy and the simulated elapsed
+ // time millis may not divide exactly.
+ int allowedSlopMillis = 1;
+ assertNearlyEquals(
+ expectedOffset.toMillis(), actualOffset.toMillis(), allowedSlopMillis);
+ }
+ }
+
+ private static Instant utcInstant(
+ int year, int monthOfYear, int day, int hour, int minute, int second, int nanos) {
+ return LocalDateTime.of(year, monthOfYear, day, hour, minute, second, nanos)
+ .toInstant(ZoneOffset.UTC);
}
@Test
@@ -98,6 +298,8 @@
@Test
public void testTimeoutFailure() throws Exception {
+ when(mSystemTimeSupplier.get()).thenReturn(LATE_ERA0_REQUEST_TIME);
+
mServer.clearServerReply();
assertFalse(mClient.requestTime(mServer.getAddress(), mServer.getPort(), 500, mNetwork));
assertEquals(1, mServer.numRequestsReceived());
@@ -106,7 +308,9 @@
@Test
public void testIgnoreLeapNoSync() throws Exception {
- final byte[] reply = HexEncoding.decode(WORKING_VERSION4.toCharArray(), false);
+ when(mSystemTimeSupplier.get()).thenReturn(LATE_ERA0_REQUEST_TIME);
+
+ final byte[] reply = HexEncoding.decode(LATE_ERA_RESPONSE.toCharArray(), false);
reply[0] |= (byte) 0xc0;
mServer.setServerReply(reply);
assertFalse(mClient.requestTime(mServer.getAddress(), mServer.getPort(), 500, mNetwork));
@@ -116,7 +320,9 @@
@Test
public void testAcceptOnlyServerAndBroadcastModes() throws Exception {
- final byte[] reply = HexEncoding.decode(WORKING_VERSION4.toCharArray(), false);
+ when(mSystemTimeSupplier.get()).thenReturn(LATE_ERA0_REQUEST_TIME);
+
+ final byte[] reply = HexEncoding.decode(LATE_ERA_RESPONSE.toCharArray(), false);
for (int i = 0; i <= 7; i++) {
final String logMsg = "mode: " + i;
reply[0] &= (byte) 0xf8;
@@ -140,10 +346,12 @@
@Test
public void testAcceptableStrataOnly() throws Exception {
+ when(mSystemTimeSupplier.get()).thenReturn(LATE_ERA0_REQUEST_TIME);
+
final int STRATUM_MIN = 1;
final int STRATUM_MAX = 15;
- final byte[] reply = HexEncoding.decode(WORKING_VERSION4.toCharArray(), false);
+ final byte[] reply = HexEncoding.decode(LATE_ERA_RESPONSE.toCharArray(), false);
for (int i = 0; i < 256; i++) {
final String logMsg = "stratum: " + i;
reply[1] = (byte) i;
@@ -162,7 +370,9 @@
@Test
public void testZeroTransmitTime() throws Exception {
- final byte[] reply = HexEncoding.decode(WORKING_VERSION4.toCharArray(), false);
+ when(mSystemTimeSupplier.get()).thenReturn(LATE_ERA0_REQUEST_TIME);
+
+ final byte[] reply = HexEncoding.decode(LATE_ERA_RESPONSE.toCharArray(), false);
Arrays.fill(reply, TRANSMIT_TIME_OFFSET, TRANSMIT_TIME_OFFSET + 8, (byte) 0x00);
mServer.setServerReply(reply);
assertFalse(mClient.requestTime(mServer.getAddress(), mServer.getPort(), 500, mNetwork));
@@ -170,6 +380,19 @@
assertEquals(1, mServer.numRepliesSent());
}
+ @Test
+ public void testNonMatchingOriginateTime() throws Exception {
+ when(mSystemTimeSupplier.get()).thenReturn(LATE_ERA0_REQUEST_TIME);
+
+ final byte[] reply = HexEncoding.decode(LATE_ERA_RESPONSE.toCharArray(), false);
+ mServer.setServerReply(reply);
+ mServer.setGenerateValidOriginateTimestamp(false);
+
+ assertFalse(mClient.requestTime(mServer.getAddress(), mServer.getPort(), 500, mNetwork));
+ assertEquals(1, mServer.numRequestsReceived());
+ assertEquals(1, mServer.numRepliesSent());
+ }
+
private static class SntpTestServer {
private final Object mLock = new Object();
@@ -177,6 +400,7 @@
private final InetAddress mAddress;
private final int mPort;
private byte[] mReply;
+ private boolean mGenerateValidOriginateTimestamp = true;
private int mRcvd;
private int mSent;
private Thread mListeningThread;
@@ -201,10 +425,16 @@
synchronized (mLock) {
mRcvd++;
if (mReply == null) { continue; }
- // Copy transmit timestamp into originate timestamp.
- // TODO: bounds checking.
- System.arraycopy(ntpMsg.getData(), TRANSMIT_TIME_OFFSET,
- mReply, ORIGINATE_TIME_OFFSET, 8);
+ if (mGenerateValidOriginateTimestamp) {
+ // Copy the transmit timestamp into originate timestamp: This is
+ // validated by well-behaved clients.
+ System.arraycopy(ntpMsg.getData(), TRANSMIT_TIME_OFFSET,
+ mReply, ORIGINATE_TIME_OFFSET, 8);
+ } else {
+ // Fill it with junk instead.
+ Arrays.fill(mReply, ORIGINATE_TIME_OFFSET,
+ ORIGINATE_TIME_OFFSET + 8, (byte) 0xFF);
+ }
ntpMsg.setData(mReply);
ntpMsg.setLength(mReply.length);
try {
@@ -245,9 +475,38 @@
}
}
+ /**
+ * Controls the test server's behavior of copying the client's transmit timestamp into the
+ * response's originate timestamp (which is required of a real server).
+ */
+ public void setGenerateValidOriginateTimestamp(boolean enabled) {
+ synchronized (mLock) {
+ mGenerateValidOriginateTimestamp = enabled;
+ }
+ }
+
public InetAddress getAddress() { return mAddress; }
public int getPort() { return mPort; }
public int numRequestsReceived() { synchronized (mLock) { return mRcvd; } }
public int numRepliesSent() { synchronized (mLock) { return mSent; } }
}
+
+ /**
+ * Generates the "real" server time assuming it is exactly between the receive and transmit
+ * timestamp and in the NTP era specified.
+ */
+ private static Instant calculateIdealServerTime(String receiveTimestampString,
+ String transmitTimestampString, int era) {
+ Timestamp64 receiveTimestamp = Timestamp64.fromString(receiveTimestampString);
+ Timestamp64 transmitTimestamp = Timestamp64.fromString(transmitTimestampString);
+ Duration serverProcessingTime =
+ Duration64.between(receiveTimestamp, transmitTimestamp).toDuration();
+ return receiveTimestamp.toInstant(era)
+ .plusMillis(serverProcessingTime.dividedBy(2).toMillis());
+ }
+
+ private static void assertNearlyEquals(long expected, long actual, long allowedSlop) {
+ assertTrue("expected=" + expected + ", actual=" + actual + ", allowedSlop=" + allowedSlop,
+ actual >= expected - allowedSlop && actual <= expected + allowedSlop);
+ }
}
diff --git a/core/tests/coretests/src/android/net/sntp/Duration64Test.java b/core/tests/coretests/src/android/net/sntp/Duration64Test.java
new file mode 100644
index 0000000..933800f
--- /dev/null
+++ b/core/tests/coretests/src/android/net/sntp/Duration64Test.java
@@ -0,0 +1,264 @@
+/*
+ * Copyright (C) 2021 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 android.net.sntp;
+
+import static android.net.sntp.Timestamp64.NANOS_PER_SECOND;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertTrue;
+
+import org.junit.Test;
+
+import java.time.Duration;
+import java.time.Instant;
+import java.time.LocalDateTime;
+import java.time.ZoneOffset;
+
+public class Duration64Test {
+
+ @Test
+ public void testBetween_rangeChecks() {
+ long maxDuration64Seconds = Timestamp64.MAX_SECONDS_IN_ERA / 2;
+
+ Timestamp64 zeroNoFrac = Timestamp64.fromComponents(0, 0);
+ assertEquals(Duration64.ZERO, Duration64.between(zeroNoFrac, zeroNoFrac));
+
+ {
+ Timestamp64 ceilNoFrac = Timestamp64.fromComponents(maxDuration64Seconds, 0);
+ assertEquals(Duration64.ZERO, Duration64.between(ceilNoFrac, ceilNoFrac));
+
+ long expectedNanos = maxDuration64Seconds * NANOS_PER_SECOND;
+ assertEquals(Duration.ofNanos(expectedNanos),
+ Duration64.between(zeroNoFrac, ceilNoFrac).toDuration());
+ assertEquals(Duration.ofNanos(-expectedNanos),
+ Duration64.between(ceilNoFrac, zeroNoFrac).toDuration());
+ }
+
+ {
+ // This value is the largest fraction of a second representable. It is 1-(1/2^32)), and
+ // so numerically larger than 999_999_999 nanos.
+ int fractionBits = 0xFFFF_FFFF;
+ Timestamp64 ceilWithFrac = Timestamp64
+ .fromComponents(maxDuration64Seconds, fractionBits);
+ assertEquals(Duration64.ZERO, Duration64.between(ceilWithFrac, ceilWithFrac));
+
+ long expectedNanos = maxDuration64Seconds * NANOS_PER_SECOND + 999_999_999;
+ assertEquals(
+ Duration.ofNanos(expectedNanos),
+ Duration64.between(zeroNoFrac, ceilWithFrac).toDuration());
+ // The -1 nanos demonstrates asymmetry due to the way Duration64 has different
+ // precision / range of sub-second fractions.
+ assertEquals(
+ Duration.ofNanos(-expectedNanos - 1),
+ Duration64.between(ceilWithFrac, zeroNoFrac).toDuration());
+ }
+ }
+
+ @Test
+ public void testBetween_smallSecondsOnly() {
+ long expectedNanos = 5L * NANOS_PER_SECOND;
+ assertEquals(Duration.ofNanos(expectedNanos),
+ Duration64.between(Timestamp64.fromComponents(5, 0),
+ Timestamp64.fromComponents(10, 0))
+ .toDuration());
+ assertEquals(Duration.ofNanos(-expectedNanos),
+ Duration64.between(Timestamp64.fromComponents(10, 0),
+ Timestamp64.fromComponents(5, 0))
+ .toDuration());
+ }
+
+ @Test
+ public void testBetween_smallSecondsAndFraction() {
+ // Choose a nanos values we know can be represented exactly with fixed point binary (1/2
+ // second, 1/4 second, etc.).
+ {
+ long expectedNanos = 5L * NANOS_PER_SECOND + 500_000_000L;
+ int fractionHalfSecond = 0x8000_0000;
+ assertEquals(Duration.ofNanos(expectedNanos),
+ Duration64.between(
+ Timestamp64.fromComponents(5, 0),
+ Timestamp64.fromComponents(10, fractionHalfSecond)).toDuration());
+ assertEquals(Duration.ofNanos(-expectedNanos),
+ Duration64.between(
+ Timestamp64.fromComponents(10, fractionHalfSecond),
+ Timestamp64.fromComponents(5, 0)).toDuration());
+ }
+
+ {
+ long expectedNanos = 5L * NANOS_PER_SECOND + 250_000_000L;
+ int fractionHalfSecond = 0x8000_0000;
+ int fractionQuarterSecond = 0x4000_0000;
+
+ assertEquals(Duration.ofNanos(expectedNanos),
+ Duration64.between(
+ Timestamp64.fromComponents(5, fractionQuarterSecond),
+ Timestamp64.fromComponents(10, fractionHalfSecond)).toDuration());
+ assertEquals(Duration.ofNanos(-expectedNanos),
+ Duration64.between(
+ Timestamp64.fromComponents(10, fractionHalfSecond),
+ Timestamp64.fromComponents(5, fractionQuarterSecond)).toDuration());
+ }
+
+ }
+
+ @Test
+ public void testBetween_sameEra0() {
+ int arbitraryEra0Year = 2021;
+ Instant one = utcInstant(arbitraryEra0Year, 1, 1, 0, 0, 0, 500);
+ assertNtpEraOfInstant(one, 0);
+
+ checkDuration64Behavior(one, one);
+
+ Instant two = utcInstant(arbitraryEra0Year + 1, 1, 1, 0, 0, 0, 250);
+ assertNtpEraOfInstant(two, 0);
+
+ checkDuration64Behavior(one, two);
+ checkDuration64Behavior(two, one);
+ }
+
+ @Test
+ public void testBetween_sameEra1() {
+ int arbitraryEra1Year = 2037;
+ Instant one = utcInstant(arbitraryEra1Year, 1, 1, 0, 0, 0, 500);
+ assertNtpEraOfInstant(one, 1);
+
+ checkDuration64Behavior(one, one);
+
+ Instant two = utcInstant(arbitraryEra1Year + 1, 1, 1, 0, 0, 0, 250);
+ assertNtpEraOfInstant(two, 1);
+
+ checkDuration64Behavior(one, two);
+ checkDuration64Behavior(two, one);
+ }
+
+ /**
+ * Tests that two timestamps can originate from times in different eras, and the works
+ * calculation still works providing the two times aren't more than 68 years apart (half of the
+ * 136 years representable using an unsigned 32-bit seconds representation).
+ */
+ @Test
+ public void testBetween_adjacentEras() {
+ int yearsSeparation = 68;
+
+ // This year just needs to be < 68 years before the end of NTP timestamp era 0.
+ int arbitraryYearInEra0 = 2021;
+
+ Instant one = utcInstant(arbitraryYearInEra0, 1, 1, 0, 0, 0, 500);
+ assertNtpEraOfInstant(one, 0);
+
+ checkDuration64Behavior(one, one);
+
+ Instant two = utcInstant(arbitraryYearInEra0 + yearsSeparation, 1, 1, 0, 0, 0, 250);
+ assertNtpEraOfInstant(two, 1);
+
+ checkDuration64Behavior(one, two);
+ checkDuration64Behavior(two, one);
+ }
+
+ /**
+ * This test confirms that duration calculations fail in the expected fashion if two
+ * Timestamp64s are more than 2^31 seconds apart.
+ *
+ * <p>The types / math specified by NTP for timestamps deliberately takes place in 64-bit signed
+ * arithmetic for the bits used to represent timestamps (32-bit unsigned integer seconds,
+ * 32-bits fixed point for fraction of seconds). Timestamps can therefore represent ~136 years
+ * of seconds.
+ * When subtracting one timestamp from another, we end up with a signed 32-bit seconds value.
+ * This means the max duration representable is ~68 years before numbers will over or underflow.
+ * i.e. the client and server are in the same or adjacent NTP eras and the difference in their
+ * clocks isn't more than ~68 years. >= ~68 years and things break down.
+ */
+ @Test
+ public void testBetween_tooFarApart() {
+ int tooManyYearsSeparation = 68 + 1;
+
+ Instant one = utcInstant(2021, 1, 1, 0, 0, 0, 500);
+ assertNtpEraOfInstant(one, 0);
+ Instant two = utcInstant(2021 + tooManyYearsSeparation, 1, 1, 0, 0, 0, 250);
+ assertNtpEraOfInstant(two, 1);
+
+ checkDuration64OverflowBehavior(one, two);
+ checkDuration64OverflowBehavior(two, one);
+ }
+
+ private static void checkDuration64Behavior(Instant one, Instant two) {
+ // This is the answer if we perform the arithmetic in a lossless fashion.
+ Duration expectedDuration = Duration.between(one, two);
+ Duration64 expectedDuration64 = Duration64.fromDuration(expectedDuration);
+
+ // Sub-second precision is limited in Timestamp64, so we can lose 1ms.
+ assertEqualsOrSlightlyLessThan(
+ expectedDuration.toMillis(), expectedDuration64.toDuration().toMillis());
+
+ Timestamp64 one64 = Timestamp64.fromInstant(one);
+ Timestamp64 two64 = Timestamp64.fromInstant(two);
+
+ // This is the answer if we perform the arithmetic in a lossy fashion.
+ Duration64 actualDuration64 = Duration64.between(one64, two64);
+ assertEquals(expectedDuration64.getSeconds(), actualDuration64.getSeconds());
+ assertEqualsOrSlightlyLessThan(expectedDuration64.getNanos(), actualDuration64.getNanos());
+ }
+
+ private static void checkDuration64OverflowBehavior(Instant one, Instant two) {
+ // This is the answer if we perform the arithmetic in a lossless fashion.
+ Duration trueDuration = Duration.between(one, two);
+
+ // Confirm the maths is expected to overflow / underflow.
+ assertTrue(trueDuration.getSeconds() > Integer.MAX_VALUE / 2
+ || trueDuration.getSeconds() < Integer.MIN_VALUE / 2);
+
+ // Now perform the arithmetic as specified for NTP: do subtraction using the 64-bit
+ // timestamp.
+ Timestamp64 one64 = Timestamp64.fromInstant(one);
+ Timestamp64 two64 = Timestamp64.fromInstant(two);
+
+ Duration64 actualDuration64 = Duration64.between(one64, two64);
+ assertNotEquals(trueDuration.getSeconds(), actualDuration64.getSeconds());
+ }
+
+ /**
+ * Asserts the instant provided is in the specified NTP timestamp era. Used to confirm /
+ * document values picked for tests have the properties needed.
+ */
+ private static void assertNtpEraOfInstant(Instant one, int ntpEra) {
+ long expectedSeconds = one.getEpochSecond();
+
+ // The conversion to Timestamp64 is lossy (it loses the era). We then supply the expected
+ // era. If the era was correct, we will end up with the value we started with (modulo nano
+ // precision loss). If the era is wrong, we won't.
+ Instant roundtrippedInstant = Timestamp64.fromInstant(one).toInstant(ntpEra);
+
+ long actualSeconds = roundtrippedInstant.getEpochSecond();
+ assertEquals(expectedSeconds, actualSeconds);
+ }
+
+ /**
+ * Used to account for the fact that NTP types used 32-bit fixed point storage, so cannot store
+ * all values precisely. The value we get out will always be the value we put in, or one that is
+ * one unit smaller (due to truncation).
+ */
+ private static void assertEqualsOrSlightlyLessThan(long expected, long actual) {
+ assertTrue("expected=" + expected + ", actual=" + actual,
+ expected == actual || expected == actual - 1);
+ }
+
+ private static Instant utcInstant(
+ int year, int monthOfYear, int day, int hour, int minute, int second, int nanos) {
+ return LocalDateTime.of(year, monthOfYear, day, hour, minute, second, nanos)
+ .toInstant(ZoneOffset.UTC);
+ }
+}
diff --git a/core/tests/coretests/src/android/net/sntp/PredictableRandom.java b/core/tests/coretests/src/android/net/sntp/PredictableRandom.java
new file mode 100644
index 0000000..bb2922b
--- /dev/null
+++ b/core/tests/coretests/src/android/net/sntp/PredictableRandom.java
@@ -0,0 +1,34 @@
+/*
+ * Copyright (C) 2021 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 android.net.sntp;
+
+import java.util.Random;
+
+class PredictableRandom extends Random {
+ private int[] mIntSequence = new int[] { 1 };
+ private int mIntPos = 0;
+
+ public void setIntSequence(int[] intSequence) {
+ this.mIntSequence = intSequence;
+ }
+
+ @Override
+ public int nextInt() {
+ int value = mIntSequence[mIntPos++];
+ mIntPos %= mIntSequence.length;
+ return value;
+ }
+}
diff --git a/core/tests/coretests/src/android/net/sntp/Timestamp64Test.java b/core/tests/coretests/src/android/net/sntp/Timestamp64Test.java
new file mode 100644
index 0000000..c923812
--- /dev/null
+++ b/core/tests/coretests/src/android/net/sntp/Timestamp64Test.java
@@ -0,0 +1,309 @@
+/*
+ * Copyright (C) 2021 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 android.net.sntp;
+
+import static android.net.sntp.Timestamp64.NANOS_PER_SECOND;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import org.junit.Test;
+
+import java.time.Instant;
+import java.util.HashSet;
+import java.util.Random;
+import java.util.Set;
+
+public class Timestamp64Test {
+
+ @Test
+ public void testFromComponents() {
+ long minNtpEraSeconds = 0;
+ long maxNtpEraSeconds = 0xFFFFFFFFL;
+
+ expectIllegalArgumentException(() -> Timestamp64.fromComponents(minNtpEraSeconds - 1, 0));
+ expectIllegalArgumentException(() -> Timestamp64.fromComponents(maxNtpEraSeconds + 1, 0));
+
+ assertComponentCreation(minNtpEraSeconds, 0);
+ assertComponentCreation(maxNtpEraSeconds, 0);
+ assertComponentCreation(maxNtpEraSeconds, Integer.MIN_VALUE);
+ assertComponentCreation(maxNtpEraSeconds, Integer.MAX_VALUE);
+ }
+
+ private static void assertComponentCreation(long ntpEraSeconds, int fractionBits) {
+ Timestamp64 value = Timestamp64.fromComponents(ntpEraSeconds, fractionBits);
+ assertEquals(ntpEraSeconds, value.getEraSeconds());
+ assertEquals(fractionBits, value.getFractionBits());
+ }
+
+ @Test
+ public void testEqualsAndHashcode() {
+ assertEqualsAndHashcode(0, 0);
+ assertEqualsAndHashcode(1, 0);
+ assertEqualsAndHashcode(0, 1);
+ }
+
+ private static void assertEqualsAndHashcode(int eraSeconds, int fractionBits) {
+ Timestamp64 one = Timestamp64.fromComponents(eraSeconds, fractionBits);
+ Timestamp64 two = Timestamp64.fromComponents(eraSeconds, fractionBits);
+ assertEquals(one, two);
+ assertEquals(one.hashCode(), two.hashCode());
+ }
+
+ @Test
+ public void testStringForm() {
+ expectIllegalArgumentException(() -> Timestamp64.fromString(""));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("."));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("1234567812345678"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("12345678?12345678"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("12345678..12345678"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("1.12345678"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("12.12345678"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("123456.12345678"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("1234567.12345678"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("12345678.1"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("12345678.12"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("12345678.123456"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("12345678.1234567"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("X2345678.12345678"));
+ expectIllegalArgumentException(() -> Timestamp64.fromString("12345678.X2345678"));
+
+ assertStringCreation("00000000.00000000", 0, 0);
+ assertStringCreation("00000001.00000001", 1, 1);
+ assertStringCreation("ffffffff.ffffffff", 0xFFFFFFFFL, 0xFFFFFFFF);
+ }
+
+ private static void assertStringCreation(
+ String string, long expectedSeconds, int expectedFractionBits) {
+ Timestamp64 timestamp64 = Timestamp64.fromString(string);
+ assertEquals(string, timestamp64.toString());
+ assertEquals(expectedSeconds, timestamp64.getEraSeconds());
+ assertEquals(expectedFractionBits, timestamp64.getFractionBits());
+ }
+
+ @Test
+ public void testStringForm_lenientHexCasing() {
+ Timestamp64 mixedCaseValue = Timestamp64.fromString("AaBbCcDd.EeFf1234");
+ assertEquals(0xAABBCCDDL, mixedCaseValue.getEraSeconds());
+ assertEquals(0xEEFF1234, mixedCaseValue.getFractionBits());
+ }
+
+ @Test
+ public void testFromInstant_secondsHandling() {
+ final int era0 = 0;
+ final int eraNeg1 = -1;
+ final int eraNeg2 = -2;
+ final int era1 = 1;
+
+ assertInstantCreationOnlySeconds(-Timestamp64.OFFSET_1900_TO_1970, 0, era0);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.OFFSET_1900_TO_1970 - Timestamp64.SECONDS_IN_ERA, 0, eraNeg1);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.OFFSET_1900_TO_1970 + Timestamp64.SECONDS_IN_ERA, 0, era1);
+
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.OFFSET_1900_TO_1970 - 1, Timestamp64.MAX_SECONDS_IN_ERA, -1);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.OFFSET_1900_TO_1970 - Timestamp64.SECONDS_IN_ERA - 1,
+ Timestamp64.MAX_SECONDS_IN_ERA, eraNeg2);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.OFFSET_1900_TO_1970 + Timestamp64.SECONDS_IN_ERA - 1,
+ Timestamp64.MAX_SECONDS_IN_ERA, era0);
+
+ assertInstantCreationOnlySeconds(-Timestamp64.OFFSET_1900_TO_1970 + 1, 1, era0);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.OFFSET_1900_TO_1970 - Timestamp64.SECONDS_IN_ERA + 1, 1, eraNeg1);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.OFFSET_1900_TO_1970 + Timestamp64.SECONDS_IN_ERA + 1, 1, era1);
+
+ assertInstantCreationOnlySeconds(0, Timestamp64.OFFSET_1900_TO_1970, era0);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.SECONDS_IN_ERA, Timestamp64.OFFSET_1900_TO_1970, eraNeg1);
+ assertInstantCreationOnlySeconds(
+ Timestamp64.SECONDS_IN_ERA, Timestamp64.OFFSET_1900_TO_1970, era1);
+
+ assertInstantCreationOnlySeconds(1, Timestamp64.OFFSET_1900_TO_1970 + 1, era0);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.SECONDS_IN_ERA + 1, Timestamp64.OFFSET_1900_TO_1970 + 1, eraNeg1);
+ assertInstantCreationOnlySeconds(
+ Timestamp64.SECONDS_IN_ERA + 1, Timestamp64.OFFSET_1900_TO_1970 + 1, era1);
+
+ assertInstantCreationOnlySeconds(-1, Timestamp64.OFFSET_1900_TO_1970 - 1, era0);
+ assertInstantCreationOnlySeconds(
+ -Timestamp64.SECONDS_IN_ERA - 1, Timestamp64.OFFSET_1900_TO_1970 - 1, eraNeg1);
+ assertInstantCreationOnlySeconds(
+ Timestamp64.SECONDS_IN_ERA - 1, Timestamp64.OFFSET_1900_TO_1970 - 1, era1);
+ }
+
+ private static void assertInstantCreationOnlySeconds(
+ long epochSeconds, long expectedNtpEraSeconds, int ntpEra) {
+ int nanosOfSecond = 0;
+ Instant instant = Instant.ofEpochSecond(epochSeconds, nanosOfSecond);
+ Timestamp64 timestamp = Timestamp64.fromInstant(instant);
+ assertEquals(expectedNtpEraSeconds, timestamp.getEraSeconds());
+
+ int expectedFractionBits = 0;
+ assertEquals(expectedFractionBits, timestamp.getFractionBits());
+
+ // Confirm the Instant can be round-tripped if we know the era. Also assumes the nanos can
+ // be stored precisely; 0 can be.
+ Instant roundTrip = timestamp.toInstant(ntpEra);
+ assertEquals(instant, roundTrip);
+ }
+
+ @Test
+ public void testFromInstant_fractionHandling() {
+ // Try some values we know can be represented exactly.
+ assertInstantCreationOnlyFractionExact(0x0, 0);
+ assertInstantCreationOnlyFractionExact(0x80000000, 500_000_000L);
+ assertInstantCreationOnlyFractionExact(0x40000000, 250_000_000L);
+
+ // Test the limits of precision.
+ assertInstantCreationOnlyFractionExact(0x00000006, 1L);
+ assertInstantCreationOnlyFractionExact(0x00000005, 1L);
+ assertInstantCreationOnlyFractionExact(0x00000004, 0L);
+ assertInstantCreationOnlyFractionExact(0x00000002, 0L);
+ assertInstantCreationOnlyFractionExact(0x00000001, 0L);
+
+ // Confirm nanosecond storage / precision is within 1ns.
+ final boolean exhaustive = false;
+ for (int i = 0; i < NANOS_PER_SECOND; i++) {
+ Instant instant = Instant.ofEpochSecond(0, i);
+ Instant roundTripped = Timestamp64.fromInstant(instant).toInstant(0);
+ assertNanosWithTruncationAllowed(i, roundTripped);
+ if (!exhaustive) {
+ i += 999_999;
+ }
+ }
+ }
+
+ private static void assertInstantCreationOnlyFractionExact(
+ int fractionBits, long expectedNanos) {
+ Timestamp64 timestamp64 = Timestamp64.fromComponents(0, fractionBits);
+
+ final int ntpEra = 0;
+ Instant instant = timestamp64.toInstant(ntpEra);
+
+ assertEquals(expectedNanos, instant.getNano());
+ }
+
+ private static void assertNanosWithTruncationAllowed(long expectedNanos, Instant instant) {
+ // Allow for < 1ns difference due to truncation.
+ long actualNanos = instant.getNano();
+ assertTrue("expectedNanos=" + expectedNanos + ", actualNanos=" + actualNanos,
+ actualNanos == expectedNanos || actualNanos == expectedNanos - 1);
+ }
+
+ @Test
+ public void testMillisRandomizationConstant() {
+ // Mathematically, we can say that to represent 1000 different values, we need 10 binary
+ // digits (2^10 = 1024). The same is true whether we're dealing with integers or fractions.
+ // Unfortunately, for fractions those 1024 values do not correspond to discrete decimal
+ // values. Discrete millisecond values as fractions (e.g. 0.001 - 0.999) cannot be
+ // represented exactly except where the value can also be represented as some combination of
+ // powers of -2. When we convert back and forth, we truncate, so millisecond decimal
+ // fraction N represented as a binary fraction will always be equal to or lower than N. If
+ // we are truncating correctly it will never be as low as (N-0.001). N -> [N-0.001, N].
+
+ // We need to keep 10 bits to hold millis (inaccurately, since there are numbers that
+ // cannot be represented exactly), leaving us able to randomize the remaining 22 bits of the
+ // fraction part without significantly affecting the number represented.
+ assertEquals(22, Timestamp64.SUB_MILLIS_BITS_TO_RANDOMIZE);
+
+ // Brute force proof that randomization logic will keep the timestamp within the range
+ // [N-0.001, N] where x is in milliseconds.
+ int smallFractionRandomizedLow = 0;
+ int smallFractionRandomizedHigh = 0b00000000_00111111_11111111_11111111;
+ int largeFractionRandomizedLow = 0b11111111_11000000_00000000_00000000;
+ int largeFractionRandomizedHigh = 0b11111111_11111111_11111111_11111111;
+
+ long smallLowNanos = Timestamp64.fromComponents(
+ 0, smallFractionRandomizedLow).toInstant(0).getNano();
+ long smallHighNanos = Timestamp64.fromComponents(
+ 0, smallFractionRandomizedHigh).toInstant(0).getNano();
+ long smallDelta = smallHighNanos - smallLowNanos;
+ long millisInNanos = 1_000_000_000 / 1_000;
+ assertTrue(smallDelta >= 0 && smallDelta < millisInNanos);
+
+ long largeLowNanos = Timestamp64.fromComponents(
+ 0, largeFractionRandomizedLow).toInstant(0).getNano();
+ long largeHighNanos = Timestamp64.fromComponents(
+ 0, largeFractionRandomizedHigh).toInstant(0).getNano();
+ long largeDelta = largeHighNanos - largeLowNanos;
+ assertTrue(largeDelta >= 0 && largeDelta < millisInNanos);
+
+ PredictableRandom random = new PredictableRandom();
+ random.setIntSequence(new int[] { 0xFFFF_FFFF });
+ Timestamp64 zero = Timestamp64.fromComponents(0, 0);
+ Timestamp64 zeroWithFractionRandomized = zero.randomizeSubMillis(random);
+ assertEquals(zero.getEraSeconds(), zeroWithFractionRandomized.getEraSeconds());
+ assertEquals(smallFractionRandomizedHigh, zeroWithFractionRandomized.getFractionBits());
+ }
+
+ @Test
+ public void testRandomizeLowestBits() {
+ Random random = new Random(1);
+ {
+ int fractionBits = 0;
+ expectIllegalArgumentException(
+ () -> Timestamp64.randomizeLowestBits(random, fractionBits, -1));
+ expectIllegalArgumentException(
+ () -> Timestamp64.randomizeLowestBits(random, fractionBits, 0));
+ expectIllegalArgumentException(
+ () -> Timestamp64.randomizeLowestBits(random, fractionBits, Integer.SIZE));
+ expectIllegalArgumentException(
+ () -> Timestamp64.randomizeLowestBits(random, fractionBits, Integer.SIZE + 1));
+ }
+
+ // Check the behavior looks correct from a probabilistic point of view.
+ for (int input : new int[] { 0, 0xFFFFFFFF }) {
+ for (int bitCount = 1; bitCount < Integer.SIZE; bitCount++) {
+ int upperBitMask = 0xFFFFFFFF << bitCount;
+ int expectedUpperBits = input & upperBitMask;
+
+ Set<Integer> values = new HashSet<>();
+ values.add(input);
+
+ int trials = 100;
+ for (int i = 0; i < trials; i++) {
+ int outputFractionBits =
+ Timestamp64.randomizeLowestBits(random, input, bitCount);
+
+ // Record the output value for later analysis.
+ values.add(outputFractionBits);
+
+ // Check upper bits did not change.
+ assertEquals(expectedUpperBits, outputFractionBits & upperBitMask);
+ }
+
+ // It's possible to be more rigorous here, perhaps with a histogram. As bitCount
+ // rises, values.size() quickly trend towards the value of trials + 1. For now, this
+ // mostly just guards against a no-op implementation.
+ assertTrue(bitCount + ":" + values.size(), values.size() > 1);
+ }
+ }
+ }
+
+ private static void expectIllegalArgumentException(Runnable r) {
+ try {
+ r.run();
+ fail();
+ } catch (IllegalArgumentException e) {
+ // Expected
+ }
+ }
+}