herm1t LIVE!ng room - Энтропия в целых числах [entries|archive|friends|userinfo]
herm1t

[ website | twilight corner in the herm1t's cave ]
[ userinfo | ljr userinfo ]
[ archive | journal archive ]

Энтропия в целых числах [Aug. 22nd, 2011|12:30 pm]
Previous Entry Add to Memories Tell A Friend Next Entry
[Tags|, ]
[Current Mood |accomplished]

Захотелось посчитать энтропию в целых числах (без существенной потери точности), получилось вот так:
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);
}
LinkLeave a comment

Comments:
From:(Anonymous)
Date:August 22nd, 2011 - 11:38 am
(Link)
это таки энтропия по Шеннону получается?
[User Picture]
From:[info]herm1t
Date:August 22nd, 2011 - 11:41 am
(Link)
да.
From:(Anonymous)
Date:August 22nd, 2011 - 11:44 am
(Link)
а кому она нужна практически?
btw ав её меряют или настоящую энтропию как-то оценивают?
[User Picture]
From:[info]herm1t
Date:August 22nd, 2011 - 11:49 am
(Link)
да, это один из самых простых способов детектирования сжатия/крипто.
а подсчет в целых числах - баловство, конечно же.
[User Picture]
From:[info]steinkrauz
Date:August 22nd, 2011 - 01:35 pm
(Link)
Offtop:

а чем Вы исходники раскрашивали?
[User Picture]
From:[info]herm1t
Date:August 22nd, 2011 - 01:43 pm
(Link)
нашел первый попавшийся сайт tohtml.com, есть еще pastebin.com или можно, что-нибудь локально поставить, у меня стоит geshi, в этот раз просто забыл про pastebin, а geshi запускать поленился. :-)
[User Picture]
From:[info]steinkrauz
Date:August 22nd, 2011 - 01:46 pm
(Link)
Спасибо!
From:(Anonymous)
Date:May 14th, 2013 - 03:02 pm
(Link)
Спасибо, пригодилось.
[User Picture]
From:[info]herm1t
Date:May 14th, 2013 - 03:04 pm
(Link)
здорово. :-) понижаете?