Re: PPC bn_div_words routine rewrite

[David Ho <davidkwho@gmail.com>]

I can tell you with certainty, with reference to the function
BN_bn2dec, that since lp is a pointer, and within the while loop
around bn_print.c:136 lp is being incremented.  Because the test
BN_is_zero(t) is always false, you have a pointer that is going off
into the stratosphere, hence the segfault on ppc8xx.

More analysis to come.

On 7/5/05, David Ho <davidkwho@gmail.com> wrote:
> First pass debugging results from gdb on ppc8xx.  Executing ssh-keygen
> with following arguments.
>=20
> (gdb) show args
> Argument list to give program being debugged when it is started is
>     "-t rsa1 -f /etc/ssh/ssh_host_key -N """.
>=20
> Program received signal SIGSEGV, Segmentation fault.
> BN_bn2dec (a=3D0x1002d9f0) at bn_print.c:136
> 136                             *lp=3DBN_div_word(t,BN_DEC_CONV);
>=20
> (gdb) i r
> r0             0x0      0
> r1             0x7fffd580       2147472768
> r2             0x30012868       805382248
> r3             0x80000000       2147483648
> r4             0xfef33fc        267334652
> r5             0x25     37
> r6             0xfccdef8        265084664
> r7             0x7fffd4c0       2147472576
> r8             0xfbad2887       4222429319
> r9             0x84044022       2214871074
> r10            0x0      0
> r11            0x2      2
> r12            0xfef2054        267329620
> r13            0x10030bc8       268635080
> r14            0x0      0
> r15            0x0      0
> r16            0x0      0
> r17            0x0      0
> r18            0x0      0
> r19            0x0      0
> r20            0x0      0
> r21            0x0      0
> r22            0x0      0
> r23            0x64     100
> r24            0x5      5
> r25            0x1002d438       268620856
> r26            0x1002d9f0       268622320
> r27            0x1002c578       268617080
> r28            0x1      1
> r29            0x10031000       268636160
> r30            0xffbf7d0        268171216
> r31            0x1002d9f0       268622320
> pc             0xfef2058        267329624
> ps             0xd032   53298
> cr             0x24044022       604258338
> lr             0xfef2054        267329620
> ctr            0xfccefa0        265088928
> xer            0x20000000       536870912
> fpscr          0x0      0
> vscr           0x0      0
> vrsave         0x0      0
>=20
> (gdb) p/x $pc
> $1 =3D 0xfef2058
>=20
> 0x0fef2058 <BN_bn2dec+472>:     stw     r3,0(r29)
>=20
> (gdb) x 0x10031000
> 0x10031000:     Cannot access memory at address 0x10031000
>=20
>=20
>=20
>=20
>=20
>=20
>=20
>=20
>=20
>=20
> On 7/5/05, David Ho <davidkwho@gmail.com> wrote:
> > This is the second confirmed report of the same problem on the ppc8xx.
> >
> > After reading my email.  I must say I was the unfriendly one, I
> > apologize for that.
> >
> > More debugging evidence to come.
> >
> > ---------- Forwarded message ----------
> > From: Murch, Christopher <cmurch@mrv.com>
> > Date: Jul 1, 2005 9:46 AM
> > Subject: RE: PPC bn_div_words routine rewrite
> > To: David Ho <davidkwho@gmail.com>
> >
> >
> > David,
> > I had observed the same issue on ppc 8xx machines after upgrading to th=
e asm
> > version of the BN routines.  Thank you very much for your work for the =
fix.
> > My question is, do you have high confidence in the other new asm ppc BN
> > routines after observing this issue or do you think they might have sim=
iliar
> > problems?
> > Thanks.
> > Chris
> >
> > -----Original Message-----
> > From: David Ho [mailto:davidkwho@gmail.com]
> > Sent: Thursday, June 30, 2005 6:22 PM
> > To: openssl-dev@openssl.org; linuxppc-embedded@ozlabs.org
> > Subject: Re: PPC bn_div_words routine rewrite
> >
> >
> > The reason I had to redo this routine, in case anyone is wondering, is
> > because ssh-keygen  segfaults when this assembly routine returns junk
> > to the BN_div_word function. On a ppc, if you issue the command
> >
> > ssh-keygen -t rsa1 -f /etc/ssh/ssh_host_key -N ""
> >
> > The program craps out when it tries to write the public key in ascii
> > decimal.
> >
> > Regards,
> > David
> >
> > On 6/30/05, David Ho <davidkwho@gmail.com> wrote:
> > > Hi all,
> > >
> > > This is a rewrite of the bn_div_words routine for the PowerPC arch,
> > > tested on a MPC8xx processor.
> > > I initially thought there is maybe a small mistake in the code that
> > > requires a one-liner change but it turns out I have to redo the
> > > routine.
> > > I guess this routine is not called very often as I see that most othe=
r
> > > routines are hand-crafted, whereas this routine is compiled from a C
> > > function that apparently has not gone through a whole lot of testing.
> > >
> > > I wrote a C function to confirm correctness of the code.
> > >
> > > unsigned long div_words (unsigned long h,
> > >                          unsigned long l,
> > >                          unsigned long d)
> > > {
> > >   unsigned long i_h; /* intermediate dividend */
> > >   unsigned long i_q; /* quotient of i_h/d */
> > >   unsigned long i_r; /* remainder of i_h/d */
> > >
> > >   unsigned long i_cntr;
> > >   unsigned long i_carry;
> > >
> > >   unsigned long ret_q; /* return quotient */
> > >
> > >   /* cannot divide by zero */
> > >   if (d =3D=3D 0) return 0xffffffff;
> > >
> > >   /* do simple 32-bit divide */
> > >   if (h =3D=3D 0) return l/d;
> > >
> > >   i_q =3D h/d;
> > >   i_r =3D h - (i_q*d);
> > >   ret_q =3D i_q;
> > >
> > >   i_cntr =3D 32;
> > >
> > >   while (i_cntr--)
> > >   {
> > >     i_carry =3D (l & 0x80000000) ? 1:0;
> > >     l =3D l << 1;
> > >
> > >     i_h =3D (i_r << 1) | i_carry;
> > >     i_q =3D i_h/d;
> > >     i_r =3D i_h - (i_q*d);
> > >
> > >     ret_q =3D (ret_q << 1) | i_q;
> > >   }
> > >
> > >   return ret_q;
> > > }
> > >
> > >
> > > Then I handcrafted the routine in PPC assembly.
> > > The result is a 26 line assembly that is easy to understand and
> > > predictable as opposed to a 81liner that I am still trying to
> > > decipher...
> > > If anyone is interested in incorporating this routine to the openssl
> > > code I'll be happy to assist.
> > > At this point I think I will be taking a bit of a break from this 3
> > > day debugging/fixing marathon.
> > >
> > > Regards,
> > > David Ho
> > >
> > >
> > > #
> > > #       Handcrafted version of bn_div_words
> > > #
> > > #       r3 =3D h
> > > #       r4 =3D l
> > > #       r5 =3D d
> > >
> > >         cmplwi  0,r5,0                  # compare r5 and 0
> > >         bc      BO_IF_NOT,CR0_EQ,.Lppcasm_div1  # proceed if d!=3D0
> > >         li      r3,-1                   # d=3D0 return -1
> > >         bclr    BO_ALWAYS,CR0_LT
> > > .Lppcasm_div1:
> > >         cmplwi  0,r3,0                  # compare r3 and 0
> > >         bc      BO_IF_NOT,CR0_EQ,.Lppcasm_div2  # proceed if h !=3D 0
> > >         divwu   r3,r4,r5                # ret_q =3D l/d
> > >         bclr    BO_ALWAYS,CR0_LT        # return result in r3
> > > .Lppcasm_div2:
> > >         divwu   r9,r3,r5                # i_q =3D h/d
> > >         mullw   r10,r9,r5               # i_r =3D h - (i_q*d)
> > >         subf    r10,r10,r3
> > >         mr      r3,r9                   # req_q =3D i_q
> > > .Lppcasm_set_ctr:
> > >         li      r12,32                  # ctr =3D bitsizeof(d)
> > >         mtctr   r12
> > > .Lppcasm_div_loop:
> > >         addc    r4,r4,r4                # l =3D l << 1 -> i_carry
> > >         adde    r11,r10,r10             # i_h =3D (i_r << 1) | i_carr=
y
> > >         divwu   r9,r11,r5               # i_q =3D i_h/d
> > >         mullw   r10,r9,r5               # i_r =3D i_h - (i_q*d)
> > >         subf    r10,r10,r11
> > >         add     r3,r3,r3                # ret_q =3D ret_q << 1 | i_q
> > >         add     r3,r3,r9
> > >         bc      BO_dCTR_NZERO,CR0_EQ,.Lppcasm_div_loop
> > > .Lppc_div_end:
> > >         bclr    BO_ALWAYS,CR0_LT        # return result in r3
> > >         .long   0x00000000
> > >
> > _______________________________________________
> > Linuxppc-embedded mailing list
> > Linuxppc-embedded@ozlabs.org
> > https://ozlabs.org/mailman/listinfo/linuxppc-embedded
> >
>