Jumping Pointers
Consider the following problem: There is an array A with byte values, for example [2, 3, -1, 2,-1]
, start position k = 0
. In each jump, you take the value of A at position k as offset with regard to your current position, i.e. k' = k+A[k]
. How many jumps can be performed before you leave the array or are caught in a loop? If you get into a loop, the algorithm should return -1. For the example above, the correct answer is 5, because you touch positions 0, 2, 1, 4, 3 before you leave the array. If A = [2, 3, -1, 2, -2]
, you touch positions 0, 2, 1, 4, 2, 1, 4, … and so on. Thus, the correct result would be -1.
I was curious about how this problem could be solved in assembly language. Here is my solution:
section .text extern printf global main main: mov edx, 0 ; Number of jumps mov esi, buffer mov edi, visited mov ebx, 0 loop: cmp ebx, 0 ; index < 0? jl print ; print result cmp ebx, len ; index >= len? jge print ; print result movzx ecx, byte [edi+ebx] cmp cl, 0 ; have we been here before? jnz infinity ; Yes, print result inc edx ; one step movsx ecx, byte [esi+ebx] mov byte [edi+ebx], 1 ; mark this position add ebx, ecx jmp loop infinity: mov edx, -1 print: push edx push output call printf add esp, 8 mov eax, 1 ; system exit mov ebx, 0 int 80h section .data output db 'Result %d', 0xa, 0x0 buffer db 2, 3, -1, 2, -1 len equ $-buffer visited db 0, 0, 0, 0, 0