在GBA上寫光線追蹤：定點數運算庫
這篇文章是關于我的GBA庫lib_hl中數學庫的定點數部分。
定點數是什么？為什么要用定點數？
在之前的文章中，我已經介紹了GBA的硬件，它的CPU竟然居然理所當然沒有浮點數運算單元！
我要寫的是光線追蹤程序，基本上都在做精確的數學運算，而這個CPU卻連浮點數都不支持，那不是沒得玩？
當然是有方法的：
1、使用軟件浮點數，在軟件層面模擬浮點數，但比起硬件浮點數慢了太多，光線追蹤是運算密集型程序，這樣肯定不行；
2、使用定點數，在電腦普遍沒有浮點運算單元時，大家都是用定點數代替小數運算。定點數運算速度只比整數運算慢幾倍，還是可以接受的。
定點數通過固定小數點位置，使用整數表示小數，與相比浮點數，定點數可表示范圍比浮點數小，而且它的表示范圍和精度不可兼得。
關于定點數的詳細原理，參見我的另一篇文章（不打算寫了），可以百度
hl_types.h
最開始寫的是一個.h頭文件，里面包含了將用到的數據類型和一些常見操作的宏定義。
無論是在什么程序中，對數據類型進行定義是非常必要的，因為int, long, long long這些類型在不同的編譯器中長度是不同的，在32位/64位的情況下也是不同的，為了程序的強適應性，應該使用自己定義的長度可知的數據類型。
基礎數據類型 代碼如下：
typedef signed char s8; //8位有符號整數 typedef signed short s16; //16位有符號整數 typedef signed int s32; //32位有符號整數 typedef signed long long s64; //64位有符號整數 typedef unsigned char u8; //8位無符號整數 typedef unsigned short u16; //16位無符號整數 typedef unsigned int u32; //32位無符號整數 typedef unsigned long long u64; //64位無符號整數 typedef volatile signed char vs8; //易變型8位有符號整數 typedef volatile signed short vs16; //易變型16位有符號整數 typedef volatile signed int vs32; //易變型32位有符號整數 typedef volatile unsigned char vu8; //易變型8位無符號整數 typedef volatile unsigned short vu16; //易變型16位無符號整數 typedef volatile unsigned int vu32; //易變型32位無符號整數
然后是一些會隨著32/64位系統變化的類型：
#ifdef _X64 typedef long long _stype; typedef unsigned long long _utype; #define _XLEN 8 #else typedef int _stype; typedef unsigned int _utype; #define _XLEN 4 #endif //通用指針類型 typedef void *t_pointer, *t_ptr; //整型地址類型 typedef _utype t_addr;
通過在64位環境下預定義一個_X64的宏，可以使_utype在32位時是4字節，64位數時是8字節長。雖然我們的GBA肯定是32位的，但假如我們要把程序遷移到64位電腦上，就要注意指針類型和地址的長度變化。
然后是一些常用的定義：
//布爾類型 typedef int Bool; #ifndef NULL #define NULL 0 #endif #ifndef TRUE #define TRUE 1 #endif #ifndef FALSE #define FALSE 0 #endif /*內聯函數聲明*/ #define _INLINE_ static inline /*獲取元素相對結構體起始地址的偏移*/ #define _OFFSET(_type,_element) ((t_addr)&(((_type *)0)->_element)) ... #define BIT(n) (1<<(n)) //第n比特為1 (2^n) ... #define SETFLAG(v,flag) v=(v|flag) //設定Flag #define HASFLAG(v,flag) (v&flag) //是否有Flag #define HASFLAGS(v,flags) ((v&(flags))==(flags)) //是否有全部flags #define NOFLAG(v,flag) ((v&flag)==0) //沒有Flag
...
其他定義后續我們需要時在補上，現在我們可以開始寫數學庫了。
hl_math.h
文件開頭加上：
#pragma once #include <hl_system.h>
#pragma once是寫給編譯器看的，意思是這段代碼只編譯一次。
之所以要在頭文件加這句話，是因為C中引用頭文件，是通過直接把頭文件的內存復制到#include的位置，如果在多個文件中都包含了同一個頭文件，編譯時就會導致宏、結構體等被多次定義，引起編譯錯誤。
另一種適合所有編譯器的寫法是：
#ifndef _XXX_H #define _XXX_H 代碼 ... #endif
定義定點數
之后開始編寫真正的代碼，先定義定點數類型：
//32位定點數 typedef s32 fp32; //32位定點數的小數位數 20bit //整數大小 -2048-2047，小數精度 0.000001 #define FP32_FBIT 20
#define FP32_1 (1<<FP32_FBIT) //fp32 1f #define FP32_H5 (1<<(FP32_FBIT-1)) //fp32 0.5f #define FP32_LIMIT1 (FP32_1-1) //fp32 不到1f的最大值 #define FP32_MAX 2147483647 #define FP32_MIN (-2147483647-1) #define FP32_MAXINT ( (1<<(31-FP32_FBIT))-1) #define FP32_MININT (-(1<<(31-FP32_FBIT))) #define FP32_PI (1686629713>>(29-FP32_FBIT)) #define FP32_SQRT2 (1518500249>>(30-FP32_FBIT)) #define FP32_SQRT3 (1859775393>>(30-FP32_FBIT)) #define FP32_F2(n) (1<<(FP32_FBIT-(n))) //fp32 1/(2^n) //16位定點數 typedef s16 fp16; //16位定點數的小數位數 10bit //整數大小 -32-31，小數精度 0.001 #define FP16_FBIT 10
#define FP16_1 (1<<FP16_FBIT) #define FP16_H5 (1<<(FP16_FBIT-1)) #define FP16_MAX 32767 #define FP16_MIN -32768 #define FP16_MAXINT ( (1<<(15-FP16_FBIT))-1) #define FP16_MININT (-(1<<(16-FP16_FBIT)))
可以看到我的定點數有32位的和16位的，32位叫fp32，主要用于精度要求比較高的大部分運算，16位的叫fp16，主要用于精度低的色彩等運算。
fp32為了運算精度，給小數部分分配了20位（可以說是非常重視精度），這樣小數的分度值是1/220 ，到小數點后6位的精度，而整數只有12位，除去符號位，可表示211=2048，范圍就是-2048~2047。
fp16的位長有效，給小數分配10位，也只有1/210=1/1024也就是0.001的精度，而整數只剩可憐的5位，范圍是-32~31。
除了定義小數位長FBIT，我還定義了一些常見數值的對應的定點數，例如1，0.5，π。可以看到，定點數的1就是1*220，0.5就是0.5*220，這就是定點數的原理。
同樣的原理我們可以寫幾個轉換函數：
//int -> fp32 static inline fp32 fp32_int(int n) { return n << FP32_FBIT; } //float -> fp32 //static inline fp32 fp32_float(float f) { return (fp32)(f * (1 << FP32_FBIT)); } //int/100 -> fp32 static inline fp32 fp32_100f(int n) { return (((s64)n << FP32_FBIT) + 50) / 100; } //fp32 -> int static inline int int_fp32(fp32 f) { return f >> FP32_FBIT; }
看完代碼對定點數的理解應該也深一些吧。
所有函數前都加上了static inline，inline是聲明這個函數是內聯函數，也就是在編譯時會被展開，避免函數調用開銷，對于我們這種常用且短小的運算函數，當然要加。但inline只是向編譯器提個建議，編譯器可能不聽，如果它覺得這個函數太大，內聯不劃算，就不內聯了。這時這個函數就變成了定義在頭文件的普通函數，這會帶來一個問題，如果頭文件被多次包含會導致函數重定義，所以加上static，聲明為靜態函數，只是在聲明它的文件中可見，避免命名沖突。其實，規范地寫，應該使用之前定義的_INLNE_，以防切換到不支持staic inline特性的編譯器。
定點數運算
之后就是運算函數了。首先是加減運算，和整數運算并無兩樣。它的運算原理如下：
假設：
整數A是小數a的定點數形式，即 A = a*fs （fs = 1<<FBIT)
整數B是小數b的定點數形式，即 B = b*fs （fs = 1<<FBIT)
則 定點數A 加 定點數B 的公式是：
A (+) B = a*fs (+) b*fs = (a+b)*fs = (A/fs+B/fs)*fs = A+B
//fp32 + fp32 **事實上沒有用的必要 static inline fp32 fp32_add(fp32 a, fp32 b) { return a + b; } //fp32 - fp32 **事實上沒有用的必要 static inline fp32 fp32_sub(fp32 a, fp32 b) { return a - b; }
然后是乘除法：
先看代碼，區別是乘完后需要縮小2FBIT，除完后需要放大2FBIT。
//fp32 * fp32 (64位安全運算) static inline fp32 fp32_mul64(fp32 a, fp32 b) { return (((s64)a) * b) >> FP32_FBIT; } //fp32 / fp32 (64位安全運算) *b<1仍可能溢出 static inline fp32 fp32_div64(fp32 a, fp32 b) { return (((s64)a) << FP32_FBIT) / b; }
定點數A乘定點數B的推導過程：
A (x) B = (a*b)*fs = (A/fs)*(B/fs)*fs = (A*B)/fs
定點數A除定點數B的推導過程：
A (÷) B = (a/b)*fs = (A/fs)/(B/fs)*fs = (A/B)*fs
不難理解，定點數是小數乘了2FBIT得到的，如果兩個定點數相乘，兩次2FBIT就累積了，所以要除去一次2FBIT。
之后是一些常用的函數：
//fp32^2 static inline fp32 fp32_pow2(fp32 a) { return (((s64)a) * a) >> FP32_FBIT; } //返回結果是u64 static inline u64 fp32_pow2_64(fp32 a) { return (((s64)a) * a) >> FP32_FBIT; } static inline fp32 fp32_lerp(fp32 a, fp32 b, fp32 t) { return a + fp32_mul64(b - a, t); }
下一部分 數學函數庫 也會包含一些定點數常用函數，例如開方和三角函數。
這里只列出小部分，其他若有需要請看源碼。
浙公網安備 33010602011771號