Re: PPC bn_div_words routine rewrite

[David Ho <davidkwho@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 5108 bytes --]

Good morning gentleman,  

Let's start the week off with less hostility and more productive
criticism on this topic.  As I see it, the popular Linux distributions
are not that interested on ppc32 since neither Novell nor Redhat
openly support this arch.  We will have to put our heads together to
make ppc32 a stable Linux platform.

On 7/1/05, Andy Polyakov <appro@fy.chalmers.se> wrote:

> BN_div_word does write to memory, but I fail
> to see how a bogus value could possibly trigger seg-fault. 

Assuming that you are a maintainer of the openssl code, which I gather
you are, would you even care to take the time to examine the code in
suspect, or find someone who is capable of doing that, I'm sure you
must have a lot of friends, at least one who is knowledgeable in the
ppc32 arch.

> The only
> possibility is that assembler doesn't follow ABI convention and corrupts
> registers, which caller is using/expects to be preserved by callee.
> There're several PPC ABI flavors in use, but OpenSSL routines were
> designed ABI-neutral, Well, "neutrality" really means "common
> denominator for ABI specs examined at the moment of coding," so there is
> a window of opportunity that it won't be "neutral" to future ABI, but is
> it really case? 

I don't understand the terminology you use here.  As I understand it
ABI is there so binaries can inter-operate in the case of dynamic
loading, when the ABI is consistent you can use any compiler that
conforms to the ABI and those binaries can work together.  As I see it
I'm building openssl and openssh with the same compiler so what is the
real issue here?  Or is it an issue at all?

If you are referring to C calling convention, then I can only guess
you have figured it out or otherwise none of the assembly routine will
work.

> That your system uses some newly designed PPC ABI? You
> never mentioned what's your system...

In my very first email, I have already said quote "tested on a MPC8xx
processor"  and I am using 2.4.24 which is nothing close to the
bleeding edge so I reckon the ABI is fairly standard.

Do you have any experience with the PowerPC arch?  

> But you're apparently right about a bug being present in PPC assembler.

So you are saying there is a bug in the GCC assembler?  How confident
are you in that?  Is the first correct step to examine the assembly
code for errors before jumping to any conclusion that the GCC
assembler is bad?

> >>This is a rewrite of the bn_div_words routine for the PowerPC arch,
> >>tested on a MPC8xx processor.
> 
> Well, suggested routine apparently sends ssh-keygen on the PPC-based
> 32-bit system I have access to to an end-less loop... 

If you care to read the c function I supplied or if you don't believe
it:  If you understand ppc 32-bit instructions, as specified in the
PowerPC Microprocessor Family: Programming Environments for 32-Bit
Microprocessors.  My routine would not be able to find a condition
that will make it go into an end-less loop,unless you messed up bad
somewhere.

> And (cd test; make
> test_bn) fails early in BN_sqr... And test/exptest fails miserably with
> "bad reciprocal"...

I don't know what you did but (make test_bn) works for me.  So I
question how diligently you are in setting up the tests.  If you are
busy, please get one of your ppc friends to do it.

> >>I initially thought there is maybe a small mistake in the code that
> >>requires a one-liner change
> 
> But apparently this appears to be the case! Please verify following:
> 
> --- crypto/bn/asm/ppc.pl.orig        2004-04-28 00:05:50.000000000 +0200
> +++ crypto/bn/asm/ppc.pl      2005-07-01 18:58:21.105656512 +0200
> @@ -1717,7 +1717,7 @@
>          li      r9,1                    # r9=1
>          $SHL    r10,r9,r8               # r9<<=r8
>          $UCMP   0,r3,r10                #
> -       bc      BO_IF,CR0_GT,Lppcasm_div2       #or if (h > (1<<r8))
> +       bc      BO_IF_NOT,CR0_GT,Lppcasm_div2   #or if (h > (1<<r8))
>          $UDIV   r3,r3,r0                #if not assert(0) divide by 0!
>                                          #that's how we signal overflow
>          bclr    BO_ALWAYS,CR0_LT        #return. NEVER REACHED.
> 

You don't think I have gone in and fix that before realizing it's
worse than that?  I am sure you didn't think I spend 3 days out in the
beach and somehow come up with an idea of clobbering some useful
routine because I think my routine is better?

In summary, what I am trying to provide the community is an
alternative to do something, the current implementation of which is
very questionable.  You might resist change which is understandable. 
But I were a diligent maintainer and I realize something is broken in
my code, then I will put the time to investigate the problem.  If I
don't have the time, I will delagate it to a friend.  If I don't have
a friend with that expertise then, I will try to make friends with the
reporter of the bug since he will most likely have spent hours fixing
the problem.

Regards,
David Ho.

[-- Attachment #2: test_bn.txt --]
[-- Type: text/plain, Size: 3397 bytes --]

bash-2.05b# make test_bn
starting big number library test, could take a while...
test BN_add
test BN_sub
test BN_lshift1
test BN_lshift (fixed)
test BN_lshift
test BN_rshift1
test BN_rshift
test BN_sqr
test BN_mul
test BN_div
test BN_div_recp
test BN_mod
test BN_mod_mul
test BN_mont
test BN_mod_exp
test BN_exp
test BN_kronecker
...++++++
....................................................................................................
test BN_mod_sqrt
.....
.....
.....
.....
.....
.....
.....
.....
.......++++++++++++
.....
......++++++++++++
.....
...++++++++++++
.....
..++++++++++++
.....
...++++++++++++
.....
........++++++++++++
.....
.................++++++++++++
.....
...........++++++++++++
.....
running bc

verify BN_add....................................................................................................
verify BN_sub......................................................................................................................................................
verify BN_lshift1....................................................................................................
verify BN_lshift (fixed)....................................................................................................
verify BN_lshift....................................................................................................
verify BN_rshift1....................................................................................................
verify BN_rshift....................................................................................................
verify BN_sqr....................................................................................................
verify BN_mul......................................................................................................................................................
verify BN_div............................................................................................................................................................................................................................................................................................................
verify BN_div_recp............................................................................................................................................................................................................................................................................................................
verify BN_mod....................................................................................................
verify BN_mod_mul............................................................................................................................................................................................................................................................................................................
verify BN_mont.....
verify BN_mod_exp.....
verify BN_exp.....
verify BN_kronecker
verify BN_mod_sqrt
2015 tests passed
test a^b%c implementations
../util/shlib_wrap.sh ./exptest
........................................................................................................................................................................................................ done