# 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; }