search

piggypiggy / fp256

An efficient library for 256 bit integer arithmetic
Apache License 2.0
43 stars 12 forks source link

Improve ll_u256_mont-riscv64.S to support wider width(384) #4

Open XuJiandong opened 3 years ago

XuJiandong commented 3 years ago

Hi @piggypiggy , We're trying to improve ll_u256_mont_mul (risc-v version) to support wider width(e.g.384 bits) . Is there any reference C implementation (or something like that) of this assembly implementation? So we can modify it much easier. Thanks.

piggypiggy commented 3 years ago

I didn't write or find 384 bit's c implementation, there is only pesudo code: paper page 7. There are c implementations for arbitrary size of integer: here and blst, armv8 384 bit implementation: blst armv8, they might be good references.

I found it quiet hard to modify ll_u256_mont-riscv64 to ll_u384_mont-riscv64 since you need to reconsider the register assignment, it brings lots of changes.

My advice: follow the pesudo code to write your own riscv code, if you find some piece of ll_u256_mont-riscv64.S useful, then copy it.

XuJiandong commented 3 years ago

Thanks @piggypiggy . Does blst version share the same algorithm as the implementation of ll_u256_mont-riscv64.S? l_u256_mont-riscv64.S is really difficult to understand.

piggypiggy commented 3 years ago

blst's c mul_mont_n implementation is the same as ll_mont_mul.c, ll_u256_mont_mul-riscv64,aarch64,x64 and blst's mul_mont_256-armv8,x86_64. But they are slightly diffrent from the pesudo code, instead they compute and plus A*B[i] then reduce it, repeat n times. You can verify that they are equivalent.

blst's 384 bit sqr_mont and fp256's mont_sqr asm code follow the pesudo code exactly. They compute A*B at first, then reduce n times.

XuJiandong commented 2 years ago

Follow up: we've ported some part of blst's assembly code into RISC-V. It's used in our Smart contracts. https://github.com/nervosnetwork/ckb-miscellaneous-scripts/tree/master/blst We need specialists like you. If you're interested in our projects, please contact me via xjd@cryptape.com.