From 72d2f80259921792a0b0dc1033f1a7709d7a7abb Mon Sep 17 00:00:00 2001 From: lkcl Date: Sun, 17 Apr 2022 12:23:13 +0100 Subject: [PATCH] --- openpower/sv/bitmanip/appendix.mdwn | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) diff --git a/openpower/sv/bitmanip/appendix.mdwn b/openpower/sv/bitmanip/appendix.mdwn index 2796d7b40..ed6092ecc 100644 --- a/openpower/sv/bitmanip/appendix.mdwn +++ b/openpower/sv/bitmanip/appendix.mdwn @@ -34,3 +34,30 @@ void div(uint32_t *n, uint32_t *d, uint32_t* q, int n_bytes, int d_bytes) { // now remainder is in n and quotient is in q } ``` + +``` +On Sat, Apr 16, 2022, 22:06 Jacob Lifshay 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 +``` -- 2.30.2