I am trying to implement Knapsack's algorithm through recursion in x86 Assembly, modeling the following Java code. However, when I run my program, it seems as if the parameter taking in the capacity of the bag (the 4th parameter) is changed following a recursive call (specifically following the prologue).
The initial call is:
knapsack(weights, values, 2, 2, 0)
When I look in the debugger, initially all the parameters are taken in as correctly:
weights is the pointer to the correct array (0x5655b2f0) ($ebp + 8)
values is the pointer to the correct array (0x5655b300) ($ebp + 12)
num_items = 2 ($ebp + 16)
capacity = 2 ($ebp + 20)
cur_value = 0 ($ebp + 24)
However, in the code executed at maximizeItemUsage, I execute the following recursive call:
knapsack(weights, values, 2, 1, 0)
However, when I look at my debugger, after the following line of code in the prologue (in knapsack):
mov %esp, %ebp
I get the following data in the parameters:
0 ($ebp + 8)
2 ($ebp + 12)
1 ($ebp + 16)
0x5655b300 ($ebp + 20)
0x5655b2f0 ($ebp + 24)
This seems quite strange, considering that the prologue is to supposed to align the stack properly. Below is my code:
# Function signature:
# int knapsack(int* w, int* v, int num_items,
# int capacity, int current);
.text
# Define our macros, which store the location of the parameters and values
# relative to the stack's base pointer (EBP)
.equ weights, 8
.equ values, 12
.equ num_items, 16
.equ capacity, 20
.equ cur_value, 24
.equ do_not_use, -4
.equ use, -8
.global knapsack
knapsack:
# solves the knapsack problem
# @weights: an array containing how much each item weighs
# @values: an array containing the value of each item
# @num_items: how many items that we have
# @capacity: the maximum amount of weight that can be carried
# @cur_weight: the current weight
# @cur_value: the current value of the items in the pack
# Prologue (prepare the stack frame)
push %ebp
mov %esp, %ebp
# Make space for local variables on the stack
# 3 variables (4 bytes each)
# Default values are 0
#
# 1. the value of the bag if we DO NOT use the current item
# 2. the value of the bag if we USE the current item
# 3. the maximum value of the bag currently
sub $8, %esp
movl $0, do_not_use(%ebp)
movl $0, use(%ebp)
# Base Case: we have utilized all the items or there is no more space left
# in the bag (num_items = 0 or capacity = 0)
cmpl $0, num_items(%ebp)
jle emptyBag
cmpl $0, capacity(%ebp)
jle emptyBag
# Case 1: We do not use the current element because adding it wil surpass capacity
# weights[n - 1] > capacity
# Push the new parameters in the stack (everything stays the same, except that
# n -> n - 1 since we are no longer using the current element)
# Compute weights[n - 1] (stored in ECX register)
# Get the memory address of the values array
movl weights(%ebp), %ecx
# Move to the memory address of weights[n - 1]
push %edx
movl num_items(%ebp), %edx # num_items
decl %edx # num_items - 1
imul $4, %edx # 4(num_items - 1)
addl %edx, %ecx # m_v + 4(num_items - 1)
# Get the actual value of weights[n - 1]
movl (%ecx), %ecx # Get value at address m_w + 4(num_items - 1)
pop %edx
# If weights[n - 1] > capacity
cmpl %ecx, capacity(%ebp)
# Shift to analyzing the previous items
jl analyzePreviousItems
# Case 2: We can use the current element (in this case, find the maximum of the values
# we use the element or if we do not use the element
jmp maximizeItemUsage
# Solidify the EAX register data
movl %eax, %eax
# Epilogue (cleanup the stack frame)
mov %ebp, %esp
pop %ebp
# Return the maximum possible weight of the bags :D
ret
maximizeItemUsage:
# knapsack(weights, values, num_items - 1, capacity, current_value)
# All parameters remain the same (except that n > n - 1)
push weights(%ebp)
push values(%ebp)
# num_items - 1
movl num_items(%ebp), %edx
decl %edx
push %edx
push capacity(%ebp)
push cur_value(%ebp)
# Call knapsack(weights, values, num_items - 1, capacity, cur_value)
call knapsack
# The value if we DO NOT use the current item
movl %eax, do_not_use(%ebp)
# knapsack(weights, values, n - 1, c - weights[n]) + values[n]
# All parameters remain the same (except that n > n - 1 and c > c - weights[n])
push weights(%ebp)
push values(%ebp)
# num_items - 1
movl num_items(%ebp), %edx
decl %edx
# capacity - weights[n] (stored in the ECX register)
# Get the memory address of the values array
movl weights(%ebp), %ecx
# Move to the memory address of weights[n]
push %edx
movl num_items(%ebp), %edx # num_items
imul $4, %edx # 4(num_items)
addl %edx, %ecx # m_w + 4(num_items)
# Restore the value of the EDX register
pop %edx
# Get the actual value of weights[n]
movl (%ecx), %ecx # Get value at address m_w + 4(num_items)
# -weights[n]
neg %ecx
# capacity - weights[n]
addl capacity(%ebp), %ecx
push %ecx
push cur_value(%ebp)
# Call knapsack(weights, values, num_items - 1, capacity - weights[n], cur_value)
call knapsack
# The value if we USE the current item
movl %eax, use(%ebp)
# Compute the maximum value of knapsack(weights, values, num_items - 1, capacity, cur_value)
# and knapsack(weights, values, n - 1, c - weights[n]) + values[n]
movl use(%ebp), %ecx
cmpl %ecx, do_not_use(%ebp)
jl setUseAsMax
movl do_not_use(%ebp), %eax
# Epilogue (cleanup the stack frame)
mov %ebp, %esp
pop %ebp
ret
setUseAsMax:
movl use(%ebp), %eax
# Epilogue (cleanup the stack frame)
mov %ebp, %esp
pop %ebp
ret
analyzePreviousItems:
# Recursive Call 1: knapsack(weights, values, n - 1, c)
# All parameters remain the same (except that n -> n - 1)
push weights(%ebp)
push values(%ebp)
# We use the EDX to contain the changed parameters since it is a
# non-volatile register
movl num_items(%ebp), %edx
decl %edx
push %edx
push capacity(%ebp)
push cur_value(%ebp)
# Call knapsack(weights, values, num_items - 1, capacity, cur_value)
call knapsack
# The value if we DO NOT use the current item
movl %eax, do_not_use(%ebp)
# Epilogue (cleanup the stack frame)
mov %ebp, %esp
pop %ebp
# Return knapsack(weights, values, n - 1, c)
ret
emptyBag:
movl 0, %eax
# Epilogue (cleanup/realign the stack frame)
mov %ebp, %esp
pop %ebp
# Return 0
ret
