Recent

Author Topic: Integer maths > 16 bits  (Read 2383 times)

MarkMLl

  • Hero Member
  • *****
  • Posts: 8032
Integer maths > 16 bits
« on: September 15, 2024, 04:08:09 pm »
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?

Area of application is hash algorithms etc., with the assumption (please) that hardware support for these will not be available.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

Thaddy

  • Hero Member
  • *****
  • Posts: 16184
  • Censorship about opinions does not belong here.
Re: Integer maths > 16 bits
« Reply #1 on: September 15, 2024, 07:29:52 pm »
All you need is rolls, shifts, and, or, xor, not and a byte array.
This stems from the olden days. Easiest if there are not signs involved.
If I smell bad code it usually is bad code and that includes my own code.

MarkMLl

  • Hero Member
  • *****
  • Posts: 8032
Re: Integer maths > 16 bits
« Reply #2 on: September 15, 2024, 07:52:54 pm »
Actually Thaddy, I need + -  * div mod and shr. I'm /entirely/ capable of writing them in assembler... I'd just rather not.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

PascalDragon

  • Hero Member
  • *****
  • Posts: 5755
  • Compiler Developer
Re: Integer maths > 16 bits
« Reply #3 on: September 15, 2024, 09:01:22 pm »
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?

At least 32- and 64-bit math should be fully supported at least if you compile the RTL using software floating point (assuming the processor in question does not support the operations in hardware). If hardware support is available then everything should work out fine if you simply compile for the target.

Only for 128-bit math I don't know right now whether we have some suitable unit already.

MarkMLl

  • Hero Member
  • *****
  • Posts: 8032
Re: Integer maths > 16 bits
« Reply #4 on: September 15, 2024, 09:47:37 pm »
Only for 128-bit math I don't know right now whether we have some suitable unit already.

ATM it's the 128-bit case that's most interesting, but I thought I'd build up gradually through the other types since they might not (by default at least) be implemented on small chips.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Integer maths > 16 bits
« Reply #5 on: September 16, 2024, 08:02:56 am »
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
« Last Edit: September 16, 2024, 08:08:27 am by MathMan »

440bx

  • Hero Member
  • *****
  • Posts: 4737
Re: Integer maths > 16 bits
« Reply #6 on: September 16, 2024, 08:06:24 am »
MathMan, you got a typo in your signature/name.
(FPC v3.0.4 and Lazarus 1.8.2) or (FPC v3.2.2 and Lazarus v3.2) on Windows 7 SP1 64bit.

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Integer maths > 16 bits
« Reply #7 on: September 16, 2024, 08:09:42 am »
MathMan, you got a typo in your signature/name.

Thanks for the heads up - getting lazy with the internal spell checker routines  :D

MarkMLl

  • Hero Member
  • *****
  • Posts: 8032
Re: Integer maths > 16 bits
« Reply #8 on: September 16, 2024, 08:49:10 am »
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

Many thanks I'll look at that- not necessarily immediately, but definitely.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MarkMLl

  • Hero Member
  • *****
  • Posts: 8032
Re: Integer maths > 16 bits
« Reply #9 on: October 10, 2024, 06:52:33 pm »
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

Code: Pascal  [Select][+][-]
  1. const
  2. {$if declared(int128types) }
  3.   hashed128= tUInt128.Q[qword(0), qword(0)];
  4.   primed128= tUInt128.Q[qword(0), qword(0)];
  5. {$endif                    }
  6.  

but that just results in "Illegal qualifier" ... "Illegal expression" errors.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Integer maths > 16 bits
« Reply #10 on: October 10, 2024, 07:20:33 pm »
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

Code: Pascal  [Select][+][-]
  1. const
  2. {$if declared(int128types) }
  3.   hashed128= tUInt128.Q[qword(0), qword(0)];
  4.   primed128= tUInt128.Q[qword(0), qword(0)];
  5. {$endif                    }
  6.  

but that just results in "Illegal qualifier" ... "Illegal expression" errors.

MarkMLl

First - thanks that you're spending the time trying it out.

Second - you got me on the constant expressions. I didn't need them so I haven't spent thought on it so far. Let me do some tinkering and get back to you, ok?

MathMan

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Integer maths > 16 bits
« Reply #11 on: October 10, 2024, 07:40:21 pm »
Ah, somewhat uninspired that is - the following works for me

Code: Pascal  [Select][+][-]
  1. const
  2.   Trial1: tUInt128 = ( L:0; H:0 );
  3.   Trial2: tUInt128 = ( Q:( 0, 0 ) );
  4.  

I did the type system like it is because I thought that I could cover endianess that way. Turns out not possible for constants as

 - in Trial1 FPC does not sort the H,L parts but needs them in the sequence defined. You'll still have to keep two constant definitions depending on endianess

- in Trial2 you simply have an array of UInt64 so you end up as above

Pitty,
MathMan

MarkMLl

  • Hero Member
  • *****
  • Posts: 8032
Re: Integer maths > 16 bits
« Reply #12 on: October 10, 2024, 07:51:37 pm »
A/ha/. So basically I'd managed to fumble : and = into the wrong sequence.

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).

I'll post some code for people to laugh at presently.

MarkMLl
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

MathMan

  • Sr. Member
  • ****
  • Posts: 405
Re: Integer maths > 16 bits
« Reply #13 on: October 10, 2024, 08:01:44 pm »
...
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

Noted - like say Zero128, One128 & Max128? You have a more inspired suggestion?

Beside - I'd probably use the Q-variant of definition, the outer brackets may be superfluous - I didn't check.

MarkMLl

  • Hero Member
  • *****
  • Posts: 8032
Re: Integer maths > 16 bits
« Reply #14 on: October 10, 2024, 08:18:37 pm »
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
MT+86 & Turbo Pascal v1 on CCP/M-86, multitasking with LAN & graphics in 128Kb.
Logitech, TopSpeed & FTL Modula-2 on bare metal (Z80, '286 protected mode).
Pet hate: people who boast about the size and sophistication of their computer.
GitHub repositories: https://github.com/MarkMLl?tab=repositories

 

TinyPortal © 2005-2018