3 ms·

How easy is it to do bigint arithmetic in RISC-V?

by edflsafoiewq 7y ago

Dylan16807 7y ago
It has perfectly good add and multiply instructions, so uh easy? What at an ISA level would make it hard?
- ncmncm 7y ago
  Connecting from one word to the next. Do you have to do 32-bit multiplications so as to retain the high half of the result, or does a 64-bit multiply deliver the high 64 bits of the result somewhere? Also there is stuff about the carry from 64-bit addition. (Substitute 16 and 32, for 32-bit units.)
  - deleted 7y ago
    [deleted]
  - Dylan16807 7y ago
    There are instructions to get the top half of a multiply, and a suggested ordering so that the chip can deliver both halves with only one calculation. There's no carry flag but I'd say it's still easy to work around that.
    - deleted 7y ago
      [deleted]
    - waterhouse 7y ago
      Specifically, I think the "sltu" (set if less than, unsigned) instruction is useful for carries. When you add two unsigned integers, the result is smaller than the inputs if and only if an overflow occurred. ; a1:a0 * a2 --> a5:a4:a3 ; using t0 as temp reg mulhu a5, a1, a2 mulu a4, a1, a2 mulhu t0, a0, a2 mulu a3, a0, a2 add a4, a4, t0 ; carry a 1 or a 0, overwriting t0 sltu t0, a4, t0 add a5, a5, t0 (edit: switched a1 and a0 for consistency)
- edflsafoiewq 7y ago
  On x86 you'd do a bigint add with an ADC chain. In RISC-V I think it would be a lot more branchy.
  - bloak 7y ago
    I know nothing about RISC-V, but my usual way of finding out how to do something standard with a given instruction set is to ask a compiler. There are online compilers, such as this one: https://cx.rv8.io/ https://cx.rv8.io/ Just type in "__int128 add(__int128 a, __int128 b) { return a + b; }" on the left, stick "-O2" into the "Compiler options", and see what you get! I don't know whether that particular compiler is doing the right thing, of course, but it gives you an idea and it's definitely less work than reading the spec.
  - waterhouse 7y ago
    No need for branches, see comment above demonstrating sltu. For a long carry chain, I guess it might look like this: ; Inputs: x = 4-word number, in a3:a2:a1:a0, ; y = 1-word number, in a4. ; Output: x+y, 5-word number, in a4:a3:a2:a1:a0. add a0, a0, a4 sltu a4, a0, a4 ; a4 = carry bit add a1, a1, a4 sltu a4, a1, a4 ; a4 = carry bit again add a2, a2, a4 sltu a4, a2, a4 add a3, a3, a4 sltu a4, a3, a4
    - edflsafoiewq 7y ago
      Ah, nice, thank you! I must have missed sltu.

How easy is it to do bigint arithmetic in RISC-V?

Dylan16807 7y ago

It has perfectly good add and multiply instructions, so uh easy? What at an ISA level would make it hard?

ncmncm 7y ago
Connecting from one word to the next. Do you have to do 32-bit multiplications so as to retain the high half of the result, or does a 64-bit multiply deliver the high 64 bits of the result somewhere? Also there is stuff about the carry from 64-bit addition. (Substitute 16 and 32, for 32-bit units.)
- deleted 7y ago
  [deleted]
- Dylan16807 7y ago
  There are instructions to get the top half of a multiply, and a suggested ordering so that the chip can deliver both halves with only one calculation. There's no carry flag but I'd say it's still easy to work around that.
  - deleted 7y ago
    [deleted]
  - waterhouse 7y ago
    Specifically, I think the "sltu" (set if less than, unsigned) instruction is useful for carries. When you add two unsigned integers, the result is smaller than the inputs if and only if an overflow occurred. ; a1:a0 * a2 --> a5:a4:a3 ; using t0 as temp reg mulhu a5, a1, a2 mulu a4, a1, a2 mulhu t0, a0, a2 mulu a3, a0, a2 add a4, a4, t0 ; carry a 1 or a 0, overwriting t0 sltu t0, a4, t0 add a5, a5, t0 (edit: switched a1 and a0 for consistency)
edflsafoiewq 7y ago
On x86 you'd do a bigint add with an ADC chain. In RISC-V I think it would be a lot more branchy.
- bloak 7y ago
  I know nothing about RISC-V, but my usual way of finding out how to do something standard with a given instruction set is to ask a compiler. There are online compilers, such as this one: https://cx.rv8.io/ https://cx.rv8.io/ Just type in "__int128 add(__int128 a, __int128 b) { return a + b; }" on the left, stick "-O2" into the "Compiler options", and see what you get! I don't know whether that particular compiler is doing the right thing, of course, but it gives you an idea and it's definitely less work than reading the spec.
- waterhouse 7y ago
  No need for branches, see comment above demonstrating sltu. For a long carry chain, I guess it might look like this: ; Inputs: x = 4-word number, in a3:a2:a1:a0, ; y = 1-word number, in a4. ; Output: x+y, 5-word number, in a4:a3:a2:a1:a0. add a0, a0, a4 sltu a4, a0, a4 ; a4 = carry bit add a1, a1, a4 sltu a4, a1, a4 ; a4 = carry bit again add a2, a2, a4 sltu a4, a2, a4 add a3, a3, a4 sltu a4, a3, a4
  - edflsafoiewq 7y ago
    Ah, nice, thank you! I must have missed sltu.