Fixed-point arithmetic 定點運算

fixed-point 是一種小數表示方式，儲存固定位數小數。某個固定單位的部份，皆可視為小數。

閱讀時，有小數點分隔整數和小數。但在內部處理程式，並沒有實際的分隔，而由程式隱含定義位置。

低成本嵌入式處理器，沒有浮點運算單元，有些計算需要定點運算適當的 scaling 來達到可接受的動態範圍。定點運算可以比浮點運算更快、更高精確度，但寫程式需要更精確預測數值範圍，調整 scaling facotr，避免 overflow。

表示法

• Qm.n：通常是有號數，不含 sign-bit，整數部份 m-bit，小數部份 n-bit。在 ARM，m 包含 sign-bit。
• UQm.n：無號數，整數部份 m-bit，小數部份 n-bit。
• Qn：小數部份 n-bit。

加法和減法：相同 scaling factor，結果 scaling factor 不變。overflow。

乘法：scaling factor 相乘。在二進位，通常使用 scaling factor that is a power of two，乘完後 scaling factor 可透過 shifting right 調整回來。Rounding 可在 shift 前加上 scaling factor 的一半。證明：round(x/y) = floor(x/y + 0.5) = floor((x + y/2)/y) = shift-of-n(x + 2^(n-1))。

// saturate to range of int16_t
int16_t sat16(int32_t x)
{
	if (x > 0x7FFF) return 0x7FFF;
	else if (x < -0x8000) return -0x8000;
	else return (int16_t)x;
}

int16_t q_mul(int16_t a, int16_t b)
{
    int16_t result;
    int32_t temp;

    temp = (int32_t)a * (int32_t)b; // result type is operand's type
    // Rounding; mid values are rounded up
    temp += 1 << (Q - 1);
    // Correct by dividing by base and saturate result
    result = sat16(temp >> Q);

    return result;
}

除法 https://lirobo.blogspot.com/2021/08/rounding-integer-division.html

int16_t q_div(int16_t a, int16_t b)
{
    int32_t temp = (int32_t)a << Q;
    // Rounding: mid values are rounded up.
    if (((temp >> 31) & 1) == ((b >> 15) & 1)) {
        temp += b>>1; // round up
    } else {
        temp -= b>>1; // round down for negative value
    }
    return (int16_t)(temp / b);
}

參考

• https://en.wikipedia.org/wiki/Fixed-point_arithmetic
• libfixmath

Rounding

Rounding 是用較短的、簡單的、或 more explicit 的近似值表示數值，例如 $23.4476 用 $23.45, 表示、，the fraction 312/937 用 1/3 表示，或 √2 用 1.414 表示。

捨棄低位元時，增加尾數 0 或減少小數位數，決定是否進位。

round down：捨去，是指 round toward zero，但在 2’s complement 數值會是 round toward negative infinity，負值是有所不同。

round up：進位。

round toward zero：無條件捨去法。正數捨去低位元是變小，負數捨去低位元是捨去一些負值而變大，所以都是趨向 0。ROUNDDOWN() truncate()

round away from zero：無條件進位法。捨去低位元時一律進位，正數是變大，負數是變小，所以都是遠離 0。ROUNDUP()

round toward negative infinity：程式的無條件捨去法。一般程式數值用 2’s complement，正數捨去低位元是變小，負數捨去低位元也是變小。floor()

round half down

round half up

round half toward zero (五捨六入)

round half away from zero (四捨五入)

round half toward even (四捨六入五成雙)

round half toward odd

round half alternatively

round half randomly

stochastic round

參考

1. https://en.wikipedia.org/wiki/Rounding

truncation：無條件捨去法
round (round-to-nearest)

• 傳統是四捨五入，只看一位是五就進位，其實五居中 (biased rounding)
• convergent rounding：不只看一位
• unbiased rounding：如果剛好居中，只會變成是偶數。

Rounding off to nearest power of 2

找出大於等於某個值的最小 power of two
count leading zeros (clz) http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
http://en.wikipedia.org/wiki/Find_first_set

http://stackoverflow.com/questions/466204/rounding-off-to-nearest-power-of-2

http://graphics.stanford.edu/~seander/bithacks.html

http://stackoverflow.com/questions/364985/algorithm-for-finding-the-smallest-power-of-two-thats-greater-or-equal-to-a-giv

barrier 多台電腦共用鍵盤和滑鼠

Barrier 予你用一組鍵盤滑鼠透過網路控制幾若電腦，意思是排除電腦之間的壁壘。Barrier 欲 Synergy 1.9 分出來，今仔 Symless 已經佮 Synergy 商業化，袂合。

每台電腦隴需要安裝佮執行 barrier。有鍵盤和滑的那台是 server，揤「Configure server」為每一台 client 拉一個新螢幕到格子，「Screen name」設作電腦的名。佇 client 設定 Server IP (或 Bonjour Auto config) 了 Start。

功能

• 切換電腦：徙滑鼠過螢幕邊仔，抑是用按鍵
• Clipboard sharing
• 跨不同作業系統
  

問題

• VirtualBox 跨邊界游標不見，需要轉動滾輪。
• 重新連線
• 滑鼠抖動
• Logging
• Auto Config
  

參考

1. https://github.com/debauchee/barrier

• https://www.ptt.cc/bbs/Linux/M.1629992667.A.B31.html
• Wayland 通訊協定

Fractional Numbers

實數分著整數 (integer) 和小數 (subinteger, fractional) 兩部份，中央是小數點 (decimal point，在二進位是 binal point)，小數是實數中比 ±1 小的部份。有時陣，有小數部份的實數嘛叫做小數，有可能是表示著分數的有限小數或循環小數、或是無理數的不循環又無限的小數。

DSP 指令假定 binal point convention 的位置如下表：

Register Size	Format	Notation	Sign Bit	Extension Bit	Fractional Bit
40-bit	Signed	9.31	1	8	31
	Unsigned	8.32	0	8	32
32-bit	Signed	1.31	1	0	31
	Unsigned	0.32	0	0	32
16-bit	Signed	1.15	1	0	15
	Unsigned	0.16	0	0	16

1.31 乘以 1.31 是 2.62，過程中需要右移 31 位、或左移一位後取前半段，以維持 1.31。但在一般 32-bit 處理器，只有整數乘法，且結果沒有 64 bits 或大於 32 bits 的空間，只能存後面 32 bits，變成相乘前兩者都要先右移 16-bit，變成 17.15 乘 17.15，結果是 34.30，實際只存後面的 2.30，再左移 1 位變成 1.31，精確度會差一點。

整數除法如何保留小數？被除數左移 16-bit、除數又移 16-bit？

int Q = a/b; // quotaent
int r = a - b * Q; // remainder
int f = 0;
int p = 0; // 十進位小數位數
while (r) {
    r *= 10;
    f *= 10;
    f += r/b;
    p++;
}

int Q = a/b; // quotaent
int r = a - b * Q; // remainder
int f = 0; // fraction
int p; // 二進位小數剩餘位數
for (p = 32; p > 0; p--) {
    f <<= 1;
    r <<= 1;
    q = r/b;
    f |= q;
    r -= b * q;
}

Saturation：結果大於最大值存成最大值，小於最小值存成最小值。

Overflow：結果超出暫存器範圍，捨棄 MSBs

Truncation 或 Rounding：移除 lower-order bits 減少 precision。

• 無條件捨去
• 四捨五入：中間值進位是 biased rounding
• 四捨六入 convergent rounding：中間值轉成最接近的偶數值是 unbiased rounding。二進位 0.01 少一位是 0.0，0.11 是 1.0

參考

1. Blackfin Processor Programming Reference

• GCC 使用 MIPS DSP ASE
• GCC 軟體 fixed-point 函式庫實作 fixed-point fractional 運算，只在特定 target 啟用。_Fract, _Accum, _Sat.
• fixed-point