Find the number in an array which is closest to an given number

Question

Exercise from an Assembly course I'm enrolled in:

Find closest number.

Add the following into the data section:

nums dd 23h,75h,111h,0abch,443h,1000h,5h,2213h,433a34h,0deadbeafh

This is an array of numbers.

Write a program that receives a number x as input, and finds the dword inside the array nums, which is the closest to x. (We define the distance between two numbers to be the absolute value of the difference: |a-b|).

Example:

For the input of 100h, the result will be 111h, because 111h is closer to 100h than any other number in the nums array. (|100h - 111h| = 11h).

Full exercise-sheet on GitHub - xorpd

Here's my approach. Please pay attention to the comments which I've added to explain my ideas.

format PE console
entry start
include 'win32a.inc' 
section '.data' data readable writeable
 nums dd 23h, 75h, 111h, 0abch, 443h, 1000h, 5h, 2213h, 433a34h, 0deadbeafh
 nums_end:
section '.text' code readable executable
start:
 xor esi, esi ; Current array-index.
 mov ecx, (nums_end - nums) / 4 ; Array-length
 mov ebx, 0x100 ; Input, Value to compare too. 
 mov edx, 0x7fffffff ; Smallest value found until now. Start with the greatest value possible.
 mov edi, edi ; Index of the element with the smallest value.
 ; -------------------------------------------------------------------------------------------------------------------
check_next:
 mov eax, ebx ; Make a copy compare-value.
 mov ebp, dword[nums + 4 * esi] ; Move the value of the current element to ebp.
 cmp eax, ebp ; If eax is smaller then ebp then we must not subtract ebp from eax.
 jb eax_is_smaller ; This would result in a negative number. ...
 sub eax, ebp
 jmp subtraction_done
eax_is_smaller:
 sub ebp, eax ; ... subtract eax from ebp instead.
 mov eax, ebp ; ... and move the result to eax.
subtraction_done:
 cmp eax, edx ; Compare the result to the current smallest value.
 jnb prepare_next
 mov edx, eax ; If the result is smaller then the current smallest value the result becomes the smallest value.
 mov edi, esi ; Save the index of the smallest value.
prepare_next:
 inc esi ; Increment the array-index.
 loop check_next ; Check the next array-element.
 ; -------------------------------------------------------------------------------------------------------------------
 mov eax, dword[nums + 4 * edi] ; Use the index of the nearest element to get the value. Then print it to stdout.
 call print_eax ; Print to stdout. Function provided by the tutor.
 ; Exit the process:
 push 0
 call [ExitProcess]
include 'training.inc'

I've tried it with different compare-values and it provided the expected value every time. So I guess it's generally correct. Nevertheless I'm not completely satisfied. I have used a lot of register.

How can I reduce the number of register? I have found a solution for the problem with getting negative values when subtracting a larger number from a smaller number. It works but it isn't elegant. Is there a better solution?

Answer 1

mov edi, edi ; Index of the element with the smallest value.

An error here. You want to zero this register. Use xor

---

A better strategy will be to simply subtract without looking at which number is the largest and then later take the absolute value of the difference.

 mov eax, [nums + 4 * esi]
 sub eax, ebx
 jnl IsPositive
 neg eax
IsPositive:
 cmp eax, edx ; Compare the result to the current smallest value.
 jnb prepare_next
 mov edx, eax
 mov edi, esi
prepare_next:

Less code and less register usage!

---

A further optimization will come from not using ECX as a loop counter. You can determine if the loop is completed by looking at the ESI array index.

 xor esi, esi ;Start at index 0
check_next:
 ...
 inc esi
 cmp esi, (nums_end - nums) / 4
 jb check_next

---

In stead of branching, you could use one of the conditional forms of mov.
Same code size but faster. Having less labels is also nicer.

 cmp eax, edx ; Compare the result to the current smallest value.
 cmovb edx, eax
 cmovb edi, esi

About coding style.

mov eax, dword[nums + 4 * edi]

Does your assembler requires you to write this redundant mention of the size?
Do you get an error if you write it shorter?

 mov eax, [nums + 4 * edi]

• michael.zech: Thanks a lot. Goanna try out the access in brackets-syntax this evening.