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

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

Issue 266243004: Clang format slam. Base URL: svn://svn.chromium.org/chrome/trunk/src
Patch Set: Created 6 years, 7 months 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 | Annotate | Revision Log
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 28 matching lines...) Expand all
39 r++; 39 r++;
40 } 40 }
41 if (x & 0x01u) { 41 if (x & 0x01u) {
42 r++; 42 r++;
43 } 43 }
44 return r; 44 return r;
45 } 45 }
46 46
47 // 6 bits table [0..63] 47 // 6 bits table [0..63]
48 const uint32 cube_root_table[] = { 48 const uint32 cube_root_table[] = {
49 0, 54, 54, 54, 118, 118, 118, 118, 123, 129, 134, 138, 143, 147, 151, 49 0, 54, 54, 54, 118, 118, 118, 118, 123, 129, 134, 138, 143,
50 156, 157, 161, 164, 168, 170, 173, 176, 179, 181, 185, 187, 190, 192, 194, 50 147, 151, 156, 157, 161, 164, 168, 170, 173, 176, 179, 181, 185,
51 197, 199, 200, 202, 204, 206, 209, 211, 213, 215, 217, 219, 221, 222, 224, 51 187, 190, 192, 194, 197, 199, 200, 202, 204, 206, 209, 211, 213,
52 225, 227, 229, 231, 232, 234, 236, 237, 239, 240, 242, 244, 245, 246, 248, 52 215, 217, 219, 221, 222, 224, 225, 227, 229, 231, 232, 234, 236,
53 250, 251, 252, 254 53 237, 239, 240, 242, 244, 245, 246, 248, 250, 251, 252, 254};
54 };
55 } // namespace 54 } // namespace
56 55
57 namespace net { 56 namespace net {
58 57
59 // Calculate the cube root using a table lookup followed by one Newton-Raphson 58 // Calculate the cube root using a table lookup followed by one Newton-Raphson
60 // iteration. 59 // iteration.
61 uint32 CubeRoot::Root(uint64 a) { 60 uint32 CubeRoot::Root(uint64 a) {
62 uint32 msb = FindMostSignificantBit(a); 61 uint32 msb = FindMostSignificantBit(a);
63 DCHECK_LE(msb, 64u); 62 DCHECK_LE(msb, 64u);
64 63
65 if (msb < 7) { 64 if (msb < 7) {
66 // MSB in our table. 65 // MSB in our table.
67 return ((cube_root_table[static_cast<uint32>(a)]) + 31) >> 6; 66 return ((cube_root_table[static_cast<uint32>(a)]) + 31) >> 6;
68 } 67 }
69 // MSB 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ... 68 // MSB 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
70 // cubic_shift 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ... 69 // cubic_shift 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ...
71 uint32 cubic_shift = (msb - 4); 70 uint32 cubic_shift = (msb - 4);
72 cubic_shift = ((cubic_shift * 342) >> 10); // Div by 3, biased high. 71 cubic_shift = ((cubic_shift * 342) >> 10); // Div by 3, biased high.
73 72
74 // 4 to 6 bits accuracy depending on MSB. 73 // 4 to 6 bits accuracy depending on MSB.
75 uint32 down_shifted_to_6bit = (a >> (cubic_shift * 3)); 74 uint32 down_shifted_to_6bit = (a >> (cubic_shift * 3));
76 uint64 root = ((cube_root_table[down_shifted_to_6bit] + 10) << cubic_shift) 75 uint64 root =
77 >> 6; 76 ((cube_root_table[down_shifted_to_6bit] + 10) << cubic_shift) >> 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

Powered by Google App Engine
This is Rietveld 408576698