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 

Kommentar hinterlassen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.


*