Calculate Hamming Weight in MIPS Assembly Language

Calculate Hamming Weight in MIPS Assembly Language Homework Sample

The hamming weight of an integer is defined to be the number of bits set to 1 in the binary representation. So the hamming weight of 5 (101) is 2. This is an easy value to calculate in assembly, using shifts and carry flag, however the task is to convert the recursive C solution into assembly instead. The value is split into 3, and then the counts are taken for each third and combined (the counts for each third, are calculated recursively as well). The program should allow you to enter a value and then display the number of 1 bits in the binary representation. So “Enter a number: 1022” would output “There are 9 ONEs in 1022”. For further assembly language programming help contact us.

Solution:

.data
prompt: .asciiz “Enter a number: ”
result1: .asciiz “There are ”
result2: .asciiz ” ONEs in ”
result3: .asciiz “\n\n”

## Uncomment following lines to calculate jal count and stack size
#jalcount: .word 0
#stackmin: .word 0
#stacksize: .word 0

.text

#—————————————————-
# main function
# int main()
#—————————————————-
main:
addi $sp, $sp, -8 # allocate space in stack for registers
sw $ra, 0($sp) # save return address
sw $s0, 4($sp) # save $s0 on stack

li $v0, 4 # printf(“Enter a number: “);
la $a0, prompt
syscall

li $v0, 5 # scanf(“%d”, &x);
syscall
move $s0, $v0 # $s0 will contain the value of x

li $v0, 4 # printf(“There are “);
la $a0, result1
syscall

## Uncomment following lines to calculate jal count and stack size
# la $t0, stackmin # save current stack pointer in stackmin
# sw $sp, 0($t0)

# calculate hamming_weight(x, 31, 0)
move $a0, $s0
li $a1, 31
li $a2, 0
jal hamming_weight

## Uncomment following lines to calculate jal count and stack size
# la $t0, stackmin # calculate stack size
# lw $t0, 0($t0)
# sub $t0, $sp, $t0 # subtract minimum from current pointer
# la $t1, stacksize
# sw $t0, 0($t1) # save stack size in variable

move $a0, $v0 # print hamming weight result
li $v0, 1
syscall

li $v0, 4 # printf(” ONEs in “);
la $a0, result2
syscall

move $a0, $s0 # print x
li $v0, 1
syscall

li $v0, 4 # printf(“\n\n”);
la $a0, result3
syscall

li $v0, 10 # return 0;
syscall

lw $ra, 0($sp) # load return address from stack
lw $s0, 4($sp) # load $s0 from stack
addi $sp, $sp, 8 # restore stack pointer
jr $ra

#—————————————————-
# Hamming function
# int hamming_weight(int x, int li, int ri)
# On entry:
# $a0 = x
# $a1 = li
# $a2 = ri
# On return:
# $v0 = hamming weight
#—————————————————-
hamming_weight:
addi $sp, $sp, -32 # allocate space in stack for registers
sw $ra, 0($sp) # save return address
sw $s1, 4($sp) # save $s1 on stack
sw $s2, 8($sp) # save $s2 on stack
sw $s3,12($sp) # save $s3 on stack
sw $s4,16($sp) # save $s4 on stack
sw $s5,20($sp) # save $s5 on stack
sw $s6,24($sp) # save $s6 on stack
sw $s7,28($sp) # save $s7 on stack

## Uncomment following lines to calculate jal count and stack size
# la $t0, jalcount # increment number of jal calls
# lw $t1, 0($t0)
# addi $t1, $t1, 1
# sw $t1, 0($t0)
#
# la $t0, stackmin # update minimum stack pointer in stackmin
# lw $t1, 0($t0)
# bge $sp, $t1, skip # if the current stack pointer is not deeper, skip
# sw $sp, 0($t0) # else, update minimum
#skip:

move $s1, $a1 # preserve value of $a1 in $s1
move $s2, $a2 # preserve value of $a2 in $s2
# MASK = $s3
# right_count = $s4
# mid_count = $s5,
# left_count = $s6
# delta_index = $s7
_if:
bge $s1, $s2, _elseif # if (li<ri) {
li $v0, 0 # return 0;
j return # }
_elseif:
bne $s1, $s2, _else # else if (li==ri) {
li $t0, 1 # MASK = 1<<li;
sllv $s3, $t0, $s1

and $t0, $a0, $s3 # return ((x & MASK)>>li);
srlv $v0, $t0, $s1
j return
_else: # } else {
#// divide into three smaller problems
sub $t0, $s1, $s2 #delta_index = (li-ri+1)/3; // integer division
addi $t0, $t0, 1
li $t1, 3
div $t0, $t1
mflo $s7

sub $a2, $s1, $s7 #left_count = hamming_weight(x, li, li-delta_index );
jal hamming_weight
move $s6, $v0

sub $a1, $s1, $s7 #mid_count = hamming_weight(x, li-delta_index-1, li-2*delta_index);
addi $a1, $a1, -1
sll $t0, $s7, 1
sub $a2, $s1, $t0
jal hamming_weight
move $s5, $v0

sll $t0, $s7, 1 #right_count = hamming_weight(x, li-2*delta_index-1, ri);
sub $a1, $s1, $t0
addi $a1, $a1, -1
move $a2, $s2
jal hamming_weight
move $s4, $v0

add $v0, $s4, $s5 #return right_count + mid_count + left_count;
add $v0, $v0, $s6

return:
lw $ra, 0($sp) # load return address from stack
lw $s1, 4($sp) # load $s1 from stack
lw $s2, 8($sp) # load $s2 from stack
lw $s3,12($sp) # load $s3 from stack
lw $s4,16($sp) # load $s4 from stack
lw $s5,20($sp) # load $s5 from stack
lw $s6,24($sp) # load $s6 from stack
lw $s7,28($sp) # load $s7 from stack
addi $sp, $sp, 32 # restore stack pointer
jr $ra