Libraries for bc and dc.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 525 lines 17 KiB Raw Permalink Blame History

 `#!/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)` ```} ``` ``` ```