Энтропия в целых числах |
[Aug. 22nd, 2011|12:30 pm] |
[ | 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);
}
|
|
|
Comments: |
From: | (Anonymous) |
Date: | August 22nd, 2011 - 11:38 am |
---|
| | | (Link) |
|
это таки энтропия по Шеннону получается?
![[User Picture]](http://lj.rossia.org/userpic/191927/26445) | From: | herm1t |
Date: | August 22nd, 2011 - 11:41 am |
---|
| | | (Link) |
|
да.
From: | (Anonymous) |
Date: | August 22nd, 2011 - 11:44 am |
---|
| | | (Link) |
|
а кому она нужна практически? btw ав её меряют или настоящую энтропию как-то оценивают?
![[User Picture]](http://lj.rossia.org/userpic/191927/26445) | From: | herm1t |
Date: | August 22nd, 2011 - 11:49 am |
---|
| | | (Link) |
|
да, это один из самых простых способов детектирования сжатия/крипто. а подсчет в целых числах - баловство, конечно же.
Offtop:
а чем Вы исходники раскрашивали?
![[User Picture]](http://lj.rossia.org/userpic/191927/26445) | From: | herm1t |
Date: | August 22nd, 2011 - 01:43 pm |
---|
| | | (Link) |
|
нашел первый попавшийся сайт tohtml.com, есть еще pastebin.com или можно, что-нибудь локально поставить, у меня стоит geshi, в этот раз просто забыл про pastebin, а geshi запускать поленился. :-)
From: | (Anonymous) |
Date: | May 14th, 2013 - 03:02 pm |
---|
| | | (Link) |
|
Спасибо, пригодилось. | |