src/integer/conv/cl_I_from_digits.cc

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