[Libre-soc-dev] SVP64 Vectorised add-carry => big int add

Jacob Lifshay programmerjake at gmail.com
Sun Apr 17 10:54:14 BST 2022


On Sat, Apr 16, 2022, 22:06 Jacob Lifshay <programmerjake at gmail.com> wrote:

> and a mrsubcarry (the one actually needed by bigint division):
> # for big_c - big_a * word_b
> result <- RC + ~(RA * RB) + CARRY # this expression is wrong, needs
> further thought
> CARRY <- HIGH_HALF(result)
> RT <- LOW_HALF(result)
>

turns out, after some checking with 4-bit words, afaict the correct
algorithm for mrsubcarry is:
# for big_c - big_a * word_b
result <- RC + ~(RA * RB) + CARRY
result_high <- HIGH_HALF(result)
if CARRY <= 1 then # unsigned comparison
    result_high <- result_high + 1
end
CARRY <- result_high
RT <- LOW_HALF(result)

afaict, that'll make the following algorithm work:

so the inner loop in the bigint division algorithm would end up being
> (assuming n, d, and q all fit in registers):
> li r3, 1 # carry in for subtraction
> mtspr CARRY, r3 # init carry spr
> setvl loop_count
> sv.mrsubcarry rn.v, rd.v, rq.s, rn.v
>

Jacob


More information about the Libre-soc-dev mailing list