#
#  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.s
#  Date          : 16/05/2003 - 16/05/2003
#  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:
     add   $t0, $0, $0     # $t0 = Trobat <- 0
     add   $t1, $0, $0     # $t1 = Esquerre <- 0
     addi  $t2, $0, 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.

     ori   $t4, $0, 2      # $t4 = Constant 2 (pel div a dins el 'while')
     ori   $t8, $0, 1      # $t8 = Constant 1 (pel subu a dins el 'while')

While:
     slt   $t7, $t1, $t2   # $t7 <- Esquerre < Dret
     bne   $t7, $0, And    # Esquerre < Dret
     beq   $t1, $t2, And   # o Esquerre == Dret 
                           # Les tres instruccions anteriors
                           # son equivalents a:   ble   $t1, $t2, And

     j     Exit            # Primera condició del 'while' falla
And:                       # Primera part de l'And ok: Esquerre <= Dret
     beq   $t0, $0, OkAnd  # && !Trobat
     j     Exit            # Segona condició del 'while' falla

OkAnd:                     # Segona part de l'And ok: !Trobat
                           # Cos del 'while'
     add   $t5, $t1, $t2   # $t5 = Esquerre + Dret
     div   $t5, $t4        # Lo = ( Esquerre + Dret ) / 2
     mflo  $t5             # $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]
     add   $t1, $t5, $0    # Esquerre = Mig
     addi  $t0, $0, 1      # Trobat = 1
     j     EndIf           # Sortir dels 'if'
Else1:
     slt   $t7, $t3, $t6   # $t7 = Valor < X[Mig]
     beq   $t7, $0, Else2
     subu  $t2, $t5, $t8   # $t2 = Dret <- Mig - 1
     j     EndIf           # Sortir dels 'if'

Else2:
     addu  $t1, $t5, $t8   # $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:
     add  $a0, $t1, $0     # $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 10                  # Valor que es vol cercar

.end