## LSU EE 4720 -- Fall 2024 -- Computer Architecture
#
## Histogram Example Program -- Live Classroom Code

# Time-stamp: <8 February 2024, 9:44:26 CST, koppel@cyc2.ece.lsu.edu>

################################################################################
## histo: Compute Character Usage Histogram

        .text
histo:
        ## Register Usage
        #
        # Call: $a0  String to analyze.
        #       $a1  Address of 26-element histogram table.
        #            Each element is a 4-byte integer.
        #            Initially all elements zero.
        # Return:
        #       No register return values.
        #       Instead, modify memory pointed to by $a1:
        #         Let h = $a1.
        #         h[0]: Number of A's.
        #         h[1]: Number of B's.
        #         ...

BACK:
        lb $t1, 0($a0)
        beq $t1, $0, DONE
        slti $t4, $t1, 122
        beq $t4, $0, BACK
        addi $a0, $a0, 1
        slti $t4, $t1, 96
        bne $t4, $0, SKIP
        nop
        # Letter is lower-case. Get and increment table entry.

        j UPDATE_TABLE
        addi $t1, $t1, -97

SKIP:
        addi $t1, $t1, -65
        sltiu $t4, $t1, 26
        beq $t4, $0, BACK

UPDATE_TABLE:
        sll $t1, $t1, 2
        add $t3, $a1, $t1

        lw $t2, 0($t3)
        addi $t2, $t2, 1
        j BACK
        sw $t2, 0($t3)


DONE:
        jr $ra
        nop


################################################################################
## Test Routine
#
#  Calls histogram program (histo) then prints table.
#

        ## Input string for testing histo.
        #
        .data
doi:
        .ascii "CDe"
        .ascii "[]\^_`@?>={|}~\n"  # Test some out-of-range characters.
        .ascii "The quick brown fox jumps over the lazy dog."
        .ascii "\n"
        .ascii "Do you know what it means to miss New Orleans"
        .ascii "And miss it each night and day"
        .ascii "I know I'm not wrong... this feeling's gettin' stronger"
        .ascii "The longer, I stay away"
        .ascii "Miss them moss covered vines...the tall sugar pines"
        .ascii "Where mockin' birds used to sing"
        .ascii "And I'd like to see that lazy Mississippi...hurryin' into spring"
        .ascii ""
        .ascii "The moonlight on the bayou.......a creole tune.... that fills the air"
        .ascii "I dream... about magnolias in bloom......and I'm wishin I was there"
        .ascii ""
        .ascii "Do you know what it means to miss new orleans"
        .ascii "When that's where you left your heart"
        .ascii "And there's one thing more...i miss the one I care for"
        .ascii "More than I miss New Orleans"
        .ascii ""
        .asciiz "-- Louis Armstrong"

msg:
        .asciiz "Letter %/t3/c  count: %/t1/3d (%/f4/6.2f%%) %/t5/s\n"
msg_perf:
        .ascii  "Histogram of %/f2/.0f chars took %/s5/d instructions, "
        .asciiz "%/f10/.1f insn / char.\n"

        .align 4
histogram_data:
        .space 104
stars:
        .space 40

TB_100:
        .double 100.0  # The constant 100, used to show percents.


        .text
        .globl __start
__start:
        mtc0 $0, $22            # Pause tracing.
        la $a1, histogram_data
        addi $t1, $a1, 0
        addi $t2, $t1, 100
L3:
        # Initialize the histogram table to all zeros.
        sw $0, 0($t1)
        bne $t1, $t2, L3
        addi $t1, $t1, 4

        # Initialize the stars (asterisks) string to all stars.
        la $t1, stars
        addi $t2, $t1, 40
        addi $t3, $0, 42  # '*'
L4:
        sb $t3, 0($t1)
        bne $t1, $t2, L4
        addi $t1, $t1, 1
        sb $0, 0($t1)     # Don't forget the null terminator.

        # Compute 100/len, where len is the length of the string at doi.
        la $a0, doi
        jal strlen
        nop
        mtc1 $v0, $f2
        cvt.d.w $f2, $f2
        la $t3, TB_100
        ldc1 $f4, 0($t3)
        div.d $f6, $f4, $f2  # f6 = 100 / len;  len is length of test string.

        addi $v0, $0, -1
        mtc0 $v0, $22           # Resume tracing. (No effect if not stepping.)
        jal histo
        mfc0 $s7, $9
        mtc0 $0, $22            # Pause tracing.
        mfc0 $s6, $9

        # Prepare to write histogram table to the console.
        add $t0, $0, $0
        addi $t3, $0, 64
        addi $t4, $t3, 26
        la $s1, histogram_data
        addi $v0, $0, 11
        la $s2, stars
        addi $s2, $s2, 41    # Address of the end of the stars string.
        la $a0, msg

L2:
        lw $t1, 0($s1)       # t1: Number of times character t3 appears.
        addi $s1, $s1, 4
        addi $t3, $t3, 1     # t3: The character corresponding to the histo bin.
        srl $t6, $t1, 1
        sub $t5, $s2, $t6    # t5: Address of some position in stars string.
        mtc1 $t1, $f0
        cvt.d.w $f0, $f0
        mul.d $f4, $f0, $f6  # f4: percentage of string.
        syscall              # Call formatted print routine.
TEST:
        bne $t3, $t4, L2
        nop

        # Prepare data for performance text.
        sub $s5, $s6, $s7     # Number of executed instructions.
        mtc1 $s5, $f8
        cvt.d.w $f4, $f8
        div.d $f10, $f4, $f2
        la $a0, msg_perf
        addi $v0, $0, 11
        syscall

        addi $v0, $0, 10
        syscall


################################################################################
## upper: Convert to Upper Case

upper:
        ## Register Usage
        #
        # $a0: (Call) Address of string to convert.
        #
        # $a0: Address of character being examined.
        # $t1: Character being examined.
        # $t2: Comparison result.
        #
        # Example:  Before: "aB."    
        #           After:  "AB."
ULOOP:
        lbu $t1, 0($a0)          # Load character from string.
        addi $a0, $a0, 1
        beq $t1, $0, UDONE
        slti $t2, $t1, 97        # < 'a'
        bne $t2, $0 ULOOP
        slti $t2, $t1, 123       # 'z' + 1
        beq $t2, $0, ULOOP
        addi $t1, $t1, -32
        j ULOOP
        sb $t1,-1($a0)

UDONE:
        jr $ra
        nop


################################################################################
## strlen: String Length

strlen:
        ## Register Usage
        #
        # $a0: Address of first character of string.
        # $v0: Return value, the length of the string.
        #
        # $t0: Character being examined.
        # $t1: Address of current character being examined.
        #
        addi $t1, $a0, 0
SLOOP:
        lbu $t0, 0($t1)
        bne $t0, $0, SLOOP
        addi $t1, $t1, 1

        addi $t1, $t1, -1
        jr $ra
        sub $v0, $t1, $a0