OLD | NEW |
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 Loading... |
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 |
OLD | NEW |