Блог

Я пытаюсь написать подпрограмму линейного поиска в сборке x64, которая возвращает индекс целевого параметра, который принимает четыре параметра. Эта функция будет сканировать массив итеративно, пока не найдет целевой элемент или не достигнет конца массива. Функция принимает три параметра. Первый параметр — это указатель на массив int. Второй параметр — это целое число, представляющее размер массива. Третий параметр — это целое число, представляющее целевой элемент для поиска в массиве. Возвращаемый тип этой функции — int и будет индексом в массиве, в котором был найден целевой объект, или -1, если это не так

Я написал psudeocode для этого

 int linearSearch(int * arr, int size, int target){
    int a;
    int index = -1;
    for(int i = 0; i < size; i  ){
        if(arr[i] == target){
            index = i;
            break;
        }
    }
    return index;
}
  

И вот мой код для этого

     global linearSearch
    
linearSearch:
    ;the prologue
    xor rax, rax    ;zero out the return address
    xor r10, r10    ;zero out the counter
    
linearSearchIterative:
    ;function body
    mov rax, -1     ;int index = -1 if not found
    cmp r10, rsi    ;compare counter i with the size
    je done         ;done with the program
    cmp rdx, [rdi 4*r10]    ;compare target with arr[i]
    je linearSearchAlter    ;jump to the index fixing part if arr[i] == target
    inc r10         ;i  
    jmp linearSearchIterative   ;go back to the start of the loop
    
linearSearchAlter:
    ;This part change the return index to where the target is
    mov rax, r10    ;index = i
    jmp done    ;end the loop
    
    
done:
    ret
  

Однако подпрограмма возвращает только -1, чего не ожидается.
Я использую тестовый файл cpp для тестирования моего кода, который должен дать следующий ожидаемый результат

 #include <iostream>
#include <cstring>
using namespace std;

extern "C" int linearSearch(int * arr, int size, int target);

int main(){

    int size;
    // prompt for array size
    cout << "Enter the array size: ";
    cin >> size;
    int * arr = new int[size];

    // read in array values
    for(int i = 0; i < size; i  ) {
        cout << "Enter value " << i << ": ";
        cin >> arr[i];
    }

    int target;
    // prompt for target
    cout << "Enter target to search for: ";
    cin >> target;

    int ind = linearSearch(arr, size, target);
    cout << ind << endl;

    if (ind > -1)
        cout << "nFound " << target << " at index " << ind << endl;
    else
        cout << "nDid not find " << target << endl;

    return 0;

}

  

Ожидаемый результат должен быть (я добавляю оператор печати для проверки значения индекса)

 Enter the array size: 5
Enter value 0: -7
Enter value 1: 2
Enter value 2: -39
Enter value 3: 12
Enter value 4: 8
Enter target to search for: 2
1

Found 2 at index 1
  

Вместо этого мой результат (я добавляю оператор печати для проверки значения индекса)

 Enter the array size: 5
Enter value 0: -7
Enter value 1: 2
Enter value 2: -39
Enter value 3: 12
Enter value 4: 8
Enter target to search for: 2
-1

Did not find 2

  

Таким образом, кажется, что подпрограмма всегда возвращает -1 вместо индекса целевого объекта. В чем должна быть проблема? Спасибо