#!/usr/local/bin/bc -l logic.bc logic_striping.bc ### Logic_Striping_Meta.BC - Analysis of genstripe patterns ## To be used with Logic.BC and Logic_Striping.BC ## Pattern analysis # negative pattern values represent flipped bits # e.g. -1[xyz...] is equivalent to 1[(1-x)(1-y)(1-z)(1-...] # this matches with the definition in rep_stripe_pattern where # 'multiplying' by the integer -1 flips all bits. # Technically this is 1s complement negation, meaning that two zeros would # exist, but in fact an infinite number of zeros exist in the positive-only # patterns: 10, 100, 1000 and these are each stated to be equivalent to their # bit flipped counterparts, so this is not a concern. # Reduces a pattern to the smallest number that will represent it # . Patterns take binary form 1[pattern to repeat] # . e.g. 101 => ...0101010101; 11001 => ...1001100110011001 # . some patterns are equivalent; # . . e.g. 10101 will create the same pattern as 101 # . Given 21 decimal therefore (10101 binary) # . . this function will return 5 (101 binary) define simplify_stripe_pattern(x) { auto os,w,wh,wp,dp,d,r,m,s os=scale;scale=0;x/=1 s=0;if(x<0){s=1;x=-x} if(x==0||x==1){if(s)x=1-x;scale=os;return x} if(x==2||x==3){if(s)x=5-x;scale=os;return x} w = bitwidth(x)-1 wh = w/2;if(wh==0)wh=1 wp = 2^w n = x-wp # trim high/lead bit if(s)n = wp-1-n # flip bits for negative for(dp=d=1;d<=wh;d++){ dp+=dp;r=w/d if(w==r*d){ m=(n*dp)/wp # check if this is a minimal bit pattern to spread #to make the above the same width as wp-1 #we need to repeat it r times #so that's m*(dp^r-1)/(dp-1) if( n*(dp-1) == m*(dp^r-1) ){n = m; break} } } if(d>wh)d=w scale=os;return n+2^d } # Pattern equivalent of raising to a power or multiplying by integer define rep_stripe_pattern(x,p) { auto d,os,s; os=scale;scale=0;x/=1;p/=1 s=0;if(p<0){p=-p;s=!s} if(x<0){x=-x;s=!s} if(x==0||x==1){scale=os;return x} if(p==0){scale=os;return 1} if(p==1&&!s){scale=os;return x} d = 2^(bitwidth(x)-1) if(s){ x=3*d-1-x if(p==1){scale=os;return x} } # negative power flips bits p = d^p x = (x-d)*(p-1)/(d-1)+p scale=os;return x } # Given pattern x, find its length with respect to its simplest form define repsof_stripe_pattern(x) { auto os,w,wh,wp,dp,d,r,m; os=scale;scale=0;x/=1 if(x<0)x=-x # sign doesn't matter here if(x==0||x==1){scale=os;return 0} w = bitwidth(x)-1 wh = w/2;if(wh==0)wh=1 wp = 2^w n = x-wp # trim high/lead bit for(dp=d=1;d<=wh;d++){ dp+=dp;r=w/d if(w==r*d){ m=(n*dp)/wp # check if this is a minimal bit pattern to spread if( n*(dp-1) == m*(dp^r-1) ){d=0;break} } } if(d)r=1 # no minimal found. prime pattern scale=os;return r } # Produce the next matching stripe pattern in a family # e.g. 1[011] -> 1[011][011]; 1[10][10] -> 1[10][10][10] define next_match_stripe_pattern(x) { auto os,w,wh,wp,dp,d,r,m,s os=scale;scale=0;x/=1 s=0;if(x<0){s=1;x=-x} if(x==0||x==1){scale=os;return x} os=scale;scale=0 w = bitwidth(x)-1 wh = w/2;if(wh==0)wh=1 wp = 2^w n = x-wp # trim high/lead bit if(s)n = wp-1-n # flip bits for negative for(dp=d=1;d<=wh;d++){ dp+=dp;r=w/d if(w==r*d){ m=(n*dp)/wp # check if this is a minimal bit pattern to spread if( n*(dp-1) == m*(dp^r-1) ){d=0;break} } } if(d){r=1;dp=wp;m=n} wp=dp^(r+1) n=wp+(m*(wp-1))/(dp-1) scale=os;return n } ## Convert stripe patterns to and from alternative formats # Convert stripe pattern of form 1[xyz...] to 2's complement format of # . [xyz...] if x == 1; # . not([(1-x)(1-y)(1-z)(1-...]) if x == 0 define stripe_pattern_to_2c(x) { auto os,w,s,n,wp; os=scale;scale=0;x/=1 s=0;if(x<0){s=1;x=-x} if(x==0||x==1){scale=os;return x-1} w=bitwidth(x);wp=2^(w-1);n=x-wp#drop lead bit if(s)n=wp-1-n#flip bits if x was negative if(n<2^(w-2))n-=wp scale=os;return n } # Convert stripe pattern of form 1[xyz...] to 1's complement format of # . [xyz...] for x == 1 # . -[(1-x)(1-y)(1-z)(1-...] if x == 0; define stripe_pattern_to_1c(x) { x = stripe_pattern_to_2c(x); if(x<0).=x++ return x } # Inverse of the above define stripe_pattern_from_1c(x) { auto os,w; os=scale;scale=0;x/=1 w=bitwidth(x) if(x>0){scale=os;return x+2^w} scale=os;return 2^(w+1)+x-1 } # Inverse of ..._to_2c define stripe_pattern_from_2c(x) { if(x<=0).=x++ return stripe_pattern_from_1c(x) } ### Advanced Pattern Combination. ### . Multiplication-like methods, Division-like inverses to multiplication ### . Addition / Catenation, Subtraction / Decatenation ## 'Standard' multiplication / division / square root # Pattern multiplication; Largely asymmetrical # . Repeats the pattern of the left hand parameter either as-is # . or bit flipped depending on the bits in the pattern of the # . right hand parameter. # . e.g. 1[pattern] x 1[0110] = # . . 1[0=>flipped pattern][1=>pattern][1=>pattern][0=>flipped pattern] # . e.g. 1[1101] x 1[0110] = 1[0010][1101][1101][0010] # . Note that this is asymmetrical. With params swapped: # . e.g. 1[0110] x 1[1101] = 1[0110][0110][1001][0110] # .......... # . Powers of two in the right parameter correspond to negative integers in # . the right parameter in rep_stripe_pattern(), whereas one less than a power # . of two corresponds to a positive integer in the same place. # . This suggests that patterns may be a strange class of sub-integer or # . perhaps some relative of surreal numbers. # . They are somewhere between bijective unary and binary! # . i.e rep...(x,p[+ve]) <==> mul...(x,2^(p+1)-1) # . and rep...(x,p[-ve]) <==> mul...(x,2^(-p)) # . so p = 3 --> 2^(3+1)-1 = 15 decimal = 1111 binary pattern # . what number would binary pattern 1101 translate back to? # . This multiplication method preserves integers represented in the above way # . and is symmetric for these, suggesting that there is something curious # . about the other patterns. define mul_stripe_patterns(x,y) { auto os,z,bx,by,qx,qz,p[],i,hy; os=scale;scale=0;x/=1;y/=1 if(x==0||y==0){scale=os;return 0} if(x==-1||x==1||y==-1||y==1){scale=os;return 1} qx = 2^(bx = bitwidth(x)-1) by = bitwidth(y)-1 if(x<0)x=3* qx +x-1 # Flip bits of -ve params if(y<0)y=3*(2^by)+y-1 if(x==3){scale=os;return y} # pattern 3 == 1[1] is multiplicative identity! if(y==3){scale=os;return x} # in either param. works even though asymmetric qz = 2^(bx*by) # n.b. pattern 2 == 1[0] works as negative m.i. p[1] = x-qx # in either param. too. p[0] = qx+qx-1-x z=0;for(i=1;i1){ hy=y/2;t=z/qx if(p[y-hy-hy]!=z-t*qx) { # if last bits of z don't match what was found print "div1_stripe_patterns: parameters are incompatible\n" scale=os;return 0 } qy/=2;y=hy;z=t } scale=os;return qx+x } # Attempt to solve z = mul...(x,y) for y define div2_stripe_patterns(z,x){ auto os,y,bz,bx,by,qz,qx,qy,nx,p2,fz,t; os=scale;scale=0;z/=1;x/=1 if(z==0||x==0){scale=os;return 0} if(z==1||z==-1){scale=os;return 1} # 1[] is zero pattern and 0/y = 0 so 1[]/y = 1[] if(x==1||x==-1){ print "div2_stripe_patterns: division by null pattern\n" scale=os;return 0 } bz=bitwidth(z)-1 bx=bitwidth(x)-1 # Check if bz is divisible by 'bx' # Return an error if not by=bz/bx if(by*bx!=bz){ print "div2_stripe_patterns: parameters of incompatible sizes\n" return 0 } qz=(qx=2^bx)*(qy=2^by) if(z<0)z=3* qz +z-1 # Flip bits of -ve params if(x<0)y=3* qx +x-1 x-=qx nx=qx-1-x y=0 for(p2=1;z>1;p2+=p2){ fz=z/qx t=z-fz*qx if(t==x){ y+=p2 } else if(t!=nx) { print "div2_stripe_patterns: parameters are incompatible\n" scale=os;return 0 } z=fz } scale=os;return qy+y } # Attempt to solve z = mul...(x,x) for x define sqrt_stripe_pattern(z){ # Usual preamble auto os,y,bz,bx,qz,qx,hy,p[],t; os=scale;scale=0;z/=1 if(z==0){scale=os;return 0} if(z==1||z==-1){scale=os;return 1} # 1[] is zero pattern and sqrt(0) = 0 so sqrt(1[]) = 1[] bz=bitwidth(z)-1 # Check if bz is a square # Return an error if not bx=sqrt(bz) if(bx*bx!=bz){ print "sqrt_stripe_pattern: parameter does not have square size\n" return 0 } qz=(qx=2^bx);qz*=qx if(z<0)z=3* qz +z-1 # Flip bits of -ve param if(z==3){scale=os;return 3} # 3 => 1[1] is multiplicative id. and so sqrt(1[1]) = 1[1] => 3 if(z+z<=3*qz){ # square root of a "negative" pattern (one that starts 1[0...]) print "sqrt_stripe_pattern: impossible square root\n" return 0 } t=z/qx;x=z-qx*t;z=t # extract bits from RHS of z, and assume these are x y=x;hy=y/2 # set y to x and assign x and !x to associated bits of y p[t=y-hy-hy]=x p[!t]=qx-1-x y=hy while(z>1){ hy=y/2;t=z/qx if(p[y-hy-hy]!=z-t*qx){ print "sqrt_stripe_pattern: parameter has no square root\n" return 0 } z=t;y=hy } # since square root has two possible values (1[pattern] and 1[!pattern]) # set x to the 'positive' / larger of the two options x=p[0];if(x0;t=r){r=gcd%t;gcd=t} x=rep_stripe_pattern(x, by/gcd) y=rep_stripe_pattern(y,t=bx/gcd) bx=by*=t # = bz qx=2^bx } x=xor(x,y) # bits flip incorrectly and q' bit is lost x=qx+qx-1-x # correct the above scale=os;return x } # Inverse of the above; Given a mixed pattern and one of the constituents # . derive the other constituent (up to repeat-equivalence) # . See notes elsewhere how patterns can be equivalent to each other # . in some uses. This is one. define unmix_stripe_patterns(z,x) { auto os,bz,bx,by,qz; os=scale;scale=0;z/=1;x/=1 if(z==0||x==0){scale=os;return 0} if(z==1||z==-1){scale=os;return 1} # 1[] is zero pattern; 0/x=0 if(x==1||x==-1){ print "unmix_stripe_patterns: can't unmix null pattern\n" scale=os;return 0 } bz=bitwidth(z)-1 bx=bitwidth(x)-1 # Check if bz is divisible by 'bx' # Return an error if not by=bz/bx if(by*bx!=bz){ print "unmix_stripe_patterns: parameters of incompatible sizes\n" return 0 } qz=2^bz if(z<0)z=3* qz +z-1 # Flip bits of -ve params #if(x<0)y=3*(2^bx) +x-1# << handled by rep...() below x = rep_stripe_pattern(x,by) # increase x to length of z z = 3*qz-1-z # flip bits of z x = xor(x,z) # nXor (self-inverse) of repeated x and z x += qz # put back missing q' bit; x = simplify_stripe_pattern(x) scale=os;return x } # Modular sum of patterns so that the new length is the LCM of the old lengths # . patterns extended to the same length and then modular arithmetic is done # Is symmetric with respect to x and y, i.e. mix...(x,y) = mix...(y,x) define modsum_stripe_patterns(x,y) { auto os,bx,by,qx,r,gcd,t os=scale;scale=0;x/=1;y/=1 if(x==0||y==0){scale=os;return 0} if(x==1||x==-1||y==-1||y==1){scale=os;return 1} qx = 2^(bx = bitwidth(x)-1) by = bitwidth(y)-1 if(x<0)x=3* qx +x-1 # Flip bits of -ve params if(y<0)y=3*(2^by)+y-1 if(bx!=by){ gcd=bx for(t=by;t>0;t=r){r=gcd%t;gcd=t} x=rep_stripe_pattern(x, by/gcd) y=rep_stripe_pattern(y,t=bx/gcd) bx=by*=t # = bz qx=2^bx } x=x-qx+y-qx # add together modulo qx if(x 1[z]+1[!y] y = 3*qy-y-1 # (re)flip bits .=z-- scale=os;return z*qy+y } # Check if last bits of z are equal to y x = z/qy if(z-x*qy==y-qy){scale=os;return x} # Guess not y = 3*qy-y-1 # (re)flip bits .=z-- scale=os;return z*qy+y } # Overlap cancelling decatenation # . 1[z]-1[y] = 1[a][b]-1[b][c] = 1[a][!c] = 1[x] # . any of a, b or c may be empty # . and b is of maximal size define decat2_stripe_patterns(z,y) { auto os,x,qy,qc,b; os=scale;scale=0;z/=1;y/=1 if(z==0||y==0){scale=os;return 0} qz = 2^(bitwidth(z)-1) qy = 2^(bitwidth(y)-1) if(z<0)z=3* qz +z-1 # Flip bits of -ve params if(y<0)y=3* qy +y-1 if(z==y){scale=os;return 1} # pattern - self = 1[] (catenate identity) if(y==1){scale=os;return z} # pattern - 1[] = self b = y-(qb=qy); qc = 1 # b will contain overlap bits if(qz 1000 + 111 -> 1[0][00] + 1[11][] = 1[0][] = 10 -> -1 # . The standard catenation would have returned 1[000][111] = 1000111 -> ??? define undecat2_stripe_patterns(z,y) { return decat2_stripe_patterns(z,-y) }