sys/src/libmp/port/mplogic.c

   1 #include "os.h"
   2 #include <mp.h>
   3 #include "dat.h"
   4
   5 /*
   6         mplogic calculates b1|b2 subject to the
   7         following flag bits (fl)
   8
   9         bit 0: subtract 1 from b1
  10         bit 1: invert b1
  11         bit 2: subtract 1 from b2
  12         bit 3: invert b2
  13         bit 4: add 1 to output
  14         bit 5: invert output
  15
  16         it inverts appropriate bits automatically
  17         depending on the signs of the inputs
  18 */
  19
  20 static void
  21 mplogic(mpint *b1, mpint *b2, mpint *sum, int fl)
  22 {
  23         mpint *t;
  24         mpdigit *dp1, *dp2, *dpo, d1, d2, d;
  25         int c1, c2, co;
  26         int i;
  27
  28         assert(((b1->flags | b2->flags | sum->flags) & MPtimesafe) == 0);
  29         if(b1->sign < 0) fl ^= 0x03;
  30         if(b2->sign < 0) fl ^= 0x0c;
  31         sum->sign = (int)(((fl|fl>>2)^fl>>4)<<30)>>31|1;
  32         if(sum->sign < 0) fl ^= 0x30;
  33         if(b2->top > b1->top){
  34                 t = b1;
  35                 b1 = b2;
  36                 b2 = t;
  37                 fl = fl >> 2 & 0x03 | fl << 2 & 0x0c | fl & 0x30;
  38         }
  39         mpbits(sum, b1->top*Dbits+1);
  40         dp1 = b1->p;
  41         dp2 = b2->p;
  42         dpo = sum->p;
  43         c1 = fl & 1;
  44         c2 = fl >> 2 & 1;
  45         co = fl >> 4 & 1;
  46         for(i = 0; i < b1->top; i++){
  47                 d1 = dp1[i] - c1;
  48                 if(i < b2->top)
  49                         d2 = dp2[i] - c2;
  50                 else
  51                         d2 = 0;
  52                 if(d1 != (mpdigit)-1) c1 = 0;
  53                 if(d2 != (mpdigit)-1) c2 = 0;
  54                 if((fl & 2) != 0) d1 ^= -1;
  55                 if((fl & 8) != 0) d2 ^= -1;
  56                 d = d1 | d2;
  57                 if((fl & 32) != 0) d ^= -1;
  58                 d += co;
  59                 if(d != 0) co = 0;
  60                 dpo[i] = d;
  61         }
  62         sum->top = i;
  63         if(co)
  64                 dpo[sum->top++] = co;
  65         mpnorm(sum);
  66 }
  67
  68 void
  69 mpor(mpint *b1, mpint *b2, mpint *sum)
  70 {
  71         mplogic(b1, b2, sum, 0);
  72 }
  73
  74 void
  75 mpand(mpint *b1, mpint *b2, mpint *sum)
  76 {
  77         mplogic(b1, b2, sum, 0x2a);
  78 }
  79
  80 void
  81 mpbic(mpint *b1, mpint *b2, mpint *sum)
  82 {
  83         mplogic(b1, b2, sum, 0x22);
  84 }
  85
  86 void
  87 mpnot(mpint *b, mpint *r)
  88 {
  89         mpadd(b, mpone, r);
  90         if(r->top != 0)
  91                 r->sign ^= -2;
  92 }
  93
  94 void
  95 mpxor(mpint *b1, mpint *b2, mpint *sum)
  96 {
  97         mpint *t;
  98         mpdigit *dp1, *dp2, *dpo, d1, d2, d;
  99         int c1, c2, co;
 100         int i, fl;
 101
 102         assert(((b1->flags | b2->flags | sum->flags) & MPtimesafe) == 0);
 103         if(b2->top > b1->top){
 104                 t = b1;
 105                 b1 = b2;
 106                 b2 = t;
 107         }
 108         fl = (b1->sign & 10) ^ (b2->sign & 12);
 109         sum->sign = (int)(fl << 28) >> 31 | 1;
 110         mpbits(sum, b1->top*Dbits+1);
 111         dp1 = b1->p;
 112         dp2 = b2->p;
 113         dpo = sum->p;
 114         c1 = fl >> 1 & 1;
 115         c2 = fl >> 2 & 1;
 116         co = fl >> 3 & 1;
 117         for(i = 0; i < b1->top; i++){
 118                 d1 = dp1[i] - c1;
 119                 if(i < b2->top)
 120                         d2 = dp2[i] - c2;
 121                 else
 122                         d2 = 0;
 123                 if(d1 != (mpdigit)-1) c1 = 0;
 124                 if(d2 != (mpdigit)-1) c2 = 0;
 125                 d = d1 ^ d2;
 126                 d += co;
 127                 if(d != 0) co = 0;
 128                 dpo[i] = d;
 129         }
 130         sum->top = i;
 131         if(co)
 132                 dpo[sum->top++] = co;
 133         mpnorm(sum);
 134 }
 135
 136 void
 137 mptrunc(mpint *b, int n, mpint *r)
 138 {
 139         int d, m, i, c;
 140
 141         assert(((b->flags | r->flags) & MPtimesafe) == 0);
 142         mpbits(r, n);
 143         r->top = DIGITS(n);
 144         d = n / Dbits;
 145         m = n % Dbits;
 146         if(b->sign == -1){
 147                 c = 1;
 148                 for(i = 0; i < r->top; i++){
 149                         if(i < b->top)
 150                                 r->p[i] = ~(b->p[i] - c);
 151                         else
 152                                 r->p[i] = -1;
 153                         if(r->p[i] != 0)
 154                                 c = 0;
 155                 }
 156                 if(m != 0)
 157                         r->p[d] &= (1<<m) - 1;
 158         }else if(b->sign == 1){
 159                 if(d >= b->top){
 160                         mpassign(b, r);
 161                         mpnorm(r);
 162                         return;
 163                 }
 164                 if(b != r)
 165                         for(i = 0; i < d; i++)
 166                                 r->p[i] = b->p[i];
 167                 if(m != 0)
 168                         r->p[d] = b->p[d] & (1<<m)-1;
 169         }
 170         r->sign = 1;
 171         mpnorm(r);
 172 }
 173
 174 void
 175 mpxtend(mpint *b, int n, mpint *r)
 176 {
 177         int d, m, c, i;
 178
 179         d = (n - 1) / Dbits;
 180         m = (n - 1) % Dbits;
 181         if(d >= b->top){
 182                 mpassign(b, r);
 183                 return;
 184         }
 185         mptrunc(b, n, r);
 186         mpbits(r, n);
 187         if((r->p[d] & 1<<m) == 0){
 188                 mpnorm(r);
 189                 return;
 190         }
 191         r->p[d] |= -(1<<m);
 192         r->sign = -1;
 193         c = 1;
 194         for(i = 0; i < r->top; i++){
 195                 r->p[i] = ~(r->p[i] - c);
 196                 if(r->p[i] != 0)
 197                         c = 0;
 198         }
 199         mpnorm(r);
 200 }
 201
 202 void
 203 mpasr(mpint *b, int n, mpint *r)
 204 {
 205         if(b->sign > 0 || n <= 0){
 206                 mpright(b, n, r);
 207                 return;
 208         }
 209         mpadd(b, mpone, r);
 210         mpright(r, n, r);
 211         mpsub(r, mpone, r);
 212 }