int ord2w_dlog()

in src/compression/dlog.c [91:133]

• 39 lines of code
• 12 McCabe index (conditional complexity)

int ord2w_dlog(const felm_t *r, const int *logT, const felm_t *Texp)
{ // Given a generator rho_2 of order 2^w1, input elements r=[x:y] and w1, compute d <- log_{rho_2}r, 
  // where r = [x,y] \equiv [a_k:1] for some k in {1,2,..2^w1-1} or r \equiv [1:0]
  // Output: corresponding digit d in [-2^{w1-1},2^{w1-1}]
    felm_t x, y;
    felm_t sum = {0}, prods[1<<(W_2_1-1)] = {0};

    fpcopy(r[0], x);
    fpcopy(r[1], y);
    fpcorrection(x);
    fpcorrection(y);

    if (is_felm_zero(y)) return 0;
    if (is_felm_zero(x)) return logT[0];
    if (memcmp(x, y, NBITS_TO_NBYTES(NBITS_FIELD)) == 0) return logT[1];
    fpcopy(y, sum);
    fpneg(sum);
    fpcorrection(sum);
    if (memcmp(x, sum, NBITS_TO_NBYTES(NBITS_FIELD)) == 0) return logT[2];    
    for (int j = 2; j < W_2; ++j) {
        for (int i = 0; i < (1<<(j-1)); ++i) {
            if ((i % 2) == 0) 
                fpmul_mont(y, Texp[(1<<(j-2)) + (i/2) - 1], prods[(1<<(j-2)) + (i/2) - 1]);
            fpcopy(y, sum);
            for (int k = 0; k <= j-2; ++k) {
                if (((i>>(j-k-2)) % 2) == 0) 
                    fpadd(sum, prods[(1<<k) + (i >> (j-k-1)) - 1], sum);
                else 
                    fpsub(sum, prods[(1<<k) + (i >> (j-k-1)) - 1], sum);
            }
            fpcorrection(sum);
            if (memcmp(x, sum, NBITS_TO_NBYTES(NBITS_FIELD)) == 0) {
                return logT[(1<<j)+i-1];
            }
            fpneg(sum);
            fpcorrection(sum);
            if (memcmp(x, sum, NBITS_TO_NBYTES(NBITS_FIELD)) == 0) {
                return logT[(1<<(j+1))-i-1-1];
            }
        }
    }
    return 0;
}