2.9BSD - /usr/src/lib/ape/shift.c

   1: #include "lint.h"
   2: #ifndef lint
   3: static char sccs_id[] = "%W%	%G%";
   4: #endif lint
   5: #include <stdio.h>
   6: #include <ape.h>
   7: #define odd(n)      ((n)&01)
   8: #define even(n)     !odd(n)
   9: 
  10: lshift(a,amount)    /* left shift a by amount words --
  11: 			 * i.e., multiply by 2^(15*amount) */
  12: PMINT a;
  13: int amount;
  14: {
  15:     short *temp;
  16:     int i, negative, alen;
  17:     char *realloc();
  18: 
  19:     negative = ( a->len < 0 );
  20:     if (negative) a->len = -a->len;
  21:     alen = a->len+amount;
  22:     fmout(a,stderr);
  23:     fputc('\n',stderr);
  24:     temp = (short *) realloc ((char *)a->val, (unsigned) alen * sizeof(short) );
  25:     fmout(a,stderr);
  26:     fputc('\n',stderr);
  27:     for (i = alen - 1; i >= amount; --i)
  28:         temp[i] = temp[i-amount];
  29:     for (i=0; i < amount; ++ i)
  30:         temp[i] = 0;
  31:     xfree(a);
  32:     a->len = negative ? -alen : alen;
  33:     a->val = temp;
  34: }
  35: 
  36: mshift(a,answer,amount) /* same as lshift, except puts answer in answer */
  37: PMINT a, answer;
  38: int amount;
  39: {
  40:     short *temp;
  41:     int i, negative, alen;
  42: 
  43:     negative = ( a->len < 0 );
  44:     if (negative)
  45:         alen = amount - a->len;
  46:     else
  47:         alen = a->len+amount;
  48:     temp =  xalloc (alen, "mshift");
  49:     for (i = alen - 1; i >= amount; --i)
  50:         temp[i] = a->val[i-amount];
  51:     for (i=0; i < amount; ++ i)
  52:         temp[i] = 0;
  53:     xfree(answer);
  54:     answer->len = negative ? -alen : alen;
  55:     answer->val = temp;
  56: }
  57: rshift(a,amount)    /* right shift a by amount words --
  58: 			 * i.e., divide by 2^(15*amount) */
  59: PMINT a;
  60: int amount;
  61: {
  62:     char *realloc();
  63:     int i, negative, alen;
  64: 
  65:     negative = ( a->len < 0 );
  66:     if (negative) a->len = -a->len;
  67:     alen = a->len-amount;
  68:     if (alen <= 0) {
  69:         xfree(a);
  70:         return;
  71:         }
  72:     for (i=amount; i < a->len; ++i)
  73:         a->val[i-amount] = a->val[i];
  74:     a->val = (short *) realloc ((char *)a->val, (unsigned) alen * sizeof(short));
  75:     a->len = negative ? -alen : alen;
  76: }
  77: 
  78: powerof2(a,n)       /* a = a*2^n */
  79: PMINT a;
  80: int n;
  81: {
  82:     int wordshift, negative, bitshift, right,  i, oldcarry, newcarry;
  83:     short mask;
  84: 
  85:     negative = a->len < 0;
  86:     if (negative) a->len = -a->len;
  87:     right = ( n < 0 );
  88:     if (right) n = -n;
  89:     wordshift = n/WORDLENGTH;
  90:     bitshift = n%WORDLENGTH;
  91:     if (right) {
  92:         rshift(a, wordshift);
  93:         mask = ~(~0 << bitshift);
  94:         oldcarry = 0;
  95:         for (i=a->len-1; i >= 0 ; --i) {
  96:             newcarry = (a->val[i] & mask) << (WORDLENGTH-bitshift);
  97:             a->val[i] = oldcarry + (a->val[i]>>bitshift);
  98:             oldcarry = newcarry;
  99:             }
 100:         if (a->val[a->len-1] == 0)
 101:             --a->len;
 102:         }
 103:     else {
 104:         lshift(a, wordshift);
 105:         mask = (~0 << WORDLENGTH-bitshift);
 106:         oldcarry = 0;
 107:         for (i=0; i < a->len; ++i) {
 108:             newcarry = (a->val[i] & mask) >> (WORDLENGTH-bitshift);
 109:             a->val[i] = oldcarry + (a->val[i]<<bitshift);
 110:             oldcarry = newcarry;
 111:             }
 112:         if (oldcarry) { /* rely on extra space given by xalloc */
 113:             a->len += 1;
 114:             a->val[a->len-1] = oldcarry;
 115:             }
 116:         }
 117:     if (negative) a->len = -a->len;
 118:     return;
 119: }
 120: 
 121: oddpart(a)  /* replace a by its odd part, returning the no. of
 122: 		 * 2's in it */
 123: PMINT a;
 124: {
 125:     int zerowords, zerobits;
 126:     short nonzero;
 127: 
 128:     mcan(a);
 129:     if (a->len == 0) return(0);
 130:     for (zerowords=0; a->val[zerowords] == 0; ++zerowords)
 131:         ;
 132:     nonzero = a->val[zerowords];
 133:     zerobits = WORDLENGTH*zerowords;
 134:     while (even(nonzero)) {
 135:         ++zerobits;
 136:         nonzero <<= 1;
 137:         }
 138:     powerof2(a,zerobits);
 139:     return(zerobits);
 140: }

Defined functions

Defined variables

Defined macros