diff options
| -rw-r--r-- | misc/Makefile | 7 | ||||
| -rwxr-xr-x | misc/cisco2list | 20 | ||||
| -rw-r--r-- | misc/ips.c | 94 | ||||
| -rwxr-xr-x | misc/stats | 9 |
4 files changed, 130 insertions, 0 deletions
diff --git a/misc/Makefile b/misc/Makefile new file mode 100644 index 0000000..fe0307d --- /dev/null +++ b/misc/Makefile @@ -0,0 +1,7 @@ +all: ips + +ips: ips.c + gcc ips.c -o ips -lm -O2 -Wall + +clean: + rm -f ips diff --git a/misc/cisco2list b/misc/cisco2list new file mode 100755 index 0000000..6f5466f --- /dev/null +++ b/misc/cisco2list @@ -0,0 +1,20 @@ +#!/usr/bin/perl +# +# Convert Cisco routing table listing to list of prefixes +# + +$loc = ($ARGV[0] eq "-l"); # Print only local prefixes + +while (<STDIN>) { + ($loc ? /^[OR]\s/ : /^B\s/) || next; + /^[ORB]( E[12])?\s+(\d+\.\d+\.\d+\.\d+)(\s|\/\d+\s)/ || die "Cannot parse $_"; + $net = $2; + $len = $3; + if ($len =~ /^\s*$/) { + # Magic rule :) + $len = ($net =~ /\.0$/) ? 24 : 32; + } + $len =~ s/^\///; + $net =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/; + printf "%02x%02x%02x%02x/%d\n", $1, $2, $3, $4, $len; +} diff --git a/misc/ips.c b/misc/ips.c new file mode 100644 index 0000000..ec7e673 --- /dev/null +++ b/misc/ips.c @@ -0,0 +1,94 @@ +#include <stdio.h> +#include <math.h> +#include <unistd.h> +#include <stdlib.h> + +int h[65536]; + +/* + * Probability analysis of hashing function: + * + * Let n be number of items and k number of boxes. For uniform distribution + * we get: + * + * Expected value of "item i is in given box": Xi = 1/k + * Expected number of items in given box: a = EX = E(sum Xi) = sum E(Xi) = n/k + * Expected square value: E(X^2) = E((sum Xi)^2) = E((sum_i Xi^2) + (sum_i,j i<>j XiXj)) = + * = sum_i E(Xi^2) + sum_i,j i<>j E(XiXj) = + * = sum_i E(Xi) [Xi is binary] + sum_i,j i<>j E(XiXj) [those are independent] = + * = n/k + n*(n-1)/k^2 + * Variance: var X = E(X^2) - (EX)^2 = n/k + n*(n-1)/k^2 - n^2/k^2 = + * = n/k - n/k^2 = a * (1-1/k) + * Probability of fixed box being zero: Pz = ((k-1)/k)^n = (1-1/k)^n = (1-1/k)^(ak) = + * = ((1-1/k)^k)^a which we can approximate by e^-a. + */ + +unsigned int hf(unsigned int n) +{ +#if 0 + n = (n ^ (n >> 16)) & 0xffff; + n = (n ^ (n << 8)) & 0xffff; +#elif 1 + n = (n >> 16) ^ n; + n = (n ^ (n << 10)) & 0xffff; +#elif 0 + n = (n >> 16) ^ n; + n *= 259309; +#elif 0 + n ^= (n >> 20); + n ^= (n >> 10); + n ^= (n >> 5); +#elif 0 + n = (n * 259309) + ((n >> 16) * 123479); +#else + return random(); +#endif + return n; +} + +int +main(int argc, char **argv) +{ + int cnt=0; + int i; + + int bits = atol(argv[1]); + int z = 1 << bits; + int max = atol(argv[2]); + + while (max--) + { + unsigned int i, e; + if (scanf("%x/%d", &i, &e) != 2) + if (feof(stdin)) + break; + else + fprintf(stderr, "BUGGG\n"); +// i >>= (32-e); +// i |= (i >> e); + cnt++; + h[(hf(i) >> 1*(16 - bits)) & (z-1)]++; + } +// printf(">>> %d addresses\n", cnt); +#if 0 + for(i=0; i<z; i++) + printf("%d\t%d\n", i, h[i]); +#else +{ + int min=cnt, max=0, zer=0; + double delta=0; + double avg = (double) cnt / z; + double exdelta = avg*(1-1/z); + double exzer = exp(-avg); + for(i=0; i<z; i++) { + if (h[i] < min) min=h[i]; + if (h[i] > max) max=h[i]; + delta += (h[i] - avg) * (h[i] - avg); + if (!h[i]) zer++; + } + printf("size=%5d, min=%d, max=%2d, delta=%-7.6g (%-7.6g), avg=%-5.3g, zero=%g%% (%g%%)\n", z, min, max, delta/z, exdelta, avg, zer/(double)z*100, exzer*100); +} +#endif + + return 0; +} diff --git a/misc/stats b/misc/stats new file mode 100755 index 0000000..57920ce --- /dev/null +++ b/misc/stats @@ -0,0 +1,9 @@ +#!/bin/sh + +make ips +echo "Global tables:" +for a in 4 5 6 7 8 9 10 11 12 13 14 15 ; do + ./ips <global $a $((1<<($a+2))) + done +echo "Local tables:" +./ips <local 6 1000 |