1
0
Fork 0
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

#!/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;i<qz;i*=qx){hy=y/2;z+=i*p[y-hy-hy];y=hy}
z+=qz
scale=os;return z
}
# Attempt to solve z = mul...(x,y) for x
define div1_stripe_patterns(z,y){
auto os,x,bz,by,bx,qz,qy,qx,t,p[],hy;
os=scale;scale=0;z/=1;y/=1
if(z==0||y==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
if(y==1||y==-1){
print "div1_stripe_patterns: division by null pattern\n"
scale=os;return 0
}
bz=bitwidth(z)-1
by=bitwidth(y)-1
# Check if bz is divisible by 'by'
# Return an error if not
bx=bz/by
if(bx*by!=bz){
print "div1_stripe_patterns: parameters of incompatible sizes\n"
scale=os;return 0
}
qz=(qy=2^by)*(qx=2^bx)
if(z<0)z=3* qz +z-1 # Flip bits of -ve params
if(y<0)y=3* qy +y-1
if(y==3){scale=os;return z} # pattern 3 == 1[1] is multiplicative identity
if(y==2){scale=os;return qx+qz-z-1} # -ve multiplicative identity
t=z/qx;x=z-qx*t;z=t # extract bits from RHS of z, and assume these are x
hy=y/2;if(y-hy-hy){x=x;t=qx-1-x}else{t=x;x=qx-1-x}
# ^ check last bit of y to see if we have obtained x or !x and swap accordingly
y=hy;qy/=2
p[0]=t # = bitflipped x
p[1]=x
while(qy>1){
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(x<p[1])x=p[1]
scale=os;return qx+x
}
## NXOR and modular arithmetic multiplication-like pattern combination
# Mix stripe patterns so that the new length is the LCM of the old lengths
# . patterns extended to the right length and the bits are NXORed
# Is symmetric with respect to x and y, i.e. mix...(x,y) = mix...(y,x)
define mix_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=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<qx)x+=qx # put back any missing q' bit
scale=os;return x
}
# Inverse of the above; Given a modular sum of patterns 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 unmodsum_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 "unmodsum_stripe_patterns: can't extract 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 "unmodsum_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
if(z<x)z+=qz
x=qz+z-x
x = simplify_stripe_pattern(x)
scale=os;return x
}
## Addition / Subtraction :: Catenation / Decatenation
# Pattern catenation; Asymmetrical
# . 1[x] + 1[y] = 1[x][y]
define cat_stripe_patterns(x,y) {
auto os,qy;
os=scale;scale=0;x/=1;y/=1
if(x==0||y==0){scale=os;return 0}
qy = 2^(bitwidth(y)-1)
if(x<0)x=3*2^(bitwidth(x)-1)+x-1 # Flip bits of -ve params
if(y<0)y=3* qy +y-1
if(x==1){scale=os;return y} # pattern 1 == 1[] is catenate identity!
if(y==1){scale=os;return x} # in either param. works even though asymmetric
.=x--
scale=os;return x*qy+y
}
# Pattern decatenation; Like subtraction but not
# . 1[z]-1[y]=1[x] if [z] is of form [x][y], else 1[z]-1[y]=1[z]+1[!y]=1[z][!y]
define decat_stripe_patterns(z,y) {
auto os,x,bz,by,qy;
os=scale;scale=0;z/=1;y/=1
if(z==0||y==0){scale=os;return 0}
bz = bitwidth(z)-1
qy = 2^(by = bitwidth(y)-1)
if(z<0)z=3* 2^bz +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
if(bz<by){
# if left pattern is shorter than right pattern
# no subtraction can occur so 1[z]-1[y] -> 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<qy){qc=qy/qz;b/=qc;qb/=qc}
# if z is shorter than y, truncate b to length of z;
# there cannot be a longer match
for(qc=qc;qb;qc+=qc){x=z/qb;if(z-x*qb==b)break;b/=2;qb/=2}
#qc-1-y%qc # RHS of result: flipped RH bits of y that did not match [!c]
#z/(qb/qc) = x*qc # LHS of result: z with matching LH bits from y removed [a]
.=x++;x=x*qc-y%qc;.=x-- # x=x*qc+qc-1-y%qc
scale=os;return x
}
# Largest total mismatch cancelling pattern catenation
# . 1[z]+1[y] = 1[a][b]+1[!b][c] = 1[a][c] = 1[x]
# . If z ends with a group of bits of opposite parity to a group of
# . bits at the start of y, then these bits ([b] and [!b]) are erased.
# . The remaining bits are then catenated.
# . This form of catenation has the advantage of preserving addition
# . for the integers as represented by powers of two and
# . one less than powers of two.
# . e.g. (-3) + 2 -> 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)
}