Bug 891177 - Move leading/trailing-zero-bit counting functions, ceiling/floor log2 functions, and round-up-pow2 functions into MathAlgorithms.h. r=terrence
authorJeff Walden <jwalden@mit.edu>
Wed, 03 Jul 2013 15:46:51 -0700
changeset 151273 021fd4e03439d25889ba2f2f6ef776c980149a9a
parent 151272 f713a828fe36a494aa38b90a8f1bc6d88fb4a771
child 151274 ab78d649fde6dd65dfe23aa85cb95788ae261bbf
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
bugs891177
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 891177 - Move leading/trailing-zero-bit counting functions, ceiling/floor log2 functions, and round-up-pow2 functions into MathAlgorithms.h. r=terrence
js/jsd/jshash.cpp
js/public/Utility.h
js/public/Vector.h
js/src/ds/LifoAlloc.cpp
js/src/ds/LifoAlloc.h
js/src/ion/AsmJSModule.h
js/src/ion/BitSet.h
js/src/ion/RangeAnalysis.cpp
js/src/ion/RangeAnalysis.h
js/src/ion/RegisterSets.h
js/src/ion/Safepoints.cpp
js/src/ion/arm/Assembler-arm.cpp
js/src/ion/arm/Assembler-arm.h
js/src/ion/arm/CodeGenerator-arm.cpp
js/src/ion/arm/Lowering-arm.cpp
js/src/ion/shared/CodeGenerator-x86-shared.cpp
js/src/ion/shared/Lowering-x86-shared.cpp
js/src/ion/shared/MacroAssembler-x86-shared.h
js/src/jsanalyze.cpp
js/src/jsarray.cpp
js/src/jsinferinlines.h
js/src/jsobj.cpp
js/src/jsutil.cpp
js/src/vm/ObjectImpl.h
js/src/vm/Shape.cpp
js/src/vm/String.cpp
mfbt/MathAlgorithms.h
mfbt/tests/Makefile.in
mfbt/tests/TestCeilingFloor.cpp
mfbt/tests/TestCountZeroes.cpp
--- a/js/jsd/jshash.cpp
+++ b/js/jsd/jshash.cpp
@@ -2,24 +2,30 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/. */
 
 /*
  * PR hash table package.
  */
+
+#include "jshash.h"
+
+#include "mozilla/MathAlgorithms.h"
+
 #include <stdlib.h>
 #include <string.h>
 #include "jstypes.h"
 #include "jsutil.h"
-#include "jshash.h"
 
 using namespace js;
 
+using mozilla::CeilingLog2Size;
+
 /* Compute the number of buckets in ht */
 #define NBUCKETS(ht)    JS_BIT(JS_HASH_BITS - (ht)->shift)
 
 /* The smallest table has 16 buckets */
 #define MINBUCKETSLOG2  4
 #define MINBUCKETS      JS_BIT(MINBUCKETSLOG2)
 
 /* Compute the maximum entries given n buckets that we will tolerate, ~90% */
@@ -67,17 +73,17 @@ JS_NewHashTable(uint32_t n, JSHashFuncti
                 JSHashAllocOps *allocOps, void *allocPriv)
 {
     JSHashTable *ht;
     size_t nb;
 
     if (n <= MINBUCKETS) {
         n = MINBUCKETSLOG2;
     } else {
-        n = JS_CEILING_LOG2W(n);
+        n = CeilingLog2Size(n);
         if (int32_t(n) < 0)
             return NULL;
     }
 
     if (!allocOps) allocOps = &defaultHashAllocOps;
 
     ht = (JSHashTable*) allocOps->allocTable(allocPriv, sizeof *ht);
     if (!ht)
@@ -347,17 +353,17 @@ JS_HashTableEnumerateEntries(JSHashTable
     }
 
 out:
     /* Shrink table if removal of entries made it underloaded */
     if (ht->nentries != nlimit) {
         JS_ASSERT(ht->nentries < nlimit);
         nbuckets = NBUCKETS(ht);
         if (MINBUCKETS < nbuckets && ht->nentries < UNDERLOADED(nbuckets)) {
-            newlog2 = JS_CEILING_LOG2W(ht->nentries);
+            newlog2 = CeilingLog2Size(ht->nentries);
             if (newlog2 < MINBUCKETSLOG2)
                 newlog2 = MINBUCKETSLOG2;
 
             /*  Check that we really shrink the table. */
             JS_ASSERT(JS_HASH_BITS - ht->shift > newlog2);
             Resize(ht, JS_HASH_BITS - newlog2);
         }
     }
--- a/js/public/Utility.h
+++ b/js/public/Utility.h
@@ -165,183 +165,16 @@ static JS_INLINE void* js_realloc(void* 
 }
 
 static JS_INLINE void js_free(void* p)
 {
     free(p);
 }
 #endif/* JS_USE_CUSTOM_ALLOCATOR */
 
-extern "C" {
-
-/*
- * Replace bit-scanning code sequences with CPU-specific instructions to
- * speedup calculations of ceiling/floor log2.
- *
- * With GCC 3.4 or later we can use __builtin_clz for that, see bug 327129.
- *
- * SWS: Added MSVC intrinsic bitscan support.  See bugs 349364 and 356856.
- */
-#if defined(_WIN32) && (_MSC_VER >= 1300) && (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
-
-unsigned char _BitScanForward(unsigned long * Index, unsigned long Mask);
-unsigned char _BitScanReverse(unsigned long * Index, unsigned long Mask);
-# pragma intrinsic(_BitScanForward,_BitScanReverse)
-
-__forceinline static int
-__BitScanForward32(unsigned int val)
-{
-    unsigned long idx;
-
-    _BitScanForward(&idx, (unsigned long)val);
-    return (int)idx;
-}
-__forceinline static int
-__BitScanReverse32(unsigned int val)
-{
-    unsigned long idx;
-
-    _BitScanReverse(&idx, (unsigned long)val);
-    return (int)(31-idx);
-}
-# define js_bitscan_ctz32(val)  __BitScanForward32(val)
-# define js_bitscan_clz32(val)  __BitScanReverse32(val)
-
-#if defined(_M_AMD64) || defined(_M_X64)
-unsigned char _BitScanForward64(unsigned long * Index, unsigned __int64 Mask);
-unsigned char _BitScanReverse64(unsigned long * Index, unsigned __int64 Mask);
-# pragma intrinsic(_BitScanForward64,_BitScanReverse64)
-#endif
-
-__forceinline static int
-__BitScanForward64(unsigned __int64 val)
-{
-#if defined(_M_AMD64) || defined(_M_X64)
-    unsigned long idx;
-
-    _BitScanForward64(&idx, val);
-    return (int)idx;
-#else
-    uint32_t lo = (uint32_t)val;
-    uint32_t hi = (uint32_t)(val >> 32);
-    return lo != 0 ?
-           js_bitscan_ctz32(lo) :
-           32 + js_bitscan_ctz32(hi);
-#endif
-}
-__forceinline static int
-__BitScanReverse64(unsigned __int64 val)
-{
-#if defined(_M_AMD64) || defined(_M_X64)
-    unsigned long idx;
-
-    _BitScanReverse64(&idx, val);
-    return (int)(63-idx);
-#else
-    uint32_t lo = (uint32_t)val;
-    uint32_t hi = (uint32_t)(val >> 32);
-    return hi != 0 ?
-           js_bitscan_clz32(hi) :
-           32 + js_bitscan_clz32(lo);
-#endif
-}
-# define js_bitscan_ctz64(val)  __BitScanForward64(val)
-# define js_bitscan_clz64(val)  __BitScanReverse64(val)
-#elif MOZ_IS_GCC
-
-#if MOZ_GCC_VERSION_AT_LEAST(3, 4, 0)
-# define USE_BUILTIN_CTZ
-#endif
-
-#elif defined(__clang__)
-
-#if __has_builtin(__builtin_ctz)
-# define USE_BUILTIN_CTZ
-#endif
-
-#endif
-
-#if defined(USE_BUILTIN_CTZ)
-
-JS_STATIC_ASSERT(sizeof(unsigned int) == sizeof(uint32_t));
-# define js_bitscan_ctz32(val)  __builtin_ctz(val)
-# define js_bitscan_clz32(val)  __builtin_clz(val)
-
-JS_STATIC_ASSERT(sizeof(unsigned long long) == sizeof(uint64_t));
-# define js_bitscan_ctz64(val)  __builtin_ctzll(val)
-# define js_bitscan_clz64(val)  __builtin_clzll(val)
-
-# undef USE_BUILTIN_CTZ
-
-#endif
-
-/*
-** Macro version of JS_CeilingLog2: Compute the log of the least power of
-** 2 greater than or equal to _n. The result is returned in _log2.
-*/
-/*
- * Use intrinsic function or count-leading-zeros to calculate ceil(log2(_n)).
- * The macro checks for "n <= 1" and not "n != 0" as js_bitscan_clz32(0) is
- * undefined.
- */
-# define JS_CEILING_LOG2(_log2,_n)                                            \
-    JS_BEGIN_MACRO                                                            \
-        unsigned int j_ = (unsigned int)(_n);                                 \
-        (_log2) = (j_ <= 1 ? 0 : 32 - js_bitscan_clz32(j_ - 1));              \
-    JS_END_MACRO
-
-/*
-** Macro version of JS_FloorLog2: Compute the log of the greatest power of
-** 2 less than or equal to _n. The result is returned in _log2.
-**
-** This is equivalent to finding the highest set bit in the word.
-*/
-/*
- * Use js_bitscan_clz32 or count-leading-zeros to calculate floor(log2(_n)).
- * Since js_bitscan_clz32(0) is undefined, the macro set the loweset bit to 1
- * to ensure 0 result when _n == 0.
- */
-# define JS_FLOOR_LOG2(_log2,_n)                                              \
-    JS_BEGIN_MACRO                                                            \
-        (_log2) = 31 - js_bitscan_clz32(((unsigned int)(_n)) | 1);            \
-    JS_END_MACRO
-
-#if JS_BYTES_PER_WORD == 4
-#  define js_FloorLog2wImpl(n)                                                \
-    ((size_t)(JS_BITS_PER_WORD - 1 - js_bitscan_clz32(n)))
-#elif JS_BYTES_PER_WORD == 8
-#  define js_FloorLog2wImpl(n)                                                \
-    ((size_t)(JS_BITS_PER_WORD - 1 - js_bitscan_clz64(n)))
-#else
-# error "NOT SUPPORTED"
-#endif
-
-} // extern "C"
-
-/*
- * Internal function.
- * Compute the log of the least power of 2 greater than or equal to n. This is
- * a version of JS_CeilingLog2 that operates on unsigned integers with
- * CPU-dependant size.
- */
-#define JS_CEILING_LOG2W(n) ((n) <= 1 ? 0 : 1 + JS_FLOOR_LOG2W((n) - 1))
-
-/*
- * Internal function.
- * Compute the log of the greatest power of 2 less than or equal to n.
- * This is a version of JS_FloorLog2 that operates on unsigned integers with
- * CPU-dependant size and requires that n != 0.
- */
-static MOZ_ALWAYS_INLINE size_t
-JS_FLOOR_LOG2W(size_t n)
-{
-    JS_ASSERT(n != 0);
-    return js_FloorLog2wImpl(n);
-}
-
 /*
  * JS_ROTATE_LEFT32
  *
  * There is no rotate operation in the C Language so the construct (a << 4) |
  * (a >> 28) is used instead. Most compilers convert this to a rotate
  * instruction but some versions of MSVC don't without a little help.  To get
  * MSVC to generate a rotate instruction, we have to use the _rotl intrinsic
  * and use a pragma to make _rotl inline.
@@ -559,26 +392,16 @@ struct ScopedReleasePtrTraits : public S
     static void release(T *ptr) { if (ptr) ptr->release(); }
 };
 SCOPED_TEMPLATE(ScopedReleasePtr, ScopedReleasePtrTraits)
 
 } /* namespace js */
 
 namespace js {
 
-/*
- * 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.
- */
-JS_ALWAYS_INLINE size_t
-RoundUpPow2(size_t x)
-{
-    return size_t(1) << JS_CEILING_LOG2W(x);
-}
-
 /* Integral types for all hash functions. */
 typedef uint32_t HashNumber;
 const unsigned HashNumberSizeBits = 32;
 
 namespace detail {
 
 /*
  * Given a raw hash code, h, return a number that can be used to select a hash
--- a/js/public/Vector.h
+++ b/js/public/Vector.h
@@ -4,16 +4,17 @@
  * 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/. */
 
 #ifndef js_Vector_h
 #define js_Vector_h
 
 #include "mozilla/Assertions.h"
 #include "mozilla/Attributes.h"
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Move.h"
 #include "mozilla/ReentrancyGuard.h"
 #include "mozilla/TypeTraits.h"
 
 #include "js/TemplateLib.h"
 #include "js/Utility.h"
 
@@ -37,17 +38,17 @@ class Vector;
  * allocated on the heap.  This means that cap*sizeof(T) is as close to a
  * power-of-two as possible.  growStorageBy() is responsible for ensuring
  * this.
  */
 template <typename T>
 static bool CapacityHasExcessSpace(size_t cap)
 {
     size_t size = cap * sizeof(T);
-    return RoundUpPow2(size) - size >= sizeof(T);
+    return mozilla::RoundUpPow2(size) - size >= sizeof(T);
 }
 
 /*
  * This template class provides a default implementation for vector operations
  * when the element type is not known to be a POD, as judged by IsPod.
  */
 template <class T, size_t N, class AP, bool IsPod>
 struct VectorImpl
@@ -689,17 +690,17 @@ Vector<T,N,AP>::growStorageBy(size_t inc
         if (newMinCap < mLength ||
             newMinCap & tl::MulOverflowMask<2 * sizeof(T)>::result)
         {
             this->reportAllocOverflow();
             return false;
         }
 
         size_t newMinSize = newMinCap * sizeof(T);
-        size_t newSize = RoundUpPow2(newMinSize);
+        size_t newSize = mozilla::RoundUpPow2(newMinSize);
         newCap = newSize / sizeof(T);
     }
 
     if (usingInlineStorage()) {
       convert:
         return convertToHeapStorage(newCap);
     }
 
--- a/js/src/ds/LifoAlloc.cpp
+++ b/js/src/ds/LifoAlloc.cpp
@@ -1,18 +1,22 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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 "ds/LifoAlloc.h"
 
+#include "mozilla/MathAlgorithms.h"
+
 using namespace js;
 
+using mozilla::RoundUpPow2;
+
 namespace js {
 namespace detail {
 
 BumpChunk *
 BumpChunk::new_(size_t chunkSize)
 {
     JS_ASSERT(RoundUpPow2(chunkSize) == chunkSize);
     void *mem = js_malloc(chunkSize);
--- a/js/src/ds/LifoAlloc.h
+++ b/js/src/ds/LifoAlloc.h
@@ -3,16 +3,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/. */
 
 #ifndef ds_LifoAlloc_h
 #define ds_LifoAlloc_h
 
 #include "mozilla/DebugOnly.h"
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/MemoryChecking.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/PodOperations.h"
 #include "mozilla/TypeTraits.h"
 
 // This data structure supports stacky LIFO allocation (mark/release and
 // LifoAllocScope). It does not maintain one contiguous segment; instead, it
 // maintains a bunch of linked memory segments. In order to prevent malloc/free
@@ -170,17 +171,17 @@ class LifoAlloc
     // Return a BumpChunk that can perform an allocation of at least size |n|
     // and add it to the chain appropriately.
     //
     // Side effect: if retval is non-null, |first| and |latest| are initialized
     // appropriately.
     BumpChunk *getOrCreateChunk(size_t n);
 
     void reset(size_t defaultChunkSize) {
-        JS_ASSERT(RoundUpPow2(defaultChunkSize) == defaultChunkSize);
+        JS_ASSERT(mozilla::RoundUpPow2(defaultChunkSize) == defaultChunkSize);
         first = latest = last = NULL;
         defaultChunkSize_ = defaultChunkSize;
         markCount = 0;
         curSize_ = 0;
     }
 
     void append(BumpChunk *start, BumpChunk *end) {
         JS_ASSERT(start && end);
--- a/js/src/ion/AsmJSModule.h
+++ b/js/src/ion/AsmJSModule.h
@@ -2,16 +2,18 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/. */
 
 #ifndef ion_AsmJSModule_h
 #define ion_AsmJSModule_h
 
+#include "mozilla/MathAlgorithms.h"
+
 #ifdef JS_ION
 
 #include "gc/Marking.h"
 #include "ion/RegisterSets.h"
 
 #include "jsscript.h"
 
 #if defined(JS_ION_PERF)
@@ -684,18 +686,17 @@ class AsmJSModule
             boundsChecks_[i].setOffset(masm.actualOffset(boundsChecks_[i].offset()));
     }
 
     void patchBoundsChecks(unsigned heapSize) {
         if (heapSize == 0)
             return;
 
         ion::AutoFlushCache afc("patchBoundsCheck");
-        uint32_t bits;
-        JS_CEILING_LOG2(bits, heapSize);
+        uint32_t bits = mozilla::CeilingLog2(heapSize);
 
         for (unsigned i = 0; i < boundsChecks_.length(); i++)
             ion::Assembler::updateBoundsCheck(bits, (ion::Instruction*)(boundsChecks_[i].offset() + code_));
 
     }
     unsigned numBoundsChecks() const {
         return boundsChecks_.length();
     }
--- a/js/src/ion/BitSet.h
+++ b/js/src/ion/BitSet.h
@@ -2,16 +2,18 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/. */
 
 #ifndef ion_BitSet_h
 #define ion_BitSet_h
 
+#include "mozilla/MathAlgorithms.h"
+
 #include "ion/IonAllocPolicy.h"
 
 namespace js {
 namespace ion {
 
 // Provides constant time set insertion and removal, and fast linear
 // set operations such as intersection, difference, and union.
 // N.B. All set operations must be performed on sets with the same maximum.
@@ -145,20 +147,19 @@ class BitSet::Iterator
             word_++;
             if (!more())
                 return *this;
 
             index_ = word_ * sizeof(value_) * 8;
             value_ = set_.bits_[word_];
         }
 
-        // The result of js_bitscan_ctz32 is undefined if the input is 0.
-        JS_ASSERT(value_ != 0);
-
-        int numZeros = js_bitscan_ctz32(value_);
+        // Be careful: the result of CountTrailingZeroes32 is undefined if the
+        // input is 0.
+        int numZeros = mozilla::CountTrailingZeroes32(value_);
         index_ += numZeros;
         value_ >>= numZeros;
 
         JS_ASSERT_IF(index_ <= set_.max_, set_.contains(index_));
         return *this;
     }
 
     unsigned int operator *() {
--- a/js/src/ion/RangeAnalysis.cpp
+++ b/js/src/ion/RangeAnalysis.cpp
@@ -19,16 +19,17 @@
 #include "ion/MIRGraph.h"
 #include "ion/RangeAnalysis.h"
 #include "ion/IonSpewer.h"
 
 using namespace js;
 using namespace js::ion;
 
 using mozilla::Abs;
+using mozilla::CountLeadingZeroes32;
 using mozilla::ExponentComponent;
 using mozilla::IsInfinite;
 using mozilla::IsNaN;
 using mozilla::IsNegative;
 using mozilla::Swap;
 
 // This algorithm is based on the paper "Eliminating Range Checks Using
 // Static Single Assignment Form" by Gough and Klaren.
@@ -461,57 +462,57 @@ Range::and_(const Range *lhs, const Rang
 
     return new Range(lower, upper);
 }
 
 Range *
 Range::or_(const Range *lhs, const Range *rhs)
 {
     // When one operand is always 0 or always -1, it's a special case where we
-    // can compute a fully precise result. Handling these up front also protects
-    // the code below from calling js_bitscan_clz32 with a zero operand or from
-    // shifting an int32_t by 32.
+    // can compute a fully precise result. Handling these up front also
+    // protects the code below from calling CountLeadingZeroes32 with a zero
+    // operand or from shifting an int32_t by 32.
     if (lhs->lower_ == lhs->upper_) {
         if (lhs->lower_ == 0)
             return new Range(*rhs);
         if (lhs->lower_ == -1)
             return new Range(*lhs);;
     }
     if (rhs->lower_ == rhs->upper_) {
         if (rhs->lower_ == 0)
             return new Range(*lhs);
         if (rhs->lower_ == -1)
             return new Range(*rhs);;
     }
 
-    // The code below uses js_bitscan_clz32, which has undefined behavior if its
-    // operand is 0. We rely on the code above to protect it.
+    // The code below uses CountLeadingZeroes32, which has undefined behavior
+    // if its operand is 0. We rely on the code above to protect it.
     JS_ASSERT_IF(lhs->lower_ >= 0, lhs->upper_ != 0);
     JS_ASSERT_IF(rhs->lower_ >= 0, rhs->upper_ != 0);
     JS_ASSERT_IF(lhs->upper_ < 0, lhs->lower_ != -1);
     JS_ASSERT_IF(rhs->upper_ < 0, rhs->lower_ != -1);
 
     int64_t lower = INT32_MIN;
     int64_t upper = INT32_MAX;
 
     if (lhs->lower_ >= 0 && rhs->lower_ >= 0) {
         // Both operands are non-negative, so the result won't be less than either.
         lower = Max(lhs->lower_, rhs->lower_);
         // The result will have leading zeros where both operands have leading zeros.
-        upper = UINT32_MAX >> Min(js_bitscan_clz32(lhs->upper_),
-                                  js_bitscan_clz32(rhs->upper_));
+        upper = UINT32_MAX >> Min(CountLeadingZeroes32(lhs->upper_),
+                                  CountLeadingZeroes32(rhs->upper_));
     } else {
         // The result will have leading ones where either operand has leading ones.
         if (lhs->upper_ < 0) {
-            unsigned leadingOnes = js_bitscan_clz32(~lhs->lower_);
+            unsigned leadingOnes = CountLeadingZeroes32(~lhs->lower_);
             lower = Max(lower, int64_t(~int32_t(UINT32_MAX >> leadingOnes)));
             upper = -1;
         }
         if (rhs->upper_ < 0) {
-            unsigned leadingOnes = js_bitscan_clz32(~rhs->lower_);
+            unsigned leadingOnes = CountLeadingZeroes32(~rhs->lower_);
             lower = Max(lower, int64_t(~int32_t(UINT32_MAX >> leadingOnes)));
             upper = -1;
         }
     }
 
     return new Range(lower, upper);
 }
 
@@ -538,35 +539,35 @@ Range::xor_(const Range *lhs, const Rang
         rhsLower = ~rhsLower;
         rhsUpper = ~rhsUpper;
         Swap(rhsLower, rhsUpper);
         invertAfter = !invertAfter;
     }
 
     // Handle cases where lhs or rhs is always zero specially, because they're
     // easy cases where we can be perfectly precise, and because it protects the
-    // js_bitscan_clz32 calls below from seeing 0 operands, which would be
+    // CountLeadingZeroes32 calls below from seeing 0 operands, which would be
     // undefined behavior.
     int32_t lower = INT32_MIN;
     int32_t upper = INT32_MAX;
     if (lhsLower == 0 && lhsUpper == 0) {
         upper = rhsUpper;
         lower = rhsLower;
     } else if (rhsLower == 0 && rhsUpper == 0) {
         upper = lhsUpper;
         lower = lhsLower;
     } else if (lhsLower >= 0 && rhsLower >= 0) {
         // Both operands are non-negative. The result will be non-negative.
         lower = 0;
         // To compute the upper value, take each operand's upper value and
         // set all bits that don't correspond to leading zero bits in the
         // other to one. For each one, this gives an upper bound for the
         // result, so we can take the minimum between the two.
-        unsigned lhsLeadingZeros = js_bitscan_clz32(lhsUpper);
-        unsigned rhsLeadingZeros = js_bitscan_clz32(rhsUpper);
+        unsigned lhsLeadingZeros = CountLeadingZeroes32(lhsUpper);
+        unsigned rhsLeadingZeros = CountLeadingZeroes32(rhsUpper);
         upper = Min(rhsUpper | int32_t(UINT32_MAX >> lhsLeadingZeros),
                     lhsUpper | int32_t(UINT32_MAX >> rhsLeadingZeros));
     }
 
     // If we bitwise-negated one (but not both) of the operands above, apply the
     // bitwise-negate to the result, completing ~((~x)^y) == x^y.
     if (invertAfter) {
         lower = ~lower;
--- a/js/src/ion/RangeAnalysis.h
+++ b/js/src/ion/RangeAnalysis.h
@@ -358,17 +358,17 @@ class Range : public TempObject {
             JS_ASSERT(max_exponent_ >= MaxInt32Exponent);
             return;
         }
 
         uint32_t max = Max(mozilla::Abs<int64_t>(lower()), mozilla::Abs<int64_t>(upper()));
         JS_ASSERT_IF(lower() == JSVAL_INT_MIN, max == (uint32_t) JSVAL_INT_MIN);
         JS_ASSERT(max <= (uint32_t) JSVAL_INT_MIN);
         // The number of bits needed to encode |max| is the power of 2 plus one.
-        max_exponent_ = max ? js_FloorLog2wImpl(max) : max;
+        max_exponent_ = max ? mozilla::FloorLog2Size(max) : max;
     }
 
     const SymbolicBound *symbolicLower() const {
         return symbolicLower_;
     }
     const SymbolicBound *symbolicUpper() const {
         return symbolicUpper_;
     }
--- a/js/src/ion/RegisterSets.h
+++ b/js/src/ion/RegisterSets.h
@@ -2,16 +2,18 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/. */
 
 #ifndef ion_RegisterSets_h
 #define ion_RegisterSets_h
 
+#include "mozilla/MathAlgorithms.h"
+
 #include "ion/Registers.h"
 #include "ion/IonAllocPolicy.h"
 
 namespace js {
 namespace ion {
 
 struct AnyRegister {
     typedef uint32_t Code;
@@ -384,28 +386,25 @@ class TypedRegisterSet
 #elif defined(JS_PUNBOX64)
         takeUnchecked(value.valueReg());
 #else
 #error "Bad architecture"
 #endif
     }
     T getAny() const {
         JS_ASSERT(!empty());
-        int ireg;
-        JS_FLOOR_LOG2(ireg, bits_);
-        return T::FromCode(ireg);
+        return T::FromCode(mozilla::FloorLog2(bits_));
     }
     T getFirst() const {
         JS_ASSERT(!empty());
-        int ireg = js_bitscan_ctz32(bits_);
-        return T::FromCode(ireg);
+        return T::FromCode(mozilla::CountTrailingZeroes32(bits_));
     }
     T getLast() const {
         JS_ASSERT(!empty());
-        int ireg = 31 - js_bitscan_clz32(bits_);
+        int ireg = 31 - mozilla::CountLeadingZeroes32(bits_);
         return T::FromCode(ireg);
     }
     T takeAny() {
         JS_ASSERT(!empty());
         T reg = getAny();
         take(reg);
         return reg;
     }
--- a/js/src/ion/Safepoints.cpp
+++ b/js/src/ion/Safepoints.cpp
@@ -1,21 +1,26 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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 "ion/Safepoints.h"
+
+#include "mozilla/MathAlgorithms.h"
+
 #include "ion/IonSpewer.h"
 #include "ion/LIR.h"
 
 using namespace js;
 using namespace ion;
 
+using mozilla::FloorLog2;
+
 bool
 SafepointWriter::init(uint32_t slotCount)
 {
     frameSlots_ = BitSet::New(slotCount);
     if (!frameSlots_)
         return false;
 
     return true;
@@ -376,18 +381,17 @@ SafepointReader::getSlotFromBitmap(uint3
             return false;
 
         // Yes, read the next chunk.
         currentSlotChunk_ = stream_.readUnsigned();
     }
 
     // The current chunk still has bits in it, so get the next bit, then mask
     // it out of the slot chunk.
-    uint32_t bit;
-    JS_FLOOR_LOG2(bit, currentSlotChunk_);
+    uint32_t bit = FloorLog2(currentSlotChunk_);
     currentSlotChunk_ &= ~(1 << bit);
 
     // Return the slot, taking care to add 1 back in since it was subtracted
     // when added in the original bitset.
     *slot = (currentSlotChunkNumber_ * sizeof(uint32_t) * 8) + bit + 1;
     return true;
 }
 
--- a/js/src/ion/arm/Assembler-arm.cpp
+++ b/js/src/ion/arm/Assembler-arm.cpp
@@ -1,27 +1,30 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/DebugOnly.h"
+#include "mozilla/MathAlgorithms.h"
 
 #include "ion/arm/Assembler-arm.h"
 #include "ion/arm/MacroAssembler-arm.h"
 #include "gc/Marking.h"
 #include "jsutil.h"
 #include "assembler/jit/ExecutableAllocator.h"
 #include "jscompartment.h"
 #include "ion/IonCompartment.h"
 
 using namespace js;
 using namespace js::ion;
 
+using mozilla::CountLeadingZeroes32;
+
 ABIArgGenerator::ABIArgGenerator() :
 #if defined(JS_CPU_ARM_HARDFP)
     intRegIndex_(0),
     floatRegIndex_(0),
 #else
     argRegIndex_(0),
 #endif
     stackOffset_(0),
@@ -931,26 +934,26 @@ Imm8::encodeTwoImms(uint32_t imm)
     // since this is being done with rotates, we also need to handle the case
     // that one of these numbers is in fact split between the left and right
     // sides, in which case the constant will look like:
     // 0bn_1a((00)*)n_2((00)*)n_1b
     //   n1a  mid  n2   rgh    n1b
     // also remember, values are rotated by multiples of two, and left,
     // mid or right can have length zero
     uint32_t imm1, imm2;
-    int left = (js_bitscan_clz32(imm)) & 0x1E;
+    int left = CountLeadingZeroes32(imm) & 0x1E;
     uint32_t no_n1 = imm & ~(0xff << (24 - left));
 
     // not technically needed: this case only happens if we can encode
     // as a single imm8m.  There is a perfectly reasonable encoding in this
     // case, but we shouldn't encourage people to do things like this.
     if (no_n1 == 0)
         return TwoImm8mData();
 
-    int mid = ((js_bitscan_clz32(no_n1)) & 0x1E);
+    int mid = CountLeadingZeroes32(no_n1) & 0x1E;
     uint32_t no_n2 = no_n1 & ~((0xff << ((24 - mid) & 0x1f)) | 0xff >> ((8 + mid) & 0x1f));
 
     if (no_n2 == 0) {
         // we hit the easy case, no wraparound.
         // note: a single constant *may* look like this.
         int imm1shift = left + 8;
         int imm2shift = mid + 8;
         imm1 = (imm >> (32 - imm1shift)) & 0xff;
@@ -971,32 +974,32 @@ Imm8::encodeTwoImms(uint32_t imm)
                             datastore::Imm8mData(imm2, imm2shift >> 1));
     }
 
     // either it wraps, or it does not fit.
     // if we initially chopped off more than 8 bits, then it won't fit.
     if (left >= 8)
         return TwoImm8mData();
 
-    int right = 32 - (js_bitscan_clz32(no_n2) & 30);
+    int right = 32 - (CountLeadingZeroes32(no_n2) & 30);
     // all remaining set bits *must* fit into the lower 8 bits
     // the right == 8 case should be handled by the previous case.
     if (right > 8)
         return TwoImm8mData();
 
     // make sure the initial bits that we removed for no_n1
     // fit into the 8-(32-right) leftmost bits
     if (((imm & (0xff << (24 - left))) << (8-right)) != 0) {
         // BUT we may have removed more bits than we needed to for no_n1
         // 0x04104001 e.g. we can encode 0x104 with a single op, then
         // 0x04000001 with a second, but we try to encode 0x0410000
         // and find that we need a second op for 0x4000, and 0x1 cannot
         // be included in the encoding of 0x04100000
         no_n1 = imm & ~((0xff >> (8-right)) | (0xff << (24 + right)));
-        mid = (js_bitscan_clz32(no_n1)) & 30;
+        mid = CountLeadingZeroes32(no_n1) & 30;
         no_n2 =
             no_n1  & ~((0xff << ((24 - mid)&31)) | 0xff >> ((8 + mid)&31));
         if (no_n2 != 0)
             return TwoImm8mData();
     }
 
     // now assemble all of this information into a two coherent constants
     // it is a rotate right from the lower 8 bits.
--- a/js/src/ion/arm/Assembler-arm.h
+++ b/js/src/ion/arm/Assembler-arm.h
@@ -632,34 +632,34 @@ class Operand2
         return oper;
     }
 };
 
 class Imm8 : public Operand2
 {
   public:
     static datastore::Imm8mData encodeImm(uint32_t imm) {
-        // In gcc, clz is undefined if you call it with 0.
+        // mozilla::CountLeadingZeroes32(imm) requires imm != 0.
         if (imm == 0)
             return datastore::Imm8mData(0, 0);
-        int left = js_bitscan_clz32(imm) & 30;
+        int left = mozilla::CountLeadingZeroes32(imm) & 30;
         // See if imm is a simple value that can be encoded with a rotate of 0.
         // This is effectively imm <= 0xff, but I assume this can be optimized
         // more
         if (left >= 24)
             return datastore::Imm8mData(imm, 0);
 
         // Mask out the 8 bits following the first bit that we found, see if we
         // have 0 yet.
         int no_imm = imm & ~(0xff << (24 - left));
         if (no_imm == 0) {
             return  datastore::Imm8mData(imm >> (24 - left), ((8+left) >> 1));
         }
         // Look for the most signifigant bit set, once again.
-        int right = 32 - (js_bitscan_clz32(no_imm)  & 30);
+        int right = 32 - (mozilla::CountLeadingZeroes32(no_imm) & 30);
         // If it is in the bottom 8 bits, there is a chance that this is a
         // wraparound case.
         if (right >= 8)
             return datastore::Imm8mData();
         // Rather than masking out bits and checking for 0, just rotate the
         // immediate that we were passed in, and see if it fits into 8 bits.
         unsigned int mask = imm << (8 - right) | imm >> (24 + right);
         if (mask <= 0xff)
--- a/js/src/ion/arm/CodeGenerator-arm.cpp
+++ b/js/src/ion/arm/CodeGenerator-arm.cpp
@@ -1,14 +1,15 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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"
 
 #include "jscntxt.h"
 #include "jscompartment.h"
 #include "jsnum.h"
 
 #include "ion/arm/CodeGenerator-arm.h"
 #include "ion/PerfSpewer.h"
 #include "ion/CodeGenerator.h"
@@ -21,16 +22,18 @@
 
 #include "jsscriptinlines.h"
 
 #include "vm/Shape-inl.h"
 
 using namespace js;
 using namespace js::ion;
 
+using mozilla::FloorLog2;
+
 // shared
 CodeGeneratorARM::CodeGeneratorARM(MIRGenerator *gen, LIRGraph *graph, MacroAssembler *masm)
   : CodeGeneratorShared(gen, graph, masm)
 {
 }
 
 bool
 CodeGeneratorARM::generatePrologue()
@@ -401,41 +404,38 @@ CodeGeneratorARM::visitMulI(LMulI *ins)
             masm.ma_add(ToRegister(lhs), ToRegister(lhs), ToRegister(dest), SetCond);
             // Overflow is handled later.
             break;
           default: {
             bool handled = false;
             if (!mul->canOverflow()) {
                 // If it cannot overflow, we can do lots of optimizations
                 Register src = ToRegister(lhs);
-                uint32_t shift;
-                JS_FLOOR_LOG2(shift, constant);
+                uint32_t shift = FloorLog2(constant);
                 uint32_t rest = constant - (1 << shift);
                 // See if the constant has one bit set, meaning it can be encoded as a bitshift
                 if ((1 << shift) == constant) {
                     masm.ma_lsl(Imm32(shift), src, ToRegister(dest));
                     handled = true;
                 } else {
                     // If the constant cannot be encoded as (1<<C1), see if it can be encoded as
                     // (1<<C1) | (1<<C2), which can be computed using an add and a shift
-                    uint32_t shift_rest;
-                    JS_FLOOR_LOG2(shift_rest, rest);
+                    uint32_t shift_rest = FloorLog2(rest);
                     if ((1u << shift_rest) == rest) {
                         masm.as_add(ToRegister(dest), src, lsl(src, shift-shift_rest));
                         if (shift_rest != 0)
                             masm.ma_lsl(Imm32(shift_rest), ToRegister(dest), ToRegister(dest));
                         handled = true;
                     }
                 }
             } else if (ToRegister(lhs) != ToRegister(dest)) {
                 // To stay on the safe side, only optimize things that are a
                 // power of 2.
 
-                uint32_t shift;
-                JS_FLOOR_LOG2(shift, constant);
+                uint32_t shift = FloorLog2(constant);
                 if ((1 << shift) == constant) {
                     // dest = lhs * pow(2,shift)
                     masm.ma_lsl(Imm32(shift), ToRegister(lhs), ToRegister(dest));
                     // At runtime, check (lhs == dest >> shift), if this does not hold,
                     // some bits were lost due to overflow, and the computation should
                     // be resumed as a double.
                     masm.as_cmp(ToRegister(lhs), asr(ToRegister(dest), shift));
                     c = Assembler::NotEqual;
--- a/js/src/ion/arm/Lowering-arm.cpp
+++ b/js/src/ion/arm/Lowering-arm.cpp
@@ -1,22 +1,26 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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"
+
 #include "ion/MIR.h"
 #include "ion/Lowering.h"
 #include "ion/arm/Assembler-arm.h"
 #include "ion/shared/Lowering-shared-inl.h"
 
 using namespace js;
 using namespace js::ion;
 
+using mozilla::FloorLog2;
+
 bool
 LIRGeneratorARM::useBox(LInstruction *lir, size_t n, MDefinition *mir,
                         LUse::Policy policy, bool useAtStart)
 {
     JS_ASSERT(mir->type() == MIRType_Value);
     if (!ensureDefined(mir))
         return false;
     lir->setOperand(n, LUse(mir->virtualRegister(), policy, useAtStart));
@@ -235,18 +239,17 @@ LIRGeneratorARM::lowerDivI(MDiv *div)
     // rewritten to use other instructions.
     if (div->rhs()->isConstant()) {
         int32_t rhs = div->rhs()->toConstant()->value().toInt32();
         // Check for division by a positive power of two, which is an easy and
         // important case to optimize. Note that other optimizations are also
         // possible; division by negative powers of two can be optimized in a
         // similar manner as positive powers of two, and division by other
         // constants can be optimized by a reciprocal multiplication technique.
-        int32_t shift;
-        JS_FLOOR_LOG2(shift, rhs);
+        int32_t shift = FloorLog2(rhs);
         if (rhs > 0 && 1 << shift == rhs) {
             LDivPowTwoI *lir = new LDivPowTwoI(useRegisterAtStart(div->lhs()), shift);
             if (div->fallible() && !assignSnapshot(lir))
                 return false;
             return define(lir, div);
         }
     }
 
@@ -276,18 +279,17 @@ LIRGeneratorARM::lowerMulI(MMul *mul, MD
 bool
 LIRGeneratorARM::lowerModI(MMod *mod)
 {
     if (mod->isUnsigned())
         return lowerUMod(mod);
 
     if (mod->rhs()->isConstant()) {
         int32_t rhs = mod->rhs()->toConstant()->value().toInt32();
-        int32_t shift;
-        JS_FLOOR_LOG2(shift, rhs);
+        int32_t shift = FloorLog2(rhs);
         if (rhs > 0 && 1 << shift == rhs) {
             LModPowTwoI *lir = new LModPowTwoI(useRegister(mod->lhs()), shift);
             if (mod->fallible() && !assignSnapshot(lir))
                 return false;
             return define(lir, mod);
         } else if (shift < 31 && (1 << (shift+1)) - 1 == rhs) {
             LModMaskI *lir = new LModMaskI(useRegister(mod->lhs()), temp(LDefinition::GENERAL), shift+1);
             if (mod->fallible() && !assignSnapshot(lir))
--- a/js/src/ion/shared/CodeGenerator-x86-shared.cpp
+++ b/js/src/ion/shared/CodeGenerator-x86-shared.cpp
@@ -1,28 +1,31 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/DebugOnly.h"
+#include "mozilla/MathAlgorithms.h"
 
 #include "jscntxt.h"
 #include "jscompartment.h"
 #include "jsmath.h"
 #include "ion/shared/CodeGenerator-x86-shared.h"
 #include "ion/shared/CodeGenerator-shared-inl.h"
 #include "ion/IonFrames.h"
 #include "ion/IonCompartment.h"
 #include "ion/ParallelFunctions.h"
 
 using namespace js;
 using namespace js::ion;
 
+using mozilla::FloorLog2;
+
 namespace js {
 namespace ion {
 
 CodeGeneratorX86Shared::CodeGeneratorX86Shared(MIRGenerator *gen, LIRGraph *graph, MacroAssembler *masm)
   : CodeGeneratorShared(gen, graph, masm)
 {
 }
 
@@ -591,18 +594,17 @@ CodeGeneratorX86Shared::visitMulI(LMulI 
             // nop
             return true; // escape overflow check;
           case 2:
             masm.addl(ToOperand(lhs), ToRegister(lhs));
             break;
           default:
             if (!mul->canOverflow() && constant > 0) {
                 // Use shift if cannot overflow and constant is power of 2
-                int32_t shift;
-                JS_FLOOR_LOG2(shift, constant);
+                int32_t shift = FloorLog2(constant);
                 if ((1 << shift) == constant) {
                     masm.shll(Imm32(shift), ToRegister(lhs));
                     return true;
                 }
             }
             masm.imull(Imm32(ToInt32(rhs)), ToRegister(lhs));
         }
 
--- a/js/src/ion/shared/Lowering-x86-shared.cpp
+++ b/js/src/ion/shared/Lowering-x86-shared.cpp
@@ -1,21 +1,26 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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"
+
 #include "ion/MIR.h"
 #include "ion/Lowering.h"
 #include "ion/shared/Lowering-x86-shared.h"
 #include "ion/shared/Lowering-shared-inl.h"
+
 using namespace js;
 using namespace js::ion;
 
+using mozilla::FloorLog2;
+
 LTableSwitch *
 LIRGeneratorX86Shared::newLTableSwitch(const LAllocation &in, const LDefinition &inputCopy,
                                        MTableSwitch *tableswitch)
 {
     return new LTableSwitch(in, inputCopy, temp(), tableswitch);
 }
 
 LTableSwitchV *
@@ -133,18 +138,17 @@ LIRGeneratorX86Shared::lowerDivI(MDiv *d
     if (div->rhs()->isConstant()) {
         int32_t rhs = div->rhs()->toConstant()->value().toInt32();
 
         // Check for division by a positive power of two, which is an easy and
         // important case to optimize. Note that other optimizations are also
         // possible; division by negative powers of two can be optimized in a
         // similar manner as positive powers of two, and division by other
         // constants can be optimized by a reciprocal multiplication technique.
-        int32_t shift;
-        JS_FLOOR_LOG2(shift, rhs);
+        int32_t shift = FloorLog2(rhs);
         if (rhs > 0 && 1 << shift == rhs) {
             LDivPowTwoI *lir = new LDivPowTwoI(useRegisterAtStart(div->lhs()), useRegister(div->lhs()), shift);
             if (div->fallible() && !assignSnapshot(lir))
                 return false;
             return defineReuseInput(lir, div, 0);
         }
     }
 
@@ -157,18 +161,17 @@ LIRGeneratorX86Shared::lowerDivI(MDiv *d
 bool
 LIRGeneratorX86Shared::lowerModI(MMod *mod)
 {
     if (mod->isUnsigned())
         return lowerUMod(mod);
 
     if (mod->rhs()->isConstant()) {
         int32_t rhs = mod->rhs()->toConstant()->value().toInt32();
-        int32_t shift;
-        JS_FLOOR_LOG2(shift, rhs);
+        int32_t shift = FloorLog2(rhs);
         if (rhs > 0 && 1 << shift == rhs) {
             LModPowTwoI *lir = new LModPowTwoI(useRegisterAtStart(mod->lhs()), shift);
             if (mod->fallible() && !assignSnapshot(lir))
                 return false;
             return defineReuseInput(lir, mod, 0);
         }
     }
     LModI *lir = new LModI(useRegister(mod->lhs()), useRegister(mod->rhs()), tempFixed(eax));
--- a/js/src/ion/shared/MacroAssembler-x86-shared.h
+++ b/js/src/ion/shared/MacroAssembler-x86-shared.h
@@ -2,16 +2,17 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/. */
 
 #ifndef ion_shared_MacroAssembler_x86_shared_h
 #define ion_shared_MacroAssembler_x86_shared_h
 
+#include "mozilla/Casting.h"
 #include "mozilla/DebugOnly.h"
 
 #ifdef JS_CPU_X86
 # include "ion/x86/Assembler-x86.h"
 #elif JS_CPU_X64
 # include "ion/x64/Assembler-x64.h"
 #endif
 #include "ion/IonFrames.h"
--- a/js/src/jsanalyze.cpp
+++ b/js/src/jsanalyze.cpp
@@ -2,31 +2,33 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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 "jsanalyze.h"
 
 #include "mozilla/DebugOnly.h"
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/PodOperations.h"
 
 #include "jscompartment.h"
 #include "jscntxt.h"
 
 #include "jsanalyzeinlines.h"
 #include "jsinferinlines.h"
 #include "jsopcodeinlines.h"
 
 using namespace js;
 using namespace js::analyze;
 
 using mozilla::DebugOnly;
 using mozilla::PodCopy;
 using mozilla::PodZero;
+using mozilla::FloorLog2;
 
 /////////////////////////////////////////////////////////////////////
 // Bytecode
 /////////////////////////////////////////////////////////////////////
 
 #ifdef DEBUG
 void
 analyze::PrintBytecode(JSContext *cx, HandleScript script, jsbytecode *pc)
@@ -1468,19 +1470,17 @@ ScriptAnalysis::analyzeSSA(JSContext *cx
 
 /* Get a phi node's capacity for a given length. */
 static inline unsigned
 PhiNodeCapacity(unsigned length)
 {
     if (length <= 4)
         return 4;
 
-    unsigned log2;
-    JS_FLOOR_LOG2(log2, length - 1);
-    return 1 << (log2 + 1);
+    return 1 << (FloorLog2(length - 1) + 1);
 }
 
 bool
 ScriptAnalysis::makePhi(JSContext *cx, uint32_t slot, uint32_t offset, SSAValue *pv)
 {
     SSAPhiNode *node = cx->analysisLifoAlloc().new_<SSAPhiNode>();
     SSAValue *options = cx->analysisLifoAlloc().newArray<SSAValue>(PhiNodeCapacity(0));
     if (!node || !options) {
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -38,16 +38,17 @@
 #include "vm/Runtime-inl.h"
 
 using namespace js;
 using namespace js::gc;
 using namespace js::types;
 
 using mozilla::Abs;
 using mozilla::ArrayLength;
+using mozilla::CeilingLog2;
 using mozilla::DebugOnly;
 using mozilla::IsNaN;
 using mozilla::PointerRangeSize;
 
 JSBool
 js::GetLengthProperty(JSContext *cx, HandleObject obj, uint32_t *lengthp)
 {
     if (obj->is<ArrayObject>()) {
@@ -1296,19 +1297,18 @@ static uint64_t const powersOf10[] = {
 static inline unsigned
 NumDigitsBase10(uint32_t n)
 {
     /*
      * This is just floor_log10(n) + 1
      * Algorithm taken from
      * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
      */
-    uint32_t log2, t;
-    JS_CEILING_LOG2(log2, n);
-    t = log2 * 1233 >> 12;
+    uint32_t log2 = CeilingLog2(n);
+    uint32_t t = log2 * 1233 >> 12;
     return t - (n < powersOf10[t]) + 1;
 }
 
 inline bool
 CompareLexicographicInt32(JSContext *cx, const Value &a, const Value &b, bool *lessOrEqualp)
 {
     int32_t aint = a.toInt32();
     int32_t bint = b.toInt32();
--- a/js/src/jsinferinlines.h
+++ b/js/src/jsinferinlines.h
@@ -4,16 +4,17 @@
  * 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/. */
 
 /* Inline members for javascript type inference. */
 
 #ifndef jsinferinlines_h
 #define jsinferinlines_h
 
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/PodOperations.h"
 
 #include "jsarray.h"
 #include "jsanalyze.h"
 #include "jscompartment.h"
 #include "jsinfer.h"
 #include "jsprf.h"
 #include "jsproxy.h"
@@ -1094,19 +1095,17 @@ const unsigned SET_ARRAY_SIZE = 8;
 static inline unsigned
 HashSetCapacity(unsigned count)
 {
     JS_ASSERT(count >= 2);
 
     if (count <= SET_ARRAY_SIZE)
         return SET_ARRAY_SIZE;
 
-    unsigned log2;
-    JS_FLOOR_LOG2(log2, count);
-    return 1 << (log2 + 2);
+    return 1 << (mozilla::FloorLog2(count) + 2);
 }
 
 /* Compute the FNV hash for the low 32 bits of v. */
 template <class T, class KEY>
 static inline uint32_t
 HashKey(T v)
 {
     uint32_t nv = KEY::keyBits(v);
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -6,16 +6,17 @@
 
 /*
  * JS object implementation.
  */
 #include "jsobjinlines.h"
 
 #include <string.h>
 
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/Util.h"
 
 #include "jstypes.h"
 #include "jsutil.h"
 #include "jsprf.h"
 #include "jsapi.h"
 #include "jsarray.h"
@@ -55,16 +56,17 @@
 
 using namespace js;
 using namespace js::gc;
 using namespace js::types;
 
 using js::frontend::IsIdentifier;
 using mozilla::ArrayLength;
 using mozilla::DebugOnly;
+using mozilla::RoundUpPow2;
 
 JS_STATIC_ASSERT(int32_t((JSObject::NELEMENTS_LIMIT - 1) * sizeof(Value)) == int64_t((JSObject::NELEMENTS_LIMIT - 1) * sizeof(Value)));
 
 Class JSObject::class_ = {
     js_Object_str,
     JSCLASS_HAS_CACHED_PROTO(JSProto_Object),
     JS_PropertyStub,         /* addProperty */
     JS_DeletePropertyStub,   /* delProperty */
--- a/js/src/jsutil.cpp
+++ b/js/src/jsutil.cpp
@@ -4,29 +4,31 @@
  * 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/. */
 
 /* Various JS utility functions. */
 
 #include "jsutil.h"
 
 #include "mozilla/Assertions.h"
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/PodOperations.h"
 
 #include <stdio.h>
 #include "jstypes.h"
 
 #ifdef WIN32
 #    include "jswin.h"
 #endif
 
 #include "js/Utility.h"
 
 using namespace js;
 
+using mozilla::CeilingLog2Size;
 using mozilla::PodArrayZero;
 
 #if USE_ZLIB
 static void *
 zlib_alloc(void *cx, uInt items, uInt size)
 {
     return js_malloc(items * size);
 }
@@ -189,17 +191,17 @@ ValToBin(unsigned logscale, uint32_t val
 {
     unsigned bin;
 
     if (val <= 1)
         return val;
     bin = (logscale == 10)
         ? (unsigned) ceil(log10((double) val))
         : (logscale == 2)
-        ? (unsigned) JS_CEILING_LOG2W(val)
+        ? (unsigned) CeilingLog2Size(val)
         : val;
     return Min(bin, 10U);
 }
 
 void
 JS_BasicStatsAccum(JSBasicStats *bs, uint32_t val)
 {
     unsigned oldscale, newscale, bin;
@@ -290,17 +292,17 @@ JS_DumpHistogram(JSBasicStats *bs, FILE 
             fprintf(fp, "[%6u, %6u]", val, end - 1);
         else
             fprintf(fp, "[%6u,   +inf]", val);
         fprintf(fp, ": %8u ", cnt);
         if (cnt != 0) {
             if (max > 1e6 && mean > 1e3)
                 cnt = uint32_t(ceil(log10((double) cnt)));
             else if (max > 16 && mean > 8)
-                cnt = JS_CEILING_LOG2W(cnt);
+                cnt = CeilingLog2Size(cnt);
             for (unsigned i = 0; i < cnt; i++)
                 putc('*', fp);
         }
         putc('\n', fp);
     }
 }
 
 #endif /* JS_BASIC_STATS */
--- a/js/src/vm/ObjectImpl.h
+++ b/js/src/vm/ObjectImpl.h
@@ -1593,17 +1593,17 @@ class ObjectImpl : public gc::Cell
      */
     static uint32_t dynamicSlotsCount(uint32_t nfixed, uint32_t span) {
         if (span <= nfixed)
             return 0;
         span -= nfixed;
         if (span <= SLOT_CAPACITY_MIN)
             return SLOT_CAPACITY_MIN;
 
-        uint32_t slots = RoundUpPow2(span);
+        uint32_t slots = mozilla::RoundUpPow2(span);
         MOZ_ASSERT(slots >= span);
         return slots;
     }
 
     /* Memory usage functions. */
     size_t tenuredSizeOfThis() const {
         return js::gc::Arena::thingSize(tenuredGetAllocKind());
     }
--- a/js/src/vm/Shape.cpp
+++ b/js/src/vm/Shape.cpp
@@ -2,16 +2,17 @@
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/. */
 
 /* JS symbol tables. */
 
 #include "mozilla/DebugOnly.h"
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/PodOperations.h"
 
 #include "jsapi.h"
 #include "jsatom.h"
 #include "jscntxt.h"
 #include "jsobj.h"
 
 #include "js/HashTable.h"
@@ -23,28 +24,29 @@
 #include "vm/Shape-inl.h"
 #include "vm/Runtime-inl.h"
 
 using namespace js;
 using namespace js::gc;
 
 using mozilla::DebugOnly;
 using mozilla::PodZero;
+using mozilla::CeilingLog2Size;
 
 bool
 ShapeTable::init(ExclusiveContext *cx, Shape *lastProp)
 {
     /*
      * Either we're creating a table for a large scope that was populated
      * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or
      * JSOP_SETPROP; or else calloc failed at least once already. In any
      * event, let's try to grow, overallocating to hold at least twice the
      * current population.
      */
-    uint32_t sizeLog2 = JS_CEILING_LOG2W(2 * entryCount);
+    uint32_t sizeLog2 = CeilingLog2Size(2 * entryCount);
     if (sizeLog2 < MIN_SIZE_LOG2)
         sizeLog2 = MIN_SIZE_LOG2;
 
     /*
      * Use rt->calloc_ for memory accounting and overpressure handling
      * without OOM reporting. See ShapeTable::change.
      */
     entries = (Shape **) cx->calloc_(sizeOfEntries(JS_BIT(sizeLog2)));
--- a/js/src/vm/String.cpp
+++ b/js/src/vm/String.cpp
@@ -1,28 +1,30 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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 "vm/String-inl.h"
 
+#include "mozilla/MathAlgorithms.h"
 #include "mozilla/MemoryReporting.h"
 #include "mozilla/PodOperations.h"
 #include "mozilla/RangedPtr.h"
 
 #include "gc/Marking.h"
 
 #include "jscompartmentinlines.h"
 
 using namespace js;
 
 using mozilla::PodCopy;
 using mozilla::RangedPtr;
+using mozilla::RoundUpPow2;
 
 bool
 JSString::isShort() const
 {
     // It's possible for short strings to be converted to flat strings;  as a
     // result, checking just for the arena isn't enough to determine if a
     // string is short.  Hence the isInline() check.
     bool is_short = (getAllocKind() == gc::FINALIZE_SHORT_STRING) && isInline();
--- a/mfbt/MathAlgorithms.h
+++ b/mfbt/MathAlgorithms.h
@@ -137,11 +137,292 @@ Abs<double>(const double d)
 
 template<>
 inline long double
 Abs<long double>(const long double d)
 {
   return std::fabs(d);
 }
 
+} // namespace mozilla
+
+#if defined(_WIN32) && (_MSC_VER >= 1300) && (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_X64))
+#  define MOZ_BITSCAN_WINDOWS
+
+  extern "C" {
+    unsigned char _BitScanForward(unsigned long* Index, unsigned long mask);
+    unsigned char _BitScanReverse(unsigned long* Index, unsigned long mask);
+#  pragma intrinsic(_BitScanForward, _BitScanReverse)
+
+#  if defined(_M_AMD64) || defined(_M_X64)
+#    define MOZ_BITSCAN_WINDOWS64
+    unsigned char _BitScanForward64(unsigned long* index, unsigned __int64 mask);
+    unsigned char _BitScanReverse64(unsigned long* index, unsigned __int64 mask);
+#   pragma intrinsic(_BitScanForward64, _BitScanReverse64)
+#  endif
+  } // extern "C"
+
+#endif
+
+namespace mozilla {
+
+namespace detail {
+
+#if defined(MOZ_BITSCAN_WINDOWS)
+
+  inline uint_fast8_t
+  CountLeadingZeroes32(uint32_t u)
+  {
+    unsigned long index;
+    _BitScanReverse(&index, static_cast<unsigned long>(u));
+    return uint_fast8_t(31 - index);
+  }
+
+
+  inline uint_fast8_t
+  CountTrailingZeroes32(uint32_t u)
+  {
+    unsigned long index;
+    _BitScanForward(&index, static_cast<unsigned long>(u));
+    return uint_fast8_t(index);
+  }
+
+  inline uint_fast8_t
+  CountLeadingZeroes64(uint64_t u)
+  {
+#  if defined(MOZ_BITSCAN_WINDOWS64)
+    unsigned long index;
+    _BitScanReverse64(&index, static_cast<unsigned __int64>(u));
+    return uint_fast8_t(63 - index);
+#  else
+    uint32_t hi = uint32_t(u >> 32);
+    if (hi != 0)
+      return CountLeadingZeroes32(hi);
+    return 32 + CountLeadingZeroes32(uint32_t(u));
+#  endif
+  }
+
+  inline uint_fast8_t
+  CountTrailingZeroes64(uint64_t u)
+  {
+#  if defined(MOZ_BITSCAN_WINDOWS64)
+    unsigned long index;
+    _BitScanForward64(&idx, static_cast<unsigned __int64>(u));
+    return uint_fast8_t(index);
+#  else
+    uint32_t lo = uint32_t(u);
+    if (lo != 0)
+      return CountTrailingZeroes32(lo);
+    return 32 + CountTrailingZeroes32(uint32_t(u >> 32));
+#  endif
+  }
+
+#  ifdef MOZ_HAVE_BITSCAN64
+#    undef MOZ_HAVE_BITSCAN64
+#  endif
+
+#elif defined(__clang__) || defined(__GNUC__)
+
+#  if defined(__clang__)
+#    if !__has_builtin(__builtin_ctz) || !__has_builtin(__builtin_clz)
+#      error "A clang providing __builtin_c[lt]z is required to build"
+#    endif
+#  else
+     // gcc has had __builtin_clz and friends since 3.4: no need to check.
+#  endif
+
+  inline uint_fast8_t
+  CountLeadingZeroes32(uint32_t u)
+  {
+    return __builtin_clz(u);
+  }
+
+  inline uint_fast8_t
+  CountTrailingZeroes32(uint32_t u)
+  {
+    return __builtin_ctz(u);
+  }
+
+  inline uint_fast8_t
+  CountLeadingZeroes64(uint64_t u)
+  {
+    return __builtin_clzll(u);
+  }
+
+  inline uint_fast8_t
+  CountTrailingZeroes64(uint64_t u)
+  {
+    return __builtin_ctzll(u);
+  }
+
+#else
+#  error "Implement these!"
+  inline uint_fast8_t CountLeadingZeroes32(uint32_t u) MOZ_DELETE;
+  inline uint_fast8_t CountTrailingZeroes32(uint32_t u) MOZ_DELETE;
+  inline uint_fast8_t CountLeadingZeroes64(uint64_t u) MOZ_DELETE;
+  inline uint_fast8_t CountTrailingZeroes64(uint64_t u) MOZ_DELETE;
+#endif
+
+} // namespace detail
+
+/**
+ * Compute the number of high-order zero bits in the NON-ZERO number |u|.  That
+ * is, looking at the bitwise representation of the number, with the highest-
+ * valued bits at the start, return the number of zeroes before the first one
+ * is observed.
+ *
+ * CountLeadingZeroes32(0xF0FF1000) is 0;
+ * CountLeadingZeroes32(0x7F8F0001) is 1;
+ * CountLeadingZeroes32(0x3FFF0100) is 2;
+ * CountLeadingZeroes32(0x1FF50010) is 3; and so on.
+ */
+inline uint_fast8_t
+CountLeadingZeroes32(uint32_t u)
+{
+  MOZ_ASSERT(u != 0);
+  return detail::CountLeadingZeroes32(u);
+}
+
+/**
+ * Compute the number of low-order zero bits in the NON-ZERO number |u|.  That
+ * is, looking at the bitwise representation of the number, with the lowest-
+ * valued bits at the start, return the number of zeroes before the first one
+ * is observed.
+ *
+ * CountTrailingZeroes32(0x0100FFFF) is 0;
+ * CountTrailingZeroes32(0x7000FFFE) is 1;
+ * CountTrailingZeroes32(0x0080FFFC) is 2;
+ * CountTrailingZeroes32(0x0080FFF8) is 3; and so on.
+ */
+inline uint_fast8_t
+CountTrailingZeroes32(uint32_t u)
+{
+  MOZ_ASSERT(u != 0);
+  return detail::CountTrailingZeroes32(u);
+}
+
+/** Analogous to CountLeadingZeroes32, but for 64-bit numbers. */
+inline uint_fast8_t
+CountLeadingZeroes64(uint64_t u)
+{
+  MOZ_ASSERT(u != 0);
+  return detail::CountLeadingZeroes64(u);
+}
+
+/** Analogous to CountTrailingZeroes32, but for 64-bit numbers. */
+inline uint_fast8_t
+CountTrailingZeroes64(uint64_t u)
+{
+  MOZ_ASSERT(u != 0);
+  return detail::CountTrailingZeroes64(u);
+}
+
+namespace detail {
+
+template<typename T, size_t Size = sizeof(T)>
+class CeilingLog2;
+
+template<typename T>
+class CeilingLog2<T, 4>
+{
+  public:
+    static uint_fast8_t compute(const T t) {
+      // Check for <= 1 to avoid the == 0 undefined case.
+      return t <= 1 ? 0 : 32 - CountLeadingZeroes32(t - 1);
+    }
+};
+
+template<typename T>
+class CeilingLog2<T, 8>
+{
+  public:
+    static uint_fast8_t compute(const T t) {
+      // Check for <= 1 to avoid the == 0 undefined case.
+      return t <= 1 ? 0 : 64 - CountLeadingZeroes64(t - 1);
+    }
+};
+
+} // namespace detail
+
+/**
+ * Compute the log of the least power of 2 greater than or equal to |t|.
+ *
+ * CeilingLog2(0..1) is 0;
+ * CeilingLog2(2) is 1;
+ * CeilingLog2(3..4) is 2;
+ * CeilingLog2(5..8) is 3;
+ * CeilingLog2(9..16) is 4; and so on.
+ */
+template<typename T>
+inline uint_fast8_t
+CeilingLog2(const T t)
+{
+  return detail::CeilingLog2<T>::compute(t);
+}
+
+/** A CeilingLog2 variant that accepts only size_t. */
+inline uint_fast8_t
+CeilingLog2Size(size_t n)
+{
+  return CeilingLog2(n);
+}
+
+namespace detail {
+
+template<typename T, size_t Size = sizeof(T)>
+class FloorLog2;
+
+template<typename T>
+class FloorLog2<T, 4>
+{
+  public:
+    static uint_fast8_t compute(const T t) {
+      return 31 - CountLeadingZeroes32(t | 1);
+    }
+};
+
+template<typename T>
+class FloorLog2<T, 8>
+{
+  public:
+    static uint_fast8_t compute(const T t) {
+      return 63 - CountLeadingZeroes64(t | 1);
+    }
+};
+
+} // namespace detail
+
+/**
+ * Compute the log of the greatest power of 2 less than or equal to |t|.
+ *
+ * FloorLog2(0..1) is 0;
+ * FloorLog2(2..3) is 1;
+ * FloorLog2(4..7) is 2;
+ * FloorLog2(8..15) is 3; and so on.
+ */
+template<typename T>
+inline uint_fast8_t
+FloorLog2(const T t)
+{
+  return detail::FloorLog2<T>::compute(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.
+ */
+inline size_t
+RoundUpPow2(size_t x)
+{
+  MOZ_ASSERT(~x > x, "can't round up -- will overflow!");
+  return size_t(1) << CeilingLog2(x);
+}
+
 } /* namespace mozilla */
 
 #endif  /* mozilla_MathAlgorithms_h_ */
--- a/mfbt/tests/Makefile.in
+++ b/mfbt/tests/Makefile.in
@@ -10,17 +10,19 @@ VPATH = @srcdir@
 include $(DEPTH)/config/autoconf.mk
 
 STL_FLAGS =
 
 CPP_UNIT_TESTS = \
   TestAtomics.cpp \
   TestBloomFilter.cpp \
   TestCasting.cpp \
+  TestCeilingFloor.cpp \
   TestCheckedInt.cpp \
+  TestCountZeroes.cpp \
   TestEndian.cpp \
   TestEnumSet.cpp \
   TestSHA1.cpp \
   TestTypeTraits.cpp \
   TestWeakPtr.cpp \
   $(NULL)
 
 # These tests don't work with AddressSanitizer enabled
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestCeilingFloor.cpp
@@ -0,0 +1,54 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* 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;
+
+static void
+TestCeiling()
+{
+  for (uint32_t i = 0; i <= 1; i++)
+    MOZ_ASSERT(CeilingLog2(i) == 0);
+
+  for (uint32_t i = 2; i <= 2; i++)
+    MOZ_ASSERT(CeilingLog2(i) == 1);
+
+  for (uint32_t i = 3; i <= 4; i++)
+    MOZ_ASSERT(CeilingLog2(i) == 2);
+
+  for (uint32_t i = 5; i <= 8; i++)
+    MOZ_ASSERT(CeilingLog2(i) == 3);
+
+  for (uint32_t i = 9; i <= 16; i++)
+    MOZ_ASSERT(CeilingLog2(i) == 4);
+}
+
+static void
+TestFloor()
+{
+  for (uint32_t i = 0; i <= 1; i++)
+    MOZ_ASSERT(FloorLog2(i) == 0);
+
+  for (uint32_t i = 2; i <= 3; i++)
+    MOZ_ASSERT(FloorLog2(i) == 1);
+
+  for (uint32_t i = 4; i <= 7; i++)
+    MOZ_ASSERT(FloorLog2(i) == 2);
+
+  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);
+}
+
+int main()
+{
+  TestCeiling();
+  TestFloor();
+  return 0;
+}
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestCountZeroes.cpp
@@ -0,0 +1,100 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* 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::CountLeadingZeroes32;
+using mozilla::CountLeadingZeroes64;
+using mozilla::CountTrailingZeroes32;
+using mozilla::CountTrailingZeroes64;
+
+static void
+TestLeadingZeroes32()
+{
+  MOZ_ASSERT(CountLeadingZeroes32(0xF0FF1000) == 0);
+  MOZ_ASSERT(CountLeadingZeroes32(0x7F8F0001) == 1);
+  MOZ_ASSERT(CountLeadingZeroes32(0x3FFF0100) == 2);
+  MOZ_ASSERT(CountLeadingZeroes32(0x1FF50010) == 3);
+  MOZ_ASSERT(CountLeadingZeroes32(0x00800000) == 8);
+  MOZ_ASSERT(CountLeadingZeroes32(0x00400000) == 9);
+  MOZ_ASSERT(CountLeadingZeroes32(0x00008000) == 16);
+  MOZ_ASSERT(CountLeadingZeroes32(0x00004000) == 17);
+  MOZ_ASSERT(CountLeadingZeroes32(0x00000080) == 24);
+  MOZ_ASSERT(CountLeadingZeroes32(0x00000040) == 25);
+  MOZ_ASSERT(CountLeadingZeroes32(0x00000001) == 31);
+}
+
+static void
+TestLeadingZeroes64()
+{
+  MOZ_ASSERT(CountLeadingZeroes64(0xF000F0F010000000) == 0);
+  MOZ_ASSERT(CountLeadingZeroes64(0x70F080F000000001) == 1);
+  MOZ_ASSERT(CountLeadingZeroes64(0x30F0F0F000100000) == 2);
+  MOZ_ASSERT(CountLeadingZeroes64(0x10F0F05000000100) == 3);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0080000000000001) == 8);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0040000010001000) == 9);
+  MOZ_ASSERT(CountLeadingZeroes64(0x000080F010000000) == 16);
+  MOZ_ASSERT(CountLeadingZeroes64(0x000040F010000000) == 17);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000008000100100) == 24);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000004100010010) == 25);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000080100100) == 32);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000041001010) == 33);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000000800100) == 40);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000000411010) == 41);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000000008001) == 48);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000000004010) == 49);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000000000081) == 56);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000000000040) == 57);
+  MOZ_ASSERT(CountLeadingZeroes64(0x0000000000000001) == 63);
+}
+
+static void
+TestTrailingZeroes32()
+{
+  MOZ_ASSERT(CountTrailingZeroes32(0x0100FFFF) == 0);
+  MOZ_ASSERT(CountTrailingZeroes32(0x7000FFFE) == 1);
+  MOZ_ASSERT(CountTrailingZeroes32(0x0080FFFC) == 2);
+  MOZ_ASSERT(CountTrailingZeroes32(0x0080FFF8) == 3);
+  MOZ_ASSERT(CountTrailingZeroes32(0x010FFF00) == 8);
+  MOZ_ASSERT(CountTrailingZeroes32(0x7000FE00) == 9);
+  MOZ_ASSERT(CountTrailingZeroes32(0x10CF0000) == 16);
+  MOZ_ASSERT(CountTrailingZeroes32(0x0BDE0000) == 17);
+  MOZ_ASSERT(CountTrailingZeroes32(0x0F000000) == 24);
+  MOZ_ASSERT(CountTrailingZeroes32(0xDE000000) == 25);
+  MOZ_ASSERT(CountTrailingZeroes32(0x80000000) == 31);
+}
+
+static void
+TestTrailingZeroes64()
+{
+  MOZ_ASSERT(CountTrailingZeroes64(0x000100000F0F0F0F) == 0);
+  MOZ_ASSERT(CountTrailingZeroes64(0x070000000F0F0F0E) == 1);
+  MOZ_ASSERT(CountTrailingZeroes64(0x000008000F0F0F0C) == 2);
+  MOZ_ASSERT(CountTrailingZeroes64(0x000008000F0F0F08) == 3);
+  MOZ_ASSERT(CountTrailingZeroes64(0xC001000F0F0F0F00) == 8);
+  MOZ_ASSERT(CountTrailingZeroes64(0x0200000F0F0F0E00) == 9);
+  MOZ_ASSERT(CountTrailingZeroes64(0xB0C10F0FEFDF0000) == 16);
+  MOZ_ASSERT(CountTrailingZeroes64(0x0AAA00F0FF0E0000) == 17);
+  MOZ_ASSERT(CountTrailingZeroes64(0xD010F0FEDF000000) == 24);
+  MOZ_ASSERT(CountTrailingZeroes64(0x7AAF0CF0BE000000) == 25);
+  MOZ_ASSERT(CountTrailingZeroes64(0x20F0A5D100000000) == 32);
+  MOZ_ASSERT(CountTrailingZeroes64(0x489BF0B200000000) == 33);
+  MOZ_ASSERT(CountTrailingZeroes64(0xE0F0D10000000000) == 40);
+  MOZ_ASSERT(CountTrailingZeroes64(0x97F0B20000000000) == 41);
+  MOZ_ASSERT(CountTrailingZeroes64(0x2C07000000000000) == 48);
+  MOZ_ASSERT(CountTrailingZeroes64(0x1FBA000000000000) == 49);
+  MOZ_ASSERT(CountTrailingZeroes64(0x0100000000000000) == 56);
+  MOZ_ASSERT(CountTrailingZeroes64(0x0200000000000000) == 57);
+  MOZ_ASSERT(CountTrailingZeroes64(0x8000000000000000) == 63);
+}
+
+int main()
+{
+  TestLeadingZeroes32();
+  TestLeadingZeroes64();
+  TestTrailingZeroes32();
+  TestTrailingZeroes64();
+  return 0;
+}