я пытаюсь выяснить, почему этот ассемблерный код x86 для идентификатора палиндромов считает все палиндромом - PullRequest
Новая
       46

я пытаюсь выяснить, почему этот ассемблерный код x86 для идентификатора палиндромов считает все палиндромом

0 голосов
/ 22 марта 2020

. Я занимался этим несколько дней, и, несмотря на просмотр всех других ответов на эту проблему на этом сайте, я не могу понять, что я делаю неправильно. Кто-нибудь может мне помочь? Почему-то, когда я перемещаю значения каждой строки, используя [esi] и [edi] в al и dl соответственно. Когда эти значения в конечном итоге сравниваются, они всегда устанавливают нулевой флаг, независимо от того, равны ли значения 

BufSize = 80
.data
msg BYTE "Input a string for reversal: ",0
msg1 BYTE "palindrome",0
msg2 BYTE "not palindrome",0
buffer BYTE BufSize DUP(?),0,0
bytesRead DWORD ?
string1 DWORD ?
string2 DWORD ?
   TEMP1 DW 0
   PALMESSAGE DB "  THE PROVIDED STRING IS A PALINDROME $"
   NOTPALMESSAGE DB "  THE PROVIDED STRING IS NOT A PALINDROME $"
.CODE
main proc

; Wait for user input
    mov edx, OFFSET buffer
    mov ecx, SIZEOF buffer
    call ReadString
    mov bytesRead, eax
    mov string1, edx
    mov ecx, bytesread
    mov esi,0

COMPARE:
   MOVZX EAX, buffer[esi]
   push eax
   inc esi
   LOOP COMPARE

    mov ecx,bytesRead
    mov esi,0

    L2: 
    pop eax ; get character
    mov buffer[esi],al  ; store in string
    inc esi
    Loop L2

    mov string2, offset buffer
    mov ecx, bytesread
    mov edx, string2
    call writestring

    mov ecx,bytesRead
    mov esi,0
    mov edi,0
    ;mov eax,0
    ;mov edx,0
    mov esi, string1
    mov edi, string2

    L3:
       mov  al, [esi]
       mov  dl, [edi]
       cmp al,0 ; end of string1?
       jne L4 ; no
       cmp dl,0 ; yes: end of string2?
       jne L4 ; no
       jmp pal ; yes, exit with ZF = 1
   L4: 
       inc esi ; point to next
       inc edi
       cmp al,dl ; characters equal?
       je L3 ; yes: continue loop
       jmp notpal         ; no: exit with flags set

PAL:  
    mov edx, OFFSET msg1
    call WriteString
    call crlf
   JMP FIN   
NOTPAL:   
    mov edx, OFFSET msg2
    call WriteString
    call crlf
FIN:


    exit
main ENDP
END main

1 Ответ

1 голос
/ 22 марта 2020

Похоже, вы используете тот же буфер для обратной строки, который вы использовали для начального ввода. Строка1 содержит тот же указатель, что и строка2. Так что, конечно, они сравниваются равными; по крайней мере, это хороший признак того, что остальная часть вашего кода может работать.

Когда эти значения в конечном итоге сравниваются, они всегда устанавливают нулевой флаг, независимо от того, равны ли значения

cmp al,dl определенно не установит ZF, если значения в al и dl` отличаются. Если вы думаете, что это происходит, вы используете свой отладчик неправильно. Это должно позволить вам проверять регистры / память, пока вы выполняете пошаговый код. В идеале даже выделение регистров, которые были изменены последней инструкцией.

Ваш неуклюжий неэффективный алгоритм выглядит так, как будто он будет работать, если вы используете отдельный буфер, если других ошибок нет.

Неэффективно, потому что он повторяется один раз, чтобы расширить строку до 4 байтов на символ в стеке, затем повторяется по нему снова для сохранения в буфере, а затем повторяется по нему снова , чтобы проверить равенство.

Стандартный алгоритм состоит в том, чтобы начинать с указателей на голову / хвост и l oop, пока они не встретятся в середине, O (n) времени, O (1) дополнительного пробела и в лучшем случае O (1) времени выполнения, если первый / последний байты отличаются. (Обращение сначала стоит O (n) времени и дополнительного пространства, прежде чем делать хотя бы одно сравнение). На x86 вы можете даже проверять 4 или 16 байтов за раз с bswap или pshufb, чтобы инвертировать байты в целочисленном или XMM-регистре, еще больше уменьшая постоянный коэффициент. (Но если сделать короткие строки особым случаем.)

Кстати, ваше сравнение l oop также может быть оптимизировано:

Обратите внимание, что если al != 0, вы можете поймать dl == 0 регистр конца строки как часть al != dl. Реализация strcmp должна проверять только строки друг против друга и одну строк на завершающий ноль.

...