Use wrapping_shr in reverse_index_bits_in_place_small

[vivekvpandya]

This get triggered when running plonky2 in wasm32-wasi target.

[dlubarov]

Hm, my understanding is a shift should panic only if debug assertions are enabled (as Robin mentioned) and the shift amount exceeds the size of the integer type, here usize.

Here n_power should be <= 6 so the shift amount should also be <= 6 so I can't think of why this would trigger. Do you have the stack trace handy?

[vivekvpandya]

Hm, my understanding is a shift should panic only if debug assertions are enabled (as Robin mentioned) and the shift amount exceeds the size of the integer type, here usize.

Here n_power should be <= 6 so the shift amount should also be <= 6 so I can't think of why this would trigger. Do you have the stack trace handy?

thread 'main' panicked at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/util/src/lib.rs:128:26:
attempt to shift right with overflow
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Error: failed to run main module `../target/wasm32-wasi/debug/demo.wasm`
Caused by:
    0: failed to invoke command default
    1: error while executing at wasm backtrace:
           0: 0x16817a - panic_abort::__rust_start_panic::abort::h7e5f56383e5819e3
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/panic_abort/src/lib.rs:96:17              - __rust_start_panic
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/panic_abort/src/lib.rs:38:5              - rust_panic
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:831:25
           1: 0x1680c7 - std::panicking::rust_panic_with_hook::hdf66bc2f41fd5166
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:801:5
           2: 0x166ec4 - std::panicking::begin_panic_handler::{{closure}}::h8bd2da1b57ff8909
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:649:13
           3: 0x166e2a - std::sys_common::backtrace::__rust_end_short_backtrace::h4a1d4fa30b25df94
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/sys_common/backtrace.rs:171:18
           4: 0x167ad6 - rust_begin_unwind
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:645:5
           5: 0x9267 - core::panicking::panic_fmt::h919872f6efaee18c
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/panicking.rs:72:14
           6: 0x6a0f - core::panicking::panic::hcdbcff129c6a1e40
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/panicking.rs:144:5
           7: 0x383b8 - plonky2_util::reverse_index_bits_in_place_small::h569ac8c80c4d65f2
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/util/src/lib.rs:128:26              - plonky2_util::reverse_index_bits_in_place::hf0d5b3c3086d43b9
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/util/src/lib.rs:191:13
           8: 0xed8f6 - plonky2_field::fft::fft_classic::h4d45851f19dbc28b
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/field/src/fft.rs:170:5
           9: 0xefd61 - plonky2_field::fft::fft_dispatch::h6e60a467b6abc9c9
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/field/src/fft.rs:48:5              - plonky2_field::fft::ifft_with_options::h09c6f8abe78d5779
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/field/src/fft.rs:82:5
          10: 0xb589b - plonky2_field::fft::ifft::h8ed37c276c8d21e6
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/field/src/fft.rs:69:5              - plonky2_field::polynomial::PolynomialValues<F>::ifft::h6e040a4c1fac48a2
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/field/src/polynomial/mod.rs:59:9              - plonky2::fri::oracle::PolynomialBatch<F,C,_>::from_values::{{closure}}::hc55194f082157538
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/plonky2/src/fri/oracle.rs:68:46              - core::ops::function::impls::<impl core::ops::function::FnMut<A> for &F>::call_mut::h16d26ad46affd808
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/ops/function.rs:272:13              - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &mut F>::call_once::h3f929a8c30226b29
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/ops/function.rs:305:13              - core::option::Option<T>::map::hfc29c9aee87449a5
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/option.rs:1072:29              - <core::iter::adapters::map::Map<I,F> as core::iter::traits::iterator::Iterator>::next::h7fe590a6a56574aa
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/iter/adapters/map.rs:104:26              - rayon::iter::plumbing::Folder::consume_iter::h1991e62f59310962
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/plumbing/mod.rs:178:21
          11: 0x20f09 - <rayon::iter::map::MapFolder<C,F> as rayon::iter::plumbing::Folder<T>>::consume_iter::h5ba1030fedd68df5
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/map.rs:248:21              - rayon::iter::plumbing::Producer::fold_with::h8d0423210c6c1625
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/plumbing/mod.rs:110:9              - rayon::iter::plumbing::bridge_producer_consumer::helper::he5697d8657a46f83
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/plumbing/mod.rs:438:13
          12: 0x866f6 - rayon::iter::plumbing::bridge_producer_consumer::helper::{{closure}}::heee6db58d11e9c7e
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/plumbing/mod.rs:418:21              - rayon_core::join::join_context::call_a::{{closure}}::h179b02a593e9573a
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.0/src/join/mod.rs:124:17              - <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once::h510279509437bc63
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/panic/unwind_safe.rs:272:9              - std::panicking::try::do_call::hbb7f61e1923255ed
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:552:40              - std::panicking::try::h10242cfb9cbb5cf6
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:516:19              - std::panic::catch_unwind::h67b3bc45d9e779cf
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panic.rs:142:14              - rayon_core::unwind::halt_unwinding::h8a6b1e813c61e0bf
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.0/src/unwind.rs:17:5              - rayon_core::join::join_context::{{closure}}::hea5da6f22b0b8228
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.0/src/join/mod.rs:142:24
          13: 0x20dd3 - rayon_core::registry::in_worker::h39d5e28468f90566
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.0/src/registry.rs:950:13              - rayon_core::join::join_context::h8b0e74165c926923
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-core-1.12.0/src/join/mod.rs:132:5              - rayon::iter::plumbing::bridge_producer_consumer::helper::he5697d8657a46f83
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/plumbing/mod.rs:416:47
          14: 0x26aaa - rayon::iter::plumbing::bridge_producer_consumer::hddca0b326808caa9
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/plumbing/mod.rs:397:12              - <rayon::iter::plumbing::bridge::Callback<C> as rayon::iter::plumbing::ProducerCallback<I>>::callback::h53c35f33618b4cc3
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/plumbing/mod.rs:373:13              - <rayon::vec::Drain<T> as rayon::iter::IndexedParallelIterator>::with_producer::hbc31c224d4844dbc
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/vec.rs:147:13              - <rayon::vec::IntoIter<T> as rayon::iter::IndexedParallelIterator>::with_producer::hefb69ef66aebf2c1
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/vec.rs:83:9
          15: 0x4dc22 - rayon::iter::plumbing::bridge::he6307596035befcc
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/plumbing/mod.rs:357:12              - <rayon::vec::IntoIter<T> as rayon::iter::ParallelIterator>::drive_unindexed::h5469c6aa5ec28890
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/vec.rs:58:9              - <rayon::iter::map::Map<I,F> as rayon::iter::ParallelIterator>::drive_unindexed::hb0e010fc70c39fb8
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/map.rs:49:9              - rayon::iter::collect::special_extend::{{closure}}::ha0ef2a69f9978f24
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/collect/mod.rs:39:46              - rayon::iter::collect::collect_with_consumer::h979c7d63bf2209a5
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/collect/mod.rs:84:18
          16: 0x4531d - rayon::iter::collect::special_extend::hbd0a2e32a0efbb8c
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/collect/mod.rs:39:5              - rayon::iter::extend::<impl rayon::iter::ParallelExtend<T> for alloc::vec::Vec<T>>::par_extend::hf7de5ff871e3669e
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/extend.rs:582:17              - rayon::iter::from_par_iter::collect_extended::h87bca6afd49707a8
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/from_par_iter.rs:19:5              - rayon::iter::from_par_iter::<impl rayon::iter::FromParallelIterator<T> for alloc::vec::Vec<T>>::from_par_iter::h4fe46a1b24f0fb4b
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/from_par_iter.rs:32:9              - rayon::iter::ParallelIterator::collect::ha85977af11f1c887
                           at /Users/jakub/.cargo/registry/src/index.crates.io-6f17d22bba15001f/rayon-1.8.0/src/iter/mod.rs:2056:9              - plonky2::fri::oracle::PolynomialBatch<F,C,_>::from_values::h10a5676c87e5f859
                           at /Users/jakub/.cargo/git/checkouts/plonky2-fb94951b5f6820ea/70d88e2/plonky2/src/fri/oracle.rs:68:54              - mozak_circuits::stark::prover::prove_with_traces::{{closure}}::h87cadad5a25295cc
                           at /Users/jakub/Developer/mozak-vm/circuits/src/stark/prover.rs:96:21              - core::ops::try_trait::NeverShortCircuit<T>::wrap_mut_1::{{closure}}::he01d44738437a56b
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/ops/try_trait.rs:385:36              - <core::iter::adapters::map::Map<I,F> as core::iter::traits::unchecked_iterator::UncheckedIterator>::next_unchecked::hd066db96ce0800fb
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/iter/adapters/map.rs:203:9
          17: 0xfe827 - core::array::try_from_trusted_iterator::next::{{closure}}::hff9ce2f232f8dadd
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/array/mod.rs:791:22              - core::array::try_from_fn_erased::h96a6cd7c64f74b99
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/array/mod.rs:822:20              - core::array::try_from_fn::h0f4dc7e0ad89ead2
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/array/mod.rs:104:11              - core::array::try_from_trusted_iterator::h7c85d1049dfcabbd
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/array/mod.rs:795:5              - core::array::<impl [T; N]>::try_map::{{closure}}::hc93e1c151ebc3147
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/array/mod.rs:538:39              - core::array::drain::drain_array_with::hf82127843824e71c
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/array/drain.rs:26:5
          18: 0xc543b - core::array::<impl [T; N]>::try_map::h1140916594d6c83b
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/array/mod.rs:538:9              - core::array::<impl [T; N]>::map::h11d09479ee65573f
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/array/mod.rs:501:14              - mozak_circuits::stark::mozak_stark::TableKindArray<T>::map::h385460b62e4a2ce8
                           at /Users/jakub/Developer/mozak-vm/circuits/src/stark/mozak_stark.rs:297:24              - mozak_circuits::stark::prover::prove_with_traces::h60a92882b1ad8f95
                           at /Users/jakub/Developer/mozak-vm/circuits/src/stark/prover.rs:89:9              - mozak_circuits::stark::prover::prove::hc0b3ba2c814132d8
                           at /Users/jakub/Developer/mozak-vm/circuits/src/stark/prover.rs:60:5
          19: 0x3f409 - mozak_circuits::test_utils::prove_and_verify_mozak_stark::ha3cb4c66c4988304
                           at /Users/jakub/Developer/mozak-vm/circuits/src/test_utils.rs:376:21
          20: 0x178e08 - wasm_demo::wasm_demo_::ha96a28517ec09898
                           at /Users/jakub/Developer/mozak-vm/wasm-demo/src/lib.rs:52:23
          21: 0x116d - demo::main::h4aa9d128e8a2cfff
                           at /Users/jakub/Developer/mozak-vm/wasm-demo/src/bin/demo.rs:22:5
          22: 0x1209 - core::ops::function::FnOnce::call_once::hc6be7a860f8e9d93
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/ops/function.rs:250:5              - std::sys_common::backtrace::__rust_begin_short_backtrace::hc64f3c337bb32282
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/sys_common/backtrace.rs:155:18
          23: 0x1218 - std::rt::lang_start::{{closure}}::hd824c9c5b68eaba8
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/rt.rs:166:18
          24: 0x162168 - core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &F>::call_once::h8b19e624a55a96dd
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/core/src/ops/function.rs:284:13              - std::panicking::try::do_call::hb9df9d476f1c4bd8
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:552:40              - std::panicking::try::he3c3da96990f392f
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:516:19              - std::panic::catch_unwind::h657c68ad228b866d
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panic.rs:142:14              - std::rt::lang_start_internal::{{closure}}::hce6f2985691bda20
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/rt.rs:148:48              - std::panicking::try::do_call::h2803462a4e47e4fc
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:552:40              - std::panicking::try::h2db3fcfdeffccd6a
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panicking.rs:516:19              - std::panic::catch_unwind::h5eed09297be7c5d3
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/panic.rs:142:14              - std::rt::lang_start_internal::hf68eb5d4997f2421
                           at /rustc/e51e98dde6a60637b6a71b8105245b629ac3fe77/library/std/src/rt.rs:148:20
          25: 0x11a5 - <unknown>!__main_void
          26: 0x1144 - <unknown>!_start
    2: wasm trap: wasm `unreachable` instruction executed

trace and first one to observe https://github.com/jakzale

[dlubarov]

Thanks, I was looking at the wrong shift, here looks like the shift amount is

let dst_lo_shr_amt = 64 - (lb_n - 6);

Seems it was written with the assumption that usize would be 64 bits, but for wasm it's probably 32? Should we replace 64 with size_of::<usize>() * 8? @nbgl

[Nashtare]

Should we replace 64 with size_of::() * 8?

Don't we have other places where usize is assumed to be 64-bit long? At least on the evm crate it is I believe.

[vivekvpandya]

Thanks, I was looking at the wrong shift, here looks like the shift amount is

let dst_lo_shr_amt = 64 - (lb_n - 6);

Seems it was written with the assumption that usize would be 64 bits, but for wasm it's probably 32? Should we replace 64 with size_of::<usize>() * 8? @nbgl

@Nashtare should we go with this suggestion? what else needs to be done to merge this PR?

[Nashtare]

Yeah I'd rather go with this suggestion instead.

[sonarcloud[bot]]

Quality Gate passed

Kudos, no new issues were introduced!

0 New issues
0 Security Hotspots
No data about Coverage
No data about Duplication

See analysis details on SonarCloud

[vivekvpandya]

@Nashtare kindly review!