| 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 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 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 |
| OLD | NEW |