home *** CD-ROM | disk | FTP | other *** search
/ The CDPD Public Domain Collection for CDTV 3 / CDPDIII.bin / pd / programming / assembler / thesource / volume4 / utilities / d2asm.lha / d2asm.c next >
Encoding:
C/C++ Source or Header  |  1993-02-14  |  4.5 KB  |  122 lines
  1. #include <stdio.h>
  2.  
  3. /* Program to generate "star-chain-sequence" for division of an unsigned
  4. 16-bit integer numerator by an unsigned 16-bit integer constant denominator.
  5. It assumes the existence of two 32-bit integer "registers", add, subtract, and
  6. shift instructions. It uses the "star-chain" multiplication routine from DDJ
  7. 125, March 1987 page 35 */
  8.  
  9. static unsigned int mult; /* global variable for trim_trailing() & binmul() */
  10.  
  11. /* Support subroutine to trim trailing 0s or 1s from global variable "mult". */
  12. int trim_trailing(one_zero) int one_zero;
  13. { /* if one_zero        == 0, trim trailing zeros in "mult", return "count"
  14.                         == 1, ones                                       */
  15.         int c; /* bit counter */
  16.         for (c = 0; ((mult & 1) == one_zero); c++, mult >>= 1) ;
  17.         return c;
  18. }/* Slightly modified version of multiplication routine */
  19. binmul(m) long m;
  20. {
  21.         int     last_shift,     /* final shift count */
  22.                 last_cnt,       /* count of low-order zeros */
  23.                 stkptr,         /* pointer to "stack[]" */
  24.                 cnt,            /* bit counter */
  25.                 ts,             /* top-of-stack element */
  26.                 flag,           /* flag for special-case */
  27.                 stack[16];      /* stack for shift-add/subs */
  28.         mult = m;
  29.         stkptr = last_cnt = 0;  /* init. stack ptr. and count */
  30.         last_shift = trim_trailing(0);  /* trim trailing 0s */
  31.         while (1)
  32.         { /* loop to decompose "mult", building stack */
  33.                 cnt = trim_trailing(1); /* count low-order 1s */
  34.                 if (cnt > 1)
  35.                 { /* more than 1 bit, shift-subtract */
  36.                         flag = 0;
  37.                         if (last_cnt == 1)
  38.          /* shift "k",sub,shift 1,add --> shift "k+1", sub */
  39.                                 stack[stkptr-1] = -(cnt+1); /* overwrite */
  40.                         else
  41.                                 stack[stkptr++] = -cnt;
  42.                 }
  43.                 else
  44.                         flag = 1; /* need another shift-add */
  45.                 if (mult == 0) break; /* decomp. "mult", now output */
  46.                 last_cnt = trim_trailing(0) + flag; /* low-order 0s */
  47.                 stack[stkptr++] = last_cnt; /* shift-add */
  48.         }
  49.         while (stkptr > 0)
  50.         { /* output code from stack */
  51.             ts = stack[--stkptr]; /* get top stack element */
  52.             if (ts < 0)
  53.             { /* generate shift-subtract instructions */
  54.                     printf("\tlsl.l\t#%d,d0\n",-ts);
  55.                     printf("\tsub.l\td1,d0\n");
  56.             }
  57.             else
  58.             { /* generate shift-add instructions */
  59.                     printf("\tlsl.l\t#%d,d0\n",ts);
  60.                     printf("\tadd.l\td1,d0\n");
  61.             }
  62.         }
  63.         if (last_shift != 0) printf("\tlsl.l\t#%d,d0\n",last_shift);
  64. }
  65.  
  66. main(int argc,char **argv)
  67. { /* generate pseudo-instructions for star-chain division */
  68.         int     a,b,r, /* computed multiplier, addend, and remainder */
  69.             i2,     /* number of bits to scale divisor */
  70.             denom,  /* intended divisor */
  71.             denom2; /* divisor scaled by powers-of-2 */
  72.         int z = 65536;  /* 2^16 */
  73.         if (argc < 2)
  74.         {
  75.         printf("\nConstant Divide -> MACRO using shift/add/sub\n");
  76.             printf("\nEnter positive integer denominator: ");
  77.             scanf("%d",&denom);
  78.             printf("\n");
  79.         }
  80.         else
  81.         {
  82.             denom = atoi(argv[1]);
  83.         }
  84.         if (denom > 65535)
  85.         {
  86.             printf("Denominator greater than 16 bits!\n");
  87.             exit(1);
  88.         }
  89.         if (denom != 0)
  90.         { /* scale denominator by powers-of-2 */
  91.             printf("D%d\tMACRO\n",denom);
  92.             mult = denom;
  93.             i2 = trim_trailing(0); /* how many powers-of-2? */
  94.             denom2 = mult;
  95.             if (denom2 == 1)
  96.             { /* divisor was power-of-2, simply scale it */
  97.                 if (i2 > 0)
  98.                 {
  99.                     printf("\tlsl.l\t#%d,d0\n",i2);
  100.                 }
  101.                 else
  102.                 {
  103.                     printf("\tnop\t\t; Divide by 1?!?  Idiot.\n");
  104.                 }
  105.             }
  106.             else
  107.             { /* divisor not power-of-2, scale and more */
  108.                 if (i2 > 0)
  109.                     printf("\tlsr.l\t#%d,d0\n",i2); /* handle scaling */
  110.             printf("\tmove.l\td0,d1\n");    /* load work register */
  111.             a = z / denom2;         /* scaled reciprocal */
  112.             r = z % denom2;        /* remainder of recip. */
  113.             b = a + r - 1;
  114.             binmul(a);
  115.             printf("\tadd.l\t#%d,d0\n",b);
  116.             printf("\tswap\td0\n");
  117.         }
  118.         printf("\tENDM\n");
  119.         }
  120.         else    printf("Cannot divide by zero\n"); /* special case */
  121. }
  122.