src/integer/bitwise/cl_I_ash_I.cc

   1 // ash().
   2
   3 // General includes.
   4 #include "cl_sysdep.h"
   5
   6 // Specification.
   7 #include "cln/integer.h"
   8
   9
  10 // Implementation.
  11
  12 #include "cl_I.h"
  13 #include "cl_DS.h"
  14 #include "cl_I_ash.h"
  15
  16 namespace cln {
  17
  18 const cl_I ash (const cl_I& x, const cl_I& y)
  19 {
  20     // Methode:
  21     // x = 0 -> 0 als Ergebnis
  22     // y = 0 -> x als Ergebnis
  23     // y > 0 -> y = intDsize*k + i, j=k+(1 falls i>0, 0 falls i=0).
  24     //          j Wörter mehr reservieren, k Nullwörter, dann übertragen,
  25     //          bei i>0: um i Bits links schieben (i=1 geht einfacher).
  26     // y < 0 -> y <= - intDsize * (Länge(A0) in Digits) -> Ergebnis = 0 oder -1.
  27     //          Sonst: -y = intDsize*k + i mit k<Länge(A0).
  28     //                  Übertrage die (Länge(A0)-k) MSDigits,
  29     //                  falls i>0: schiebe sie um i Bits nach rechts (i=1 geht einfacher).
  30         if (zerop(x))
  31                 return 0;               // x=0 -> 0 als Ergebnis
  32         if (zerop(y))
  33                 return x;               // y=0 -> x als Ergebnis
  34         CL_ALLOCA_STACK;
  35         if (!minusp(y)) {
  36                 // y>=0
  37                 var uintL i; // i = y mod intDsize, >=0, <intDsize
  38                 var cl_uint k; // k = y div intDsize, >=0, <2^intCsize
  39                 if (bignump(y)) {
  40                         #if (log2_intDsize+intCsize <= cl_value_len-1)
  41                         // y >= 2^(cl_value_len-1) >= intDsize*2^intCsize
  42                         cl_ash_error(y);
  43                         #else
  44                         // y >= 2^(cl_value_len-1)
  45                         // usable only if y < intDsize*2^intCsize
  46                         var cl_heap_bignum* bn = TheBignum(y);
  47                         var uintC len = bn->length;
  48                         if (len > ceiling(log2_intDsize+intCsize+1,intDsize))
  49                                 cl_ash_error(y);
  50                         // bn_minlength <= len <= ceiling(log2_intDsize+intCsize+1,intDsize).
  51                         if (bn_minlength == ceiling(log2_intDsize+intCsize+1,intDsize)
  52                             || len == ceiling(log2_intDsize+intCsize+1,intDsize))
  53                                 if (mspref(arrayMSDptr(bn->data,len),0) >= (uintD)bit((log2_intDsize+intCsize)%intDsize))
  54                                         cl_ash_error(y);
  55                         #if (log2_intDsize+intCsize > intDsize)
  56                         #define IF_LENGTH(i)  \
  57                           if (bn_minlength <= i && i <= ceiling(log2_intDsize+intCsize+1,intDsize) && (i == ceiling(log2_intDsize+intCsize+1,intDsize) || len == i))
  58                         IF_LENGTH(1)
  59                                 k = 0;
  60                         else IF_LENGTH(2)
  61                                 k = get_uint1D_Dptr(arrayLSDptr(bn->data,2) lspop 1);
  62                         else IF_LENGTH(3)
  63                                 k = get_uint2D_Dptr(arrayLSDptr(bn->data,3) lspop 1);
  64                         else IF_LENGTH(4)
  65                                 k = get_uint3D_Dptr(arrayLSDptr(bn->data,4) lspop 1);
  66                         else IF_LENGTH(5)
  67                                 k = get_uint4D_Dptr(arrayLSDptr(bn->data,5) lspop 1);
  68                         else
  69                                 cl_abort();
  70                         #undef IF_LENGTH
  71                         k = k << (intDsize-log2_intDsize);
  72                         #else
  73                         // log2_intDsize+intCsize <= intDsize,
  74                         // implies len==1 or len==2 && lspref(arrayLSDptr(bn->data,len),1) == 0.
  75                         k = 0;
  76                         #endif
  77                         k |= lspref(arrayLSDptr(bn->data,len),0) >> log2_intDsize;
  78                         i = lspref(arrayLSDptr(bn->data,len),0) % intDsize;
  79                         #endif
  80                 } else {
  81                         var uintV y_ = FN_to_V(y); // Wert von y, >=0, <intDsize*2^intCsize
  82                         i = y_%intDsize;
  83                         k = floor(y_,intDsize);
  84                 }
  85                 var uintD* LSDptr;
  86                 var uintC len;
  87                 var const uintD* x_LSDptr;
  88                 I_to_NDS_nocopy(x, ,len=,x_LSDptr=,cl_false,); // DS zu x bilden.
  89                 if (k >= (uintC)(~(uintC)len)) // kann len+k+1 Überlauf geben?
  90                         { cl_ash_error(y); } // ja -> Fehler
  91                 num_stack_alloc_1(len+k,,LSDptr=);
  92                 LSDptr = clear_loop_lsp(LSDptr,k); // k Nulldigits
  93                 var uintD* MSDptr = copy_loop_lsp(x_LSDptr,LSDptr,len);
  94                 // Nun ist MSDptr/len/LSDptr die DS zu x.
  95                 // Oberhalb von ihr liegen k Nulldigits, unterhalb ist 1 Digit Platz.
  96                 // MSDptr/len+k/.. ist jetzt die Gesamt-DS.
  97                 // Noch um i Bits nach links schieben:
  98                 if (!(i==0)) // Bei i>0
  99                   { // noch ein weiteres Digit dazunehmen (Vorzeichen)
 100                     {var uintD sign = sign_of_sintD(mspref(MSDptr,0));
 101                      lsprefnext(MSDptr) = sign;
 102                      len++;
 103                     }
 104                     // Schiebeschleife: die unteren len Digits um i Bits schieben
 105                     if (i==1)
 106                       { shift1left_loop_lsp(LSDptr,len); }
 107                     else
 108                       { shiftleft_loop_lsp(LSDptr,len,i,0); }
 109                   }
 110                 return DS_to_I(MSDptr,len+k);
 111         } else {
 112                 // y<0
 113                 var uintL i; // i = (-y) mod intDsize, >=0, <intDsize
 114                 var cl_uint k; // k = (-y) div intDsize, >=0, <2^intCsize
 115                 if (bignump(y)) {
 116                         #if (log2_intDsize+intCsize <= cl_value_len-1)
 117                         // -y-1 >= 2^(cl_value_len-1) >= intDsize*2^intCsize
 118                         goto sign;
 119                         #else
 120                         // -y-1 >= 2^(cl_value_len-1)
 121                         // usable only if -y-1 < intDsize*2^intCsize
 122                         // We write -y-1 = lognot(y) = k*intDsize+i and then add 1.
 123                         var cl_heap_bignum* bn = TheBignum(y);
 124                         var uintC len = bn->length;
 125                         if (len > ceiling(log2_intDsize+intCsize+1,intDsize))
 126                                 goto sign;
 127                         // bn_minlength <= len <= ceiling(log2_intDsize+intCsize+1,intDsize).
 128                         if (bn_minlength == ceiling(log2_intDsize+intCsize+1,intDsize)
 129                             || len == ceiling(log2_intDsize+intCsize+1,intDsize))
 130                                 if (mspref(arrayMSDptr(bn->data,len),0) < (uintD)(-bit((log2_intDsize+intCsize)%intDsize)))
 131                                         goto sign;
 132                         #if (log2_intDsize+intCsize > intDsize)
 133                         #define IF_LENGTH(i)  \
 134                           if (bn_minlength <= i && i <= ceiling(log2_intDsize+intCsize+1,intDsize) && (i == ceiling(log2_intDsize+intCsize+1,intDsize) || len == i))
 135                         IF_LENGTH(1)
 136                                 k = 0;
 137                         else IF_LENGTH(2)
 138                                 k = ~get_sint1D_Dptr(arrayLSDptr(bn->data,2) lspop 1);
 139                         else IF_LENGTH(3)
 140                                 k = ~get_sint2D_Dptr(arrayLSDptr(bn->data,3) lspop 1);
 141                         else IF_LENGTH(4)
 142                                 k = ~get_sint3D_Dptr(arrayLSDptr(bn->data,4) lspop 1);
 143                         else IF_LENGTH(5)
 144                                 k = ~get_sint4D_Dptr(arrayLSDptr(bn->data,5) lspop 1);
 145                         else
 146                                 cl_abort();
 147                         #undef IF_LENGTH
 148                         k = k << (intDsize-log2_intDsize);
 149                         #else
 150                         // log2_intDsize+intCsize <= intDsize,
 151                         // implies len==1 or len==2 && lspref(arrayLSDptr(bn->data,len),1) == ~0.
 152                         k = 0;
 153                         #endif
 154                         k |= (uintD)(~lspref(arrayLSDptr(bn->data,len),0)) >> log2_intDsize;
 155                         i = (uintD)(-lspref(arrayLSDptr(bn->data,len),0)) % intDsize;
 156                         if (i == 0)
 157                                 if (++k == 0)
 158                                         goto sign;
 159                         #endif
 160                 } else {
 161                         var uintV y_ = -FN_to_V(y); // Wert von -y, >0, <intDsize*2^intCsize
 162                         i = y_%intDsize;
 163                         k = floor(y_,intDsize);
 164                 }
 165                 // DS zu x bilden:
 166                 var uintD* MSDptr;
 167                 var uintC len;
 168                 I_to_NDS(x, MSDptr=,len=,); // DS zu x bilden.
 169                 if (k>=len) goto sign; // -y >= intDsize*len -> Vorzeichen von x zurück
 170                 len -= k; // rechte k Digits einfach streichen
 171                 // Noch ist len>0. Um i Bits nach rechts schieben:
 172                 if (!(i==0)) // Bei i>0:
 173                   { // Schiebe len Digits ab MSDptr um i Bits nach rechts:
 174                     if (i==1)
 175                       { shift1right_loop_msp(MSDptr,len,sign_of_sintD(mspref(MSDptr,0))); }
 176                       else
 177                       { shiftrightsigned_loop_msp(MSDptr,len,i); }
 178                   }
 179                 return DS_to_I(MSDptr,len);
 180         }
 181 sign:   // Ergebnis ist 0, falls x>=0, und -1, falls x<0:
 182         return (minusp(x) ? cl_I(-1) : cl_I(0));
 183 }
 184
 185 }  // namespace cln