sysprog21 / mado

A window system for resource-constrained devices
MIT License
33 stars 12 forks source link

Shrink the size of sine table #13

Closed jserv closed 1 month ago

jserv commented 1 month ago

In the file src/trig.c, there is a lookup table for the sine function pre-calculated with fixed-point arithmetic. According to the size command provided by binutils, the lookup table and its related functions (sin, cos, tan) contribute more than 2 KiB to the code size on Aarch64.

$ size .libtwin.a/src/trig.c.o
   text    data     bss     dec     hex filename
   2460       0       0    2460     99c .libtwin.a/src/trig.c.o

Instead of relying on table lookups, we can perform calculations on the fly and ensure a reasonably fast response time by utilizing a smaller table or a combination of bit operations. Additionally, instead of invoking twin_sin and twin_cos functions, we can use the sincos function to retrieve sine and cosine values simultaneously, reducing the number of function calls.

Reference: 2024 Report

jserv commented 1 month ago

libfixmath implements Q16.16 format fixed point operations in C. When FIXMATH_FAST_SIN is enabled, its fast implementation for sin operates at 159% the speed of its most accurate version, with a slightly lower accuracy of approximately 2.3%. See fix16_trig.c

In addition, libfixmath64 is a derived version of libfixmath, converted into Q31.32 (Q31) format for larger integer range.

jserv commented 1 month ago

The q is a small fixed point number library, and its format is a signed Q16.16. The trigonometric functions, and some others, are implemented internally with CORDIC.