src/integer/conv/cl_I_from_digits.cc

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