main.s.final

.section .maze, "aw"
.align 3
.global laberinto
.section .data
    estado: .dword 0x4e45204f4745554a, 0x21214f5352554320
    _stack_ptr: .dword _stack_end

// ------------- Modificar para agregar datos constantes --------------

// --------------------------------------------------------------------

.section .text
.global _start

// Constantes
.equ ESPACIO, 0x20
.equ SALIDA,  0x23
.equ PERSONA, 0x58

// Direcciones relativas al personaje
.equ DIR_UP,    0
.equ DIR_RIGHT, 1
.equ DIR_DOWN,  2
.equ DIR_LEFT,  3

_start:
    ldr     x1, =_stack_ptr
    ldr     x1, [x1]
    mov     sp, x1
    mov x0, xzr
    mov x4, xzr
    ldr x0, =laberinto


/* w11 es flag para indicar si se puede avanzar o no.
 * x19 es flag para indicar la direccion actual:
 * 0 = arriba, 1 = derecha, 2 = abajo, 3 = izquierda.
 * x1 es el contador de pasos.
 * x3 es la fila, x4 es la columna. (x3, x4) es una coodernada
 *
 */

main:
// ------------- El código principal debe ir aqui abajo ---------------

    // Iniciamos el contador de pasos en 0
    mov x1, xzr

    // Buscamos la posicion inicial de X en el laberinto
    // x9 tendra la dirección de memoria de X
    bl seeking_x

    // Orientación inicial mirando hacia abajo DIR_DOWN = 2
    // x19 mira para abajo
    mov x19, #DIR_DOWN

    // Hand-on-wall rule
    // https://en.wikipedia.org/wiki/Maze-solving_algorithm
resolve_loop:
    // Intentamos ir a la izquierda relativa (relativa a x19)
    bl turn_left
    // Chequeamos si podemos avanzar a la izquierda relativa a x19
    bl peek_forward
    // si w11=0, entonces es transitable,
    // si w11=1 entonces es pared, seguimos intentando
    cbz w11, do_move

    // Como no pudimos ir a la izquierda,
    // deshacemos el giro
    bl turn_right

    // Intentamos ir al frente (relativo a x19)
    bl peek_forward
    // si w11=0, entonces es transitable,
    // si w11=1 entonces es pared, seguimos intentando
    cbz w11, do_move

    // No pudimos ir al frente, entonces
    // Intentamos ir a la derecha (relativa a x19)
    bl turn_right
    bl peek_forward
    // si w11=0, entonces es transitable,
    // si w11=1 entonces es pared, seguimos intentando
    cbz w11, do_move

    // No pudimos ir a la derecha, entonces
    // Intentamos ir para atrás (relativo a x19)
    // Como ya estabamos mirando a la derecha de x19,
    // girar a la derecha otra vez nos deja mirando para atrás de x19,
    bl turn_right
    // intentar avanzar para atrás
    bl peek_forward
    cbz w11, do_move

    // callejon sin salida, no deberia suceder en un laberinto valido
    b resolve_loop

do_move:
    // Luz verde para avanzar,
    // x19 es la dirección a la que estamos mirando,

    // Calculamos coordenadas destino (x12, x13)
    mov x12, x3
    mov x13, x4

    // Si estamos mirando para arriba, la fila destino es fila-1
    cmp x19, #DIR_UP
    b.eq do_move_up
    // Si estamos mirando para la derecha, la columna destino es col+1
    cmp x19, #DIR_RIGHT
    b.eq do_move_right
    // Si estamos mirando para abajo, la fila destino es fila+1
    cmp x19, #DIR_DOWN
    b.eq do_move_down
    // Si estamos mirando para la izquierda, la columna destino es col-1
    sub x13, x13, #1
    b do_move_map
do_move_up:
    // fila destino es fila-1
    sub x12, x12, #1
    b do_move_map
do_move_right:
    add x13, x13, #1
    b do_move_map
do_move_down:
    add x12, x12, #1

do_move_map:
    // calculamos direccion destino
    // x14 = base + fila*16 + col
    mov x14, x0
    mov x15, #16
    madd x14, x15, x12, x14
    add x14, x14, x13

    // en este punto x14 es la direccion destino

    // leemos el byte destino
    ldrb w5, [x14]

    // verificamos si es la salida
    cmp w5, #SALIDA
    b.eq reached_exit

    // Como no era salida, entonces es un espacio transitable, avanzamos,
    // escribimos espacio en la posición vieja (x9 = dirección actual de X)
    mov w8, #ESPACIO
    strb w8, [x9]

    // escribimos X en la posición nueva (x14 = dirección destino)
    mov w8, #PERSONA
    strb w8, [x14]

    // seteamos coordenadas actuales a las coordenadas destino
    // es decir, donde ahora se encuentra el personaje X
    mov x3, x12
    mov x4, x13
    mov x9, x14

    // incrementar contador de pasos
    add x1, x1, #1

    // seguimos intentando
    b resolve_loop


/*
 * La funcion reached_exit se llama cuando el personaje
 * llega a la salida del laberinto. Escribe "Juego finalizado"
 * en el estado, y luego entra en un loop infinito.
 */

reached_exit:
    ldr x20, =estado
    mov x21, #0x754A
    movk x21, #0x6765, lsl #16
    movk x21, #0x206F, lsl #32
    movk x21, #0x6966, lsl #48
    str x21, [x20]
    mov x22, #0x616E
    movk x22, #0x6C69, lsl #16
    movk x22, #0x617A, lsl #32
    movk x22, #0x6F64, lsl #48
    str x22, [x20, #8]
    add x1, x1, #1

// --------------------------------------------------------------------

infloop: b infloop


/*
 * peek_forward chequea si la celda al frente es transitable
 *
 * Como el personaje puede estar mirando en cualquier dirección (x19),
 * calcula cuál es la celda al frente y lee su contenido en memoria.
 *
 * La dirección de memoria del destino se calcula con la formula del paper:
 *   dir = base + fila*16 + columna
 * Luego lee el byte y lo compara con ESPACIO (0x20) y SALIDA (0x23).
 *
 * @param  x0  = dirección base del laberinto
 * @param  x3  = fila actual del personaje
 * @param  x4  = columna actual del personaje
 * @param  x19 = orientación actual (DIR_UP=0, DIR_RIGHT=1, DIR_DOWN=2, DIR_LEFT=3)
 *
 * @return w11 = 0 si la celda al frente es transitable (ESPACIO o SALIDA)
 *         w11 = 1 si es pared u otro caracter no transitable
 *
 * Temporales: x12 para fila destino,
 *             x13 para columna destino,
 *             x14 para direccion destino,
 *             x15 para multiplicar fila por 16
 *
 * No modifica: x0, x3, x4, x9, x19
 */
peek_forward:
    mov x12, x3
    mov x13, x4

    // si estamos mirando arriba, la fila destino es fila-1
    cmp x19, #DIR_UP
    b.eq peek_forward_up
    // si estamos mirando a la derecha, la columna destino es col+1
    cmp x19, #DIR_RIGHT
    b.eq peek_forward_right
    // si estamos mirando abajo, la fila destino es fila+1
    cmp x19, #DIR_DOWN
    b.eq peek_forward_down
    // si estamos mirando a la izquierda, la columna destino es col-1
    sub x13, x13, #1
    b peek_forward_map
peek_forward_up:
    sub x12, x12, #1
    b peek_forward_map
peek_forward_right:
    add x13, x13, #1
    b peek_forward_map
peek_forward_down:
    add x12, x12, #1

peek_forward_map:
    // Calculamos la dirección destino
    // dirección = base + fila*16 + col
    mov x14, x0
    mov x15, #16
    madd x14, x15, x12, x14
    add x14, x14, x13

    // Leemos el byte destino
    ldrb w5, [x14]

    // Comparamos con espacio y salida
    cmp w5, #ESPACIO
    b.eq peek_forward_go
    cmp w5, #SALIDA
    b.eq peek_forward_go
    // no es ni espacio ni salida, entonces no es transitable
    // seteamos la flag w11 a 1 para indicar que no se puede avanzar
    mov w11, #1
    b peek_forward_end
peek_forward_go:
    // es transitable,
    // seteamos la flag w11 a 0 para indicar que se puede avanzar
    mov w11, #0
peek_forward_end:
    // retornamos
    br x30



// GIROS relativos a la direccion actual (x19)

 /* turn_left */
turn_left:
    sub x19, x19, #1
    and x19, x19, #3
    br  x30

/* turn_right */
turn_right:
    add x19, x19, #1
    and x19, x19, #3
    br  x30

/* turn_back */
turn_back:
    add x19, x19, #2
    and x19, x19, #3
    br x30


/*
 * map: x9 = base + x3*16 + x4
 * @param x0=base, x3=fila, x4=col
 * @return x9=dirección
 */
map:
    mov x15, #16
    mov x9, x0
    madd x9, x15, x3, x9
    add x9, x9, x4
    br x30


/*
 * seeking_x busca la X en el laberinto,
 * recorre el laberinto byte a byte hasta encontrar la X,
 * y calcula su fila y columna.
 *
 * @param  x0 = dirección base
 * @return x9 = dirección de X, x3 = fila, x4 = columna
 */
seeking_x:
    mov x3, xzr
    mov x4, xzr
    mov x9, x0
seeking_x_loop:
    ldrb w11, [x9]
    cmp w11, #PERSONA
    b.eq x_found
    add x9, x9, #1
    b seeking_x_loop
x_found:
    sub x10, x9, x0
    lsr x3, x10, #4
    and x4, x10, #0xF
    br x30


// Movimientos absolutos

/* move_left */
move_left:
    mov x26, x30
    bl map
    mov x7, x9
    sub x9, x9, #1
    ldrb w5, [x9]
    cmp w5, #SALIDA
    b.eq move_left_exit
    cmp w5, #ESPACIO
    b.ne move_left_fail
    mov w8, #ESPACIO
    strb w8, [x7]
    mov w8, #PERSONA
    strb w8, [x9]
    sub x4, x4, #1
    add x1, x1, #1
    mov w11, #0
    b move_left_end
move_left_fail:
    mov w11, #1
    b move_left_end
move_left_exit:
    add x1, x1, #1
    b reached_exit

move_left_end:
    br x26


/* move_right */
move_right:
    mov x26, x30
    bl map
    mov x7, x9
    add x9, x9, #1
    ldrb w5, [x9]
    cmp w5, #SALIDA
    b.eq move_right_exit
    cmp w5, #ESPACIO
    b.ne move_right_fail
    mov w8, #ESPACIO
    strb w8, [x7]
    mov w8, #PERSONA
    strb w8, [x9]
    add x4, x4, #1
    add x1, x1, #1
    mov w11, #0
    b move_right_end

move_right_fail:
    mov w11, #1
    b move_right_end
move_right_exit:
    add x1, x1, #1
    b reached_exit
move_right_end:
    br x26


/* move_down */
move_down:
    mov x26, x30
    bl map
    mov x7, x9
    add x3, x3, #1
    bl map
    ldrb w5, [x9]
    cmp w5, #SALIDA
    b.eq move_down_exit
    cmp w5, #ESPACIO
    b.ne move_down_fail
    mov w8, #ESPACIO
    strb w8, [x7]
    mov w8, #PERSONA
    strb w8, [x9]
    add x1, x1, #1
    mov w11, #0
    b move_down_end

move_down_fail:
    sub x3, x3, #1
    mov w11, #1
    b move_down_end
move_down_exit:
    add x1, x1, #1
    b reached_exit
move_down_end:
    br x26

move_up:
    mov x26, x30
    bl map
    mov x7, x9
    sub x3, x3, #1
    bl map
    ldrb w5, [x9]
    cmp w5, #SALIDA
    b.eq move_up_exit
    cmp w5, #ESPACIO
    b.ne move_up_fail
    mov w8, #ESPACIO
    strb w8, [x7]
    mov w8, #PERSONA
    strb w8, [x9]
    add x1, x1, #1
    mov w11, #0
    b move_up_end

move_up_fail:
    add x3, x3, #1
    mov w11, #1
    b move_up_end
move_up_exit:
    add x1, x1, #1
    b reached_exit

move_up_end:
    br x26