home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / BNLIB / LBN68020.C < prev    next >
C/C++ Source or Header  |  1996-05-16  |  8KB  |  310 lines
  1. /*
  2.  * lbn68020.c - 32-bit bignum primitives for the 68020+ (0r 683xx) processors.
  3.  *
  4.  * Copyright (c) 1995  Colin Plumb.  All rights reserved.
  5.  * For licensing and other legal details, see the file legal.c.
  6.  *
  7.  * This was written for Metrowerks C, and while it should be reasonably
  8.  * portable, NOTE that Metrowerks lets a callee trash a0, a1, d0, d1, and d2.
  9.  * Some 680x0 compilers make d2 callee-save, so instructions to save it
  10.  * will have to be added.
  11.  * 
  12.  * This code supports 16 or 32-bit ints, based on UINT_MAX.
  13.  * Regardless of UINT_MAX, only bignums up to 64K words (2 million bits)
  14.  * are supported.  (68k hackers will recognize this as a consequence of
  15.  * using dbra.)
  16.  *
  17.  * These primitives use little-endian word order.
  18.  * (The order of bytes within words is irrelevant to this issue.)
  19.  *
  20.  * TODO: Schedule this for the 68040's pipeline.  (When I get a 68040 manual.)
  21.  */
  22.  
  23. #include <limits.h>
  24.  
  25. #include "lbn.h"        /* Should include lbn68020.h */
  26.  
  27. /*
  28.  * The Metrowerks C compiler (1.2.2) produces bad 68k code for the
  29.  * following input, which happens to be the inner loop of lbnSub1,
  30.  * so a few less than critical routines have been recoded in assembly
  31.  * to avoid the bug.  (Optimizer on or off does not matter.)
  32.  * 
  33.  * unsigned
  34.  * decrement(unsigned *num, unsigned len)
  35.  * {
  36.  *      do {
  37.  *              if ((*num++)-- != 0)
  38.  *                      return 0;
  39.  *      } while (--len);
  40.  *      return 1;
  41.  * }
  42.  */
  43. asm BNWORD32
  44. lbnSub1_32(BNWORD32 *num, unsigned len, BNWORD32 borrow)
  45. {
  46.         movea.l 4(sp),a0        /* num */
  47. #if UINT_MAX == 0xffff
  48.         move.l  10(sp),d0       /* borrow */
  49. #else
  50.         move.l  12(sp),d0       /* borrow */
  51. #endif
  52.         sub.l   d0,(a0)+
  53.         bcc             done
  54. #if UINT_MAX == 0xffff
  55.         move.w  8(sp),d0        /* len */
  56. #else
  57.         move.w  10(sp),d0       /* len */
  58. #endif
  59.         subq.w  #2,d0
  60.         bcs             done
  61. loop:
  62.         subq.l  #1,(a0)+
  63.         dbcc    d0,loop
  64. done:
  65.         moveq.l #0,d0
  66.         addx.w  d0,d0
  67.         rts
  68. }
  69.  
  70. asm BNWORD32
  71. lbnAdd1_32(BNWORD32 *num, unsigned len, BNWORD32 carry)
  72. {
  73.         movea.l 4(sp),a0        /* num */
  74. #if UINT_MAX == 0xffff
  75.         move.l  10(sp),d0       /* carry */
  76. #else
  77.         move.l  12(sp),d0       /* carry */
  78. #endif
  79.         add.l   d0,(a0)+
  80.         bcc             done
  81. #if UINT_MAX == 0xffff
  82.         move.w  8(sp),d0        /* len */
  83. #else
  84.         move.w  10(sp),d0       /* len */
  85. #endif
  86.         subq.w  #2,d0
  87.         bcs             done
  88. loop:
  89.         addq.l  #1,(a0)+
  90.         dbcc    d0,loop
  91. done:
  92.         moveq.l #0,d0
  93.         addx.w  d0,d0
  94.         rts
  95. }
  96.  
  97. asm void
  98. lbnMulN1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
  99. {
  100.         machine 68020
  101.         
  102.         movem.l d3-d5,-(sp)     /* 12 bytes of extra data */
  103.         moveq.l #0,d4
  104.         move.l  16(sp),a1       /* out */
  105.         move.l  20(sp),a0       /* in */
  106. #if UINT_MAX == 0xffff
  107.         move.w  24(sp),d5       /* len */
  108.         move.l  26(sp),d2       /* k */
  109. #else
  110.         move.w  26(sp),d5       /* len */
  111.         move.l  28(sp),d2       /* k */
  112. #endif
  113.  
  114.         move.l  (a0)+,d3        /* First multiply */
  115.         mulu.l  d2,d1:d3        /* dc.w    0x4c02, 0x3401 */
  116.         move.l  d3,(a1)+
  117.  
  118.         subq.w  #1,d5           /* Setup for loop unrolling */
  119.         lsr.w   #1,d5
  120.         bcs.s   m32_even
  121.         beq.s   m32_short
  122.         
  123.         subq.w  #1,d5           /* Set up software pipeline properly */
  124.         move.l  d1,d0
  125.         
  126. m32_loop:
  127.         move.l  (a0)+,d3
  128.         mulu.l  d2,d1:d3        /* dc.w    0x4c02, 0x3401 */
  129.         add.l   d0,d3
  130.         addx.l  d4,d1
  131.         move.l  d3,(a1)+
  132. m32_even:
  133.  
  134.         move.l  (a0)+,d3
  135.         mulu.l  d2,d0:d3        /* dc.w    0x4c02, 0x3400 */
  136.         add.l   d1,d3
  137.         addx.l  d4,d0
  138.         move.l  d3,(a1)+
  139.  
  140.         dbra    d5,m32_loop
  141.         
  142.         move.l  d0,(a1)
  143.         movem.l (sp)+,d3-d5
  144.         rts
  145. m32_short:
  146.         move.l  d1,(a1)
  147.         movem.l (sp)+,d3-d5
  148.         rts
  149. }
  150.  
  151.  
  152. asm BNWORD32
  153. lbnMulAdd1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
  154. {
  155.         machine 68020
  156.         movem.l d3-d5,-(sp)     /* 12 bytes of extra data */
  157.         moveq.l #0,d4
  158.         move.l  16(sp),a1       /* out */
  159.         move.l  20(sp),a0       /* in */
  160. #if UINT_MAX == 0xffff
  161.         move.w  24(sp),d5       /* len */
  162.         move.l  26(sp),d2       /* k */
  163. #else
  164.         move.w  26(sp),d5       /* len */
  165.         move.l  28(sp),d2       /* k */
  166. #endif
  167.  
  168.         move.l  (a0)+,d3        /* First multiply */
  169.         mulu.l  d2,d1:d3        /* dc.w    0x4c02, 0x3401 */
  170.         add.l   d3,(a1)+
  171.         addx.l  d4,d1
  172.  
  173.         subq.w  #1,d5           /* Setup for loop unrolling */
  174.         lsr.w   #1,d5
  175.         bcs.s   ma32_even
  176.         beq.s   ma32_short
  177.         
  178.         subq.w  #1,d5           /* Set up software pipeline properly */
  179.         move.l  d1,d0
  180.         
  181. ma32_loop:
  182.         move.l  (a0)+,d3
  183.         mulu.l  d2,d1:d3        /* dc.w    0x4c02, 0x3401 */
  184.         add.l   d0,d3
  185.         addx.l  d4,d1
  186.         add.l   d3,(a1)+
  187.         addx.l  d4,d1
  188. ma32_even:
  189.  
  190.         move.l  (a0)+,d3
  191.         mulu.l  d2,d0:d3        /* dc.w    0x4c02, 0x3400 */
  192.         add.l   d1,d3
  193.         addx.l  d4,d0
  194.         add.l   d3,(a1)+
  195.         addx.l  d4,d0
  196.  
  197.         dbra    d5,ma32_loop
  198.         
  199.         movem.l (sp)+,d3-d5
  200.         rts
  201. ma32_short:
  202.         move.l  d1,d0   
  203.         movem.l (sp)+,d3-d5
  204.         rts
  205. }
  206.  
  207.  
  208. asm BNWORD32
  209. lbnMulSub1_32(BNWORD32 *out, BNWORD32 const *in, unsigned len, BNWORD32 k)
  210. {
  211.         machine 68020
  212.         movem.l d3-d5,-(sp)     /* 12 bytes of extra data */
  213.         moveq.l #0,d4
  214.         move.l  16(sp),a1       /* out */
  215.         move.l  20(sp),a0       /* in */
  216. #if UINT_MAX == 0xffff
  217.         move.w  24(sp),d5       /* len */
  218.         move.l  26(sp),d2       /* k */
  219. #else
  220.         move.w  26(sp),d5       /* len */
  221.         move.l  28(sp),d2       /* k */
  222. #endif
  223.  
  224.         move.l  (a0)+,d3        /* First multiply */
  225.         mulu.l  d2,d1:d3        /* dc.w    0x4c02, 0x3401 */
  226.         sub.l   d3,(a1)+
  227.         addx.l  d4,d1
  228.  
  229.         subq.w  #1,d5           /* Setup for loop unrolling */
  230.         lsr.w   #1,d5
  231.         bcs.s   ms32_even
  232.         beq.s   ms32_short
  233.         
  234.         subq.w  #1,d5           /* Set up software pipeline properly */
  235.         move.l  d1,d0
  236.         
  237. ms32_loop:
  238.         move.l  (a0)+,d3
  239.         mulu.l  d2,d1:d3        /* dc.w    0x4c02, 0x3401 */
  240.         add.l   d0,d3
  241.         addx.l  d4,d1
  242.         sub.l   d3,(a1)+
  243.         addx.l  d4,d1
  244. ms32_even:
  245.  
  246.         move.l  (a0)+,d3
  247.         mulu.l  d2,d0:d3        /* dc.w    0x4c02, 0x3400 */
  248.         add.l   d1,d3
  249.         addx.l  d4,d0
  250.         sub.l   d3,(a1)+
  251.         addx.l  d4,d0
  252.  
  253.         dbra    d5,ms32_loop
  254.         
  255.         movem.l (sp)+,d3-d5
  256.         rts
  257.         
  258. ms32_short:
  259.         move.l  d1,d0
  260.         movem.l (sp)+,d3-d5
  261.         rts
  262. }
  263.  
  264.  
  265. asm BNWORD32
  266. lbnDiv21_32(BNWORD32 *q, BNWORD32 nh, BNWORD32 nl, BNWORD32 d)
  267. {
  268.         machine 68020
  269.         move.l  8(sp),d0
  270.         move.l  12(sp),d1
  271.         move.l  4(sp),a0
  272.         divu.l  16(sp),d0:d1    /*  dc.w    0x4c6f, 0x1400, 16 */
  273.         move.l  d1,(a0)
  274.         rts
  275. }
  276.  
  277. asm unsigned
  278. lbnModQ_32(BNWORD32 const *n, unsigned len, unsigned d)
  279. {
  280.         machine 68020
  281.         move.l  4(sp),a0        /* n */
  282.         move.l  d3,a1
  283. #if UINT_MAX == 0xffff
  284.         moveq.l #0,d2
  285.         move.w  8(sp),d1        /* len */
  286.         move.w  10(sp),d2       /* d */
  287. #else
  288.         move.w  10(sp),d1       /* len */
  289.         move.l  12(sp),d2       /* d */
  290. #endif
  291.         dc.w    0x41f0, 0x1cfc  /* lea  -4(a0,d1.L*4),a0 */
  292.  
  293.     /* First time, divide 32/32 - may be faster than 64/32 */
  294.         move.l  (a0),d3
  295.         divul.l d2,d0:d3        /* dc.w    0x4c02, 0x3000 */
  296.         subq.w  #2,d1
  297.         bmi    mq32_done
  298.  
  299. mq32_loop:
  300.         move.l  -(a0),d3
  301.         divu.l  d2,d0:d3        /* dc.w    0x4c02,0x3400 */
  302.         dbra    d1,mq32_loop    
  303.                         
  304. mq32_done:
  305.         move.l  a1,d3
  306.         rts
  307. }
  308.  
  309. /* 45678901234567890123456789012345678901234567890123456789012345678901234567 */
  310.