ZKASM Feijoa Features

# ZKASM Feijoa Features ## SAVE, RESTORE Feature to save and restore registers. The registers involved are B, C, D, E, RR, RCX, and RID. Also, the *op* was saved. The op saved is restored as FREE INPUT (\$). The RID register (Restore ID) is an internal register used to save and restore, avoid the use, or modify the RID register. The syntax for SAVE is with registers SAVE(B,C,D,E,RR,RCX), but also you could use SAVE without specifying registers. In the case of RESTORE, it always was without specifying registers. Register A isn't saved because it's usually used as a return value. It's possible to save register A (or others not included) using op: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>A :SAVE(B,C,D,E,RR,RCX)</div><div>; some code</div><div>$ => A :RESTORE</div></div> This feature introduce's a change on RETURN, now RETURN using next value of RR, means it's compatible something like: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; using next value of RR, it's value saved on tmpRR</div><div>$ => RR :RETURN,MLOAD(tmpRR)</div></div> Since Register RR is saved, we don't worry about RR throwing CALLs that use save and restore. We write recursive functions (but we shouldn't use them). An example of a typical factorial recursive function: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>fact: </div><div> :SAVE(B,C,D,E,RR,RCX)</div> <div> ; check if direct case (A == 1)</div><div> 1 => B</div><div> $ :EQ,JMPC(fact_finish)</div> <div> ; store current value of A in C</div><div> A => C</div> <div> ; call again to fact with A - 1</div><div> $ => A :SUB,CALL(fact)</div><div> </div><div> ; A * fact(A - 1)</div><div> C => B</div><div> 0 => D,C</div><div> ${A * B} => A :ARITH</div> <div>fact_finish: </div><div> :RESTORE,RETURN</div></div> SAVE and RESTORE are compatible with JMP, JMPx, CALL, and MSTORE. Also, SAVE is compatible with MLOAD. RESTORE is incompatible with restore registers assignations (dual assignation between restore and left assignation). For example: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div> $ => B :RESTORE ; ERROR: because B it's restored</div><div> ; cannot use B,C,D,E,RR,RCX,RID</div> <div> $ => A :RESTORE ; OK: because A it isn't restored </div><div> ; really it's restored op as freeinput</div> <div> 30 => B</div><div> 10 :SAVE</div><div> 15 => B</div><div> $ + B => A :RESTORE ; OK: B isn't assigned, after RESTORE</div><div> ; A contains value of op when SAVE added</div><div> ; with value of B before restore</div><div> ; after RESTORE A = 25, B = 30</div></div> Each save must be restored precisely once. At the end of the program, all saves without restoration must be cleaned because if not, **proof generation fails**. You would have non-restored saves, for example, if you use jmp (OOC) or similar.For this reason, this code must be called near the end of the program. <div style="color: #3b3b3b;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>VAR GLOBAL lastRID</div> <div>clearPedingRestores:</div><div> :SAVE(B,C,D,E,RR,RCX)</div><div> RID :MSTORE(lastRID)</div> <div>clearPedingRestores_loop:</div><div> ${getPendingRID(mem.lastRID)} => RID :JMPN(clearPedingRestores_end)</div><div> :RESTORE, JMP(clearPedingRestores_loop)</div> <div>clearPedingRestores_end:</div><div> $ => RID :MLOAD(lastRID)</div><div> :RESTORE</div> <div> 0 => RID</div></div> ## Assume Free Input When we use an operation with "single" FREE INPUT (\$), the executor fills the value because it knows how to calculate it. Still, after validating this non-trust calculation, use the op, not the FREE INPUT. This behavior doesn't make much sense, especially regarding memory operation. With the internal assumeFree flag, we indicate to the processor that it has to verify the FREE INPUT, not the op. This behavior could be used with memory-style instructions like MLOAD and HASHx. In assembly, to indicate it, we use the prefix F_ on instructions, like F_MLOAD, F_HASHP, etc. For example: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; increment value of B with contents of var1</div> <div>; using MLOAD (worse case) - 4 steps</div><div>C :MSTORE(tmpC)</div><div>$ => C :MLOAD(var1)</div><div>B + C => B </div><div>$ => C :MLOAD(tmpC)</div> <div>; using F_MLOAD - 1 step</div><div>$ + B => B :F_MLOAD(var1)</div></div> We could use assumeFree with HASH, for example: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; increment value of B with contents of HASHP</div> <div>; using HASHP1 (worse case)</div><div>C :MSTORE(tmpC)</div><div>$ => C :HASHP1(E)</div><div>B + C => B </div><div>$ => C :MLOAD(tmpC)</div> <div>; using F_HASHP1</div><div>$ + B => B :F_HASHP1(E)</div> </div> With this feature, sense introduces a sugar syntax for memory access, using the name of a variable without F_MLOAD or MSTORE. For example: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; equivalent lines</div><div>$ + B => B :F_MLOAD(var1)</div><div>var1 + B => B</div> <div>; equivalent lines (MSTORE because storing op)</div><div>C + 2 :MSTORE(var1)</div><div>C + 2 => var1</div> <div>; ERROR: two memory access</div><div>var2 + 2 => var1</div></div> To access arrays it's better to use [] syntax. For example: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; equivalent lines</div><div>$ + B => B :F_MLOAD(var1+2*E+5)</div><div>$ + B => B :F_MLOAD(var1[2*E+5])</div><div>var1[2*E+5] + B => B</div> <div>; equivalent lines</div><div>C + 2 :MSTORE(var1+3*RR)</div><div>C + 2 :MSTORE(var1[3*RR])</div><div>C + 2 => var1[3*RR]</div></div> With this feature, has sense reorganizes the use of addrRel (the relative/dynamic part of address calculated on runtime using E and RR registers). One address has two parts: a static part and a dynamic/relative part. The idea is that each instruction/part (mload/mstore, jmpAddr, elseAddr) has its static part and a flag indicating if use dynamic/relative part. If two instructions/parts have the same relative part, they could share it. Also, change flags ind and indE, now they are multipliers (as described in pil). For example: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>B :JMPNZ(@label+2*RR)</div><div>B :JMPNZ(@label+RR)</div><div>B :JMPZ(labelZ, @labelNZ+E) </div><div>B :JMPZ(@labelZ+2*E, @labelNZ+2*E) ; OK: addrRel is the same 2*E</div><div>B :JMPZ(@labelZ+2*E, @labelNZ+E) ; ERROR: addrRel isn't the same 2*E vs E</div><div>B :JMPZ(@labelZ+E, @labelNZ+RR) ; ERROR: addrRel isn't the same E vs RR</div> <div>; VALID options</div><div>$ :HASHP(E), MLOAD(data)</div><div>$ :HASHP(E-2), MSTORE(data)</div><div>$ :HASHP(E), MLOAD(data), JMPZ(@label + RR, labelElse)</div> <div>; addrRel=3*RR-2*E, offset=data+5, jmpAddr=@lIFZ+2 elseAddr=@lELSE</div><div>$ :HASHP(E+5), MLOAD(data[3*RR-2*E+5]), JMPZ(@lIFZ+3*RR-2*E+2,@lELSE+3*RR-2*E)</div> <div>$ => B :MLOAD(matriz_20x30[E*30 + RR])</div></div> In hash operations, a dynamic address is usually used. To allow using hash with these indirections, define that the hash address always uses E with an offset that could be zero. This means that now, we can't use RR or only constant for the hash address. Some examples: <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>$ => A :HASHK32(E) ;OK</div><div>$ => A :HASHPDIGEST(E+3) ;OK</div> <div>$ => A :HASHK32(0) ;ERROR: Always use E0</div> <div>$ => A :HASHPDIGEST(E+3),MSTORE(values[RR]) ;OK</div><div>$ => A :HASHPDIGEST(E+3),MSTORE(values[E]) ;OK</div> <div>; addrRel=3*E, addr=values+3*E, hashAddr= E0+3</div><div>$ => A :HASHPDIGEST(E+3),MSTORE(values[3*E]);OK</div></div> The difference between instruction CALL and JMP is that CALL stores zkPC + 1 in register RR, but the rest is the same. This version introduces the conditional calls to avoid the parts of ROM that appear legacy code that sets RR with zkPC. With conditional calls, always set register RR, independent of condition. Some examples: <div style="color: #3b3b3b;margin-bottom: 10px;background-color: #f8f8f8;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; CALL if OP0 is zero</div><div>B :CALL_Z(@label+RR)</div><div>B :CALL_NZ(label)</div><div>C :CALL_Z(label, labelElse)</div> <div>; CALL if carry</div><div>$ :EQ,CALL_C(label)</div><div>$ :EQ,CALL_NC(label)</div><div>$ :EQ,CALL_C(@label+RR, labelElse)</div> <div>; CALL if OP0 is 32 bit negative </div><div>B :CALL_N(label)</div><div>B :CALL_N(@label+RR, labelElse)</div> </div> ## HASH bytes With this feature, there are two possibilities for specifying hash bytes: dynamically with the D0 register and statically with instruction. To use statically, you must call HASHXn, where n is the number of bytes (1-32). If you call HASHX without n, use the D0 register as the number of bytes. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; hash 3 bytes of A</div><div>3 => D</div><div>A :HASHK(E)</div> <div>; hash 1 byte of A</div><div>A :HASHK1(E)</div> <div>; hash 3 bytes of A</div><div>A :HASHK3(E)</div> <div>; with hash-bytes also continue using dynamic number of bytes</div><div>4 => D</div><div>A :HASHK(E)</div> <div>; hash 32 bytes of A</div><div>$ => A :HASHK32(E) </div> </div> ## ASSERT Byte Free Input This feature guarantees (assert) that FREE0 is a valid byte; if FREE0 has a nonvalid byte, the proof cannot be generated. For this reason, we must be sure that the value calculated in FREE input has a byte value (0-255). The use is different than $0 because it does not check the free input; it only loads to op the FREE0, which is limited to a field element (less than 64 bits). FreeByte is similar to JMPN; you must be sure that the value is a valid 32-bit value. FreeByte avoids MAP (malicious prover), returning a bigger value. Some examples: <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; a MAP only could return a value from 0 to 255</div><div>; using to rebuild byte to byte for example</div><div>$BYTE{A & 0xFF} + C * 256 => C</div> <div>; using to limited jmp tables</div><div>${A & 0xFF} => RR :JMPN(assertFails)</div><div>255 - RR :JMPN(assertFails)</div><div>$ => C :JMP(table+RR),MLOAD(somethingToLoad)</div> <div>; using to limited jmp tables</div><div>$BYTE{A & 0xFF} => RR</div><div>$ => C :JMP(table+RR),MLOAD(somethingToLoad)</div></div> FreeByte is incompatible with JMPN, because use same flags. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>$BYTE{A & 0xFF} => RR :JMPZ(isZero) ;OK, it isn't JMPN</div> <div>$BYTE{A & 0xFF} => RR :JMPN(isZero) ;ERROR: use JMPN and FreeByte</div><div> ;no sense, RR must be 0-255, JMPN never jumps.</div> <div>$BYTE{A & 0xFF} - 3 => RR :JMPN(isZero) ;ERROR: use JMPN and FreeByte</div></div> ## MEM_ALIGN with variable length One previous limitation of MEM_ALIGN was that it only worked with 32-byte values, and it wasn't useful to read bytes over 256-bit memory. For this reason, modify MEM_ALIGN to allow specifying the number of bytes. With this new PIL2 design compatible with PIL1, we could add free extra features, and the final solution is eight (8) columns cheaper than the precedent. These extra features are alignment (left, right) and endian (little, big). To be compatible with the current ROM code by default right-alignment and big-endian. To avoid using more registers, all these parameters are coded in a mode; for compatibility, use C0 to specify this mode. The formula for this mode is: ``` mode = offset_bytes (0-64) + 128 * length (0-32, 0 for compatibility is equivalent to 32) + 8192 * left_alignment (0-1) + 16384 * little_endian (0-1) ``` At this point, it's better to review the features of mem_align. To read from memory, we need to read two consecutive addresses (M0, M1) and store them on registers A and B, respectively. Use C to store mode and OP to obtain bytes read. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; MEM_ALIGN_RD</div><div>; </div><div>; <───────────── 32 bytes ───────────> <───────────── 32 bytes ───────────></div><div>; ┌────────────────────────────────────┬────────────────────────────────────┐</div><div>; M0 (A) │ M0(A) ┆ │ M1 (B)┆ │</div><div>; └────────────────────────────────────┴────────────────────────────────────┘</div><div>; │ │ │ │ │ │ │ </div><div>; ▼ ▼ ▼ ▼ ▼ ▼ ▼ </div><div>; <── offset(bytes) ──>┌───────────────────────┐ </div><div>; │V(OP) │ </div><div>; └───────────────────────┘ </div><div>; <─── length (bytes) ──></div></div> Another parameter of mem_align is its alignment, which defines how bytes read are stored inside the 32-byte register. If the length is 32, the left and right alignments are the same. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>;</div><div>; <───────────── 32 bytes ───────────></div><div>; ┌────────────┬───────────────────────┐</div><div>; RIGHT ALIGNMENT │ 000...000 │ V(OP) │</div><div>; (default) └────────────┴───────────────────────┘</div><div>; <─── length (bytes) ──></div><div>;</div><div>; <───────────── 32 bytes ───────────></div><div>; ┌───────── ─────────────┬───────────┐</div><div>; LEFT ALIGNMENT │ V(OP) │ 000...000 │</div><div>; └───────────────────────┴───────────┘</div><div>; <─── length (bytes) ──></div><div>;</div></div> The last parameter of mem_align is its endian type, which defines how the ordered bytes are read. Big endian takes bytes as they are in memory, while little endian reverses them. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>;</div><div>; <───────────── 32 bytes ───────────> <───────────── 32 bytes ───────────></div><div>; ┌────────────────────────────────────┬────────────────────────────────────┐</div><div>; M0 (A) │ M0(A) A2 A1 A0 │ B31 B30 M1(B) │</div><div>; └────────────────────────────────────┴────────────────────────────────────┘</div><div>; │ │ │ │ │ </div><div>; ▼ ▼ ▼ ▼ ▼ </div><div>; ┌────────────────────────┐ </div><div>; BIG ENDIAN V(OP)| A2 A1 A0 B31 B30 │ </div><div>; (default) └────────────────────────┘ </div><div>;</div><div>; ┌────────────────────────┐ </div><div>; LITTLE ENDIAN V(OP)| B30 B31 A0 A1 A2 A3 │ </div><div>; └────────────────────────┘ </div> </div> Finally, operation MEM_ALIGN_WR, in this case, verifies D as W0 and E as W1, indicating how memory M0 and M1 were modified after "writing" n bytes of OP with offset. The extra parameters alignment and endian define how to take this byte from V (OP). <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; <───────────── 32 bytes ───────────> <───────────── 32 bytes ───────────></div><div>; ┌────────────────────────────────────┬────────────────────────────────────┐</div><div>; │ M0(A) │ M1 (B) │</div><div>; └────────────────────────────────────┴────────────────────────────────────┘</div><div>; │ │ │ │ │ │ │ │ │ </div><div>; │ │ │ │ <─── length (bytes) ──> │ │ │ │ │ </div><div>; <── offset(bytes) ──>┌───────────────────────┐ │ │ │ │ │ </div><div>; │ │ │ │ │V(OP) │ │ │ │ │ │ </div><div>; │ │ │ │ └───────────────────────┘ │ │ │ │ │ </div><div>; │ │ │ │ │ │ │ │ │ │ │ │ │ </div><div>; ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼ </div><div>; ┌────────────────────────────────────┬────────────────────────────────────┐</div><div>; │ W0(D) ┆ │ W1 (E) ┆ │</div><div>; └────────────────────────────────────┴────────────────────────────────────┘</div></div> Some examples for compatible cases: <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div> ; #3168 w=[101376-101407]</div><div> ; ·---------·---------·---########################################</div><div> 0x101112131415161718191A1B1C1D1E1F202122232425262728292A2B2C2D2E2Fn => A</div><div> ; ########################--·---------·---------·---------·-------</div><div> 0x303132333435363738393A3B3C3D3E3F404142434445464748494A4B4C4D4E4Fn => B</div><div> 12n => C</div><div> $ => A :MEM_ALIGN_RD</div><div> 0x1C1D1E1F202122232425262728292A2B2C2D2E2F303132333435363738393A3Bn :ASSERT</div> <div> ; #3172 w=[101504-101535]</div><div> 0x101112131415161718191A1B1C1D1E1F202122232425262728292A2B2C2D2E2Fn => A</div><div> ; ·---------·---------·---########################################</div><div> 0x101112131415161718191A1B0E1E2E3E4E5E6E7E8E9EAEBECEDEEEEF0F1F2F3Fn => D</div><div> 12n => C</div><div> 0x303132333435363738393A3B3C3D3E3F404142434445464748494A4B4C4D4E4Fn => B</div><div> ; ########################--·---------·---------·---------·-------</div><div> 0x4F5F6F7F8F9FAFBFCFDFEFFF3C3D3E3F404142434445464748494A4B4C4D4E4Fn => E</div><div> 0x0E1E2E3E4E5E6E7E8E9EAEBECEDEEEEF0F1F2F3F4F5F6F7F8F9FAFBFCFDFEFFFn :MEM_ALIGN_WR</div> </div> In this new version, MEM_ALIGN_WR8 does not exist because it's a particular case of MEM_ALIGN_WR with length = 1. The only inconvenience is that you need to set registers B and E to zero. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div> 12n + 1n * %MA_LEN_FACTOR => C</div><div> 0x101112131415161718191A1B1C1D1E1F202122232425262728292A2B2C2D2E2Fn => A</div><div> ; ·---------·---------·---##----·---------·---------·---------·---</div><div> 0x101112131415161718191A1BFF1D1E1F202122232425262728292A2B2C2D2E2Fn => D</div><div> 0 => B,E</div><div> 0x00000000000000000000000000000000000000000000000000000000000000FFn :MEM_ALIGN_WR</div> <div> ; supports dirty bytes on write</div> <div> 0x101112131415161718191A1B1C1D1E1F202122232425262728292A2B2C2D2E2Fn => A</div><div> ; ·---------·---------·---##----·---------·---------·---------·---</div><div> 0x101112131415161718191A1BFF1D1E1F202122232425262728292A2B2C2D2E2Fn => D</div><div> 12n + 1n * %MA_LEN_FACTOR => C</div><div> 0 => B,E</div><div> 0x0E1E2E3E4E5E6E7E8E9EAEBECEDEEEEF0F1F2F3F4F5F6F7F8F9FAFBFCFDFEFFFn :MEM_ALIGN_WR</div> </div> ## ARITH_MOD (modular arithmetic) Given registers `A,B,C,D,op`, it checks whether the linear operation `A*B + C` is equal to `op` modulo `D`, i.e.: $$ A · B + C = \text{op} \pmod{D} $$ It can be used to optimized division-related operations. For example, it could be used to safely verify the remainder of a division. Say you want to compute/verify $A \% D$, you could use the modular arithmetic as follows: <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; Compute A%D and return it on register C</div><div>checkRem:</div><div> ; A·1 + 0 = op (mod D)</div><div> 1 => B</div><div> 0 => C</div><div> ${A % D} => E :ARITH_MOD</div><div> E => C :RETURN</div></div> As a second example, addition modulo a prime `p` pre-feijoa was done as follows: <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>addFpBN254:</div><div> ; 1] Compute and check the sum over Z</div><div> ; A·[1] + C = [D]·2²⁵⁶ + [E]</div><div> ; A·1 + C = op (mod BN254_P)</div><div> 1 => B</div><div> $${var _addFpBN254_AC = A + C}</div><div> ${_addFpBN254_AC >> 256} => D</div><div> ${_addFpBN254_AC} => E :ARITH</div> <div> ; 2] Check it over Fp, that is, it must be satisfied that:</div><div> ; [BN254_P]·[(A+C) / p] + [(A+C) % p] = D·2²⁵⁶ + E</div><div> ; where C < BN254_P</div><div> %BN254_P => A</div><div> ${_addFpBN254_AC / const.BN254_P} => B ; quotient (256 bits)</div><div> ${_addFpBN254_AC % const.BN254_P} => C ; residue (256 bits)</div><div> E :ARITH</div> <div> ; 3] Check that the result is lower than BN254_P</div><div> A => B</div><div> C => A</div><div> 1 :LT, RETURN</div></div> using 2 standard arithmetic (one for controlling the possible overflow and the other for ensuring that `a = q·b + r`) and one binary to check the result is alias-free. With the modular arithmetic, this could be expressed as: <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>addFpBN254:</div><div> ; A·1 + C = op (mod BN254_P)</div><div> 1 => B</div><div> %BN254_P => D</div><div> ${(A + C) % D} => E :ARITH_MOD</div><div> E => C :RETURN</div></div> More examples: <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div>; 1] 0·0 + 0 = 0 (mod 1)</div><div>0n => A</div><div>0n => B</div><div>0n => C</div><div>1n => D</div><div>0n :ARITH_MOD</div> <div>; 2] 1·0 + 0 = 0 (mod 1)</div><div>1n => A</div><div>0n => B</div><div>0n => C</div><div>1n => D</div><div>0n :ARITH_MOD</div> <div>; 3] 0·1 + 0 = 0 (mod 1)</div><div>0n => A</div><div>1n => B</div><div>0n => C</div><div>1n => D</div><div>0n :ARITH_MOD</div> <div>; 4] 0·0 + 1 = 0 (mod 1)</div><div>0n => A</div><div>0n => B</div><div>1n => C</div><div>1n => D</div><div>0n :ARITH_MOD</div> <div>; 5] x·y + z = 0 (mod 1)</div><div>82404511619898090395080044893130374032931121663279308706641192292251088604573n => A</div><div>218016309922137699094797478333585171696794824697587846381595937510543687571n => B</div><div>63787468536760849300814264976359137980835693562263609965507003207114627618515n => C</div><div>1n => D</div><div>0n :ARITH_MOD</div> <div>; 6] Small random test</div><div>17741 => A</div><div>901868 => B</div><div>536729 => C</div><div>355064 => D</div><div>327885 :ARITH_MOD</div> <div>; 7] Big random test</div><div>19056371982582167475593876340225319134850470258276413387066558886464698322210n => A</div><div>20914269056602289532121456290808074920610800738424321255588157751277776260456n => B</div><div>10634756649036098220049242607700175280465139227303175868315978071819374369450n => C</div><div>10707315989258942200484412153631767731310293817155149881083576310392120779817n => D</div><div>6920609207119167395959131992066380589796703421563779918050515844861464646812n :ARITH_MOD</div> </div> Since we ensure via lookups that $0 \leq \text{op} < D$, it cannot be used with $D = 0$. This is consistent with the definition because division by 0 is not well-defined. It correctly works with $D = 1$, even tho the arithmetic check might be unoptimal for this particular case. ## Conditional Constant This feature allows to define a more readable syntax for comparing values of op0. Internally, a constant value was added to op0 before comparison. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div> ; without cond const feature</div><div> D :MLOAD(bytes)</div><div> D - 32 :JMPZ(labelD32)</div> <div> ; with cond const feature</div><div> D :JMP_EQ(32, labelD32),MLOAD(bytes)</div></div> This constant value is calculated in compilation time. It could contain constants, numbers, and more complex expressions, all of which must be resolved in compilation time. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div> A :JMP_EQ(230, label)</div><div> A :JMP_EQ(%K1, label)</div><div> A+10 :JMP_EQ(%K1+10, label)</div><div> 2*A-10 :JMP_EQ(2*%K1-10, label)</div><div> 2*A :JMP_EQ(%K1 == 230 ? 460 : 2, label)</div></div> This feature has six (6) operations. EQ and NE use JMPZ internally, while LT, LE, GT, and GE use JMPN. For this reason, EQ and NE work with all finite fields, but LT, LE, GT, and GE work only with 32 bits (positive or negative), considering subtracting constants. Also, all these "instructions" are available with CALL. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div> A :JMP_EQ(230, label) ; equal</div><div> A :JMP_NE(230, label) ; not equal</div><div> A :JMP_LT(230, label) ; less than (32 bits)</div><div> A :JMP_LE(230, label) ; less or equal than (32 bits)</div><div> A :JMP_GT(230, label) ; greater than (32 bits)</div><div> A :JMP_GE(230, label) ; greater or equal than (32 bits)</div> <div> A :CALL_EQ(230, label) ; equal</div><div> A :CALL_NE(230, label) ; not equal</div><div> A :CALL_LT(230, label) ; less than (32 bits)</div><div> A :CALL_LE(230, label) ; less or equal than (32 bits)</div><div> A :CALL_GT(230, label) ; greater than (32 bits)</div><div> A :CALL_GE(230, label) ; greater or equal than (32 bits)</div></div> These instructions could define else-address when the condition is false. <div style="color: #3b3b3b;background-color: #f8f8f8;margin-bottom: 10px;padding: 10px;font-family: 'Dejavu Sans Mono','Ubuntu Mono','Roboto Mono','Source Code Pro','JetBrains Mono','Droid Sans Mono', 'monospace', monospace, 'Droid Sans Mono', 'monospace', monospace;font-weight: normal;font-size: 13px;line-height: 18px;white-space: pre;"><div> A :JMP_EQ(230, label, elseLabel)</div><div> A :CALL_EQ(230, label, elseLabel)</div></div> ## 384-bit Arithmetic Described [here](https://hackmd.io/5pZOs4Y1RKeRsFVr9ZQLfg). # Open Points - recover instruction F_MSTORE - recover hash address as only constant - free-feature to allow hash address no consecutive (distance max: 256k) - use prefix \_\_ (or \_) for file scope labels and variables # TBD for Next Release - ARITH_DIV DIV(A,B)=\[OP,D\] D < B - free_bits - ASSERT_U32 - LOOP_RR or similar - MINC(constant_32bits) - MDEC(constant_32bits) - MSET(fromAddr, toAddr, value) - MCOPY(addr1, addr2) copy a word between positions

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.