42 different cases on a match causes a StackOverflowError

Essentially, I want to use dynamic dispatch to return one of 42 different types of PostQuantumTypes as seen below:

fn get_new_alice(algorithm: u8) -> Box<dyn PostQuantumType> {
        assert!(algorithm < ALGORITHM_COUNT);
        match algorithm {
            // 0
            BABYBEAR => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice())
            }
            // 1
            BABYBEAREPHEM => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice())
            }
            // 2
            FIRESABER => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_firesaber::new_alice())
            }
            // ...
            FRODOKEM640AES => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem640aes::new_alice())
            }

            FRODOKEM640SHAKE => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem640shake::new_alice())
            }

            FRODOKEM976AES => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem976aes::new_alice())
            }

            FRODOKEM976SHAKE => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem976shake::new_alice())
            }

            FRODOKEM1344AES => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem1344aes::new_alice())
            }

            FRODOKEM1344SHAKE => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_frodokem1344shake::new_alice())
            }

            KYBER512 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber512::new_alice())
            }

            KYBER768 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber768::new_alice())
            }

            KYBER1024 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber1024::new_alice())
            }

            KYBER51290S => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber51290s::new_alice())
            }

            KYBER76890S => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber76890s::new_alice())
            }

            KYBER102490S => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_kyber102490s::new_alice())
            }

            LEDAKEMLT12 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ledakemlt12::new_alice())
            }

            LEDAKEMLT32 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ledakemlt32::new_alice())
            }

            LEDAKEMLT52 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ledakemlt52::new_alice())
            }

            LIGHTSABER => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_lightsaber::new_alice())
            }

            MAMABEAR => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mamabear::new_alice())
            }

            MAMABEAREPHEM => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mamabearephem::new_alice())
            }

            MCELIECE348864 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece348864::new_alice())
            }

            MCELIECE348864F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece348864f::new_alice())
            }

            MCELIECE460896 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece460896::new_alice())
            }

            MCELIECE460896F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece460896f::new_alice())
            }

            MCELIECE6688128 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece6688128::new_alice())
            }

            MCELIECE6688128F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece6688128f::new_alice())
            }

            MCELIECE6960119 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece6960119::new_alice())
            }

            MCELIECE6960119F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece6960119f::new_alice())
            }

            MCELIECE8192128 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece8192128::new_alice())
            }

            MCELIECE8192128F => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_mceliece8192128f::new_alice())
            }

            NEWHOPE512CCA => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_newhope512cca::new_alice())
            }

            NEWHOPE512CPA => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_newhope512cpa::new_alice())
            }

            NEWHOPE1024CCA => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_newhope1024cca::new_alice())
            }

            NEWHOPE1024CPA => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_newhope1024cpa::new_alice())
            }

            NTRUHPS2048509 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ntruhps2048509::new_alice())
            }

            NTRUHPS2048677 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ntruhps2048677::new_alice())
            }

            NTRUHPS4096821 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ntruhps4096821::new_alice())
            }

            NTRUHRSS701 => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_ntruhrss701::new_alice())
            }

            PAPABEAR => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_papabear::new_alice())
            }

            PAPABEAREPHEM => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_papabearephem::new_alice())
            }

            SABER => {
                Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_saber::new_alice())
            }

            _ => {
                unreachable!()
            }
        }

However, when there are this many cases, it causes a StackOverflowError. What would be a better way of mapping byte-sized values to the corresponding constructor?

This works, but is undesirable:

        std::thread::Builder::new()
            .stack_size(16*1024*1024)
            .spawn(run)
            .unwrap()
            .join()
            .unwrap();

Note that when creating a box, the boxed value is first created on the stack, then moved into the box. Could one of the kinds being super large (e.g. containing a large array) by any chance be the problem?

If the issue really is the match itself, you can create a top-level function that isn't generic for each case, make an array of function pointers, then index into that and call the corresponding function.

1 Like

Yeah, there are some types with a fixed array size (e.g., [u8; size])

I think so, it makes sense from the debugging

This would work well. Good thinking! I'll give it a shot and see what happens.

You may want to consider using vec_utils::UninitBox to create the boxes of types with large arrays, as it's much better at allowing the optimizer to create the box directly in the heap allocation as opposed to moving it after creating it on the stack.

I think I'm not expressing the idea correctly in this language. How might the correct implementation look?

pub(crate) mod function_pointers {
    use crate::PostQuantumType;
    use crate::algorithm_dictionary::ALGORITHM_COUNT;

    pub static ALICE_FP: [fn() -> dyn PostQuantumType; ALGORITHM_COUNT as usize] = [
        crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice,
        crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice,
        // ...
    ];
}

Sorry, the constructors don't return dyn PostQuantumType ­— they return the concrete instance. There's a difference between a trait object and a concrete instance. You also need them to wrap them in a box, so you need something like this:

fn box_babybear() -> Box<dyn PostQuantumType> {
    Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice())
}
fn box_babybearephem() -> Box<dyn PostQuantumType> {
    Box::new(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice())
}
// ...

Then create an array to these functions. You may find this macro interesting:

macro_rules! box_fn {
    ($constructor:expr) => {{
        fn my_box_fn() -> Box<dyn PostQuantumType> {
            Box::new($constructor)
        }
        
        my_box_fn
    }};
}
static CONSTRUCTORS: [fn() -> Box<dyn PostQuantumType>; ALGORITHM_COUNT] = [
    box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice()),
    box_fn!(...),
    box_fn!(...),
];

playground

1 Like

I'd suggest also adding #[inline(never)] on these functions.

1 Like

This is what I have now:

pub(crate) mod function_pointers {
    use crate::PostQuantumType;
    use crate::algorithm_dictionary::ALGORITHM_COUNT;

    macro_rules! box_fn {
    ($constructor:expr) => {{
        fn my_box_fn() -> Box<dyn PostQuantumType> {
            Box::new($constructor)
        }

        my_box_fn
    }};
}

    pub(crate) static ALICE_FP: [fn() -> Box<dyn PostQuantumType>; 2] = [
        box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice),
        box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice)
    ];

    pub(crate) static BOB_FP: [fn(&[u8]) -> Box<dyn PostQuantumType>; 2] = [
        box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_bob),
        box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_bob)
    ];

}

(I set the array len to 2 for sake of debugging process)

I get this error now:

error[E0308]: mismatched types
   --> ez_pqcrypto\src\lib.rs:259:9
    |
259 |         my_box_fn
    |         ^^^^^^^^^ incorrect number of function parameters
...
269 |         box_fn!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_bob),
    |         -------------------------------------------------------------------------------- in this macro invocation
    |
    = note: expected fn pointer `for<'r> fn(&'r [u8]) -> std::boxed::Box<_>`
                  found fn item `fn() -> std::boxed::Box<_> {function_pointers::BOB_FP::my_box_fn}`


You will need a separate macro for the bob case.

1 Like

Okay, I tried this:

    macro_rules! box_alice {
        ($constructor:expr) => {{
            fn alice_box_fn() -> Box<dyn PostQuantumType> {
                Box::new($constructor)
            }

            alice_box_fn
        }};
    }

    macro_rules! box_bob {
        ($constructor:expr) => {{
            fn bob_box_fn() -> Box<dyn PostQuantumType> {
                Box::new($constructor)
            }

            bob_box_fn
        }};
    }

    pub(crate) static ALICE_FP: [fn() -> Box<dyn PostQuantumType>; 2] = [
        box_alice!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_alice),
        box_alice!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_alice)
    ];

    pub(crate) static BOB_FP: [fn(&[u8]) -> Box<dyn PostQuantumType>; 2] = [
        box_bob!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_bob),
        box_bob!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybearephem::new_bob)
    ];

Getting closer. This error is now the barrier:

error[E0308]: mismatched types
   --> ez_pqcrypto\src\lib.rs:269:13
    |
269 |             bob_box_fn
    |             ^^^^^^^^^^ incorrect number of function parameters
...
279 |         box_bob!(crate::post_quantum_structs::PostQuantumAlgorithmData_babybear::new_bob),
    |         --------------------------------------------------------------------------------- in this macro invocation
    |
    = note: expected fn pointer `for<'r> fn(&'r [u8]) -> std::boxed::Box<_>`
                  found fn item `fn() -> std::boxed::Box<_> {function_pointers::BOB_FP::bob_box_fn}`

You probably want this:

macro_rules! box_alice {
    ($constructor:expr) => {{
        #[inline(never)]
        fn alice_box_fn() -> Box<dyn PostQuantumType> {
            Box::new(($constructor)())
        }

        alice_box_fn
    }};
}

macro_rules! box_bob {
    ($constructor:expr) => {{
        #[inline(never)]
        fn bob_box_fn(arr: &[u8]) -> Box<dyn PostQuantumType> {
            Box::new(($constructor)(arr))
        }

        bob_box_fn
    }};
}
1 Like

You did it! Thank you :slight_smile:

1 Like