mfbt/MathAlgorithms.h

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 /* mfbt maths algorithms. */
   7
   8 #ifndef mozilla_MathAlgorithms_h_
   9 #define mozilla_MathAlgorithms_h_
  10
  11 #include "mozilla/Assertions.h"
  12
  13 namespace mozilla {
  14
  15 // Greatest Common Divisor
  16 template<typename IntegerType>
  17 MOZ_ALWAYS_INLINE IntegerType
  18 EuclidGCD(IntegerType a, IntegerType b)
  19 {
  20   // Euclid's algorithm; O(N) in the worst case.  (There are better
  21   // ways, but we don't need them for the current use of this algo.)
  22   MOZ_ASSERT(a > 0);
  23   MOZ_ASSERT(b > 0);
  24
  25   while (a != b) {
  26     if (a > b) {
  27       a = a - b;
  28     } else {
  29       b = b - a;
  30     }
  31   }
  32
  33   return a;
  34 }
  35
  36 // Least Common Multiple
  37 template<typename IntegerType>
  38 MOZ_ALWAYS_INLINE IntegerType
  39 EuclidLCM(IntegerType a, IntegerType b)
  40 {
  41   // Divide first to reduce overflow risk.
  42   return (a / EuclidGCD(a, b)) * b;
  43 }
  44
  45 } /* namespace mozilla */
  46
  47 #endif  /* mozilla_MathAlgorithms_h_ */