在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/2²⁰ ，到小数点后6位的精度，而整数只有12位，除去符号位，可表示2¹¹=2048，范围就是-2048~2047。

fp16的位长有效，给小数分配10位，也只有1/2¹⁰=1/1024也就是0.001的精度，而整数只剩可怜的5位，范围是-32~31。

除了定义小数位长fbit，我还定义了一些常见数值的对应的定点数，例如1，0.5，π。可以看到，定点数的1就是1*2²⁰，0.5就是0.5*2²⁰，这就是定点数的原理。

同样的原理我们可以写几个转换函数：

//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; }

 

然后是乘除法：

 先看代码，区别是乘完后需要缩小2^fbit，除完后需要放大2^fbit。

//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

不难理解，定点数是小数乘了2^fbit得到的，如果两个定点数相乘，两次2^fbit就累积了，所以要除去一次2^fbit。

 

之后是一些常用的函数：

//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); }

下一部分 数学函数库 也会包含一些定点数常用函数，例如开方和三角函数。

这里只列出小部分，其他若有需要请看源码。