Home | History | Annotate | Download | only in congestion_control 
      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
      3 // found in the LICENSE file.
      4 
      5 #include "net/quic/congestion_control/cube_root.h"
      6 
      7 #include "base/logging.h"
      8 
      9 namespace {
     10 
     11 // Find last bit in a 64-bit word.
     12 int FindMostSignificantBit(uint64 x) {
     13   if (!x) {
     14     return 0;
     15   }
     16   int r = 0;
     17   if (x & 0xffffffff00000000ull) {
     18     x >>= 32;
     19     r += 32;
     20   }
     21   if (x & 0xffff0000u) {
     22     x >>= 16;
     23     r += 16;
     24   }
     25   if (x & 0xff00u) {
     26     x >>= 8;
     27     r += 8;
     28   }
     29   if (x & 0xf0u) {
     30     x >>= 4;
     31     r += 4;
     32   }
     33   if (x & 0xcu) {
     34     x >>= 2;
     35     r += 2;
     36   }
     37   if (x & 0x02u) {
     38     x >>= 1;
     39     r++;
     40   }
     41   if (x & 0x01u) {
     42     r++;
     43   }
     44   return r;
     45 }
     46 
     47 // 6 bits table [0..63]
     48 const uint32 cube_root_table[] = {
     49     0,  54,  54,  54, 118, 118, 118, 118, 123, 129, 134, 138, 143, 147, 151,
     50   156, 157, 161, 164, 168, 170, 173, 176, 179, 181, 185, 187, 190, 192, 194,
     51   197, 199, 200, 202, 204, 206, 209, 211, 213, 215, 217, 219, 221, 222, 224,
     52   225, 227, 229, 231, 232, 234, 236, 237, 239, 240, 242, 244, 245, 246, 248,
     53   250, 251, 252, 254
     54 };
     55 }  // namespace
     56 
     57 namespace net {
     58 
     59 // Calculate the cube root using a table lookup followed by one Newton-Raphson
     60 // iteration.
     61 uint32 CubeRoot::Root(uint64 a) {
     62   uint32 msb = FindMostSignificantBit(a);
     63   DCHECK_LE(msb, 64u);
     64 
     65   if (msb < 7) {
     66     // MSB in our table.
     67     return ((cube_root_table[static_cast<uint32>(a)]) + 31) >> 6;
     68   }
     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, ...
     71   uint32 cubic_shift = (msb - 4);
     72   cubic_shift = ((cubic_shift * 342) >> 10);  // Div by 3, biased high.
     73 
     74   // 4 to 6 bits accuracy depending on MSB.
     75   uint32 down_shifted_to_6bit = (a >> (cubic_shift * 3));
     76   uint64 root = ((cube_root_table[down_shifted_to_6bit] + 10) << cubic_shift)
     77       >> 6;
     78 
     79   // Make one Newton-Raphson iteration.
     80   // 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.
     82   root = 2 * root + (a / (root * (root - 1)));
     83   root = ((root * 341) >> 10);  // Div by 3, biased low.
     84   return static_cast<uint32>(root);
     85 }
     86 
     87 }  // namespace net
     88