how does Florian's Grisu2 algorithm work?

Question

I come across a problem about converting double to ascii, after searching, I got Florian's paper "Printing Floating-Point Numbers Quickly and Accurately with Integers", Grisu2 algorithm is really awesome and much faster. I have understood Grisu2's idea but I don't know how to implement it, so I got Florian's C implement, it's a little complicated for me and I still don't really understand 2 functions: cached_power and digit_gen, could anyone who knows Grisu2 help me?

Comments show my question.

    //    cached_power function:

static const uint64_t powers_ten[] = {0xbf29dcaba82fdeae , 0xeef453d6923bd65a,...};  
//how do these numbers precomputed 
static const int powers_ten_e[] = {-1203 , -1200 , -1196 , -1193 , -1190 , ...};//and what do they mean?

static diy_fp_t cached_power(int k) 
{//does this function mean give k and return the normalized 10^k diy_fp_t?
      diy_fp_t res;
      int index = 343 + k;//why add 343?
      res.f = powers_ten[index];
      res.e = powers_ten_e[index];
      return res;
}

this one is more complicated

void digit_gen(diy_fp_t Mp, diy_fp_t delta,//Is Mp normalized?
char* buffer, int* len, int* K) 
{
     uint32_t div; int d, kappa; diy_fp_t one;
     one.f = ((uint64_t)1) << -Mp.e; one.e = Mp.e;//what if Mp.e is positive? what's the purpose of one?
     uint32_t p1 = Mp.f >> -one.e; /// Mp_cut// what does p1 mean?
     uint64_t p2 = Mp.f & (one.f - 1);//what does p2 mean?
     *len = 0; kappa = 3; div = TEN2;//why kappa=3 and div=100? is kappa related to div?
    while (kappa > 0) 
    {    /// Mp_inv1  //what does this loop mean?
         d = p1 / div;
         if (d || *len) buffer[(*len)++] = '0' + d;
         p1 %= div; kappa--; div /= 10;
         if ((((uint64_t)p1) << -one.e) + p2 <= delta.f) 
         { /// Mp_delta
             *K += kappa; return;
         }
    }
    do 
    {  //what does this loop mean?
         p2 *= 10;
         d = p2 >> -one.e;
         if (d || *len) buffer[(*len)++] = '0' + d; /// Mp_inv2
         p2 &= one.f - 1; kappa--; delta.f *= 10;// p2&=one.f-1 means what?
    } while (p2 > delta.f);
    *K += kappa;
}

Answer 1

The first part:

diy_fp_t is a floating point struct with mantisse and exponent as separate members (not very interesting, but it´s here: https://github.com/miloyip/dtoa-benchmark/blob/master/src/grisu/diy_fp.h).

The purpose of cached_power(k) is to compute the value of 10^k and save the result to a diy_fp_t. Because that is neither trivial nor fast for the computer, the author has arrays (one for mantisse, one for exponent) of precalculated values (as good as possible) of the necessary powers (Grisu won´t use other powers than that. An explanation is in the paper, chapter 4 and 5).

The array in the example code begins with the value for 10^(-343), this is 0xbf29dcaba82fdeae * 2^(-1203), = 13774783565108600494 * 2^(-1203). 10^(-342) belongs to the next array position, and so on. And because -343 has the array index [0], 343 is added first.