AVR无恢复除法：如何避免除数最高位置位时的代码膨胀？

问题本质 #

原实现里，当除数最高有效位（MSB）置位时，无恢复除法的初始余数为0，第一次执行sub/sbc减除数操作会直接触发借位，导致后续商位的判断逻辑完全混乱，不得不额外加zeroOne这类特殊分支处理。但这类分支的指令量会随操作数位数增加而大幅增长，严重拖慢运算速度，还破坏了无恢复除法的简洁性。

核心解决思路 #

要消除特殊分支，关键是先对除数和被除数做左对齐预处理：

• 循环左移除数，直到它的MSB位于32位操作数的最高位（即第31位），同时记录左移的次数shift_cnt
• 被除数同步左移相同的次数shift_cnt
• 执行标准的无恢复除法循环，此时预处理后的除数MSB固定在最高位，初始余数减除数的操作逻辑完全统一，不会出现异常
• 最后将得到的商右移shift_cnt次，还原出正确的商值

这种预处理只需要少量循环指令，且操作数位数增加时，预处理的指令量不会线性增长，完全保留无恢复除法的速度优势。

修改后的代码实现 #

#define quotient    __tmp_reg__
#define byteCnt     r23          ; 循环计数
#define dividend    r_arg1HH
#define shift_cnt   r22          ; 对齐左移次数

__udivmodsi4NonRestoring:       ; 返回：arg2=商, arg1=余数 (arg1=被除数, arg2=除数)
    ; 第一步：对齐除数和被除数，将除数MSB移到32位最高位
    clr     shift_cnt
    clr     r_remHH
    clr     r_remHL
_align_loop:
    ; 检查除数MSB是否已在32位最高位（r_arg2HH的第7位）
    sbrc    r_arg2HH, 7
    rjmp    _align_done
    ; 左移除数1位
    lsl     r_arg2L
    rol     r_arg2H
    rol     r_arg2HL
    rol     r_arg2HH
    ; 左移被除数1位
    lsl     r_arg1L
    rol     r_arg1H
    rol     r_arg1HL
    rol     r_arg1HH
    inc     shift_cnt
    rjmp    _align_loop
_align_done:

    ; 初始化无恢复除法变量
    mov     r_remL, r_remHL
    mov     r_remH, r_remHH
    ldi     byteCnt, 4
    ldi     quotient, 1

_udivmodsi4_pos:
    lsl     dividend            ; 1. 左移被除数
    rol     r_remL              ; 2-5. 将被除数位移入余数
    rol     r_remH
    rol     r_remHL
    rol     r_remHH
subtract:
    sub     r_remL, r_arg2L     ; 6-9. 余数减除数
    sbc     r_remH, r_arg2H
    sbc     r_remHL, r_arg2HL
    sbc     r_remHH, r_arg2HH
    brcs    _udivmodsi4_nep     ; 余数为负，跳转到恢复逻辑
    sec                         ; 商位设为1
_udivmodsi4_ep:
    rol     quotient            ; 将商位移入quotient
    brcc    _udivmodsi4_pos     ; 继续处理下一位
    dec     byteCnt
    breq    _post_shift

byteLoop:
    ; 移位商字节
    mov     r_arg1HH, r_arg1HL
    mov     r_arg1HL, r_arg1H
    mov     r_arg1H , r_arg1L
    mov     r_arg1L , quotient
    ldi     quotient, 1
    sbrc    r_arg1L, 0
    rjmp    _udivmodsi4_pos
_udivmodsi4_neg:
    lsl     dividend            ; 1. 左移被除数
    rol     r_remL              ; 2-5. 将被除数位移入余数
    rol     r_remH
    rol     r_remHL
    rol     r_remHH
    add     r_remL, r_arg2L     ; 6-9. 余数加除数（恢复）
    adc     r_remH, r_arg2H
    adc     r_remHL, r_arg2HL
    adc     r_remHH, r_arg2HH
    brcs    _udivmodsi4_ep      ; 余数恢复为正，跳转到商位处理
_udivmodsi4_nep:
    lsl     quotient            ; 商位设为0
    brcc    _udivmodsi4_neg     ; 继续处理下一位
    dec     byteCnt
    brne    byteLoop
    ; 最后恢复余数
    add     r_remL , r_arg2L
    adc     r_remH , r_arg2H
    adc     r_remHL, r_arg2HL
    adc     r_remHH, r_arg2HH

_post_shift:
    ; 将商右移shift_cnt次，还原正确值
    mov     r_arg2L , quotient
    mov     r_arg2H , r_arg1L
    mov     r_arg2HL, r_arg1H
    mov     r_arg2HH, r_arg1HL
_shift_loop:
    tst     shift_cnt
    breq    _set_remainder
    ; 右移商32位
    lsr     r_arg2HH
    ror     r_arg2HL
    ror     r_arg2H
    ror     r_arg2L
    dec     shift_cnt
    rjmp    _shift_loop

_set_remainder:
    ; 设置余数返回值
    mov     r_arg1L , r_remL
    mov     r_arg1H , r_remH
    mov     r_arg1HL, r_remHL
    mov     r_arg1HH, r_remHH
    ret                         ; 最坏情况<500周期

改动说明 #

1. 移除特殊分支：删掉了原代码中的zeroOne分支及对应的判断指令，所有情况统一走对齐+标准无恢复除法流程
2. 对齐预处理：新增的_align_loop循环负责将除数MSB移到32位最高位，同时同步左移被除数，记录移位次数
3. 商修正：除法完成后，通过_shift_loop将商右移对应次数，还原出正确的商值
4. 保留速度优势：对齐预处理的循环次数最多31次（32位操作数），但实际平均次数远低于此，且无恢复除法的核心循环完全没有额外分支，整体速度和原实现的标准路径相当，同时消除了特殊场景的额外开销

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