Making The Quake Code More Efficient

[R0B]

I've been looking through the FixedPointMath.c file and have noticed a couple places where Dan has said the code could be more efficient.  Do the two new functions do the trick for those old ones?<br><br>OLD<br><br>//TODO: could be more efficient<br>fixedpoint_t fpm_Ceil(fixedpoint_t fxp) {<br>      if (fxp&0x0000ffff) {<br>            if (fxp<=0) return -(fixedpoint_t)((-fxp)&0xffff0000);<br>            return (fxp&0xffff0000)+FPM_FROMLONGC(1);<br>      }<br>      return fxp;<br>}<br>//TODO: could be more efficient<br>fixedpoint_t fpm_Floor(fixedpoint_t fxp) {<br>      if (fxp&0x0000ffff) {<br>            if (fxp<0) return -(long)(((-fxp)&0xffff0000)+FPM_FROMLONGC(1));<br>            return fxp&0xffff0000;<br>      }<br>      return fxp;<br>}<br><br><br><br><br>NEW<br><br>fixedpoint_t fpm_Ceil(fixedpoint_t fxp) {<br>      if (fxp <= 0) return fxp & 0xffff0000;<br>      else return (fxp + 0xffff) & ~0xffff;<br>}<br><br>fixedpoint_t fpm_Floor(fixedpoint_t fxp) {<br>      if (fxp >= 0) return fxp & 0xffff0000;<br>      else return (fxp + 0xffff) & ~0xffff;<br>}<br>

[roadkilldave]

Your best bet would be to compile and test it out for FPS to see if it is faster.

[Dan East]

The FixedPointMath.c routines are not being used at this time. After the PQ project was at a stable point I foolishly decided to attempt a global, generic replacement of all Floating point math with Fixed point. I created a new fixed point type, and the routines you see in FixedPointMath to handle fixed point operations. I then went through the source and replaced floating point operators (+, -, *, etc) with function calls to my new routines. After a huge amount of effort, it wouldn't work. What I found was that the range and precision of the various floating point vars was far greater than what can be stored with 32 bit fixed point (16.16).<br><br>So, to convert a set of routines from floating point to fixed point, I follow the following tedious steps:<br><br>1: I identify the potential floating point vars I want to convert.<br><br>2: I identify every routine that modifies that var.<br><br>3: I use a logging function at every point that var is modified to record the min, max and smallest precision value that variable is assigned throughout the course of execution (usually allowing a full demo to run).<br><br>4: Based on the results of the logging I determine what fixed point precision (if any) to use for that particular variable.<br><br>5: I then have to study what operations occur between those variables. Some fixed point operations result in a loss of precision, others in a loss of range. I have to try and synchonize the fixed point precision so that multiplication and division operations don't result in overflow / underflow. I usually have a little precision to work with, but there are cases when I literaly did not have 1 single extra bit of precision to spare.<br><br>Dan East

[R0B]

Then, could you point me in the direction of a place that you think that I could optimize to increase performance.  That change actually gave me .1 fps greater, but that could just be a fluctuation in speed for some reason too.

[R0B]

This question is mainly for Dan, but if you think you know the answer (and many of you probably do) feel free to respond.  I am going to start rewriting functions from PQ in asm, and I wouldlike to know which ones will be the most benificial, and give the best speed increases.  Please just point me in the right direction.

[Digby]

Wow Dan, that sounds remarkably similar to something I did a few months back.  I wrote a C++ CFixedPoint class and supported every operator that you would use with floats.  I had the debug build actual do a true floating point routine under the hood along side the fixed point operation.  I keep track of the difference in an attempt at seeing what could break due to the fixed point implementation's lack of precision compared to the true floating point result.<br><br>I don't remember the exact results from profiling matrix concatentation routines, but it was quite a bit faster than the floating point library on my iPaq.  If anyone is interested I can dig up the test results and post here.<br><br>

[R0B]

Sure, post away.

[Dan East]

I'll have to look into that. If you download the original Quake source from ID software you'll find a lot of x86 asm code. That may be a place to start, converting their asm to ARM. Also, they undoubtedly only wrote the more critical routines in ASM.<br><br>Dan East

[Dan East]

Well, the main issue I ran into wasn't that the precision was off a bit, it was when a very small value fell off to zero, or when I overflowed / underflowed and ended up changing sign and all that crap. In the debug build I would check, for example, to see if the result of a division with a non-zero dividend was 0.<br>I guess Quake could be converted to C++ if such a class seemed like it would work / help. I assume it dynamically adjusts precision?<br><br>Dan East

[Digby]

[Digby]

[Dan East]

[R0B]

[R0B]

[roadkilldave]