c - 使用NASM构建KMP前缀

我正在尝试在NASM中实现以下C代码，然后将其链接到C程序并从那里运行。

我正在尝试实现的代码:

   void preKmp(char *x, int m, int kmpNext[]) {
   int i, j;

   i = 0;
   j = kmpNext[0] = -1;
   while (i < m) {
      while (j > -1 && x[i] != x[j])
         j = kmpNext[j];
      i++;
      j++;
      if (x[i] == x[j])
         kmpNext[i] = kmpNext[j];
      else
         kmpNext[i] = j;
   }
}

我在NASM中的尝试和评论:

;nasm -f elf32 table.asm -o table.o

segment .bss
kmpNext resd 256


segment .text
global table

table:
    push ebp          ;save the old base pointer value
    mov  ebp,esp      ;base pointer <- stack pointer

    mov eax,[ebp+8]     ;function argument, eax = search_string
    mov ecx, 0          ;i = 0
    mov edx, -1         ;j = -1
    mov [kmpNext], edx  ;kmpNext[0] = -1
oWhile:
    cmp byte [eax + ecx*4], 0  ;end of array control
    je finished
iWhile:
    cmp edx, -1
    jle pass
    mov edi,[eax + ecx*4] ;edi = x[i]
    mov esi,[eax + edx*4] ;esi = x[j]
    cmp edi, esi
    je pass
    mov edx, [kmpNext +edx*4] ;j = kmpNext[j]
pass:
    inc ecx
    inc edx
    mov edi,[eax + ecx*4] ;edi = x[i]
    mov esi,[eax + edx*4] ;esi = x[j]
    cmp edi, esi
    jne store
    mov edi, [kmpNext + edx*4]  ;edi = kmpNext[j]
    mov [kmpNext + ecx*4], edi  ;kmpNext[i] = edi
store:
    mov [kmpNext + ecx*4], edx  ;kmpNext[i] = j
    jmp oWhile
finished:
    mov eax, kmpNext;

    pop ebp
    ret

我在其中调用NASM函数的C代码:

#include <stdio.h>
#include <string.h>

int* table(char *str);

int main(void)
{
    char str[256];
    int i, n, *pre;

    printf("Enter string: ");
    scanf("%s" , str) ;
    n = strlen(str);
    pre = table(str);
    for (i = 0; i < n; i++){
      printf("%d ", pre[i]);

    }
    printf("\n");
    return 0;
}

一切都能编译并运行正常，但输出错误。例如，

对于“可口可乐”，我应该得到:-1 -1 0 -1 0 1 -1 -1

我在哪里:-1 0 0 0 0 0 0 0

有人可以指出我在NASM代码中的错误吗？

我怀疑问题在于此行:

mov esi，[eax + ecx * 4]

运行调试器时，看不到esi内容的变化。

最佳答案

1)主要错误是，str是字节(8位)数组，但是您将其视为整数(32位)数组。

2)有两个while循环。 他们两个都需要跳回以重复。

3)store是else -case。如果if -case适合，则它不能运行。在这种情况下，跳转到oWhile是适当的。

这是更正的功能:

table:
    push ebp          ;save the old base pointer value
    mov  ebp,esp      ;base pointer <- stack pointer

    push edi          ; callee saved
    push ebx

    mov eax,[ebp+8]     ;function argument, eax = search_string
    mov ecx, 0          ;i = 0
    mov edx, -1         ;j = -1
    mov [kmpNext], edx  ;kmpNext[0] = -1

oWhile:
    cmp byte [eax + ecx], 0  ;end of array control
    je finished

iWhile:
    cmp edx, -1
    jle pass

    mov bl,[eax + ecx] ; bl = x[i]
    mov bh,[eax + edx] ; bh = x[j]
    cmp bl, bh

    je pass
    mov edx, [kmpNext +edx*4] ;j = kmpNext[j]
    jmp iWhile

pass:
    inc ecx
    inc edx

    mov bl,[eax + ecx] ; bl = x[i]
    mov bh,[eax + edx] ; bh = x[j]
    cmp bl, bh

    jne store
    mov edi, [kmpNext + edx*4]  ;edi = kmpNext[j]
    mov [kmpNext + ecx*4], edi  ;kmpNext[i] = edi

    jmp oWhile

store:
    mov [kmpNext + ecx*4], edx  ;kmpNext[i] = j
    jmp oWhile

finished:
    mov eax, kmpNext;

    pop ebx
    pop edi
    pop ebp
    ret

关于c - 使用NASM构建KMP前缀，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32948730/