Index: net/quic/congestion_control/cubic.cc |
diff --git a/net/quic/congestion_control/cubic.cc b/net/quic/congestion_control/cubic.cc |
index 3d03b9f60d1249af6a6c808e6ee6624ff2852a19..221209886cd98420d75e516a9c53e590d8c388a6 100644 |
--- a/net/quic/congestion_control/cubic.cc |
+++ b/net/quic/congestion_control/cubic.cc |
@@ -9,9 +9,14 @@ |
#include "base/basictypes.h" |
#include "base/logging.h" |
#include "base/time/time.h" |
+#include "net/quic/congestion_control/cube_root.h" |
+#include "net/quic/quic_protocol.h" |
+ |
+using std::max; |
namespace net { |
+namespace { |
// Constants based on TCP defaults. |
// The following constants are in 2^10 fractions of a second instead of ms to |
// allow a 10 shift right to divide. |
@@ -25,52 +30,6 @@ const uint32 kBetaSPDY = 939; // Back off factor after loss for SPDY, reduces |
// the CWND by 1/12th. |
const uint32 kBetaLastMax = 871; // Additional back off factor after loss for |
// the stored max value. |
- |
-namespace { |
-// Find last bit in a 64-bit word. |
-int FindMostSignificantBit(uint64 x) { |
- if (!x) { |
- return 0; |
- } |
- int r = 0; |
- if (x & 0xffffffff00000000ull) { |
- x >>= 32; |
- r += 32; |
- } |
- if (x & 0xffff0000u) { |
- x >>= 16; |
- r += 16; |
- } |
- if (x & 0xff00u) { |
- x >>= 8; |
- r += 8; |
- } |
- if (x & 0xf0u) { |
- x >>= 4; |
- r += 4; |
- } |
- if (x & 0xcu) { |
- x >>= 2; |
- r += 2; |
- } |
- if (x & 0x02u) { |
- x >>= 1; |
- r++; |
- } |
- if (x & 0x01u) { |
- r++; |
- } |
- return r; |
-} |
- |
-// 6 bits table [0..63] |
-const uint32 cube_root_table[] = { |
- 0, 54, 54, 54, 118, 118, 118, 118, 123, 129, 134, 138, 143, 147, 151, |
- 156, 157, 161, 164, 168, 170, 173, 176, 179, 181, 185, 187, 190, 192, 194, |
- 197, 199, 200, 202, 204, 206, 209, 211, 213, 215, 217, 219, 221, 222, 224, |
- 225, 227, 229, 231, 232, 234, 236, 237, 239, 240, 242, 244, 245, 246, 248, |
- 250, 251, 252, 254 |
-}; |
} // namespace |
Cubic::Cubic(const QuicClock* clock) |
@@ -80,34 +39,6 @@ Cubic::Cubic(const QuicClock* clock) |
Reset(); |
} |
-// Calculate the cube root using a table lookup followed by one Newton-Raphson |
-// iteration. |
-uint32 Cubic::CubeRoot(uint64 a) { |
- uint32 msb = FindMostSignificantBit(a); |
- DCHECK_LE(msb, 64u); |
- |
- if (msb < 7) { |
- // MSB in our table. |
- return ((cube_root_table[static_cast<uint32>(a)]) + 31) >> 6; |
- } |
- // MSB 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ... |
- // cubic_shift 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ... |
- uint32 cubic_shift = (msb - 4); |
- cubic_shift = ((cubic_shift * 342) >> 10); // Div by 3, biased high. |
- |
- // 4 to 6 bits accuracy depending on MSB. |
- uint32 down_shifted_to_6bit = (a >> (cubic_shift * 3)); |
- uint64 root = ((cube_root_table[down_shifted_to_6bit] + 10) << cubic_shift) |
- >> 6; |
- |
- // Make one Newton-Raphson iteration. |
- // Since x has an error (inaccuracy due to the use of fix point) we get a |
- // more accurate result by doing x * (x - 1) instead of x * x. |
- root = 2 * root + (a / (root * (root - 1))); |
- root = ((root * 341) >> 10); // Div by 3, biased low. |
- return static_cast<uint32>(root); |
-} |
- |
void Cubic::Reset() { |
epoch_ = QuicTime::Zero(); // Reset time. |
last_update_time_ = QuicTime::Zero(); // Reset time. |
@@ -143,8 +74,8 @@ QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck( |
// Cubic is "independent" of RTT, the update is limited by the time elapsed. |
if (last_congestion_window_ == current_congestion_window && |
(current_time.Subtract(last_update_time_) <= MaxCubicTimeInterval())) { |
- return std::max(last_target_congestion_window_, |
- estimated_tcp_congestion_window_); |
+ return max(last_target_congestion_window_, |
+ estimated_tcp_congestion_window_); |
} |
last_congestion_window_ = current_congestion_window; |
last_update_time_ = current_time; |
@@ -160,7 +91,7 @@ QuicTcpCongestionWindow Cubic::CongestionWindowAfterAck( |
time_to_origin_point_ = 0; |
origin_point_congestion_window_ = current_congestion_window; |
} else { |
- time_to_origin_point_ = CubeRoot(kCubeFactor * |
+ time_to_origin_point_ = CubeRoot::Root(kCubeFactor * |
(last_max_congestion_window_ - current_congestion_window)); |
origin_point_congestion_window_ = |
last_max_congestion_window_; |