我正在嘗試修補一個舊的 8 位匯編程式例程（它恰好是 M6800，但這并不是真正特定于機器的）以獲取 16 位值并向下舍入到最接近的 0x50（dec 80）倍數。當前代碼僅通過對低位元組執行 1來截斷到最接近的32AND 0xE0 ，這當然會將低 5 位整齊地清零并在不觸及高位元組的情況下獲得正確的結果。
這是在做一些螢屏數學運算，因此輸入值只會在 to 的范圍0xE000內0xE7CF。由于 80 顯然不是 2 的冪，所以我不能輕易做到這一點，但鑒于這是一個補丁，我試圖在不添加通用除法或查找表等的情況下將指令數量保持在理想狀態。
我很難過，懷疑沒有特別聰明的方法可以做到這一點。80 不是 2 的冪，而是 16 的倍數……這對我沒有幫助嗎？任何見解，指標等都將受到贊賞。謝謝。
uj5u.com熱心網友回復：
首先，因為80 = 16 * 5向下舍入為 和 的倍數80意味著向下舍入為16和的倍數5。第一個很容易右移，所以現在我們剩下的mod 5部分是：
def mod5(x):
return x % 5
def round80(x):
x >>= 4
x -= mod5(x)
x <<= 4
return x
mod5不是那么容易做到的，但是梅森模數有一個巧妙的構造，它首先計算mod15，然后將值降低為模 5。一開始并不那么直觀，但它只涉及加法和移位，應該是很容易實作。這是python版本：
def mod15(x):
x = (x >> 8) (x & 0xFF)
x = (x >> 4) (x & 0xF)
if x >= 15: x -= 15
if x >= 15: x -= 15 # (see note)
return x
def mod5(x):
x = mod15(x)
if x >= 5: x -= 5
if x >= 5: x -= 5
return x
def round80(x):
x >>= 4
x -= mod5(x)
x <<= 4
return x
為了安全起見，我驗證了此代碼的所有可能值：
for i in range(0x10000):
trivial = i - (i % 80)
assert trivial == round80(i)
另一個注意事項：對于您的輸入范圍if，第二個內部mod15實際上可以省略，將其注釋掉沒有任何區別。如果您需要整個范圍，則無法洗掉它。[0,0xffff]
我不是 M6800 組裝方面的專家，所以我不會嘗試撰寫最終代碼，但它應該相對簡單，特別是考慮到唯一的 16 位操作是mod15.
沒有除法，沒有乘法，也沒有查找表 - 我希望這足夠短以滿足您的需求！
uj5u.com熱心網友回復：
我們采用 Darios 技巧并將其應用于有限的輸入范圍。
由于 80 可以除以 16，為了向下舍入到 80 的下一個倍數，我們可以丟棄最右邊的十六進制數字（將其設定為零）并將該數字左側的數字向下舍入到下一個 5 的倍數。
這可以通過確定這種除法的余數并減去它來完成。最左邊的數字是常數 0xE。0xE00 mod 5 = 4。第二個數字是十六進制乘以 16。16 mod 5 = 1。所以除以 5 的余數是 4 第二個數字 第三個數字。
由于我們必須將輸入位元組移動到中間數字并移回以從輸入中減去（或者作為另一種方式，從移位的數字中減去和移回差值），我們也可以使用向左移動的數字，只要它們適合一個位元組以保存移位操作。
中間兩個數字和 4 的最大和是 4 0x6 0xf = 25。所以我們可以用最高 8 倍的數字來計算以保持在 255 以下。
有不同的方法可以從 4 到 25 之間的數字中獲得除以 5 的余數。通過回圈或通過范圍和分支的一系列測驗。（與今天相比，早期處理器的分支和記憶體訪問成本較低。）我們必須在執行時間和代碼大小之間找到折衷方案。
我們可以根據結果進行實際計算和分支，而不是為了設定分支標志而進行測驗，這也節省了指令。
使用的標志是進位、零和符號。
進位/借位為我們提供了先前的加法或減法超過 255 或低于 0 并環繞的資訊。
零/等于告訴我們結果為 0。
符號為我們提供最高有效位，或者如果我們進行所有計算乘以 8，則先前的總和實際上是 16 或更高。16*8=128，這是 8 位無符號整數的 MSB 的值。
假設索引暫存器指向輸入數字的高位元組，然后是記憶體中的低位元組（摩托羅拉經常使用的大端約定，但是在訪問記憶體時，可以在下面的代碼中簡單地更改索引）。
LDAA #00H,X ; load high byte into A
ANDA #0FH ; take lower digit
LDAB #01H,X ; load low byte into B
ANDB #F0H ; select higher digit of B
ASLA ; do everything with numbers * 8
ASLA
ASLA
LSRB ; shift right by 1
ABA ; add B to A
ADDA #20H ; add 8*4 for contribution of 0xE000
AGAIN:
SUBA #28H ; subtract 8*5
BCC AGAIN ; no borrow, do it again
ADDA #28H ; we subtracted once too much, undo
ASLA ; multiply by 2 again
TAB ; transfer A to B
LDAA #01H,X ; load low byte into A
ANDA #F0H ; set lower digit to 0
SBA ; subtract B from A, keep carry
STAA #01H,X ; store low byte back
BCC FINISHED; no borrow occured
DEC #00H,X ; borrow -> decrement high byte
FINISHED:
該解決方案占用 34 個位元組，最多執行 30 條指令（最少執行 20 條）。
變體 1：
LDAA #00H,X ; load high byte into A
ANDA #0FH ; take lower digit
LDAB #01H,X ; load low byte into B
ANDB #F0H ; select higher digit of B
ASLA ; do everything with numbers * 8
ASLA
ASLA
LSRB ; shift right by 1
ABA ; add B to A
BPL PLUS0_15; 0..15
SUBA #(21*8); 16..21 -21
BCC GOOD ; 21 change = -21
ADDA #(5*8) ; 16..20 -21 5
BRA GOOD ; change = -16
PLUS0_15: ; 0..15
BNE PLUS1_15; 1..15
ADDA #(4*8) ; 0 4
BRA GOOD ; change = 4
PLUS1_15: ; 1..15
SUBA #(11*8); -11
BCC GOOD ; 11..15 change = -11
ADDA #(5*8) ; -11 5
BCS GOOD ; 6..10 change = -6
ADDA #(5*8) ; 1..5 -11 5 5
; change = -1
GOOD:
ASLA ; multiply by 2 again
TAB ; transfer A to B
LDAA #01H,X ; load low byte into A
ANDA #F0H ; set lower digit to 0
SBA ; subtract B from A, keep carry
STAA #01H,X ; store low byte back
BCC FINISHED; no borrow occured
DEC #00H,X ; borrow -> decrement high byte
FINISHED:
該解決方案占用 52 個位元組并執行多達 24 條指令（最少執行 19 條）。更快，但更大。
變體 2：
LDAA #00H,X ; load high byte into A
ANDA #0FH ; take lower digit
LDAB #01H,X ; load low byte into B
ANDB #F0H ; select higher digit of B
ASLA ; do everything with numbers * 8
ASLA
ASLA
LSRB ; shift right by 1
ABA ; add B to A
BPL PLUS0_15; 0..15
SUBA #(21*8); 16..21 -21
BRA SAMECODE
;BCC GOOD ; 21 change = -21
;ADDA #(5*8); 16..20 -21 5
;BRA GOOD ; change = -16
PLUS0_15: ; 0..15
CMPA #(6*8);
BCC PLUS6_15; 6..15
SUBA #(6*8) ; -1
BRA SAMECODE
;BCC GOOD ; 1..5 change = -1
;ADDA #(5*8); 0 -1 5
;BRA GOOD ; change = 4
PLUS6_15: ; 6..15
SUBA #(11*8); -11
SAMECODE:
BCC GOOD ; 11..15 change = -11
ADDA #(5*8) ; -11 5
GOOD:
ASLA ; multiply by 2 again
TAB ; transfer A to B
LDAA #01H,X ; load low byte into A
ANDA #F0H ; set lower digit to 0
SBA ; subtract B from A, keep carry
STAA #01H,X ; store low byte back
BCC FINISHED; no borrow occured
DEC #00H,X ; borrow -> decrement high byte
FINISHED:
該解決方案占用 46 個位元組，最多執行 24 條指令（最少執行 20 條）。代碼重用要小一些，最佳情況要差一些，最壞情況相同。人們應該更好地比較平均情況。
變體 3：
LDAA #00H,X ; load high byte into A
ANDA #0FH ; take lower digit
LDAB #01H,X ; load low byte into B
ANDB #F0H ; select higher digit of B
ASLA ; do everything with numbers * 8
ASLA
ASLA
LSRB ; shift right by 1
ABA ; add B to A
BPL PLUS0_15; 0..15
SUBA #(21*8); 16..21 -21
BCC GOODA ; 21 change = -21
BRA SAMECODE
;ADDA #(5*8); 16..20 -21 5
;BRA GOODA ; change = -16
PLUS0_15: ; 0..15
SUBA #(6*8) ;
BCS PLUS0_5 ; 0..5
TAB ; Transfer A to B (keep safe for 6..10)
SUBA #(5*8) ; -6-5
BCC GOODA ; 11..15 change = -11
BRA GOODB ; 6..10 change = -6
PLUS0_5: ; 0..5
ADDA #(5*8) ; -6 5
BCS GOODA ; 1..5 change = -1
SAMECODE:
ADDA #(5*8) ; 0 -6 5 5
; change = 4
GOODA:
TAB ; transfer A to B
GOODB:
ASLB ; multiply by 2 again
LDAA #01H,X ; load low byte into A
ANDA #F0H ; set lower digit to 0
SBA ; subtract B from A, keep carry
STAA #01H,X ; store low byte back
BCC FINISHED; no borrow occured
DEC #00H,X ; borrow -> decrement high byte
FINISHED:
該解決方案占用 51 個位元組，最多執行 23 條指令（最少執行 19 條）。再次變大，但在最壞的情況下更好。
更傳統的解決方案（也與 0x50 以外的除數一起使用）：
LDAA #00H,X ; load high byte
SUBA #DCH ; subtract 0xDC; 0xDC00 is divisible by 80; prevent overflow of counter, shorten execution time; we know input is at least 0xE000
CLR #00H,X ; clear counter
LDAB #01H,X ; load low byte
REP1:
INC #00H,X ; count
SUBB #50H ; try subtracting 0x50
SBCA #00H ; subract with borrow
BCC REP1 ; not finished
LDAA #DBH ; initialize high byte with 0xDB
LDAB #B0H ; initialize low byte with 0xB0 (counter is 1 too high)
REP2:
ADDB #50H ; add 0x50 to low byte
ADCA #00H ; add carry to high byte
DEC #00H,X ; decrease counter
BNE REP2 ; until zero
STAB #01H,X ; store back low byte
STAA #00H,X ; store back high byte
此解決方案需要 32 個位元組并執行多達 312 條指令（最少 112 條）。至少體積更小。
作為比較，舍入到 0x20 的倍數而不是 0x50 的方法：
LDAA #01H,X ; load low byte
ANDA #E0H ; zero the 5 low bits
STAA #01H,X ; store back
將需要 6 個位元組并執行 3 條指令。
uj5u.com熱心網友回復：
這不是聰明的數學運算或小玩意兒，但如果您正在優化代碼空間，您可能會考慮一個簡單的回圈。使用您的輸入范圍，只有 26 個可能的輸出值，因此最壞情況的運行時間并不可怕。
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
/* Truncate to nearest multiple of 80, with input range 0xE000 to 0xE7D0. */
uint16_t truncate_to_80(uint16_t n) {
uint16_t ret = 0xDFC0; /* Lowest possible output. */
while (ret 80 <= n) {
ret = ret 80;
}
return ret;
}
int main(void) {
for (int i = 0xE000; i <= 0xE7D0; i ) {
uint16_t truncated = truncate_to_80(i);
assert(truncated == (i - (i % 80)));
printf("%d -> %d\n", i, truncated);
}
}
uj5u.com熱心網友回復：
0x50 不是 2 的冪，所以它有奇數素因數。這使得它在二進制計算機上變得更加困難。商和余數都取決于整個整數的所有高位。
Dario 的 mod5 想法利用 2^n 1 特殊情況非常有用，避免了乘法逆或移位/加法迭代除法的完整一般情況。
它仍然有些痛苦，特別是因為 6800（與 AVR 不同）只能移位 1。AVR 的swap指令（交換半位元組 = 旋轉 4）在這里很有用，編譯器很好地利用它來移位 4，用于 Dario 的 C 版本代碼（https://godbolt.org/z/c7qhKx6aY）。
AVR 是另一個 8 位微控制器，因此看看編譯器如何在那里做事有點有趣。它有 32 個暫存器，而6800 有兩個（加上一個 16 位 IX，但對其的操作非常有限：http ://www.8bit-era.cz/6800.html列出了指令集）。它只有 1 的班次，與swap我看到的 AVR 完全不同，所以 4 次的班次更貴。（移位 8 仍然是免費的，16 位數字仍然存盤在 8 位的一半中。）
我引入了uint8_t值足夠窄的新變數，幫助編譯器避免浪費指令。（并為手寫 asm 版本識別這些點。）我還重寫了一些東西以減少移位，尤其是減少完整的 16 位移位，但我認為手動進行此類優化的空間更大，例如可能使用移位值直接回傳 a mod5 << 4，而不是讓呼叫者這樣做。
例如(x >> 4) (x & 0xF)可能是(x & 0xf0) ((uint8_t)x<<4)，但這不會使它適合一個位元組；還有一點可能會延伸到下一個位元組。也許只有右移一位或兩位位置，因此在使用 8 位減法執行m -= 15andm -= 5步驟后，向后移位的距離更短。
否則，至少這些步驟中的第一個必須處理延伸到另一個位元組的值的頂部。借用只會從低到高傳播，但您確實需要正確比較，所以您不能只是截斷并丟棄它；那將是 mod 16 而不是 mod 15。
#include <stdint.h>
inline
uint8_t mod15(unsigned short x){
x = (x >> 8) (x & 0xFF); // carry-out can produce a 9-bit result
uint8_t m = (x >> 4) (x & 0xF);
#if 0
do {
m -= 15;
} while((int8_t)m >= 0);
m = 15;
#else
if(m >= 15) m -= 15;
//if(m >= 15) m -= 15; // not needed for partial range
#endif
// or slower, just let a mod5 loop run potentially more iterations
return m;
}
inline
uint8_t mod5(unsigned short x){
uint8_t m = mod15(x);
//while(!__builtin_sub_overflow(m, 5, &m) ){}
//m = 5;
//uint8_t m1 = m - 5;
//if (m < 5) return m1;
#if 1
do { // GCC makes a small loop, clang calls a modulo function :/
m -= 5;
} while((int8_t)m >= 0);
m = 5;
#else
if(m >= 5) m -= 5;
if(m >= 5) m -= 5;
#endif
return m;
}
unsigned short round80(unsigned short x){
//x >>= 4;
uint8_t m5 = mod5(x>>4);
x &= -16;
x -= m5 << 4;
//x <<= 4;
return x;
}
我還沒有真正嘗試撰寫它的 6800 版本。它很可能需要一些暫存空間，無論是在堆疊上使用推/拉，還是在某處訪問空間更便宜。只有 2 個 8 位暫存器 A 和 B，這就是全部值。
16 位右移 1 可以用LSR B/完成ROR A。我認為這確實需要在某個時候發生，但如果以后不做的話，也許可以盡可能地避免。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/488486.html
上一篇：有沒有辦法查看目標檔案中“.rodata （記憶體位置）”的內容？
下一篇：6502代碼中的高效多重間接尋址