A Fixed Point Arithmetic Library


#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!


(goes by "spacebruce" elsewhere) #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.


(Pharap) #21

Like I say, I’ll cross that bridge when I get to it.
I like to do research and testing before adding features because it’s better to delay a new feature in an attempt to pre-empt problems than it is to retroactively remove a feature.

I’ve already learnt my lesson from the random number facility
(which I plan to either remove or migrate in future).