home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / BNLIB / LBN960JX.S < prev    next >
Text File  |  1996-05-16  |  9KB  |  251 lines
  1. # Assembly-language bignum primitives for the i960 Jx series.
  2. #
  3. # The Jx series is fairly straightforward single-instruction-issue 
  4. # implementation, with a 1-cycle-issue 4-cycle-latency non-pipelined
  5. # multiplier that we can use.  Note also that loads which hit in the
  6. # cache have 2 cycles of latency and stores stall until all pending
  7. # loads are done.
  8. #
  9. # What is intensely annoying about the i960 is that it uses the same
  10. # flags for all conditional branches (even compare-and-branch sets the
  11. # flags) AND for the carry bit.  Further, it is hard to manipulate
  12. # that bit.
  13. #
  14. # Calling conventions:
  15. # The r registers are all local, if you set them up.  There's an alternative
  16. # calling convention that uses bal (branch and link) and doesn't set them up.
  17. # Currently, all of these functions are designed to work that way.
  18. # g0-g7 are argument registers and volatile across calls.  return in g0-g3.
  19. # g8-g11 are extra argument registers, and volatile if used, but
  20. #    preserved if not.  Here, they are not.
  21. # g12 is used for PIC, and is preserved.
  22. # g13 is a pointer to a structure return value, if used, and is volatile.
  23. # g14 is magic, and is used as a return address in the branch-and-link
  24. #    convention, and as a pointer to an argument block if the arguments
  25. #    won't fit in registers, but is usually hardwired 0 and must be
  26. #    returned set to zero (0).
  27. # g15 is the frame pointer, and shouldn't be messed with.
  28. # The AC (condition codes) are all volatile.
  29. # The fp registers are all volatile, but irrelevant.
  30. #
  31.  
  32. # BNWORD32
  33. # lbnMultAdd1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
  34. # This adds "k" * "in" to "len" words of "out" and returns the word of
  35. # carry.
  36. #
  37. # For doing multiply-add, the 960 is a bit annoying because it uses
  38. # the same status bits for the carry flag and for the loop indexing
  39. # computation, and doesn't have an "add with carry out but not carry in"
  40. # instruction.  Fortunately, we can arrange to have the loop indexing
  41. # leave the carry bit clear most of the time.
  42. #
  43. # The basic sequence of the loop is:
  44. # 1. Multiply k * *in++ -> high, low
  45. # 2. Addc carry word and carry bit to low
  46. # 3. Addc carry bit to high, producing carry word (note: cannot generate carry!)
  47. # 4. Addc low to *out++
  48. #
  49. # Note that the carry bit set in step 4 is used in step 2.  The only place
  50. # in this loop that the carry flag isn't in use is between steps 3 and 4,
  51. # so we have to rotate the loop to place the loop indexing operations here.
  52. # (Which consist of a compare-and-decrement and a conditional branch.)
  53. # The loop above ignores the details of when to do loads and stores, which
  54. # have some flexibility, but must be carefully scheduled to avoid stalls.
  55. #
  56. # The first iteration has no carry word in, so it requires only steps 1 and 4,
  57. # and since we begin the loop with step 4, it boils down to just step 1
  58. # followed by the loop indexing (which clears the carry bit in preparation
  59. # for step 4).
  60. #
  61. # Arguments are passed as follows:
  62. # g0 - out pointer
  63. # g1 - in pointer
  64. # g2 - length
  65. # g3 - k
  66. # The other registers are used as follows.
  67. # g4 - low word of product
  68. # g5 - high word of product
  69. # g6 - current word of "out"
  70. # g7 - carry word
  71. # g13 - current word of "in"
  72.  
  73.     .globl _lbnMulAdd1_32
  74. _lbnMulAdd1_32:
  75.     ld    (g1),g13       # Fetch *in
  76.     addo    g1,4,g1       # Increment in
  77.     emul    g13,g3,g4    # Do multiply (step 1)
  78.     ld    (g0),g6       # Fetch *out
  79.     chkbit    0,g2        # Check if loop counter was odd
  80.     shro    1,g2,g2       # Divide loop counter by 2
  81.     mov    g5,g7        # Move high word to carry
  82.     bno    ma_loop1    # If even, jump to ma_loop1
  83.     cmpo    0,g2        # If odd, was it 1 (now 0)?
  84.     be    ma_done       # If equal (carry set), jump to ending code
  85.  
  86. # Entered with carry bit clear
  87. ma_loop:
  88.     ld    (g1),g13      # Fetch *in
  89.     addc    g4,g6,g6    # Add low to *out (step 4), generate carry
  90.     emul    g13,g3,g4    # Do multiply (step 1)
  91.     st    g6,(g0)      # Write out *out
  92.     addo    g0,4,g0      # Increment out
  93.     addo    g1,4,g1      # Increment in
  94.     ld    (g0),g6      # Fetch next *out
  95.     addc    g7,g4,g4    # Add carries to low (step 2)
  96.     addc    g5,0,g7      # Add carry bit to high (step 3) & clear carry
  97. ma_loop1:
  98.     ld    (g1),g13      # Fetch *in
  99.     addc    g4,g6,g6    # Add low to *out (step 4), generate carry
  100.     emul    g13,g3,g4    # Do multiply (step 1)
  101.     st    g6,(g0)      # Write out *out
  102.     addo    g0,4,g0      # Increment out
  103.     addo    g1,4,g1      # Increment in
  104.     ld    (g0),g6      # Fetch next *out
  105.     addc    g7,g4,g4    # Add carries to low (step 2)
  106.     addc    g5,0,g7      # Add carry bit to high (step 3) & clear carry
  107.  
  108.     cmpdeco    1,g2,g2
  109.     bne    ma_loop
  110. # When we come here, carry is *set*, and we stil have to do step 4
  111. ma_done:
  112.     cmpi    0,1        # Clear carry (equal flag)
  113.     addc    g4,g6,g6    # Add low to *out (step 4), generate carry
  114.     st    g6,(g0)       # Write out *out
  115.     addc    g7,0,g0       # Add carry bit and word to produce return value
  116.     ret
  117.  
  118. # Now, multiply N by 1 is similarly annoying.  We only have one add in the
  119. # whole loop, which should just be able to leave its carry output in the
  120. # carry flag for the next iteration, but we need the condition codes to do
  121. # loop testing.  *Sigh*.
  122. #
  123. # void
  124. # lbnMultN1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
  125. # This stores len+1 words of "k" * len words of "in" and stores the result
  126. # in "out".
  127. #
  128. # To avoid having to do a move after the first iteration, for the first
  129. # step, g4/g5 is the product.  For second step, g6/g7 is used for product
  130. # storage and g5 is the carry in.  It alternates from then on.
  131.     .globl _lbnMulN1_32
  132. _lbnMulN1_32:
  133.     ld    (g1),g13     # Fetch *in
  134.     addo    g1,4,g1     # Increment in
  135.     emul    g13,g3,g4    # Do multiply (step 1)
  136.     chkbit    0,g2        # Check if loop counter was odd
  137.     shro    1,g2,g2      # Divide loop counter by 2
  138.     bno    m_loop1      # If even, jump to ma_loop1
  139.     mov    g4,g6
  140.     cmpo    0,g2        # If counter was odd, was it 1 (now 0)?
  141.     mov    g5,g7
  142.     be    m_done        # If equal (carry set), jump to ending code
  143.  
  144. # Entered with carry bit clear
  145. m_loop:
  146.     # Result in g6, carry word in g7
  147.     ld    (g1),g13    # Fetch *in
  148.     addo    g1,4,g1     # Increment in
  149.     emul    g13,g3,g4    # Do multiply (step 1)
  150.     st    g6,(g0)     # Write out *out
  151.     addo    g0,4,g0        # Increment out
  152.     addc    g7,g4,g4    # Add carries to low (step 2)
  153. # No need to add carry bit here, because it'll get remembered until next addc.
  154. #    addc    g5,0,g5     # Add carry bit to high (step 3)
  155. m_loop1:
  156.     # Carry word in g5
  157.     ld    (g1),g13    # Fetch *in
  158.     addo    g1,4,g1        # Increment in
  159.     emul    g13,g3,g6    # Do multiply (step 1)
  160.     st    g4,(g0)        # Write out *out
  161.     addo    g0,4,g0     # Increment out
  162.     addc    g5,g6,g6    # Add carries to low (step 2)
  163.     addc    g7,0,g7     # Add carry bit to high (step 3)
  164.  
  165.     cmpdeco    1,g2,g2
  166.     bne    m_loop
  167.  
  168. # When we come here, we have to store g6 and the carry word in g7.
  169. m_done:
  170.     st    g6,(g0)     # Write out *out
  171.     st    g7,4(g0)    # Write out *out
  172.     ret
  173.  
  174. # BNWORD32
  175. # lbnMultSub1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
  176. # This subtracts "k" * "in" from "len" words of "out" and returns the word of
  177. # borrow.
  178. #
  179. # This is similar to multiply-add, but actually a bit more obnoxious,
  180. # because of the carry situation.  The 960 uses a carry (rather than a borrow)
  181. # bit on subtracts, so the carry bit should be 1 for a subc to do the
  182. # same thing as an ordinary subo.  So we use two carry chains: one from
  183. # the add of the low-order words to the high-order carry word, and a second,
  184. # which uses an extra register, to connect the subtracts.  This avoids
  185. # the need to fiddle with inverting the bit in the usual case.
  186. #
  187. # Arguments are passed as follows:
  188. # g0 - out pointer
  189. # g1 - in pointer
  190. # g2 - length
  191. # g3 - k
  192. # The other registers are used as follows.
  193. # g4 - low word of product
  194. # g5 - high word of product
  195. # g6 - current word of "out"
  196. # g7 - carry word
  197. # g13 - current word of "in"
  198. # g14 - remembered carry bit
  199.  
  200.     .globl _lbnMulSub1_32
  201. _lbnMulSub1_32:
  202.     ld    (g1),g13    # Fetch *in
  203.     addo    g1,4,g1     # Increment in
  204.     emul    g13,g3,g4    # Do multiply (step 1)
  205.     ld    (g0),g6     # Fetch *out
  206.     chkbit    0,g2        # Check if loop counter was odd
  207.     mov    1,g14       # Set remembered carry for first iteration
  208.     shro    1,g2,g2     # Divide loop counter by 2
  209.     mov    g5,g7       # Move high word to carry
  210.     bno    ms_loop1    # If even, jump to ma_loop1
  211.     cmpo    0,g2        # If odd, was it 1 (now 0)?
  212.     be    ms_done     # If equal (carry set), jump to ending code
  213.  
  214. # Entered with carry bit clear
  215. ms_loop:
  216.     ld    (g1),g13    # Fetch *in
  217.     cmpi    g14,1       # Set carry flag
  218.     subc    g4,g6,g6    # Subtract low from *out (step 4), gen. carry
  219.     emul    g13,g3,g4    # Do multiply (step 1)
  220.     addc    0,0,g14     # g14 = carry, then clear carry
  221.     st    g6,(g0)     # Write out *out
  222.     addo    g0,4,g0     # Increment out
  223.     addo    g1,4,g1     # Increment in
  224.     ld    (g0),g6     # Fetch next *out
  225.     addc    g7,g4,g4    # Add carries to low (step 2)
  226.     addc    g5,0,g7     # Add carry bit to high (step 3)
  227. ms_loop1:
  228.     ld    (g1),g13    # Fetch *in
  229.     cmpi    g14,1       # Set carry flag for subtrsct
  230.     subc    g4,g6,g6    # Subtract low from *out (step 4), gen. carry
  231.     emul    g13,g3,g4    # Do multiply (step 1)
  232.     addc    0,0,g14     # g14 = carry, then clear carry
  233.     st    g6,(g0)     # Write out *out
  234.     addo    g0,4,g0     # Increment out
  235.     addo    g1,4,g1     # Increment in
  236.     ld    (g0),g6     # Fetch next *out
  237.     addc    g7,g4,g4    # Add carries to low (step 2)
  238.     addc    g5,0,g7     # Add carry bit to high (step 3)
  239.  
  240.     cmpdeco    1,g2,g2
  241.     bne    ms_loop
  242. # When we come here, carry is *set*, and we stil have to do step 4
  243. ms_done:
  244.     cmpi    g14,1       # set carry (equal flag)
  245.     subc    g4,g6,g6    # Add low to *out (step 4), generate carry
  246.     st    g6,(g0)     # Write out *out
  247.     subc    0,0,g14     # g14 = -1 if no carry (borrow), 0 if carry
  248.     subo    g14,g7,g0    # Add borrow bit to produce return value
  249.     mov    0,g14       # Restore g14 to 0 for return
  250.     ret
  251.