1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
// Copyright 2018 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "third_party/blink/renderer/core/timing/time_clamper.h"
#include "base/bit_cast.h"
#include "base/rand_util.h"
#include <cmath>
namespace blink {
namespace {
const int64_t kTenLowerDigitsMod = 10000000000;
} // namespace
TimeClamper::TimeClamper() : secret_(base::RandUint64()) {}
// This is using int64 for timestamps, because https://bit.ly/doubles-are-bad
base::TimeDelta TimeClamper::ClampTimeResolution(
base::TimeDelta time,
bool cross_origin_isolated_capability) const {
int64_t time_microseconds = time.InMicroseconds();
bool was_negative = false;
// If the input time is negative, turn it to a positive one and keep track of
// that.
if (time_microseconds < 0) {
was_negative = true;
time_microseconds =
-std::max(-std::numeric_limits<int64_t>::max(), time_microseconds);
}
// Split the time_microseconds to lower and upper digits to prevent uniformity
// distortion in large numbers. We will clamp the lower digits portion and
// later add on the upper digits portion.
int64_t time_lower_digits = time_microseconds % kTenLowerDigitsMod;
int64_t time_upper_digits = time_microseconds - time_lower_digits;
// Determine resolution based on the context's cross-origin isolation
// capability. https://w3c.github.io/hr-time/#dfn-coarsen-time
int resolution = cross_origin_isolated_capability
? kFineResolutionMicroseconds
: kCoarseResolutionMicroseconds;
// Clamped the time based on the resolution.
int64_t clamped_time = time_lower_digits - time_lower_digits % resolution;
// Determine if the clamped number should be clamped up, rather than down.
// The threshold to determine that is a random number smaller than resolution,
// such that the probability of clamped time being clamped up rather than
// down is proportional to its distance from the clamped_down time.
// As such it remains a double, in order to guarantee that distribution,
// and the clamping's uniformity.
double tick_threshold = ThresholdFor(clamped_time, resolution);
if (time_lower_digits >= tick_threshold)
clamped_time += resolution;
// Add back the upper digits portion while avoiding signed integer overflow.
time_upper_digits = std::min(
time_upper_digits, std::numeric_limits<int64_t>::max() - clamped_time);
clamped_time += time_upper_digits;
// Flip the number back to being negative if it started that way.
if (was_negative)
clamped_time = -clamped_time;
return base::Microseconds(clamped_time);
}
inline double TimeClamper::ThresholdFor(int64_t clamped_time,
int resolution) const {
uint64_t time_hash = MurmurHash3(clamped_time ^ secret_);
return clamped_time + resolution * ToDouble(time_hash);
}
// static
inline double TimeClamper::ToDouble(uint64_t value) {
// Exponent for double values for [1.0 .. 2.0]
static const uint64_t kExponentBits = uint64_t{0x3FF0000000000000};
static const uint64_t kMantissaMask = uint64_t{0x000FFFFFFFFFFFFF};
uint64_t random = (value & kMantissaMask) | kExponentBits;
return base::bit_cast<double>(random) - 1;
}
// static
inline uint64_t TimeClamper::MurmurHash3(uint64_t value) {
value ^= value >> 33;
value *= uint64_t{0xFF51AFD7ED558CCD};
value ^= value >> 33;
value *= uint64_t{0xC4CEB9FE1A85EC53};
value ^= value >> 33;
return value;
}
} // namespace blink
|
