| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // ====================================================================== | ||
| 2 | // \title Algorithms.cpp | ||
| 3 | // \author sjsreehari | ||
| 4 | // \brief cpp file for general-purpose mathematical algorithms | ||
| 5 | // | ||
| 6 | // \copyright | ||
| 7 | // Copyright (C) 2026 California Institute of Technology. | ||
| 8 | // ALL RIGHTS RESERVED. United States Government Sponsorship | ||
| 9 | // acknowledged. | ||
| 10 | // ====================================================================== | ||
| 11 | |||
| 12 | #include <Fw/Types/Assert.hpp> | ||
| 13 | #include <Utils/Algorithms.hpp> | ||
| 14 | #include <limits> | ||
| 15 | |||
| 16 | namespace Utils { | ||
| 17 | namespace Algorithms { | ||
| 18 | |||
| 19 | 38 | FwSizeType gcd(FwSizeType a, FwSizeType b) { | |
| 20 | 38 | const FwSizeType maxIterations = static_cast<FwSizeType>(std::numeric_limits<FwSizeType>::digits) * 2; | |
| 21 |
3/4✓ Branch 0 taken 114 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 76 times.
✓ Branch 3 taken 38 times.
|
114 | for (FwSizeType i = 0; (i < maxIterations) && (b != 0); i++) { |
| 22 | 76 | FwSizeType temp = b; | |
| 23 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 76 times.
|
76 | b = a % b; |
| 24 | 76 | a = temp; | |
| 25 | } | ||
| 26 | 38 | FW_ASSERT(b == 0); | |
| 27 | 38 | return a; | |
| 28 | } | ||
| 29 | |||
| 30 | 30 | FwSizeType lcm(FwSizeType a, FwSizeType b) { | |
| 31 | 30 | FW_ASSERT(a != 0); | |
| 32 | 30 | FW_ASSERT(b != 0); | |
| 33 | 30 | const FwSizeType g = gcd(a, b); | |
| 34 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
|
30 | const FwSizeType a_div_g = a / g; |
| 35 | // Ensure that lcm will not overflow | ||
| 36 | 30 | FW_ASSERT((std::numeric_limits<FwSizeType>::max() / b) >= a_div_g, static_cast<FwAssertArgType>(a), | |
| 37 | static_cast<FwAssertArgType>(b)); | ||
| 38 | 30 | return a_div_g * b; | |
| 39 | } | ||
| 40 | |||
| 41 | } // namespace Algorithms | ||
| 42 | } // namespace Utils | ||
| 43 |