.text
        .globl main


# esercizio 1 (ottimizzato e con tutti i quantificatori dati)
#       $a0 puntatore al testo
#       $a1 puntatore al pattern
#       $t0 carattere (del pattern)
#       $t1 quantificatore
#       $t2 carattere (del testo)

opt:    bne $t0,$t2,loop
one:    bne $t0,$t2,err
        addu $a0,$a0,1
loop:   addu $a1,$a1,2
match:  lbu $t2,($a0)
        lbu $t0,($a1)
        beqz $t0,end
        lbu $t1,1($a1)
        beq $t1,'?',opt
        beq $t1,'!',one
        beq $t1,'*',star
plus:   bne $t0,$t2,err
star1:  addu $a0,$a0,1
        lbu $t2,($a0)
star:   beq $t0,$t2,star1
        j loop
end:    bnez $t2,err
        li $v0,1
        jr $ra
err:    li $v0,0
        jr $ra


# esercizio 2 (soluzione semplice senza buffer)
#       $a0 puntatore stringa inizio
#       $a1 puntatore stringa meta'+1
#       $t0 carattere prima parte
#       $t1 carattere seconda parte

merge2: beq $a0,$a1,endall
        lbu $t0,($a0)
        lbu $t1,($a1)
        bgt $t0,$t1,second2

first2: addu $a0,$a0,1
        beq $a0,$a1,endall
        lbu $t0,($a0)
        ble $t0,$t1,first2
second2:subu $t2,$a1,1
loop2:  lbu $t3,($t2)
        sb $t3,1($t2)
        subu $t2,$t2,1
        bge $t2,$a0,loop2
        sb $t1,($a0)
        addu $a0,$a0,1
        addu $a1,$a1,1
        lbu $t1,($a1)
        beqz $t1,endall
        bgt $t0,$t1,second2
        j first2

endall: jr $ra


# esercizio 2 (soluzione con buffer in memoria o nello stack)
#       $a0 puntatore stringa inizio
#       $a1 puntatore stringa meta'+1
#       $t0 puntatore stringa inizio (copia)
#       $t1 puntatore stringa meta'+1 (copia)
#       $t2 lunghezza stringa
#       $t3 puntatore al buffer
#       $t4 puntatore al buffer (copia)
#       $t5 carattere prima parte
#       $t6 carattere seconda parte

merge:  move $t0,$a0
        move $t1,$a1
        subu $t2,$a1,$a0
        sll $t2,$t2,1
        beqz $t2,end3

# con buffer in memoria
#       move $a0,$t2
#       li $v0,9
#       syscall
#       move $t3,$v0
#       move $t4,$v0
#       move $a0,$t0

# con buffer nello stack
        subu $sp,$sp,$t2
        move $t3,$sp
        move $t4,$sp


        lbu $t5,($a0)
        lbu $t6,($a1)
        bgt $t5,$t6,second

first:  sb $t5,($t3)
        addu $t3,$t3,1
        addu $a0,$a0,1
        beq $a0,$t1,end1
        lbu $t5,($a0)
        ble $t5,$t6,first
second: sb $t6,($t3)
        addu $t3,$t3,1
        addu $a1,$a1,1
        lbu $t6,($a1)
        beqz $t6,end2
        ble $t6,$t5,second
        j first

end1:   sb $t6,($t3)
        addu $t3,$t3,1
        addu $a1,$a1,1
        lbu $t6,($a1)
        bnez $t6,end1
        j copia
end2:   sb $t5,($t3)
        addu $t3,$t3,1
        addu $a0,$a0,1
        lbu $t5,($a0)
        blt $a0,$t1,end2

copia:  lbu $t5,($t4)
        sb $t5,($t0)
        addu $t4,$t4,1
        addu $t0,$t0,1
        blt $t4,$t3,copia

end3:
# con buffer nello stack
        addu $sp,$sp,$t2

        jr $ra


# main e dati di prova non richiesti nel compito
# forniti solo per testare le soluzioni

main:   subu $sp,$sp,8
        sw $ra,4($sp)

        la $a0,txt
        la $a1,pat
        jal match
        beqz $v0,nomatch
        la $a0,ok
        li $v0,4
        syscall
nomatch:

        la $a0,str
        la $a1,str+4
        jal merge2
        la $a0,str
        li $v0,4
        syscall

        lw $ra,4($sp)
        addu $sp,$sp,8
        jr $ra

        .data
txt:    .asciiz "abbbcd"
pat:    .asciiz "a!b*c?d+e*f?"
ok:     .asciiz "ok"

str:   .asciiz "bdefacxy" # cambiare anche $a1