algorithm - 将四进制转换为八进制。 ASM 8086

Question

我必须为 8086 处理器准备将四进制数转换为八进制数的程序。

我的想法:

将每个数字乘以 4 的指数并添加到寄存器中。稍后检查 8 的最高指数不高于第一步的总和。除以 8 的指数，直到余数为 0。每一个除法结果都是一位八进制数。但是对于 16 位数字，4 的最后一个指数是 4^15。我想这不是最佳算法。

还有别的办法吗？也许二进制和 3 位分组。

Answer 1

事实证明，您确实可以一次处理 3 位数的值。通过这种方式，您可以处理任意长度的字符串，而不受寄存器大小的限制。不确定你为什么需要这样做，除非外星人试图使用具有巨大长度的四进制数字的 ascii 字符串与我们交流。可能会发生。

可以以任何一种方式进行翻译(从右到左或从左到右)。但是，这两者都存在一些挑战:

如果您正在处理 RtL，您需要在开始之前知道输出字符串的长度(以便您知道在计算数字时将数字写在哪里)。这是可行的，但有点棘手。用最简单的术语来说，长度是 ((strlen(Q) + 2)/3) * 2。几乎 得到它。但是，在许多情况下，您最终可能会在开头有一个空格。 “1”和“10”将给出空格。 “20”不会。可以计算出正确的值，但这很烦人。

同样，处理LtR也有类似的问题。你没有弄清楚在哪里写数字的问题，但考虑:如果将字符串转换为“123”，那么转换很简单(八进制 33)。但是，如果您开始处理，并且完整的字符串是“1231”(八进制 155)怎么办？在那种情况下，您需要像“001231”(01 55)一样处理它。 IOW，数字可以以 3 为一组进行处理，但是您需要处理数字数量不能被 3 整除的初始情况。

我通常避免发布家庭作业的解决方案。但是，我怀疑您是否会把它作为您的“解决方案”，并且谷歌(几乎)可能会派人来这里需要类似的东西。

一些注意事项:

1. 此代码旨在使用 Microsoft 的 fastcall(它使测试更容易)从 C 调用并使用 masm 编译。
2. 虽然它是用 32 位(我的环境)编写的，但没有什么特别需要 32 位的。既然你说你的目标是 8086，我就尽量避免任何“高级”指令。转换为 16 位甚至 64 位应该不会有太大挑战。
3. 它从左到右处理。
4. 与任何编写良好的例程一样，它会验证其参数。它在错误时输出零长度字符串，例如输入字符串中的无效数字。
5. 如果输出缓冲区为 NULL，它将崩溃。我想我可以在出错时返回 bool(目前返回 void)，但是，好吧，我没有。
6. 我确信代码可以更紧凑(不能总是这样吗？)，但对于“家庭作业项目质量”来说，这似乎是合理的。

除此之外，注释应该解释代码。

.386
.model flat
.code

; Call from C via:
; extern "C" void __fastcall PrintOct(const char *pQuat, char *pOct);

; On Entry:
; ecx: pQuat
; edx: pOct

; On Exit:
; eax, ecx, edx clobbered
; all others preserved
; If pOct is zero bytes long, an error occurred (probably invalid digits)

@PrintOct@8 PROC

; -----------------------
; If pOct is NULL, there's nothing we can do
    test edx, edx
    jz Failed

; -----------------------
; Save the registers we modify (except for
; eax, edx and ecx which we treat as scratch).
    push esi
    push ebx
    push edi

    mov esi, ecx
    mov edi, edx
    xor ebx, ebx

; -----------------------
; esi: pQuat
; edi: pOct
; ebx: zero (because we use lea)
; ecx: temp pointer to pQuat

; Reject NULL pQuat
    test esi, esi
    jz WriteNull

; -----------------------
; Reject 0 length pQuat
    mov bl, BYTE PTR [esi]
    test bl, bl
    jz WriteNull

; -----------------------
; How many chars in pQuat?
    mov dl, bl ; bl is first digit as ascii.  Preserve it.

CountLoop:
    inc ecx ; One more valid char

; While we're counting, check for invalid digits
    cmp dl, '0'
    jl WriteNull
    cmp dl, '3'
    jg WriteNull

    mov dl, BYTE PTR [ecx] ; Read the next char
    test dl, dl ; End of string?
    jnz CountLoop

    sub ecx, esi

; -----------------------
; At this point, there is at least 1 valid digit, and
; ecx contains # digits
; bl still contains first digit as ascii

; Normally we process 3 digits at a time.  But the number of
; digits to process might not be an even multiple of 3.

; This code finds the 'remainder' when dividing ecx by 3.
; It might seem like you could just use 'div' (and you can),
; but 'div' is so insanely expensive, that doing all these
; lines is *still* cheaper than a single div.
    mov eax, ecx
    mov edx, 0AAAAAAABh
    mul edx
    shr edx, 1
    lea edx, [edx+edx*2]
    sub ecx, edx ; This gives us the remainder (0-2).

; If the remainder is zero, use the normal 3 digit load
    jz LoadTriplet

; -----------------------
; Build a triplet from however many leading 'odd' digits
; there are (1 or 2).  Result is in al.

    lea eax, DWORD PTR [ebx-48] ; This get us the first digit

; If there was only 1 digit, don't try to load 2
    cmp cl, 1
    je OneDigit

; Load the other digit

    shl al, 2
    mov bl, BYTE PTR [esi+1]
    sub bl, 48
    or al, bl

OneDigit:

    add esi, ecx ; Update our pQuat pointer
    jmp ProcessDigits

; -----------------------
; Build a triplet from the next 3 digits.
; Result is in al.

; bl contains the first digit as ascii
LoadTriplet:

    lea eax, DWORD PTR [ebx-48]

    shl al, 4 ; Make room for the other 2 digits.

    ; Second digit
    mov cl, BYTE PTR [esi+1]
    sub cl, '0'
    shl cl, 2
    or al, cl

    ; Third digit
    mov bl, BYTE PTR [esi+2]
    sub bl, '0'
    or al, bl

    add esi, 3 ; Update our pQuat pointer

; -----------------------
; At this point
; al: Triplet
; ch: DigitWritten (initially zeroed when computing remainder)
ProcessDigits:

    mov dl, al
    shr al, 3 ; left digit
    and dl, 7 ; right digit

    ; If we haven't written any digits, and we are
    ; about to write a zero, skip it. This deals
    ; with both "000123" and "2" (due to OneDigit,
    ; the 'left digit' might be zero).

    ; If we haven't written any digits yet (ch == 0), and the
    ; value we are are about to write is zero (al == 0), skip
    ; the write.
    or ch, al
    jz Skip1

    add al, '0' ; Convert to ascii
    mov BYTE PTR [edi], al ; Write a digit
    inc edi ; Update pointer to output buffer

    jmp Skip1a ; No need to check again

Skip1:
    or ch, dl ; Both check and update DigitWritten
    jz Skip2

Skip1a:

    add dl, '0' ; Convert to ascii
    mov BYTE PTR [edi], dl ; Write a digit
    inc edi ; Update pointer to output buffer

Skip2:

; Load the next digit.
    mov bl, BYTE PTR [esi]
    test bl, bl
    jnz LoadTriplet

; -----------------------
; All digits processed.  We know there is at least 1 valid digit
; (checked on entry), so if we never wrote anything, the value
; must have been zero.  Since we skipped it to avoid
; unnecessary preceding zeros, deal with it now.

    test ch, ch
    jne WriteNull
    mov BYTE PTR [edi], '0'
    inc edi

; -----------------------
; Write the trailing NULL.  Note that if the returned string is
; 0 bytes long, an error occurred (probably invalid digits).
WriteNull:
    mov BYTE PTR [edi], 0

; -----------------------
; Cleanup
    pop edi
    pop ebx
    pop esi

Failed:
    ret

@PrintOct@8 ENDP

end

我运行了一个包含 1,000,000,000 个四进制数字的字符串以及 0-4,294,967,295 之间的所有值。似乎有效。

我欢迎我们新的 4 位数外星霸主。