A Fixed Point Arithmetic Library


(Pharap) #1

For a long time now people have mentioned fixed point arithmetic here and there, but I’ve always thought it’s a shame that it’s not something more accessible to less experienced users. Worse yet the amount of online explanation of fixed point arithmetic is few and far between, so it’s difficult for even experienced programmers to find a good level of information about it.

Hence for the last 2-3 months I’ve been secretly working (on and off) on a library that will help to make fixed point arithmetic more accessible.

I was originally intending to only announce the library today and to delay the release for a few more days until I could add more tutorials and demos, but I really need a break from working on it, so I’m releasing it now.

It isn’t yet available from the library manager, but I have requested that it be added so it should be available eventually. (It’s issue #6777.)

It has been accepted into the library manager, so including the library is just a matter of:

#include <FixedPoints.h>
#include <FixedPointsCommon.h>

Note that the former header sets up the templates and the latter sets up type aliases. i.e. the former includes types like UFixed<8, 8>, SFixed<7, 8> etc and the latter includes types like UQ8x8, SQ7x8. Including the latter is recommended for people who aren’t used to using templates.


The README.md is a reasonable introduction to the library, but for more information about fixed points I added this:

It’s a bit on the tecnical side, but fear not, there is hopefully going to be a more friendly tutorial in this month’s Arduboy magazine, written by @filmote with minor edits from myself.


During the development of this library, a few select users (most of whom I had prior contact with) were informed about this library before its release.

One of these users was @filmote, who liked the idea enough that he ended up using the library in the game he was developing at the time, so it sort of turned into an ‘eat your own dogfood’ situation where @filmote was testing the library by using it in his game. This was a two way deal, @filmote got smooth movement and relatively quick bugfixes whilst I got a free source of actual road testing which helped bring up bugs to be squashed and feature requests.

@filmote’s game is the first game to use the FixedPoints library so I’m giving it a prominent placement here:

I’d be happy to list/link to any other games or programs that make use of this library in the future.


Special thanks to:

@filmote - head tester

@eried - early helper

Special mentions to:

@crait, @Bergasms

And last but not least,
thanks to @noel_abercrombie, king of the ducks.


Fixed point multiplication
Help With Game Develeopment
Multiplayer implementation ideas and stream of consciousness for Speed Snake
[WIP] Raycaster
#2

This looks great! I’ve been using fixed point numbers a lot for transformations, but my code has gotten a lot harder to follow as a result. It will be awesome to see this in the library manager!


(Simon) #3

I used this in my 1943 game … made the code much simpler!


(Bruce) #4

Congratulatory quack


#5

nice library and nicely written with good usage of modern c++ which is still rare these days imho.


(Simon) #6

Its really a work of art, isn’t it ?


(Scott) #7

If you change your 1943 game to link to FixedPoints installed as a library, or any other game does, I’ll add FixedPoints to the list of recommended libraries in step 2 of the Quick Start Guide.


Happy New Year 2018 How are we doing?
[WIP] Raycaster
(Pharap) #8

I think it’s a tragedy that more people aren’t using modern C++ techniques, hence I’m always trying to drill the modern features into people. They’re not just handy, they improve type safety, readability and in some cases performance.


(Boti Kis) #9

Can you also add it to PlatformIO please? :heart:


(Pharap) #10

I’ll look into doing that at some point.
I haven’t used PlatformIO before so I’ll have to investigate it first.

It probably won’t be for at least a couple of days.
I’m going on/have gone on a short C++ programming hiatus because this project has burnt me out somewhat (though I don’t know how long it will last, I’m a bit of a programmaholic).


(Scott) #11

The FixedPoint library has a library.json file for PlatformIO, so adding it should be easy.
http://docs.platformio.org/en/latest/userguide/lib/cmd_register.html

The manifest URL for library registration:
https://raw.githubusercontent.com/Pharap/FixedPointsArduino/master/library.json


(Simon) #12

Thanks @MLXXXp - the 1943 game was a test bed for some of the functionality in the FixedPoints library during my testing. I actually released the game before @Pharap was ready to release his code so packaged the library as it existed then with it. The next steps for my game are to update the library to the released version which will allow me to not package it.


(Pharap) #13

Thank you for your patience, PlatformIO support has been added as of version 1.0.2.


(Felipe Manga) #14

I decided to experiment with @Pharap’s FixedPoints library in my jam entry.
The optimal format in my case is SQ23.8 and I need to do a lot of multiplication.

Basically, multiplying two 23.8 numbers looks something like this:
result = A * B >> 8;

Unfortunately, the right shift is done by dividing by 256 instead of simply discarding the lower byte.
In my game, this results in a hex file with 22370 bytes and a cpuLoad of over 110. Too big, too slow.

I added the following template specialization and the hex file dropped to 18118 bytes (4250 bytes smaller), with a cpuLoad of 80.

template<>
SFixed<23,8> operator *(const SFixed<23,8> & left, const SFixed<23,8> & right)
{
  int64_t r = left.getInternal() * right.getInternal();
  uint8_t *b = reinterpret_cast<uint8_t *>(&r);
  return SFixed<23, 8>::fromInternal( *reinterpret_cast<int32_t*>(b+1) );
}

(Pharap) #15

This is one of the reasons I made the library template heavy, it’s very easy to specialise.

The library is designed more with the power of two cases in mind (4.4, 8.8, 16.16, 32.32),
I haven’t spent much time on the in between cases, in part due to apparent lack of interest.

The larger types will always be somewhat costly on the AVR chips - no barrel shifter, no division opcode, the need to chain addition/subtraction opcodes, the multiplication opcode only working on 8 bit quantities.

I was hoping the compiler was smart enough to realise that >> 8 means it can just discard the lower byte.
It has realised that in previous cases, but maybe that’s because smaller types were being used.

I also want to point out that pointer arithmetic on void * is in fact illegal and the only reason that b + 1 works here is because of GCC’s compiler extensions.
Using uint8_t * would be a more portable solution.

Either way, it will be good to see another game using FixedPoints.


(Felipe Manga) #16

I hoped so too and I didn’t even bother checking, but it showed up when I profiled the code.
Here’s a specialization for SQ15.16.

template<>
SFixed<15,16> operator *(const SFixed<15,16> & left, const SFixed<15,16> & right)
{
  int64_t r = left.getInternal() * right.getInternal();
  uint8_t *b = reinterpret_cast<uint8_t *>(&r);
  return SFixed<15,16>::fromInternal( *reinterpret_cast<int32_t*>(b+2) );
}

I’ll edit the previous post to use uint8_t. I’m still rusty from all the javascript I’ve been writing. :stuck_out_tongue:


(Pharap) #17

I’ve got an issue ready:

I’ll look into actually editing them in at a later date,
I’ve already got a bit of a backlog of issues.

I’ll have to investigate what the best way to do it is though.
I’m aware that type punning is sometimes frowned upon because it can have some unexpected implications.
(Also endianness could be an issue.)


Sometimes I use void main(void) despite knowing the standard forbids it,
but otherwise I try to avoid extensions and stick to the standard.


(Felipe Manga) #18

You’re probably not going to be able to find a very good cross-platform solution. The ideal implementation is what you already have, especially on other processors like ARM. Forcing it to drop bytes is getting around a specific platform+compiler oddity (or a bug?), so I’d use #ifdef __AVR__ around the specializations and would not have to worry about endianness.


(Pharap) #19

I’ll think about it more when I get round to handling it.
It probably will come down to handling different processors specifically, but preliminary research indicates that unions might be a better solution than pointers as a precaution (inlining is somewhat likely, and statement rearrangement may follow).

(I’d have to check whether that only applies to C, but chances are C++ inherited it.)


(Felipe Manga) #20

I tried this:

template<>
SFixed<23,8> operator *(const SFixed<23,8> & left, const SFixed<23,8> & right)
{
  union {
    struct {
      uint8_t pad;
      int32_t i32;
    };
    int64_t i64;
  } u;
  u.i64 = left.getInternal() * right.getInternal();
  return SFixed<23, 8>::fromInternal( u.i32 );
}

It works, but produces slightly larger code. I’m not sure I’d prefer this, both are ugly code smells to get around a compiler derp.