如何将ARM模式下int32_t插入排序汇编修改为适配uint16_t半字排序

背景说明 #

以下为用于排序完整有符号字（int32_t）的第一版代码，逻辑与后续给出的C++参考代码完全对齐。

我尝试将其修改为可排序uint16_t无符号半字的版本，目前代码基本完成但存在逻辑缺失，排序功能无法正常运行。本次适配的目标架构为ARM（ARM模式，非Thumb模式），当前已完成的代码如下：

sort:   STMFD   SP!,{R4-R6,LR}
        MOV     R2,#1   //for (unsigned i = 1;
L1:     CMP     R2,R1
        BHS     L4      //                     i < toSort.size();
        MOV     R3,R2   //      for (unsigned j = i
L2:     SUBS    R3,R3,#1//                          - 1;          --j)
        BLO     L3      //                               j != -1;
        ADD     R6,R0,R3,LSL #2
        LDRH    R4,[R6]
        LDRH    R5,[R6,#2]
        CMP     R5,R4   //              if (toSort[j+1] < toSort[j])
        STRHT   R4,[R6,#2]
        STRHT   R5,[R6] //                      swap(toSort[j], toSort[j+1]);
        BLT     L2     
L3:     ADD     R2,R2,#1//              else break;               ++i)
     B       L1      
L4:     LDMFD   SP!,{R4-R6,PC}

需要对齐的C++参考逻辑如下：

void insertionSort(vector<int>& toSort) 
{                                       
        for (int i = 1; i < toSort.size(); ++i)
                for (int j = i - 1; j >= 0; --j)
                        if (toSort[j+1] < toSort[j])
                                swap(toSort[j], toSort[j+1]);
                        else
                                break; 
}

错误点排查&修复 #

你的代码存在两处核心逻辑错误，直接导致排序失效：

• 地址偏移计算错误：原int32_t版本每个元素占4字节，因此索引j需要左移2位（乘以4）计算地址偏移；但uint16_t每个元素仅占2字节，偏移应该左移1位（乘以2），对应修改ADD R6,R0,R3,LSL #2为ADD R6,R0,R3,LSL #1
• 无符号数条件码误用：你操作的是无符号uint16_t，但代码中使用了有符号场景的条件码：
  • 跳转指令BLT是有符号小于跳转，需要替换为适配无符号数的BLO（无符号低于跳转）
  • 条件存储指令STRHT是有符号小于条件存储，需要替换为适配无符号数的STRHLO（无符号低于条件存储）

修复后的完整可用代码如下：

sort:   STMFD   SP!,{R4-R6,LR}
        MOV     R2,#1   // 外层循环初始化 i = 1
L1:     CMP     R2,R1
        BHS     L4      // i >= 数组长度则退出排序
        MOV     R3,R2   // 内层循环初始化 j = i
L2:     SUBS    R3,R3,#1// j自减1
        BLO     L3      // j < 0则退出内层循环
        ADD     R6,R0,R3,LSL #1  // 按uint16_t宽度2字节计算元素地址
        LDRH    R4,[R6]
        LDRH    R5,[R6,#2]
        CMP     R5,R4   // 无符号比较相邻元素大小
        STRHLO  R4,[R6,#2]
        STRHLO  R5,[R6] // 若后一个元素更小则交换
        BLO     L2      // 交换后继续向前比较
L3:     ADD     R2,R2,#1// 无需交换则进入下一轮外层循环
        B       L1      
L4:     LDMFD   SP!,{R4-R6,PC}

调用约定 #

调用该汇编函数时，约定R0传入uint16_t数组首地址，R1传入数组元素总个数即可正常运行。

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