search

llvm-mos / llvm-mos-sdk

SDK for developing with the llvm-mos compiler
https://www.llvm-mos.org
Other
281 stars 56 forks source link

Add fixed point math library #316

Closed jroweboy closed 8 months ago

jroweboy commented 9 months ago

Add a general purpose fixed point math library. Leaving it as a draft PR until I get the time to add the test cases to llvm-test-suite and fix any issues we find there. (I wasn't able to build locally so I've been developing in godbolt in the meantime)

Also I think there's some ambiguous resolve errors for comparing fixed point numbers right now that I need to fix before merging too. I would expect that number = 9.4_8_8; number > 7.7_8_8 should work, but it can't decide which comparison operator to use and errors out currently.

I am just pushing this here so I don't lose track of it, but if you want to do an early review to help out with code clarity/style/etc feel free to do so!

johnwbyrd commented 9 months ago

There's a great deal of relevant prior art here. Examples:

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0037r7.html https://www.open-std.org/JTC1/SC22/WG14/www/docs/n1169.pdf https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0106r0.html https://github.com/mizvekov/fp

Have courage... I don't believe that you are solving an easy problem.

mysterymath commented 9 months ago
  • I don't see support for multiplication or division of your novel type. Handling the various cases in multiplication and division (choosing a destination precision, respecting or disrespecting overflows, respecting the sign bit if any, normalizing to the destination type) is one of the most inconvenient problems in computing with frac's, and I would hope that we could help out the user in this regard.

I'd like to push back on this, at least for multiplication of two fixed points, since implementing it well is quite nontrivial. I don't think a minimum viable version of this needs to support it, since it's also not very common in the NES scene that is requesting the feature (correct me if I'm wrong on this one).

johnwbyrd commented 9 months ago

Handling the various cases in multiplication and implementing it well is quite nontrivial. I don't think an initial version of this needs to support it, since it's also not very common in the NES scene that is requesting the feature

I think it's worth considering now, exactly because of its nontriviality. It is exactly the sort of thing that's hard to add later, once you bet the farm on a specific architecture. At the very least, I think it's not unreasonable to ask @jroweboy to review the references that I provided, and report back and see if he's had any novel enlightenment. Even if we don't implement it now, I'd like to be assured that we can implement it later.

mysterymath commented 9 months ago

Handling the various cases in multiplication and implementing it well is quite nontrivial. I don't think an initial version of this needs to support it, since it's also not very common in the NES scene that is requesting the feature

I think it's worth considering now, exactly because of its nontriviality. It is exactly the sort of thing that's hard to add later, once you bet the farm on a specific architecture. At the very least, I think it's not unreasonable to ask @jroweboy to review the references that I provided, and report back and see if he's had any novel enlightenment. Even if we don't implement it now, I'd like to be assured that we can implement it later.

It's not hard to add pretty much anything later; we still have very loose backwards compatibility guarantees, and the newer the feature, the looser they are. The only exception is things that a bunch of other features in the SDK end up depending on, but that's wildly unlikely for a C++ fixed point library. Better is the enemy of good, and once a few problems have been resolved, this will be pretty useful even at its current scope.

johnwbyrd commented 9 months ago

The NES community has waited approximately 39 years for this feature; I don't necessarily think a day or two of delay will break anyone's heart.

I'm not saying don't do it; I'm just saying that now is the best time for due diligence and stealing good ideas.

mysterymath commented 9 months ago

The NES community has waited approximately 39 years for this feature; I don't necessarily think a day or two of delay will break anyone's heart.

I'm not saying don't do it; I'm just saying that now is the best time for due diligence and stealing good ideas.

I don't think that literature reviews should be a prerequisite for contributing to a hobby compiler that we work on for fun. llvm-mos should welcome authors with all degrees of seriousness, and the purpose of asking more from someone in a code review should only to be ensure that the fun the author is having is balanced well with the fun the users of what they write will have.

In any case, I don't think this PR is the correct venue for this discussion; we should move this to Discord. In the interim, I'll use my sway as current maintainer to say that this PR should proceed as-is if and while we have a broader discussion about what we want our bar to be.

jroweboy commented 9 months ago

It looks to me that your code rounds the int and frac components to byte boundaries. What about the case of odd fractional formats, such as 10.8 or 5.3? I don't see your code exercising those cases.

Thanks to feedback here, I'm testing out using the bitfield support built-in to the compiler to see if the code gen is still just as good. Note that even in this original code it still supports 5.3 as the StorageSize is just the sum of the int/frac types, and masking is used to break it down into the correct int/frac sizes. The IntSize being rounded up was just to get better codegen since it didn't like as_i and other methods to take a non-rounded bitint number.

There's a great deal of relevant prior art here

Yes! And there's also prior art for high level languages with the 6502 as well. I spoke with pubby (maker of nesfab) which is a compiler with builtin fixed point support to get some ideas of what is expected from this feature. NESFab only support byte sized fractional values, but still has compile time float -> fixed support like I want to offer here. Multiplication extends the values into the combined size of the output type (so if you have an 8.8 * 12.4 it becomes 20.12) and division is unimplemented as its rather troublesome for something people don't use in practice.

The test suite (if that was its intention) seems a little thin.

I mentioned this in the original post, but the test suite will be added to llvm-mos-lit test cases once I've established the implementation a little better.

I'm down to work towards a multiplication solution that addresses all of your concerns, especially since there's existing art for this on 6502 systems (well at least the one i'm familiar with), but I'm not so keen on division as it quickly becomes problematic for very little benefit IMO.

mysterymath commented 9 months ago

I'm down to work towards a multiplication solution that addresses all of your concerns, especially since there's existing art for this on 6502 systems (well at least the one i'm familiar with), but I'm not so keen on division as it quickly becomes problematic for very little benefit IMO.

So long as the fixed point type sizes are identical, (a * 2^-f) / (b * 2^-f) = a / b = (a * 2^f / b) * 2^-f. Accordingly, it's only slightly more difficult than division by a non-fixed-point integer:a 2^-f / b = (a / b) 2^-f`. It gets complex if the fixed point fractions are different, but that can be also be called out as a compile time error. The difficulty in this case, as with multiplication, is that wider arithmetic must be done, and it can be difficult to do this efficiently.