# Algorithms

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:

```cpp
// 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:

```cpp
// 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:

```cpp
// 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:

```cpp
// 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!

```cpp
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:

```cpp
// 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:

```cpp
// 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:

```cpp
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:

```cpp
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);
```

!!! tip "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`.

!!! success "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:

```cpp
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:

```cpp
// 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
```
