[Libre-soc-bugs] [Bug 782] add galois field bitmanip instructions

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=782

--- Comment #36 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to Jacob Lifshay from comment #35)

> yeah, i added the comments, i figured it would help with your algorithm
> dyslexia :)

yeah very much, thank you, was really straightforward.
amazingly this seems to get the right answer:

https://git.libre-soc.org/?p=libreriscv.git;a=commitdiff;h=0a9f45f2615f35902c4783bcdd07ab6151db841d

any change to "x" as long as it is less than 0x11b seems to
produce the correct value for y1 (bottom of the test), but
i had to hunt through a lot of random values of y to find one
that produced the right answer (again, independent of changes
to x)

no idea why, but hey

i guessed that "reducing polynomial" means the global "polyred",
and that from the for-loop "1 to 2*m" that this meant that m
is the degree, which then allowed me to use "if s & mask1"
which is testing the MSB

looking closely at the algorithm, now, i think we can use
"count-leading-1s" to skip ahead a number of loops:

    i = 1
    while i < 2*degree+1:
        jump = count_leading_1s(r)
        if jump == 0:
            ...
            ...
        else:
            r <<= jump            # jump left
            u <<= jump            # jump left
            j += jump

that would save on iterations, similar to how you can jump ahead
in long-division by detecting runs of zeros.

-- 
You are receiving this mail because:
You are on the CC list for the bug.