assembly

Question

我正在尝试使用 MSVC 程序集 8086 内联列出前 N 个自然数 (N <= 6) 的所有排列。我无法更改 C 程序的任何内容，我只能管理汇编代码。所以这就是我所做的（并且使用 N <= 3），使用字典算法：

#include <stdio.h>
int main() {
// Variabili
int N=4;    // N <= 6
int Perm[4326];    // permutations array: the dimension is sufficient for N <= 6
int Num;     // At the end it must contains the number of generated permutations
// Assembler block
__asm
{
    XOR EAX, EAX    ; Reset EAX (permutations counter)
    MOV ECX, N        ; Put N into ECX
    CMP ECX, 1        ; Compare ECX and 1
    JBE Piccolo        ; If ECX <= 1 go to Piccolo (particular cases 1 and 0)
    DEC ECX        ; Decrement ECX (so ECX = N - 1)
    MOV EAX, N    ; Put N into EAX
    MaxPerm:
        MUL ECX            ; Do EDX:EAX = EAX * ECX
        LOOP MaxPerm    ; Loop to find permutations number
    MOV Num, EAX    ; Move EAX (permutations number) into Num
    MOV EAX, 1        ; Set EAX (permutations number) to 1
    MOV EBX, 0        ; Reset EBX (EBX = 0)
    MOV ECX, 1        ; Reset ECX
    CicloIniziale:
        DEC ECX                    ; Decrement ECX (to compare it with N)
        CMP ECX, N                ; Compare ECX and N
        JE Permutazione            ; If ECX == N the first permutation has been written, skip to the generation of the next ones
        INC ECX                    ; Else increment ECX
        MOV Perm[4*EBX], ECX    ; Insert ECX into the Perm array
        INC ECX                    ; Increment ECX
        INC EBX                    ; Increment EBX
        JMP CicloIniziale        ; Continue the loop
    Permutazione:
        XOR EAX, EAX    ; Local index
        XOR EBX, EBX    ; Previous permutation index
        MOV ECX, N        ; Current permutation index
        MOV EDI, 1        ; Value of k
        MOV ESI, 1        ; New position of k
        
        CicloPermutazione:
            CMP EAX, N                ; Compare ECX and EAX
            JE ResetPerm            ; If the end of the permutation has been reached, go to ResetPerm
            MOV EDX, Perm[4*EBX]    ; Otherwise save the element of the previous permutation in position EBX in EDX
            CMP EDX, EDI            ; Compare EDX and EDI
            JE ValoreUguale            ; If they are equal, then go to ValoreUguale
            CMP EAX, ESI            ; Otherwise compare EBX and ESI
            JE InserisciElSpostato    ; If it's time to move the item, go to InserisciElSpostato
            MOV Perm[4*ECX], EDX    ; Returns the value of the previous permutation to the new permutation
            ContinuaCiclo:
                INC EBX                    ; Increment the previous permutation index
                INC EAX                    ; Increment the local index
                INC ECX                    ; Increment the new permutation index
                JMP CicloPermutazione    ; Continue the loop
        
            InserisciElSpostato:
                MOV Perm[4*ECX], EDI    ; Put EDI in the new permutation
                MOV EDX, N                ; EDX = N
                DEC EDX                    ; EDX -= 1
                CMP ESI, EDX            ; Compare ESI and EDX
                JE ResettaK                ; If ESI == EDX go to ResettaK
                JMP ContinuaCiclo        ; Continue the loop
            
            ValoreUguale:
                CMP EAX, 0                ; Confronta EAX e 0
                JZ PrimaPos                ; If EAX == 0 (first position) go to PrimaPos
                MOV EDX, Perm[4*EBX+4]    ; Else save the element into position EBX - 1
                MOV Perm[4*ECX], EDX    ; Insert EDX in the new permutation
                JMP ContinuaCiclo        ; Continue the loop
                
                PrimaPos:
                    MOV EDX, Perm[4*EBX+4]    ; Save into EDX the element in position ECX + 1
                    MOV Perm[4*ECX], EDX    ; Insert EDX into the new permutation
                    JMP ContinuaCiclo        ; Continue the loop
            ResettaK:
                XOR ESI, ESI            ; Reset ESI
                MOV EDI, Perm[4*EDI]    ; EDI = Perm[EDI]
                JMP ContinuaCiclo        ; Continue the loop
            ResettaKN:
                CMP EDI, N            ; Compare EDI and N
                JNE ContinuaCiclo    ; if EDI != N then continue the loop
                JMP ResettaK        ; Else go to ResettaK
        ResetPerm:
            MOV EAX, Num            ; EAX = Num
            MUL DWORD PTR N            ; EAX *= N (Elements of number of all the permutations)
            CMP EAX, ECX            ; Compare EAX and ECX
            JE Fine                    ; If EAX == ECX (permutations done) then finish the program
            XOR EAX, EAX            ; Otherwise reset EAX
            INC ESI                    ; Increment k index
            JMP CicloPermutazione    ; Continue the loop
    Piccolo:            ; If N = 0 or N = 1, the only permutation that can exists is made by only 1 element
        MOV Num, 1
        MOV Perm[0], ECX
        
    Fine:
}
// Print
{
    int i,j,k;
    printf("%d permutations of the first %d natural numbers\n", Num, N);
    for (i=k=0;i<Num;i++)
    {
        for (j=0;j<N;j++)
        {
            printf("%3d",Perm[k++]);
        }
        printf("\n");
    }
}
return 0;
}

问题是这个程序只适用于 N <= 3 而我没有发现问题！这些是我得到的输出：

N = 3 及以下工作正常：

6 permutations of the first 3 natural numbers
1  2  3
2  1  3
2  3  1
3  2  1
3  1  2
1  3  2

N = 4（同5和6）：

24 permutations of the first 4 natural numbers
1  2  3  4
2  1  3  4
2  3  1  4
2  3  4  1
3  2  4  1
3  4  2  1
3  4  1  2
4  3  1  2
4  1  3  2
4  1  2  3
1  4  2  3
1  2  4  3
1  2  3  4
1  3  3  4
1  3  2  4
1  3  4  2
1  4  4  2
1  4  3  2
1  4  2  3
1  2  2  3
1  2  4  3
1  2  3  4
1  3  3  4
1  3  2  4

正如您所看到的，在第一个循环的最后一个排列之后，接下来的排列就乱七八糟了...

你能帮帮我吗？谢谢

Answer 1

您写了几行代码，其中代码与随附的注释不匹配。如果我是你，我会怀疑在那里发现可能的错误。

CMP EAX, N             ; Compare ECX and EAX
CMP EAX, ESI           ; Otherwise compare EBX and ESI
MOV EDX, Perm[4*EBX+4] ; Else save the element into position EBX - 1
MOV EDX, Perm[4*EBX+4] ; Save into EDX the element in position ECX + 1

这将是与评论匹配的代码：

cmp ecx, eax
cmp ebx, esi
mov edx, Perm[4*ebx - 4]  ; 'save' == 'save into EDX' (*)
mov edx, Perm[4*ecx + 4]

我并不是说这些会解决问题，因为也许您的注释是错误的而您的代码是正确的。

(*) 而不是非常混乱的短语“save into EDX”，最好写成“load EDX with/from[=39” =]".

您写了很多多余的评论。
以下是其中的一小部分：

MOV EAX, N ; Put N into EAX MOV EBX, 0 ; Reset EBX (EBX = 0) CMP ECX, 1 ; Compare ECX and 1 INC ECX ; Increment ECX INC EBX ; Increment EBX

MOV EDX, N ; EDX = N DEC EDX ; EDX -= 1 CMP ESI, EDX ; Compare ESI and EDX JE ResettaK ; If ESI == EDX go to ResettaK

帮自己一个忙，不要再写这些多余的评论了。它们使任何人（包括您自己）（尝试）理解代码变得更加困难。

最近的一篇博客 post 讨论了编写代码注释的主题：https://Whosebug.blog/2021/07/05/best-practices-for-writing-code-comments/

Answer 2

最后，我设法编写了一个 C 程序，它使用 C++ STD 库的 next_permutation 函数的算法来完成这项工作。然后，我在 Godbolt（在线编译器）的帮助下将 C 代码翻译成汇编。

所以：

使用next_permutation函数编写C程序：https://godbolt.org/z/7avGaWfha
展开main中的所有函数：https://godbolt.org/z/7z9MGWefK
最后在Godbolt的大力帮助下，翻译成汇编

assembly - 排列生成问题

assembly - Issue with permutations generation

c

x86

permutation

inline-assembly