Skip to content

Algorithms

lbuild module: modm:math:algorithm

A collection of useful and lightweight algorithms.

Convenience Iterators

Inspired by Python's built-in range and enumerate functions, you can use modm::range and modm::enumerate in for loops:

// Iterates over 0 .. 9
for (auto i : modm::range(10)) {
    MODM_LOG_INFO << i << modm::endl;
}
// Iterates over 10 .. 19
for (auto i : modm::range(10, 20)) {
    MODM_LOG_INFO << i << modm::endl;
}
// Iterates over 20, 22, 24, 26, 28
for (auto i : modm::range(20, 30, 2)) {
    MODM_LOG_INFO << i << modm::endl;
}

// Iterates over 0 .. N-1, where N = size of iterable
for (auto [i, item] : modm::enumerate(iterable)) {
    MODM_LOG_INFO << i << item << modm::endl;
}

Prescaler Calculators

Peripheral output frequencies are usually generated by dividing an input clock with a prescaler in hardware. Finding the closest prescaler value for a desired output frequency can be unintuitive, therefore, these classes provide a simple interface for a constexpr calculator.

All calculators return a Result struct containing desired, input, and output frequencies, the relative error of the output vs desired frequency, and the prescaler and its index. The prescaler index is typically the value to write to the register directly:

// 16-bit linear prescaler [1, 2^16] mapped as [0, 0xffff].
constexpr auto result = Prescaler::from_linear(10_MHz, 1_kHz, 1, 1ul << 16);
static_assert(result.input_frequency == 10_MHz);
static_assert(result.desired_frequency == 1_kHz);
// Calculator finds an exact match without error
static_assert(result.frequency == 1_kHz);
static_assert(result.error == 0);
// with prescaler 1e4 = 1e7 / 1e3.
static_assert(result.prescaler == 10'000);
static_assert(result.index == 9'999);
PERIPHERAL->PRESCALER = result.index;

The index is particularly useful for non-contiguous prescalers, the most common being power-of-two values:

// Power-of-two prescaler with 8 values between [16, 4096].
constexpr auto result = Prescaler::from_power(32_kHz, 100_Hz, 1ul << 4, 1ul << 12);
// Calculator cannot find an exact match! Closest has -25% error!
static_assert(result.frequency == 125_Hz);
static_assert(result.error == -0.25);
// Ideal Prescaler is 320, clostest is 256
static_assert(result.prescaler == 256);
// Index is 256 = 1ul << (4 + 4)
static_assert(result.index == 4);

Non-contiguous prescalers can also be created with a modifier function:

// Only even prescalers from [2, 1024]
constexpr auto result = Prescaler::from_function(
        110_MHz, 3.5_MHz, 1, 512, [](uint32_t i){ return i*2; });
// Ideal prescaler is 31.4, closest is 32 with ~2% error.
static_assert(result.frequency == 3.4375_MHz);
static_assert(result.error == 0.02);
static_assert(result.prescaler == 32);
static_assert(result.index == 15); // 32/2 - 1

For all other cases, prescalers can be passed as an initializer list or as any forward range. Note that the prescaler values must be sorted, otherwise the calculator will compute the wrong prescaler values!

constexpr auto result = Prescaler::from_list(1_MHz, 1_kHz, {2,4,16,256,1024});
constexpr auto result = Prescaler::from_range(2_kHz, 1_kHz, std::array{1,2,3});

A special case is made of two chained prescalers that are both linear powers-of-two. These are often called "fractional prescalers" and act as a single binary-scaled linear prescaler and can thus be modeled as such:

// A fractional 12.4-bit prescaler can be modeled as a single 16-bit prescaler.
constexpr auto result = Prescaler::from_linear(SystemClock::Usart1, 115200, 16, 1ul << 16);
// The resulting prescaler can be written directly to the register.
USART1->BRR = result.prescaler;

Prescalers with Counters

However, often chained prescalers cannot be converted to a linear prescaler, for example, a timer with a set of power-of-two prescalers and a 16 or 32-bit counter. These must be computed with a different class:

// A prescaler with power-of-two values [4, 256] going into a 12-bit down counter.
constexpr auto result = PrescalerCounter::from_power(32_kHz, 1_Hz, 1ul << 12, 4, 256);
// Calculator finds an exact match without error
static_assert(result.frequency == 1_Hz);
static_assert(result.error == 0);
// with prescaler 8 and counter 4'000.
static_assert(result.prescaler == 8);
static_assert(result.counter == 4'000);
static_assert(result.index == 1);

The calculator only picks the first prescaler with the lowest error, however, in this example, there can be multiple exact solutions:

32000 = 8 × 4000 = 16 × 2000 = ... = 128 × 250 = 256 × 125

If the prescaler and counter is used to generate a waveform like PWM, then it is beneficial to pick the combination with the largest counter value. However, if the use case is to preserve power, then a slow running counter requires the highest prescaler. Therefore the order of prescalers can be reversed:

constexpr auto result = PrescalerCounter::from_power(32_kHz, 1_Hz, 1ul << 12, 256, 4);
static_assert(result.prescaler == 256);
static_assert(result.counter == 125);
// Index is not the same!
static_assert(result.index == 0);

The same applies to the PrescalerCounter::from_linear() and PrescalerCounter::from_function() calculators, while the order for lists and forward ranges can be entirely arbitrary:

constexpr auto result = PrescalerCounter::from_list(32_kHz, 1_Hz, 1ul << 12, {128,16,256,4});
static_assert(result.prescaler == 128);
static_assert(result.counter == 250);
// Index is relative to the list order now!
static_assert(result.index == 0);

Time Durations

While the calculator is designed for frequencies, time durations can also be computed by transforming the input as frequency = 1.0 / duration and then transforming the output back as duration = 1.0 / frequency.

Floating-Point Frequencies

You can define the type used for frequency representation by using the GenericPrescaler<double> and GenericPrescalerCounter<double> classes.

Tolerance of Prescaler Error

Each Result has a signed(!), relative error attached, which can be used to assert on the quality of the calculation. Note that using static_assert on the error directly will only print the error values:

static_assert(std::abs(result.error) < 5_pct);

error: static assertion failed
 | static_assert(std::abs(result.error) < tolerance);
 |               ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
note: the comparison reduces to '(0.10 < 0.05)'

However, by using a helper method, the requested and closest available frequencies can be displayed to the developer:

// Accidentally used kBaud instead of Baud, which cannot be generated
constexpr auto result = Prescaler::from_linear(SystemClock::Usart2, 115200_kBd, 16, 1ul << 16);
modm::assertBaudrateInTolerance<result.frequency, result.desired_frequency, tolerance>();

In instantiation of 'static void modm::PeripheralDriver::assertBaudrateInTolerance()
[with long long unsigned int available = 3000000; long long unsigned int requested = 115200000; float tolerance = 0.01f]':
error: static assertion failed: The closest available baudrate exceeds the tolerance of the requested baudrate!
 | static_assert(modm::isValueInTolerance(requested, available, tolerance),
 |               ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
note: 'modm::isValueInTolerance<long long unsigned int>(115200000, 3000000, 0.01f)' evaluates to false

Dependencies

modm:math:algorithm modm_math_algorithm modm: math: algorithm modm_math_units modm: math: units modm_math_algorithm->modm_math_units