#
#  Autor(s)      : Jordi Ferrer Plana
#  e-mail        : jferrerp@eia.udg.es
#  Branch        : Estructura i Tecnologia de Computadors (ETIS/ETIG)
#
#  Working Group : Departament d'Electrònica, Informàtica i Automàtica
#  Project       : Exemples
#
#  Homepage      : http://eia.udg.es/etc/
#
#  Module        : Cerca dicotòmica en assemblador de MIPS (SPIM).
#
#  File          : cerca_v2.s
#  Date          : 16/05/2003 - 06/05/2006
#  Encoding      : ISO-8859-1 (Latin-1)
#
#  Compiler      : SPIM >= ver. 6.5
#  Libraries     : -
#
#  Notes         : - Realitza una cerca dicotòmica en un vector ordenat
#                    d'enters.
#                  - El programa escriu per la cónsola de l'SPIM el valor
#                    que es cercava en cas que es trobi o bé, la posició
#                    dins del vector on li tocaria anar en cas que no es
#                    trobi.
#
# ----------------------------------------------------------------------------
#
#      Copyright (C) 2002-2003, Jordi Ferrer Plana
#
#      This program is free software; you can redistribute it and/or
#      modify it under the terms of the GNU General Public License   
#      as published by the Free Software Foundation; either version 2
#      of the License, or (at your option) any later version.
#
#      This program is distributed in the hope that it will be useful,
#      but WITHOUT ANY WARRANTY; without even the implied warranty of
#      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
#
#      See the GNU General Public License (http://www.gnu.org/copyleft/)
#      for more details.
#
# ----------------------------------------------------------------------------
#


.text
          # En aquest exemple, 'n' no es guarda com a variable
n=4       # Ull! n=5 no es fa servir i n-1 no funciona a l'SPIM, per tant, 'n'
          # és la 'posició del darrer element' enlloc del 'número d'elements'.
main:
     li    $t0, 0          # $t0 = Trobat <- 0
     li    $t1, 0          # $t1 = Esquerre <- 0
     li    $t2, n          # $t2 = Dret <- 'n' - 1
     lw    $t3, Valor      # $t3 = Valor. Canviant aquesta instrucció per:
                           #   addi  $v0, $0, 5    # ( read_int )
                           #   syscall
                           #   add   $t3, $v0, $0  # $t3 = Valor <- Valor llegit
                           # es llegeix el valor per teclat.
While:                     # Condicions complementàries del 'while'
     bgt   $t1, $t2, Exit  # Si Esquerre > Dret, Sortir
     bne   $t0, $0, Exit   # Si Trobat, Sortir

                           # Cos del 'while'
     add   $t5, $t1, $t2   # $t5 = Esquerre + Dret
     srl   $t5, $t5, 1     # $t5 = Mig <- ( Esquerre + Dret ) / 2
     sll   $t7, $t5, 2     # $t7 = Mig * 4
     lw    $t6, X($t7)     # $t6 = X[Mig]

     bne   $t3, $t6, Else1 # Valor != X[Mig]
     move  $t1, $t5        # Esquerre = Mig
     li    $t0, 1          # Trobat = 1
     j     EndIf           # Sortir dels 'if'
Else1:
     bge   $t3, $t6, Else2 # Si Valor >= X[Mig], Else
     addi  $t2, $t5, -1    # $t2 = Dret <- Mig - 1
     j     EndIf           # Sortir dels 'if'

Else2:
     addi  $t1, $t5, 1     # $t1 = Esquerre <- Mig + 1

EndIf:
     j     While           # Propera iteració

Exit:                      # Fora del 'while'
     beq  $t0, $0, Else3   # Trobat == 0
     sll  $t7, $t1, 2      # $t7 <- Esquerre * 4
     lw   $a0, X($t7)      # $a0 <- X[Esquerre]
     j    Escriure         # Fora de l''if'
Else3:
     move $a0, $t1         # $a0 <- Esquerre

Escriure:                  # Escriure el resultat (X[Esquerre] o Esquerre)
     ori  $v0, $0, 1       # $v0 <- 1 ( print_int )
     syscall

.end

.data                            # Les dades

    X: .word 3, 10, 15, 24, 33   # Vector constant
Valor: .word 0                  # Valor que es vol cercar

.end