src/integer/conv/cl_I_from_digits.cc

   1 // digits_to_I().
   2
   3 // General includes.
   4 #include "base/cl_sysdep.h"
   5
   6 // Specification.
   7 #include "integer/cl_I.h"
   8
   9
  10 // Implementation.
  11
  12 #include "base/digitseq/cl_DS.h"
  13 #include "integer/conv/cl_I_cached_power.h"
  14
  15 namespace cln {
  16
  17 static const cl_I digits_to_I_base2 (const char * MSBptr, uintC len, uintD base)
  18 {
  19         // base is a power of two: write the digits from least significant
  20         // to most significant into the result NUDS. Result needs
  21         // 1+ceiling(len*log(base)/(intDsize*log(2))) or some more digits.
  22         CL_ALLOCA_STACK;
  23         var uintD* erg_MSDptr;
  24         var uintC erg_len;
  25         var uintD* erg_LSDptr;
  26         var int b = (base==2 ? 1 : base==4 ? 2 : base==8 ? 3 : base==16 ? 4 : /*base==32*/ 5);
  27         num_stack_alloc(1+(len*b)/intDsize,,erg_LSDptr=);
  28         erg_MSDptr = erg_LSDptr; erg_len = 0;
  29         var uintD d = 0;  // resulting digit
  30         var int ch_where = 0;  // position of ch inside d
  31         var uintC min_len = 0;  // first non-zero digit
  32         while (min_len < len && *(const uintB *)(MSBptr+min_len) == '0') {
  33             ++min_len;
  34         }
  35         while (len > min_len) {
  36                 var uintB ch = *(const uintB *)(MSBptr+len-1); // next character
  37                 if (ch!='.') { // skip decimal point
  38                         // Compute value of ch ('0'-'9','A'-'Z','a'-'z'):
  39                         ch = ch - '0';
  40                         if (ch > '9'-'0') { // not a digit?
  41                                 ch = ch+'0'-'A'+10;
  42                                 if (ch > 'Z'-'A'+10) {// not an uppercase letter?
  43                                         ch = ch+'A'-'a'; // must be lowercase!
  44                                 }
  45                         }
  46                         d = d | (uintD)ch<<ch_where;
  47                         ch_where = ch_where+b;
  48                         if (ch_where >= intDsize) {
  49                             // d is ready to be written into the NUDS:
  50                             lsprefnext(erg_MSDptr) = d;
  51                             ch_where = ch_where-intDsize;
  52                             d = (uintD)ch >> b-ch_where;  // carry
  53                             erg_len++;
  54                         }
  55                 }
  56                 len--;
  57         }
  58         if (d != 0) {  // is there anything left over?
  59                 lsprefnext(erg_MSDptr) = d;
  60                 ++erg_len;
  61         }
  62         return NUDS_to_I(erg_MSDptr,erg_len);
  63 }
  64
  65 static const cl_I digits_to_I_baseN (const char * MSBptr, uintC len, uintD base)
  66 {
  67         // base is not a power of two: Add digits one by one. Result needs
  68         // 1+ceiling(len*log(base)/(intDsize*log(2))) or some more digits.
  69         CL_ALLOCA_STACK;
  70         var uintD* erg_MSDptr;
  71         var uintC erg_len;
  72         var uintD* erg_LSDptr;
  73         var uintC need = 1+floor(len,intDsize*256); // > len/(intDsize*256) >=0
  74         switch (base) { // multiply need with ceiling(256*log(base)/log(2)):
  75                 case 2: need = 256*need; break;
  76                 case 3: need = 406*need; break;
  77                 case 4: need = 512*need; break;
  78                 case 5: need = 595*need; break;
  79                 case 6: need = 662*need; break;
  80                 case 7: need = 719*need; break;
  81                 case 8: need = 768*need; break;
  82                 case 9: need = 812*need; break;
  83                 case 10: need = 851*need; break;
  84                 case 11: need = 886*need; break;
  85                 case 12: need = 918*need; break;
  86                 case 13: need = 948*need; break;
  87                 case 14: need = 975*need; break;
  88                 case 15: need = 1001*need; break;
  89                 case 16: need = 1024*need; break;
  90                 case 17: need = 1047*need; break;
  91                 case 18: need = 1068*need; break;
  92                 case 19: need = 1088*need; break;
  93                 case 20: need = 1107*need; break;
  94                 case 21: need = 1125*need; break;
  95                 case 22: need = 1142*need; break;
  96                 case 23: need = 1159*need; break;
  97                 case 24: need = 1174*need; break;
  98                 case 25: need = 1189*need; break;
  99                 case 26: need = 1204*need; break;
 100                 case 27: need = 1218*need; break;
 101                 case 28: need = 1231*need; break;
 102                 case 29: need = 1244*need; break;
 103                 case 30: need = 1257*need; break;
 104                 case 31: need = 1269*need; break;
 105                 case 32: need = 1280*need; break;
 106                 case 33: need = 1292*need; break;
 107                 case 34: need = 1303*need; break;
 108                 case 35: need = 1314*need; break;
 109                 case 36: need = 1324*need; break;
 110                 default: NOTREACHED
 111         }
 112         // Now we have need >= len*log(base)/(intDsize*log(2)).
 113         need += 1;
 114         // Add digits one by one:
 115         num_stack_alloc(need,,erg_LSDptr=);
 116         // erg_MSDptr/erg_len/erg_LSDptr is a NUDS, erg_len < need.
 117         erg_MSDptr = erg_LSDptr; erg_len = 0;
 118         while (len > 0) {
 119                 var uintD newdigit = 0;
 120                 var uintC chx = 0;
 121                 var uintD factor = 1;
 122                 while (chx < power_table[base-2].k && len > 0) {
 123                         var uintB ch = *(const uintB *)MSBptr; MSBptr++; // next character
 124                         // Compute value of ('0'-'9','A'-'Z','a'-'z'):
 125                         ch = ch-'0';
 126                         if (ch > '9'-'0') { // not a digit?
 127                                 ch = ch+'0'-'A'+10;
 128                                 if (ch > 'Z'-'A'+10) {// not an uppercase letter?
 129                                         ch = ch+'A'-'a';  // must be lowercase!
 130                                 }
 131                         }
 132                         factor = factor*base;
 133                         newdigit = base*newdigit+ch;
 134                         chx++;
 135                         len--;
 136                 }
 137                 var uintD carry = mulusmall_loop_lsp(factor,erg_LSDptr,erg_len,newdigit);
 138                 if (carry!=0) {
 139                         // need to extend NUDS:
 140                         lsprefnext(erg_MSDptr) = carry;
 141                         erg_len++;
 142                 }
 143         }
 144         return NUDS_to_I(erg_MSDptr,erg_len);
 145 }
 146
 147 static const cl_I digits_to_I_divconq (const char * MSBptr, uintC len, uintD base)
 148 {
 149         // This is quite insensitive to the breakeven point.
 150         // On a 1GHz Athlon I get approximately:
 151         //   base  3: breakeven around 25000
 152         //   base 10: breakeven around  8000
 153         //   base 36: breakeven around  2000
 154         if (len>80000/base) {
 155                 // Divide-and-conquer:
 156                 // Find largest i such that B = base^(k*2^i) satisfies B <= X.
 157                 var const cached_power_table_entry * p;
 158                 var uintC len_B = power_table[base-2].k;
 159                 for (uintC i = 0; ; i++) {
 160                         p = cached_power(base, i);
 161                         if (2*len_B >= len)
 162                                 break;
 163                         len_B = len_B*2;
 164                 }
 165                         return digits_to_I_divconq(MSBptr,len-len_B,base) * p->base_pow
 166                              + digits_to_I_divconq(MSBptr+len-len_B,len_B,base);
 167         } else {
 168                 return digits_to_I_baseN(MSBptr, len, base);
 169         }
 170 }
 171
 172 const cl_I digits_to_I (const char * MSBptr, uintC len, uintD base)
 173 {
 174         if ((base & (base-1)) == 0) {
 175                 return digits_to_I_base2(MSBptr, len, base);
 176         } else {
 177                 // digits_to_I_divconq cannot handle decimal points, so remove it here
 178                 CL_ALLOCA_STACK;
 179                 const uintD * digits_copy;
 180                 num_stack_alloc(len,,digits_copy=);
 181                 char * copy_ptr = (char *)digits_copy;
 182                 uintC n = 0;
 183                 for (uintC i = 0; i < len; ++i) {
 184                         const char ch = MSBptr[i];
 185                         if (ch != '.') { // skip decimal point
 186                                 copy_ptr[n] = ch;
 187                                 n++;
 188                         }
 189                 }
 190                 return digits_to_I_divconq((const char*)digits_copy, n, base);
 191         }
 192 }
 193
 194 }  // namespace cln