Fautes de segmentation dans la recherche binaire dans l'assemblage NASM

Question

Bonjour, j'ai du mal à trouver la raison pour laquelle mon implémentation de recherche binaire est en panne (je suis nouveau dans l'assemblage NASM).

Désolé, je sais que ce n'est pas vraiment une MVP, mais je ne vois pas comment en faire une en assemblage.

%define n [ebp+8]
%define list [ebp+12]
%define low [ebp+16]
%define high [ebp+20] ; Parameters loading from the stack
binary_search:
  push ebp
  mov ebp, esp

  mov ebx, n
  mov edi, list
  mov ecx, low
  mov edx, high

  cmp ecx, edx ; if (low > high)
  jg .FIRST

  mov eax, edx ; Next few lines for mid = low + (high - low)/2
  sub eax, ecx
  sar eax, 1 ; Will this give an appropriate index? (i.e is it floor division?)
  add eax, ecx
  lea esi, [edi+eax*4] ;Getting list[mid]
  cmp ebx, [esi]; if (n == list[mid])
  je .END
  jl .SECOND
  jg .THIRD

  jmp .END

.FIRST:
  mov eax, -1 ; return -1
  jmp .END

.SECOND:
  mov edx, eax ; return middle - 1
  dec edx
  jmp .CONTINUE

.THIRD:
  mov ecx, eax ; low = mid - 1
  dec ecx
  jmp .CONTINUE

.CONTINUE:
  push edx
  push ecx
  push edi
  push esi
  push ebx
  call binary_search ; recursive call, causing the segfault.
  pop ebx
  pop esi
  pop edi
  pop ecx
  pop edx
  jmp .END

.END:
  mov esp, ebp
  pop ebp
  ret

Après avoir commenté différentes sections, j'ai déterminé qu'il y a définitivement quelque chose à faire avec mon appel récursif à binary_search qui cause le seg fault. (Trouvé dans .CONTINUE) Qu'est-ce que je fais de travers dans le corps de binary_search qui n'est pas compatible avec de multiples appels récursifs ?

L'algorithme de recherche binaire :

binary_search(n, list, low, high)

    if (low > high)
        return -1

    mid = low + (high - low) / 2

    if (n == list[mid])
       return middle;
    if (n < list[mid])
       high = mid - 1
    else
        low = mid + 1

    return binary_search(n, list, low, high)

Je sais que c'est un peu long, mais merci :)

Edit : son mode 32-bit

Answer 1

Cette partie définit le protocole de votre fonction :

%define n [ebp+8]
%define list [ebp+12]
%define low [ebp+16]
%define high [ebp+20] ; Parameters loading from the stack
binary_search:
  push ebp
  mov ebp, esp

Le mot-clé [ebp] tiendra l'ancien ebp valeur, dword [ebp+4] l'ancien eip pour y revenir, puis vos paramètres suivent. Ce sont n, list, low, et high, dans cet ordre. Au fur et à mesure que la pile se développe vers le bas, vous devez pousser sur la pile dans l'ordre suivant : le paramètre le plus haut adressé (qui se trouve être "high") est poussé en premier, puis le deuxième plus haut (low), et ainsi de suite (list, n, eip , ebp ).

La partie suivante détermine les registres que vous utilisez pour contenir les variables initialisées à partir de ces paramètres de trame de pile :

  mov ebx, n
  mov edi, list
  mov ecx, low
  mov edx, high

(Soit ecx o edx est modifié avant l'appel récursif. Mais ils agissent toujours comme les variables "basse" et "haute" dans ce code).

Maintenant pour vérifier votre site d'appel récursif. Essentiellement, vous voulez repasser tous les registres que vous utilisez à la fonction. ebx = n, edi = liste, ecx = faible, edx = haut. C'est ce que vous faites :

.CONTINUE:
  push edx
  push ecx
  push edi
  push esi
  push ebx
  call binary_search ; recursive call, causing the segfault.
  pop ebx
  pop esi
  pop edi
  pop ecx
  pop edx

Si vous faites correspondre les variables poussées avec les paramètres de la trame de la pile attendus par le protocole de votre fonction, vous obtenez :

  push edx    ; (unused)
  push ecx    ; high
  push edi    ; low
  push esi    ; list
  push ebx    ; n
  call binary_search

La variable représentée par esi est uniquement utilisé en interne par votre fonction. Elle n'a pas besoin d'être transmise aux appels suivants. De plus, il perturbe le protocole de votre fonction. edx , ecx et edi sont déplacées d'un emplacement de pile plus haut qu'elles ne devraient l'être pour transmettre ces variables à votre appel récursif. La solution est de laisser tomber push esi y pop esi ici.

---

Il y a quelques autres problèmes potentiels avec votre code :

• Comme je l'ai mentionné dans les commentaires, vous devez utiliser inc ecx pas dec ecx .

• Quelle est la convention d'appel de votre programme utilisée pour appeler cette fonction ? Vous semblez utiliser beaucoup de registres et vous ne conservez que ebp y esp .

• Si votre convention d'appel permet de modifier le contenu des paramètres du cadre de la pile sans limites, vous pouvez remplacer le littéral call que vous utilisez pour effectuer une récursion, par un "tail call" dont les paramètres sont modifiés par rapport à ceux que vous passez actuellement à la fonction call . Et réutiliser l'ensemble du cadre de la pile. À ce stade, cela ressemblerait beaucoup à une boucle. Peut-être que vous voulez une implémentation réelle (littéralement) récursive. Les approches itératives ou optimisées pour les appels de queue ont besoin de O(1) d'espace de pile, par opposition à votre O(log2 n).