#!/bin/sh
cat > /dev/null << EOF
One issue RadioGatun has is that it uses triangle numbers to calculate
the rotation amounts. While this works, triangle numbers only have
full coverage (each element in the mill has a different rotation amount,
or each possible rotation amount is used if the mill is bigger than the
word size) when the word size is a power of two.
That in mind, I am looking at other ways to determine the rotation amount
in RadioGatun variants:
1) Determine the rotation amount by adding a relatively prime number.
Simple, works.
2) Determine the rotation constant by multiplying an odd number then
adding another number.
3) Try using NORX-style addition (a ^ b ^ ((a & b) << 1)). Doesn’t
work too well
------
./rotate.amount.sh | grep -v coverage: | grep add | awk '
{print $3","$5","$6}' | perl -pe '
s/x5/a5/;s/x9/b9/;s/x6/c6/;s/x3/d3/;s/x7/e7/;s/x3/f3/;' | sort -n | awk -F, '
{if(!a[$1]){print}a[$1]++}' | tr -d '[a-z]'
EOF
awk 'BEGIN {
a[1] = 1
mill = 19
for(w = 1 ; w <= 64 ; w++) {
r = 0
s = "("
cm = ""
delete a # POSIX: http://austingroupbugs.net/view.php?id=544
# Let’s look at the triangle numbers
for(c = 0 ; c < mill ; c++) {
r = r + c;
a[r % w] = 1;
s = s cm (r%w)
cm = ","
}
s = s ")"
co = 0
for(b in a) {
co++;
}
if(co == w || co == mill) {
print "word size: " w " triangle coverage: " co " " s
}
# Only powers of 2 are any good with triangle numbers, so...
# VARIANT ONE: Add a relatively prime number
# Let’s try adding a relatively prime number
# First, let’s find a relative prime
if(w % 5 != 0) {
m = 5
} else if(w % 3 != 0) {
m = 3
} else if(w % 7 != 0) {
m = 7
} else if(w % 2 != 0) {
m = 2
} else {
m = 11
}
r = 0
s = "("
cm = ""
delete a
for(c = 0 ; c < mill ; c++) {
r+=m
a[r % w] = 1;
s = s cm (r%w)
cm = ","
}
s = s ")"
co = 0
for(b in a) {
co++
}
if(co == w || co == mill) {
print "word size: " w " add " m " coverage: " co " " s
}
#VARIANT TWO: Add a relatively prime number, favoring 7, then XOR it
# The reason for seven is because we already use that number in the mill
# Let’s try adding a relatively prime number
# First, let’s find a relative prime
if(w % 7 != 0) {
m = 7
} else if(w % 3 != 0) {
m = 3
} else if(w % 5 != 0) {
m = 5
} else if(w % 2 != 0) {
m = 2
} else {
m = 11
}
for(x=0;x<=10;x++) {
r = 0
s = "("
cm = ""
delete a
for(c = 0 ; c < mill ; c++) {
if(x < 10) {
r=xor((c*m),x)
} else {
r=xor((c*m),c)
}
a[r % w] = 1;
s = s cm (r%w)
cm = ","
}
s = s ")"
co = 0
for(b in a) {
co++
}
if((co == w || co == mill) && x < 10) {
print "word size: " w " add " m " x"x" coverage " co " " s
} else if(co == w || co == mill) {
print "word size: " w " add " m " xC coverage " co " " s
}
}
# NORX-style addition: c = (a ^ b) ^ ((a & b) << 1)
# Note that, since this code uses bitwise and and xor, it uses non-standard
# bitwise operations. Note also that both GAWK and Busybox AWK support
# these operations.
for(m = 2; m < 10 ; m++) {
r = 0
s = "("
cm = ""
delete a
for(c = 0 ; c < mill ; c++) {
r = xor(r,m,lshift(and(r,m),1))
a[r % w] = 1;
s = s cm (r%w)
cm = ","
}
s = s ")"
co = 0
for(b in a) {
co++
}
if(co == w || co == mill) {
print "word size: " w " NORX " m " coverage: " co " " s
}
}
# Let’s try multiplying by an odd number then adding another number
for(m = 3; m < 10; m+=2) {
for(n = 0; n < 10; n++) {
r = 1
s = "("
cm = ""
delete a
for(c = 0 ; c < mill ; c++) {
r*=m
r+=n
a[r % w] = 1;
s = s cm (r%w)
cm = ","
}
s = s ")"
co = 0
for(b in a) {
co++
}
if(co == w || co == mill) {
print "word size: " w " *" m " +" n " coverage: " co " " s
}
}}
# SHOULD WE ONLY TRY BYTE-SIZE WORDS?
if(w >= 8 && 1 == 2) {
w += 7
}
}
}'