Re: [Devel] Some thoughts about fttrigon.c

[David Turner]

Hello Eike,

address@hidden wrote:
> Quite a while ago I looked at fttrigon.c and --- in the course ---
> read a bit about "cordic" math. Unfortunately I lost my notes, but
> since the functions are now in use, I try to recall some issues:
>
> 1) Possible omission of initial left shift in "ft_trig_pseudo_rotate"
>    and "ft_trig_pseudo_polarize"
>
> Both, "ft_trig_pseudo_rotate" and "ft_trig_pseudo_polarize" do some
> argument reduction. This makes it possible to omit the initial left
> shift in these functions. To approximate angles between -90 and 90
> degrees it's enough to use a discrete basis starting with atan(2^0)=
> 45 deg.
>
> It's possible to push argument reduction one step further. This allows
> one to choose a basis starting with atan(2^-1) which is advantageous
> (see below). But then again, the needed additional code is probably not
> worth it.
>
> An immediate gain of choosing a basis atan(2^i), i=0, -1, ... (apart
> from less code) is that the "cordic shrink factor" grows, i.e. the
> vectors, whilst pseudo-rotating, are not being stretched as much. This
> means we can preserve two additional bits in "ft_trig_prenorm".
>
>
> 2) Using optimal fixed point representations in interim calculations
>
> After switching to a different basis (see above) it may be worthwhile
> to choose an 8.24 format for the atan-table. This format can then be
> used as an interim format (after argument reduction in "ft_trig_pseudo_
> rotate" and before "result expansion" (?) in "ft_trig_pseudo_polarize")
> for angles. This gives a higher precision and allows more iterations
> (if wanted).

This is interesting, but I don't think I'll have the time to change anything
to the CORDIC code myself. I designed it because I wanted accurate sine/cosine
computations as well as a high-performance vector length operations that
would work very well with fixed points.

There aren't drastic requirements on performance, and I'm pretty pleased
with the current code. If you believe that you can provide some enhancements,
please do so :-)

I don't think we should modify the code to support variable iterations
numbers, it's out of the scope of a font engine after all :-)

> 3) Rounding
>
> Forgot most of the things regarding rounding. The current rounding of
> theta in "ft_trig_pseudo_polarize" is not clear to me. Applying 1) and
> 2) allows some rounding though.
Fact is that you'll always encounter random bits at the end of a CORDIC
computation. This mostly comes from the limited accuracy of the pre-computed
Atan values, and I don't know how to control these precisely..

> 4) Desired precision
>
> IIRC there were some precision issues involved regarding differing FT1
> and FT2 output. This brings up the question: How much precision do we
> actually need? Reading the TrueType spec I couldn't find any details. In
> any case, it is thinkable of varying the number of iterations (making it
> an additional argument to "ft_trig_pseudo_rotate" and "ft_trig_pseudo_
> polarize"). E.g. using 17 iterations for FT_Cos, FT_Sin is enough. Things
> are no getting better using a 16.16 format. In other situations you are
> getting better result using more than the current 23 iterations.
the differences were not due to the CORDIC computations, only to classical
vector dot-products.

> Apart from 1) it's probably not worth taking any of the above into account.
>
> Also, I assume, the fttrigon.c code is mainly meant as a platform-
> independent implementation making it easy to compare different ports of
> freetype; so again, tweaking (except for the embedded folks) might not be
> worth it (having modern fpu's in mind).
Fact is that this code is not heavily used, so tweaking it will not
improve the engine performance in any noticable way :-)


> It was fun reading the fttrigon.c code and doing so running into the
> opportunity of getting to know some cordic things ... Thanks FreeType!
You're welcome :-)

> Eike.
>
> PS: In case of interest, I can dig out some code to illustrate the above.
Well, I'll be glad to accept a patch if you're certain that your new code
is correct. CORDIC is realtively hard to master in my opinion, so being careful
is important..


Best Regards,

- David Turner
- The FreeType Project  (www.freetype.org)