Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(454)

Side by Side Diff: net/quic/congestion_control/cube_root.cc

Issue 761903003: Update from https://crrev.com/306655 (Closed) Base URL: git@github.com:domokit/mojo.git@master
Patch Set: Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « net/proxy/proxy_resolver_v8_tracing.cc ('k') | net/quic/congestion_control/cubic.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. 1 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #include "net/quic/congestion_control/cube_root.h" 5 #include "net/quic/congestion_control/cube_root.h"
6 6
7 #include "base/logging.h" 7 #include "base/logging.h"
8 8
9 namespace { 9 namespace {
10 10
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after
57 namespace net { 57 namespace net {
58 58
59 // Calculate the cube root using a table lookup followed by one Newton-Raphson 59 // Calculate the cube root using a table lookup followed by one Newton-Raphson
60 // iteration. 60 // iteration.
61 uint32 CubeRoot::Root(uint64 a) { 61 uint32 CubeRoot::Root(uint64 a) {
62 uint32 msb = FindMostSignificantBit(a); 62 uint32 msb = FindMostSignificantBit(a);
63 DCHECK_LE(msb, 64u); 63 DCHECK_LE(msb, 64u);
64 64
65 if (msb < 7) { 65 if (msb < 7) {
66 // MSB in our table. 66 // MSB in our table.
67 return ((cube_root_table[static_cast<uint32>(a)]) + 31) >> 6; 67 return ((cube_root_table[a]) + 31) >> 6;
68 } 68 }
69 // MSB 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ... 69 // MSB 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
70 // cubic_shift 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ... 70 // cubic_shift 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ...
71 uint32 cubic_shift = (msb - 4); 71 uint32 cubic_shift = (msb - 4);
72 cubic_shift = ((cubic_shift * 342) >> 10); // Div by 3, biased high. 72 cubic_shift = ((cubic_shift * 342) >> 10); // Div by 3, biased high.
73 73
74 // 4 to 6 bits accuracy depending on MSB. 74 // 4 to 6 bits accuracy depending on MSB.
75 uint32 down_shifted_to_6bit = (a >> (cubic_shift * 3)); 75 uint64 root =
76 uint64 root = ((cube_root_table[down_shifted_to_6bit] + 10) << cubic_shift) 76 ((cube_root_table[a >> (cubic_shift * 3)] + 10) << cubic_shift) >> 6;
77 >> 6;
78 77
79 // Make one Newton-Raphson iteration. 78 // Make one Newton-Raphson iteration.
80 // Since x has an error (inaccuracy due to the use of fix point) we get a 79 // Since x has an error (inaccuracy due to the use of fix point) we get a
81 // more accurate result by doing x * (x - 1) instead of x * x. 80 // more accurate result by doing x * (x - 1) instead of x * x.
82 root = 2 * root + (a / (root * (root - 1))); 81 root = 2 * root + (a / (root * (root - 1)));
83 root = ((root * 341) >> 10); // Div by 3, biased low. 82 root = ((root * 341) >> 10); // Div by 3, biased low.
84 return static_cast<uint32>(root); 83 return static_cast<uint32>(root);
85 } 84 }
86 85
87 } // namespace net 86 } // namespace net
OLDNEW
« no previous file with comments | « net/proxy/proxy_resolver_v8_tracing.cc ('k') | net/quic/congestion_control/cubic.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698