What are the options for 32-, 64- and 128-bit five-function integer maths on devices like the RP2040 and arbitrary RISC-V targets, with minimal external dependencies?
Only for 128-bit math I don't know right now whether we have some suitable unit already.
MathMan, you got a typo in your signature/name.
Hi MarkMLI,
Take a look at the attached. Though not fully fleshed - missing some stuff for signed integers - it may be a good starting point. External dependency - FPC has to provide support up to 64 bit types, which I understand from PascalDragons response can be assumed.
If you want/need to extend, then pls let me know. Maybe I can help.
Cheers,
MathMan
I've spent roughly the last day adding 64-bit handling to some units that hash text (for CHAP-style password checking etc.) and inefficiently test for primality, and then moved on to incorporating your 128-bit library.
I've /twice/ been bitten by the same problem: import the types unit but forget the one with the code, and then wonder why operators don't work. It's one of those damn silly things and is of course entirely self-inflicted, but things /almost/ work to an extent that allows one to overlook the obvious cause.
The thing that's really giving me problems is constant handling. The lack of in-expression tuples is obviously a problem, but what's the correct incantation: I'd have expected it to be something like
but that just results in "Illegal qualifier" ... "Illegal expression" errors.
MarkMLl
...
I'd suggest that predefined constants for the additive and multiplicative identities and all-bits-set would be useful (actually applies to all types IMO).
...
MarkMLl
I'd suggest Zero128, Unity128 and AllBits128.
At present I'm using the L and H forms, because we know that the compiler will object if the endianess changes. I'm hoping at some point to crank up my surviving SPARC system which will allow a bigendian test...
MarkMLl
I'll probably post the test code I'm using tomorrow. It applies a fairly naive hashing algorithm to a passphrase for a number of word sizes (originally 16 and 32 bits, now also 64 and 128) and then tries to find the nearest prime to the result... obviously this is slow when word size is large.
Obviously during startup I'm running testcases, and Near128Prime(0) highlights that it would be useful to be able to suppress range/overflow checks when crossing zero. Apart from that there's the missing mod operator (which can be easily refined locally).
If you would also show the source of Near128Prime I'd take a look at that too. I assume that function takes a considerable amount of the overall execution, especially in the 128 bit case. There are some pretty interesting detection algorithms out there - but I'd first have to deep-dive into the math. So /if/ I can speed that up then it will take some time.
If you only need mod for unsigned types then I can add that pretty fast.
If you would also show the source of Near128Prime I'd take a look at that too. I assume that function takes a considerable amount of the overall execution, especially in the 128 bit case. There are some pretty interesting detection algorithms out there - but I'd first have to deep-dive into the math. So /if/ I can speed that up then it will take some time.
If you only need mod for unsigned types then I can add that pretty fast.
Compilable project before the end of tomorrow. Unsigned mod would be entirely OK, possibly also Odd() which should be another easy one.
MarkMLl
Ok, I'll start with mod. Look for 'IsOdd' it's already there - now that I look at it I can't remember why I named it that way. Especially as I declared it as 'overload' which would hint as me trying to overload it to the RTL function, which however is 'odd' :o
- I consider implementing 'DivMod' which would return quotient and remainder from a single calculation. As often both values are needed in concert that might be worth the effort to implement. Your take?Yes, please: I use divmod a lot for all kind of purposes. ( although for my purposes I doubt if I need a big integer library for that.)
- I consider implementing 'DivMod' which would return quotient and remainder from a single calculation. As often both values are needed in concert that might be worth the effort to implement. Your take?Yes, please: I use divmod a lot for all kind of purposes. ( although for my purposes I doubt if I need a big integer library for that.)
Basically processing a value in chunks (div) and then process the remainder (mod). Would be nice to have it thread safe.
Uhm, thread safety wasn't on my agenda so far as this is only 128 bit math and I'm not sure about use cases that would need thread safety here. We can take that offline I guess - PM me please.
- I'd like to clean up on the signed types 'div' and 'mod' operators. But I'm unsure about the direction. Issue is - the way FPC calculates these for ordinal types is mathematically incorrect. Should I now go for the 'correct' implementation or continue the 'used too' to 128 bit? This is a question also to everybody else who happens to read this thread, or has downloaded my first version of the library - I know there are some.
I think it might be necessary to have some way of passing "out of band" state to the library, and this would definitely need to be thread-safe.
The exception I commented on earlier appears to be caused by overflow checks being enabled at the project level, so when Int128 was compiled with overflow checks enabled at the project level mandatory exceptions were built in: they can't be disabled by {$q- } at the point of invocation.
So while for operands of <= 64 bits this works:
it's ineffective for 128-bit operands.
That implies that it would be useful to have something like PushChecks and PopChecks procedures, plus CheckOverflow and possibly something like CompilerMode so that a caller could tell the library how the mod operator should behave.
Also I think it would be desirable if all exception messages were distinct, even if they were only distinguished by (a), (b) and so on.
If even a trivial change had been made to the library since it was last compiled, the exception address could easily be out of step with reality.
- implement a checked and unchecked type variant and extend the operator overloading accordingly
- if you want to disable checks on the invocation level then you can use the unchecked type for calculations
...
In the interim, I've put this at the top of int128.pas to decouple the checks it uses internally from the rest of the project.
I'd also note that I'm defining USE_FPC64 and USE_INT128 at the project level. I might remove the first of those after I've checked the situation on the RPi Pico etc., although that definitely won't be this week.
MarkMLl