fixed-point trig approximations without tables

[jnmartin84]

Doom uses lookup tables for fixed-point trig approximations.

I did an experiment in the past using cached vs uncached accesses for these and it performs the same which suggests to me if we can find a fast way to approximate in code, not using memory, it wont hurt anything and it might improve performance.

They are currently always accessed uncached in 64Doom. These accesses are hundreds of cycles.

Some of these may be able to be approximated in other ways.

I started by looking at the simplest case of tantoangle.

It can be fit with the following with acceptable results: #define tantoangle(x) ((angle_t)((-47*((x)*(x))) + (359628*(x)) - 3150270))

3 multiplies, 1 add, 1 sub. Not hundreds of cycles.

Looking at the rest of the tables to see what can be done.

[jnmartin84]

There are other approximations for sin/cos/tan I tried to work with in the past but wasn't able to finesse them enough to make them work for Doom without visual issues. Giving that another shot.

[jnmartin84]

See: http://www.coranac.com/2009/07/sines/ The third-order approximation presented here works with some parameter tweaks and compiles down to 17 instructions, the 2 integer multiplies being the worst with respect to latency/pipeline:

  sll    v0,a0,0x13
  sll    a0,a0,0x14
  xor    a0,a0,v0
  bgez    a0,<finesine+0x18>
  lui    v1,0x8000
  subu    v0,v1,v0
<finesine+0x18>:
  sra    v0,v0,0x11
  mult    v0,v0
  lui    v1,0x1
  ori    v1,v1,0x8000
  mflo    a0
  sra    a0,a0,0xb
  subu    v1,v1,a0
  mult    v1,v0
  mflo    v0
  jr    ra
  sra    v0,v0,0xd

[jnmartin84]

started with commit e5311d8ebe196d000018f10501eee4f5480adfc3

[jnmartin84]

I have an approximation for finetangent, still finessing the conversion of it from floating point to fixed point, I need to work out how to scale/transform things

[jnmartin84]

Finetangent approximation with commit a1212bb0583c3818479b58576e259224d8516f25

floating-point for now, need to do more work on converting to fixed-point