php/e11bit.php
<html>
<?php
require_once('env.php');
/*----------------------------------------------------------------------------------------------------------------------
mask: handle integer as bit arrays value of a positiv integer i = sum(i[k] * 2 ** k)
----------------------------------------------------------------------------------------------------------------------*/
const intW = PHP_INT_SIZE << 3, # width of integer = number of bits
intR = 1, # rightmost (lowest value) bit set, all others 0
intL = PHP_INT_MIN, # leftmost (highest value, sign) bit set, all others 0
intA = -1; # all bits set
function bitCount($i) {
for($c=0; $i !== 0; $i<<=1)
if (($i & intL) !== 0)
$c++;
return $c;
}
function mask() { #define bit masks arrays (indexed by e = 2**e): for int. maskL, maskR, maskA, maskAh see at end
define ('intE', (int) round(log(intW, 2)));
$maskR[0] = intR;
$maskL[0] = intL;
for ($f = 1 + $e=0; $maskL[$e] !== -1; $f = 1 + ++$e) {
$maskR[$f] = $maskR[$e] | ($maskR[$e] << (1 << $e)); # << inserts 0 from right
$maskL[$f] = $maskL[$e] >> (1 << $e); # >> duplicates sign bit
}
assert (intE === $e);
assert(1 << intE === intW);
assert($maskL[intE] === intA);
assert($maskR[intE] === intA);
assert(intE + 1 == count($maskL));
assert(intE + 1 == count($maskR));
$maskA[intE] = 1;
for ($e=intE-1; $e >= 0; $e--)
$maskA[$e] = $maskA[$e+1] | ($maskA[$e+1] << (1<<$e));
for ($e=0; $e<= intE; $e++) {
$r = $maskA[$e];
for ($f=0; $f <= $e-2; $f++)
$r |= $r << (1<$f);
$maskAh[$e] = $r;
}
$maswR[0] = 0;
for ($w=1; $w <= intW; $w++)
$maswR[$w] = ($maswR[$w-1]<<1) | intR ;
define('maskL', $maskL); # left 2**e=w bits set to 1
define('maskR', $maskR); # right 2**e=w bits set to 1
define('maskA', $maskA); # in All windows of 2**e=w bits, the right bit = 1
define('maskAh', $maskAh); # in All windows of 2**e=w bits, the right half of bits = 1
define('maswR', $maswR); # indexed by w: right w bits 1
}
function maskSrc($v) {
static $v2s = null;
if ($v2s === null) {
foreach(['intE', 'intW', 'intR', 'intL', 'intA'] as $s)
$v2s[constant($s)] = $s;
dbg(3, 'int...', $v2s);
foreach(['maskL', 'maskR', 'maskA', 'maskAh', 'maswR'] as $s) {
foreach(constant($s) as $k => $l)
if ( ! isset($v2s[$l]))
$v2s[$l] = "{$s}[$k]";
}
dbg(3, 'mas...', $v2s);
}
$s = isset($v2s[$v]) ? $v2s[$v] : ($v >= 0 ? '0x' . dechex($v) : '-0x' . dechex(-$v));
assert($v === eval("return $s;"), "$v --> $s");
return $s;
}
function maskOut() {
$f = '%b';
outTB();
outTCF('l', 'r');
outTRH("const/expr", 'e', 'dec', 'hex', 'bin');
foreach(["PHP_INT_SIZE", "intW", "PHP_INT_MAX", "PHP_INT_MIN", "intL", "intA", 257, -258
, "(PHP_INT_MIN | 256) << 4", "(PHP_INT_MIN | 256) >> 4"] as $t) {
eval("\$v = $t;");
outTRD($t, sprintf('%9.2e', $v), $v, sprintf('%x', $v), sprintf('%b', $v));
}
outTBEnd();
out('');
$f ='%0' . (intW>>2) .'x';
outTB();
outTCF('l', 'r');
outTRH('int', "intE", "intW", 'intR', 'intL', 'intA', '');
outTRD('int: int*', intE, intW, sprintf($f, intR), sprintf($f, intL), sprintf($f, intA));
outTRD('int: dec', intE, intW, intR, intL, intA);
outTRH('name', "e", "maskW", 'maskR', 'maskL', 'maskA', 'maskAh', 'maswR', 'bitCount(maskA)');
outTRH('which windows', "", "w = 2**e", 'Right', 'Left', 'All', 'All');
outTRH('which bits in win', "", "win size", 'all', 'all', 'right', 'half');
for ($e=0; $e<= intE; $e++)
outTRD("[$e]", $e, 1<<$e, sprintf($f, maskR[$e]), sprintf($f, maskL[$e])
, sprintf($f, maskA[$e]), sprintf($f, maskAh[$e]), sprintf($f, maswR[1<<$e]), bitCount(maskA[$e]));
outTBEnd();
out("bitCount 0", bitCount(0) , ", 256", bitCount(256), ", 255", bitCount(255), ", 2046", bitCount(2046),
', maskA[1]', bitCount(maskA[1]), ', ~maskA[2]', bitCount(~maskA[2]), ", -1", bitCount(-1));
out('iw2to', iw2to);
}
/*----------------------------------------------------------------------------------------------------------------------
iw Integer Word arithmetic
arithmetic modulo 2**intW
results aways as int (machine word 32 or 64 bit)
using bcMath
----------------------------------------------------------------------------------------------------------------------*/
function iwIni() {
if (! defined('maskR'))
mask();
define('iwMod', bcPow(2, intW));
for ($e = 0; $e < intE; $e++)
$iw2to[$e] = 1 << (1<<$e);
for ( ; $e < 20; $e++)
$iw2to[$e] = bcPow(2, 1<<$e);
define('iw2to', $iw2to);
}
iwIni();
function iw2int($v) {
$w = bcMod($v, iwMod);
return (int) (bcComp($w, PHP_INT_MIN)<0 ? bcadd($w, iwMod) : (bcComp($w, PHP_INT_MAX)>0 ? bcSub($w, iwMod) : $w));
}
function iw2inE($v, $e=-1) {
return $e < 0 ? iw2int($v) : (iw2int($v) & maskR[$e]);
}
function iwAdd($l, $r, $e=-1) {
$s = $l + $r;
return (is_integer($s) ? $s : iw2int(bcadd($l, $r))) & maskR[$e < 0 ? intE : $e];
}
function iwMul($l, $r, $e=-1) {
$p = $l * $r;
return (is_integer($p) ? $p : iw2int(bcmul($l, $r))) & maskR[$e < 0 ? intE : $e];
}
function bitAdd($l, $r) {
return gettype($s = $l + $r) === 'integer' ? $s : ($s > 0 ? $l + PHP_INT_MIN + $r + PHP_INT_MIN : $l - PHP_INT_MIN + $r - PHP_INT_MIN);
}
function bitAddB($l, $r) {
$a = ($l & (~ (intL >> 1))) + ($r & (~ (intL >> 1)));
$b = (($l >> (intW - 2)) & 3) + (($r >> (intW - 2)) & 3) + (($a >> (intW - 2)) & 3);
return ($b << (intW - 2)) | ((~ (intL >> 1)) & $a);
}
function addTestE($f, $l, $r) {
for ($e=0; $e < intE and (~maskR[$e] & ($l | $r)) !== 0; $e++) {};
testFun($f, ($l + $r) & maskR[$e], $l, $r, $e);
if ($e < intE and (($l | $r) >> ((1<<$e)-1)))
testFun($f, $l + $r, $l, $r, $e+1);
}
function addTestMiMa($f, $l, $r) { # test near INT_MAX and INT_MIN
bitTest1($f, $l, $r, $l + $r);
bitTest1($f, "$l", "PHP_INT_MIN + $r", "PHP_INT_MIN + $l + $r");
bitTest1($f, "PHP_INT_MIN + $l", "$r", "PHP_INT_MIN + $l + $r");
bitTest1($f, "PHP_INT_MIN + $l", "PHP_INT_MIN + $r", "$l + $r");
bitTest1($f, $l, -$r, $l - $r);
bitTest1($f, "$l", "PHP_INT_MAX-$r", $l > $r ? "PHP_INT_MIN + $l - $r -1" : "PHP_INT_MAX -$r + $l");
bitTest1($f, "PHP_INT_MIN + $l", -$r, $l >= $r ? "PHP_INT_MIN + $l - $r" : "PHP_INT_MAX -$r + $l + 1");
bitTest1($f, "PHP_INT_MIN + $l", "PHP_INT_MAX-$r", "-1 + $l - $r");
bitTest1($f, -$l, $r, -$l + $r);
bitTest1($f, "-$l", "PHP_INT_MIN+$r", $l > $r ? "PHP_INT_MAX - $l + $r +1" : "PHP_INT_MIN +$r - $l");
bitTest1($f, "PHP_INT_MAX-$l", "$r", $l >= $r ? "PHP_INT_MAX - $l + $r" : "PHP_INT_MIN +$r - $l - 1");
bitTest1($f, "PHP_INT_MAX-$l", "PHP_INT_MIN+$r", " - $l + $r -1");
bitTest1($f, -$l, -$r, -$l - $r);
bitTest1($f, "-$l", "PHP_INT_MAX-$r", "PHP_INT_MAX - $l - $r");
bitTest1($f, "PHP_INT_MAX-$l", "-$r", "PHP_INT_MAX - $l - $r");
bitTest1($f, "PHP_INT_MAX-$l", "PHP_INT_MAX-$r", "-2 - $l - $r");
}
function bitTestTR($h, $s, $v, $oo='outTRD') {
$oo($h, $s, $v, sprintf('%x', $v), sprintf('%b', $v), bitCount($v));
}
function bitTestTRlrs($fun, $lS, $l, $rS, $r, $sS, $s) {
bitTestTR('', $lS, $l);
bitTestTR(strpos($fun, 'dd') ? '+' : '*', $rS, $r);
bitTestTR($fun, $sS, $s, 'outTRH');
}
function bitTest1($fun, $lS, $rS, $sS) {
global $dbg;
$f = '%064b';
eval("\$l = $lS; \$r = $rS; \$s = $sS;");
if ($dbg)
bitTestTRlrs($fun, $lS, $l, $rS, $r, $sS, $s);
testFun($fun, $s, $l, $r, -1, $lS, $rS, $sS);
}
function bitMul($l, $r) { # bitMultiplication (int -> [0, 2**64-1] modulo 2**64) using bcmath
static $bcI = null, $bcH;
if ($bcI === null) {
$bcI = bcpow(2,intW);
$bcH = bcpow(2,intW-1);
}
$x = bcmod(bcmul($l >= 0 ? $l : bcadd($bcI, $l), $r >= 0 ? $r : bcadd($bcI, $r)), $bcI);
return (int) ($x < $bcH ? $x : bcsub($x, $bcI));
}
function bitMulInt($l, $r) { # bitMultiplication (int -> [0, 2**64-1] modulo 2**64) using PHP int only
static $mW = null, $mW2, $mL, $mM, $mR, $mRL;
if ($mW === null) {
$mW = (intW >> 1) - 1;
$mW2= $mW << 1;
$mL = PHP_INT_MIN >> (intW - ($mW << 1) - 1);
$mR = ( ~ $mL) >> $mW;
$mM = -1 ^ ($mL | $mR);
$mRL= $mR >> ($mW*3-intW);
dbg1('bitMultInt intW', intW, ', intE', intE, ", mW $mW, mW2 $mW2,"
, sprintf('L %x, M %x, R %x, RL %x', $mL, $mM, $mR, $mRL));
}
$c = ($l & $mR) * ($r & $mR);
$b = ($c>>$mW) + (($l>>$mW) & $mR) * ($r & $mR) + ($l & $mR) * (($r>>$mW) & $mR);
$a = ($b>>$mW) + (($l>>$mW2) & $mRL) * ($r & $mR) + (($l>>$mW) & $mR) * (($r>>$mW) & $mR)
+ ($l & $mR) * (($r>>$mW2) & $mRL) ;
$p = ($a << $mW2) | (($b << $mW) & $mM) | ($c & $mR);
dbg(2, "bitMulInt($l, $r =", $l * $r, ") -> $p");
return $p;
}
function bitMulGmp($l, $r) { # bitMultiplication (int -> [0, 2**64-1] modulo 2**64) using gmp math
static $gmpI = null, $gmpH;
if ($gmpI === null) {
$gmpI = gmp_pow(gmp_init(2), intW);
$gmpH = gmp_pow(gmp_init(2), intW-1);
}
$x = gmp_mod(gmp_mul(gmp_init(dechex($l), 16), gmp_init(dechex($r), 16)), $gmpI);
return gmp_intval(gmp_cmp($x, $gmpH) < 0 ? $x : gmp_sub($x, $gmpI));
}
function bitMulTestMiMa($fun, $l, $r) { # test near INT_MAX and INT_MIN
bitTest1($fun, $l, $r, $l * $r);
bitTest1($fun, "$l", "PHP_INT_MIN + $r", ($l & 1) ? "PHP_INT_MIN + $l * $r": "$l * $r");
bitTest1($fun, "PHP_INT_MIN + $l", "$r", ($r & 1) ? "PHP_INT_MIN + $l * $r": "$l * $r");
bitTest1($fun, "PHP_INT_MIN + $l", "PHP_INT_MIN + $r", (($l ^ $r) & 1) ? "PHP_INT_MIN + $l * $r" : "$l * $r");
bitTest1($fun, $l, -$r, $l * -$r);
bitTest1($fun, "$l", "PHP_INT_MAX-$r", ($l & 1) ? "PHP_INT_MAX - $l + 1 - $l * $r" : "-$l - $l * $r");
bitTest1($fun, "PHP_INT_MIN + $l", -$r, ($r & 1) ? ($l === 0 ? "PHP_INT_MIN" : "PHP_INT_MAX - $l * $r + 1"): "-$l * $r");
bitTest1($fun, "PHP_INT_MIN + $l", "PHP_INT_MAX-$r", (($l - $r) & 1) ? "-$l -$r * $l" : ($l === 0 ? "PHP_INT_MIN" :"PHP_INT_MAX -$l - $l * $r + 1"));
bitTest1($fun, -$l, $r, -$l * $r);
bitTest1($fun, "-$l", "PHP_INT_MIN+$r", ($l & 1) ? (($l === 0 or $r === 0) ? "PHP_INT_MIN" : "PHP_INT_MAX - $l * $r + 1"): "-$l * $r");
bitTest1($fun, "PHP_INT_MAX-$l", "$r", ($r & 1) ? "PHP_INT_MAX - $r + 1 - $l * $r" : "-$r - $l * $r");
bitTest1($fun, "PHP_INT_MAX-$l", "PHP_INT_MIN+$r", (($l - $r) & 1) ? "-$r -$r * $l" : ($r == 0 ? "PHP_INT_MIN" : "PHP_INT_MAX -$r - $l * $r + 1"));
bitTest1($fun, -$l, -$r, -$l * -$r);
bitTest1($fun, "-$l", "PHP_INT_MAX-$r", ($l & 1) ? "PHP_INT_MIN + $l + $l * $r " : "$l + $l * $r");
bitTest1($fun, "PHP_INT_MAX-$l", "-$r", ($r & 1) ? "PHP_INT_MIN + $r + $l * $r " : "$r + $l * $r");
bitTest1($fun, "PHP_INT_MAX-$l", "PHP_INT_MAX-$r", (($l + $r) & 1) ? "PHP_INT_MIN + 1 + $l + $r + $l * $r" : "1 + $l + $r + $l * $r");
}
function testIni($d=0, $a=1) {
global $testCnt, $testErr, $testII, $dbg;
$testCnt = $testErr = 0;
$testII = ['dbg' => $d, 'dbgOld' => $dbg, 'assert' => $a, 'assertOld' => envAssert()
, 'start' => microtime(true), 'replay' => ['testReplay'], 'errOut' => 'testErrOut'];
testSetEnv();
}
function testErrOut($msg, $fun, $rEx, $rRe, ...$args) {
out("$msg: $fun(" . i2str($args, ', ') . ") ->", $rRe, 'but expected', $rEx);
}
function testReplay () {
global $dbg;
$dbg=99;
out('replay with dbg', envAssert(1));
}
function testSetEnv() {
global $testII, $dbg;
$dbg = $testII['dbg'];
envAssert($testII['assert']);
}
function testEnd() {
global $testCnt, $testErr, $testII;
$ela = microtime(true) - $testII['start'];
out("testEnd $testErr errors, $testCnt tests, " . sprintf('%8.6f', $ela) . "secs"
. ($testCnt<1 ? '' : ", " . sprintf('%8.6f', $ela/$testCnt)) . 'secs/test');
$dbg = $testII['dbgOld'];
envAssert($testII['assertOld']);
}
function testFun($fun, $rEx, ...$args) {
global $testCnt, $testErr, $testII;
$testCnt++;
$r = $fun(...$args);
if ($r === $rEx)
return;
$testErr++;
$testII['errOut']("test $testCnt error ($testErr):", $fun, $rEx, $r, ...$args);
foreach($testII['replay'] as $p) {
$p();
$r2 = $fun(...$args);
if ($r2 !== $r) {
$testII['errOut']("replay with different result:", $fun, $rEx, $r2, ...$args);
}
}
testSetEnv();
}
function addR($l, $r, $mE=-1) {
global $dbg, $assN, $assT;
#how many bits?
if ($mE < 0)
for ($mE=0; $mE < intE and (~(maskR[$mE] >> 1) & ($l | $r)) !== 0; $mE++) {};
$f = "%0" . (1<<$mE) . "b";
$mR = maskR[$mE];
$a = $mR & ($l ^ $r); # l+r for each window of 1 bit
$b = $mR & (~ $l ^ $r) ; # l+r+1 for each window of 1 bit
$c = $mR & (($l & $r) << 1); # carry for l+r
$d = $mR & (($l | $r) << 1); # carry for l+r + 111...
if ($dbg >= 2) {
out("addR1 mE=$mE, $l + $r =", $l+$r, sprintf("$f + $f = $f", $l, $r, $l+$r));
if ($dbg >= 3)
out(sprintf("a $f, b $f, c $f, d $f", $a, $b, $c, $d), "addR1 w=1");
}
assert(($yN = $mE >= intE and ((intL>>1) & ($l | $r)) !== 0) # no asserts if we might get int overflows
or ($yS = ($l + $r) & ($yM = $mE < intE ? maskR[$mE] : ~ (intL >> 1))) === (($a + $c) & $yM));
assert($yN or (($yS + (maskA[0] & $mR)) & $mR) === (($b + $d) & $mR));
assert(dbg(3, "yN", $yN, ++$assT, $assN += (int) $yN) or true);
for ($e=1; $e<=$mE; $e++) {
$v = 1<<($e-1);
$w = 1<<$e;
$m = (~$c) & (maskA[$e] << $v) | maskA[$e];
for ($q=0; $q<$e-1;$q++) #this loop does not cost anything, it on simulates wiring!
$m |= $m << (1<<$q);
$aN = $mR & (($m & $a) | ((~$m) & $b));
$m = (~$d) & (maskA[$e] << $v);
for ($q=0; $q<$e-1;$q++) #this loop does not cost anything, it on simulates wiring!
$m |= $m << (1<<$q);
$b = $mR & (($m & $a) | ((~$m) & $b));
$a = $aN;
$cN = $mR & (~($c << $v) & $c | ($c << $v) & $d) & maskA[$e];
$d = $mR & (~($d << $v) & $c | ($d << $v) & $d) & maskA[$e];
$c = $cN;
assert($yN or $yS === (($a + $c) & $mR));
assert($yN or (($yS + (maskA[$e] & $yM)) & $yM) === (($b + $d) & $mR));
if ($dbg >= 2)
out("addR3 loop1", sprintf("c $f, d $f, m $f", $c, $d, $m));
if ($dbg >= 3)
for($i=0; $i < intE; $i+=$w)
out("i $i:", ($l >> $i) & maskR[$e], '+', ($r >> $i) & maskR[$e], '=',
(($a>>$i) & maskR[$e]) + (($c>>$i) & (maskR[$e] <<$w)),
(($b>>$i) & maskR[$e]) + (($d>>$i) & (maskR[$e] <<$w)));
}
dbg(2, "addREnd $l + $r = $a, +1 = $b");
assert($yN or $a === $yS);
assert($yN or $b === (($yS + 1) & $yM));
return $a;
}
function addC($l, $r, $mE=-1) {
if ($mE < 0) #how many bits?
for ($mE=0; $mE < intE and (~(maskR[$mE] >> 1) & ($l | $r)) !== 0; $mE++) {};
$mR = maskR[$mE];
$c = $mR & (($l & $r) << 1); # carry for l+r
$d[0] = $mR & ($l ^ $r); # carry for l+r + 111...
for ($e=0; $e < $mE; $e++) {
$e1 = $e + 1;
$w=1<<$e;
$d[$e1] = $d[$e] & ($d[$e] >> $w) & maskA[$e]; # all1 for w bit windows
$c ^= $mR & maskA[$e1] & (($d[$e] & $c) << $w); # xor carry at bits 2*i*w (bit 0 always 0!)
}
for ($e= $mE-1; $e >= 0; $e--) {
$e1 = $e + 1;
$w=1<<$e;
$c ^= $mR & (maskA[$e1] << (3 * $w)) & (($d[$e] & $c) << $w); # xor carry at bits (2 *i + 1)*w (bit w always 0)
}
$s = $l ^ $r ^ $c;
dbg(2, "addC($l, $r =", $l + $r, ") -> $s eM=$mE");
assert(((($l & $mR) + ($r & $mR)) & $mR) === $s or gettype(($l & $mR) + ($r+$mR)) !== 'integer');
return $s;
}
function mul($l, $r) {
$t = [];
$noAss = ($l | $r) & (intA << ((intW >> 1) - 1));
$rA = $r;
for ($lA=$l; $lA and $rA; $lA = ($lA>>1) & ~ intL) {
$t[] = ($lA & 1) ? $rA : 0;
$rA <<=1;
}
$len = [count($t)];
assert($noAss or array_sum($t) === $r * $l);
while (($c = count($t) -2 ) > 0) {
$u = [];
for ($i = 0; $i < $c; $i+=3) {
$u[] = $t[$i] ^ $t[$i+1] ^ $t[$i+2];
$u[] = (($t[$i] & ($t[$i+1] | $t[$i+2])) | ($t[$i+1] & $t[$i+2])) << 1;
}
for ( ; $i < $c+2; $i++)
$u[] = $t[$i];
$t = $u;
assert($noAss or array_sum($t) === $r * $l);
$len[] = count($t);
}
$p = count($t) === 0 ? 0 : (count($t) === 1 ? $t[0] : (count($t) === 2 ? addC($t[0], $t[1]) : err("too big", $t)));
dbg(2, "mul($l, $r) -> $p,", count($len), "steps", $len);
assert($noAss or $l * $r === $p);
return $p;
}
function rlAddCarry($cE) { # reversible carry lookahead: (l, r) ==> (l, l^r, l^r^(l+r))
$cW = 1<<$cE;
$c = ['e' => $cE, 'return' => 'r',
#['out', 'l', 'r', 'c', "d1", "rlAddCarry $cE begin"],
['ccNot', 'c', '', 'l<<1', 'r<<1'],
['xor' , 'r', '', 'l']];
# compute carry and all1 for increasing windows sizes
$c[] = ['ccNot', "d1", maskA[1], 'r<<1', "r<<2"]; # all1 for e=1
$c[] = ['ccNot', 'c' , maskA[1], 'r<<1', "c<<1"]; # fix carry for e=1
for ($e=2; $e < $cE; $e++) {
$v = 1<<($e1 = $e-1);
$c[] = ['ccNot', "d$e", maskA[$e], "d$e1", "d$e1<<$v"]; # all1
$c[] = ['ccNot', 'c' , maskA[$e], "d$e1", "c<<$v"]; # fix carry
#$c[] = ['out', 'l', 'r', 'c', "d$e", "after carry up $e $v"];
}
for ($e=$cE-1; $e >1; $e--) {
$v = 1<<($e1=$e-1);
$c[] = ['ccNot', "d$e", maskA[$e], "d$e1", "d$e1<<$v"]; #uncompute all1
$c[] = ['ccNot', 'c' , maskA[$e]<<$v,"d$e1", "c<<$v"]; #fix carry in the middle
#$c[] = ['out', 'l', 'r', 'c', "d$e", "after carry down $e $v"];
}
$c[] = ['ccNot', "d$e", maskA[1], "r<<1", "r<<2"]; #uncompute all1 for e=1
$c[] = ['ccNot', 'c' , maskA[1]<<1, "r<<1", "c<<1"]; #fix carry in the middle for e=1
#$c[] = ['out', 'l', 'r', 'c', "d1", "rlAddCarry $cE end"];
return $c;
}
function rlCompileAss($oo, $m, $e, $c) {
if ($oo['shI'] === 0) {
} elseif ($oo['shift'][0] === '>') {
$m <<= $oo['shI'];
$c = "($c<<{$oo['shI']})";
} else {
$m = maswR[intW - $oo['shI']] & ($m >> $oo['shI']);
$c = "($c>>{$oo['shI']})";
}
if (intA !== $m &= maskR[$e])
$c = maskSrc($m) . " & $c"
. ($m === maskR[$e] ? '' : (' | ' . maskSrc(maskR[$e] & ~$m) . " & {$oo['src']}"));
return "{$oo['src']} = $c;\n";
}
function rlCompile($nm, ...$args) {
static $compiled = [], $coco=0;
$key = "$nm(" . implode(', ', $args) . ')';
if (isset($compiled[$key]))
# out("compile found $key");
return $compiled[$key];
# }
global $dbg;
$src = $nm(...$args);
out("compile $key", count($src));
$e = $src['e'] ?? $args[0];
assert(is_int($e) and $e >= 0 and $e <= intE);
$vrs = [];
$code = ['name' => $key, 'e' => $e, 'w' => $w=(1<<$e), 'fmt' => "%0{$w}b"];
$cdF = $cdB = '';
if ($dbg)
outOL();
$sz = 0;
foreach ($src as $sX => $s) {
# dbg(7, "src $sX", $s);
$dpt = 0;
if (! is_int($sX) ) {
$code[$sX] = $s;
continue;
} elseif (! is_array($s)) {
err("not array $sX =>", $s);
} elseif (($sC = count($s)) < 2) {
err("array size $sC: $sX =>", $s);
} elseif ('out' === ($g = $s[0])) {
$c = 'rlOut($d';
for ($i=1; $i<$sC; $i++)
$c .= ", '" . addslashes($s[$i]) ."'";
$c .= ");\n";
} elseif ('run' === $g) {
$c = "rlRun('$s[1]', ['" . implode("', '", $s[2])
. "'], \$d, " . ((($s[3] ?? '') === '!') ? '1 - ' : '') . "\$back);\n";
} elseif ('show' === $g) {
$c = "rlShow('$s[1]', \$d);\n";
} elseif ($sC > 5 ) {
err("array size $sC: $sX =>", $s);
} else { # real gate
for ($i = 1 ; $i < $sC; $i===1 ? $i+=2 : $i++) {
$v = $s[$i];
$oo = [];
if ($oo['not'] = ($v[0] === '~'))
$v = substr($v, 1);
$sh = substr($v, $x = strcspn($v, '<>'));
$v = substr($v, 0, $x);
$shI = 0;
if ($sh !== '') {
while ($sh !== '') {
$x = strcspn($sh, '<>', 2);
if (trim($shD = substr($sh, 2, $x), '0123456789') !== '' or $shD === '')
err("shift {$s[$i]} sh=$sh x=$x");
elseif (substr($sh, 0, 2) === '>>')
$shI += $shD;
elseif (substr($sh, 0, 2) === '<<')
$shI -= $shD;
else
err("shift {$s[$i]}");
$sh = substr($sh, $x+2);
}
$sh = $shI === 0 ? '' : ($shI > 0 ? ">>$shI" : "<<" . ($shI = -$shI));
# dbg(9, "shift [$s[$i] ==> $sh / $shI");
}
$oo['src'] = '$d[\'' . addslashes($oo['nm'] = $v) . '\']';
$oo['shift'] = $sh;
$oo['shI'] = $shI;
$oo['ex'] = ($oo['shI'] === 0) ? $oo['src'] : "({$oo['src']}{$oo['shift']})";
if ($oo['not'])
$oo['ex'] = "(~{$oo['ex']})";
$dpt = max($dpt, 1 + ($vrs[$oo['nm']] ?? $vrs[$oo['nm']] = 0));
$op[$i] = $oo;
}
$d = $op[1]['ex'];
$vrs[$op[1]['nm']] = $dpt;
assert(! $op[1]['not']);
$m = '' === ($m = $s[2] ?? '') ? maskR[$e] : (maskR[$e] & $m);
$sz += bitCount($m);
if ($g === 'ccNot') {
if ($sC !== 5)
err("ccNot needs exactly 2 ops: $sX =>", $s);
$c = rlCompileAss($op[1], $m, $e, "($d ^ ({$op[3]['ex']} & {$op[4]['ex']}))");
} elseif ($g === 'fredkin') {
if ($sC !== 5)
err("fredkin needs exactly 2 ops: $sX =>", $s);
$ms = '(' . maskSrc($m) . " & {$op[4]['ex']})";
$c = rlCompileAss($op[1], $m, $e, "((~$ms) & $d | $ms & {$op[3]['ex']})")
. rlCompileAss($op[3], $m, $e, "((~$ms) & {$op[3]['ex']} | $ms & $d)") ;
assert(substr($c, 0, strlen($op[1]['src'])+2) === $op[1]['src'] . ' =');
$c = '$v1' . substr($c, strlen($op[1]['src'])) . $op[1]['src'] . " = \$v1;\n";
} elseif ($g === 'not') {
if ($sC > 3)
err("not needs no ops: $sX =>", $s);
$c = rlCompileAss($op[1], $m, $e, "(~$d)");
} elseif ($g === 'xor') {
if ($sC !== 4)
err("xor needs exactly 1 op: $sX =>", $s);
$c = rlCompileAss($op[1], $m, $e, "($d ^ {$op[3]['ex']})");
} else {
err("bad gate $g: $sX =>", $s);
}
/* if ($opShI[1] === 0) {
} elseif ($oo['shift'][0] === '>') {
$m <<= $opShI[1];
$c = "($c<<{$opShI[1]})";
} else {
$m = maswR[intW -$opShI[1]] & ($m >> $opShI[1]);
$c = "($c>>{$opShI[1]})";
}
if (intA !== $m &= maskR[$e])
$c = maskSrc($m) . " & $c"
. ($m === maskR[$e] ? '' : (' | ' . maskSrc(maskR[$e] & ~$m) . " & $opSrc[1]"));
$c = "$opSrc[1] = $c;\n";
} else { # fredkin
$c1 = $m === intA ? $op[4] : "($op[4] & $m)";
if (($sh = $opShift[3]) === '' or $sh === '<<0' or $sh === '>>0') {
$sh = '';
$mS = $m;
} elseif ($sh[0] === '>') {
$sh = '<<' . ($si = substr($sh, 2));
$mS = ($m << $si) & maskR[$e];
} elseif ($sh[0] === '<') {
$sh = '>>' . ($si = substr($sh, 2));
$mS = ($m >> $si) & maswR[$w - $si];
} else {
err("bad opShift[$i]", $opShift[$i]);
}
assert(bitCount($m) === bitCount($mS));
$m2 = '(' . maskSrc($mS) . " & ($op[4]$sh))";
$c = '$v1 = (' . maskSrc(maskR[$e]) . " & (~ $m1) & $d) | ($m1 & $op[3]);\n"
# & $op[4])maskR[$e] & (((~ $m1) & $d) | ($m1 & $op[3]));\n"
. "$opSrc[3] = (" . maskSrc(maskR[$e]) . " & (~ $m2) & $opSrc[3]) | ($m2 & ($d$sh));\n"
. "$d = \$v1;\n";
} */
} # real gate
if ($dbg>9)
outLi($s, "***** $c dept $dpt, size $sz");
$cdF .= $c;
$cdB = "$c $cdB";
} # foreach $s
$code['size'] = $sz;
$code['depth'] = $dpt = array_reduce($vrs, 'max', 0);
if ($dbg)
outOLEnd("compile end $key depth $dpt, size $sz");
$fuB = "function(&\$d) {\n";
$fuE = isset($code['return']) ? ('return $d[\'' . addslashes($code['return']) . '\']; }' ) : '}';
# $m1 = memory_get_usage();
eval("\$code[0] = $fuB\n\$back=0;\n$cdF\n$fuE;");
eval("\$code[1] = $fuB\n\$back=1;\n$cdB\n$fuE;");
/* $m2 = memory_get_usage();
gc_collect_cycles();
gc_mem_caches();
out(sprintf('memory get usage from %8.3e via %8.3e to %8.3e coco %5d', $m1, $m2, memory_get_usage(), ++$coco)); */
$code['vars'] = array_keys($vrs);
# $code['src'] = $src;
return $compiled[$key] = $code;
}
function rlRun($sFun, $sArgs, &$d, $back=0) {
$sArgs[0] = $d['conf']['e'];
$c = rlCompile($sFun, ...$sArgs);
# rlShow("rlRunBegin back=$back", $d);
# out("rlRun $sFun(", $sArgs, ") back=$back vars=", $c['vars']);
foreach ($c['vars'] as $v)
if (! isset($d[$v]))
$d[$v] = 0;
$r = $c[$back]($d);
# rlShow("rlRunEnd back=$back returned=$r=" . sprintf($c['fmt'], $r), $d);
return $r;
}
function rlShow($t, $d) {
$e = $d['conf']['e'];
$w = 1 << $e;
$f = "%0${w}b";
out($t, "e=$e m=". sprintf('%b', maskR[$e]), 'conf', $d['conf']);
forEach($d as $k => $v)
if ($k !== 'conf')
out (str_pad("....$k", 10, '.'), sprintf($f, $v), $v);
}
function rlOut($d) {
$e = $d['conf']['e'];
$w = 1 << $e;
$f = "%0${w}b";
$t = '';
for ($x=1; $x < func_num_args(); $x++) {
$n = func_get_arg($x);
$t .= ", $n" . (isset($d[$n]) ? (" => " . sprintf($f, $d[$n]) . " $d[$n]") : "");
}
out(substr($t, 2));
}
function rlAddProof() { # output table with highlevel schema of rlAdd and proof
outH('reversible carry lookahead adder depth log w');
outTB();
outTRH(0, 'op' ,'left', 'right', 'carry');
outTRH(1, 'rlAddCarry' ,'l', 'r', '0');
outTRD(2, '^', 'l', 'l ^ r', 'l ^ r ^ (l+r)');
outTRD(3, '^ ~', 'l', '~l ^ (l + r)', 'l ^ r ^ (l+r)');
outTRD(4, 'rlAddCarry backward', 'l', '~l ^ (l + r) ', 'l ^ r ^ (l+r)');
outTRD(5, '~' ,'l', '~ (l+r)', '0');
outTRH(6, '' ,'l', 'l+r', '0');
# outTRD(7);
outTRD('', '4 -> 5 because backward yields');
outTRD(7, '-->5 rlAddCarry ' , 'l', '~ (l+r)', '0');
outTRD(8, '===' ,'l', 'l ^ ~(l+r)', 'l ^ ~(l+r) ^ (l + ~(l+r)');
outTRD(9, '===' ,'l', '~l ^ (l+r)', 'l ^ ~(l+r) ^ (l + (1 - l - r))');
outTRD(10, '===' ,'l', '~l ^ (l+r)', 'l ^ ~(l+r) ^ (1 - r)');
outTRD(11, '===' ,'l', '~l ^ (l+r)', 'l ^ ~(l+r) ^ ~r');
outTRD(12, '-->4' ,'l', '~l ^ (l+r)', 'l ^ r ^ (l+r)');
outTBEnd();
}
function rlAdd($l, $r='src', $e=-1, $back='onlyGetSource') { # reversible lookahead adder
if ($r === 'src')
return ['e' => $l, 'return' => 'r',
['run', 'rlAddCarry', []],
['xor', 'r', '', 'c'],
# ['out', 'l', 'r', 'c', "after carryForward and xor"],
['xor', 'r', '', '~l'],
['run', 'rlAddCarry', [], '!'],
['not', 'r'],
# ['out', 'l', 'r', 'c', "endResult"]
];
if ($e < 0) #how many bits?
for ($e=0; $e < intE and (~(maskR[$e] >> 1) & ($l | $r)) !== 0; $e++) {};
dbg(2, "$l + $r =", $l + $r, "e=$e");
$d = ['l' => $l, 'r' => $r, 'conf' => ['e' => $e, 'args' => [$e], 'src' => function($e) {
}]];
$s = rlRun('rlAdd', [-1], $d, 0);
# out("$l + $r = $s =", $l + $r); #, sprintf(", %0${e}b + %0${e}b = %0${e}b", $l, $r, $s));
assert ($s === $d['r']);
assert ($s === bitAdd($l, $r) and $s == $d['r'] and $l === $d['l']);
rlAssert($d, 0, ['l' => $l, 'r' => bitAdd($l, $r)]);
return $s;
}
function rlSub($l, $r='src', $e=-1, $back='onlyGetSource') { # reversible lookahead adder
#how many bits?
if ($e < 0)
for ($e=0; $e < intE and (~(maskR[$e] >> 1) & ($l | -$r)) !== 0; $e++) {};
$d = ['r' => $l, 'l' => $r, 'conf' => ['e' => $e]];
$s = rlRun('rlAdd', [$e], $d, 1);
# out("$l - $r = $s =", $l - $r); #, sprintf(", %0${e}b - %0${e}b = %0${e}b", $l, $r, $s));
assert ($s === $d['r']);
assert($s === $l - $r and $s == $d['r'] and $r === $d['l']);
rlAssert($d, 0, ['l' => $r, 'r' => $l - $r]);
return $s;
}
function rlAssert($d, $z, $m) {
# rlShow('rlAssert', $d);
foreach($d as $k => $v)
if ($k !== 'conf')
assert($v === ($m[$k] ?? $z), "assert: $k => $v <<>> " . ($m[$k] ?? "z=$z"));
}
function rlFredkinSrc($e, $r, $m, $s, $c) { # fredkin gate
return [['show', 'fredkin before'], ['fredkin', $r, $m, $s, $c], ['show', 'fredkin after']];
}
function rlFredkin($r=null, $s=null, $c=null) { # fredkin gate
$d = [ 'r' => $r, 's' => $s, 'c' => $c, 'conf' => ['e' => intE]];
rlRun('rlFredkinSrc', [intE, 'r', '', 's', 'c'], $d, 0);
rlRun('rlFredkinSrc', [intE, 'r', '', 's', 'c'], $d, 0);
rlRun('rlFredkinSrc', [intE, 'r', 0xfff0, 's<<4', 'c'], $d, 0);
rlRun('rlFredkinSrc', [intE, 'r', 0xfff0, 's<<4', 'c'], $d, 0);
}
function rlCAddSrc($eO, $r, $a, $b, $c='c', $sN = 'sN') { # reversible conditional adder
$wO = 1 << $eO; # width of operands
$q = ['e' => min(intE, $eO+1) # exponent of width of result
, 'return' => substr($r, 0, strcspn($r, '<>'))
# , 0 => ['show', "rlCAdd begin"]
];
dbg(3, "rlCAddSrc($eO, $r, $a, $b) begin", $q);
for($w=0; $w < $wO; $w++) {
$q[] = ['ccNot', $r, 1<<$w, $a, "$b<<$w"];
$q[] = ['fredkin', $a, 1<<$w, "$c<<$w", "~$r"];
# $q[] = ['show', "rlCAdd forw $w"];
}
$q[] = ['ccNot', $sN, intR, $b, $c];
for($w = $wO -1; $w >= 0; $w--) {
$q[] = ['fredkin', $a, 1<<$w, "$c<<$w", "~$r"];
$q[] = ['ccNot', $r, 1<<$w, "$c<<$w", "$b<<$w"];
# $q[] = ['show', "rlCAdd back $w"];
}
for($w=0; $w < $wO; $w++) {
$q[] = ['fredkin', $r, 1<<$w, $a, "g<<$w"];
$q[] = ['ccNot', 'g', intR, "~$r>>$w", "$a>>$w"];
}
$q[] = ['not', $b, intR];
$q[] = ['ccNot', $b, intR, 'g', "~$sN"];
for($w= $wO -1; $w >= 0; $w--) {
$q[] = ['ccNot', 'g', intR, "~$r>>$w", "$a>>$w"];
$q[] = ['fredkin', $r, 1<<$w, $a, "g<<$w"];
}
# $q[] = ['show', 'afterAdd'];
return $q;
}
function rlCAdd($e, $r, $a, $b, $back=0) { # reversible conditional adder
if ($e < 0) #how many bits? 2**e is the width of the operands, r has doubble width
for ($e=0; $e <= intE and (~maskR[$e] & ($r | $a)) !== 0; $e++) {};
$d = ['r' => $r, 'a' => $a, 'b' => $b, 'conf' => ['e' => $e]];
$res = rlRun('rlCAddSrc', [$e, 'r', 'a', 'b', 'c'], $d, $back);
dbg(2, "rlCAdd $r + $a with $b ==> $res sN = {$d['sN']} g={$d['g']}");
if ( 0 <= $r and $r < $a)
rlAssert($d, 0, ["a" => $a , "b" => ($a === 0 ? ($b & ~ intR | ~$b & intR) : $b & ~ intR)
, "r" => ((! ($b & intR)) ? $r : iw2InE($qX = bcadd($r, $a), $e))
, 'sN' => ((! ($b & intR)) ? 0 : (int) (bcComp($qX, iw2to[$e]) >= 0))]);
return $res;
}
/* ?????????????
function rlCAddShift($eR, $shft, $r, $a, $b, $sN = "$b>>$shft", $c='c') { # reversible conditional adder
assert($eR >= 1 and $eR <= intE);
$eO = $eR-1;
$wO = 1<<$eO;
$q = ['return' => $r
# , 0 => ['show', "rlCAdd begin"]
];
for($w=0; $w < $wO; $w++) {
$q[] = ['ccNot', $r, 1<<($shft+$w), "$a<<$shft", "$b<<$w"];
$q[] = ['fredkin', $a, 1<<$w, "$c<<$w", "~$r<<$shft"];
# $q[] = ['show', "rlCAdd forw $w"];
}
$q[] = ['ccNot', "$b<<" . ($wO+$shft) , intR, $b, $c];
for($w= (1<<$eM) -1; $w >= 0; $w--) {
$q[] = ['fredkin', $a, 1<<$w, "$c<<$w", "~$r<<$shft"];
$q[] = ['ccNot', $r, 1<<($shft+$w), "$c<<$w", "$b<<$w"];
# $q[] = ['show', "rlCAdd back $w"];
}
for($w=0; $w < (1<<$eM); $w++) {
$q[] = ['fredkin', $r, 1<<($w+$shft), $a, "g<<$w"];
$q[] = ['ccNot', 'g', intR, "~$r>>$w", "$a>>$w"];
}
$q[] = ['not', $b, intR];
$q[] = ['ccNot', $b, intR, 'g', "~$sN"];
for($w= (1<<$eM) -1; $w >= 0; $w--) {
$q[] = ['ccNot', 'g', intR, "~$r>>$w", "$a>>$w"];
$q[] = ['fredkin', $r, 1<<$w, $a, "g<<$w"];
}
# $q[] = ['show', 'afterAdd'];
return $q;
} ????? */
function rlMulSrc($e) { # reversible multiplication
# function rlCAddSrc($eO, $r, $a, $b, $c='c', $sN = 'sN') { # reversible conditional adder
assert($e < intE);
$w = 1<<$e;
$q = ['return' => 'r'];
# $q[] = ['show', "rlMul begin"];
for ($v=0; $v<$w and $v+$w<intW; $v++) {
$q[] = ['run', 'rlcAddSrc', [$e, "r>>$v", 'a', "b>>$v", 'c', 'r>>' . ($w+$v)]];
# $q[] = ['show', "rlMul after v=$v"];
}
return $q;
}
function rlMul($e, $r, $a, $b, $back=0) { # reversible conditional adder
if ($e < 0) #how many bits? 2**e is the width of the operands, r has doubble width
for ($e=0; $e <= intE and (~maskR[$e] & ($a | $b)) !== 0; $e++) {};
$eR = min($e+1, intE);
$d = ['r' => $r, 'a' => $a, 'b' => $b, 'conf' => ['e' => $e]];
$res = rlRun('rlMulSrc', [$e], $d, $back);
dbg(2, "rlMul $r + $a * $b ==> $res sN");
if ( 0 <= $r and $r < $a)
rlAssert($d, 0, ["a" => $a , 'r' => iwAdd($r, iwMul($a, $b), $e)]);
return $res;
}
function rlDiv($e, $r, $a) { # reversible conditional adder
if ($e < 0) #how many bits? 2**e is the width of the operands, r has doubble width
for ($e=0; $e < intE-1 and (~maskR[$e] & ($a | $r)) !== 0; $e++) {};
$d = ['r' => $r, 'a' => $a,'conf' => ['e' => $e]];
$res = rlRun('rlMulSrc', [$e], $d, 1);
dbg(2, "rlDiv $r % $a => [{$d['b']}, {$d['r']}]");
return [$d['b'], $d['r']];
}
function gateSt(&$g, $bits) {
$p = 1 << $bits;
$g = []; #[[0, 0, 0, 0, false], [1, (1 << $p) -1, 0 ,0, false]];
for ($i=0; $i<$bits; $i++) {
$r = 0;
for ($j=0; $j < $p; $j++) {
if (($j >> $i) & 1 === 1)
$r |= 1 << $j;
}
$g[] = ["v$i", $r, 0, 0, -1, -1, false];
}
}
function gateAdd(&$g, $bits) {
$c = count($g);
$p = 1 << $bits;
$q = (1 << $p) -1 ;
for ($i = 0; $i<$c; $i++) {
$l = $g[$i][1];
gateAdd1($g, "not $i", ~ $l & $q, $i, -1);
for ($j = $i+1; $j<$c; $j++) {
$r = $g[$j][1];
gateAdd1($g, "$i and $j", $l & $r , $i, $j);
gateAdd1($g, "$i or $j", $l | $r , $i, $j);
gateAdd1($g, "$i xor $j", ($l ^ $r) & $q , $i, $j);
}
}
}
function gateAdd1(&$g, $t, $r, $i, $j) {
$de = 1 + max($g[$i][2], $j < 0 ? 0 : $g[$j][2]);
$sz = gateSz($g, $i, $j);
$mv = -1;
foreach($g as $k => $e) {
if ($e[1] !== $r)
continue;
if ($e[2] < $de or $e[3] <= $sz)
return;
$mv = $k;
break;
}
$n = [$t, $r, $de, $sz, $i, $j];
if ($mv === -1) {
$g[] = $n;
return;
}
out("add1 overriting $mv $e[1] $e[2] $e[3] by $r $de $sz");
$g[$mv] = $n;
return;
# not necessary, because depth is not increasing!
foreach($g as $k => &$e) {
if ($e[2] <= 0)
continue;
if ($e[3] === $sz = gateSz($g, $e[4], $e[5]))
continue;
out("$k size from $e[3] ==> $sz");
if ($sz >= $e[3])
err("add1 size increasing after overrite");
$e[3] = $sz;
}
}
function gateSz($g, $i, $j) {
$used = [];
gateSz1($used, $g, $i, $j);
return 1 + count($used);
}
function gateSz1(&$u, $g, $i, $j) {
if ($i >= 0 and $g[$i][2] > 0 and ! isset($u[$i])) {
$u[$i] = 1;
gateSz1($u, $g, $g[$i][4], $g[$i][5]);
}
if ($j >= 0 and $g[$j][2] > 0 and ! isset($u[$j])) {
$u[$j] = 1;
gateSz1($u, $g, $g[$j][4], $g[$j][5]);
}
}
function gateOut($g, $bits, $tr) {
outTB();
outTCF('r', 'l', 'r');
outTRH('cell', 'formula', 'result', 'bin', 'depth', 'size', 'target');
$p = 1 << $bits;
foreach ($g as $i => $e)
outTRD($i, $e[0], $e[1], sprintf("%b", $e[1]), $e[2], $e[3], $tr === $e[1] ? '***': '');
outTbEnd();
}
outBegin('Bit Operators');
errHHAct();
iwIni();
out('envArgs =', envArgs('addC'), envArgs() === envArgO() ? '' : '# default , originally=' . a2str(envArgO()));
out('supported args (uri or commandline) :'
, $argAll = 'mask, bitAdd, bitAddB, bitMul, bitMulInt, bitMulGmp, addR, addC, mul, test, dbg');
#out(hexdec(dechex(-1)));
#out(intA, intL, PHP_INT_MAX, bcPow(2, intW-1), bcPow(2, intW), iwAdd(-1, 0));
#out("maskSrc 1, -1", maskSrc(1), maskSrc(-1));
#out("maskSrc 1234, -890", maskSrc(1234), maskSrc(-890));
out('bcMod( 55, 2)', bcMod( 55, 2), bcMod( 55, -2), bcMod( -55, 2), bcMod( -55, -2));
out('iwAdd( 55, 2)', iwAdd( 55, 2), iwAdd( PHP_INT_MAX, PHP_INT_MAX), iwAdd( PHP_INT_MIN, PHP_INT_MIN));
$testCC = 17;
$dbg = $dbgSet = 0;
$errHHOld = null;
foreach ($argIt = envArgIt() as $argK => $argV) {
$strt = microtime(true);
$cc = 0;
if ($argK === 'bitAdd' or $argK === 'bitAddB' or $argK === 'iwAdd' or $argK === 'addC' or $argK === 'addR' or $argK === 'rlAdd') {
outH($argK);
$assN = $assT = 0;
if ($argK === 'rlAdd') {
rlAddProof();
$dbg=99;
rlAdd(101, 47);
rlAdd(85, 171);
rlAdd(-7567, 11);
rlSub(101, 47);
rlSub(85, 171);
rlSub(-7567, 11);
$dbg=$dbgSet;
}
outTB();
outTCF('l', 'r');
outTRH('op', 'src eq', 'dec', 'hex', 'binary', 'bitCount');
testIni(0, 0);
$testII['errOut'] = function ($msg, $fun, $rEx, $rRe, $l, $r, $xyz='', $lS='', $rS='', $eS='') {global $dbg;
if (! $dbg)
bitTestTRlrs($fun, $lS, $l, $rS, $r, $eS, $rEx);
bitTestTR("$msg", "$fun yields", $rRe);
};
$testII['replay'] = [ function () {
global $dbg;
$dbg=99;
outTRH('replay', 'with dbg' . envAssert(1), '', '', '');
}];
$dbg=max(1, $dbgSet);
testFun($argK, 249, 102, 147);
testFun($argK, 85, 161, -76);
addTestMiMa($argK, 3, 10);
$dbg = $dbgSet;
if ('' !== $sub = $argK === 'rlAdd' ? 'rlSub' : '') {
testFun($sub, 81, 148, 67);
testFun($sub, -76, 85, 161);
}
foreach ([0, 1, 2, 3, 4, 15, 16, 17, 267] as $s)
for ($l = 0; $l <= $s; $l++)
addTestMiMa($argK, $l, $s-$l);
outTBEnd();
$testII['errOut'] = 'testErrOut';
$testII['replay'] = ['testReplay'];
if (substr($argK, 0, 3) === 'bit') {
for ($s=0; $s <= $testCC; $s++)
for ($l = 0; $l <= $s; $l++) {
testFun($argK, $s, $l, $r = $s - $l);
testFun($argK, $l - $r, $l, -$r);
testFun($argK, -$l + $r, -$l, $r);
testFun($argK, -$s, -$l, -$r);
}
} else {
for ($s=0; $s <= $testCC; $s++)
for ($l = 0; $l <= $s; $l++) {
addTestE($argK, $l, $r = $s-$l);
addTestE($argK, $l, -$r);
addTestE($argK, -$l, $r);
addTestE($argK, -$l, -$r);
}
}
if ('' !== $sub) {
for ($s=0; $s <= $testCC; $s++)
for ($l = 0; $l <= $s; $l++) {
$r = $s-$l;
testFun($sub, $l-$r, $l, $r);
testFun($sub, $l+$r, $l, -$r);
testFun($sub, -$l-$r, -$l, $r);
testFun($sub, -$l+$r, -$l, -$r);
}
}
testEnd();
out("assT $assT N $assN");
$cc += $testCnt;
} elseif ($argK === 'rlMul' ) {
outH("$argK");
testIni(0, 0);
$dbg=9;
testFun($argK, 7 + 10 * 5, 2, 7, 10, 5);
testFun($argK, 7, 2, 57, 10, 0, true);
testFun($argK, 137 + 1234 * 987, -1, 137, 1234, 987);
$dbg=$dbgSet;
$q = 0;
for ($s=0; $s <= $testCC; $s++)
for ($l = 0; $l <= $s; $l++) {
$r = $s-$l;
$q = $l === 0 ? 0 : ++$q % $l;
testFun($argK, $l*$r+$q , -1, $q, $l, $r);
}
$ma = maskR[intE-1];
for ($s=0; $s <= $testCC; $s++)
for ($i = 0; $i <= $s; $i++) {
$l = $ma -$i;
$r = $ma - $s + $i;
$q = $l === 0 ? 0 : (++$q % $l);
testFun($argK, iwAdd(iwMul($l, $r), $q) , -1, $q, $l, $r);
}
testEnd();
} elseif ($argK === 'rlDiv' ) {
outH("$argK");
testIni(0, 0);
$dbg=9;
testFun($argK, [5, 7], 2, 57, 10, 0);
testFun($argK, [5, 6], 2, 57, 10, 0);
testFun($argK, [987, 137], -1, 137 + 1234 * 987, 1234);
$dbg=$dbgSet;
$q = 0;
for ($s=0; $s <= $testCC; $s++)
for ($l = 0; $l <= $s; $l++) {
$r = $s-$l;
$q = $l === 0 ? 0 : ++$q % $l;
testFun($argK, $l == 0 ? [1, $l*$r+$q] : [$r, $q], -1, $l*$r+$q, $l);
}
out('div1 end');
$ma = maskR[intE-1];
for ($s=0; $s <= $testCC; $s++)
for ($i = 0; $i <= $s; $i++) {
$l = $ma -$i;
$r = $ma - $s + $i;
$q = $l === 0 ? 0 : (++$q % $l);
testFun($argK, [$r, $q], -1, iwAdd(iwMul($l, $r), $q) , $l);
}
testEnd();
} elseif (substr($argK, 0 ,6) === 'bitMul' or $argK === 'mul') {
outH("$argK");
testIni(0, 0);
$dbg=9;
$argK(235,567);
$dbg=1;
outTB();
outTCF('l', 'r');
outTRH('op', 'src eq', 'dec', 'hex', 'binary', 'bitCount');
bitMulTestMiMa($argK, 5, 3);
bitMulTestMiMa($argK, 6, 255);
$dbg = 0;
foreach ([0, 1, 2, 3, 4, 15, 16, 17, 267] as $s)
for ($l = 0; $l <= $s; $l++)
bitMulTestMiMa($argK, $l, $s-$l);
if (substr($argK, 0, 3) === 'bit') {
for ($s=0; $s <= $testCC; $s++)
for ($l = 0; $l <= $s; $l++) {
$r = $s - $l;
testFun($argK, $l * $r, $l, $r);
testFun($argK, $l * -$r, $l, -$r);
testFun($argK, -$l * $r, -$l, $r);
testFun($argK, -$l * -$r, -$l, -$r);
}
} else { /*
for ($s=0; $s <= $testCC; $s++)
for ($l = 0; $l <= $s; $l++) {
mulTestE($argK, $l, $r = $s-$l);
mulTestE($argK, $l, -$r);
mulTestE($argK, -$l, $r);
mulTestE($argK, -$l, -$r);
} */
}
testEnd();
$cc += $testCnt;
outTBEnd();
} elseif ($argK === 'fredkin') {
rlFredkin(0xfff, 0x33333, 0x50f55);
} elseif ($argK === 'rlCAdd') {
testIni();
$dbg=7;
testFun('rlCAdd', 111, 3, 37, 74, 33);
testFun('rlCAdd', 37, 3, 37, 74, 48);
testFun('rlCAdd', 55, 3, 137, 174, 33);
testFun('rlCAdd', -125, -1, -88, -37, 1);
$dbg = $dbgSet;
for ($s=0; $s <= $testCC; $s++)
for ($l = 0; $l <= $s; $l++) {
$r = $s - $l;
for ($e=0; $e < intE and ((~maskR[$e]) & ($l | $r)) !== 0; $e++) {};
$e2 = ((~maskR[$e]) & ($l + $r)) !== 0 ? $e+1 : -1;
for ($b = 0; $b <= 1; $b++) {
testFun('rlCAdd', ($r + $b * $l) % (1<<(1<<$e)), $e, $r, $l, $b);
testFun('rlCAdd', $r - $b * $l, -1, $r, -$l, $b);
if ($e2 >= 0)
testFun('rlCAdd', $r + $b * $l, $e2, $r, $l, $b);
}
}
testEnd();
} elseif ($argK === 'mask') {
outH('mask');
maskOut();
} elseif ($argK === 'dbg') {
$dbg = $dbgSet = $argV ?? 1;
} elseif ($argK === 'test') {
$testCC = $argV ?? 17;
} elseif ($argK === 'rlAdd') {
rlAdd(101, 47);
rlAdd(85, 171);
rlAdd(-7567, 11);
rlSub(101, 47);
rlSub(85, 171);
rlSub(-7567, 11);
for ($s=0; $s <= $testCC; $s++)
# foreach([0,1,2,3,4,5,7,8,15,16,13,32,33,63,64,65, 257] as $s)
for ($l=0; $l <= $s; $l++) {
$r = $s - $l;
$cc += 8;
rlAdd($l, $r);
rlAdd($l, -$r);
rlAdd(-$l, $r);
rlAdd(-$l, -$r);
rlSub($l, $r);
rlSub($l, -$r);
rlSub(-$l, $r);
rlSub(-$l, -$r);
}
} elseif ($argK === 'gator') {
outH("gate tester");
$g = [];
gateSt($g, 3);
gateAdd($g, 3);
gateAdd($g, 3);
gateAdd($g, 3);
gateOut($g, 3, 232);
outH("log log n adder, classical logic");
} else {
err("bad arg $argK => $argV, supported are $argAll");
}
$ela = microtime(true) - $strt;
if ($dbg or $cc > 0 or $ela > 0.01 or $errHHOld !== $errHHCat)
out("$argK: $cc tests,", sprintf('%8.6f', $ela) . "secs," , $cc<1 ? '' : sprintf('%8.6f', $ela/$cc) . 'secs/test,'
, 'errors=', $errHHOld = $errHHCat);
}
outEnd(__file__);
?>