Monday, August 22, 2011

Entropy with integers

Recently I've got stuck to code the entropy routine without floating point (without significant loss of precission) here what I ended with:
int mul_lb(uint32_t x, uint32_t a)
{
        uint32_t r = 0, f = 0, n = 0;
        while (x >= 2) {
                f = (f >> 1) | ((x & 1) << 31);
                r++, n++, x >>= 1;
        }
        if (n) {
                if (++n > 16)
                        n = 16;
                f = ((f >> 1) | 0x80000000) >> (32 - n);
                r *= a;
                while (a > 1) {
                        f *= f, f >>= n, a >>= 1;
                        if ((f >> (--n - 1)) >= 2)
                                r += a, f >>= 1;
                }
        }
        return r;
}

void entropy(uint8_t *b, int l)
{
        int i, e = 0;
        uint32_t c[256];
        bzero(c, sizeof(c));
        for (i = 0; i < l; i++)
                c[b[i]]++;
        for (i = 0; i < 256; i++)
                if (c[i] > 1)
                        e -= mul_lb(c[i], c[i]);
        e /= l >> 5;
        e += mul_lb(l, 32);
        if (e > 255)
                e = 255;
        printf("E=%d (%f)\n", e, e / 32.0);
}

2 comments: