# btrIn.rb
=begin
This Ruby program reads a Boolean transformation in a [ ]-
representation [f1,f2,...,fn] from the console and creates a file
of a tree decomposition of each coordinate function fi.
The program asks for a file name to be created, the dimension n,
property (circular, skew-circular, or general), and then each
Boolean function fi (only f1, if circular or skew-circular).
Each Boolean function fi should be entered like
1*2*(-3vs2(4,-5,6))*(-7v-9),
where a positive integer i denotes the projection function pi,
a negative integer -i denotes ~pi, * denotes AND, v denotes OR,
and s2(4,-5,6) is the symmetric function of 2-products of
the three functions p4, ~p5, and p6.
=end
class Bstring
#Class of string expressions of Boolean functions
def initialize(str)
#Removes the outermost parentheses if possible.
t_str = str
if (t_str[0,1] == "(") and (t_str[t_str.length-1,1] == ")")
t_str = t_str.chop
t_str = t_str.sub(/\(/, "")
countP = 0
for i in 0..(t_str.length-1)
if t_str[i,1] == "("
countP += 1
else
if t_str[i,1] == ")"
countP -= 1
end
end
if countP < 0
t_str = "(" + t_str + ")"
break
end
end
end
@str = t_str
end
def split(regx)
=begin
splits a string into two parts by the first preference of regx
considering the priority of parentheses. Returns the array of
[regx, first, second] or nil.
=end
first = ""
second = @str
sw = nil
while second
if (second =~ regx)
first = first + $`
second = $'
if (first.count "(") == (first.count ")")
sw = "Match"
break
else
first = first + $&
end
else
break
end
end
if sw == "Match"
[$&, first, second]
else
nil
end
end
def binaryOp
=begin
Sprits a string by "v" and returns the array of a binary operation
["v", operand1, operand2]; if not possible, splits the string
by "*" and returns ["*", operand1, operand2]. If no splitting is
possible, returns ["u", operand].
=end
if s = split(/v/)
return s
else
if s = split(/\*/)
return s
else
["u", @str]
end
end
end
def bTree
#Returns a tree decomposition of a Boolean function
tree = [[]]
level = 0
tree[level][0] = binaryOp
while tree[level].length > 0
i = -1
j = -1
tree[level+1] = []
tree[level].each do |term|
i += 1
if term[0] != "u"
j += 1
tree[level+1][j] = Bstring.new(term[1]).binaryOp
tree[level+1][j][3] = i
tree[level+1][j][4] = 0
j += 1
tree[level+1][j]= Bstring.new(term[2]).binaryOp
tree[level+1][j][3] = i
tree[level+1][j][4] = 1
end
end
level += 1
end
tree[0][0][3] = level
return tree
end
end
#Main program starts here
puts "Enter a file name"
fname = gets
bfile = File.new(fname.chomp, "w")
puts "Enter the dimension"
line = gets
dim = line.chomp.to_i
property = nil
puts "Circular, Skew-circular, or General? c or s or g?"
while property != "c" and property != "s" and property != "g"
line = gets
property = line.chomp
end
bfile.print dim, " ", property, "\n"
#Prints the dimension and property in the first line
print dim, " ", property, "\n"
1.upto(dim) do |count|
if count == 1 or property == "g"
print "Enter a Boolean function ", count, "\n"
line = gets
str0 = Bstring.new(line.chomp)
level = str0.bTree[0][0][3]
bfile.print level, "\n"
#Prints the number of tree levels in the second line
0.upto(level-1) do |i|
str0.bTree[i].each do|j|
print j[0]," ",j[1]," ",j[2]," ",j[3]," ",j[4],"\t"
end
print "\n"
end
0.upto(level-1) do |i|
str0.bTree[i].each do|j|
bfile.print j[0]," ",j[1]," ",j[2]," ",j[3]," ",j[4],"\t"
end
bfile.print "\n"
end
end
end
bfile.close
#btrMap.rb
=begin
This Ruby program reads a file of a tree decomposition of a Boolean Transformation F
created by btrIn.rb and outputs a file of the transformation table.
The name of the output file is the name of the input file + the extension .map.
If the dimension is n, then 2^n values of the funtion F are written following the
dimension n. The xth integer y, 0 <= x <= 2^n -1 is the value F(x), where y is also
an integer. If y = F(x) then -1 is written for y. The corresponding n-arrays of
the Boolean points x and y in Q^n are respectively i_to_B(n, x) and i_to_B(n, y).
=end
class Bool < Array
# Boolean array
def c
# Returns the comlement a Boolean array.
com = []
1.upto(self.length-1) do |i|
com[i] = -self[i] + 1
end
return com
end
end
def i_to_B(dim, x)
# Converts an integer to a Boolean array
b = Bool.new
1.upto(dim) do |i|
b[i] = x%2
x /= 2
end
return b
end
def inputTree(dim, property, f_obj, coord)
#Reads a Boolean function tree in string format from the file f_obj
#Returns a Boolean function tree in numerical format.
#Coordinate numbers are convrted to numerical values.
#If property is "c" (circular) or "s" (skew-circular),
#the coordinate numbers are further converted for coord > 1.
bfile = f_obj
ftree = []
lev_num = (bfile.gets).chomp.to_i
0.upto(lev_num-1) do |level|
ftree[level] = []
line = bfile.gets
lev_op = line.chomp.split(/\t/)
0.upto(lev_op.length-1) do |i|
ftree[level][i] = []
b_op = lev_op[i].split(/\s/)
for j in 0..2
ftree[level][i][j] = b_op[j]
end
for j in 3..4
ftree[level][i][j] = b_op[j].to_i
end
if b_op[0] == "u"
term = b_op[1]
ftree[level][i][1] = term.to_i
if ftree[level][i][1] == 0
term = term.sub(/s/, "")
term = term.sub(/\(/, ",")
term = term.sub(/\)/, "")
b_op[2] = term.split(/,\s*/)
ftree[level][i][2] = []
0.upto(b_op[2].length - 1) do |k|
ftree[level][i][2][k] = b_op[2][k].to_i
end
end
if property != "g"
term = ftree[level][i]
if term[1] > 0
term[1] = (term[1]+coord-2)%dim + 1
else
if term[1] < 0
term[1] = -((-term[1]+coord-2)%dim + 1)
else
1.upto(term[2].length - 1) do |k|
if term[2][k] > 0
term[2][k] = (term[2][k]+coord-2)%dim + 1
else
term[2][k] = -((-term[2][k]+coord-2)%dim + 1)
end
if property == "s"
for j in 1..(coord-1)
if term[2][k].abs == j
term[2][k] = -term[2][k]
end
end
end
end
end
end
if property == "s"
for j in 1..(coord-1)
if term[1].abs == j
term[1] = -term[1]
end
end
end
end
end
end
end
ftree[0][0][3] = lev_num
return ftree
end
def bAlgebra(op, arg1, arg2)
#Returns the Boolean operation arg1 op arg2
if op == "*"
return arg1 & arg2
else
return arg1 | arg2
end
end
def valueComp(ftree, x_point)
#Returns the value f(x_point) of the Boolean function f represented by ftree
#and the Boolean point x_point represented by a Boolean array.
value = nil
(ftree[0][0][3]-1).downto(0) do |level|
ftree[level].each do |term|
if term[0] == "u"
if term[1] > 0
value = x_point[term[1]]
else
if term[1] < 0
value = -x_point[-term[1]] + 1
else
value = 0
count = 0
1.upto(term[2].length - 1) do |i|
if term[2][i] > 0
count += x_point[term[2][i]]
else
count = count - x_point[-term[2][i]] + 1
end
if count == term[2][0]
value = 1
break
end
end
end
end
else
value = bAlgebra(term[0], term[1], term[2])
end
if level == 0 then return value
else
ftree[level-1][term[3]][1 + term[4]] = value
end
end
end
end
def bTr(b_func, dim, x)
#Returns F(x) of the Boolean Transformation F =[f1,...fn], where each fi is defined by b_func[i]
y = 0
x_point = i_to_B(dim, x)
dim.downto(1) do |i|
if x_point[i] == 1
value = valueComp(b_func[i], x_point)
else
value = valueComp(b_func[i], x_point.c)
end
y <<= 1
y |= (x_point[i] + value) & 1
end
return y
end
#Main program starts here
puts "Enter a file name"
fname = gets
fname = fname.chomp
bfile = File.new(fname, "r")
line = bfile.gets
dim, property = line.chomp.split(/\s+/)
dim = dim.to_i
b_func = []
if property == "g"
1.upto(dim) do |coord|
b_func[coord] = inputTree(dim, property, bfile, coord)
end
bfile.close
else
1.upto(dim) do |coord|
b_func[coord] = inputTree(dim, property, bfile, coord)
bfile.close
if coord != dim
bfile = File.new(fname.chomp, "r")
line = bfile.gets
end
end
end
# print Boolean function trees
1.upto(dim) do |i|
0.upto(b_func[i][0][0][3]-1) do |level|
b_func[i][level].each do |j|
print j[0], " ", j[1], " ", j[2], " ", j[3], " ", j[4], "\t"
end
print "\n"
end
end
puts "Mapping"
print Time.now.to_s, "\n"
fname = fname + ".map"
mapfile = File.new(fname, "w")
mapfile.print dim, "\n"
0.upto(2**dim - 1) do |x|
y = bTr(b_func, dim, x)
if y == x
mapfile.print -1, "\n"
else
mapfile.print y, "\n"
end
end
mapfile.close
print Time.now.to_s, "\n"
/*orbit.c*/
/*This C program describes the orbits of a Boolean transformation.
The input file is *.map and created by "btrMap.rb" */
#include
#include
#include
#include
void i_to_B( int dim, int x, int *ptr );
int exp( int x, int y );
int s_to_i( char *ptr );
int unsigned ypoint[104858], zpoint[314574];
int cindex[104858];
main()
{
FILE *fptr;
char c, *d, fname[10];
char line [32];
char boolpt[32];
int dim;
int i, j;
int match, sw;
int bvector[32];
int x, y, z, u;
int firstUnmarkedX;
unsigned numP, mark;
int count = 0, ccount = 0, countR;
ReadMapping:
while( 1 )
{
printf( "\n** Type file name.\n" );
fflush( stdin );
gets( fname );
if( fptr = fopen( fname, "r" ) )
break;
else
{
perror( "Read error." );
goto ReadMapping;
}
}
fscanf(fptr, "%d", &dim);
printf( "\nMapping: dim= %d", dim );
numP = exp( 2, dim );
for( x = 0; x <= numP - 1; x++ )
{
fscanf(fptr, "%d", &y);
if ( y < 0 )
ypoint[x] = x;
else
ypoint[x] = y;
}
fclose( fptr);
CalculateOrbits:
printf( "\nCalculate orbits: " );
mark = exp( 2, 31);
count = 0; countR = 1; firstUnmarkedX = 0;
zpoint[0] = mark;
while( 1 )
{
if( zpoint[count] >= mark )
{
match = 0;
for( u = firstUnmarkedX; u <= numP - 1; u++ )
{
if( ypoint[u] < mark )
{
firstUnmarkedX = u;
count++;
zpoint[count] = u; /*First point of a new orbit*/
match = 1;
break;
}
}
if( !match ) /*No unmarked points left*/
break;
}
else
{
while( u <= numP - 1 )
{
count++;
zpoint[count] = ypoint[zpoint[count-1]];
if( ypoint[zpoint[count-1]] < mark )
ypoint[zpoint[count-1]] = mark + countR;
else /*End of orbit, since the point is marked*/
{
countR++;
break;
}
}
}
}
OutputOrbits:
numP = count;
printf( "\nPrint all orbits, y or n? ");
c = getche( );
if ( c == 'n' ) goto PrintOrbits;
PrintAllOrbits:
printf( "\nAll Orbits: " );
count = 0;
zpoint[0] = mark;
c = 'y';
for( u = 1; u <= numP; u++ )
{
if( zpoint[u - 1] >= mark )
{
count++;
if( !(count % 4) )
if( c != 'n' )
{
printf( "\n Print orbits or stop, y, n, or s? ");
c = getche( );
/*Pause. If 'n' is keyed in, Orbits are not printed.
If 's' is keyed in, breaks.*/
}
if( c == 's' )
break;
if( c!= 'n' )
printf( "R%d ", count );
}
if( zpoint[u] >= mark )
{
if( c != 'n' )
printf( "R%d. ", zpoint[u] - mark );
if( (zpoint[u] - mark == count)&&(zpoint[u-1] != zpoint[u-2]) )
{
ccount++;
cindex[ccount] = count;
}
}
else
if( c != 'n' )
{
x = zpoint[u];
i_to_B( dim, x, bvector );
for( j = 1; j <= dim; j++ )
printf( "%d", bvector[j] );
printf( " " );
}
}
PrintCycles:
printf( "\nCycles: " );
count = 0; ccount = 1;
c = 'y';
for( u = 1; u <= numP; u++ )
{
if( zpoint[u - 1] >= mark )
{
count++;
if( count == cindex[ccount] )
if( c != 'n' )
printf( "R%d ", count );
}
if( zpoint[u] >= mark )
{
if( count == cindex[ccount] )
{
if( c != 'n' )
printf( "R%d. ", zpoint[u] - mark );
if( !(ccount % 4) )
if( c != 'n' )
{
printf( "\n Continue? y or n? ");
c = getche( );
/*Pauses. If 'n' is keyed in, Cycles are not printed.*/
}
ccount++;
}
}
else
{
if( count == cindex[ccount] )
if( c != 'n' )
{
i_to_B( dim, zpoint[u], bvector );
for( j = 1; j <= dim; j++ )
printf( "%d", bvector[j] );
printf( " " );
}
}
}
printf( "\nNumber of non-loop cycles = %d.", ccount - 1 );
PrintOrbits:
/*Prints a single orbit with an initial point entered from the
console*/
while( 1 )
{
printf ("\nEnter an initial point or q for quit. " );
fflush( stdin );
gets( boolpt );
d = strstr( boolpt, "q" );
if( d )
break;
if ( strlen( boolpt ) != dim )
continue;
z = s_to_i( boolpt );
sw = 0;
for( u = 1; u <= numP; u++ )
{
if( zpoint[u] == z )
while( 1 )
{
x = zpoint[u];
i_to_B( dim, x, bvector );
for( j = 1; j <= dim; j++ )
printf( "%d", bvector[j] );
printf( " " );
u++;
if( zpoint[u] >= mark )
{
printf( "R%d. ", zpoint[u] - mark );
sw = 1;
break;
}
}
if( sw )
break;
}
}
return 1;
}
int exp( int x, int y )
{
int i;
int z = 1;
for( i = 1; i <= y; i++ )
z *= x;
return z;
}
void i_to_B( int dim, int x, int *ptr )
{
int bit;
for( bit = 0; bit <= dim - 1; bit++ )
{
*(ptr + bit + 1) = x % 2;
x /= 2;
}
}
int s_to_i( char *ptr )
/*Returns the integer expression of a Boolean string*/
{
int bit;
char coord;
int x = 0;
for( bit = 0; bit <= 31; bit++ )
{
coord = *(ptr + bit);
if( coord != '\0' )
x += exp( 2, bit )*(coord - 48);
else
break;
}
return x;
}