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 \r
  14 namespace cln {\r
  15 \r
  16 const cl_I digits_to_I (const char * MSBptr, uintL len, uintD base)\r
  17 {\r
  18       CL_ALLOCA_STACK;\r
  19       var uintD* erg_MSDptr;\r
  20       var uintC erg_len;\r
  21       var uintD* erg_LSDptr;\r
  22       if ((base & (base-1)) == 0) {\r
  23         // Fast path for powers of two: write the digits from least\r
  24         // significant to most significant into the result NUDS.\r
  25         var int b = (base==2 ? 1 : base==4 ? 2 : base==8 ? 3 : base==16 ? 4 : /*base==32*/ 5);\r
  26         num_stack_alloc(1+(len*b)/intDsize,,erg_LSDptr=);\r
  27         erg_MSDptr = erg_LSDptr; erg_len = 0;\r
  28         var uintD d = 0;  // resulting digit\r
  29         var int ch_where = 0;  // position of ch inside d\r
  30         while (len > 0)\r
  31           { var uintB ch = *(const uintB *)(MSBptr+len-1); // next character\r
  32             if (!(ch=='.')) // skip decimal point\r
  33               { // Compute value of ch ('0'-'9','A'-'Z','a'-'z'):\r
  34                 ch = ch - '0';\r
  35                 if (ch > '9'-'0') // not a digit?\r
  36                   { ch = ch+'0'-'A'+10;\r
  37                     if (ch > 'Z'-'A'+10) // not an uppercase letter?\r
  38                       { ch = ch+'A'-'a'; } // must be lowercase!\r
  39                   }\r
  40                 d = d | (uintD)ch<<ch_where;\r
  41                 ch_where = ch_where+b;\r
  42                 if (ch_where >= intDsize) {\r
  43                   // d is ready to be written into the NUDS:\r
  44                   lsprefnext(erg_MSDptr) = d;\r
  45                   ch_where = ch_where-intDsize;\r
  46                   d = (uintD)ch >> b-ch_where;  // carry\r
  47                   erg_len++;\r
  48                 }\r
  49               }\r
  50             len--;\r
  51           }\r
  52         if (d != 0) {  // is there anything left over?\r
  53           lsprefnext(erg_MSDptr) = d;\r
  54           ++erg_len;\r
  55         }\r
  56       } else {\r
  57         // Slow path: Add digits one by one for non-powers of two.\r
  58         // Platz fürs Ergebnis:\r
  59         // 1+ceiling(len*log(base)/(intDsize*log(2))) or some more digits\r
  60         var uintL need = 1+floor(len,intDsize*256); // > len/(intDsize*256) >=0\r
  61         switch (base) // multiply need with ceiling(256*log(base)/log(2)):\r
  62           {\r
  63           //case 2: need = 256*need; break;\r
  64             case 3: need = 406*need; break;\r
  65           //case 4: need = 512*need; break;\r
  66             case 5: need = 595*need; break;\r
  67             case 6: need = 662*need; break;\r
  68             case 7: need = 719*need; break;\r
  69           //case 8: need = 768*need; break;\r
  70             case 9: need = 812*need; break;\r
  71             case 10: need = 851*need; break;\r
  72             case 11: need = 886*need; break;\r
  73             case 12: need = 918*need; break;\r
  74             case 13: need = 948*need; break;\r
  75             case 14: need = 975*need; break;\r
  76             case 15: need = 1001*need; break;\r
  77           //case 16: need = 1024*need; break;\r
  78             case 17: need = 1047*need; break;\r
  79             case 18: need = 1068*need; break;\r
  80             case 19: need = 1088*need; break;\r
  81             case 20: need = 1107*need; break;\r
  82             case 21: need = 1125*need; break;\r
  83             case 22: need = 1142*need; break;\r
  84             case 23: need = 1159*need; break;\r
  85             case 24: need = 1174*need; break;\r
  86             case 25: need = 1189*need; break;\r
  87             case 26: need = 1204*need; break;\r
  88             case 27: need = 1218*need; break;\r
  89             case 28: need = 1231*need; break;\r
  90             case 29: need = 1244*need; break;\r
  91             case 30: need = 1257*need; break;\r
  92             case 31: need = 1269*need; break;\r
  93           //case 32: need = 1280*need; break;\r
  94             case 33: need = 1292*need; break;\r
  95             case 34: need = 1303*need; break;\r
  96             case 35: need = 1314*need; break;\r
  97             case 36: need = 1324*need; break;\r
  98             default: NOTREACHED\r
  99           }\r
 100         // Now we have need >= len*log(base)/(intDsize*log(2)).\r
 101         need += 1;\r
 102         // Add digits one by one:\r
 103         num_stack_alloc(need,,erg_LSDptr=);\r
 104         erg_MSDptr = erg_LSDptr; erg_len = 0;\r
 105         while (len > 0)\r
 106           { // erg_MSDptr/erg_len/erg_LSDptr is a NUDS, erg_len < need.\r
 107             var uintB ch = *(const uintB *)MSBptr; MSBptr++; // next character\r
 108             if (!(ch=='.')) // skip decimal point\r
 109               { // Compute value of ('0'-'9','A'-'Z','a'-'z'):\r
 110                 ch = ch - '0';\r
 111                 if (ch > '9'-'0') // not a digit?\r
 112                   { ch = ch+'0'-'A'+10;\r
 113                     if (ch > 'Z'-'A'+10) // not an uppercase letter?\r
 114                       { ch = ch+'A'-'a'; } // must be lowercase!\r
 115                   }\r
 116                 // multiply erg with base and add ch:\r
 117                {var uintD carry = mulusmall_loop_lsp(base,erg_LSDptr,erg_len,ch);\r
 118                 if (!(carry==0))\r
 119                   // need to extend NUDS:\r
 120                   { lsprefnext(erg_MSDptr) = carry; erg_len++; }\r
 121               }}\r
 122             len--;\r
 123           }\r
 124       }\r
 125       return NUDS_to_I(erg_MSDptr,erg_len);\r
 126 }\r
 127 \r
 128 }  // namespace cln\r