浮動小数点演算をサポートしない実行環境において、小数点演算はソフトウェア実装のSoft-Floatが選択肢の一つとなるが低速である。
固定小数点は浮動小数点と比較して表現可能な数値幅が狭い代わりに、整数値として四則演算を行うため高速である。LinuxのBPFは浮動小数点の演算に非対応であるため、固定小数点で代替できるよう変換処理を実装した。
浮動小数点（Floating-Point）とは
浮動小数点はIEEE754で定義されている。
32bit浮動小数点の内部表現を図に示す。上位1bitが符号を示し、続く8bitが指数部、下位23bitが仮数部を示す。
C言語では、共用体（Union）とビットフィールドを用いて内部を表現できる。フィールドの並び順はアーキテクチャのバイトオーダーに依存する。以降はリトルエンディアンを前提とする。
typedef union {
float f;
struct {
uint32_t fraction: 23;
uint32_t exponent: 8;
uint32_t sign: 1;
} internal;
} Float;
固定小数点（Fixed-Point）とは
固定小数点は、小数点を固定ビット数だけ左シフトし、整数値として表現したものである。
下位10bitを小数点以下とした場合を図に示す。int32_tの下位1bitは2^0となるところ、固定小数点では2^(-n)と解釈する。
値域はビットシフト分だけ小さくなるため、C言語での実装時は64bit整数型int64_tを用いる。
typedef int64_t FixPT;
浮動小数点と固定小数点の変換
浮動小数点の仮数部は2^(-1)以下を示すため、固定小数点のビット列と一致する箇所が存在する。
浮動小数点 ⇒ 固定小数点
浮動小数点⇒固定小数点において、シフトするビット数は浮動小数点の指数部（exponent）から求まる。
// exponent = 143, n = 10, bits of fraction = 23 lshift = (143 - 127) + 10 - 23 = 3
また、省略された整数部の1を補完する必要がある。符号は2の補数で表現できるため、最後に符号部を見て反転させる。
fix = (fraction + 1 << 23) >> rshift; fix = exponent ? -fix : fix;
固定小数点 ⇒ 浮動小数点
固定小数点⇒浮動小数点において、浮動小数点の仮数部は符号情報を含まないため、先とは逆に非負整数に戻す。
fix = fix < 0 ? -fix : fix;
仮数部（1.X...X）に該当する位置を特定するため、固定小数点の桁数を特定する必要がある。GCCではビルトイン関数__builtin_clzで上位から0が連続するビット数を取得できる。以下のnum_digitsは仮数部で表現したときの小数点以下の桁数を示す。
// bits of fixed-point = 32, clz (count left zeros) num_digits = 32 - __builtin_clz(32) - 1
指数部exponentは固定小数点から何ビットずれているかで計算できる。
// n = 10, exponent bias = 127 exponent = num_digits - 10 + 127
また、ずれた分だけ右シフトして仮数部fractionを求める。
rshift = num_digits - 23; fraction = x >> rshift;
詳細な実装
一般化のため、固定小数点のビットシフト数などの定数値を以下のように定義した。
#define FIX_SHIFT 16 #define FLOAT_FRACTION_SZ 23 #define FLOAT_EXPONENT_SZ 8 #define FLOAT_EXPONENT_BIAS 127
浮動小数点⇒固定小数点では、最大でも2^31以上は表現できないため変換失敗を考慮する。また、C言語で負の数のシフトは未定義であるため条件分岐が必要となる。
inline FixPT Float2Fix(float x, errno_t *err) {
Float *f = (Float*)&x;
FixPT fix;
int8_t rshift = FLOAT_FRACTION_SZ - FIX_SHIFT + FLOAT_EXPONENT_BIAS - f->internal.exponent;
if (rshift > FLOAT_FRACTION_SZ || rshift <= 1 + FLOAT_FRACTION_SZ - (int8_t)sizeof(FixPT) * CHAR_BIT) {
*err = ERANGE;
return 0;
}
if (rshift >= 0) {
fix = ((int64_t)f->internal.fraction + ((int64_t)1 << FLOAT_FRACTION_SZ)) >> rshift;
} else {
fix = ((int64_t)f->internal.fraction + ((int64_t)1 << FLOAT_FRACTION_SZ)) << -rshift;
}
return f->internal.sign ? -fix : fix;
}
inline float Fix2Float(FixPT x) {
Float f;
f.internal.sign = x < 0;
x = x < 0 ? -x : x;
uint8_t num_digits = sizeof(FixPT) * CHAR_BIT - 1 - clzl(x);
f.internal.exponent = num_digits - FIX_SHIFT + FLOAT_EXPONENT_BIAS;
int8_t rshift = num_digits - FLOAT_FRACTION_SZ;
if (rshift >= 0) {
f.internal.fraction = x >> rshift;
} else {
f.internal.fraction = x << -rshift;
}
return f.f;
}
上と同様に倍精度浮動小数点および整数との相互変換を実装した。
GitHubリポジトリ：https://github.com/88IO/fixpt/
コメント