dev: optimize bitshifts by using a lookup table for powers of two

[enitrat]

for the powers of two up to 256, we can define a lookup table and use that lookup table to execute bitshift operations, instead of calling the expensive cairo function pow.

• If p <=255, use the lookup table POW_2
• if p>255, fallback on using pow.

Hint: In a generic context, you can get the value 255 of type T by doing BitSize::<u256>::bits() - One::<T>::one() - make sure you're using the right types for that.

kakarot-ssj/crates/utils/src/math.cairo

Lines 195 to 212 in b1f7f8c

	fn shl(self: T, shift: T) -> T {
	// if we shift by more than nb_bits of T, the result is 0
	// we early return to save gas and prevent unexpected behavior
	if shift > BitSize::<T>::bits().try_into().unwrap() - One::one() {
	panic_with_felt252('mul Overflow');
	}
	let two = One::one() + One::one();
	self * two.pow(shift)
	}
	fn shr(self: T, shift: T) -> T {
	// early return to save gas if shift > nb_bits of T
	if shift > BitSize::<T>::bits().try_into().unwrap() - One::one() {
	panic_with_felt252('mul Overflow');
	}
	let two = One::one() + One::one();
	self / two.pow(shift)
	}

kakarot-ssj/crates/utils/src/math.cairo

Lines 242 to 255 in b1f7f8c

	fn wrapping_shl(self: T, shift: T) -> T {
	let two = One::<T>::one() + One::<T>::one();
	let (result, _) = self.overflowing_mul(two.wrapping_pow(shift));
	result
	}
	fn wrapping_shr(self: T, shift: T) -> T {
	let two = One::<T>::one() + One::<T>::one();
	if shift > BitSize::<T>::bits().try_into().unwrap() - One::one() {
	return Zero::zero();
	}
	self / two.pow(shift)
	}

[manlikeHB]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

Hi, I am Cairo dev with lots of experience contributing to Cairo projects, my OD profile is a witness to this. This feat is right within my comfort zone.

I have had experience working on projects were bitshift operations were implemented I can use those as a reference for implementing this.

How I plan on tackling this issue

After implementing this, I will write a robust unit test and ensure all test case are covered and the feat behaves as expected.

[MPSxDev]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

Hello, I am Manuel, a process engineer and web3 developer. I have participated in Starknet Bootcamps, ETHGlobal and am an Elite winner of Speedrunstark. I have a high capacity to solve problems. I am a member of the DojoCoding community.
I hope this issue is assigned to me. I am available to work immediately to achieve what is required in the shortest time possible.

How I plan on tackling this issue

To address the requirements of the issue, I will:

1. Create a lookup table POW_2 containing powers of two up to 256.
2. Implement logic to check if the exponent p is less than or equal to 255:
   • If p <= 255, use the corresponding value from the POW_2 lookup table for optimization.
   • If p > 255, fallback to using the pow function.
3. Ensure that the implementation utilizes the correct types by calculating the value 255 with BitSize::<u256>::bits() - One::<T>::one().
4. Test the new implementation to verify correctness and performance improvements.

[guha-rahul]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

I have been a rust and zk dev before and i have implemented lookup tables for zk cryptography . I think that will help me in this issue

How I plan on tackling this issue

1. Read the codebase
   2.implement the lookup table
2. replace the expensive cairo math with these tables
3. Ask questions if i am stuck anywhere

[augustin-v]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

I am a newcomer in the blockchain dev world, and I'd really like to be given a chance to complete my first OnlyDust contribution. I have experience with Node Guardians's brainfvck VM in Cairo, where I used bitshift operations a lot, as well as the cairo-profiler. Thank you

How I plan on tackling this issue

I would create a look up cable to store powers of two from w0 to 2255 in an array pow_2. Then check the value of p.
And of course communicate if I encounter any problem

[saimeunt]

I am applying to this issue via OnlyDust platform.

My background and how it can be leveraged

I have some experience in Cairo, mostly porting Solidity ERCs to Cairo:
https://github.com/carbonable-labs/cairo-erc-7496
https://github.com/carbonable-labs/cairo-erc-7498

How I plan on tackling this issue

I will carefully implement the required optimization by leveraging a lookup table for powers of 2 <= 255.
I will make sure to follow the hint given to generically obtain the value 255 from any type using bitsize introspection.

[onlydustapp]

The maintainer enitrat has assigned augustin-v to this issue via OnlyDust Platform.
Good luck!