Why does this Cairo program put powers of 2 in the memory?

Question

I'm trying to solve this bonus question from the "How Cairo Works" tutorial. I ran the following function, opened the Cairo tracer and saw that the memory is full with powers of 2. Why is that?

func main():
    [fp + 1] = 2; ap++
    [fp] = 5201798304953761792; ap++
    jmp rel -1
end

Answer 1

Here are some leading questions that can help you reach the answer. Answers to the questions after a break:

1. Where does the jmp rel -1 instruction jump to?
2. What does the target instruction do? What happens after it?
3. How did this instruction end up in the program section of the memory?

---

1. jmp rel -1 is encoded in the memory at addresses 5-6. When it is executed, we have pc = 5, thus after the jump we will execute the instruction at pc = 4, which is 0x48307fff7fff8000.
2. This bytecode encodes the instruction [ap] = [ap - 1] + [ap - 1]; ap++ (to check, you can manually decode the flags and offsets [Edit: see below], or simply write a cairo program with this instruction and see what it compiles to). After it is executed, pc is increased by 1, so we again execute jmp rel -1, and so on in an infinite loop. It should be clear why this fills the memory with powers of 2 (the first 2, at address 10, was written by the [fp + 1] = 2; ap++ instruction).
3. The instruction [fp] = 5201798304953761792; ap++ has an immediate argument (the right hand side, 5201798304953761792). Instructions with immediate arguments are encoded as two field elements in the memory, the first encoding the general instruction (e.g. [fp] = imm; ap++), and the second being the immediate value itself. This immediate value is thus written in address 4, and indeed 5201798304953761792 is the same as 0x48307fff7fff8000. Similarly, the 2 at address 2 is the immediate argument of the instruction [fp + 1] = 2, and the -1 at address 6 is the immediate of jmp rel -1.

To summarize, this strange behavior is due to the relative jump moving to an address of an immediate value and parsing it as a standalone instruction. Normally this wouldn't occur, since pc is incremented by 2 after executing an instruction with an immediate value, and by 1 when executing an instruction without one, so it always continues to the next compiled instruction. The unlabeled jump was necessary here to reach this unexpected program counter.

---

How can one manually decode the flags and offsets of 0x48307fff7fff8000? Consulting the Cairo whitepaper (mostly pages 50-59), we see that the lower three 16-bit words encode offsets off_dst = 0, off_op0 = off_op1 = -1 (the values 0x8000, 0x7fff, 0x7fff are offset by 2¹⁵, or alternatively can be considered as signed integers, as detailed on page 51). The flag word is 0x4830, which has 4 flags set to 1 and the rest are 0: the set flags, from least to most, are f₄, f₅, f₁₁ and f₁₄, which correspond to the flags OP1_AP, RES_ADD, AP_ADD1 and OPCODE_ASSERT_EQ (according to page 58). Let us explore the meaning of these flags (derived from the constraints listed in pages 58-59):

• The OP1_AP flag means operand 1 is taken relative to ap, with offset off_op1, i.e. op1 = [ap - 1]. Operand 0 and dst are also relative to ap by default (when the relevant flags are not set), and including the above offsets we see that op0 = [ap - 1], dst = [ap].
• The RES_ADD flag means the operation between op0 and op1 is addition, i.e. the constraint res = [ap - 1] + [ap - 1] is enforced.
• The OPCODE_ASSERT_EQ flag means this is as equality assertion command, which means res will be equaled to dst by enforcing dst - res = 0, which we now see is equivalent to [ap] = [ap - 1] + [ap - 1].
• Finally, the AP_ADD1 flag simply means ap is advanced by 1, which corresponds to the ap++ part of the command.

Taken all together, we get the command [ap] = [ap - 1] + [ap - 1]; ap++ as claimed.