[Libre-soc-dev] bigmul REMAP and pow(x,y,mod)

Luke Kenneth Casson Leighton lkcl at lkcl.net
Sun Oct 1 08:40:42 BST 2023

On Sunday, October 1, 2023, Jacob Lifshay <programmerjake at gmail.com> wrote:

> I didn't actually finish everything you said I did

ah ok. well divmod is pretty damn good.

>  -- I'm at the step
> right before having a working modular exponentiation algorithm -- I've
> implemented multiply and divmod, I haven't yet written powmod which is
> to be implemented in terms of those two.

awesome. that gets the algorithm first iteration done.
i do wonder though if Knuth D would be shorter (or only
10% greater or so). but that can be tackled incrementally.
i'd really love to have more budget for this one. sigh.
also are you planning to use function calls? (even just

btw a step in the logical reasoning, i missed out: i considered
the trick of using mfspr / mtspr to save/rollback SVSTATE.
this is perfectly valid but could slow down some implementations.
rough pseudocode:

   svindex something
   setvl VF=1

   mfspr r0, SVSTATE # save SVSTATE for later rollback

   svstep. # gets an inner-loop notification at some point
   bc CR0.EQ, inner1 # maybe not Eq bit but you get the idea

   mtspr SVSTATE, r0 # roll back SVSTATE

and in that way you can *re-run* a sub-portion of the REMAP
Schedule, hell even arbitrarily jump around to any part of it.
all of the "regoffsets" (srcstep, dststep) are all there, as long
as you don't alter the REMAP SPRs without also context-switching
them it's fine to do this sort of thing. just potentially slower.

hence instead considering an svshape3 which *explicitly* creates
a 3rd (middle) loop, which is effectively what the above
pseudocode is doing: shoving a "for k in (0,1)" right smack
in the middle of the REMAP Schedue, manually.


crowd-funded eco-conscious hardware: https://www.crowdsupply.com/eoma68

More information about the Libre-soc-dev mailing list