-
Notifications
You must be signed in to change notification settings - Fork 44
Expand file tree
/
Copy pathaddmul.asm
More file actions
116 lines (114 loc) · 5.41 KB
/
addmul.asm
File metadata and controls
116 lines (114 loc) · 5.41 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// Arithmetic on little-endian integers represented with 128-bit limbs.
// All integers must be under a given length bound, and are padded with leading zeroes.
// Sets a[0:len] += b[0:len] * val, and returns the carry (a limb of up to 128 bits).
global addmul_bignum:
// stack: len, a_start_loc, b_start_loc, val, retdest
DUP1
// stack: len, len, a_start_loc, b_start_loc, val, retdest
ISZERO
%jumpi(len_zero)
%build_current_general_address_no_offset
PUSH 0
// stack: carry_limb=0, base_addr, i=len, a_cur_loc=a_start_loc, b_cur_loc=b_start_loc, val, retdest
addmul_loop:
// stack: carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP2
DUP6 ADD // base_addr + b_cur_loc
// stack: b_cur_addr, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
MLOAD_GENERAL
// stack: b[cur], carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP7
// stack: val, b[cur], carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
MUL
// stack: val * b[cur], carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP1
// stack: val * b[cur], val * b[cur], carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
%shr_const(128)
// stack: (val * b[cur]) // 2^128, val * b[cur], carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
SWAP1
// stack: val * b[cur], (val * b[cur]) // 2^128, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
%shl_const(128)
%shr_const(128)
// stack: prod_lo = val * b[cur] % 2^128, prod_hi = (val * b[cur]) // 2^128, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP4
DUP7 ADD // base_addr + a_cur_loc
// stack: a_cur_addr, prod_lo, prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
MLOAD_GENERAL
// stack: a[cur], prod_lo, prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP1
// stack: a[cur], a[cur], prod_lo, prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
SWAP2
// stack: prod_lo, a[cur], a[cur], prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
ADD
%shl_const(128)
%shr_const(128)
// stack: prod_lo' = (prod_lo + a[cur]) % 2^128, a[cur], prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP1
// stack: prod_lo', prod_lo', a[cur], prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
SWAP2
// stack: a[cur], prod_lo', prod_lo', prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
GT
// stack: prod_lo_carry_limb = a[cur] > prod_lo', prod_lo', prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
SWAP1
// stack: prod_lo', prod_lo_carry_limb, prod_hi, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
SWAP2
// stack: prod_hi, prod_lo_carry_limb, prod_lo', carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
ADD
// stack: prod_hi' = prod_hi + prod_lo_carry_limb, prod_lo', carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP3
// stack: carry_limb, prod_hi', prod_lo', carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP3
// stack: prod_lo', carry_limb, prod_hi', prod_lo', carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
ADD
%shl_const(128)
%shr_const(128)
// stack: to_write = (prod_lo' + carry_limb) % 2^128, prod_hi', prod_lo', carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
SWAP2
// stack: prod_lo', prod_hi', to_write, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP3
// stack: to_write, prod_lo', prod_hi', to_write, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
LT
// stack: carry_limb_new = to_write < prod_lo', prod_hi', to_write, carry_limb, i, a_cur_loc, b_cur_loc, val, retdest
%stack (vals: 3, c) -> (vals)
// stack: carry_limb_new, prod_hi', to_write, addr, i, a_cur_loc, b_cur_loc, val, retdest
ADD
// stack: carry_limb = carry_limb_new' + prod_hi', to_write, addr, i, a_cur_loc, b_cur_loc, val, retdest
SWAP1
// stack: to_write, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
DUP3
DUP6 ADD // base_addr + a_cur_loc
// stack: a_cur_addr, to_write, carry_limb, addr, i, a_cur_loc, b_cur_loc, val, retdest
%swap_mstore
// stack: carry_limb, base_addr, i, a_cur_loc, b_cur_loc, val, retdest
SWAP2
// stack: i, base_addr, carry_limb, a_cur_loc, b_cur_loc, val, retdest
%decrement
// stack: i-1, base_addr, carry_limb, a_cur_loc, b_cur_loc, val, retdest
SWAP3
// stack: a_cur_loc, base_addr, carry_limb, i-1, b_cur_loc, val, retdest
INCR1
// stack: a_cur_loc+1, base_addr, carry_limb, i-1, b_cur_loc, val, retdest
SWAP4
// stack: b_cur_loc, base_addr, carry_limb, i-1, a_cur_loc+1, val, retdest
INCR1
// stack: b_cur_loc+1, base_addr, carry_limb, i-1, a_cur_loc+1, val, retdest
%stack (b, addr, c, i, a) -> (c, addr, i, a, b)
// stack: carry_limb, base_addr, i-1, a_cur_loc+1, b_cur_loc+1, val, retdest
DUP3
// stack: i-1, carry_limb, base_addr, i-1, a_cur_loc+1, b_cur_loc+1, val, retdest
%jumpi(addmul_loop)
addmul_end:
// stack: carry_limb_new, base_addr, i-1, a_cur_loc+1, b_cur_loc+1, val, retdest
%stack (c, addr, i, a, b, v) -> (c)
// stack: carry_limb_new, retdest
SWAP1
// stack: retdest, carry_limb_new
JUMP
len_zero:
// stack: len, a_start_loc, b_start_loc, val, retdest
%pop4
// stack: retdest
PUSH 0
// stack: carry_limb=0, retdest
SWAP1
JUMP