1 /*
2  * Copyright (C) 2021 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package android.net.sntp;
17 
18 import android.text.TextUtils;
19 
20 import com.android.internal.annotations.VisibleForTesting;
21 
22 import java.time.Instant;
23 import java.util.Objects;
24 import java.util.Random;
25 
26 /**
27  * The 64-bit type ("timestamp") that NTP uses to represent a point in time. It only holds the
28  * lowest 32-bits of the number of seconds since 1900-01-01 00:00:00. Consequently, to turn an
29  * instance into an unambiguous point in time the era number must be known. Era zero runs from
30  * 1900-01-01 00:00:00 to a date in 2036.
31  *
32  * It stores sub-second values using a 32-bit fixed point type, so it can resolve values smaller
33  * than a nanosecond, but is imprecise (i.e. it truncates).
34  *
35  * See also <a href=https://www.eecis.udel.edu/~mills/y2k.html>NTP docs</a>.
36  *
37  * @hide
38  */
39 public final class Timestamp64 {
40 
41     public static final Timestamp64 ZERO = fromComponents(0, 0);
42     static final int SUB_MILLIS_BITS_TO_RANDOMIZE = 32 - 10;
43 
44     // Number of seconds between Jan 1, 1900 and Jan 1, 1970
45     // 70 years plus 17 leap days
46     static final long OFFSET_1900_TO_1970 = ((365L * 70L) + 17L) * 24L * 60L * 60L;
47     static final long MAX_SECONDS_IN_ERA = 0xFFFF_FFFFL;
48     static final long SECONDS_IN_ERA = MAX_SECONDS_IN_ERA + 1;
49 
50     static final int NANOS_PER_SECOND = 1_000_000_000;
51 
52     /** Creates a {@link Timestamp64} from the seconds and fraction components. */
fromComponents(long eraSeconds, int fractionBits)53     public static Timestamp64 fromComponents(long eraSeconds, int fractionBits) {
54         return new Timestamp64(eraSeconds, fractionBits);
55     }
56 
57     /** Creates a {@link Timestamp64} by decoding a string in the form "e4dc720c.4d4fc9eb". */
fromString(String string)58     public static Timestamp64 fromString(String string) {
59         final int requiredLength = 17;
60         if (string.length() != requiredLength || string.charAt(8) != '.') {
61             throw new IllegalArgumentException(string);
62         }
63         String eraSecondsString = string.substring(0, 8);
64         String fractionString = string.substring(9);
65         long eraSeconds = Long.parseLong(eraSecondsString, 16);
66 
67         // Use parseLong() because the type is unsigned. Integer.parseInt() will reject 0x70000000
68         // or above as being out of range.
69         long fractionBitsAsLong = Long.parseLong(fractionString, 16);
70         if (fractionBitsAsLong < 0 || fractionBitsAsLong > 0xFFFFFFFFL) {
71             throw new IllegalArgumentException("Invalid fractionBits:" + fractionString);
72         }
73         return new Timestamp64(eraSeconds, (int) fractionBitsAsLong);
74     }
75 
76     /**
77      * Converts an {@link Instant} into a {@link Timestamp64}. This is lossy: Timestamp64 only
78      * contains the number of seconds in a given era, but the era is not stored. Also, sub-second
79      * values are not stored precisely.
80      */
fromInstant(Instant instant)81     public static Timestamp64 fromInstant(Instant instant) {
82         long ntpEraSeconds = instant.getEpochSecond() + OFFSET_1900_TO_1970;
83         if (ntpEraSeconds < 0) {
84             ntpEraSeconds = SECONDS_IN_ERA - (-ntpEraSeconds % SECONDS_IN_ERA);
85         }
86         ntpEraSeconds %= SECONDS_IN_ERA;
87 
88         long nanos = instant.getNano();
89         int fractionBits = nanosToFractionBits(nanos);
90 
91         return new Timestamp64(ntpEraSeconds, fractionBits);
92     }
93 
94     private final long mEraSeconds;
95     private final int mFractionBits;
96 
Timestamp64(long eraSeconds, int fractionBits)97     private Timestamp64(long eraSeconds, int fractionBits) {
98         if (eraSeconds < 0 || eraSeconds > MAX_SECONDS_IN_ERA) {
99             throw new IllegalArgumentException(
100                     "Invalid parameters. seconds=" + eraSeconds + ", fraction=" + fractionBits);
101         }
102         this.mEraSeconds = eraSeconds;
103         this.mFractionBits = fractionBits;
104     }
105 
106     /** Returns the number of seconds in the NTP era. */
getEraSeconds()107     public long getEraSeconds() {
108         return mEraSeconds;
109     }
110 
111     /** Returns the fraction of a second as 32-bit, unsigned fixed-point bits. */
getFractionBits()112     public int getFractionBits() {
113         return mFractionBits;
114     }
115 
116     @Override
toString()117     public String toString() {
118         return TextUtils.formatSimple("%08x.%08x", mEraSeconds, mFractionBits);
119     }
120 
121     /** Returns the instant represented by this value in the specified NTP era. */
toInstant(int ntpEra)122     public Instant toInstant(int ntpEra) {
123         long secondsSinceEpoch = mEraSeconds - OFFSET_1900_TO_1970;
124         secondsSinceEpoch += ntpEra * SECONDS_IN_ERA;
125 
126         int nanos = fractionBitsToNanos(mFractionBits);
127         return Instant.ofEpochSecond(secondsSinceEpoch, nanos);
128     }
129 
130     @Override
equals(Object o)131     public boolean equals(Object o) {
132         if (this == o) {
133             return true;
134         }
135         if (o == null || getClass() != o.getClass()) {
136             return false;
137         }
138         Timestamp64 that = (Timestamp64) o;
139         return mEraSeconds == that.mEraSeconds && mFractionBits == that.mFractionBits;
140     }
141 
142     @Override
hashCode()143     public int hashCode() {
144         return Objects.hash(mEraSeconds, mFractionBits);
145     }
146 
fractionBitsToNanos(int fractionBits)147     static int fractionBitsToNanos(int fractionBits) {
148         long fractionBitsLong = fractionBits & 0xFFFF_FFFFL;
149         return (int) ((fractionBitsLong * NANOS_PER_SECOND) >>> 32);
150     }
151 
nanosToFractionBits(long nanos)152     static int nanosToFractionBits(long nanos) {
153         if (nanos > NANOS_PER_SECOND) {
154             throw new IllegalArgumentException();
155         }
156         return (int) ((nanos << 32) / NANOS_PER_SECOND);
157     }
158 
159     /**
160      * Randomizes the fraction bits that represent sub-millisecond values. i.e. the randomization
161      * won't change the number of milliseconds represented after truncation. This is used to
162      * implement the part of the NTP spec that calls for clients with millisecond accuracy clocks
163      * to send randomized LSB values rather than zeros.
164      */
randomizeSubMillis(Random random)165     public Timestamp64 randomizeSubMillis(Random random) {
166         int randomizedFractionBits =
167                 randomizeLowestBits(random, this.mFractionBits, SUB_MILLIS_BITS_TO_RANDOMIZE);
168         return new Timestamp64(mEraSeconds, randomizedFractionBits);
169     }
170 
171     /**
172      * Randomizes the specified number of LSBs in {@code value} by using replacement bits from
173      * {@code Random.getNextInt()}.
174      */
175     @VisibleForTesting
randomizeLowestBits(Random random, int value, int bitsToRandomize)176     public static int randomizeLowestBits(Random random, int value, int bitsToRandomize) {
177         if (bitsToRandomize < 1 || bitsToRandomize >= Integer.SIZE) {
178             // There's no point in randomizing all bits or none of the bits.
179             throw new IllegalArgumentException(Integer.toString(bitsToRandomize));
180         }
181 
182         int upperBitMask = 0xFFFF_FFFF << bitsToRandomize;
183         int lowerBitMask = ~upperBitMask;
184 
185         int randomValue = random.nextInt();
186         return (value & upperBitMask) | (randomValue & lowerBitMask);
187     }
188 }
189