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