Bug 895792 - Fix RoundUpPow2's required precondition to not be wrong. r=terrence
authorJeff Walden <jwalden@mit.edu>
Thu, 25 Jul 2013 20:01:45 -0700
changeset 152550 4a126050ecdbdfc3a7b4432783db8ac8373af002
parent 152549 b0b60f193dec254045cff510f5ad200a64471448
child 152551 1bb4b1eba285fd3074140b1af90b62e22502254f
push id2859
push userakeybl@mozilla.com
push dateMon, 16 Sep 2013 19:14:59 +0000
treeherdermozilla-beta@87d3c51cd2bf [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersterrence
bugs895792
milestone25.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 895792 - Fix RoundUpPow2's required precondition to not be wrong. r=terrence
mfbt/MathAlgorithms.h
mfbt/tests/TestCeilingFloor.cpp
--- a/mfbt/MathAlgorithms.h
+++ b/mfbt/MathAlgorithms.h
@@ -409,21 +409,22 @@ FloorLog2(const T t)
 /** A FloorLog2 variant that accepts only size_t. */
 inline uint_fast8_t
 FloorLog2Size(size_t n)
 {
   return FloorLog2(n);
 }
 
 /*
- * Round x up to the nearest power of 2.  This function assumes that the most
- * significant bit of x is not set, which would lead to overflow.
+ * Compute the smallest power of 2 greater than or equal to |x|.  |x| must not
+ * be so great that the computed value would overflow |size_t|.
  */
 inline size_t
 RoundUpPow2(size_t x)
 {
-  MOZ_ASSERT(~x > x, "can't round up -- will overflow!");
+  MOZ_ASSERT(x <= (size_t(1) << (sizeof(size_t) * CHAR_BIT - 1)),
+             "can't round up -- will overflow!");
   return size_t(1) << CeilingLog2(x);
 }
 
 } /* namespace mozilla */
 
 #endif /* mozilla_MathAlgorithms_h */
--- a/mfbt/tests/TestCeilingFloor.cpp
+++ b/mfbt/tests/TestCeilingFloor.cpp
@@ -2,16 +2,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this file,
  * You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "mozilla/MathAlgorithms.h"
 
 using mozilla::CeilingLog2;
 using mozilla::FloorLog2;
+using mozilla::RoundUpPow2;
 
 static void
 TestCeiling()
 {
   for (uint32_t i = 0; i <= 1; i++)
     MOZ_ASSERT(CeilingLog2(i) == 0);
 
   for (uint32_t i = 2; i <= 2; i++)
@@ -41,14 +42,44 @@ TestFloor()
 
   for (uint32_t i = 8; i <= 15; i++)
     MOZ_ASSERT(FloorLog2(i) == 3);
 
   for (uint32_t i = 16; i <= 31; i++)
     MOZ_ASSERT(FloorLog2(i) == 4);
 }
 
+static void
+TestRoundUpPow2()
+{
+  MOZ_ASSERT(RoundUpPow2(0) == 1);
+  MOZ_ASSERT(RoundUpPow2(1) == 1);
+  MOZ_ASSERT(RoundUpPow2(2) == 2);
+  MOZ_ASSERT(RoundUpPow2(3) == 4);
+  MOZ_ASSERT(RoundUpPow2(4) == 4);
+  MOZ_ASSERT(RoundUpPow2(5) == 8);
+  MOZ_ASSERT(RoundUpPow2(6) == 8);
+  MOZ_ASSERT(RoundUpPow2(7) == 8);
+  MOZ_ASSERT(RoundUpPow2(8) == 8);
+  MOZ_ASSERT(RoundUpPow2(9) == 16);
+
+  MOZ_ASSERT(RoundUpPow2(15) == 16);
+  MOZ_ASSERT(RoundUpPow2(16) == 16);
+  MOZ_ASSERT(RoundUpPow2(17) == 32);
+
+  MOZ_ASSERT(RoundUpPow2(31) == 32);
+  MOZ_ASSERT(RoundUpPow2(32) == 32);
+  MOZ_ASSERT(RoundUpPow2(33) == 64);
+
+  size_t MaxPow2 = size_t(1) << (sizeof(size_t) * CHAR_BIT - 1);
+  MOZ_ASSERT(RoundUpPow2(MaxPow2 - 1) == MaxPow2);
+  MOZ_ASSERT(RoundUpPow2(MaxPow2) == MaxPow2);
+  // not valid to round up when past the max power of two
+}
+
 int main()
 {
   TestCeiling();
   TestFloor();
+
+  TestRoundUpPow2();
   return 0;
 }