Motorola 68000汇编冒泡排序优化咨询：基于ROL的降序字节数组排序

原代码问题与优化方向 #

1. 冗余/错误指令移除与简化 #

以下是原代码中可移除或简化的指令，部分同时修正了逻辑bug：

• 移除SWAP中的move.b -1(a0),d3：INNER_LOOP中move.b (a0)+,d2已经将左元素加载到d2的低8位，这条加载指令完全冗余，直接复用d2即可。
• 移除SWAP中的addq.l #1,a0：这条指令会导致数组指针额外前进，跳过下一组需要比较的元素，属于逻辑错误+冗余操作——INNER_LOOP的move.b (a0)+会自动推进指针，无需手动调整。
• 简化交换存储逻辑：原代码中用d5提取右元素、andi.w #$00FF,d3提取左元素的步骤可简化：旋转后的寄存器高8位为右元素，低8位为左元素，通过lsr.w #8提取右元素，利用move.b自动取低8位的特性存储左元素，省掉冗余的掩码操作和寄存器拷贝。

2. 循环结构效率优化 #

针对冒泡排序的特性和68000架构特性，可从以下几点优化循环：

• 用dbra指令替代subq+bge组合：dbra是68000专为循环设计的单周期指令，执行效率高于subq.l #1,dX + bge.s LOOP的组合，同时代码更紧凑。注意dbra的计数逻辑：初始值设为循环次数-1，指令会自动递减计数，当计数≥-1时继续循环。
• 添加"无交换"标记，提前终止排序：冒泡排序中，若某一轮没有发生任何交换，说明数组已经完全有序，可直接终止排序。用寄存器（如d5）记录是否发生交换，外层循环结束后检查标记，避免不必要的循环。
• 记录最后交换位置，减少比较次数：通过寄存器记录最后一次交换的数组位置，下一轮内层循环只需比较到该位置之前，无需对已经有序的尾部元素重复比较，进一步减少循环次数。

优化后的代码示例 #

ORG $8000
    
START:
      moveq.l #len-1,d7        ; 初始外层循环次数
      lea.l array,a0           ; 初始化数组指针（仅执行一次）

OUTER_LOOP:
      moveq.l #-1,d5           ; d5标记最后一次交换的位置，初始为-1（无交换）
      moveq.l #len-2,d6        ; 内层循环比较次数

INNER_LOOP: 
      move.b (a0)+,d2    
      cmp.b (a0),d2      
      blt.s SWAP               ; 左元素小于右元素，执行交换
     
NOSWAP: 
      dbra d6, INNER_LOOP      ; 递减计数，未完成则继续内层循环
      
      tst.l d5                 ; 检查是否发生过交换
      bmi.s SORT_DONE          ; 无交换则直接结束排序
      
      lea.l array,a0           ; 重置指针到数组开头
      dbra d7, OUTER_LOOP      ; 递减外层计数，继续循环

SORT_DONE:
      SIMHALT           
      
SWAP:
    move.b  (a0),d4            ; 加载右元素到d4低8位
    lsl.w   #8,d2              ; 左元素移到d2高8位
    or.w    d4,d2              ; 合并为 [左][右] 的16位值
    rol.w   #8,d2              ; 循环左移8位，得到 [右][左] 的16位值
    
    move.w  d2,d3
    lsr.w   #8,d3              ; 提取右元素到d3低8位
    move.b  d3,-1(a0)          ; 将右元素存入左位置
    move.b  d2,(a0)            ; 将左元素存入右位置（自动取d2低8位）
    
    move.l a0,d5               ; 更新最后交换的位置为当前指针
    bra.s NOSWAP        

; DATA
array DC.B 5,3,8,1,7    
len EQU 5               

END START

额外说明 #

• dbra指令的使用：内层循环初始值设为len-2，对应len-1次比较操作，符合冒泡排序的内层循环次数要求。
• 最后交换位置的进阶优化：可将内层循环的计数直接设为d5 - array -1，避免对尾部有序元素的重复比较，进一步提升效率。

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