`HybridUint` for mix-match `Uint` in-struct

[pinkforest]

This could be a variant of "worst case" where the Limbs are MaybeUninit or heapless::Vec which uses MaybeUninit behind the scenes.

This would allow easier portability between BoxedUint and no-alloc variant without re-writing into fixed sizes whilst avoiding global alloc ? e.g. here:

• [WIP] Fixed-size no_alloc-friendly keys RSA#636 (comment)

Say there is:

struct Foo {
  a: HeaplessUint<2>, // U64/U128 Max
  b: HeaplessUint<1>, // U32/64 Max
}

It would be more memory efficient than:

struct Foo<U: Unsigned> {
  a: U
  b: U
}

Where used U can be U2048 | U4096 etc. in case which it takes double the space vs optimising through worst case.

And more flexible than relying on type-aliases:

struct Foo {
  a: U2048,
  b: U128,
}

Arguably it is just another form of Uint<Limbs> but Heapless is essentially optimizing through [MaybeUninit<Limb>; N]

[tarcieri]

I think it would maybe make more sense to have something backed by hybrid-array so we could use typenum size calculations. crypto-bigint is about fixed-precision integers whose size doesn't change so we always use a constant number of iterations, so we don't benefit from data structures like heapless::Vec or MaybeUninit.

The backing storage for BoxedUint is actually a boxed slice of limbs, not a Vec: https://github.com/RustCrypto/crypto-bigint/blob/master/src/uint/boxed.rs#L59

BoxedUint is trying its hardest to work like the stack-allocated version.

[andrewwhitehead]

Maybe eventually BoxedUint could be made generic in the storage type, for types that aren't necessarily stored on the stack or free to allocate/clone. I created flex-alloc for this sort of purpose although it could use more test coverage and real world usage.

[pinkforest]

is about fixed-precision integers whose size doesn't chang

Only with construction by what I mean where upon construct it is called with intended bits precision and it will stay fixed ever long after that whilst still allowing compiler to optimize the final size (upon construct) with MaybeUninit<T> the array elements that may or may not get constructed at the beginning.

Heapless was also due in case we don't tolerate unsafe in the crate which can reside in heapless - which also has Box btw.

On heapless case it's not different from array [MaybeUninit<u32/u64>; MAX_LIMBS] but having unsafe or not in crate is.

boxed slice of limbs, not a Vec

Heapless is "fake Vec" which uses MaybeUninit behind the scenes for T and includes the capacity information but will not grow from itself unlike alloc Vec which will also move and double size upon growing over capacity (for which I made a special container that does unmovable slab storage https://github.com/yaws-rs/edifice)

[pinkforest]

Like for example referring to the key example I need it in:

FixedRsaPrivateKey<U: Unsigned> {
  d: U,
  p: U,
  q: U,
  x: ...
}

That means I can have AnyUint<MAX> that's U:Unsigned where it gets optimized to size actually needed upon construct.

I can group them further

FixedRsaPrivateKey<U: Unsigned, P: Unsigned> {
  d: U,
  p: P,
  q: P,
  x: ...
}

where I can have AnyUint<MAX_D> and AnyUint<MAX_P> that both are U:Unsigned grouped together

Given the problem here it taking +4kB stack in:

• [WIP] Fixed-size no_alloc-friendly keys RSA#636 (comment)

We can optimize the elements through grouping by setting max intended size for "fake growable" that can be generalized.

This way both U and P can be also BoxedUint (heap) as well as AnyUint<MAX> (stack)

It also allows construction where instead of Option<PreComputed> where it did not get initialized and takes zero stack given in current fixed construct with no MaybeUnit it will take the space regardless if it's None.

[tarcieri]

We've supported heapless for over half a decade in AEADs. I'm quite familiar with what it is and used it when I was doing embedded work.

The thing is heapless::Vec still has runtime dynamism around its length, even if it's fixed-size. That's what we don't want. That's why we don't use Vec at all, even when the alloc feature is enabled.

Using something like hybrid-array gives you the full power of typenum type-level arithmetic to do things like multiply sizes by two and so forth and would give you the expressiveness you need to describe those relationships, but without the things we don't need like MaybeUninit elements and variable-lengths at runtime.

[pinkforest]

So should it be HybridUint ?

struct HybridUint<S: ArraySize>(Array<Limb, S>);

struct MultiSize {
    a: HybridUint<U2>,
    b: HybridUint<U3>,
}

It still works generalizing Uint<Limbs> though but then it's going to drag the generics X size-variations.

struct MultiSize<M: Unsigned, P: Unsigned> {
    m: M,
    p: P,
    q: P,
}

Though expressing overly generic like this will just force to use the biggest variant again?

struct MultiSizeGeneric<H> {
    a: H,
    b: H,
}

The question is how to mix the constructor parameters for different (relationally-compatible) size needs around one type, e.g. RSA2048 etc. without adding too many generics and without having sizes that need to be explicitly mentioned - or at least where there is linkage between say A/B)

I see your comment about making Uint as generic around bits

• https://docs.rs/crypto-bigint/latest/src/crypto_bigint/uint.rs.html#75

heapless also has Box fwiw

[tarcieri]

We're probably "at capacity" in terms of adding more integer types to crypto-bigint (except maybe a BoxedInt for parity with Int, as a wrapper for BoxedUint) as the library is already quite large, but with UintRef now exposed it should become possible to implement additional integer types in external crates using UintRef as the core (to a certain degree, there are still a lot of gaps, but those would be good to fill in and could DRY out the existing implementation).

I did also realize that there might be merit to heapless::Vec for rsa: if you use fixed-size integers it will monomorphize for a given key/modulus size, which is great if you only want to use one key size, but if you want to use a smaller key size you're still going at the speed of the key size you monomorphized for, or you have to monomorphize for every key size you want to support.

heapless::Vec would take up as much space as the largest key size you want to support, but would operate at the correct speed for a given key size.

[kayabaNerve]

While not really related to the original issue, but related to the above comment, I actively use UintRef to solely operate on the relevant portion of a container and hope to see that as the future for optimizing around partial numbers/ as a common core for containers.

Re: the actual issue, multiple generics works on paper, but a UintRef around a heapless::Vec or around a hybrid_array::Array<Limb, _> sounds like the proper solution to me, without maintenance burden to crypto-bigint.

Apologies for the late comment on the matter. I'm just browsing the open issues and really want to endorse UintRef simply for how much sense it makes to me.