home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / BNLIB / LBN68000.C < prev    next >
C/C++ Source or Header  |  1996-05-16  |  15KB  |  461 lines
  1. /*
  2.  * lbn68000.c - 16-bit bignum primitives for the 68000 (or 68010) 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 (1 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.  
  21. #include <limits.h>
  22.  
  23. #include "lbn.h"        /* Should include lbn68000.h */
  24.  
  25. /*
  26.  * The Metrowerks C compiler (1.2.2) produces bad 68k code for the
  27.  * following input, which happens to be the inner loop of lbnSub1,
  28.  * so a few less than critical routines have been recoded in assembly
  29.  * to avoid the bug.  (Optimizer on or off does not matter.)
  30.  * 
  31.  * unsigned
  32.  * decrement(unsigned *num, unsigned len)
  33.  * {
  34.  *      do {
  35.  *              if ((*num++)-- != 0)
  36.  *                      return 0;
  37.  *      } while (--len);
  38.  *      return 1;
  39.  * }
  40.  */
  41. asm BNWORD16
  42. lbnSub1_16(BNWORD16 *num, unsigned len, BNWORD16 borrow)
  43. {
  44.         movea.l 4(sp),a0        /* num */
  45. #if UINT_MAX == 0xffff
  46.         move.w  10(sp),d0       /* borrow */
  47. #else
  48.         move.w  12(sp),d0       /* borrow */
  49. #endif
  50.         sub.w   d0,(a0)+
  51.         bcc             done
  52. #if UINT_MAX == 0xffff
  53.         move.w  8(sp),d0        /* len */
  54. #else
  55.         move.w  10(sp),d0       /* len */
  56. #endif
  57.         subq.w  #2,d0
  58.         bcs             done
  59. loop:
  60.         subq.w  #1,(a0)+
  61.         dbcc    d0,loop
  62. done:
  63.         moveq.l #0,d0
  64.         addx.w  d0,d0
  65.         rts
  66. }
  67.  
  68. asm BNWORD16
  69. lbnAdd1_16(BNWORD16 *num, unsigned len, BNWORD16 carry)
  70. {
  71.         movea.l 4(sp),a0        /* num */
  72. #if UINT_MAX == 0xffff
  73.         move.w  10(sp),d0       /* carry */
  74. #else
  75.         move.w  12(sp),d0       /* carry */
  76. #endif
  77.         add.w   d0,(a0)+
  78.         bcc             done
  79. #if UINT_MAX == 0xffff
  80.         move.w  8(sp),d0        /* len */
  81. #else
  82.         move.w  10(sp),d0       /* len */
  83. #endif
  84.         subq.w  #2,d0
  85.         bcs             done
  86. loop:
  87.         addq.w  #1,(a0)+
  88.         dbcc    d0,loop
  89. done:
  90.         moveq.l #0,d0
  91.         addx.w  d0,d0
  92.         rts
  93. }
  94.  
  95. asm void
  96. lbnMulN1_16(BNWORD16 *out, BNWORD16 const *in, unsigned len, BNWORD16 k)
  97. {
  98.         move.w  d3,-(sp)        /* 2 bytes of stack frame */
  99.         move.l  2+4(sp),a1      /* out */
  100.         move.l  2+8(sp),a0      /* in */
  101. #if UINT_MAX == 0xffff
  102.         move.w  2+12(sp),d3     /* len */
  103.         move.w  2+14(sp),d2     /* k */
  104. #else
  105.         move.w  2+14(sp),d3     /* len (low 16 bits) */
  106.         move.w  2+16(sp),d2     /* k */
  107. #endif
  108.  
  109.         move.w  (a0)+,d1        /* First multiply */
  110.         mulu.w  d2,d1
  111.         move.w  d1,(a1)+
  112.         clr.w   d1
  113.         swap    d1
  114.  
  115.         subq.w  #1,d3           /* Setup for loop unrolling */
  116.         lsr.w   #1,d3
  117.         bcs.s   m16_even
  118.         beq.s   m16_short
  119.         
  120.         subq.w  #1,d3           /* Set up software pipeline properly */
  121.         move.l  d1,d0
  122.         
  123. m16_loop:
  124.         move.w  (a0)+,d1
  125.         mulu.w  d2,d1
  126.         add.l   d0,d1
  127.         move.w  d1,(a1)+
  128.         clr.w    d1
  129.         swap    d1
  130. m16_even:
  131.  
  132.         move.w  (a0)+,d0
  133.         mulu.w  d2,d0
  134.         add.l   d1,d0
  135.         move.w  d0,(a1)+
  136.         clr.w   d0
  137.         swap    d0
  138.  
  139.         dbra    d3,m16_loop
  140.         
  141.         move.w  d0,(a1)
  142.         move.w  (sp)+,d3
  143.         rts
  144. m16_short:
  145.         move.w  d1,(a1)
  146.         move.w  (sp)+,d3
  147.         rts
  148. }
  149.  
  150.  
  151. asm BNWORD16
  152. lbnMulAdd1_16(BNWORD16 *out, BNWORD16 const *in, unsigned len, BNWORD16 k)
  153. {
  154.         move.w  d4,-(sp) 
  155.         clr.w   d4
  156.         move.w  d3,-(sp)        /* 4 bytes of stack frame */
  157.         move.l  4+4(sp),a1      /* out */
  158.         move.l  4+8(sp),a0      /* in */
  159. #if UINT_MAX == 0xffff
  160.         move.w  4+12(sp),d3     /* len */
  161.         move.w  4+14(sp),d2     /* k */
  162. #else
  163.         move.w  4+14(sp),d3     /* len (low 16 bits) */
  164.         move.w  4+16(sp),d2     /* k */
  165. #endif
  166.  
  167.         move.w  (a0)+,d1        /* First multiply */
  168.         mulu.w  d2,d1
  169.         add.w   d1,(a1)+
  170.         clr.w   d1
  171.         swap    d1
  172.         addx.w  d4,d1
  173.  
  174.         subq.w  #1,d3           /* Setup for loop unrolling */
  175.         lsr.w   #1,d3
  176.         bcs.s   ma16_even
  177.         beq.s   ma16_short
  178.         
  179.         subq.w  #1,d3           /* Set up software pipeline properly */
  180.         move.l  d1,d0
  181.         
  182. ma16_loop:
  183.         move.w  (a0)+,d1
  184.         mulu.w  d2,d1
  185.         add.l   d0,d1
  186.         add.w   d1,(a1)+
  187.         clr.w   d1
  188.         swap    d1
  189.         addx.w  d4,d1
  190. ma16_even:
  191.  
  192.         move.w  (a0)+,d0
  193.         mulu.w  d2,d0
  194.         add.l   d1,d0
  195.         add.w   d0,(a1)+
  196.         clr.w   d0
  197.         swap    d0
  198.         addx.w  d4,d0
  199.  
  200.         dbra    d3,ma16_loop
  201.         
  202.         move.w  (sp)+,d3
  203.         move.w  (sp)+,d4
  204.         rts
  205. ma16_short:
  206.         move.w  (sp)+,d3
  207.         move.l  d1,d0   
  208.         move.w  (sp)+,d4
  209.         rts
  210. }
  211.  
  212.  
  213.  
  214. asm BNWORD16
  215. lbnMulSub1_16(BNWORD16 *out, BNWORD16 const *in, unsigned len, BNWORD16 k)
  216. {
  217.         move.w  d4,-(sp) 
  218.         clr.w   d4
  219.         move.w  d3,-(sp)        /* 4 bytes of stack frame */
  220.         move.l  4+4(sp),a1      /* out */
  221.         move.l  4+8(sp),a0      /* in */
  222. #if UINT_MAX == 0xffff
  223.         move.w  4+12(sp),d3     /* len */
  224.         move.w  4+14(sp),d2     /* k */
  225. #else
  226.         move.w  4+14(sp),d3     /* len (low 16 bits) */
  227.         move.w  4+16(sp),d2     /* k */
  228. #endif
  229.  
  230.         move.w  (a0)+,d1        /* First multiply */
  231.         mulu.w  d2,d1
  232.         sub.w   d1,(a1)+
  233.         clr.w   d1
  234.         swap    d1
  235.         addx.w  d4,d1
  236.  
  237.         subq.w  #1,d3           /* Setup for loop unrolling */
  238.         lsr.w   #1,d3
  239.         bcs.s   ms16_even
  240.         beq.s   ms16_short
  241.         
  242.         subq.w  #1,d3           /* Set up software pipeline properly */
  243.         move.l  d1,d0
  244.         
  245. ms16_loop:
  246.         move.w  (a0)+,d1
  247.         mulu.w  d2,d1
  248.         add.l   d0,d1
  249.         sub.w   d1,(a1)+
  250.         clr.w   d1
  251.         swap    d1
  252.         addx.w  d4,d1
  253. ms16_even:
  254.  
  255.         move.w  (a0)+,d0
  256.         mulu.w  d2,d0
  257.         add.l   d1,d0
  258.         sub.w   d0,(a1)+
  259.         clr.w   d0
  260.         swap    d0
  261.         addx.w  d4,d0
  262.  
  263.         dbra    d3,ms16_loop
  264.         
  265.         move.w  (sp)+,d3
  266.         move.w  (sp)+,d4
  267.         rts
  268. ms16_short:
  269.         move.w  (sp)+,d3
  270.         move.l  d1,d0   
  271.         move.w  (sp)+,d4
  272.         rts
  273. }
  274.  
  275. /* The generic long/short divide doesn't know that nh < d */
  276. asm BNWORD16
  277. lbnDiv21_16(BNWORD16 *q, BNWORD16 nh, BNWORD16 nl, BNWORD16 d)
  278. {
  279.         move.l  8(sp),d0        /* nh *and* nl */
  280.         divu.w    12(sp),d0
  281.         move.l    4(sp),a0
  282.         move.w    d0,(a0)
  283.         clr.w    d0
  284.         swap    d0
  285.         rts
  286. }
  287.  
  288. asm unsigned
  289. lbnModQ_16(BNWORD16 const *n, unsigned len, BNWORD16 d)
  290. {
  291.         move.l  4(sp),a0        /* n */
  292.         moveq.l    #0,d1
  293. #if UINT_MAX == 0xffff
  294.         move.w  8(sp),d1        /* len */
  295.         move.w  10(sp),d2       /* d */
  296. #else
  297.         move.w  10(sp),d1       /* len (low 16 bits) */
  298.         move.w  12(sp),d2       /* d */
  299. #endif
  300.  
  301.         add.l    d1,a0
  302.         add.l    d1,a0            /* n += len */
  303.         moveq.l    #0,d0
  304.         subq.w  #1,d1
  305.  
  306. mq16_loop:
  307.         move.w  -(a0),d0        /* Assemble remainder and new word */
  308.         divu.w  d2,d0            /* Put remainder in high half of d0 */
  309.         dbra    d1,mq16_loop    
  310.                         
  311. mq16_done:
  312.         clr.w   d0
  313.         swap    d0
  314.         rts
  315. }
  316.  
  317. /*
  318.  * Detect if this is a 32-bit processor (68020+ *or* CPU32).
  319.  * Both the 68020+ and CPU32 processors (which have 32x32->64-bit
  320.  * multiply, what the 32-bit math library wants) support scaled indexed
  321.  * addressing.  The 68000 and 68010 ignore the scale selection
  322.  * bits, treating it as *1 all the time.  So a 32-bit processor
  323.  * will evaluate -2(a0,a0.w*2) as 1+1*2-2 = 1.
  324.  * A 16-bit processor will compute 1+1-2 = 0.
  325.  *
  326.  * Thus, the return value will indicate whether the chip this is
  327.  * running on supports 32x32->64-bit multiply (mulu.l).
  328.  */
  329. asm int
  330. is68020(void)
  331. {
  332.         machine 68020
  333.         lea     1,a0
  334. #if 0
  335.         lea     -2(a0,a0.w*2),a0    /* Metrowerks won't assemble this, arrgh */
  336. #else
  337.         dc.w    0x41f0, 0x82fe
  338. #endif
  339.         move.l    a0,d0
  340.         rts
  341. }
  342. /*
  343.  * Since I had to hand-assemble that fancy addressing mode, I had to study
  344.  * up on 680x0 addressing modes.
  345.  * A summary of 680x0 addressing modes.
  346.  * A 68000 effective address specifies an operand on an instruction, which
  347.  * may be a register or in memory.  It is made up of a 3-bit mode and a
  348.  * 3-bit register specifier.  The meanings of the various modes are:
  349.  *
  350.  * 000 reg - Dn, n specified by "reg"
  351.  * 001 reg - An, n specified by "reg"
  352.  * 010 reg - (An)
  353.  * 011 reg - (An)+
  354.  * 100 reg - -(An)
  355.  * 101 reg - d16(An), one 16-bit displacement word follows, sign-extended
  356.  * 110 reg - Fancy addressing mode off of An, see extension word below
  357.  * 111 000 - abs.W, one 16-bit signed absolute address follows
  358.  * 111 001 - abs.L, one 32-bit absolute address follows
  359.  * 111 010 - d16(PC), one 16-bit displacemnt word follows, sign-extended
  360.  * 111 011 - Fancy addressing mode off of PC, see extension word below
  361.  * 111 100 - #immediate, followed by 16 or 32 bits of immediate value
  362.  * 111 101 - unused, reserved
  363.  * 111 110 - unused, reserved
  364.  * 111 111 - unused, reserved
  365.  *
  366.  * Memory references are to data space, except that PC-relative references
  367.  * are to program space, and are read-only.
  368.  *
  369.  * Fancy addressing modes are followed by a 16-bit extension word, and come
  370.  * in "brief" and "full" forms.
  371.  * The "brief" form looks like this.  Bit 8 is 0 to indicate this form:
  372.  *
  373.  * 1   1   1   1   1   1   1  
  374.  * 6   5   4   3   2   1   0   9   8   7   6   5   4   3   2   1   0
  375.  * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  376.  * |A/D|  register |L/W| scale | 0 |   8-bit signed displacement   |
  377.  * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  378.  *
  379.  * The basic effective address specifies a 32-bit base register - A0 through
  380.  * A7 or PC (the address of the following instruction).
  381.  * The A/D and register fields specify an index register.  A/D is 1 for
  382.  * address registers, and 0 for data registers.  L/W specifies the length
  383.  * of the index register, 1 for 32 bits, and 0 for 16 bits (sign-extended).
  384.  * The scale field is a left shift amount (0 to 3 bits) to apply to the
  385.  * sign-extended index register.  The final address is d8(An,Rn.X*SCALE),
  386.  * also written (d8,An,Rn.X*SCALE).  X is "W" or "L", SCALE is 1, 2, 4 or 8.
  387.  * "*1" may be omitted, as may a d8 of 0.
  388.  *
  389.  * The 68000 supports this form, but only with a scale field of 0.
  390.  * It does NOT (says the MC68030 User's Manual MC68030UM/AD, section 2.7)
  391.  * decode the scale field and the following format bit.  They are treated
  392.  * as 0.
  393.  * I recall (I don't have the data book handy) that the CPU32 processor
  394.  * core used in the 683xx series processors supports variable scales,
  395.  * but only the brief extension word form.  I suspect it decodes the
  396.  * format bit and traps if it is not zero, but I don't recall.
  397.  *
  398.  * The "full" form (680x0, x >= 2 processors only) looks like this: 
  399.  *
  400.  * 1   1   1   1   1   1   1  
  401.  * 6   5   4   3   2   1   0   9   8   7   6   5   4   3   2   1   0
  402.  * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  403.  * |A/D|  register |L/W| scale | 1 | BS| IS|BD size| 0 | P |OD size|
  404.  * +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  405.  *
  406.  * The first 8 bits are interpreted the same way as in the brief form,
  407.  * except that bit 8 is set to 1 to indicate the full form.
  408.  * BS, Base Suppress, if set, causes a value of 0 to be used in place of
  409.  * the base register value.  If this is set, the base register
  410.  * specified is irrelevant, except that if it is the PC, the fetch is
  411.  * still done from program space.  The specifier "ZPC" can be used in
  412.  * place of "PC" in the effective address mnemonic to represent this
  413.  * case.
  414.  * IS, Index Suppress, if set, causes a value of 0 to be used in place
  415.  * of the scaled index register. In this case, the first 7 bits of the
  416.  * extension word are irrelevant.
  417.  * BD size specifies the base displacement size.  A value of 00
  418.  * in this field is illegal, while 01, 10 and 11 indicate that the
  419.  * extension word is followed by 0, 1 or 2 16-bit words of base displacement
  420.  * (zero, sign-extended to 32 bits, and most-significant word first,
  421.  * respectively) to add to the base register value.
  422.  * Bit 3 is unused.
  423.  * The P bit is the pre/post indexing bit, and only applies if an outer
  424.  * displacement is used.  This is explained later.
  425.  * OD size specifies the size of an outer displacement.  In the simple
  426.  * case, this field is set to 00 and the effective address is
  427.  * (disp,An,Rn.X*SCALE) or (disp,PC,Rn.X*SCALE).
  428.  * In this case the P bit must be 0.  Any of those compnents may be
  429.  * suppressed, with a BD size of 01, the BS bit, or the IS bit.
  430.  * If the OD size is not 00, it encodes an outer displacement in the same
  431.  * manner as the BD size, and 0, 1 or 2 16-bit words of outer displacement
  432.  * follow the base displacement in the instruction stream.  In this case,
  433.  * this is a double-indirect addressing mode.  The base, base displacement,
  434.  * and possibly the index, specify a 32-bit memory word which holds a value
  435.  * which is fetched, and the outer displacement and possibly the index are
  436.  * added to produce the address of the operand.
  437.  * If the P bit is 0, this is pre-indexed, and the index value is added
  438.  * before the fetch of the indirect word, producing an effective address
  439.  * of ([disp,An,Rn.X*SCALE],disp).  If the P bit is 1, the post-indexed case,
  440.  * the memory word is fectched from base+base displacement, then the index
  441.  * and outer displacement are added to compute the address of the operand.
  442.  * This effective address is written ([disp,An],Rn.X*SCALE,disp).
  443.  * (In both cases, "An" may also be "PC" or "ZPC".)
  444.  * Any of the components may be omitted.  If the index is omitted (using the
  445.  * IS bit), the P bit is irrelevant, but must be written as 0.
  446.  * Thus, legal combinations of IS, P and OD size are:
  447.  * 0 0 00 - (disp,An,Rn.X*SCALE), also written disp(An,Rn.X*SCALE)
  448.  * 0 0 01 - ([disp,An,Rn.X*SCALE])
  449.  * 0 0 10 - ([disp,An,Rn.X*SCALE],d16)
  450.  * 0 0 11 - ([disp,An,Rn.X*SCALE],d32)
  451.  * 0 1 01 - ([disp,An],Rn.X*SCALE)
  452.  * 0 1 10 - ([disp,An],Rn.X*SCALE,d16)
  453.  * 0 1 11 - ([disp,An],Rn.X*SCALE,d32)
  454.  * 1 0 00 - (disp,An), also written disp(An)
  455.  * 1 0 01 - ([disp,An])
  456.  * 1 0 10 - ([disp,An],d16)
  457.  * 1 0 11 - ([disp,An],d32)
  458.  */ 
  459.  
  460. /* 45678901234567890123456789012345678901234567890123456789012345678901234567 */
  461.