use a jump table for computing powers of two

ifenjika · Dec 16, 2021 · ba8539f · ba8539f
1 parent 2616119
commit ba8539f
Show file tree

Hide file tree

Showing 3 changed files with 147 additions and 6 deletions.
diff --git a/warp/cairo-src/evm/bit_packing.cairo b/warp/cairo-src/evm/bit_packing.cairo
@@ -3,13 +3,15 @@ from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
 from starkware.cairo.common.math import assert_lt, unsigned_div_rem
 from starkware.cairo.common.pow import pow
 
+from evm.pow2 import pow2
+
 const UINT128_BOUND = 2 ** 128
 
 func extract_unaligned_uint128{range_check_ptr, bitwise_ptr : BitwiseBuiltin*}(
         shift, low, high) -> (value):
     # Given two aligned uint128's, extract an unaligned uint128,
     # shifted by 'shift' bytes from the 'high' high end.
-    let (p) = pow(256, 16 - shift)
+    let (p) = pow2(128 - 8 * shift)
     let (low_mask) = bitwise_not(p - 1)
     let (low_part) = bitwise_and(low, low_mask)
     let (high_part) = bitwise_and(high, p - 1)
@@ -64,8 +66,8 @@ func split_on_byte{range_check_ptr}(value, byte_pos) -> (low, high):
     return (low=r, high=q)
 end
 
-func exp_byte{range_check_ptr}(d) -> (res):
-    return pow(256, d)
+func exp_byte(d) -> (res):
+    return pow2(8 * d)
 end
 
 func extract_byte{range_check_ptr}(x, pos) -> (low, byte, high):
@@ -77,7 +79,7 @@ func extract_byte{range_check_ptr}(x, pos) -> (low, byte, high):
     return (low, byte, high)
 end
 
-func put_byte{range_check_ptr}(pos, low, byte, high) -> (x):
+func put_byte(pos, low, byte, high) -> (x):
     let (d) = exp_byte(pos)
     return ((high * 256 + byte) * d + low)
 end
diff --git a/warp/cairo-src/evm/pow2.cairo b/warp/cairo-src/evm/pow2.cairo
@@ -0,0 +1,137 @@
+from starkware.cairo.common.registers import get_label_location
+
+func pow2(i) -> (res):
+    let (data_address) = get_label_location(data)
+    return ([data_address + i])
+
+    data:
+    dw 1
+    dw 2
+    dw 4
+    dw 8
+    dw 16
+    dw 32
+    dw 64
+    dw 128
+    dw 256
+    dw 512
+    dw 1024
+    dw 2048
+    dw 4096
+    dw 8192
+    dw 16384
+    dw 32768
+    dw 65536
+    dw 131072
+    dw 262144
+    dw 524288
+    dw 1048576
+    dw 2097152
+    dw 4194304
+    dw 8388608
+    dw 16777216
+    dw 33554432
+    dw 67108864
+    dw 134217728
+    dw 268435456
+    dw 536870912
+    dw 1073741824
+    dw 2147483648
+    dw 4294967296
+    dw 8589934592
+    dw 17179869184
+    dw 34359738368
+    dw 68719476736
+    dw 137438953472
+    dw 274877906944
+    dw 549755813888
+    dw 1099511627776
+    dw 2199023255552
+    dw 4398046511104
+    dw 8796093022208
+    dw 17592186044416
+    dw 35184372088832
+    dw 70368744177664
+    dw 140737488355328
+    dw 281474976710656
+    dw 562949953421312
+    dw 1125899906842624
+    dw 2251799813685248
+    dw 4503599627370496
+    dw 9007199254740992
+    dw 18014398509481984
+    dw 36028797018963968
+    dw 72057594037927936
+    dw 144115188075855872
+    dw 288230376151711744
+    dw 576460752303423488
+    dw 1152921504606846976
+    dw 2305843009213693952
+    dw 4611686018427387904
+    dw 9223372036854775808
+    dw 18446744073709551616
+    dw 36893488147419103232
+    dw 73786976294838206464
+    dw 147573952589676412928
+    dw 295147905179352825856
+    dw 590295810358705651712
+    dw 1180591620717411303424
+    dw 2361183241434822606848
+    dw 4722366482869645213696
+    dw 9444732965739290427392
+    dw 18889465931478580854784
+    dw 37778931862957161709568
+    dw 75557863725914323419136
+    dw 151115727451828646838272
+    dw 302231454903657293676544
+    dw 604462909807314587353088
+    dw 1208925819614629174706176
+    dw 2417851639229258349412352
+    dw 4835703278458516698824704
+    dw 9671406556917033397649408
+    dw 19342813113834066795298816
+    dw 38685626227668133590597632
+    dw 77371252455336267181195264
+    dw 154742504910672534362390528
+    dw 309485009821345068724781056
+    dw 618970019642690137449562112
+    dw 1237940039285380274899124224
+    dw 2475880078570760549798248448
+    dw 4951760157141521099596496896
+    dw 9903520314283042199192993792
+    dw 19807040628566084398385987584
+    dw 39614081257132168796771975168
+    dw 79228162514264337593543950336
+    dw 158456325028528675187087900672
+    dw 316912650057057350374175801344
+    dw 633825300114114700748351602688
+    dw 1267650600228229401496703205376
+    dw 2535301200456458802993406410752
+    dw 5070602400912917605986812821504
+    dw 10141204801825835211973625643008
+    dw 20282409603651670423947251286016
+    dw 40564819207303340847894502572032
+    dw 81129638414606681695789005144064
+    dw 162259276829213363391578010288128
+    dw 324518553658426726783156020576256
+    dw 649037107316853453566312041152512
+    dw 1298074214633706907132624082305024
+    dw 2596148429267413814265248164610048
+    dw 5192296858534827628530496329220096
+    dw 10384593717069655257060992658440192
+    dw 20769187434139310514121985316880384
+    dw 41538374868278621028243970633760768
+    dw 83076749736557242056487941267521536
+    dw 166153499473114484112975882535043072
+    dw 332306998946228968225951765070086144
+    dw 664613997892457936451903530140172288
+    dw 1329227995784915872903807060280344576
+    dw 2658455991569831745807614120560689152
+    dw 5316911983139663491615228241121378304
+    dw 10633823966279326983230456482242756608
+    dw 21267647932558653966460912964485513216
+    dw 42535295865117307932921825928971026432
+    dw 85070591730234615865843651857942052864
+    dw 170141183460469231731687303715884105728
+    dw 340282366920938463463374607431768211456
+end
diff --git a/warp/cairo-src/evm/uint256.cairo b/warp/cairo-src/evm/uint256.cairo
@@ -7,6 +7,8 @@ from starkware.cairo.common.uint256 import (
     Uint256, uint256_add, uint256_cond_neg, uint256_eq, uint256_lt, uint256_mul, uint256_pow2,
     uint256_shl, uint256_signed_div_rem, uint256_signed_lt, uint256_sub, uint256_unsigned_div_rem)
 
+from evm.pow2 import pow2
+
 const UINT128_BOUND = 2 ** 128
 
 func u256_add{range_check_ptr}(x : Uint256, y : Uint256) -> (result : Uint256):
@@ -44,7 +46,7 @@ func u256_shr{range_check_ptr, bitwise_ptr : BitwiseBuiltin*}(i : Uint256, a : U
         #    = (h & (p-1)) * 2^128 / p + (l&~(p-1)) / p
         #    = (h & (p-1) * 2^128 + l&~(p-1)) / p
         # h' = h >> i = (h - h&(p-1)) / p
-        let (p) = pow(2, i.low)
+        let (p) = pow2(i.low)
         let (low_mask) = bitwise_not(p - 1)
         let (low_part) = bitwise_and(a.low, low_mask)
         let (high_part) = bitwise_and(a.high, p - 1)
@@ -53,7 +55,7 @@ func u256_shr{range_check_ptr, bitwise_ptr : BitwiseBuiltin*}(i : Uint256, a : U
     end
     let (le_255) = is_le(i.low, 255)
     if le_255 == 1:
-        let (p) = pow(2, i.low - 128)
+        let (p) = pow2(i.low - 128)
         let (mask) = bitwise_not(p - 1)
         let (res) = bitwise_and(a.high, mask)
         return (Uint256(res / p, 0))