Need help to build a generics making operation with it's parameter

Hi, i'm trying to create( translate from C++) a generic containing an array with size determined by the generic parameters. If const generics where fully supported, the code would be:

pub struct FirUpsampler<const SIZE:usize,const RATIO: usize>{
    h:usize, //history index
    c:[f32;SIZE],//coefficients
    x:[f32;usize::next_power_of_two ((SIZE + RATIO - 1) / RATIO)],//history
}

unfortunately, this doesn't work because generics parameter are not allowed in const operation.

So i tried to use typenum +generic_array, so i got this code:

#![recursion_limit="256"]
#[macro_use] extern crate typenum;

use typenum::marker_traits::{Unsigned,PowerOfTwo};
use typenum::consts::*;
use generic_array::{ArrayLength, GenericArray};

type NextPowerOfTwo<VAL> = op!(((VAL - U1) | (VAL - U1) >> U1 | (VAL - U1) >> U2 |(VAL - U1) >> U4 | (VAL - U1) >> U8 | (VAL - U1) >> U16)+U1);

/// FIR upsampler, optimised not to store the 0 samples
pub struct FirUpsampler<SIZE,RATIO>
where SIZE : Unsigned + PowerOfTwo + ArrayLength<f32>, RATIO :Unsigned
{
    h:usize, //history index
    c:GenericArray<f32,SIZE>,//coefficients
    x:GenericArray<f32,NextPowerOfTwo<op!((SIZE + RATIO - U1) / RATIO)>>,//history
}

Unfortunatly, it's seems to require one trait bound per typenum operation, which is almost inconceivable. I tried to workaround with 'num_traits' but i failed :frowning_face:

Any idea on how i can implement this ?

Are you allowed to use Vec and manage the array sizes at runtime?

No, because i'd like to run this code on embedded target.

@YruamaLairba, I'm on mobile at the moment, so I can't flesh this out. But I think you could define a new trait and implement it for typenum types. It would map to either a usize const for the next power of two, or perhaps the f32 array type directly.

That being said, I've tried to do similar things, and the types can get hairy quickly. If this is the only compile-time sizing you need to do, then it's probably fine. But if you need to carry this through all your code, you might see if there's a way you can live with known array sizes (not computed at compile-time) and the heapless crate. You waste some space, but the code gets MUCH simpler.

maybe, but at the moment i don't see how to do it without writing implementation for each typenum type. I mean i don't know how to use a "generic representation" of typenum to write it once for all typenum.

Nope, never mind. I thought you could use an associated constant as an array length, at least in a struct definition, but that's wrong. You have to do the entire calculation in the type domain, which you've already seen is cumbersome with typenum. Sorry, I don't have any other immediate ideas.

meanwhile, i trying this for my NextPowerOfTwo:

use typenum::marker_traits::{Unsigned,PowerOfTwo};
use typenum::type_operators::*;
use typenum::operator_aliases::*;
use typenum::consts::*;
use typenum::bit::*;
use typenum::uint::*;

trait NextPowerOfTwo{
    type Output;
}

type NextPowerOfTwoVal<V> = <V as NextPowerOfTwo>::Output;

impl<T> NextPowerOfTwo for T
where T: Logarithm2,
U2 : Pow<Log2<T>>{
    type Output = Exp<U2,Log2<T>>;
}

fn main(){
    println!("{}",NextPowerOfTwoVal::<U0>::USIZE);
}

This doesn't work, it's seems to produce a recursion loop.

@YruamaLairba, you might want to consider if the compile-time checks are worth the complexity. Even for simple concatenation of arrays, the type signatures can get complex. I was using typenum for array concatenation in an embedded context, but after six months away from the code, I came back and realized just how ugly it was. I switched to heapless::Vec and I'm much happier with the result.

If the arrays are small, you might just bite the bullet with a fixed, upfront size. If they're large, have you considered something like heapless::pool::Box? That might be better than moving around a large array anyway.

Wait, scratch that, I've never actually used heapless::pool::Box, so I'm not sure if it actually could solve your problem here. Sorry about that.

I can permit to spend(or waste) many time on this, and i progress. I'm now able to round to next power of two with typenum, and this trick will probably reused at many place. I was inspired by Log2, because implementation is very close.
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d34240fc3098089f5953eecb3055a4dd

I want to avoid heapless for some reason:

  • I didn't use yet, so i don't know how it works
  • I'd like to be able to use the same code in embedded and not embedded target when it's possible.
  • i'd like to avoid "allocation" when it's technically not required.

i admit those reason are weak :slight_smile:

1 Like

I think i did it.

@bradleyharden your right, trait bound tend to clutter the code and is very difficult to understand without diving into typenum. I will see with practice if it's cool or crap.

//! Finite impulse response filters, with options for up- and down-sampling.
use core::ops::Add;
use core::ops::Div;
use core::ops::Mul;
use core::ops::Sub;
use generic_array::{ArrayLength, GenericArray};
use typenum::bit::*;
use typenum::consts::*;
use typenum::marker_traits::PowerOfTwo;
use typenum::marker_traits::Unsigned;
use typenum::operator_aliases::*;
use typenum::uint::*;

pub trait RoundToNextPowerOfTwo {
    type Output;
}

pub type RoundToNextPowerOfTwoVal<V> = <V as RoundToNextPowerOfTwo>::Output;

pub trait NextPowerOfTwo {
    type Output;
}

pub type NextPowerOfTwoVal<V> = <V as NextPowerOfTwo>::Output;

pub trait PrivateNextPowerOfTwo {
    type Output;
}

impl RoundToNextPowerOfTwo for UTerm {
    type Output = U1;
}

impl<U, B> RoundToNextPowerOfTwo for UInt<U, B>
where
    Self: Sub<B1>,
    Sub1<Self>: NextPowerOfTwo,
{
    type Output = <Sub1<Self> as NextPowerOfTwo>::Output;
}

impl<N> NextPowerOfTwo for N
where
    N: PrivateNextPowerOfTwo,
{
    type Output = <Self as PrivateNextPowerOfTwo>::Output;
}

// next_power_of_2(0) = 1.
impl PrivateNextPowerOfTwo for UTerm {
    type Output = U1;
}

// General case of next_power_of_2(Self) where Self >= 2.
impl<U, B> PrivateNextPowerOfTwo for UInt<U, B>
where
    U: Unsigned + NextPowerOfTwo,
    B: Bit,
    NextPowerOfTwoVal<U>: Mul<U2>,
{
    type Output = Prod<NextPowerOfTwoVal<U>, U2>;
}


/// FIR upsampler, optimised not to store the 0 samples
pub struct FirUpsampler<SIZE, RATIO>
where
    //Bound for typenum arithmetics
    SIZE: Unsigned + Add<RATIO>,
    RATIO: Unsigned,
    Sum<SIZE,RATIO> : Sub<B1>,
    Sub1<Sum<SIZE,RATIO>>: Div<RATIO>,
    Quot<Sub1<Sum<SIZE,RATIO>>,RATIO>: RoundToNextPowerOfTwo,
    //Bound for Generic Array
    SIZE: PowerOfTwo + ArrayLength<f32>,
    RoundToNextPowerOfTwoVal<Quot<Sub1<Sum<SIZE,RATIO>>,RATIO>> : PowerOfTwo + ArrayLength<f32>,

{
    h: usize,                                               //history index
    c: GenericArray<f32, SIZE>,                             //coefficients
    x: GenericArray<f32, RoundToNextPowerOfTwoVal<Quot<Sub1<Sum<SIZE,RATIO>>,RATIO>>>, //history
}

Clever solution. Yeah, if you can express the operation recursively, the typenum approach becomes a lot more tractable.

I can appreciate wanting to find a way to express it, no matter how complex the solution. It's a fun little problem. That's what I wanted too (at first).

But looking at that final code... yikes :grimacing:, lol. I have a reasonable understanding of typenum and even I get completely lost in it. To me, it's just not worth it.

One day, though, we'll have full const generics and this will all go away.

Out of curiosity, did you try switching to nightly and activating the generic_const_exprs feature?

Literally translating your C++ code to Rust seems to compile with no problems:

#![allow(incomplete_features, dead_code)]
#![feature(generic_const_exprs)]

pubstruct FirUpsampler<const SIZE: usize, const RATIO: usize>
where
    [(); usize::next_power_of_two((SIZE + RATIO - 1) / RATIO)]: ,
{
    h: usize,
    c: [f32; SIZE],
    x: [f32; usize::next_power_of_two((SIZE + RATIO - 1) / RATIO)],
}

(playground)

@Michael-F-Bryan No, i didn't try. But i will probably switch to that if generic_const_exprs land stable while i'm working with it.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.