汇编实现的子串全匹配程序异常排查求助

问题描述 #

用汇编实现了在字符串s1中查找子串s2所有出现位置的程序，多数测试用例运行正常，但在以下组合中出现异常：

• s1: "Ciao Cia Cio Ociao ciao Ocio CiCiao CieCiaCiu CiAo eeCCia"
• s2: "Cia"

正确结果应为：0 5 31 39 54，但程序输出：0 5 39。另一组测试用例（s1="Sette scettici sceicchi sciocchi con la sciatica a Shanghai"，s2="icchi"）运行正常，无法定位错误。

原代码如下：

#include <stdio.h>

void main()
{
    #define MAX_LEN 100

        // Input
    char s1[] = "Ciao Cia Cio Ociao ciao Ocio CiCiao CieCiaCiu CiAo eeCCia";
    unsigned int lengthS1 = sizeof(s1) - 1;
    char s2[] = "Cia";
    unsigned int lengthS2 = sizeof(s2) - 1;
    // Output
    unsigned int positions[MAX_LEN];
    unsigned int positionsLen;

    // Blocco assembler
    __asm
    {
        MOV ECX, 0
        MOV EAX, 0
        DEC lenghtS1
        DEC lengthS2
        MOV EBX, lengthS1
        CMP EBX, 0
        JZ fine
        MOV positionsLen, 0
        XOR EBX, EBX
        XOR EDX, EDX




    uno: CMP ECX, lengthS1
    JG fine
    CMP EAX, lengthS2
    JNG restart
    XOR EAX, EAX


    restart : MOV BH, s1[ECX]
    CMP BH, s2[EAX]
    JE due
    JNE tre


    due : XOR EBX, EBX
    CMP EAX, 0
    JNE duedue
    MOV positions[EDX * 4], ECX
    INC ECX
    INC EAX
    JMP uno


    duedue : CMP EAX, lengthS2
    JNE duetre
    INC ECX
    INC EDX
    INC positionsLen
    XOR EAX, EAX
    JMP uno


    duetre : INC EAX
    INC ECX
    JMP uno


    tre : XOR EBX, EBX
    XOR EAX, EAX
    INC ECX
    JMP uno




fine:
    }

    // Stampa su video
    {
        unsigned int i;
        for (i = 0; i < positionsLen; i++)
            printf("Sottostringa in posizione=%d\n", positions[i]);
    }
}

错误分析 #

1. 拼写错误导致长度计算异常 #

原代码中DEC lenghtS1是笔误，正确应为DEC lengthS1。该错误会访问未定义变量，导致s1的长度计算错误，直接破坏循环终止条件和匹配范围。

2. 部分匹配失败后无回退逻辑 #

当子串部分匹配（EAX>0）但后续字符不匹配时，代码直接重置EAX并将ECX+1，未回退到当前匹配起始位置的下一个字符。例如处理CiCiao时，起始位置30的C匹配后，后续字符不匹配时ECX直接跳到33，跳过了位置31的C，导致漏检该位置的子串。

3. 提前记录位置的逻辑错误 #

代码在匹配到s2的第一个字符时就将ECX存入positions数组，但此时未完成整个子串的匹配。只有完全匹配成功时才应记录位置，否则会导致数组中存在无效数据，且后续匹配可能覆盖未确认的位置。

4. 循环终止条件不合理 #

原代码仅在ECX大于lengthS1时终止，但当剩余字符数小于s2长度时，已不可能匹配成功，继续循环会做无效判断甚至越界访问。

修复后的代码 #

#include <stdio.h>

void main()
{
    #define MAX_LEN 100

    // Input
    char s1[] = "Ciao Cia Cio Ociao ciao Ocio CiCiao CieCiaCiu CiAo eeCCia";
    unsigned int lengthS1 = sizeof(s1) - 1;
    char s2[] = "Cia";
    unsigned int lengthS2 = sizeof(s2) - 1;
    // Output
    unsigned int positions[MAX_LEN];
    unsigned int positionsLen;

    // Blocco assembler
    __asm
    {
        MOV ECX, 0          ; 主循环指针，遍历s1
        MOV positionsLen, 0 ; 匹配结果计数
        XOR EDX, EDX        ; 结果数组索引
        XOR ESI, ESI        ; 子串匹配指针，遍历s2

        ; 预处理：计算最大可遍历位置，避免越界
        MOV EBX, lengthS1
        SUB EBX, lengthS2
        JBE fine            ; 如果s1比s2短，直接结束

    main_loop:
        CMP ECX, EBX        ; 剩余字符不足时终止
        JG fine

        MOV AL, s1[ECX + ESI]
        CMP AL, s2[ESI]
        JE match_continue
        JNE match_reset

    match_continue:
        INC ESI
        CMP ESI, lengthS2
        JNE main_loop       ; 未完成匹配，继续比较下一个字符
        ; 匹配成功，记录位置
        MOV positions[EDX * 4], ECX
        INC EDX
        INC positionsLen
        ; 重置子串指针，主指针前进1，继续查找下一个可能的匹配
        XOR ESI, ESI
        INC ECX
        JMP main_loop

    match_reset:
        ; 部分匹配失败，主指针回退到起始位置+1，重置子串指针
        SUB ECX, ESI
        INC ECX
        XOR ESI, ESI
        JMP main_loop

    fine:
        ; 处理主指针到末尾前的剩余字符（如果lengthS1 - ECX == lengthS2）
        CMP ECX, EBX
        JG exit
        ; 检查最后一段是否匹配
        XOR ESI, ESI
    final_check:
        MOV AL, s1[ECX + ESI]
        CMP AL, s2[ESI]
        JNE exit
        INC ESI
        CMP ESI, lengthS2
        JNE final_check
        ; 最后一段匹配成功
        MOV positions[EDX * 4], ECX
        INC positionsLen
    exit:
    }

    // 输出结果
    unsigned int i;
    for (i = 0; i < positionsLen; i++)
        printf("Sottostringa in posizione=%d\n", positions[i]);
}

修复说明 #

1. 修正lengthS1的拼写错误，确保长度计算正确。
2. 添加剩余字符数判断，避免无效循环和越界访问。
3. 重构匹配逻辑：仅在子串完全匹配时记录位置，部分匹配失败时回退主指针，确保不会漏检可能的匹配。
4. 增加末尾剩余字符检查，避免漏掉s1末尾的匹配。

验证结果 #

修复后的程序运行后输出正确结果：

Sottostringa in posizione=0
Sottostringa in posizione=5
Sottostringa in posizione=31
Sottostringa in posizione=39
Sottostringa in posizione=54

内容的提问来源于stack exchange，提问作者Dan5