home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / BNLIB / LBNPPC.C < prev    next >
C/C++ Source or Header  |  1996-05-17  |  12KB  |  319 lines
  1. #include "lbnppc.h"
  2.  
  3. /*
  4.  * lbnppc.c - Assembly primitives for the bignum library, PowerPC version.
  5.  *
  6.  * Copyright (c) 1995  Colin Plumb.  All rights reserved.
  7.  * For licensing and other legal details, see the file legal.c
  8.  *
  9.  * Register usage during function calls is:
  10.  * r0 - volatile
  11.  * r1 - stack pointer, preserved
  12.  * r2 - TOC pointer, preserved
  13.  * r3 - First argument and return value register
  14.  * r4-r10 - More argument registers, volatile
  15.  * r11-r12 - Volatile
  16.  * r13-r31 - Preserved
  17.  * LR, CTR, XER and MQ are all volatile.
  18.  * LR holds return address on entry.
  19.  *
  20.  * On the PPC 601, unrolling the loops more doesn't seem to speed things
  21.  * up at all.  I'd be curious if other chips differed.
  22.  */
  23. #if __MWERKS__ < 0x800
  24.  
  25. #include "ppcasm.h"    /* PowerPC assembler */
  26.  
  27. /*
  28.  * MulN1 expects (*out, *in, len, k), count >= 1
  29.  *                r3    r4   r5   r6
  30.  */
  31. static const unsigned mulN1[] = {
  32.     PPC_LWZ(7,4,0),     /* Load first word of in in r7 */
  33.     PPC_MULLW(8,7,6),    /* Low half of multiply in r8 */
  34.     PPC_MTCTR(5),        /* Move len into CTR */
  35.     PPC_ADDIC(0,0,0),    /* Clear carry bit for loop */
  36.     PPC_MULHWU(5,7,6),    /* High half of multiply in r5 */
  37.     PPC_STW(8,3,0),
  38.     PPC_BC(18,31,7),    /* Branch to Label if --ctr == 0 */
  39. /* Loop: */
  40.     PPC_LWZU(7,4,4),    /* r7 = *++in */
  41.     PPC_MULLW(8,7,6),    /* r8 = low word of product */
  42.     PPC_ADDE(8,8,5),    /* Add carry word r5 and bit CF to r8 */
  43.     PPC_STWU(8,3,4),    /* *++out = r8 */
  44.     PPC_MULHWU(5,7,6),    /* r5 is high word of product, for carry word */
  45.     PPC_BC(16,31,-5),    /* Branch to Loop if --ctr != 0 */
  46. /* Label: */
  47.     PPC_ADDZE(5,5),        /* Add carry flag to r5 */
  48.     PPC_STW(5,3,4),        /* out[1] = r5 */
  49.     PPC_BLR()
  50. };
  51.  
  52. /*
  53.  * MulAdd1 expects (*out, *in, len, k), count >= 1
  54.  *                  r3    r4   r5   r6
  55.  */
  56. static unsigned const mulAdd1[] = {
  57.     PPC_LWZ(7,4,0),     /* Load first word of in in r7 */
  58.     PPC_LWZ(0,3,0),        /* Load first word of out into r0 */
  59.     PPC_MULLW(8,7,6),    /* Low half of multiply in r8 */
  60.     PPC_MTCTR(5),        /* Move len into CTR */
  61.     PPC_MULHWU(5,7,6),    /* High half of multiply in r5 */
  62.     PPC_ADDC(8,8,0),    /* r8 = r8 + r0 */
  63.     PPC_STW(8,3,0),        /* Store result to memory */
  64.     PPC_BC(18,31,10),    /* Branch to Label if --ctr == 0 */
  65. /* Loop: */
  66.     PPC_LWZU(7,4,4),    /* r7 = *++in */
  67.     PPC_LWZU(0,3,4),    /* r0 = *++out */
  68.     PPC_MULLW(8,7,6),    /* r8 = low word of product */
  69.     PPC_ADDE(8,8,5),     /* Add carry word r5 and carry bit CF to r8 */
  70.     PPC_MULHWU(5,7,6),    /* r5 is high word of product, for carry word */
  71.     PPC_ADDZE(5,5),        /* Add carry bit from low add to r5 */
  72.     PPC_ADDC(8,8,0),    /* r8 = r8 + r0 */
  73.     PPC_STW(8,3,0),     /* *out = r8 */
  74.     PPC_BC(16,31,-8),    /* Branch to Loop if --ctr != 0 */
  75. /* Label: */
  76.     PPC_ADDZE(3,5),        /* Add carry flag to r5 and move to r3 */
  77.     PPC_BLR()
  78. };
  79.  
  80. /*
  81.  * MulSub1 expects (*out, *in, len, k), count >= 1
  82.  *                  r3    r4   r5   r6
  83.  *
  84.  * Multiply and subtract is rather a pain.  If the subtract of the
  85.  * low word of the product from out[i] generates a borrow, we want to
  86.  * increment the carry word (initially in the range 0..0xfffffffe).
  87.  * However, the PPC's carry bit CF is *clear* after a subtract, so
  88.  * we want to add (1-CF) to the carry word.  This is done using two
  89.  * instructions:
  90.  *
  91.  * SUBFME, subtract from minus one extended.  This computes
  92.  *   rD = ~rS + 0xffffffff + CF.  Since rS is from 0 to 0xfffffffe,
  93.  *   ~rS is from 1 through 0xffffffff, and the sum with 0xffffffff+CF is
  94.  *   from 0 through 0xfffffffff, setting the carry flag unconditionally, and
  95.  * NOR, which is used as a bitwise invert NOT instruction.
  96.  *
  97.  * The SUBFME performs the computation rD = ~rS + 0xffffffff + CF,
  98.  * = (-rS - 1) + (CF - 1) = -(rS - CF + 1) - 1 = ~(rS + 1-CF),
  99.  * which is the bitwise complement of the value we want.
  100.  * We want to add the complement of that result to the low word of the
  101.  * product, which is just what a subtract would do, if only we could get
  102.  * the carry flag clear.  But it's always set, except for SUBFE, and the
  103.  * operation we just performed unconditionally *sets* the carry flag.  Ugh.
  104.  * So find the complement in a separate instruction.
  105.  */
  106. static unsigned const mulSub1[] = {
  107.     PPC_LWZ(7,4,0),     /* Load first word of in in r7 */
  108.     PPC_LWZ(0,3,0),        /* Load first word of out into r0 */
  109.     PPC_MTCTR(5),        /* Move len into CTR */
  110.     PPC_MULLW(8,7,6),    /* Low half of multiply in r8 */
  111.     PPC_MULHWU(5,7,6),    /* High half of multiply in r5 */
  112.     PPC_SUBFC(8,8,0),    /* r8 = r0 - r8, setting CF */
  113.     PPC_STW(8,3,0),        /* Store result to memory */
  114.     PPC_SUBFME(5,5),    /* First of two insns to add (1-CF) to r5 */
  115.     PPC_BC(18,31,12),    /* Branch to Label if --ctr == 0 */
  116. /* Loop: */
  117.     PPC_LWZU(7,4,4),    /* r7 = *++in */
  118.     PPC_LWZU(0,3,4),    /* r0 = *++out */
  119.     PPC_NOR(5,5,5),        /* Second of two insns to add (1-CF) to r5 */
  120.     PPC_MULLW(8,7,6),    /* r8 = low word of product */
  121.     PPC_ADDC(8,8,5),     /* Add carry word r5 to r8 */
  122.     PPC_MULHWU(5,7,6),    /* r5 is high word of product, for carry word */
  123.     PPC_ADDZE(5,5),        /* Add carry bit from low add to r5 */
  124.     PPC_SUBFC(8,8,0),    /* r8 = r0 - r8, setting CF */
  125.     PPC_STW(8,3,0),     /* *out = r8 */
  126.     PPC_SUBFME(5,5),    /* First of two insns to add (1-CF) to r5 */
  127.     PPC_BC(16,31,-10),    /* Branch to Loop if --ctr != 0 */
  128. /* Label: */
  129.     PPC_NOR(3,5,5),        /* Finish adding (1-CF) to r5, store in r3 */
  130.     PPC_BLR()
  131. };
  132.  
  133. #if 0
  134. /*
  135.  * Args: BNWORD32 *n, BNWORD32 const *mod, unsigned mlen, BNWORD32 inv)
  136.  *                r3                  r4            r5             r6
  137.  * r7, r8 and r9 are the triple-width accumulator.
  138.  * r0 and r10 are temporary registers.
  139.  * r11 and r12 are temporary pointers into n and mod, respectively. 
  140.  * r2 (!) is another temporary register.
  141.  */
  142. static unsigned const montReduce[] = {
  143.     PPC_MTCTR(5),    /* ??? */
  144.     PPC_LWZ(7,3,0),        /* Load low word of n into r7 */
  145.     PPC_LWZ(10,4,0),    /* Fetch low word of mod */
  146.     PPC_MULLW(0,7,6),    /* Invert r7 into r0 */
  147.     PPC_STW(0,3,0),        /* Store back for future use */
  148.     PPC_MULHWU(8,10,7),    /* Get high word of whatnot */
  149.     PPC_MULLW(10,10,7),    /* Get low word of it */
  150.     PPC_ADDC(7,7,10),    /* Add low word of product to r7 */
  151.     PPC_ADDZE(8,8),        /* Add carry to high word */
  152.     PPC_
  153.     
  154.  
  155.     PPC_MULHW(8,7,6),
  156.     PPC_ADDC(7,7,0),    /* Add inverse back to r7 */
  157.     PPC_ADDZE(8,8),
  158.     PPC_
  159.     
  160.     PPC_LWZU(
  161. /* Loop: */
  162.     PPC_LWZU(0,11,4),
  163.     PPC_LWZU(10,23,-4),
  164.     PPC_MULLW(2,0,10),
  165.     PPC_ADDC(7,7,2),
  166.     PPC_MULHWU(0,0,10),
  167.     PPC_ADDE(8,8,0),
  168.     PPC_ADDZE(9,9),
  169.     PPC_BC(16,31,-7),    /* Branch to Loop if --ctr != 0 */
  170.  
  171.     PPC_ADDIC_(count,-1),
  172.     PPC_LWZU(0,x,4),
  173.     PPC_ADDC(0,7,0),
  174.     PPC_STW(0,x,0),
  175.     PPC_ADDZE(7,8),
  176.     PPC_ADDZE(8,9),
  177.     PPC_LI(9,0),
  178.     PPC_BC(xx,2,yy),
  179.     
  180. };
  181. #endif
  182.  
  183. /*
  184.  * Three overlapped transition vectors for three functions.
  185.  * A PowerPC transition vector for a (potentially) inter-module
  186.  * jump or call consists of two words, an instruction address
  187.  * and a Table Of Contents (TOC) pointer, which is loaded into
  188.  * r1.  Since none of the routines here have global variables,
  189.  * they don't need a TOC pointer, so the value is unimportant.
  190.  * This array places an unintersting 32-bit value after each address.
  191.  */
  192. unsigned const * const lbnPPC_tv[] = {
  193.     mulN1,
  194.     mulAdd1,
  195.     mulSub1,
  196.     0
  197. };
  198.  
  199. #else /* __MWERKS >= 0x800 */
  200.  
  201. /*
  202.  * MulN1 expects (*out, *in, len, k), count >= 1
  203.  *                r3    r4   r5   r6
  204.  */
  205. asm void
  206. lbnMulN1_32(register unsigned *out, register unsigned const *in,
  207.     register unsigned len, register unsigned k)
  208. {
  209.     lwz     r7,0(in)     /* Load first word of in in r7 */
  210.     mtctr    len            /* Move len into CTR */
  211.     mullw    r8,r7,k        /* Low half of multiply in r8 */
  212.     addic    r0,r0,0        /* Clear carry bit for loop */
  213.     mulhwu    len,r7,k    /* High half of multiply in len */
  214.     stw     r8,0(out)    /* *out = r8 */
  215.     mulhwu    len,r7,k    /* len is high word of product, for carry */
  216.     bdz-    label        /* Branch to Label if --ctr == 0 */
  217. loop:
  218.     lwzu    r7,4(in)    /* r7 = *++in */
  219.     mullw    r8,r7,k        /* Low half of multiply in r8 */
  220.     adde    r8,r8,len    /* Add carry word len and bit CF to r8 */
  221.     stwu    r8,4(out)    /* *++out = r8 */
  222.     mulhwu    len,r7,k    /* len is high word of product, for carry */
  223.     bdnz+    loop        /* Branch to Loop if --ctr != 0 */
  224. label:
  225.     addze    len,len        /* Add carry flag to carry word */
  226.     stw     len,4(out)
  227.     blr
  228. }
  229.  
  230. /*
  231.  * MulAdd1 expects (*out, *in, len, k), count >= 1
  232.  *                  r3    r4   r5   r6
  233.  */
  234. asm unsigned
  235. lbnMulAdd1_32(register unsigned *out, register unsigned const *in,
  236.     register unsigned len, register unsigned k)
  237. {
  238.     lwz     r7,0(in)     /* Load first word of in in r7 */
  239.     lwz     r0,0(out)    /* Load first word of out into r0 */
  240.     mullw    r8,r7,k     /* Low half of multiply in r8 */
  241.     mtctr    len         /* Move len into CTR */
  242.     mulhwu    len,r7,k    /* High half of multiply in len */
  243.     addc    r8,r8,r0    /* r8 = r8 + r0 */
  244.     stw     r8,0(out)    /* Store result to memory */
  245.     bdz-    label        /* Branch to Label if --ctr == 0 */
  246. loop:
  247.     lwzu    r7,4(in)    /* r7 = *++in */
  248.     lwzu    r0,4(out)    /* r0 = *++out */
  249.     mullw    r8,r7,k        /* r8 = low word of product */
  250.     adde    r8,r8,len    /* Add carry word len and carry bit CF to r8 */
  251.     mulhwu    len,r7,k    /* len is high word of product, for carry */
  252.     addze    len,len        /* Add carry bit from low add to r5 */
  253.     addc    r8,r8,r0    /* r8 = r8 + r0 */
  254.     stw     r8,0(out)    /* *out = r8 */
  255.     bdnz+    loop        /* Branch to Loop if --ctr != 0 */
  256. label:
  257.     addze    r3,r5        /* Add carry flag to r5 and move to r3 */
  258.     blr
  259. }
  260.  
  261. /*
  262.  * MulSub1 expects (*out, *in, len, k), count >= 1
  263.  *                  r3    r4   r5   r6
  264.  *
  265.  * Multiply and subtract is rather a pain.  If the subtract of the
  266.  * low word of the product from out[i] generates a borrow, we want to
  267.  * increment the carry word (initially in the range 0..0xfffffffe).
  268.  * However, the PPC's carry bit CF is *clear* after a subtract, so
  269.  * we want to add (1-CF) to the carry word.  This is done using two
  270.  * instructions:
  271.  *
  272.  * SUBFME, subtract from minus one extended.  This computes
  273.  *   rD = ~rS + 0xffffffff + CF.  Since rS is from 0 to 0xfffffffe,
  274.  *   ~rS is from 1 through 0xffffffff, and the sum with 0xffffffff+CF is
  275.  *   from 0 through 0xfffffffff, setting the carry flag unconditionally, and
  276.  * NOR, which is used as a bitwise invert NOT instruction.
  277.  *
  278.  * The SUBFME performs the computation rD = ~rS + 0xffffffff + CF,
  279.  * = (-rS - 1) + (CF - 1) = -(rS - CF + 1) - 1 = ~(rS + 1-CF),
  280.  * which is the bitwise complement of the value we want.
  281.  * We want to add the complement of that result to the low word of the
  282.  * product, which is just what a subtract would do, if only we could get
  283.  * the carry flag clear.  But it's always set, except for SUBFE, and the
  284.  * operation we just performed unconditionally *sets* the carry flag.  Ugh.
  285.  * So find the complement in a separate instruction.
  286.  */
  287. asm unsigned
  288. lbnMulSub1_32(register unsigned *out, register unsigned const *in,
  289.     register unsigned len, register unsigned k)
  290. {
  291.     lwz     r7,0(in)     /* Load first word of in in r7 */
  292.     lwz     r0,0(out)    /* Load first word of out into r0 */
  293.     mtctr    len         /* Move len into CTR */
  294.     mullw    r8,r7,k     /* Low half of multiply in r8 */
  295.     mulhwu    len,r7,k    /* High half of multiply in len */
  296.     subfc    r8,r8,r0    /* r8 = r0 - r8, setting CF */
  297.     stw     r8,0(out)    /* Store result to memory */
  298.     subfme    len,len        /* First of two insns to add (1-CF) to len */
  299.     bdz-    label        /* Branch to Label if --ctr == 0 */
  300. loop:
  301.     lwzu    r7,4(in)    /* r7 = *++in */
  302.     lwzu    r0,4(out)    /* r0 = *++out */
  303.     nor     len,len,len    /* Second of two insns to add (1-CF) to len */
  304.     mullw    r8,r7,k        /* r8 = low word of product */
  305.     addc    r8,r8,len    /* Add carry word len to r8 */
  306.     mulhwu    len,r7,k    /* len is high word of product, for carry */
  307.     addze    len,len        /* Add carry bit from low add to len */
  308.     subfc    r8,r8,r0    /* r8 = r0 - r8 */
  309.     stw     r8,0(out)    /* *out = r8 */
  310.     subfme    len,len        /* First of two insns to add (1-CF) to len */
  311.     bdnz+    loop        /* Branch to Loop if --ctr != 0 */
  312. label:
  313.     nor     r3,r5,r5    /* Finish adding (1-CF) to len, store in r3 */
  314.     blr
  315. }
  316.  
  317. #endif /* __MWERKS >= 0x800 */
  318. /* 45678901234567890123456789012345678901234567890123456789012345678901234567 */
  319.