On Monday 2010-10-25 11:13, Jan Engelhardt wrote:
>On Monday 2010-10-25 05:19, Maciej Åenczykowski wrote:
>
>>> To be read as: one OV is reachable by 13 input values; 5 OVs are each
>>> reachable by 12 input values (IV) (i.e. a group of 60 IV lead to only 5
>>> OV), etc.
>>
>>I don't quite follow what you are doing here.
>
>See the code at the end of the mail; that will probably help some
>people more than my description.
/* calculate all possible 32-bit hashes
needs 16G of address space, so better have a 64-bit kernel at hand
*/
#define _GNU_SOURCE 1
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <errno.h>
#include <fcntl.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ARRAY_SIZE(x) (sizeof(x) / sizeof(*(x)))
#define S_IRUGO (S_IRUSR | S_IRGRP | S_IROTH)
#define S_IWUGO (S_IWUSR | S_IWGRP | S_IWOTH)
#define jrot(x,k) (((x) << (k)) | ((x) >> (32 - (k))))
/* jhash_mix - mix 3 32-bit values reversibly. */
#define jhash_mix(a, b, c) { \
a -= c; a ^= jrot(c, 4); c += b; \
b -= a; b ^= jrot(a, 6); a += c; \
c -= b; c ^= jrot(b, 8); b += a; \
a -= c; a ^= jrot(c, 16); c += b; \
b -= a; b ^= jrot(a, 19); a += c; \
c -= b; c ^= jrot(b, 4); b += a; \
}
#define jhash_final(a, b, c) { \
c ^= b; c -= jrot(b, 14); \
a ^= c; a -= jrot(c, 11); \
b ^= a; b -= jrot(a, 25); \
c ^= b; c -= jrot(b, 16); \
a ^= c; a -= jrot(c, 4); \
b ^= a; b -= jrot(a, 14); \
c ^= b; c -= jrot(b, 24); \
}
static uint32_t hash_jlookup3(const void *vkey, size_t length)
{
static const unsigned int JHASH_GOLDEN_RATIO = 0x9e3779b9;
const uint8_t *key = vkey;
uint32_t a, b, c;
a = b = c = JHASH_GOLDEN_RATIO + length;
/* All but the last block: affect some 32 bits of (a,b,c) */
for (; length > 12; length -= 12, key += 12) {
a += key[0] + ((uint32_t)key[1] << 8) +
((uint32_t)key[2] << 16) + ((uint32_t)key[3] << 24);
b += key[4] + ((uint32_t)key[5] << 8) +
((uint32_t)key[6] << 16) + ((uint32_t)key[7] << 24);
c += key[8] + ((uint32_t)key[9] << 8) +
((uint32_t)key[10] << 16)+ ((uint32_t)key[11] << 24);
jhash_mix(a, b, c);
}
switch (length) {
case 12: c += ((uint32_t)key[11]) << 24;
case 11: c += ((uint32_t)key[10]) << 16;
case 10: c += ((uint32_t)key[9]) << 8;
case 9: c += key[8];
case 8: b += ((uint32_t)key[7]) << 24;
case 7: b += ((uint32_t)key[6]) << 16;
case 6: b += ((uint32_t)key[5]) << 8;
case 5: b += key[4];
case 4: a += ((uint32_t)key[3]) << 24;
case 3: a += ((uint32_t)key[2]) << 16;
case 2: a += ((uint32_t)key[1]) << 8;
case 1: a += key[0];
break;
case 0: return c;
}
jhash_final(a,b,c);
return c;
}
static uint32_t hash_djb2(const void *p, size_t z)
{
const char *c = p;
unsigned long v = 5381;
while (*c != '\0')
v = ((v << 5) + v) ^ *c++;
/* v = v * 33 ^ *c++; */
return v;
}
static uint32_t *freq;
static const unsigned long long freq_size = 0x100000000UL * sizeof(*freq);
static void map_freq(void)
{
int fd;
fd = open("jenkins3.frq", O_RDWR | O_CREAT, S_IRUGO | S_IWUGO);
if (fd < 0) {
perror("open");
abort();
}
if (ftruncate(fd, freq_size) < 0) {
perror("ftruncate");
abort();
}
freq = mmap(NULL, freq_size, PROT_READ | PROT_WRITE,
MAP_SHARED, fd, 0);
if (freq == NULL) {
perror("mmap");
abort();
}
}
static void malloc_freq(void)
{
freq = malloc(freq_size);
if (freq == NULL) {
perror("malloc");
abort();
}
}
static inline void calc_all_hashes(void)
{
uint32_t x, y;
memset(freq, 0, freq_size);
for (x = 0; x < UINT32_MAX; ++x) {
if ((x & 0xFFFFF) == 0)
fprintf(stderr, "\r\e[2K""fill: %08x", x);
y = hash_jlookup3(&x, sizeof(x));
if (freq[y] < UINT32_MAX)
++freq[y];
}
}
static void freq_chart(void)
{
uint32_t dist[32];
uint32_t x;
for (x = 0; x < UINT32_MAX; ++x) {
if ((x & 0xFFFFFF) == 0)
fprintf(stderr, "\r\e[2K""%s: %08x", __func__, x);
if (freq[x] >= ARRAY_SIZE(dist))
printf("\nHash %08x reachable by %u input values\n",
x, dist[x]);
if (dist[freq[x]] < UINT32_MAX)
++dist[freq[x]];
}
if (freq[UINT32_MAX] < ARRAY_SIZE(dist) &&
dist[freq[UINT32_MAX]] < UINT16_MAX)
++dist[freq[UINT32_MAX]];
fprintf(stderr, "\n----\n");
for (x = 0; x < ARRAY_SIZE(dist); ++x)
printf("%10ux %u\n", dist[x], x);
}
static void xy_plot(void)
{
uint32_t x, r = 0;
printf("# x y\n");
for (x = 0; x < UINT32_MAX; ++x) {
r += freq[x];
if ((x & 0xFFFFF) == 0)
printf("%u %u\n", x, r);
}
}
int main(int argc, const char **argv)
{
step = (argc >= 2) ? strtoul(argv[1], NULL, 0) : 0;
// map_freq();
malloc_freq();
calc_all_hashes();
if (step == 1)
freq_chart();
else if (step == 2)
xy_plot();
return 0;
}
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
