两个 16 位数字的 GCD（最大公约数）
GCD (Greatest Common Divisor) for two 16-bit numbers
这里的目标是为两个以小端表示法存储的 16 位数字找到 GCD。这些数字存储在以下存储单元中：
- 第一个数字：0x3000-0x3001
- 秒数：0x4000-0x4001
- 结果应为：0x5000-0x5001
以下示例适用于 8 位数字：
ORG 0000H
MOV 30H, #09
MOV 40H, #06
MOV A, 30H
MOV B, 40H
CJNE A, B, next
LJMP stop
next:
JNC loop
MOV A, R2
MOV B, R1
loop:
MOV R3, B
DIV AB
MOV A, R3
MOV R7, B
CJNE R7, #00H, loop
stop:
MOV 50H, A
END
问题：如何修改此代码以对两个 16 位数字进行运算？我是否需要对单个字节进行操作，然后使用数据指针 (DPTR) 将它们 load/move 到所需的存储单元？
（我正在使用 µVision IDE）
计算最大公约数的一种方法是使用 Euclid's algorithm。要获得两个 16 位数字的 GCD，需要扩大我们在 8051 上的非常有限的 DIV AB。这并非不可能，但我选择使用一种根本不需要除法的算法。
二进制GCD算法
我们可以避免 8051 有限的除法能力，并使用一种算法，通过一系列移位和减法来代替模数计算。下面是 Binary GCD algorithm 在 BASIC 中的样子：
Procedure BinaryGCD
; Calculates R% = GCD(A%,B%)
If A%=0 Or B%=0 Then
R% = 1
Else
C% = 0
While Even(A%) And Even(B%)
Inc C%
A% = Shr(A%,1)
B% = Shr(B%,1)
Wend
Do
While Even(A%)
A% = Shr(A%,1)
Wend
While Even(B%)
B% = Shr(B%,1)
Wend
Exit If A%=B%
If A%>B% Then
Sub A%,B%
Else
Sub B%,A%
Endif
Loop
R% = Shl(A%,C%)
Endif
Return
实施说明
将存储在外部存储器中的数字复制到内部存储器中的位地址区。为什么是这样？使用内部存储器避免了必须一直操作 16 位地址的麻烦。并且专门使用位地址区域，允许编写用于测试 even/odd 条件的高效代码。在位地址区域之外存储需要更多字节和更多周期，更不用说它会破坏累加器。比较：
; Multiprecision number starts at 58h (not bit addressable)
MOV A, #1
ANL A, 58h
JNZ IsOdd
; Uses 6 bytes and consumes 4 cycles
; Multiprecision number starts at 28h (bit addressable)
JB 64, IsOdd
; Uses 3 bytes and consumes 2 cycles
请注意，我的程序可以处理从字节到 qword 以及介于两者之间的所有内容的无符号多精度数字。我首先创建了一系列方便的子例程来处理多字节数字。这些子例程中的许多都被调用一次，因此也可以轻松地内联。为了生成一个可读的程序，我选择不这样做。
子程序
IN()
对于每个子例程，R0、R1 和 DPTR 寄存器在输入时是指向所涉及数字开头的指针（最低有效字节，因为这是小端）。
OUT()
在从 mpLoad 和 mpStore 进行 return 时，R1 和 DPTR 都会提前，以便无需重新加载指针寄存器即可处理相邻项。
在从 mpTest 进行 return 时，累加器 A 很重要。如果 A 为零，则提交的数字为零。
在从 mpCmp 进行 return 时，累加器 A 和进位标志 C 很重要。如果 A 为零，则提交的数字彼此相等。否则，明确的 C 表示第一个数字 (@R0) 大于第二个数字 (@R1)，反之亦然 C.
MOD()
这里列出了子例程使用的所有寄存器，但没有 return 记录值。
; Copies a multiprecision number from external memory to internal memory
; IN(R1,DPTR) OUT(R1,DPTR) MOD(A,R2)
mpLoad:
MOV R2, #MPC
Load:
MOVX A, @DPTR
MOV @R1, A
INC DPTR
INC R1
DJNZ R2, Load
RET
; Copies a multiprecision number from internal memory to external memory
; IN(R1,DPTR) OUT(R1,DPTR) MOD(A,R2)
mpStore:
MOV R2, #MPC
Store:
MOV A, @R1
MOVX @DPTR, A
INC DPTR
INC R1
DJNZ R2, Store
RET
; Doubles a multiprecision number
; IN(R1) OUT() MOD(A,R1,R2)
mpShl:
MOV R2, #MPC
CLR C
Shl:
MOV A, @R1
RLC A
MOV @R1, A
INC R1
DJNZ R2, Shl
RET
; Halves a multiprecision number
; IN(R1) OUT() MOD(A,R2)
mpShr:
MOV R2, #MPC
MOV A, R1
ADD A, R2 ; -> C == 0
MOV R1, A
Shr:
DEC R1
MOV A, @R1
RRC A
MOV @R1, A
DJNZ R2, Shr
RET
; Tests if a multiprecision number is zero
; IN(R1) OUT(A) MOD(R1,R2)
mpTest:
MOV R2, #MPC
MOV A, #0
Test:
ORL A, @R1
INC R1
DJNZ R2, Test
RET
; Compares two multiprecision numbers
; IN(R0,R1) OUT(A,C) MOD(R0,R1,R2)
mpCmp:
MOV R2, #MPC
MOV A, R1
ADD A, R2
MOV R1, A
MOV A, R0
ADD A, R2 ; -> C == 0
MOV R0, A
Cmp:
DEC R0
DEC R1
MOV A, @R0
SUBB A, @R1
JNZ CmpRet
DJNZ R2, Cmp
CmpRet:
RET
; Subtracts two multiprecision numbers
; IN(R0,R1) OUT() MOD(A,R0,R1,R2)
mpSub:
MOV R2, #MPC
CLR C
Sub:
MOV A, @R0
SUBB A, @R1
MOV @R0, A
INC R0
INC R1
DJNZ R2, Sub
RET
主要代码
您可以轻松地将它变成一个成熟的程序。
MPC EQU 2 ; Number of bytes per number aka precision
NumX EQU 20h ; Internal memory storage address for first number
NumY EQU 28h ; Internal memory storage address for second number
; -------------------------
MOV R1, #NumX
MOV DPTR, #3000h ; External memory storage address for first number
LCALL mpLoad
MOV R1, #NumY
MOV DPTR, #4000h ; External memory storage address for second number
LCALL mpLoad
; -------------------------
MOV R3, #MPC
MOV R0, #NumX
MOV R1, #NumX
LCALL mpTest ; -> A
JZ SetOne
MOV R1, #NumY
LCALL mpTest ; -> A
JNZ Begin
SetOne:
INC A ; 0 -> 1, 255 -> 0, 255 -> 0, ...
MOV @R0, A
MOV A, #255
INC R0
DJNZ R3, SetOne
SJMP Copy
; -------------------------
Begin:
MOV R3, #0 ; Bits
While1:
JB 0, While3 ; Jump if NumX[bit0] == 1
JB 64, While2 ; Jump if NumY[bit0] == 1
INC R3 ; Bits++
MOV R1, #NumX
LCALL mpShr ; X >> 1
MOV R1, #NumY
LCALL mpShr ; Y >> 1
SJMP While1
; -------------------------
While2:
JB 0, While3 ; Jump if NumX[bit0] == 1
MOV R1, #NumX
LCALL mpShr ; X >> 1
SJMP While2
; - - - - - - - - - - - - -
While3:
JB 64, Compare ; Jump if NumY[bit0] == 1
MOV R1, #NumY
LCALL mpShr ; Y >> 1
SJMP While3
; - - - - - - - - - - - - -
Compare:
MOV R0, #NumX
MOV R1, #NumY
LCALL mpCmp ; -> A C
JZ Equal
MOV R0, #NumX
MOV R1, #NumY
JNC Minus ; Do (X - Y)
MOV R0, #NumY
MOV R1, #NumX
Minus:
LCALL mpSub ; Did (X - Y) or (Y - X)
SJMP While2
; -------------------------
Equal:
MOV A, R3 ; Bits
JZ Copy
Scale: ; X << Bits
MOV R1, #NumX
LCALL mpShl ; X << 1
DJNZ R3, Scale
; -------------------------
Copy:
MOV R1, #NumX
MOV DPTR, #5000h ; External memory storage address for resulting number
LCALL mpStore
; -------------------------
EXIT:
NOP
SJMP $
; Here you add the subroutines
END
这里的目标是为两个以小端表示法存储的 16 位数字找到 GCD。这些数字存储在以下存储单元中：
- 第一个数字：0x3000-0x3001
- 秒数：0x4000-0x4001
- 结果应为：0x5000-0x5001
以下示例适用于 8 位数字：
ORG 0000H
MOV 30H, #09
MOV 40H, #06
MOV A, 30H
MOV B, 40H
CJNE A, B, next
LJMP stop
next:
JNC loop
MOV A, R2
MOV B, R1
loop:
MOV R3, B
DIV AB
MOV A, R3
MOV R7, B
CJNE R7, #00H, loop
stop:
MOV 50H, A
END
问题：如何修改此代码以对两个 16 位数字进行运算？我是否需要对单个字节进行操作，然后使用数据指针 (DPTR) 将它们 load/move 到所需的存储单元？
（我正在使用 µVision IDE）
计算最大公约数的一种方法是使用 Euclid's algorithm。要获得两个 16 位数字的 GCD，需要扩大我们在 8051 上的非常有限的 DIV AB。这并非不可能，但我选择使用一种根本不需要除法的算法。
二进制GCD算法
我们可以避免 8051 有限的除法能力，并使用一种算法，通过一系列移位和减法来代替模数计算。下面是 Binary GCD algorithm 在 BASIC 中的样子：
Procedure BinaryGCD
; Calculates R% = GCD(A%,B%)
If A%=0 Or B%=0 Then
R% = 1
Else
C% = 0
While Even(A%) And Even(B%)
Inc C%
A% = Shr(A%,1)
B% = Shr(B%,1)
Wend
Do
While Even(A%)
A% = Shr(A%,1)
Wend
While Even(B%)
B% = Shr(B%,1)
Wend
Exit If A%=B%
If A%>B% Then
Sub A%,B%
Else
Sub B%,A%
Endif
Loop
R% = Shl(A%,C%)
Endif
Return
实施说明
将存储在外部存储器中的数字复制到内部存储器中的位地址区。为什么是这样？使用内部存储器避免了必须一直操作 16 位地址的麻烦。并且专门使用位地址区域，允许编写用于测试 even/odd 条件的高效代码。在位地址区域之外存储需要更多字节和更多周期，更不用说它会破坏累加器。比较：
; Multiprecision number starts at 58h (not bit addressable)
MOV A, #1
ANL A, 58h
JNZ IsOdd
; Uses 6 bytes and consumes 4 cycles
; Multiprecision number starts at 28h (bit addressable)
JB 64, IsOdd
; Uses 3 bytes and consumes 2 cycles
请注意，我的程序可以处理从字节到 qword 以及介于两者之间的所有内容的无符号多精度数字。我首先创建了一系列方便的子例程来处理多字节数字。这些子例程中的许多都被调用一次，因此也可以轻松地内联。为了生成一个可读的程序，我选择不这样做。
子程序
IN()
对于每个子例程，R0、R1 和 DPTR 寄存器在输入时是指向所涉及数字开头的指针（最低有效字节，因为这是小端）。
OUT()
在从 mpLoad 和 mpStore 进行 return 时，R1 和 DPTR 都会提前，以便无需重新加载指针寄存器即可处理相邻项。
在从 mpTest 进行 return 时，累加器 A 很重要。如果 A 为零，则提交的数字为零。
在从 mpCmp 进行 return 时，累加器 A 和进位标志 C 很重要。如果 A 为零，则提交的数字彼此相等。否则，明确的 C 表示第一个数字 (@R0) 大于第二个数字 (@R1)，反之亦然 C.
MOD()
这里列出了子例程使用的所有寄存器，但没有 return 记录值。
; Copies a multiprecision number from external memory to internal memory
; IN(R1,DPTR) OUT(R1,DPTR) MOD(A,R2)
mpLoad:
MOV R2, #MPC
Load:
MOVX A, @DPTR
MOV @R1, A
INC DPTR
INC R1
DJNZ R2, Load
RET
; Copies a multiprecision number from internal memory to external memory
; IN(R1,DPTR) OUT(R1,DPTR) MOD(A,R2)
mpStore:
MOV R2, #MPC
Store:
MOV A, @R1
MOVX @DPTR, A
INC DPTR
INC R1
DJNZ R2, Store
RET
; Doubles a multiprecision number
; IN(R1) OUT() MOD(A,R1,R2)
mpShl:
MOV R2, #MPC
CLR C
Shl:
MOV A, @R1
RLC A
MOV @R1, A
INC R1
DJNZ R2, Shl
RET
; Halves a multiprecision number
; IN(R1) OUT() MOD(A,R2)
mpShr:
MOV R2, #MPC
MOV A, R1
ADD A, R2 ; -> C == 0
MOV R1, A
Shr:
DEC R1
MOV A, @R1
RRC A
MOV @R1, A
DJNZ R2, Shr
RET
; Tests if a multiprecision number is zero
; IN(R1) OUT(A) MOD(R1,R2)
mpTest:
MOV R2, #MPC
MOV A, #0
Test:
ORL A, @R1
INC R1
DJNZ R2, Test
RET
; Compares two multiprecision numbers
; IN(R0,R1) OUT(A,C) MOD(R0,R1,R2)
mpCmp:
MOV R2, #MPC
MOV A, R1
ADD A, R2
MOV R1, A
MOV A, R0
ADD A, R2 ; -> C == 0
MOV R0, A
Cmp:
DEC R0
DEC R1
MOV A, @R0
SUBB A, @R1
JNZ CmpRet
DJNZ R2, Cmp
CmpRet:
RET
; Subtracts two multiprecision numbers
; IN(R0,R1) OUT() MOD(A,R0,R1,R2)
mpSub:
MOV R2, #MPC
CLR C
Sub:
MOV A, @R0
SUBB A, @R1
MOV @R0, A
INC R0
INC R1
DJNZ R2, Sub
RET
主要代码
您可以轻松地将它变成一个成熟的程序。
MPC EQU 2 ; Number of bytes per number aka precision
NumX EQU 20h ; Internal memory storage address for first number
NumY EQU 28h ; Internal memory storage address for second number
; -------------------------
MOV R1, #NumX
MOV DPTR, #3000h ; External memory storage address for first number
LCALL mpLoad
MOV R1, #NumY
MOV DPTR, #4000h ; External memory storage address for second number
LCALL mpLoad
; -------------------------
MOV R3, #MPC
MOV R0, #NumX
MOV R1, #NumX
LCALL mpTest ; -> A
JZ SetOne
MOV R1, #NumY
LCALL mpTest ; -> A
JNZ Begin
SetOne:
INC A ; 0 -> 1, 255 -> 0, 255 -> 0, ...
MOV @R0, A
MOV A, #255
INC R0
DJNZ R3, SetOne
SJMP Copy
; -------------------------
Begin:
MOV R3, #0 ; Bits
While1:
JB 0, While3 ; Jump if NumX[bit0] == 1
JB 64, While2 ; Jump if NumY[bit0] == 1
INC R3 ; Bits++
MOV R1, #NumX
LCALL mpShr ; X >> 1
MOV R1, #NumY
LCALL mpShr ; Y >> 1
SJMP While1
; -------------------------
While2:
JB 0, While3 ; Jump if NumX[bit0] == 1
MOV R1, #NumX
LCALL mpShr ; X >> 1
SJMP While2
; - - - - - - - - - - - - -
While3:
JB 64, Compare ; Jump if NumY[bit0] == 1
MOV R1, #NumY
LCALL mpShr ; Y >> 1
SJMP While3
; - - - - - - - - - - - - -
Compare:
MOV R0, #NumX
MOV R1, #NumY
LCALL mpCmp ; -> A C
JZ Equal
MOV R0, #NumX
MOV R1, #NumY
JNC Minus ; Do (X - Y)
MOV R0, #NumY
MOV R1, #NumX
Minus:
LCALL mpSub ; Did (X - Y) or (Y - X)
SJMP While2
; -------------------------
Equal:
MOV A, R3 ; Bits
JZ Copy
Scale: ; X << Bits
MOV R1, #NumX
LCALL mpShl ; X << 1
DJNZ R3, Scale
; -------------------------
Copy:
MOV R1, #NumX
MOV DPTR, #5000h ; External memory storage address for resulting number
LCALL mpStore
; -------------------------
EXIT:
NOP
SJMP $
; Here you add the subroutines
END