home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / BNLIB / LBN80386.S < prev    next >
Text File  |  1996-05-16  |  9KB  |  395 lines
  1.  
  2. ### Assembly primitives for bignum library, 80386 family, 32-bit code.
  3. ###
  4. ### Copyright (c) 1995, Colin Plumb.
  5. ### For licensing and other legal details, see the file legal.c.
  6. ###
  7. ### Several primitives are included here.  Only lbnMulAdd1 is *really*
  8. ### critical, but once that's written, lnmMulN1 and lbnMulSub1 are quite
  9. ### easy to write as well, so they are included here as well.
  10. ### lbnDiv21 and lbnModQ are so easy to write that they're included, too.
  11. ###
  12. ### All functions here are for 32-bit flat mode.  I.e. near code and
  13. ### near data, although the near offsets are 32 bits.
  14. ### Preserved registers are esp, ebp, esi, edi and ebx.  That last
  15. ### is needed by ELF for PIC, and differs from the IBM PC calling
  16. ### convention.
  17.  
  18. align4=4    # could be 2
  19. align8=8    # could be 3
  20. align16=16    # cound be 4
  21.  
  22.  
  23. .text
  24.  
  25. # We declare each symbol with two names, to deal with ELF/a.out variances.
  26.     .globl    lbnMulN1_32
  27.     .globl    _lbnMulN1_32
  28.     .globl    lbnMulAdd1_32
  29.     .globl    _lbnMulAdd1_32
  30.     .globl    lbnMulSub1_32
  31.     .globl    _lbnMulSub1_32
  32.     .globl    lbnDiv21_32
  33.     .globl    _lbnDiv21_32
  34.     .globl    lbnModQ_32
  35.     .globl    _lbnModQ_32
  36.  
  37. ## Register usage:
  38. ## %eax - low half of product
  39. ## %ebx - carry to next iteration
  40. ## %ecx - multiplier (k)
  41. ## %edx - high half of product
  42. ## %esi - source pointer
  43. ## %edi - dest pointer
  44. ## %ebp - loop counter
  45. ##
  46. ## Stack frame:
  47. ## +--------+ %esp+20  %esp+24  %esp+28  %esp+32  %esp+36
  48. ## |    k   |
  49. ## +--------+ %esp+16  %esp+20  %esp+24  %esp+28  %esp+32
  50. ## |   len  |
  51. ## +--------+ %esp+12  %esp+16  %esp+20  %esp+24  %esp+28
  52. ## |   in   |
  53. ## +--------+ %esp+8   %esp+12  %esp+16  %esp+20  %esp+24
  54. ## |   out  |
  55. ## +--------+ %esp+4   %esp+8   %esp+12  %esp+16  %esp+20
  56. ## | return |
  57. ## +--------+ %esp     %esp+4   %esp+8   %esp+12  %esp+16
  58. ## |  %esi  |
  59. ## +--------+          %esp     %esp+4   %esp+8   %esp+12
  60. ## |  %ebp  |
  61. ## +--------+                   %esp     %esp+4   %esp+8
  62. ## |  %ebx  |
  63. ## +--------+                            %esp     %esp+4
  64. ## |  %edi  |
  65. ## +--------+                                     %esp
  66.  
  67.     .align    align16
  68. lbnMulN1_32:
  69. _lbnMulN1_32:
  70.     pushl    %esi        # U
  71.     movl    12(%esp),%esi    # V    load in
  72.     pushl    %ebp        # U
  73.     movl    20(%esp),%ebp    # V    load len
  74.     pushl    %ebx        # U
  75.     movl    28(%esp),%ecx    # V    load k
  76.     pushl    %edi        # U
  77.     movl    20(%esp),%edi    # V    load out
  78.  
  79. ## First multiply step has no carry in.
  80.     movl    (%esi),%eax        # V
  81.     leal    -4(,%ebp,4),%ebx    # U    loop unrolling
  82.     mull    %ecx            # NP    first multiply
  83.     movl    %eax,(%edi)        # U
  84.     andl    $12,%ebx        # V    loop unrolling
  85.  
  86.     addl    %ebx,%esi        # U    loop unrolling
  87.     addl    %ebx,%edi        # V    loop unrolling
  88.  
  89.     jmp    *m32_jumptable(%ebx)    # NP    loop unrolling
  90.  
  91.     .align    align4
  92. m32_jumptable:
  93.     .long    m32_case0
  94.     .long    m32_case1
  95.     .long    m32_case2
  96.     .long    m32_case3
  97.  
  98.     nop
  99.     .align    align8
  100.     nop
  101.     nop
  102.     nop    # Get loop nicely aligned
  103.  
  104. m32_case0:
  105.     subl    $4,%ebp        # U
  106.     jbe    m32_done    # V
  107.  
  108. m32_loop:
  109.     movl    4(%esi),%eax    # U
  110.     movl    %edx,%ebx    # V    Remember carry for later
  111.     addl    $16,%esi    # U
  112.     addl    $16,%edi    # V
  113.     mull    %ecx        # NP
  114.     addl    %ebx,%eax    # U    Add carry in from previous word
  115.     adcl    $0,%edx        # U
  116.     movl    %eax,-12(%edi)    # V
  117. m32_case3:
  118.     movl    -8(%esi),%eax    # U
  119.     movl    %edx,%ebx    # V    Remember carry for later
  120.     mull    %ecx        # NP
  121.     addl    %ebx,%eax    # U    Add carry in from previous word
  122.     adcl    $0,%edx        # U
  123.     movl    %eax,-8(%edi)    # V
  124. m32_case2:
  125.     movl    -4(%esi),%eax    # U
  126.     movl    %edx,%ebx    # V    Remember carry for later
  127.     mull    %ecx        # NP
  128.     addl    %ebx,%eax    # U    Add carry in from previous word
  129.     adcl    $0,%edx        # U
  130.     movl    %eax,-4(%edi)    # V
  131. m32_case1:
  132.     movl    (%esi),%eax    # U
  133.     movl    %edx,%ebx    # V    Remember carry for later
  134.     mull    %ecx        # NP
  135.     addl    %ebx,%eax    # U    Add carry in from previous word
  136.     adcl    $0,%edx        # U
  137.     movl    %eax,(%edi)    # V
  138.  
  139.     subl    $4,%ebp        # U
  140.     ja    m32_loop    # V
  141.  
  142. m32_done:
  143.     movl    %edx,4(%edi)    # U
  144.     popl    %edi        # V
  145.     popl    %ebx        # U
  146.     popl    %ebp        # V
  147.     popl    %esi        # U
  148.     ret            # NP
  149.  
  150.  
  151.     .align    align16
  152. lbnMulAdd1_32:
  153. _lbnMulAdd1_32:
  154.  
  155.     pushl    %esi        # U
  156.     movl    12(%esp),%esi    # V    load in
  157.     pushl    %edi        # U
  158.     movl    12(%esp),%edi    # V    load out
  159.     pushl    %ebp        # U
  160.     movl    24(%esp),%ebp    # V    load len
  161.     pushl    %ebx        # U
  162.     movl    32(%esp),%ecx    # V    load k
  163.  
  164. ## First multiply step has no carry in.
  165.     movl    (%esi),%eax        # V
  166.     movl    (%edi),%ebx        # U
  167.     mull    %ecx            # NP    first multiply
  168.     addl    %eax,%ebx        # U
  169.     leal    -4(,%ebp,4),%eax    # V    loop unrolling
  170.     adcl    $0,%edx            # U
  171.     andl    $12,%eax        # V    loop unrolling
  172.     movl    %ebx,(%edi)        # U
  173.  
  174.     addl    %eax,%esi        # V    loop unrolling
  175.     addl    %eax,%edi        # U    loop unrolling
  176.  
  177.     jmp    *ma32_jumptable(%eax)    # NP    loop unrolling
  178.  
  179.     .align    align4
  180. ma32_jumptable:
  181.     .long    ma32_case0
  182.     .long    ma32_case1
  183.     .long    ma32_case2
  184.     .long    ma32_case3
  185.  
  186.     .align    align8
  187.     nop
  188.     nop
  189.     nop            # To align loop properly
  190.  
  191.  
  192. ma32_case0:
  193.     subl    $4,%ebp        # U
  194.     jbe    ma32_done    # V
  195.  
  196. ma32_loop:
  197.     movl    4(%esi),%eax    # U
  198.     movl    %edx,%ebx    # V    Remember carry for later
  199.     addl    $16,%esi    # U
  200.     addl    $16,%edi    # V
  201.     mull    %ecx        # NP
  202.     addl    %ebx,%eax    # U    Add carry in from previous word
  203.     movl    -12(%edi),%ebx    # V
  204.     adcl    $0,%edx        # U
  205.     addl    %eax,%ebx    # V
  206.     adcl    $0,%edx        # U
  207.     movl    %ebx,-12(%edi)    # V
  208. ma32_case3:
  209.     movl    -8(%esi),%eax    # U
  210.     movl    %edx,%ebx    # V    Remember carry for later
  211.     mull    %ecx        # NP
  212.     addl    %ebx,%eax    # U    Add carry in from previous word
  213.     movl    -8(%edi),%ebx    # V
  214.     adcl    $0,%edx        # U
  215.     addl    %eax,%ebx    # V
  216.     adcl    $0,%edx        # U
  217.     movl    %ebx,-8(%edi)    # V
  218. ma32_case2:
  219.     movl    -4(%esi),%eax    # U
  220.     movl    %edx,%ebx    # V    Remember carry for later
  221.     mull    %ecx        # NP
  222.     addl    %ebx,%eax    # U    Add carry in from previous word
  223.     movl    -4(%edi),%ebx    # V
  224.     adcl    $0,%edx        # U
  225.     addl    %eax,%ebx    # V
  226.     adcl    $0,%edx        # U
  227.     movl    %ebx,-4(%edi)    # V
  228. ma32_case1:
  229.     movl    (%esi),%eax    # U
  230.     movl    %edx,%ebx    # V    Remember carry for later
  231.     mull    %ecx        # NP
  232.     addl    %ebx,%eax    # U    Add carry in from previous word
  233.     movl    (%edi),%ebx    # V
  234.     adcl    $0,%edx        # U
  235.     addl    %eax,%ebx    # V
  236.     adcl    $0,%edx        # U
  237.     movl    %ebx,(%edi)    # V
  238.  
  239.     subl    $4,%ebp        # U
  240.     ja    ma32_loop    # V
  241.  
  242. ma32_done:
  243.     popl    %ebx        # U
  244.     popl    %ebp        # V
  245.     movl    %edx,%eax    # U
  246.     popl    %edi        # V
  247.     popl    %esi        # U
  248.     ret            # NP
  249.  
  250.  
  251.     .align    align16
  252. lbnMulSub1_32:
  253. _lbnMulSub1_32:
  254.     pushl    %esi        # U
  255.     movl    12(%esp),%esi    # V    load in
  256.     pushl    %edi        # U
  257.     movl    12(%esp),%edi    # V    load out
  258.     pushl    %ebp        # U
  259.     movl    24(%esp),%ebp    # V    load len
  260.     pushl    %ebx        # U
  261.     movl    32(%esp),%ecx    # V    load k
  262.  
  263. /* First multiply step has no carry in. */
  264.     movl    (%esi),%eax        # V
  265.     movl    (%edi),%ebx        # U
  266.     mull    %ecx            # NP    first multiply
  267.     subl    %eax,%ebx        # U
  268.     leal    -4(,%ebp,4),%eax    # V    loop unrolling
  269.     adcl    $0,%edx            # U
  270.     andl    $12,%eax        # V    loop unrolling
  271.     movl    %ebx,(%edi)        # U
  272.  
  273.     addl    %eax,%esi        # V    loop unrolling
  274.     addl    %eax,%edi        # U    loop unrolling
  275.  
  276.     jmp    *ms32_jumptable(%eax)    # NP    loop unrolling
  277.  
  278.     .align    align4
  279. ms32_jumptable:
  280.     .long    ms32_case0
  281.     .long    ms32_case1
  282.     .long    ms32_case2
  283.     .long    ms32_case3
  284.  
  285.     .align    align8
  286.     nop
  287.     nop
  288.     nop
  289.  
  290. ms32_case0:
  291.     subl    $4,%ebp        # U
  292.     jbe    ms32_done    # V
  293.  
  294. ms32_loop:
  295.     movl    4(%esi),%eax    # U
  296.     movl    %edx,%ebx    # V    Remember carry for later
  297.     addl    $16,%esi    # U
  298.     addl    $16,%edi    # V
  299.     mull    %ecx        # NP
  300.     addl    %ebx,%eax    # U    Add carry in from previous word
  301.     movl    -12(%edi),%ebx    # V
  302.     adcl    $0,%edx        # U
  303.     subl    %eax,%ebx    # V
  304.     adcl    $0,%edx        # U
  305.     movl    %ebx,-12(%edi)    # V
  306. ms32_case3:
  307.     movl    -8(%esi),%eax    # U
  308.     movl    %edx,%ebx    # V    Remember carry for later
  309.     mull    %ecx        # NP
  310.     addl    %ebx,%eax    # U    Add carry in from previous word
  311.     movl    -8(%edi),%ebx    # V
  312.     adcl    $0,%edx        # U
  313.     subl    %eax,%ebx    # V
  314.     adcl    $0,%edx        # U
  315.     movl    %ebx,-8(%edi)    # V
  316. ms32_case2:
  317.     movl    -4(%esi),%eax    # U
  318.     movl    %edx,%ebx    # V    Remember carry for later
  319.     mull    %ecx        # NP
  320.     addl    %ebx,%eax    # U    Add carry in from previous word
  321.     movl    -4(%edi),%ebx    # V
  322.     adcl    $0,%edx        # U
  323.     subl    %eax,%ebx    # V
  324.     adcl    $0,%edx        # U
  325.     movl    %ebx,-4(%edi)    # V
  326. ms32_case1:
  327.     movl    (%esi),%eax    # U
  328.     movl    %edx,%ebx    # V    Remember carry for later
  329.     mull    %ecx        # NP
  330.     addl    %ebx,%eax    # U    Add carry in from previous word
  331.     movl    (%edi),%ebx    # V
  332.     adcl    $0,%edx        # U
  333.     subl    %eax,%ebx    # V
  334.     adcl    $0,%edx        # U
  335.     movl    %ebx,(%edi)    # V
  336.  
  337.     subl    $4,%ebp        # U
  338.     ja    ms32_loop    # V
  339.  
  340. ms32_done:
  341.     popl    %ebx        # U
  342.     popl    %ebp        # V
  343.     movl    %edx,%eax    # U
  344.     popl    %edi        # V
  345.     popl    %esi        # U
  346.     ret            # NP
  347.  
  348. ## Two-word by one-word divide.  Stores quotient, returns remainder.
  349. ## BNWORD32 lbnDiv21_32(BNWORD32 *q, BNWORD32 nh, BNWORD32 nl, BNWORD32 d)
  350. ##                      4            8            12           16
  351.  
  352.     .align align16
  353. lbnDiv21_32:
  354. _lbnDiv21_32:
  355.     movl    8(%esp),%edx    # U    Load nh
  356.     movl    12(%esp),%eax    # V    Load nl
  357.     movl    4(%esp),%ecx    # U    Load q
  358.     divl    16(%esp)    # NP
  359.     movl    %eax,(%ecx)    # U    Store quotient
  360.     movl    %edx,%eax    # V    Return remainder
  361.     ret
  362.  
  363. ## Multi-word by one-word remainder.
  364. ## This speeds up key generation.  It's not worth unrolling and so on;
  365. ## using 32-bit divides is enough of a speedup.
  366. ##
  367. ## The modulus (in %ebp) is often 16 bits.  Given that the dividend is 32
  368. ## bits, the chances of saving the first divide because the high word of the
  369. ## dividend is less than the modulus are low enough it's not worth taking
  370. ## the cycles to test for it.
  371. ##
  372. ## unsigned lbnModQ_32(BNWORD32 const *n, unsigned len, unsigned d)
  373. ##                     4                  8             12
  374.     .align align16
  375. lbnModQ_32:
  376. _lbnModQ_32:
  377.     movl    4(%esp),%eax        # U    Load n
  378.     pushl    %ebp            # V
  379.     movl    12(%esp),%ebp        # U    Load len
  380.     pushl    %esi            # V
  381.     leal    -4(%eax,%ebp,4),%esi    # U
  382.     movl    20(%esp),%ecx        # V    Load d
  383.     xorl    %edx,%edx        # U    Clear MSW for first divide
  384. modq32_loop:
  385.     movl    (%esi),%eax        # U
  386.     subl    $4,%esi            # V
  387.     divl    %ecx            # NP
  388.     decl    %ebp            # U
  389.     jnz    modq32_loop        # V
  390.  
  391.     popl    %esi            # U
  392.     movl    %edx,%eax        # V
  393.     popl    %ebp            # U
  394.     ret                # NP
  395.