Алгоритм Bucket Straw2 в CRU SH Ceph - PullRequest
Новая
       83

Алгоритм Bucket Straw2 в CRU SH Ceph

0 голосов
/ 04 апреля 2020

Я работаю над Straw2 корзиной, используемой в CRU SH алгоритме из Ceph . У меня есть конкретные вопросы c. Код приведен ниже:

Вопросы:

  • Почему необходимо взять log из га sh значение ?
  • Является ли x положением ps , рассчитанным функцией crush_hash32_2 ?
  • Какая функция crush_ln () в данном коде фактически выполняет вычисления? Меня смущает комментарий 2 ^ 44 * log2 (input + 1) .
  • Почему существует необходимость создания отрицательного числа на основе ln (натуральный логарифм) га sh значение? 
u = hash32_3(bucket-> h.hash, x, ids[i], r);  
u &= 0xffff;   
ln = crush_ln(u) - 0x1000000000000ll; 
return div64_s64(ln, weight);
}

/* compute 2^44*log2(input+1) */
static __u64 crush_ln(unsigned int xin)
{
    unsigned int x = xin;
    int iexpon, index1, index2;
    __u64 RH, LH, LL, xl64, result;

    x++;

    /* normalize input */
    iexpon = 15;

    // figure out number of bits we need to shift and
    // do it in one step instead of iteratively
    if (!(x & 0x18000)) {
      int bits = __builtin_clz(x & 0x1FFFF) - 16;
      x <<= bits;
      iexpon = 15 - bits;
    }

    index1 = (x >> 8) << 1;
    /* RH ~ 2^56/index1 */
    RH = __RH_LH_tbl[index1 - 256];
    /* LH ~ 2^48 * log2(index1/256) */
    LH = __RH_LH_tbl[index1 + 1 - 256];

    /* RH*x ~ 2^48 * (2^15 + xf), xf<2^8 */
    xl64 = (__s64)x * RH;
    xl64 >>= 48;

    result = iexpon;
    result <<= (12 + 32);

    index2 = xl64 & 0xff;
    /* LL ~ 2^48*log2(1.0+index2/2^15) */
    LL = __LL_tbl[index2];

    LH = LH + LL;

    LH >>= (48 - 12 - 32);
    result += LH;

    return result;
}  ```
...