fp64lib design principles

Creating a full blown 64-bit floating point library requires some planning and working structure. The following design and coding principles helped me to maintain consistency across the dozens of files and algorithms.

Design principles are overall guidelines, independent of the current algorithm. They cover both guidelines for the overall architecture of the library and the files within, but also some more implementation specific guidelines.

For some topics, like for the trigonometric functions (e.g. sine or cosine), I had to make a decision, which algorithm to choose. These special decisions are covered in the chapter “Design Desicions” below.

  1. Overall objective is to create a full blown 64-bit floating point library for the family of Atmel AVR microprocessors in assembly language. “Full blown” means, that all functions of “math.h” are available.
  2. In addition, also all functions implemented in avr_f64, the 64bit C library, will have to be made available.
  3. Minimize the code size, even at the cost of more execution time! Every byte counts!
  4. As a consequence, common routines (like shifting) are to be placed in separate files (1 routine per file) as a subroutine.
  5. In order to facilitate later integration into the AVR GCC compiler, structure and naming of files follows the already existing 32-bit float library, called libm32 throughout the rest of this document.
  6. All functions are callable via the C language interface.
    Externally called functions are prefixed by “fp64_”.
    Internal functions are prefixed by “__fp64_”.
  7. The library will not be designed to be re-entrant. i.e. it will neither support to be called via threads nor via interrupts. As even the simplest 64bit floating point operation will take several 100 instruction cycles, these operations shall not be used in interrupt routines.
  8. If possible, all values should be stored in registers.
  9. With the AVR 328 architecture, it is not possible to store more than 4 64bit values in its 32 registers. If an algorithm needs more space for variables, using static memory is preferred instead of using stack space, as it is easier to address and to handle. However, using static memory is only possible as the library is designed not to be reentrant. If you call library routines inside interrupts, unexpected side effects may happen due to the use of static memory!
  10. Macros are to be avoided as they extend code size. Exceptions are the commonly used “XCALL”, “XJMP” macros used in avr32 to hide code generation dependant on the target architecture .
  11. Follow the IEEE 754 standard very closely with the following exceptions:
    1. Only 1 rounding mode is implemented. → Rounding mode can not be set.
    2. Fp64lib only supports “silent signalling”.
  12. For testing the implementation, the results of avr64 are the “gold” standard. An algorithm is considered to be ok, if the results match the avr64 results – with the following exceptions:
    1. fp64lib implements calculations with subnormal numbers – these are not supported by avr64.
    2. Processing of non-normal numbers (NaN, +Inf, -Inf) in avr64 dows not always follow IEEE 754. fp64lib follows are more strict adherence to IEEE 754.
  13. fp64lib is targeted for Arduino and Arduino IDE users. Therefore, normal Arduino users have to be able to follow development and testing of the library. As a consequence, no special tools (like AVRsim or AVRice) can be used for testing and debugging.
  14. The significand is 52 bit plus the “hidden” leading bit, i.e. 53 bit in total which can be stored into 7 8-bit registers. The significand is always stored left-aligned including the “hidden” leading bit, i.e. the most significant bit (MSB) is always set. As a consequence of left-alignment, there are 3 “empty” bits at the right end (LSB) of the significand. These 3 bits are used to extend the significand to 56 bit. All internal calculations have to be made with at least 56 bit precision.
  15. For multiplication, internal calculation will be made with 72 bit (9 8-bit registers) to minimize rounding errors. Full 106 bit (2*53 bit) precision multiplication provides no benefit to 72 bit precision, which both are rounded to 53 bit for the end result.
  16. All constant values should be stored in program memory to avoid using memory for variables.
  17. For the trigonometric functions, for CORDIC algorithm was chosen to be superior regarding space efficiency than the usually used Taylor approximations.
    1. This design principle was changed, as CORDIC provides a non-constant precision, where in some conditions not more than 6 decimal digits were exact. The algorithms were changed to approximations with polynominals or rational polynominals, with some optimization to keep the speed and to reduce the memory footprint.
  18. If an algorithm was taken over from avr32, code structure (including naming of code labels) follows avr32 structure.
  19. To take advantage of AVR branch restrictions, special cases are checked at the very beginning of the code and the handling of these special cases is before main entry point of the file.
  20. Overall structure of a file is:
    1. Comment header, including license
    2. File specific definitions, e.g. declaration of register usage
    3. Code for handling special cases
    4. Main Entry
    5. Checking for special cases
    6. Implementation of algorithm
    7. Returning value
    8. Constant table(s), if needed
    9. Static memory reservation(s), if needed
  21. To allow internal calling of algorithms, routines should provide an entry point after arguments were unpacked and checked.