API tools faq
paste
chadjoan

PHP WideFraction (formerly FixedPoint64) rough sketch rev4

chadjoan
Jul 15th, 2024 (edited)
36
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
PHP 137.00 KB | None | 0 0
raw download clone embed print report
  1. <?php
  2. declare(strict_types=1);
  3.  
  4. namespace Kickback\Common\Exceptions;
  5.  
  6. use \Kickback\Common\Exceptions\CustomException;
  7.  
  8. /*
  9. * Exception that should be thrown whenever any code is called in the `\Kickback\...`
  10. * namespace without having been implemented yet.
  11. */
  12. class UnimplementedException extends CustomException {}
  13. ?>
  14.  
  15. <?php
  16. // The below comments are probably halfway obsolete at this point,
  17. // but mostly because I've been DOING them, and it's been going pretty
  18. // smoothly. The only catch is that I'm starting to realize the scale
  19. // of the task at hand and... ugh. The design is looking pretty good,
  20. // but the implementation will take some work to catch up!
  21. //   2024-07-15 -- Lily
  22. //
  23. // Before 2024-07-15:
  24. //
  25. // Notable future direction for the math stuff:
  26. // Int64 turned into IntNN and began supporting both 32-bit and 64-bit operations.
  27. // Int128 doesn't really have an analogous transform, but it should be possible
  28. // to create operations for that too...
  29. // But the thing that REALLY needs to happen is the creation of 3 bins:
  30. // functions that operate on (algebraically) atomic values, ex: cmp($a,$b)
  31. // functions that operate on values represented in two parts, ex: cmp($ah,$al,  $bh,$bl)
  32. // functions that operate on values represented in _four_ parts, ex: cmp($a3,$a2,$a1,$a0,  $b3,$b2,$b1,$b0)
  33. //
  34. // All of those will be "low level", in a sense:
  35. // It's hard to know dynamically which one to call, because the argument counts change.
  36. //
  37. // So there will need to be abstractions that represent numbers with the correct
  38. // magnitude of parts, and then select the appropriate functions to operate
  39. // on those composites. Such an abstraction might be the FixedPoint64 class.
  40. // (I'm starting to be tempted to call it Rational64, because that's more like
  41. // what it _really_ is, though FixedPoint64 still might reflect its _usage_ better,
  42. // hmmmmmmm.)
  43. // The FixedPoint64 class could represent its internals with as many or as few
  44. // integers as it wants, and could switch between operations based on the
  45. // host system's capabilities.
  46. //
  47. // I think that ideally, the file would be templated and preprocessed by
  48. // PHP code into 2 different class files, with each class implementing
  49. // a different magnitude of integer representation (atomic vs 2-part)
  50. // and calling the appropriate functions as needed. (We'll still need the
  51. // 4-part low-level functions, because doing things like multiplying
  52. // two 2-part numbers will require a 4-part multiplication function!)
  53. //
  54. // If that proves too difficult, then we could just always store FixedPoint64's
  55. // internal representation a 2-parts for each integer. In the 64-bit case,
  56. // one of them will always be unused. (Though, oddly enough, this would
  57. // open the possibility of _128-bit_ fixed-point numbers! Albeit, such things
  58. // would then only work on 64-bit systems and not 32-bit systems, and away
  59. // we go again... until we implement 8-part functions to support 128-bit
  60. // numbers on 32-bit systems. We'll be tempted to use the 256-bit math
  61. // that's now available on 64-bit systems, and then need to implement
  62. // 16-part functions as a way to make 256-bit math compatible with 32-bit
  63. // systems. OH NO OWN GOAL (etc)
  64. // Really, we'll probably just say 64-bit FixedPoint/Rational is good enough
  65. // for now, and we'll expand to 128-bit ONLY if we have a reason to.
  66. // But it'll at least be totally doable, with established patterns to guide
  67. // how it'd be done!)
  68. //
  69. // final class IntX1
  70. // {
  71. // }
  72. //
  73. // final Class IntX2
  74. // {
  75. // }
  76. //
  77. // // Everything from X4 up is probably template-able.
  78. // final class IntX4
  79. // {
  80. // }
  81. //
  82. // // Implement this to enable 128-bit multiplies on 32-bit arch.
  83. // final class IntX8
  84. // {
  85. // }
  86. //
  87.  
  88. /*
  89. declare(strict_types=1);
  90.  
  91. namespace Kickback\Common\Math;
  92. */
  93. final class Testing
  94. {
  95.     /*
  96.     * Apparently PHP devs made it _really_ hard for the `assert` statement to
  97.     * actually halt or report errors when triggered:
  98.     * https://stackoverflow.com/questions/40129963/assert-is-not-working-in-php-so-simple-what-am-i-doing-wrong
  99.     *
  100.     * So here's a version that Just Works.
  101.     *
  102.     * We should probably make sure it turns off in production mode.
  103.     * Right now it just always goes.
  104.     */
  105.     public static function _assert(bool $expr, string $msg = "An assertion was triggered.") : void
  106.     {
  107.         if ( !$expr ) {
  108.             throw new \AssertionError($msg);
  109.         }
  110.     }
  111.  
  112.     // Prevent instantiation/construction of the (static/constant) class.
  113.     /** @return never */
  114.     private function __construct() {
  115.         throw new \Exception("Instantiation of static class " . get_class($this) . "is not allowed.");
  116.     }
  117. }
  118. ?>
  119.  
  120. <?php
  121. /*
  122. declare(strict_types=1);
  123.  
  124. namespace Kickback\Common\Math\LowLevel;
  125. */
  126.  
  127. // TODO: The WideIntX1 class below will end up templated, so that we can
  128. // operate on integers of arbitrary width.
  129.  
  130. /**
  131. * `WideIntX1` is the base-case for an implementation of wide integers in PHP.
  132. *
  133. * Wide integers are integer types with a fixed-width, but a fixed-width that
  134. * is longer/wider than the host language's native integer type(s).
  135. *
  136. * In PHP, there is only one (native/builtin) integer type (`int`), and
  137. * its width (presumably) depends on the size of arithmetic integers on
  138. * the host system (so 32-bit integers when PHP is executed on a 32-bit CPU,
  139. * or 64-bit integers if PHP is executed on a 64-bit CPU).
  140. *
  141. * All operations in the WideIntN family will be implemented according to
  142. * twos-complement arithmatic. This is, notably, NOT what PHP's built-in
  143. * integer type does. At least, not always. PHP's `int` type will use
  144. * twos-complement most of the time, but when an integer expression causes
  145. * _signed_ overflow (including, informally, "underflow"), then
  146. *
  147. */
  148. final class WideIntX1
  149. {
  150.     // =========================================================================
  151.     // The below comments relate to the `add_with_carry` function (and, by
  152.     // extension, the `add` function.) These comments are placed outside
  153.     // of the function to reduce clutter between procedural steps, and
  154.     // also to make things faster if the function ever gets reparsed
  155.     // multiple times for any reason (ex: cheap metaprogramming techniques).
  156.     //
  157.     // We want to detect overflow during addition or subtraction in some cases.
  158.     //
  159.     // This function also gives us a chance to ensure that (int+int) addition
  160.     // will always return an `int`, because the `+` operator doesn't actually
  161.     // do that by default in PHP! (It usually will, but not if the result overflows.)
  162.     //
  163.     // In cases where there is a signed integer overflow, PHP will convert the
  164.     // result of the addition into a floating point number. This is not what
  165.     // we want when we expect ordinary twos-complement addition. Though we CAN
  166.     // use this fact, along with the `is_int()` function, to detect all
  167.     // signed overflow.
  168.     //
  169.     // In the case of unsigned integer overflow, we will need to detect it
  170.     // separately using bitwise logic exclusively.
  171.     //
  172.     // The bitwise logic for unsigned overflow detection is as follows:
  173.     //
  174.     // In the below table, `a` and `b` are the inputs. `c` is the result of
  175.     // the addition (after correcting any of PHP's signed-overflow-float-conversion).
  176.     // And `r` is the unsigned carry.
  177.     //
  178.     // To derive our truth table, we observe what happens when we add two
  179.     // 2-bit numbers together to yield a 3-bit number. The most-significant bit (msb)
  180.     // of the 3-bit number will tell us if an overflow occurs.
  181.     //
  182.     // To help us analyse a bit further, we also write a 2nd table to the
  183.     // right of the 1st one, and write down the same expression with only
  184.     // the 2nd bit shown for each variable.
  185.     //
  186.     //  a + b =  c  : a+b = c
  187.     //  00+00 = 000 : 0+0 = 0 -> no carry
  188.     //  00+01 = 001 : 0+0 = 0 -> no carry
  189.     //  00+10 = 010 : 0+1 = 1 -> no carry
  190.     //  00+11 = 011 : 0+1 = 1 -> no carry
  191.     //  01+00 = 001 : 0+0 = 0 -> no carry
  192.     //  01+01 = 010 : 0+0 = 1 -> no carry
  193.     //  01+10 = 011 : 0+1 = 1 -> no carry
  194.     //  01+11 = 100 : 0+1 = 0 -> overflow|carry (unsigned)
  195.     //  10+00 = 010 : 1+0 = 1 -> no carry
  196.     //  10+01 = 011 : 1+0 = 1 -> no carry
  197.     //  10+10 = 100 : 1+1 = 0 -> overflow|carry (unsigned)
  198.     //  10+11 = 101 : 1+1 = 0 -> overflow|carry (unsigned)
  199.     //  11+00 = 011 : 1+0 = 1 -> no carry
  200.     //  11+01 = 100 : 1+0 = 0 -> overflow|carry (unsigned)
  201.     //  11+10 = 101 : 1+1 = 0 -> overflow|carry (unsigned)
  202.     //  11+11 = 110 : 1+1 = 1 -> overflow|carry (unsigned)
  203.     //
  204.     // Notably, the less significant bit of these numbers is inconsequental
  205.     // for unsigned carry detection (as long as we have `c`).
  206.     // We only need to concern ourselves with the most significant bits!
  207.     //
  208.     // If we then eliminate the duplicate rows in the msb-only table,
  209.     // we end up with this:
  210.     //
  211.     //  a+b = c
  212.     //  0+0 = 0 -> no carry
  213.     //  0+0 = 1 -> no carry
  214.     //  0+1 = 0 -> overflow|carry (unsigned)
  215.     //  0+1 = 1 -> no carry
  216.     //  1+0 = 0 -> overflow|carry (unsigned)
  217.     //  1+0 = 1 -> no carry
  218.     //  1+1 = 0 -> overflow|carry (unsigned)
  219.     //  1+1 = 1 -> overflow|carry (unsigned)
  220.     //
  221.     // The above generalizes to all integers with larger bit-widths, because
  222.     // we can always use right-bit-shift to discard everything besides the
  223.     // most significant bit.
  224.     //
  225.     // Now we know the relationship between the `a-b-c` msbs, and the
  226.     // carry-or-not status, which we'll call `r` in our truth table.
  227.     //
  228.     // Truth table that we want:
  229.     //
  230.     // : a b c : r :
  231.     // -------------
  232.     // : 0 0 0 : 0 :
  233.     // : 0 0 1 : 0 :
  234.     // : 0 1 0 : 1 :
  235.     // : 0 1 1 : 0 :
  236.     // : 1 0 0 : 1 :
  237.     // : 1 0 1 : 0 :
  238.     // : 1 1 0 : 1 :
  239.     // : 1 1 1 : 1 :
  240.     //
  241.     // Now we'll test expressions in our truth table until we find something
  242.     // that matches `r` by applying bitwise operations to `a`, `b`, and `c`:
  243.     //
  244.     // : a b c : r : ~c : (a|b) : (a&b) : (a|b)&~c : (a&b)|((a|b)&~c) :
  245.     // ----------------------------------------------------------------
  246.     // : 0 0 0 : 0 :  1 :   0   :   0   :     0    :        0         :
  247.     // : 0 0 1 : 0 :  0 :   0   :   0   :     0    :        0         :
  248.     // : 0 1 0 : 1 :  1 :   1   :   0   :     1    :        1         :
  249.     // : 0 1 1 : 0 :  0 :   1   :   0   :     0    :        0         :
  250.     // : 1 0 0 : 1 :  1 :   1   :   0   :     1    :        1         :
  251.     // : 1 0 1 : 0 :  0 :   1   :   0   :     0    :        0         :
  252.     // : 1 1 0 : 1 :  1 :   1   :   1   :     1    :        1         :
  253.     // : 1 1 1 : 1 :  0 :   1   :   1   :     0    :        0         :
  254.     //
  255.     // We have now learned that the expression `(a&b)|((a|b)&~c)` will always
  256.     // predict the correct value for `r`, which is unsigned carry (overflow).
  257.     //
  258.     // This is probably not the most optimal expression, but it may very well
  259.     // be pretty close. We'd need to simplify aggressively to get any better,
  260.     // and it probably won't matter anyways. Most importantly, we can correctly
  261.     // guess the unsigned carry flag after computing an unsigned addition.
  262.     //
  263.     // In the below add and subtract functions, `a`, `b`, and `c` all have
  264.     // the same name, and `r` is represented by the variable `$u_carry`.
  265.     //
  266.     // We can apply the above expression to entire {32|64}-bit integers, and the
  267.     // sign bits in the integers will have the exact same outcomes as in
  268.     // the above truth table.
  269.     //
  270.     // Then we'll need to bit-shift-right by all bits but one
  271.     // (63 bits in the 64-bit case, or 31 bits in the 32-bit case)
  272.     // to get a {0,1} set indicating no carry (0) or carry (1):
  273.     // `$u_carry = (($a&$b)|(($a|$b)&~$c)) >> {31|63};`
  274.     //
  275.     // However, because PHP does not provide an _unsigned_ shift-right,
  276.     // any shift-right on a value with a set sign-bit (sign=1) will result
  277.     // in the variable being filled with 1s.
  278.     //
  279.     // So after the bit-shift, `$u_carry` will either be 0 or it will be 0xFFFF...FFFF.
  280.     // But we want it to be 0 or 1.
  281.     //
  282.     // So we can clear the sign extension bits by ANDing with 1:
  283.     // `$u_carry = (1 & ((($a&$b)|(($a|$b)&~$c)) >> {31|63}));`
  284.  
  285.     private const NUM_BITS_IN_INT = PHP_INT_SIZE*8;
  286.     private const SIGN_SHIFT = (self::NUM_BITS_IN_INT - 1);
  287.     private const HALF_SHIFT = (self::NUM_BITS_IN_INT >> 1);
  288.     private const HALF_MASK  = ((1 << self::HALF_SHIFT)-1);
  289.  
  290.     public static function add(int $a, int $b) : int
  291.     {
  292.         $s_carry = (int)0;
  293.         $u_carry = (int)0;
  294.         return self::subtract_with_borrow($a, $b, $s_carry, $u_carry);
  295.     }
  296.  
  297.     public static function add_with_carry(int $a, int $b, int &$s_carry, &$u_carry) : int
  298.     {
  299.         $c = $a + $b;
  300.  
  301.         if ( is_int($c) ) {
  302.             // Most common branch.
  303.             $u_carry = (1 & ((($a&$b)|(($a|$b)&~$c)) >> self::SIGN_SHIFT));
  304.             $s_carry = 0;
  305.             //echo(sprintf("add_with_carry: a=%016X, b=%016X, c=%016X, (a&b)=%016X, ((a|b)&~c)=%016X, carry=%016X\n", $a, $b, $c, ($a&$b), (($a|$b)&~$c), $u_carry));
  306.             return $c;
  307.         } else {
  308.             // !is_int($c)
  309.             // Uncommon branch: signed overflow.
  310.             $s_carry = 1;
  311.             return self::add_by_halves($a,$b,$u_carry);
  312.         }
  313.     }
  314.  
  315.     // An earlier (and non-working) version of the above function used
  316.     // the below bit-twiddle expressions, from
  317.     //   https://grack.com/blog/2022/12/20/deriving-a-bit-twiddling-hack/
  318.     // to check for overflow. I didn't notice at the time, but these turned
  319.     // out to be for SIGNED overflow detection. Since PHP does that for us
  320.     // (and _to_ us, even), we won't need bit twiddles for the signed case.
  321.     // So we won't be needing these:
  322.     //$carry = ((($c ^ $a) & ($c ^ $b)) >> 63);
  323.     //$carry = ((~($a ^ $b) & ($c ^ $a)) >> 63);
  324.  
  325.     // =========================================================================
  326.     // `add_by_halves(int a, int b, int u_carry):int`
  327.     //
  328.     // Slow-but-accurate addition function that breaks a 64-bit integer
  329.     // into two 32-bit parts (lo and hi halves), then adds them together.
  330.     // The result of each addition is 33-bits wide, but that fits just
  331.     // fine into a 64-bit integer. After carry propagation, the (lo and hi)
  332.     // halves are reassembled into the final 64-bit integer.
  333.     //
  334.     // This is potentially more complicated and slow than the "just use `+`"
  335.     // function, but it has the tremendous advantage of never converting
  336.     // the final result into a floating point number with incorrect contents.
  337.     // (PHP will automatically convert the result of integer expressions
  338.     // into a floating point value if the integer expression results in
  339.     // a signed overflow.)
  340.     //
  341.     // Since this function already needs to do carry propagation, it can
  342.     // return the unsigned carry status in the `&$u_carry` parameter
  343.     // as a free action.
  344.     //
  345.     // Signed carry is not as trivial, so it is not performed here.
  346.     // (It's still potentially very "easy", but it should probably be
  347.     // computed by the caller only if it's needed.)
  348.     //
  349.     private static function add_by_halves(int $a, int $b, &$u_carry) : int
  350.     {
  351.         // Shorthand:
  352.         $half_mask  = self::HALF_MASK;  // =0xFFFF on 32-bit host, and =0xFFFF_FFFF on 64-bit host.
  353.         $half_shift = self::HALF_SHIFT; // =16 when on 32-bit host, and =32 when on 64-bit host.
  354.  
  355.         // Unpack $a:
  356.         $al = $a & $half_mask;   // $al : Low  {16|32} bits of $a
  357.         $ah = $a >> $half_shift; // $ah : High {16|32} bits of $a
  358.         $ah &= $half_mask;       // Leave space in $ah for carry/overflow detection.
  359.  
  360.         // Unpack $b:
  361.         $bl = $b & $half_mask;   // $bl : Low  {16|32} bits of $b
  362.         $bh = $b >> $half_shift; // $bh : High {16|32} bits of $b
  363.         $bh &= $half_mask;       // Leave space in $bh for carry/overflow detection.
  364.  
  365.         // Part-wise addition:
  366.         $cl = $al + $bl; // $cl : Low  {16|32} bits of result from $a+$b
  367.         $ch = $ah + $bh; // $ch : High {16|32} bits of result from $a+$b, so far unadjusted for carry propagation.
  368.  
  369.         // Propagate low-carry into $ch:
  370.         $carry_lo = ($cl >> $half_shift);
  371.         $ch += $carry_lo;
  372.  
  373.         // Detect unsigned carry from the entire result:
  374.         $carry_hi = ($ch >> $half_shift);
  375.         //echo(sprintf("add_by_halves: ah=%016X, al=%016X, bh=%016X, bl=%016X, ch=%016X, cl=%016X, carry_hi=%016X, carry_lo=%016X\n", $ah,$al,  $bh,$bl,  $ch,$cl,  $carry_hi,$carry_lo));
  376.  
  377.         // Pack the result back into a single integer:
  378.         $c = ($ch << $half_shift) | ($cl & $half_mask);
  379.         //echo(sprintf("add_by_halves: a=%016X, b=%016X, c=%016X, carry=%016X\n", $a, $b, $c, $carry_hi));
  380.  
  381.         // Return results:
  382.         $u_carry = $carry_hi;
  383.         return $c;
  384.     }
  385.  
  386.     public static function unittest_add_with_carry() : void
  387.     {
  388.         echo(__CLASS__."::".__FUNCTION__."...");
  389.  
  390.         // Shorthand to avoid having to write out long 64-bit hex values.
  391.         $x0000 = (int)0;
  392.         $x0001 = (int)1;
  393.         $x0002 = (int)2;
  394.         $x8000 = PHP_INT_MIN;
  395.         $x8001 = PHP_INT_MIN+1;
  396.         $xFFFF = (int)-1;
  397.         $xFFFE = (int)-2;
  398.         $x7FFF = PHP_INT_MAX;
  399.         $x7FFE = PHP_INT_MAX-1;
  400.  
  401.         $s_carry = (int)0;
  402.         $u_carry = (int)0;
  403.  
  404.         Testing::_assert($x0000 === self::add_with_carry($x0000,$x0000,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(0 === $u_carry);
  405.         Testing::_assert($x0001 === self::add_with_carry($x0000,$x0001,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(0 === $u_carry);
  406.         Testing::_assert($x0001 === self::add_with_carry($x0001,$x0000,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(0 === $u_carry);
  407.         Testing::_assert($x0002 === self::add_with_carry($x0001,$x0001,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(0 === $u_carry);
  408.  
  409.         Testing::_assert($x0000 === self::add_with_carry($x0000,$x0000,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(0 === $u_carry);
  410.         Testing::_assert($xFFFF === self::add_with_carry($x0000,$xFFFF,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(0 === $u_carry);
  411.         Testing::_assert($xFFFF === self::add_with_carry($xFFFF,$x0000,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(0 === $u_carry);
  412.         Testing::_assert($xFFFE === self::add_with_carry($xFFFF,$xFFFF,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(1 === $u_carry);
  413.  
  414.         Testing::_assert($x0000 === self::add_with_carry($x0001,$xFFFF,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(1 === $u_carry);
  415.         Testing::_assert($x7FFF === self::add_with_carry($xFFFF,$x8000,$s_carry,$u_carry));
  416.         Testing::_assert(1 === $s_carry);
  417.         Testing::_assert(1 === $u_carry); // PHP Math is b0rked?! It says 0xFFFF...FFFF + 0x8000...0000 === 0x8000...0000, which is WRONG. It should return 0x7FFF...FFFF.
  418.  
  419.         Testing::_assert($x0001 === self::add_with_carry($x0002,$xFFFF,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(1 === $u_carry);
  420.         Testing::_assert($x7FFE === self::add_with_carry($xFFFE,$x8000,$s_carry,$u_carry)); Testing::_assert(1 === $s_carry); Testing::_assert(1 === $u_carry); // PHP Math is b0rked?!
  421.  
  422.         Testing::_assert($x8000 === self::add_with_carry($x8001,$xFFFF,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(1 === $u_carry);
  423.         Testing::_assert($x7FFE === self::add_with_carry($x7FFF,$xFFFF,$s_carry,$u_carry)); Testing::_assert(0 === $s_carry); Testing::_assert(1 === $u_carry);
  424.  
  425.         echo(" done.\n");
  426.     }
  427.  
  428.     public static function subtract(int $a, int $b) : int
  429.     {
  430.         $s_borrow = (int)0;
  431.         $u_borrow = (int)0;
  432.         return self::subtract_with_borrow($a, $b, $s_borrow, $u_borrow);
  433.     }
  434.  
  435.     public static function subtract_with_borrow(int $a, int $b, int &$s_borrow, &$u_borrow) : int
  436.     {
  437.         $c = $a - $b;
  438.  
  439.         //echo(sprintf("a=%016X, b=%016X, c=%016X, (a&b)=%016X, ((a|b)&~c)=%016X, carry=%016X\n", $a, $b, $c, ($a&$b), (($a|$b)&~$c), $carry));
  440.  
  441.         if ( is_int($c) ) {
  442.             // Most common branch.
  443.             $u_borrow = (1 & ((($a&$b)|(($a|$b)&~$c)) >> self::SIGN_SHIFT)); // TODO: CHECK THIS LOGIC. It might be different for subtraction?
  444.             $s_borrow = 0;
  445.             return $c;
  446.         } else {
  447.             // !is_int($c)
  448.             // Uncommon branch: signed overflow.
  449.             $s_borrow = 1;
  450.             return self::subtract_by_halves($a,$b,$u_borrow);
  451.         }
  452.     }
  453.  
  454.     // Pretty much the same thing as `add_by_halves`, except for subtraction.
  455.     private static function subtract_by_halves(int $a, int $b, &$u_borrow) : int
  456.     {
  457.         // Shorthand:
  458.         $half_mask  = self::HALF_MASK;  // =0xFFFF on 32-bit host, and =0xFFFF_FFFF on 64-bit host.
  459.         $half_shift = self::HALF_SHIFT; // =16 when on 32-bit host, and =32 when on 64-bit host.
  460.  
  461.         // Unpack $a:
  462.         $al = $a & $half_mask;   // $al : Low  {16|32} bits of $a
  463.         $ah = $a >> $half_shift; // $ah : High {16|32} bits of $a
  464.         $ah &= $half_mask;       // Leave space in $ah for borrow/overflow detection.
  465.  
  466.         // Unpack $b:
  467.         $bl = $b & $half_mask;   // $bl : Low  {16|32} bits of $b
  468.         $bh = $b >> $half_shift; // $bh : High {16|32} bits of $b
  469.         $bh &= $half_mask;       // Leave space in $bh for borrow/overflow detection.
  470.  
  471.         // Part-wise subtraction:
  472.         $cl = $al - $bl; // $cl : Low  {16|32} bits of result from $a+$b
  473.         $ch = $ah - $bh; // $ch : High {16|32} bits of result from $a+$b, so far unadjusted for borrow propagation.
  474.  
  475.         // Propagate low-borrow into $ch:
  476.         $borrow_lo = (($cl >> $half_shift) & 1);
  477.         $ch -= $borrow_lo;
  478.  
  479.         // Detect unsigned borrow from the entire result:
  480.         $borrow_hi = (($ch >> $half_shift) & 1);
  481.  
  482.         // Pack the result back into a single integer:
  483.         $c = ($ch << $half_shift) | ($cl & $half_mask);
  484.  
  485.         // Return results:
  486.         $u_borrow = $borrow_hi;
  487.         return $c;
  488.     }
  489.  
  490.     public static function unittest_subtract_with_borrow()
  491.     {
  492.         echo(__CLASS__."::".__FUNCTION__."...");
  493.         echo(" UNIMPLEMENTED! (Please fix!)\n");
  494.     }
  495.  
  496.     /*
  497.     * It is probably better to use `multiply_64x64` in most cases.
  498.     *
  499.     * This is the underlying implementation of `multiply_64x64`, and having
  500.     * it separated out as a different function is useful for testing purposes.
  501.     */
  502.     public static function multiply_(int $digit_bit_width,  int $a, int $b,  int &$out_hi, int &$out_lo) : void
  503.     {
  504.         Testing::_assert($digit_bit_width <= 32);
  505.         $mask_lo = ((1 << $digit_bit_width) - 1);
  506.         $max_digit = $mask_lo;
  507.  
  508.         // Reorganize the two 64-bit integers into four 32-bit integers.
  509.         // This helps because now the 32-bit integers will have at least
  510.         // 32 bits of "headroom" for doing multiplications.
  511.         $a_lo = $a & $mask_lo;
  512.         $a_hi = $a >> $digit_bit_width;
  513.         $b_lo = $b & $mask_lo;
  514.         $b_hi = $b >> $digit_bit_width;
  515.  
  516.         // Multiplies. We need 4 of them for a school-style long multiply.
  517.         // There are faster methods, but this will do for now.
  518.         //
  519.         // Graphically:
  520.         //                a_hi  a_lo
  521.         //             x  b_hi  b_lo
  522.         //             -------------
  523.         //                x_hi  x_lo
  524.         //          y_hi  y_lo
  525.         //          z_hi  z_lo
  526.         // +  w_hi  w_lo
  527.         // -----------------------
  528.         //    ????  ????  ????  ????
  529.         //
  530.         // Note that these multiplications, or at least the ones involving
  531.         // the $*_lo operands, must be _unsigned_ multiplications.
  532.         // However, because these are 32-bit values stored in 64-bit variables,
  533.         // the sign bit will _never_ be set, so it won't matter if we
  534.         // use a 64-bit signed multiplication on them.
  535.         //
  536.         $x = $a_lo * $b_lo;
  537.         $y = $a_lo * $b_hi;
  538.         $z = $a_hi * $b_lo;
  539.         $w = $a_hi * $b_hi;
  540.         // TODO: BUG? If the above multiplies cause a signed overflow, PHP will probably convert the result to a `float`!
  541.  
  542.         // To make the logic more clear, we will also define the
  543.         // variables corresponding to the {x,y,z,w}_{hi,lo} placeholders.
  544.         $x_lo = $x & $mask_lo;
  545.         $y_lo = $y & $mask_lo;
  546.         $z_lo = $z & $mask_lo;
  547.         $w_lo = $w & $mask_lo;
  548.  
  549.         $x_hi = $x >> $digit_bit_width;
  550.         $y_hi = $y >> $digit_bit_width;
  551.         $z_hi = $z >> $digit_bit_width;
  552.         $w_hi = $w >> $digit_bit_width;
  553.  
  554.         // PHP doesn't provide an unsigned right-shift, so we must clear
  555.         // any sign-extended bits in things that were right-shifted.
  556.         $x_hi = $x & $mask_lo;
  557.         $y_hi = $y & $mask_lo;
  558.         $z_hi = $z & $mask_lo;
  559.         $w_hi = $w & $mask_lo;
  560.  
  561.         // Calculate the bottom row of 32-bit integers.
  562.         //
  563.         // Note that some of these additions might "overflow", but
  564.         // because we are storing our 32-bit integers in 64-bit variables,
  565.         // the carry values will be captured.
  566.         //
  567.         // These will get shuffled into the output integers
  568.         // once the accumulation is done.
  569.         //
  570.         // Graphically:
  571.         //                a_hi  a_lo
  572.         //             x  b_hi  b_lo
  573.         //             -------------
  574.         //                x_hi  x_lo
  575.         //          y_hi  y_lo
  576.         //          z_hi  z_lo
  577.         // +  w_hi  w_lo
  578.         // -----------------------
  579.         //    out3  out2  out1  out0
  580.         //
  581.         $out0 = $x_lo;
  582.         $out1 = $x_hi + $y_lo + $z_lo;
  583.         $out2 = $y_hi + $z_hi + $w_lo;
  584.         $out3 = $w_hi;
  585.  
  586.         // Perform carry operations.
  587.         // (Beware: order-of-operations is important.)
  588.         if ( $out1 > $max_digit )
  589.         {
  590.             $out2 += ($out1 >> $digit_bit_width);
  591.             $out1 &= $mask_lo;
  592.         }
  593.  
  594.         if ( $out2 > $max_digit )
  595.         {
  596.             $out3 += ($out2 >> $digit_bit_width);
  597.             $out2 &= $mask_lo;
  598.         }
  599.         // Note that $out3 is involved in an addition, but won't generate
  600.         // a carry-out. It won't overflow, for math reasons.
  601.  
  602.         // Now we have four proper 32-bit integers (two pairs) with no carry bits,
  603.         // so we can concatenate the pairs to get two 64-bit integers and have our 128-bit result.
  604.         $lo = $out0 | ($out1 << $digit_bit_width);
  605.         $hi = $out2 | ($out3 << $digit_bit_width);
  606.  
  607.         // Return our results from the function.
  608.         $out_lo = $lo;
  609.         $out_hi = $hi;
  610.     }
  611.  
  612.     public static function unittest() : void
  613.     {
  614.         echo("Unittests for ".__CLASS__."\n");
  615.         self::unittest_add_with_carry();
  616.         self::unittest_subtract_with_borrow();
  617.         echo("\n");
  618.     }
  619. }
  620. ?>
  621.  
  622. <?php
  623. /*
  624. declare(strict_types=1);
  625.  
  626. namespace Kickback\Common\Math\LowLevel;
  627.  
  628. use \Kickback\Common\Math\LowLevel\WideIntX1;
  629. */
  630. final class WideIntX2
  631. {
  632.     private const MASK_LO = ((1 << 32) - 1);
  633.     private const MASK_SIGN = (1 << 63);
  634.  
  635.     // Below is a branchless implementation of a comparison algorithm for
  636.     // a comparison operation on 128-bit integers that area each specified
  637.     // as `hi` and `lo` 64-bit integers.
  638.     //
  639.     // This probably doesn't need to be branchless, and I doubt that PHP code
  640.     // will benefit from that very much.
  641.     //
  642.     // I'm mostly just practicing my skill at writing branchless code, because
  643.     // it is a useful skill to have in other places.
  644.     //
  645.     // I'm still going to use the branchless version because (1) it works
  646.     // and (2) it _might_ help somewhere. It's probably the best way to do things.
  647.     // The only disadvantage would be that it just took longer to write.
  648.     //
  649.     // -- Lily Joan  2024-07-11
  650.     //
  651.     //
  652.     // With the personal statement out of the way, here's out it actually works:
  653.     //
  654.     // The code looks like this:
  655.     //
  656.     // $d1 = $a_hi - $b_hi;
  657.     // $d0 = $a_lo - $b_lo;
  658.     //
  659.     // // Set all bits of `$mask` to 1 if p is nonzero.
  660.     // // Clear all bits if p is zero.
  661.     // $mask = ($d1 | -$d1) >> 63;
  662.     //
  663.     // $r = $d1 | ($d0 & ~$mask);
  664.     //
  665.     // $p = $r >> 63;
  666.     // $q = ~($r-1) >> 63
  667.     //
  668.     // return ($p-$q)|$p;
  669.     //
  670.     // =========================================================================
  671.     // ================== $mask = ($d1 | -$d1) >> 63; ==========================
  672.     // The statement `$mask = ($d1 | -$d1) >> 63;` calculates a mask that is all 1s
  673.     // whenever `$d1` is non-zero, and all 0s whenever `$d1` is zero.
  674.     //
  675.     // The first step to understanding this is to realize that the subexpression
  676.     // `($d1 | -$d1)` will, for non-zero inputs, ALWAYS have its sign-bit set.
  677.     // For the input of zero, it will have its sign-bit clear.
  678.     //
  679.     // It does this by exploiting the fact that the number 0 is neither positive nor
  680.     // negative. Here are the possibilities:
  681.     // :    $d1    : sign($d1) :   -$d1     : sign(-$d1) : sign($d1) | sign(-$d1) :
  682.     // ----------------------------------------------------------------------------
  683.     // : $d1  >  0 :    0      : -$d1  <  0 :     1      :           1            :
  684.     // : $d1 === 0 :    0      : -$d1 === 0 :     0      :           0            :
  685.     // : $d1  <  0 :    1      : -$d1  >  0 :     0      :           1            :
  686.     //
  687.     // Once we have a sign bit that is 1 for all (and only) non-zero inputs,
  688.     // we can shift the value to the right by at least 63 bits to sign-extend the
  689.     // the sign bit to fill the entire variable.
  690.     //
  691.     // Here's another truth table showing what happens for 2-bit integers:
  692.     //
  693.     // :             $d1             : 00 : 01 : 10 : 11 :
  694.     // ---------------------------------------------------
  695.     // :            -$d1             : 00 : 10 : 10 : 01 :
  696.     // :          $d1 | -$d1         : 00 : 11 : 10 : 11 :
  697.     // : ($d1 | -$d1) >> (#bits - 1) : 00 : 11 : 11 : 11 :
  698.     //
  699.     // =========================================================================
  700.     // ================== $r = $d1 | ($d0 & ~$mask); ===========================
  701.     // The statement `$r = $d1 | ($d0 & ~$mask);` selects which "digit" of
  702.     // the 128-bit operands is being used for comparison. It uses information
  703.     // in `$mask` to ensure it picks the high parts if they differ, and
  704.     // picks the low parts if the high parts are equal.
  705.     //
  706.     // The full expression would look more like this:
  707.     //   `($d1 & $mask) | ($d0 & ~$mask);`
  708.     //
  709.     // We can simplify it to
  710.     //   `$d1 | ($d0 & ~$mask)`
  711.     // by noting that $mask is derived from $d1 and will always be 0 when
  712.     // $d1 is 0. As such, there is no reason to AND the two together,
  713.     // because it will never alter the resulting value.
  714.     //
  715.     // (thought discontinued)
  716.  
  717.  
  718.  
  719.     // Other notes, most about how to derive p and q logic:
  720.     // :    p    : 00 : 01 : 10 : 11 : 00 : 01 : 10 : 11 : 00 : 01 : 10 : 11 : 00 : 01 : 10 : 11 :
  721.     // :    q    : 00 : 00 : 00 : 00 : 01 : 01 : 01 : 01 : 10 : 10 : 10 : 10 : 11 : 11 : 11 : 11 :
  722.     // :    m    : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 : 00 :
  723.     // -------------------------------------------------------------------------------------------
  724.     // :  p ^ q  : 00 : 01 : 10 : 11 : 01 : 00 : 11 : 10 : 10 : 11 : 00 : 01 : 11 : 10 : 01 : 00 :
  725.     //
  726.     //
  727.     // : p | -p  : 00 : 11 : 10 : 11 :
  728.     // : >> bits : 00 : 11 : 11 : 11 :
  729.     //
  730.     // $p = $r >> 63
  731.     //
  732.     // >0 =0 <0 min
  733.     // 00 00 11 11 r >> 63 == p
  734.     // //00 11 11 00 r-1 >> 63
  735.     // 11 00 00 11 ~(r-1) >> 63 == q
  736.     // //11 00 11 00 p^q
  737.     // //00 00 00 11 p&q
  738.     // //11 00 11 11 p|q
  739.     // 01 00 11 00 p-q
  740.     // 01 00 11 11 (p-q)|p
  741.  
  742.     /*
  743.     *  Returns -1, 0, or 1 based on a comparison of the given 128-bit integers.
  744.     *
  745.     *  Defined such that:
  746.     *  * a < b implies cmp(a,b) < 0
  747.     *  * a > b implies cmp(a,b) > 0
  748.     *  * a == b implies cmp(a,b) == 0.
  749.     */
  750.     public static function cmp(int $a_hi, int $a_lo,   int $b_hi, int $b_lo) : int
  751.     {
  752.         // TODO: BUG: Needs work to support integers with parts >PHP_INT_MAX
  753.         // (Thus it currently does not pass unittests.)
  754.         // (We'll probably end up looking at u_carry flags. This is a common
  755.         // technique for assembly/CPUs to detect if one number is larger
  756.         // than another: just subtract them and see if a borrow flag is set!)
  757.         // TODO: Also, we should have signed+unsigned versions of this!
  758.         $d1 = IntNN::subtract($a_hi, $b_hi);
  759.         $d0 = IntNN::subtract($a_lo, $b_lo);
  760.  
  761.         // Set all bits of `$mask` to 1 if p is nonzero.
  762.         // Clear all bits if p is zero.
  763.         $mask = ($d1 | -$d1) >> 63;
  764.  
  765.         $r = $d1 | ($d0 & ~$mask);
  766.  
  767.         $p = $r >> 63;
  768.         $q = ~($r-1) >> 63;
  769.         $r2 = (($p-$q)|$p);
  770.         echo(sprintf("\nd1=%016X, d0=%016X, mask=%016X, r=%016X, p=%016X, q=%016X, r2=%016X", $d1,$d0, $mask, $r, $p, $q, $r2));
  771.  
  772.         return $r2;
  773.     }
  774.  
  775.     public static function unittest_cmp()
  776.     {
  777.         echo(__CLASS__."::".__FUNCTION__."...");
  778.  
  779.         Testing::_assert(self::cmp( 0, 0,   0, 0) === 0);
  780.         Testing::_assert(self::cmp( 0, 0,   0, 1)  <  0);
  781.         Testing::_assert(self::cmp( 0, 1,   0, 0)  >  0);
  782.         Testing::_assert(self::cmp( 0, 1,   0, 1) === 0);
  783.         Testing::_assert(self::cmp(-1, 0,  -1, 0) === 0);
  784.         Testing::_assert(self::cmp(-1, 0,   0, 0)  <  0);
  785.         Testing::_assert(self::cmp(-1, 0,   1, 0)  <  0);
  786.         Testing::_assert(self::cmp( 0, 0,  -1, 0)  >  0);
  787.         Testing::_assert(self::cmp( 0, 0,   0, 0) === 0);
  788.         Testing::_assert(self::cmp( 0, 0,   1, 0)  <  0);
  789.         Testing::_assert(self::cmp( 1, 0,  -1, 0)  >  0);
  790.         Testing::_assert(self::cmp( 1, 0,   0, 0)  >  0);
  791.         Testing::_assert(self::cmp( 1, 0,   1, 0) === 0);
  792.  
  793.         // Ensure that it's returning values in the set {-1,0,1}, and not in the set {-N,0,N} or somesuch.
  794.         Testing::_assert(self::cmp(  0, 0,   16, 0) === -1);
  795.         Testing::_assert(self::cmp( 16, 0,    0, 0) ===  1);
  796.         Testing::_assert(self::cmp(-16, 0,    0, 0) === -1);
  797.         Testing::_assert(self::cmp(  0, 0,  -16, 0) ===  1);
  798.  
  799.         // Also test another even value (looking for edge cases).
  800.         Testing::_assert(self::cmp( 0, 0,   0, 0) === 0);
  801.         Testing::_assert(self::cmp( 0, 0,   0, 2)  <  0);
  802.         Testing::_assert(self::cmp( 0, 2,   0, 0)  >  0);
  803.         Testing::_assert(self::cmp( 0, 2,   0, 2) === 0);
  804.         Testing::_assert(self::cmp(-2, 0,  -2, 0) === 0);
  805.         Testing::_assert(self::cmp(-2, 0,   0, 0)  <  0);
  806.         Testing::_assert(self::cmp(-2, 0,   2, 0)  <  0);
  807.         Testing::_assert(self::cmp( 0, 0,  -2, 0)  >  0);
  808.         Testing::_assert(self::cmp( 0, 0,   0, 0) === 0);
  809.         Testing::_assert(self::cmp( 0, 0,   2, 0)  <  0);
  810.         Testing::_assert(self::cmp( 2, 0,  -2, 0)  >  0);
  811.         Testing::_assert(self::cmp( 2, 0,   0, 0)  >  0);
  812.         Testing::_assert(self::cmp( 2, 0,   2, 0) === 0);
  813.  
  814.         // Notably, we've carefully avoided negative values in the less-significant parts, so far.
  815.         // That's because the less-significant integers shall be treated as
  816.         // unsigned integers, but PHP only has _signed_ comparison.
  817.         // So we better check for mistakes of that kind!
  818.         $x0000 = (int)0;
  819.         $xFFFF = (int)-1;
  820.         Testing::_assert(self::cmp($x0000,$x0000,  $x0000,$x0000) === 0); // 0 === 0
  821.         Testing::_assert(self::cmp($x0000,$x0000,  $x0000,$xFFFF)  <  0); // 0 < (2^32 - 1)
  822.         Testing::_assert(self::cmp($x0000,$x0000,  $xFFFF,$x0000)  >  0); // 0 > -(2^32)
  823.         Testing::_assert(self::cmp($x0000,$x0000,  $xFFFF,$xFFFF)  >  0); // 0 > -1
  824.         Testing::_assert(self::cmp($x0000,$xFFFF,  $x0000,$x0000)  >  0); // (2^32 - 1) > 0
  825.         Testing::_assert(self::cmp($x0000,$xFFFF,  $x0000,$xFFFF) === 0); // (2^32 - 1) === (2^32 - 1)
  826.         Testing::_assert(self::cmp($x0000,$xFFFF,  $xFFFF,$x0000)  >  0); // (2^32 - 1) > -(2^32)
  827.         Testing::_assert(self::cmp($x0000,$xFFFF,  $xFFFF,$xFFFF)  >  0); // (2^32 - 1) > -1
  828.         Testing::_assert(self::cmp($xFFFF,$x0000,  $x0000,$x0000)  <  0); // -(2^32) < 0
  829.         Testing::_assert(self::cmp($xFFFF,$x0000,  $x0000,$xFFFF)  <  0); // -(2^32) < (2^32 - 1)
  830.         Testing::_assert(self::cmp($xFFFF,$x0000,  $xFFFF,$x0000) === 0); // -(2^32) === -(2^32)
  831.         Testing::_assert(self::cmp($xFFFF,$x0000,  $xFFFF,$xFFFF)  <  0); // -(2^32) < -1
  832.         Testing::_assert(self::cmp($xFFFF,$xFFFF,  $x0000,$x0000)  <  0); // -1 < 0
  833.         Testing::_assert(self::cmp($xFFFF,$xFFFF,  $x0000,$xFFFF)  <  0); // -1 < (2^32 - 1)
  834.         Testing::_assert(self::cmp($xFFFF,$xFFFF,  $xFFFF,$x0000)  >  0); // -1 > -(2^32)
  835.         Testing::_assert(self::cmp($xFFFF,$xFFFF,  $xFFFF,$xFFFF) === 0); // -1 === -1
  836.  
  837.         echo(" done.\n");
  838.     }
  839.  
  840.     /*
  841.     * Multiplies two 64-bit integers, resulting in a single 128-bit integer.
  842.     *
  843.     * Because PHP does not have a native 128-bit integer type (or the ability
  844.     * to define structs that can be returned from functions), the returned
  845.     * value is placed into two 64-bit integer reference-type parameters.
  846.     */
  847.     public static function multiply_64x64(int $a, int $b, int &$out_hi, int &$out_lo) : void
  848.     {
  849.         self::multiply_NxN(32, $a, $b, $out_hi,$out_lo);
  850.     }
  851.  
  852.     // This is not part of the public API because there is no point.
  853.     // It _should_ do exactly what the `*` operator does.
  854.     // It's just designed to use the `multiply_64x64` function, so that
  855.     // we can see if it gives results identical to `*`, at least whenever
  856.     // the two are given operands that don't overflow.
  857.     private static function multiply_NxN_lo(int $bit_width, int $a, int $b) : int
  858.     {
  859.         $out_lo = (int)0;
  860.         $out_hi = (int)0;
  861.         self::multiply_NxN($bit_width, $a, $b,  $out_hi,$out_lo);
  862.         return $out_lo;
  863.     }
  864.  
  865.     public static function unittest_multiply_64x64() : void
  866.     {
  867.         echo(__CLASS__."::".__FUNCTION__."...");
  868.  
  869.         Testing::_assert(0x0000 === self::multiply_NxN_lo(8, 0x00, 0x00));
  870.         Testing::_assert(0x0000 === self::multiply_NxN_lo(8, 0x00, 0x01));
  871.         Testing::_assert(0x0000 === self::multiply_NxN_lo(8, 0x01, 0x00));
  872.         Testing::_assert(0x0000 === self::multiply_NxN_lo(8, 0x00, 0xFF));
  873.         Testing::_assert(0x0000 === self::multiply_NxN_lo(8, 0xFF, 0x00));
  874.         Testing::_assert(0x0001 === self::multiply_NxN_lo(8, 0x01, 0x01));
  875.         Testing::_assert(0x000F === self::multiply_NxN_lo(8, 0x01, 0x0F));
  876.         Testing::_assert(0x000F === self::multiply_NxN_lo(8, 0x0F, 0x01));
  877.         Testing::_assert(0x00E1 === self::multiply_NxN_lo(8, 0x0F, 0x0F));
  878.         Testing::_assert(0x0010 === self::multiply_NxN_lo(8, 0x01, 0x10));
  879.         Testing::_assert(0x0010 === self::multiply_NxN_lo(8, 0x10, 0x01));
  880.         Testing::_assert(0x0100 === self::multiply_NxN_lo(8, 0x10, 0x10));
  881.         Testing::_assert(0x4000 === self::multiply_NxN_lo(8, 0x80, 0x80));
  882.         Testing::_assert(0x3F01 === self::multiply_NxN_lo(8, 0x7F, 0x7F));
  883.         Testing::_assert(0xFC04 === self::multiply_NxN_lo(8, 0xFE, 0xFE));
  884.         Testing::_assert(0xFD02 === self::multiply_NxN_lo(8, 0xFE, 0xFF));
  885.         Testing::_assert(0xFD02 === self::multiply_NxN_lo(8, 0xFF, 0xFE));
  886.         Testing::_assert(0xFE01 === self::multiply_NxN_lo(8, 0xFF, 0xFF));
  887.         Testing::_assert(0x7E81 === self::multiply_NxN_lo(8, 0x7F, 0xFF));
  888.         Testing::_assert(0x7F80 === self::multiply_NxN_lo(8, 0x80, 0xFF));
  889.         Testing::_assert(0x3F80 === self::multiply_NxN_lo(8, 0x80, 0x7F));
  890.  
  891.         for ( $i = (int)0; $i < 256; $i++ )
  892.         {
  893.             for ( $j = (int)0; $j < 256; $j++ )
  894.             {
  895.                 $expected = (int)($i*$j);
  896.                 $got = self::multiply_NxN_lo(8, $i, $j);
  897.                 Testing::_assert($expected === $got, sprintf("Operands: i=%02x; j=%02x; Expected: %04x; Got: %04X", $i, $j, $expected, $got));
  898.             }
  899.         }
  900.  
  901.         Testing::_assert(0x0000_0000 === self::multiply_NxN_lo(16, 0x0000, 0x0000));
  902.         Testing::_assert(0x0000_0000 === self::multiply_NxN_lo(16, 0x0000, 0x0001));
  903.         Testing::_assert(0x0000_0000 === self::multiply_NxN_lo(16, 0x0001, 0x0000));
  904.         Testing::_assert(0x0000_0000 === self::multiply_NxN_lo(16, 0x0000, 0xFFFF));
  905.         Testing::_assert(0x0000_0000 === self::multiply_NxN_lo(16, 0xFFFF, 0x0000));
  906.         Testing::_assert(0x0000_0001 === self::multiply_NxN_lo(16, 0x0001, 0x0001));
  907.         Testing::_assert(0x0000_FFFF === self::multiply_NxN_lo(16, 0x0001, 0xFFFF));
  908.         Testing::_assert(0x0000_FFFF === self::multiply_NxN_lo(16, 0xFFFF, 0x0001));
  909.         Testing::_assert(0xFFFE_0001 === self::multiply_NxN_lo(16, 0xFFFF, 0xFFFF));
  910.         Testing::_assert(0XA518_60E1 === self::multiply_NxN_lo(16, 0xF00F, 0xB00F));
  911.  
  912.         Testing::_assert(0x0000_0000_0000_0000 === self::multiply_NxN_lo(32, 0x0000_0000, 0x0000_0000));
  913.         Testing::_assert(0x0000_0000_0000_0000 === self::multiply_NxN_lo(32, 0x0000_0000, 0x0000_0001));
  914.         Testing::_assert(0x0000_0000_0000_0000 === self::multiply_NxN_lo(32, 0x0000_0001, 0x0000_0000));
  915.         Testing::_assert(0x0000_0000_0000_0000 === self::multiply_NxN_lo(32, 0x0000_0000, 0xFFFF_FFFF));
  916.         Testing::_assert(0x0000_0000_0000_0000 === self::multiply_NxN_lo(32, 0xFFFF_FFFF, 0x0000_0000));
  917.         Testing::_assert(0x0000_0000_0000_0001 === self::multiply_NxN_lo(32, 0x0000_0001, 0x0000_0001));
  918.         Testing::_assert(0x0000_0000_FFFF_FFFF === self::multiply_NxN_lo(32, 0x0000_0001, 0xFFFF_FFFF));
  919.         Testing::_assert(0x0000_0000_FFFF_FFFF === self::multiply_NxN_lo(32, 0xFFFF_FFFF, 0x0000_0001));
  920.         Testing::_assert(0xFFFF_FFFE_0000_0001 === self::multiply_NxN_lo(32, 0xFFFF_FFFF, 0xFFFF_FFFF));
  921.  
  922.         // Explicit test of 128-bit returning version, and of 64-bit inputs.
  923.         $a64 = (int)0xAceBe11e_CafeBabe;
  924.         $b64 = (int)0xF100fCa7_F1edFa57;
  925.         $out_hi = (int)0;
  926.         $out_lo = (int)0;
  927.         self::multiply_64x64($a64,  $b64,  $out_hi,$out_lo);
  928.         Testing::_assert(0x8E9C_2945_7ED5_0292 === $out_lo);
  929.         Testing::_assert(0xA2CA_B997_9FFE_C71C === $out_hi);
  930.  
  931.         echo(" done.\n");
  932.     }
  933.  
  934.     /**
  935.     * @param      int  $numerator_hi
  936.     * @param      int  $numerator_lo
  937.     * @param      int  $denominator
  938.     * @param-out  int  $quotient_hi
  939.     * @param-out  int  $quotient_lo
  940.     * @returns    int  The remainder.
  941.     */
  942.     public static function divide_128x64(int $numerator_hi, int $numerator_lo, int $denominator, int &$quotient_hi, int &$quotient_lo) : int
  943.     {
  944.         // TODO: Test what PHP does with integer divide-by-zero.
  945.         // In principle, PHP should throw a DivisionByZeroError whenever this
  946.         // happens. In that case, we can just proceed as normal, because
  947.         // the first time division is used in this function, it'll cause
  948.         // that error to be thrown.
  949.         // See: https://www.php.net/manual/en/class.divisionbyzeroerror.php
  950.         // (But I haven't tested to make _sure_ PHP does this. If it doesn't
  951.         // throw an exception, then we should. Propagating weird values
  952.         // through the calculation could result in hard-to-find bugs.)
  953.  
  954.         // Special-case the value denominator value of `1`, both to make this
  955.         // identity operation be fast, but also to ensure that we don't have
  956.         // to worry about any weird corner cases for denominators that are
  957.         // less than 2. (It can matter, because binary arithmatic.)
  958.         if ( $denominator === 1 ) {
  959.             $quotient_hi = $numerator_hi;
  960.             $quotient_lo = $numerator_lo;
  961.             return 0;
  962.         }
  963.  
  964.         // Give these predictable values.
  965.         // This will be helpful in debugging if an error happens:
  966.         // you'll always know what these started as!
  967.         $quotient_hi = (int)0;
  968.         $quotient_lo = (int)0;
  969.  
  970.         // Store the sign bit that the result will have.
  971.         $sign = ($numerator_hi ^ $denominator) & self::MASK_SIGN;
  972.  
  973.         // Sign extraction, so it doesn't mess with our division.
  974.         $sign = $hi & self::MASK_SIGN;
  975.         $hi &= ~self::MASK_SIGN;
  976.  
  977.         // Extract remainders.
  978.         //
  979.         // Right now we are mostly interested in $hi_remainder.
  980.         // This will be necessary later for estimating the low portion of the result.
  981.         //
  982.         // The $lo_remainder will simply be returned by the function as-is,
  983.         // since this may help the caller with rounding logic.
  984.         $lo_remainder = $lo % $denominator;
  985.         $hi_remainder = $hi % $denominator;
  986.  
  987.         // Component-wise division.
  988.         //
  989.         // (We use `intdiv` because `/` might do a check to see if one or both
  990.         // of its operands are floating point numbers, because it is a floating
  991.         // point operation by default. `intdiv`, on the other hand, is explicitly
  992.         // intended for integer division, so it may perform/behave better for this use.)
  993.         $lo = intdiv($lo, $denominator);
  994.         $hi = intdiv($hi, $denominator);
  995.  
  996.         // Calculate the carry.
  997.         $min_carry = PHP_INT_MAX; // Basically ((2^64 / 2) - 1). We'd prefer (2^64), but can't represent it.
  998.         $min_carry = intdiv($min_carry, $denominator);
  999.         $min_carry <<= 1; // Undo the earlier divide-by-2 in the ((2^64 / 2) - 1) = PHP_INT_MAX.
  1000.  
  1001.         // Perform the carry.
  1002.         $lo += ($hi_remainder * $min_carry);
  1003.  
  1004.         // For safety reasons, we'll also calculate a "max" carry.
  1005.         $max_carry_init = (1 << 62);
  1006.         $max_carry = intdiv($max_carry_init, $denominator);
  1007.         if ( ($denominator * $max_carry) !== $max_carry_init ) {
  1008.             // Always round up.
  1009.             $max_carry++;
  1010.         }
  1011.         $max_carry <<= 2;
  1012.         $max_carry += 3; // Always round up.
  1013.  
  1014.         // Perform the carry.
  1015.         $max_lo += ($hi_remainder * $max_carry);
  1016.  
  1017.         // This loop takes our approximation and improves it until we have
  1018.         // the correct quotient.
  1019.         $test_lo = (int)0;
  1020.         $test_hi = (int)0;
  1021.         $test_carry = (int)0;
  1022.  
  1023.         // TODO: BUG? Inspect the below `+=` operators and the IntNN:add_with_carry
  1024.         // to ensure that this function will be handling overflow conditions
  1025.         // correctly. Right now, it probably _isn't_ (though we could get lucky?).
  1026.  
  1027.         self::multiply_64x64($denominator,  $lo,  $test_hi,$test_lo);
  1028.         $test_hi += ($hi * $denominator);
  1029.  
  1030.         while ( true )
  1031.         {
  1032.             $test_lo = IntNN::add_with_carry($test_lo, $denominator, $test_carry);
  1033.             $test_hi += $test_carry;
  1034.             // if ( test > numerator )
  1035.             if ( self::cmp($test_hi, $test_lo, $numerator_hi, $numerator_lo) > 0 ) {
  1036.                 break;
  1037.             }
  1038.  
  1039.             // The additional increment of $denominator in the $test variable
  1040.             // corresponds to incrementing the $lo value by 1.
  1041.             $lo++;
  1042.  
  1043.             // This handles the aforementioned "safety reasons".
  1044.             // It prevents us from infinite-looping, or from trying to
  1045.             // iterate most of a 64-bit integer's possible values
  1046.             // when it is already futile to get the correct answer.
  1047.             // Ideally, this will never be executed.
  1048.             // If the surrounding function works as intended, then the loop
  1049.             // will ALWAYS converge before this condition becomes true.
  1050.             if ($lo > $max_lo) {
  1051.                 $class_name = __CLASS__;
  1052.                 $func_name = __FUNCTION__;
  1053.                 throw new \Exception(sprintf(
  1054.                     "Internal error: `$class_name::$func_name` did not converge when it should have. ".
  1055.                     "Aborting to prevent excessive looping and CPU drain. ".
  1056.                     "This means that the `$func_name` function is broken and may return incorrect results, ".
  1057.                     "even when this error isn't thrown. Please report this error. ".
  1058.                     "Parameters: {numerator_hi:%016X, numerator_lo:%016X, denominator:%016X}",
  1059.                     $numerator_hi, $numerator_lo, $denominator
  1060.                     ));
  1061.             }
  1062.         }
  1063.  
  1064.         // Pass results to the caller.
  1065.         $quotient_hi = $hi;
  1066.         $quotient_lo = $lo;
  1067.         return $lo_remainder;
  1068.  
  1069.         /*
  1070.         TODO: Comment is kinda sorta relevant but also outdated already.
  1071.  
  1072.         // This will be multiplied by the $hi_remainder to get the portion
  1073.         // of the number that is being carried into the $lo component of the result.
  1074.         //
  1075.         // Note that this should be `(2^64/$denominator)` EXACTLY.
  1076.         // Unfortunately, we can't be exact for two reasons:
  1077.         // * Rational numbers (the exact result) can't be represented by finite integers.
  1078.         // * The number 2^64 is out of the range of 64-bit integers (one more than the max!)
  1079.         //
  1080.         // Now we'll get clever, and our function will get slower.
  1081.         //
  1082.         // We notice that the multiplier doesn't _need_ to be exact.
  1083.         // We can make a guess. And the guess can be wrong. As long as it's
  1084.         // always wrong in a way that's a little bit low.
  1085.         //
  1086.         // If it's low, it will result in our end-result being too low.
  1087.         // Then we can multiply our guess by the denominator.
  1088.         // The result will be less than the numerator.
  1089.         // (If we had exact numbers instead of integers, multiplying the quotient
  1090.         // by the denominator would result in _exactly_ the numerator.)
  1091.         //
  1092.         // Then we can just add the $denominator over and over, checking
  1093.         // it with a multiplication, until it is too high.
  1094.         // Once it is too high, we return the last number that multiplied
  1095.         // to a value
  1096.         //
  1097.         */
  1098.     }
  1099.  
  1100.     public static function unittest_divide_128x64()
  1101.     {
  1102.         echo(__CLASS__."::".__FUNCTION__."...");
  1103.         // TODO: Oh god this needs testing BADLY.
  1104.         echo(" UNIMPLEMENTED! (Please fix!)\n");
  1105.         // echo(" done.\n");
  1106.     }
  1107.  
  1108.     public static function unittest()
  1109.     {
  1110.         echo("Unittests for ".__CLASS__."\n");
  1111.         self::unittest_cmp();
  1112.         self::unittest_multiply_64x64();
  1113.         self::unittest_divide_128x64();
  1114.         echo("\n");
  1115.     }
  1116.  
  1117.     // Prevent instantiation/construction of the (static/constant) class.
  1118.     /** @return never */
  1119.     private function __construct() {
  1120.         throw new \Exception("Instantiation of static class " . get_class($this) . "is not allowed.");
  1121.     }
  1122. }
  1123.  
  1124. ?>
  1125.  
  1126. <?php
  1127. /*
  1128. declare(strict_types=1);
  1129.  
  1130. namespace Kickback\Common\Math;
  1131. */
  1132. final class Signedness
  1133. {
  1134.     public const SIGNED    = 0;
  1135.     public const UNSIGNED  = 1;
  1136.     public const AMBIGUOUS = 2;
  1137.  
  1138.     public static function to_identifier(int $signedness) : string
  1139.     {
  1140.         switch($signedness)
  1141.         {
  1142.             case self::SIGNED   : return "SIGNED";
  1143.             case self::UNSIGNED : return "UNSIGNED";
  1144.             case self::AMBIGUOUS: return "AMBIGUOUS";
  1145.         }
  1146.         return "ERROR: Unknown signedness ($signedness)";
  1147.     }
  1148.  
  1149.     public static function to_string(int $signedness) : string {
  1150.         return self::to_identifier($signedness);
  1151.     }
  1152.  
  1153.     // Prevent instantiation/construction of the (static/constant) class.
  1154.     /** @return never */
  1155.     private function __construct() {
  1156.         throw new \Exception("Instantiation of static class " . get_class($this) . "is not allowed.");
  1157.     }
  1158. }
  1159. ?>
  1160.  
  1161. <?php
  1162. /*
  1163. declare(strict_types=1);
  1164.  
  1165. namespace Kickback\Common\Math;
  1166. */
  1167. // TODO: I forget if it's better to do this, or to use an `enum` type. Whatevs.
  1168. // (At least now we have enough solid functionality that if we try to convert
  1169. // this (and the Signedness class) over to enums, we'll find out very _quickly_
  1170. // if it's a good idea or not! <grin>)
  1171.  
  1172. final class RoundingMode
  1173. {
  1174.     // Rounding modes.
  1175.     // (I think this is all of the possibilities? TODO: Verify.)
  1176.  
  1177.     // TODO: I'm VERY tempted to make BANKERS rounding be the default rounding mode.
  1178.     // Like, it's a rounding procedure that cancels accumulated error during
  1179.     // successive rounds. How fncking cool is that?
  1180.     // Why NOT make that the default?
  1181.     // (I mean, it might be a little bit slower than truncation...
  1182.     // but probably not in any perceivable way. Like, <1%.
  1183.     // And it makes your error accumulate at a rate of sqrt(n) instead of (n),
  1184.     // for n operations.
  1185.     // And it's going to be used for WideFractions and WideIntegers, which
  1186.     // will probably not be slow, but they won't be the FASTEST thing to
  1187.     // begin with. (They are really optimized for correctness and exactness,
  1188.     // at a probably small-ish expense of speed.))
  1189.  
  1190.     /** The default rounding mode shall mimic x86 integer truncation. */
  1191.     public const DEFAULT = 0;
  1192.  
  1193.     public const ALL_TOWARDS_NEG_INF  =  1;
  1194.     public const ALL_TOWARDS_POS_INF  =  2;
  1195.     public const ALL_TOWARDS_ZERO     =  3;
  1196.     public const ALL_AWAY_FROM_ZERO   =  4;
  1197.     public const ALL_TOWARDS_EVEN     =  5;
  1198.     public const ALL_TOWARDS_ODD      =  6;
  1199.     public const HALF_TOWARDS_NEG_INF =  7;
  1200.     public const HALF_TOWARDS_POS_INF =  8;
  1201.     public const HALF_TOWARDS_ZERO    =  9; // Similar to PHP_ROUND_HALF_DOWN
  1202.     public const HALF_AWAY_FROM_ZERO  = 10; // Similar to PHP_ROUND_HALF_UP
  1203.     public const HALF_TOWARDS_EVEN    = 11; // Similar to PHP_ROUND_HALF_EVEN; bankers' rounding.
  1204.     public const HALF_TOWARDS_ODD     = 12; // Similar to PHP_ROUND_HALF_ODD
  1205.  
  1206.     // Useful alias.
  1207.     public const BANKERS = self::HALF_TOWARDS_EVEN;
  1208.  
  1209.     /**
  1210.     * If the `$rounding_mode` parameter equals RoundingMode::DEFAULT, then
  1211.     * it this function will return the more specific RoundingMode that this
  1212.     * refers to.
  1213.     *
  1214.     * If `$rounding_mode` is any other value, then it that value will be
  1215.     * returned unmodified.
  1216.     */
  1217.     public static function resolve_default(int $rounding_mode = self::DEFAULT) : int
  1218.     {
  1219.         if ( $rounding_mode === self::DEFAULT ) {
  1220.             // This mimics x86 integer truncation. (I think? TODO: Double-check this.)
  1221.             return self::ALL_TOWARDS_NEG_INF;
  1222.         } else {
  1223.             return $rounding_mode;
  1224.         }
  1225.     }
  1226.  
  1227.     public static function to_identifier(int $rounding_mode) : string
  1228.     {
  1229.         switch($rounding_mode)
  1230.         {
  1231.             case self::DEFAULT             : return "DEFAULT";
  1232.             case self::ALL_TOWARDS_NEG_INF : return "ALL_TOWARDS_NEG_INF";
  1233.             case self::ALL_TOWARDS_POS_INF : return "ALL_TOWARDS_POS_INF";
  1234.             case self::ALL_TOWARDS_ZERO    : return "ALL_TOWARDS_ZERO";
  1235.             case self::ALL_AWAY_FROM_ZERO  : return "ALL_AWAY_FROM_ZERO";
  1236.             case self::ALL_TOWARDS_EVEN    : return "ALL_TOWARDS_EVEN";
  1237.             case self::ALL_TOWARDS_ODD     : return "ALL_TOWARDS_ODD";
  1238.             case self::HALF_TOWARDS_NEG_INF: return "HALF_TOWARDS_NEG_INF";
  1239.             case self::HALF_TOWARDS_POS_INF: return "HALF_TOWARDS_POS_INF";
  1240.             case self::HALF_TOWARDS_ZERO   : return "HALF_TOWARDS_ZERO";
  1241.             case self::HALF_AWAY_FROM_ZERO : return "HALF_AWAY_FROM_ZERO";
  1242.             case self::HALF_TOWARDS_EVEN   : return "HALF_TOWARDS_EVEN";
  1243.             case self::HALF_TOWARDS_ODD    : return "HALF_TOWARDS_ODD";
  1244.         }
  1245.  
  1246.         return "ERROR: Unknown rounding mode ($rounding_mode)";
  1247.     }
  1248.  
  1249.     public static function to_string(int $rounding_mode) : string
  1250.     {
  1251.         if ( $rounding_mode === self::DEFAULT ) {
  1252.             $resolved_mode = self::resolve_default();
  1253.             return "DEFAULT ($resolved_mode)";
  1254.         } else {
  1255.             return self::rounding_mode_to_identifier($rounding_mode);
  1256.         }
  1257.     }
  1258.  
  1259.     // Prevent instantiation/construction of the (static/constant) class.
  1260.     /** @return never */
  1261.     private function __construct() {
  1262.         throw new \Exception("Instantiation of static class " . get_class($this) . "is not allowed.");
  1263.     }
  1264. }
  1265. ?>
  1266.  
  1267. <?php
  1268. /*
  1269. declare(strict_types=1);
  1270.  
  1271. namespace \Kickback\Common\Meta;
  1272. */
  1273.  
  1274. class Template
  1275. {
  1276.     // TODO: How to populate this?
  1277.     // (DO we need to populate this?)
  1278.     private array $parameters_? = null;
  1279.     public function parameters() : array
  1280.     {
  1281.  
  1282.     }
  1283.  
  1284.     public function instantiate(string $namespace, string $base_name, array $parameters) : void
  1285.     {
  1286.         throw new UnimplementedException(__CLASS__."->".__FUNCTION__." hasn't been implemented yet.");
  1287.         // TODO: Compute $instance_path;
  1288.         // NOTE: $instance_path might, itself, need to contain template parameter subsitutions!
  1289.         //   That way, we could make a file like WideIntX@{N}.template.php and then know,
  1290.         //   based on the template parameter N being N=4, that the $base_name should be "WideIntX4" instead of "WideIntX@{N}".
  1291.         //   Thus, it is unnecessary to ask the template what its class/interface/etc name would be.
  1292.         //   That's important, because if we have to ask the template, then
  1293.         //   we won't know the $base_name until we have already used the $base_name to process the template!
  1294.         //   (Also it might be VERY cool if we could create an idiomatic format
  1295.         //   for encoding template parameters into class/interface/etc names.
  1296.         //   Then it'd be possible to have the autoloader (!) instantiate templates (!!).
  1297.         //   Though, admittedly, it would probably be so ugly that we'd just
  1298.         //   do instantiation-upon-construction anyways.)
  1299.         //
  1300.         if ( !file_exists($instance_path ) {
  1301.             self::template_instance_codegen($namespace, $base_name, $parameters, $instance_path);
  1302.         }
  1303.  
  1304.         require_once($instance_path);
  1305.     }
  1306.  
  1307.     private function template_instance_codegen(string $namespace, string $base_name, array $parameters, string $instance_path) : void
  1308.     {
  1309.         throw new UnimplementedException(__CLASS__."->".__FUNCTION__." hasn't been implemented yet.");
  1310.         // TODO: Write specific code for all of this.
  1311.         // TODO: Probably alter some of the path generation instructions so that
  1312.         //   the instance files and temporary files go some place sane, like:
  1313.         //   * temporary files: somewhere in (\Kickback\SCRIPT_ROOT . "/tmp/...")
  1314.         //   * instance files: somewhere in (\Kickback\SCRIPT_ROOT . "/TemplateInstances/...")
  1315.         //
  1316.         // Generate the file:
  1317.         // * $template_file_path = \Kickback\SCRIPT_ROOT ."/". self::classpath_to_filepath($namespace, $base_name) . ".template.php";
  1318.         //     * (BTW, to make this efficient, the below should probably use something like fread/fwrite line-by-line, and NOT slurp the file using `file_get_contents`)
  1319.         //     * if ( exists($template_file_path) ) { spin for up to 30 seconds, waiting for the file to be deleted, then move to "Process the template file" instructions. }
  1320.         //     * Read and process the base_name.template.php ($template_file_path) file:
  1321.         //     * $base_template_text = file_get_contents($template_file_path);
  1322.         //     * $base_template_text: Replace [<][?][p][h][p]...[?][>] with @@@php...@@@
  1323.         //     * $base_template_text: Replace all @@php...@@ with [<][?][p][h][p]...[?][>]
  1324.         //     * $template_tmp1_file_path = $template_file_path . ".tmp";
  1325.         //     * Write the results ($base_template_text) to $template_tmp1_file_path
  1326.         // * Process the template file:
  1327.         //     * (Is there any way to stream ob_ content line-by-line, so we don't have to store the whole file in memory?)
  1328.         //     * (If we stream it, we should stream it to another temporary file.)
  1329.         //     * If streaming: if ( exists($template_tmp2_path) ) { spin for up to 30 seconds, waiting for the file to be deleteted, then  }
  1330.         //     * ob_start();
  1331.         //     * require_once($template_tmp1_file_path);
  1332.         //     * $template_output = ob_get_clean();
  1333.         //     * $template_output: Replace all @@@php...@@@ with [<][?][p][h][p]...[?][>]
  1334.         // * Write $template_output (or $template_tmp2_file_path) out to $instance_path.
  1335.         // * Remove file at $template_tmp1_file_path (if needed)
  1336.         // * Remove file at $template_tmp2_file_path (if needed)
  1337.     }
  1338. }
  1339. ?>
  1340.  
  1341. <?php
  1342. /*
  1343. declare(strict_types=1);
  1344.  
  1345. namespace \Kickback\Common\Meta;
  1346.  
  1347. use \Kickback\Common\Meta\Template;
  1348. */
  1349.  
  1350. class TemplateProcessor
  1351. {
  1352.     // TODO:
  1353.     // * Implement all of the methods needed for the WideFraction template
  1354.     //     to be able to generate it's code.
  1355.     // * Find some way for the Template class to communicate its instance
  1356.     //     to the TemplateProcessor class. This is crucial for things like
  1357.     //     accessing the template parameter list from within the template itself.
  1358.  
  1359.     public function echo_header_code() : void
  1360.     {
  1361.         TODO: implement
  1362.     }
  1363.  
  1364.     public function echo_instance_base_name() : void
  1365.     {
  1366.         TODO: implement
  1367.     }
  1368. }
  1369. ?>
  1370.  
  1371. <?php
  1372. @@php
  1373. /*
  1374. declare(strict_types=1);
  1375.  
  1376. namespace \Kickback\Common\Math\Types;
  1377.  
  1378. use \Kickback\Common\Meta\Template;
  1379. */
  1380. final class WideFractionPart
  1381. {
  1382.     public string $numerator;   // The name of the member, not an actual numerical value.
  1383.     public string $denominator; // The name of the member, not an actual numerical value.
  1384. }
  1385.  
  1386. final class WideFractionTemplateProcessor extends TemplateProcessor
  1387. {
  1388.     // The constant denominator case is nice because it allows us to avoid
  1389.     // having to store the additional $denominator member for the WideFractions
  1390.     // that have commonly used constant denominators (things like 100, 1000, etc).
  1391.     //
  1392.     // This can potentially make calculations faster too, not just because
  1393.     // "less memory == less cache thrashing", but more specifically because
  1394.     // it allows some intermediate quantities to be calculated.
  1395.     //
  1396.     private bool $has_constant_denominator_ = ;
  1397.     public function has_constant_denominator() : bool
  1398.     {
  1399.         // TODO: Probably this should be done in the constructor, instead of lazily here.
  1400.         if ( $this->has_constant_denominator_ === null ) {
  1401.             if(($array_key_exists("constant_denominator", $this->parameters()))
  1402.             && ($this->parameters["constant_denominator"] !== 0)) {
  1403.                 $this->has_constant_denominator_ = true;
  1404.             } else {
  1405.                 $this->has_constant_denominator_ = false;
  1406.             }
  1407.  
  1408.         }
  1409.         return $this->has_constant_denominator_;
  1410.     }
  1411.  
  1412.     private int $number_of_parts_ = 0;
  1413.     public function number_of_parts() : int
  1414.     {
  1415.         // TODO: Probably this should be done in the constructor, instead of lazily here.
  1416.         if ( $this->number_of_parts_ === 0 ) {
  1417.             $this->number_of_parts_ = $this->parameters()["N"];
  1418.         }
  1419.         return $this->number_of_parts_;
  1420.     }
  1421.  
  1422.     private \SplFixedArray $parts_ = $this->make_parts_array();
  1423.     private function make_parts_array() : \SplFixedArray
  1424.     {
  1425.         // TODO: \SplFixedArray syntax check!
  1426.         $n = $this->number_of_parts();
  1427.         $parts_array = new \SplFixedArray($n);
  1428.         for ($i = (int)0; $i < $n; $i++)
  1429.         {
  1430.             $part = new WideFractionPart();
  1431.             $part->$numerator   = "numerator"   . strval($i);
  1432.             $part->$denominator = "denominator" . strval($i);
  1433.             $this->parts_[$i] = $part;
  1434.         }
  1435.         return $parts_array;
  1436.     }
  1437.  
  1438.     public function parts() : \SplFixedArray
  1439.     {
  1440.         return $this->parts_;
  1441.     }
  1442.  
  1443.     public function echo_parameter_list(string $param_name, int $from = 0, int $to = $this->number_of_parts()) : void
  1444.     {
  1445.         $this->echo_code("string ${param_name}" . strval($from))
  1446.         for ($i = $from+1; $i < $to; $i++) {
  1447.             $this->echo_code(", string ${param_name}" . strval($i));
  1448.         }
  1449.         $this->echo_code(" ");
  1450.     }
  1451.  
  1452.     public function echo_parameter_list_lo(string $param_name) : void
  1453.     {
  1454.         $n = $this->number_of_parts();
  1455.         $this->echo_parameter_list($param_name, 0, $n/2);
  1456.     }
  1457.  
  1458.     public function echo_parameter_list_hi(string $param_name) : void
  1459.     {
  1460.         $n = $this->number_of_parts();
  1461.         $this->echo_parameter_list($param_name, ($n/2)+1, $n);
  1462.     }
  1463.  
  1464.     public function echo_member_arg_list(string $member_name, int $from = 0, int $to = $this->number_of_parts()) : void
  1465.     {
  1466.         $parts = $this->parts();
  1467.         $this->echo_code($parts[$from]->$member_name)
  1468.         for ($i = $from+1; $i < $to; $i++) {
  1469.             $this->echo_code(",".$parts[$i]->$member_name);
  1470.         }
  1471.         $this->echo_code(" ");
  1472.     }
  1473.  
  1474.     public function echo_numerator_arg_list_lo() : void
  1475.     {
  1476.         $n = $this->number_of_parts();
  1477.         $this->echo_member_arg_list("numerator", 0, $n/2);
  1478.     }
  1479.  
  1480.     public function echo_numerator_arg_list_hi() : void
  1481.     {
  1482.         $n = $this->number_of_parts();
  1483.         $this->echo_member_arg_list("numerator", ($n/2)+1, $n);
  1484.     }
  1485.  
  1486.     public function echo_denominator_arg_list_lo() : void
  1487.     {
  1488.         $n = $this->number_of_parts();
  1489.         $this->echo_member_arg_list("denominator", 0, $n/2);
  1490.     }
  1491.  
  1492.     public function echo_denominator_arg_list_hi() : void
  1493.     {
  1494.         $n = $this->number_of_parts();
  1495.         $this->echo_member_arg_list("denominator", ($n/2)+1, $n);
  1496.     }
  1497. }
  1498.  
  1499. function variable_scoping_function() : void
  1500. {
  1501.     // TODO: Figure out better template processor syntax.
  1502.     $template = new WideFractionTemplateProcessor(__namespace__, basename(__FILE__, '.template.php'));
  1503.     $template->echo_header_code();
  1504. @@
  1505.  
  1506. final class @@php $template->echo_instance_base_name() @@
  1507. {
  1508.     @@php
  1509.     for ($template->parts() as $part) {
  1510.         $numerator_part = $part->numerator;
  1511.         $denominator_part = $part->denominator;
  1512.         $template->set_indentation(1);
  1513.         $template->echo_code("private int \$$numerator_part;\n");
  1514.         $template->echo_code("private int \$$denominator_part;\n");
  1515.     }
  1516.     @@
  1517.  
  1518.     private static function banker_round(int $numerator, int $increment) : int
  1519.     {
  1520.         Testing::_assert($increment > 1);
  1521.  
  1522.         // Even if we don't use $even_increment in most cases,
  1523.         // we should still assert that it fits in _all_ cases, just to give
  1524.         // this function consistent behavior (e.g. whether it asserts or not
  1525.         // should depend on `$increment` and not on `$numerator`.)
  1526.         //$even_increment = ($increment<<1);
  1527.         Testing::_assert(($increment<<1) <= PHP_INT_MAX);
  1528.  
  1529.         if ( $numerator >= 0 ) {
  1530.             return self::banker_round_unsigned_($numerator, $increment);
  1531.         }
  1532.         else {
  1533.             return self::banker_round_signed_($numerator, $increment);
  1534.         }
  1535.     }
  1536.  
  1537.     private static function banker_round_signed_(int $numerator, int $increment) : never
  1538.     {
  1539.         // TODO!
  1540.         Testing::_assert(false, "Signed rounding is not yet implemented.");
  1541.     }
  1542.  
  1543.     private static function banker_round_unsigned_(int $numerator, int $increment) : int
  1544.     {
  1545.         /* TODO: cut?
  1546.         // We calculate the $round_down_amount (conventional rounding)
  1547.         // from the $round_down_even_amount (bankers' rounding)
  1548.         // so that we avoid having to modulus more than once.
  1549.         $round_down_even_amount = $numerator % $even_increment;
  1550.         $round_down_amount = $round_down_even_amount;
  1551.         if ( $round_down_amount > $increment ) {
  1552.             $round_down_amount -= $increment;
  1553.         }
  1554.         */
  1555.  
  1556.         // First, attempt conventional rounding (e.g. "round-to-nearest-increment").
  1557.         $rounding_amount = (int)0;
  1558.         if ( self::get_rounding_amount_($numerator, $increment, $rounding_amount) ) {
  1559.             return $rounding_amount;
  1560.         } else {
  1561.             // If that didn't work, then fall back on the tie breaker.
  1562.             return self::banker_round_tie_breaker_($numerator, $increment);
  1563.         }
  1564.     }
  1565.  
  1566.     private static function get_rounding_amount_(int $numerator, int $increment, &$rounding_amount) : bool
  1567.     {
  1568.         $round_down_amount = $numerator % $increment;
  1569.         $round_up_amount = $increment - $round_down_amount;
  1570.         if ( $round_down_amount < $round_up_amount ) {
  1571.             $rounding_amount = -$round_down_amount;
  1572.             return true;
  1573.         } else
  1574.         if ( $round_down_amount > $round_up_amount ) {
  1575.             $rounding_amount = $round_up_amount;
  1576.             return true;
  1577.         } else {
  1578.             // If that didn't work, then there's a problem, and it's probably this tie:
  1579.             Testing::_assert($round_down_amount === $round_up_amount);
  1580.             $rounding_amount = 0; // TODO: Is this right?
  1581.             return false;
  1582.         }
  1583.     }
  1584.  
  1585.     // This is set out into its own function because the tie breaker
  1586.     // is unlikely to be executed very frequently. As such, it might
  1587.     // be faster (code-execution-wise) to break this out into it's own function.
  1588.     //
  1589.     // Reasons why this might be the case:
  1590.     // * Interpreter is less likely to need to parse/analyse this code when `banker_round` is called.
  1591.     // * This is more cache-friendly: the CPU won't need to load the instructions for the tie breaker every time `banker_round` is called.
  1592.     // * This makes `banker_round` smaller and therefore more inline-able.
  1593.     //
  1594.     // I am not sure how much any of those _actually_ matter, and it's not
  1595.     // really worth testing at the moment, but this is _usually_ a good way
  1596.     // to optimize code, and it seems to have few or no disadvantages.
  1597.     private static function banker_round_tie_breaker_(int $numerator, int $increment) : int
  1598.     {
  1599.         // Now the bankers' rounding comes into play.
  1600.         // We break the tie by rounding to the nearest _even_ increment.
  1601.         $even_increment = $increment << 1;
  1602.  
  1603.         // This involves just doing the rounding again, but with $increment*2.
  1604.         $rounding_amount = (int)0;
  1605.         Testing::_assert(self::get_rounding_amount_($numerator, $even_increment, $rounding_amount));
  1606.         return $rounding_amount;
  1607.     }
  1608.     // TODO: The above bankers' rounding code is pretty sus. I was very sleepy while writing it. o.O
  1609.  
  1610.     private static function unittest_banker_round() : void
  1611.     {
  1612.         echo(__CLASS__."::".__FUNCTION__."...");
  1613.         // TODO: This needs testing if you want to trust any financials done with it.
  1614.         echo(" UNIMPLEMENTED! (Please fix!)\n");
  1615.         // echo(" done.\n");
  1616.     }
  1617.  
  1618.  
  1619.  
  1620.     /*
  1621.     * Beware: This operation is NOT commutative like normal multiplication.
  1622.     * That's because the choice of destination decides which divisor to use
  1623.     * when scaling back the oversized numerator that results from the
  1624.     * initial multiplication.
  1625.     *
  1626.     * The `multiply` and `multiply_into` functions have the commutative property.
  1627.     *
  1628.     * This method will not perform any explicit memory allocations
  1629.     * unless an error has occurred.
  1630.     */
  1631.     public function multiply_by(WideFraction $other, int $rounding_mode = RoundingMode::DEFAULT) : void
  1632.     {
  1633.         // ASSUMPTION: We wish the output to have the same divisor as $this, not $other (or anything else).
  1634.         $this->numerator = self::multiply_raw($this, $other, $this->denominator, $rounding_mode);
  1635.     }
  1636.  
  1637.     /*
  1638.     * Multiplies `$fp64a` and `$fp64b` together, then stores the result
  1639.     * into the `$destination` object.
  1640.     *
  1641.     * As a convenience, the `$destination` object is returned.
  1642.     *
  1643.     * When rounding or truncating the fractional multiplication results,
  1644.     * the `$destination` parameter's `$denominator` field is used
  1645.     * as a divisor.
  1646.     *
  1647.     * This operation has commutative property over `$fp64a` and `$fp64b`.
  1648.     *
  1649.     * This function will not perform any explicit memory allocations
  1650.     * unless an error has occurred.
  1651.     */
  1652.     public static function multiply_into(WideFraction $fp64a, WideFraction $fp64b, WideFraction $destination, int $rounding_mode = RoundingMode::DEFAULT) : WideFraction
  1653.     {
  1654.         Testing::_assert(isset($destination));
  1655.         $tmp = WideFraction::multiply_raw($fp64a, $fp64b, $destination->denominator, $rounding_mode);
  1656.         $destination->numerator = $tmp;
  1657.         return $destination;
  1658.     }
  1659.  
  1660.     private static function multiply_raw(WideFraction $fp64a, WideFraction $fp64b, int $divisor, int $rounding_mode = RoundingMode::DEFAULT) : int
  1661.     {
  1662.         // TODO: Verify that divisors are being chosen correctly.
  1663.         // (Actually the below seems to be pretty well argued, now that it's
  1664.         // all been written down. Still, we should make sure it all gets tested.)
  1665.         // TODO: Make sure unittests cover all of the branches in this function.
  1666.  
  1667.         // ---=== Design Notes ===---
  1668.         // I am currently reasoning like so:
  1669.         //
  1670.         // Suppose we multiply two numbers, `a` and `b`.
  1671.         // `a` has a denominator of 2^16, giving it 16 bits of precision.
  1672.         // `b` has a denominator of 2^8, giving it 8 bits of precision.
  1673.         //
  1674.         // The product `a * b` will then have 24 bits of precision, with a denominator of 2^24.
  1675.         //
  1676.         // If we want to store the product into `a'`, which has the same precision as `a`,
  1677.         // then we will need to divide the product by 2^8 (the denominator of `b`)
  1678.         // to acquire a value with 16 bits of precision (because `16 = 24 - 8`).
  1679.         //
  1680.         // If we want to store the product into `b'`, which has the same precision as `b`,
  1681.         // then we will need to divide the product by 2^16 (the denominator of `a`)
  1682.         // to acquire a value with 8 bits of precision (because `8 = 24 - 16`).
  1683.         //
  1684.         // If we want to store the product into `c`,  which has N bits of precision,
  1685.         // then we will need to divide by the number of bits required to reach
  1686.         // that: `24 - x = N`, so `x = 24 - N`.
  1687.         // We divide by `2^(24 - N)` to reach the precision for `c`.
  1688.         //
  1689.         // But wait, what if `N>24`? Well, that's a good thing to notice,
  1690.         // because the destination may actually have more precision than
  1691.         // is given by the product of the multiplicands' denominators.
  1692.         // In that case, we will need to multiply instead of divide!
  1693.         //
  1694.         // Now, what if `a` has `P` bits of precision, and `b` has `Q` bits of precision?
  1695.         // We will need to adjust our formula slightly:
  1696.         // `x = (P+Q) - N`.
  1697.         //
  1698.         // Now, what if `a` has an arbitrary denominator `A` and `b`, likewise has `B`?
  1699.         // The full (wide) product will have a denominator of `AB = A * B`.
  1700.         //
  1701.         // To store into `a'`, we'll need to find `A` in terms of `AB` and `B`.
  1702.         // We write `A` like so: `A = (A * B) / B`.
  1703.         // Thus, `A = AB / B` (by substitution.).
  1704.         //
  1705.         // To store into `b'`, we'll need to find `B` in terms of `AB` and `A`.
  1706.         // We write `B` like so: `B = (A * B) / A`.
  1707.         // Thus, `B = AB / A` (by substitution.).
  1708.         //
  1709.         // To store into `c`, we'll write `C` in terms of `AB` and `X`, then find `X`.
  1710.         // `C = AB/X`
  1711.         // `C*X = AB`
  1712.         // `X = AB/C`
  1713.         // In the code, we will already know `C` because it is the denominator of `c`.
  1714.         // We will need to find `X` so that we can call `divide_128x64` with it.
  1715.         // Now we know how to do that. (I hope.)
  1716.         //
  1717.         // Another algebraic expression for how `c`'s numerator (`cn`) would be calculated:
  1718.         //   cn/cd = (an/ad) * (bn/bd)
  1719.         //   cn = (an/ad) * (bn/bd) * cd
  1720.         //   cn = ((an*bn) / (ad*bd)) * cd
  1721.         //   cn = (an * bn * cd) / (ad * bd)
  1722.         //   cn = (an * bn) * (cd / (ad * bd)) <- if( cd < (ad*bd) ) { do this? }
  1723.         //   cn = (an * bn) / ((ad * bd) / cd) <- if( (ad*bd) < cd ) { do this? }
  1724.  
  1725.         Testing::_assert($divisor > 0);
  1726.         Testing::_assert($divisor <= PHP_INT_MAX);
  1727.  
  1728.         $a = $fp64a->numerator;
  1729.         $b = $fp64b->numerator;
  1730.         $a_div = $fp64a->denominator;
  1731.         $b_div = $fp64b->denominator;
  1732.  
  1733.         // ---=== Multiplication ===---
  1734.         // Multiply 64bit * 64bit to yield 128bit value.
  1735.         $lo = (int)0;
  1736.         $hi = (int)0;
  1737.         Int128::multiply_64x64($a,  $b,  $hi,$lo);
  1738.  
  1739.         // Do the same for the denominators/divisor.
  1740.         $div_lo = (int)0;
  1741.         $div_hi = (int)0;
  1742.         Int128::multiply_64x64($a_div,  $b_div,  $div_hi,$div_lo);
  1743.  
  1744.         // ---=== Division: Denominator ===---
  1745.         // We need to figure out what number to divide or new numerator by,
  1746.         // so that it ends up with the precision described by `$divisor`.
  1747.         // This will be `($a->denominator * $b->denominator) / $divisor`.
  1748.         $scale_direction = (int)0;
  1749.         $div_quotient_lo = (int)0;
  1750.         $div_quotient_hi = (int)0;
  1751.         $div_remainder   = (int)0;
  1752.         if ( $divisor === 0 || $divisor === 1 ) {
  1753.             Testing::_assert($scale_direction === 0);
  1754.             $div_quotient_lo = $div_lo;
  1755.             $div_quotient_hi = $div_hi;
  1756.             Testing::_assert($div_remainder === 0);
  1757.         } else
  1758.         if ( 0 === $div_hi && $divisor > $div_lo ){
  1759.             $scale_direction = 1;
  1760.             // TODO: Division here is not guaranteed to be twos-complement compatible.
  1761.             $div_quotient_lo = intdiv($divisor, $div_lo);
  1762.             Testing::_assert($div_quotient_hi === 0);
  1763.             $div_remainder = $divisor % $div_lo;
  1764.             // TODO: What to do with $div_remainder?
  1765.         }
  1766.         else {
  1767.             $scale_direction = -1;
  1768.             $div_remainder = Int128::divide_128x64($div_hi,$div_lo,  $divisor,  $div_quotient_hi,$div_quotient_lo);
  1769.  
  1770.             // TODO: This limitation isn't strictly necessary;
  1771.             // this is something that CAN happen with valid inputs,
  1772.             // and there is going to be a way to handle it.
  1773.             // It just seems kinda unlikely, and I don't have the time to write it right now.
  1774.             if ( $div_quotient_hi !== 0 ) {
  1775.                 // TODO: Better error message; put parameters and details about the denominators.
  1776.                 $class_name = __CLASS__;
  1777.                 $func_name = __FUNCTION__;
  1778.                 throw new \Exception(
  1779.                     "$class_name::$func_name: Unimplemented combination of input parameters; ".
  1780.                     "The product of the inputs' denominators divided by the destination's denominator ".
  1781.                     "must be a number that fits within PHP_INT_MAX.");
  1782.             }
  1783.             // TODO: What to do with $div_remainder?
  1784.         }
  1785.         // TODO: $div_remainder is a smell suggesting that we haven't done enough math or something.
  1786.         // In particular, this codepath is making it clear that handling arbitrary
  1787.         // input denominators leads to situations where there is no common factor
  1788.         // to divide by.
  1789.         //
  1790.         // Like, if `A = 2^16` and `B = 2^8`, then either `C = 2^16` or `C = 2^8`
  1791.         // will both work fine because `AB = 2^24` which has even factors of both 2^16 and 2^8.
  1792.         // `C` could be any power-of-2 in that situation, though powers greater than 23
  1793.         // will either cause us to do zero scaling or scale up (multiply the result and zero-fill the LSBs).
  1794.         //
  1795.         // However, if `A = 3` and `B = 5`, then `C` has to be some multiple
  1796.         // of either 3 or 5 in order for the scaling to happen cleanly.
  1797.         // If we plug in `C = 2`, then we get `X = 15/2`, which is clearly not an integer.
  1798.         // (It might be possible to get around this by using those remainders
  1799.         // in the later scaling expressions, but it is clear how in my current sleepy state.)
  1800.  
  1801.         // ---=== Rounding ===---
  1802.         // Round the 128bit value, modulo the `$divisor` parameter.
  1803.         // (We really only need to do this for the lower 64 bits, because $divisor can't be bigger than that.)
  1804.         // TODO: Implement more rounding modes? (Also `banker_round` is pretty sus at the moment b/c sleep not enough.)
  1805.         if ( $scale_direction < 0 )
  1806.         {
  1807.             if ( $rounding_mode == RoundingMode::HALF_TOWARDS_EVEN ) {
  1808.                 $lo = self::banker_round($lo, $divisor);
  1809.             } else
  1810.             if ( $rounding_mode != RoundingMode::DEFAULT ) {
  1811.                 throw new \Exception("Unimplemented rounding mode ".RoundingMode::to_string($rounding_mode));
  1812.             }
  1813.         }
  1814.  
  1815.         // ---=== Division (or multiplication): Numerator ===---
  1816.         // Shrink the 128bit value until it is at the desired precision according to `$divisor`.
  1817.         // This will ready it for overflow checking.
  1818.         $quotient_lo = (int)0;
  1819.         $quotient_hi = (int)0;
  1820.         $remainder   = (int)0;
  1821.         if ( $scale_direction === 0 ) {
  1822.             $quotient_lo = $lo;
  1823.             $quotient_hi = $hi;
  1824.             Testing::_assert($remainder === 0);
  1825.         } else
  1826.         if ( $scale_direction > 0 ) {
  1827.             // Least likely case of all of them, but also the most complicated.
  1828.             $tmp1_out_lo = (int)0;
  1829.             $tmp1_out_hi = (int)0;
  1830.             $tmp2_out_lo = (int)0;
  1831.             $tmp2_out_hi = (int)0;
  1832.             Int128::multiply_64x64($lo,  $div_quotient_lo,  $tmp1_out_hi,$tmp1_out_lo);
  1833.             Int128::multiply_64x64($hi,  $div_quotient_lo,  $tmp2_out_hi,$tmp2_out_lo);
  1834.             $quotient_lo = $tmp1_out_lo;
  1835.             $quotient_hi = $tmp1_out_hi + $tmp2_out_lo;
  1836.             Testing::_assert($tmp2_out_hi === 0);
  1837.         } else
  1838.         if ( $scale_direction < 0 ) {
  1839.             $remainder = Int128::divide_128x64($hi,$lo,  $divisor,  $quotient_hi,$quotient_lo);
  1840.         }
  1841.  
  1842.         // ---=== Overflow/Error Handling ===---
  1843.         // Now we check for overflow (and maybe do some validation on rounding logic).
  1844.         // If there is no overflow, then we can safely discard the high part of the quotient.
  1845.         if ( $rounding_mode != RoundingMode::DEFAULT ) {
  1846.             Testing::_assert($remainder === 0); // Because rounding should have handled this already.
  1847.         }
  1848.  
  1849.         if ( 0 !== $quotient_hi ) {
  1850.             $class_name = __CLASS__;
  1851.             $func_name = __FUNCTION__;
  1852.             $rounding_mode_str = RoundingMode::to_string($rounding_mode);
  1853.             throw new \ArithmeticError(sprintf(
  1854.                 "Overflow in `$class_name::$func_name`. ".
  1855.                 "Parameters: {fp64a->numerator:%016X, fp64a->denominator:%016X, fp64b->numerator:%016X, fp64b->denominator:%016x, divisor:%016X, rounding_mode:$rounding_mode_str}",
  1856.                 $fp64a->numerator, $fp64a->denominator, $fp64b->numerator, $fp64b->denominator, $divisor
  1857.                 ));
  1858.         }
  1859.  
  1860.         // ---=== Return ===---
  1861.         return $quotient_lo;
  1862.     }
  1863.  
  1864.     public static function unittest_multiply() : void
  1865.     {
  1866.         // Left as exercise for reader.
  1867.         echo(__CLASS__."::".__FUNCTION__."...");
  1868.         echo(" done.\n");
  1869.     }
  1870.  
  1871.     public function divide_by_into(WideFraction $denominator, WideFraction &$quotient, WideInt? &$Remainder = null) : void
  1872.     {
  1873.         throw new UnimplementedException(__CLASS__."::".__FUNCTION__." hasn't been implemented yet.");
  1874.     }
  1875.  
  1876.     /*
  1877.     * Copies all state (ex: numerator and denominator) from one WideFraction
  1878.     * to another, with the requirement that both of them must be of the same
  1879.     * type, and that type must be the class this method is in.
  1880.     *
  1881.     * Those constraints lend themselves to a pretty straight-forward
  1882.     * implementation that doesn't have many (if any) bounds/validity checks
  1883.     * required.
  1884.     */
  1885.     public static function blit(self $dest, self $source) : void
  1886.     {
  1887.         @@php
  1888.         for ($template->parts() as $part) {
  1889.             $numerator_part = $part->numerator;
  1890.             $denominator_part = $part->denominator;
  1891.             $template->set_indentation(2);
  1892.             $template->echo_code("\$dest->$numerator_part   = \$source->$numerator_part;\n");
  1893.             $template->echo_code("\$dest->$denominator_part = \$source->$denominator_part\n");
  1894.         }
  1895.         @@
  1896.     }
  1897.  
  1898.     /*
  1899.     * Modifies the given WideFraction by replacing it with its inverse.
  1900.     *
  1901.     * Mathematically, the inverse of a rational number `n / d` is `d / n`.
  1902.     * In other words: inverting a fraction is the same as swapping its
  1903.     * numerator and denominator.
  1904.     *
  1905.     * This probably won't be used much for code that uses wide fractions
  1906.     * as fixed-point numbers, but it can be handy in some calculations
  1907.     * because it does an operation similar to division
  1908.     * (e.g. `$my_frac->invert()` computes `WideFraction::divide(1,$my_frac)`),
  1909.     * but with none of the costs of division.
  1910.     *
  1911.     *
  1912.     *
  1913.     * @see inverse_into
  1914.     * @see inverse_from
  1915.     */
  1916.     public function invert() : void
  1917.     {
  1918.         @@php
  1919.         for ($template->parts as $part) {
  1920.             $numerator_part = $part->numerator;
  1921.             $denominator_part = $part->denominator;
  1922.             $template->set_indentation(2);
  1923.             $template->echo_code("\$temp = \$this->$denominator_part;\n");
  1924.             $template->echo_code("\$this->$numerator_part = \$this->$denominator_part;\n");
  1925.             $template->echo_code("\$this->$denominator_part = \$temp\n");
  1926.         }
  1927.         @@
  1928.     }
  1929.  
  1930.     /*
  1931.     * @see invert
  1932.     * @see inverse_from
  1933.     */
  1934.     public function inverse_into(WideFraction $dest) : self
  1935.     {
  1936.         self::blit($dest,$this);
  1937.         $dest->invert();
  1938.         return $dest;
  1939.     }
  1940.  
  1941.  
  1942.     /*
  1943.     * @see invert
  1944.     * @see inverse_into
  1945.     */
  1946.     public function inverse_from(WideFraction $src) : self
  1947.     {
  1948.         self::blit($this,$src);
  1949.         $this->invert();
  1950.         return $this;
  1951.     }
  1952.  
  1953.     /*
  1954.     * Allocates a new instance of the same class as `$this`, then copies
  1955.     * the contents of `$this` into that new instance.
  1956.     *
  1957.     * @return  self  The new instance.
  1958.     */
  1959.     public function dup() : self
  1960.     {
  1961.         $result = new self();
  1962.         self::blit($result,$this);
  1963.         return $result;
  1964.     }
  1965.  
  1966.     public static function unittest() : void
  1967.     {
  1968.         echo("Unittests for ".__CLASS__."\n");
  1969.         // Put unittests for other methods here...
  1970.         self::unittest_banker_round();
  1971.         // ... or here ...
  1972.         self::unittest_multiply();
  1973.         // ... or here.
  1974.         echo("\n");
  1975.     }
  1976. }
  1977.  
  1978. @@php
  1979. } // variable_scoping_function
  1980. variable_scoping_function();
  1981. @@
  1982. ?>
  1983.  
  1984.  
  1985. <?php
  1986. // WideFixedFraction.php
  1987. /*
  1988. declare(strict_types=1);
  1989.  
  1990. namespace Kickback\Common\Math\Types;
  1991.  
  1992. use \Kickback\Common\Math\Types\Integer;
  1993. use \Kickback\Common\Math\RoundingMode;
  1994. use \Kickback\Common\Math\Signedness;
  1995. */
  1996.  
  1997. /**
  1998. * This is the conventional class to use when constructing a WideFraction
  1999. * with a constant denominator.
  2000. *
  2001. * It is otherwise nearly identical to the WideFraction class (and type).
  2002. *
  2003. * @see WideFraction
  2004. */
  2005. abstract class WideFixedFraction extends WideFraction
  2006. {
  2007.     // TODO: Finish designing all of the WideFraction factory methods,
  2008.     // then create analogous versions in this class.
  2009.  
  2010.     public static function make(
  2011.         // runtime parameter(s):
  2012.         int $numerator = 0,
  2013.         int $denominator = 0, // can be elided (left as 0) if assigning a constant denominator.
  2014.  
  2015.         // named template parameters:
  2016.         int  $numerator_bit_width,
  2017.         int  $denominator_bit_width = 0, // Either this or $constant_denominator_int must be non-zero.
  2018.         int  $constant_denominator_int = 0, // Either this or $denominator_bit_width must be non-zero.
  2019.         // TODO: constant_denominator_wide?
  2020.         bool $has_constant_config = false,
  2021.         int  $signedness = Signedness::SIGNED,
  2022.         int  $rounding_mode = RoundingMode::DEFAULT,
  2023.  
  2024.     ) : void
  2025.     {
  2026.         $template = WideFractionTemplate::instantiate(__NAMESPACE__,__CLASS__,
  2027.             numerator_width:$bit_width,
  2028.             constant_denominator_int:$denominator);
  2029.         $template_class_path = $template->class_path();
  2030.         if ( $has_constant_config ) {
  2031.             $result = new $template_class_path($numerator,$denominator);
  2032.         } else {
  2033.             $result = new $template_class_path($numerator,$denominator, signedness:$signedness, rounding_mode:$rounding_mode);
  2034.         }
  2035.         throw new UnimplementedException(__CLASS__."::".__FUNCTION__." hasn't been implemented yet.");
  2036.         return $result;
  2037.     }
  2038. }
  2039. ?>
  2040.  
  2041. <?php
  2042. // WideFraction.php
  2043. /*
  2044. declare(strict_types=1);
  2045.  
  2046. namespace Kickback\Common\Math\Types;
  2047.  
  2048. use \Kickback\Common\Math\Types\Integer;
  2049. use \Kickback\Common\Math\RoundingMode;
  2050. use \Kickback\Common\Math\Signedness;
  2051. */
  2052.  
  2053.     // TODO: I really like being able to see the broad overview above,
  2054.     // the list of what exists. I'm tempted to make an interface that
  2055.     // just has all of the methods of the WideFraction class, but none
  2056.     // of the verbose documentation. WideFraction would then implement
  2057.     // that interface to ensure the two remain in sync. There would otherwise
  2058.     // be no reason for any calling code to use the interface; it'd just
  2059.     // be there to provide synchronization guarantees on
  2060.     // "read the source"-style documentation.
  2061.     // And then it would be admissible to put really long descriptions on all
  2062.     // of the WideFraction methods. It'd become hard to see, from text editor PoV,
  2063.     // what methods exist, but then we'd be able to just look at the interface
  2064.     // and know (most) of what's available.
  2065.     //
  2066.     // Update: I wrote the interface. (Untested.) It's below.
  2067.  
  2068. // Yes, this interface will probably just be put into WideFraction.php.
  2069. // Yes, that will make it impossible to autoload this interface.
  2070. // This is perfectly fine. This interface isn't meant to be actually used.
  2071. // It's meant to document what's available in the WideFraction class,
  2072. // for anyone using a text editor that wants a concise reference.
  2073. // (It is very difficult to write decently descriptive comments in the
  2074. // WideFraction class without also making it VERY difficult to see where
  2075. // the definitions are and which definitions are available. Good for detailed
  2076. // reading, but bad for "at a glance". The interface is intended to complement
  2077. // that documentation by providing an "at a glance" version.)
  2078. //
  2079. // In other words:
  2080. // There is  no reason for any calling code to use the interface;
  2081. // it's just here to provide synchronization guarantees for
  2082. // "read the source"-style documentation.
  2083. //
  2084. // It is good to put this in WideFraction.php if possible, because the
  2085. // two things will have a circular dependency:
  2086. // WideFractionMethods depends on WideFraction for defining method parameters,
  2087. // while WideFraction depends on WideFractionMethods (well, "implements" it)
  2088. // to keep the method definitions synchronized.
  2089. interface WideFractionMethods
  2090. {
  2091.     // TODO: Paste uncommented copies of all of the WideFraction methods
  2092.     // here (and remove the `absract` attribute because interfaces don't use that).
  2093.     // This interface will then serve as a quick reference (from text-editor perspective)
  2094.     // of what's available in the WideFraction class.
  2095.  
  2096.     // Here's an example, the comparison methods are already moved over:
  2097.     // (Compare to the scene in the WideFraction class!)
  2098.  
  2099.     // ---=== Configuration properties ===---
  2100.  
  2101.     public function has_constant_denominator() : bool;
  2102.     public function has_constant_config() : bool;
  2103.     public function numerator_bit_width() : int;
  2104.     public function denominator_bit_width() : int;
  2105.     public function signedness(int? $new_signedness = null) : int;
  2106.     public function rounding_mode(int? $new_rounding_mode = null) : int;
  2107.  
  2108.     // ---=== Internal Accessors ===---
  2109.  
  2110.     // These are intentionally absent from the interface.
  2111.     // (It might not be THAT bad to put them here, but it's the kind of
  2112.     // thing we should probably only do if there's a need for it.)
  2113.  
  2114.     // ---=== Comparison operations ===---
  2115.  
  2116.     /** Default comparisons */
  2117.     public function cmp(WideFraction $other) : int;
  2118.     public function eq(WideFraction $other) : bool; /** @see cmp */
  2119.     public function ne(WideFraction $other) : bool; /** @see cmp */
  2120.     public function lt(WideFraction $other) : bool; /** @see cmp */
  2121.     public function gt(WideFraction $other) : bool; /** @see cmp */
  2122.     public function lte(WideFraction $other) : bool; /** @see cmp */
  2123.     public function gte(WideFraction $other) : bool; /** @see cmp */
  2124.  
  2125.     /** Default comparisons with integer right-hand-side */
  2126.     public function cmp_int(int $other) : int;
  2127.     public function eq_int(int $other) :  bool; /** @see cmp_int */
  2128.     public function ne_int(int $other) :  bool; /** @see cmp_int */
  2129.     public function lt_int(int $other) :  bool; /** @see cmp_int */
  2130.     public function gt_int(int $other) :  bool; /** @see cmp_int */
  2131.     public function lte_int(int $other) : bool; /** @see cmp_int */
  2132.     public function gte_int(int $other) : bool; /** @see cmp_int */
  2133.  
  2134.     /** Default comparisons with string right-hand-side */
  2135.     public function cmp_str(string $other) : int;
  2136.     public function eq_str(string $other) : bool;  /** @see cmp_str */
  2137.     public function ne_str(string $other) : bool;  /** @see cmp_str */
  2138.     public function lt_str(string $other) : bool;  /** @see cmp_str */
  2139.     public function gt_str(string $other) : bool;  /** @see cmp_str */
  2140.     public function lte_str(string $other) : bool; /** @see cmp_str */
  2141.     public function gte_str(string $other) : bool; /** @see cmp_str */
  2142.  
  2143.     /** (U)nsigned WideFraction comparisons */
  2144.     public function ucmp(WideFraction &$other) : int;
  2145.     public function ueq(WideFraction &$other) : bool;  /** @see ucmp */
  2146.     public function une(WideFraction &$other) : bool;  /** @see ucmp */
  2147.     public function ult(WideFraction &$other) : bool;  /** @see ucmp */
  2148.     public function ugt(WideFraction &$other) : bool;  /** @see ucmp */
  2149.     public function ulte(WideFraction &$other) : bool; /** @see ucmp */
  2150.     public function ugte(WideFraction &$other) : bool; /** @see ucmp */
  2151.  
  2152.     /** (U)nsigned integer comparisons */
  2153.     public function ucmp_int(int $other) : int;
  2154.     public function ueq_int(int $other) : bool;  /** @see ucmp_int */
  2155.     public function une_int(int $other) : bool;  /** @see ucmp_int */
  2156.     public function ult_int(int $other) : bool;  /** @see ucmp_int */
  2157.     public function ugt_int(int $other) : bool;  /** @see ucmp_int */
  2158.     public function ulte_int(int $other) : bool; /** @see ucmp_int */
  2159.     public function ugte_int(int $other) : bool; /** @see ucmp_int */
  2160.  
  2161.     /** (U)nsigned string comparisons */
  2162.     public function ucmp_str(string $other) : int;
  2163.     public function ueq_str(string $other) : bool;  /** @see ucmp_str */
  2164.     public function une_str(string $other) : bool;  /** @see ucmp_str */
  2165.     public function ult_str(string $other) : bool;  /** @see ucmp_str */
  2166.     public function ugt_str(string $other) : bool;  /** @see ucmp_str */
  2167.     public function ulte_str(string $other) : bool; /** @see ucmp_str */
  2168.     public function ugte_str(string $other) : bool; /** @see ucmp_str */
  2169.  
  2170.     /** (S)igned WideFraction comparisons */
  2171.     public function scmp(WideFraction &$other) : int;
  2172.     public function seq(WideFraction &$other) : bool;  /** @see scmp */
  2173.     public function sne(WideFraction &$other) : bool;  /** @see scmp */
  2174.     public function slt(WideFraction &$other) : bool;  /** @see scmp */
  2175.     public function sgt(WideFraction &$other) : bool;  /** @see scmp */
  2176.     public function slte(WideFraction &$other) : bool; /** @see scmp */
  2177.     public function sgte(WideFraction &$other) : bool; /** @see scmp */
  2178.  
  2179.     /** (S)igned integer comparisons */
  2180.     public function scmp_int(int $other) : int;
  2181.     public function seq_int(int $other) : bool;  /** @see scmp_int */
  2182.     public function sne_int(int $other) : bool;  /** @see scmp_int */
  2183.     public function slt_int(int $other) : bool;  /** @see scmp_int */
  2184.     public function sgt_int(int $other) : bool;  /** @see scmp_int */
  2185.     public function slte_int(int $other) : bool; /** @see scmp_int */
  2186.     public function sgte_int(int $other) : bool; /** @see scmp_int */
  2187.  
  2188.     /** (S)igned string comparisons */
  2189.     public function scmp_str(string $other) : int;
  2190.     public function seq_str(string $other) : bool;  /** @see scmp_str */
  2191.     public function sne_str(string $other) : bool;  /** @see scmp_str */
  2192.     public function slt_str(string $other) : bool;  /** @see scmp_str */
  2193.     public function sgt_str(string $other) : bool;  /** @see scmp_str */
  2194.     public function slte_str(string $other) : bool; /** @see scmp_str */
  2195.     public function sgte_str(string $other) : bool; /** @see scmp_str */
  2196.  
  2197.     // ---=== Arithmetic operations ===---
  2198.  
  2199.     // TODO: Replace all of the `self` with WideFraction.
  2200.     public function add(WideFraction &$a, WideFraction &$b, WideFraction? &$c = null, WideFraction? &$d = null) : self;
  2201.     public function add_ww(WideFraction &$a, WideFraction &$b, WideFraction? &$c = null, WideFraction? &$d = null) : self;
  2202.     public function add_wi(WideFraction &$a, int $b) : self;
  2203.     public function add_iw(int $a, WideFraction &$b) : self;
  2204.     public function add_ii(int $a, int $b) : self;
  2205.     public function increment_by(WideFraction &$b) : void;
  2206.     public function increment() : void;
  2207.     public function incr_by(int $b) : void;
  2208.     public function incr() : void; // Should do same thing as `increment()`.
  2209.     public function subtract(WideFraction &$a, WideFraction &$b) : self;
  2210.     public function decrement_by(WideFraction &$b) : void;
  2211.     public function decrement() : void;
  2212.     public function decr_by(int $b) : void;
  2213.     public function decr() : void;
  2214.     public function negate() : void;
  2215.     public function multiply(WideFraction &$a, WideFraction &$b, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2216.     public function mult(WideFraction &$a, int $b, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2217.     public function multiply_by(WideFraction &$b, int $rounding_mode = RoundingMode::DEFAULT) : void;
  2218.     public function mult_by(int $b, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2219.     public function divide(WideFraction &$numerator, WideFraction &$denominator, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2220.     public function div(WideFraction &$numerator, int $denominator, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2221.     public function divide_by(WideFraction &$denominator, int $rounding_mode = RoundingMode::DEFAULT) : void;
  2222.     public function div_by(int $denominator, int $rounding_mode = RoundingMode::DEFAULT) : void;
  2223.     public function modulus(WideFraction &$numerator, WideFraction &$denominator, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2224.     public function mod(WideFraction &$numerator, int $denominator, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2225.     public function modulus_by(WideFraction &$denominator, int $rounding_mode = RoundingMode::DEFAULT) : void;
  2226.     public function mod_by(int $denominator, int $rounding_mode = RoundingMode::DEFAULT) : void;
  2227.     public function divide_and_modulus(WideFraction &$numerator, WideFraction &$denominator, WideFraction &$out_remainder, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2228.     public function div_n_mod(WideFraction &$numerator, int $denominator, int &$out_remainder, int $rounding_mode = RoundingMode::DEFAULT) : self;
  2229.     public function divide_and_modulus_by(WideFraction &$denominator, WideFraction &$out_remainder, int $rounding_mode = RoundingMode::DEFAULT) : void;
  2230.     public function div_n_mod_by(int $denominator, int &$out_remainder, int $rounding_mode = RoundingMode::DEFAULT) : void;
  2231.     public function inverse_of(WideFraction &$a) : self;
  2232.     public function invert() : self;
  2233.  
  2234.     // ---=== Logical operations ===---
  2235.     public function sign() : int;
  2236. }
  2237.  
  2238. // TODO: How to ensure that WideFraction operations are not aliasing results?
  2239. // Ex:
  2240. // $a = WideFraction::from_integer(64, 1, 100);
  2241. // $b = WideFraction::from_integer(64, 2, 100);
  2242. // $c = WideFraction::from_integer(64, 3, 100);
  2243. // $d = WideFraction::from_integer(64, 0, 100);
  2244. // $e = WideFraction::from_integer(64, 0, 100);
  2245. //
  2246. // $e->add($d->add($a,$b),$d->add($a,$c));
  2247. //
  2248. // // Problem: the above expression requires $d to store two addition results
  2249. // // before $e even has a chance to see either result.
  2250. // // Likely, the 2nd one (depending on PHP's order-of-arg-evaluation)
  2251. // // will save its result, and the first will be aliased to that.
  2252. //
  2253. // Bad result #1: $e->equals(6) // $e <- (3 + 3) because $a+$b was the prior add op and overwrote the first add op
  2254. // Bad result #2: $e->equals(8) // $e <- (4 + 4) because $a+$c was the prior add op and overwrote the first add op
  2255. // Good result: $e->equals(7) // $e <- (3 + 4) <- ((1+2) + (1+3))
  2256. //
  2257. // If you're having trouble seeing it, think of the above in terms
  2258. // of builtin variables with normal expressions, except that you're required
  2259. // to always do an assignment with every operation:
  2260. //
  2261. // int $a = 1;
  2262. // int $b = 2;
  2263. // int $c = 3;
  2264. // int $d = 0;
  2265. // int $e = 0;
  2266. //
  2267. // $e = (($d = $a + $b) + ($d = $a + $c));
  2268. //
  2269. // What would you think the above expression would evaluate to?
  2270. // Because unless PHP does something very profound, it won't be 7.
  2271. // (OH SHIT. I just ran it. PHP, uh, did something very profound. How the fnck?)
  2272. //
  2273. // Anyhow...
  2274. //
  2275. // Even if PHP somehow clones variables for us, it'll still probably require
  2276. // memory allocations, which are probably multiple orders of magnitude slower
  2277. // than any of the operations that will be done by these things (including multiplication and division, of course).
  2278. // It would (probably) mean that PHP is silently subverting the whole
  2279. // "preallocate your shit" doctrine that this API is designed to use.
  2280. //
  2281. // And some thoughts about mitigation:
  2282. // Maybe this can at least be caught dynamically with some kind of Exception("Value \$a was assigned but never used!") kind of detection+response?
  2283. // Unfortunately, this will require storing one bit of information. And can't be made constant. Ugh.
  2284. // (And given that the above example PHP returns 7, will it just automatically clone things when a mutating member is called? That would be very hard to detect or anticipate. HMmmmm.)
  2285. // (Actually, I wouldn't be surprised if ref parameters are a way to avoid that kind of undetectable scenario.
  2286. // (They'd even allow $b to detect if the arguments are the same object, and throw an error for that!)
  2287. // (Alright, I'm going to change the API for that really quick, because that's the most likely good scenario.)
  2288. // Oh I will probably call it "Write Protection"! What a throw back! (You know, like the little dinky slide-switch on 3.5" floppies that you accidentally flip, so as to prevent yourself from being able to use your own equipment. Good fun!)
  2289.  
  2290.  
  2291. /**
  2292. * The WideFraction type is represented as a sequence of built-in `int` integers
  2293. * for its numerator, and another such sequence as its denominator, along with
  2294. * an auxiliary single `int` used to store dynamic configuration.
  2295. *
  2296. * The primary intended use-case for this class is as
  2297. * a highly flexible variable-base fixed-point number representation.
  2298. * It is expected to be usually used as a way to do precise and exacting
  2299. * decimal calculations. As an unintended consequence, it may be able to
  2300. * do some other interesting operations too (ex: approximate rational numbers),
  2301. * but that functionality will not be a development priority.
  2302. *
  2303. * The size of these sequences is fixed upon template instantiation.
  2304. *
  2305. * The denominator will conventionally be defined by calling factory methods
  2306. * in the `WideFixedFraction` class.
  2307. * The denominator may also be defined as a constant during template instantiation,
  2308. * by specifying "constant_denominator=(your chosen denominator)" as a template
  2309. * parameter (this is what `WideFixedFraction` does under-the-hood).
  2310. *
  2311. * Using a constant denominator allows the WideFraction instance to elide storing
  2312. * the denominator entirely. It also provides optimization opportunities
  2313. * for some operations where an intermediate can be precomputed when
  2314. * the denominators are constant. Internally, the template will replace
  2315. * all variable references to the denominator with literal values.
  2316. *
  2317. * The WideFraction's configuration information can be made constant as well.
  2318. * This will elide the auxilliary integer used to represent that information.
  2319. * This is done by passing the "constant_config" or "constant_config=true"
  2320. * template parameter, and then specifying values for any configuration
  2321. * that the caller requires to be different from the defaults.
  2322. * These template parameters will have the same name as their property
  2323. * counterparts in the class itself.
  2324. *
  2325. * Attempting to call a config property setter on a WideFraction that has
  2326. * constant properties will result in an Exception being thrown.
  2327. * (TODO: Define a more specific exception class for this.)
  2328. *
  2329. * WideFractions may be signed, unsigned, or ambiguously signed.
  2330. *
  2331. * These states are enumerated in the `Signedness` constant class.
  2332. *
  2333. * When a WideFraction is ambiguously signed, the way the value is handled during
  2334. * some operations (ex: comparison) will depend on which variation of the
  2335. * operation is used. Most operations (ex: addition, subtraction, negation,
  2336. * all logical operations, and so on) are inherently sign agnostic (due to
  2337. * how they work on twos-complement numbers), and will not have separate
  2338. * versions for informing signed-versus-unsigned behavior on
  2339. * ambiguously signed WideFractions.
  2340. *
  2341. * WideFractions may have a default RoundingMode, which can be set through
  2342. * the `rounding_mode` property.
  2343. *
  2344. * (Future direction: if we find it tedious to always specify rounding mode
  2345. * after constructing WideFractions, we might be able to implement a feature
  2346. * where we can instantiate the template separately from object construction,
  2347. * then give the template a "initial_default_rounding_mode" parameter, then
  2348. * use the template's `make_*` factory functions to yield WideFractions
  2349. * that will then always have the desired RoundingMode.)
  2350. *
  2351. * The de facto implementation of this type is implemented by generating a class
  2352. * that simply has all of the integers present in it as plain variables.
  2353. * This ensures type safety and may possibly compute faster, as it requires
  2354. * PHP to do fewer (hopefully zero) memory allocations during normal arithmetic
  2355. * and logical operations, and doesn't add array operations on top of the
  2356. * integer operations that would need to be done in either case.
  2357. *
  2358. * This class template is built upon the static template WideIntegerOperations.
  2359. * The functions in WideIntegerOperations can be difficult or tedious to call
  2360. * (either they require the caller to know how many primitive integers
  2361. * they need to use for an operation in advance, or require the caller
  2362. * to implement a template to abstract that information), so the WideFraction
  2363. * class is not just providing fractional math implementations, but it is
  2364. * also providing a convenient abstraction for interacting with "Wide"
  2365. * number operations.
  2366. *
  2367. * Notably, WideInteger is a special case of WideFraction with
  2368. * a constant denominator that has a value of 1.
  2369. *
  2370. * @see RoundingMode
  2371. * @see Signedness
  2372. * @see WideFixedFraction
  2373. * @see WideIntegerOperations
  2374. */
  2375. abstract class WideFraction implements WideFractionMethods
  2376. {
  2377.     // NOTE: Just to be clear: None of the shit in this class is working right now.
  2378.     // Almost all of these methods don't exist yet.
  2379.     // The thing that DOES exist is some of the low-level logic that will
  2380.     // be required to implement them, and that makes me feel better about our odds.
  2381.  
  2382.     // TODO: When implementing these methods: pay attention to preventing aliasing of WideFraction parameters!
  2383.     // Also make sure that things like $this->cmp($other) check for aliasing $this to &$other.
  2384.     // That will not only make things safer, but in a case like cmp, it can be an optimization:
  2385.     // an expression is always equal to itself and never less than or greataer than!
  2386.     //
  2387.  
  2388.     // ---=== Initialization Methods ===---
  2389.     // e.g. Object Construction and Template Instantiation
  2390.  
  2391.     // TODO: Move this function into a WideFractionTemplate class.
  2392.     // It needs to be a static method either way, because templates are
  2393.     // supposed to be memoized, and having to `new` them would
  2394.     // look wrong in the caller's code, even if the new object
  2395.     // were to reuse all of the info from a previous instantiation.
  2396.     public static function instantiate(
  2397.         string $namespace, string $base_name, string $instance_name,
  2398.             // named template parameters:
  2399.             int  $numerator_bit_width,
  2400.             int  $denominator_bit_width = 0, // Either this or $constant_denominator_int must be non-zero.
  2401.             int  $constant_denominator_int = 0, // Either this or $denominator_bit_width must be non-zero.
  2402.             // TODO: constant_denominator_wide?
  2403.             bool $has_constant_config = false,
  2404.             int  $signedness = Signedness::SIGNED,
  2405.             int  $rounding_mode = RoundingMode::DEFAULT,
  2406.  
  2407.     ) : void
  2408.     {
  2409.         TODO: IMPORTANT: This is, of course, necessary for the thing to work at all.
  2410.     }
  2411.  
  2412.     /**
  2413.     * Factory method for creating WideFractions with dynamic denominators.
  2414.     *
  2415.     * To make a WideFraction with a constant denominator,
  2416.     * see the WideFixedFraction class.
  2417.     *
  2418.     * @see WideFixedFraction
  2419.     */
  2420.     public static function from_int(
  2421.         // required template parameters:
  2422.         int  $numerator_bit_width,
  2423.         int  $denominator_bit_width = 0, // defaults to being the same thing as the numerator.
  2424.  
  2425.         // runtime parameter(s):
  2426.         int  $numerator = 0,
  2427.         int  $denominator,
  2428.  
  2429.         // optional template parameters:
  2430.         bool $has_constant_config = false,
  2431.         int  $signedness = Signedness::SIGNED,
  2432.         int  $rounding_mode = RoundingMode::DEFAULT,
  2433.  
  2434.     ) : void
  2435.     {
  2436.         if ( 0 === $denominator_bit_width ) {
  2437.             $denominator_bit_width = $numerator_bit_width;
  2438.         }
  2439.  
  2440.         $template = WideFractionTemplate::instantiate(
  2441.             __NAMESPACE__,__CLASS__,
  2442.             numerator_width:       $numerator_bit_width,
  2443.             denominator_bit_width: $denominator_bit_width,
  2444.             has_constant_config:   $has_constant_config,
  2445.             signedness:            $signedness,
  2446.             rounding_mode:         $rounding_mode
  2447.         );
  2448.  
  2449.         $template_class_path = $template->class_path();
  2450.         $result = new $template_class_path($numerator,$denominator, signedness:$signedness, rounding_mode:$rounding_mode);
  2451.         throw new UnimplementedException(__CLASS__."::".__FUNCTION__." hasn't been implemented yet.");
  2452.         return $result;
  2453.     }
  2454.  
  2455.     // TODO: Given recent conversations, it might be a good idea to also
  2456.     // allow a percent sign (%) to go after any expressions in the string
  2457.     // handed to WideFraction::from_string(). This would allow us to
  2458.     // write percentage quantities in a natural way, which is helpful
  2459.     // for business programming, and possibly other things too.
  2460.     //
  2461.     // It miiight be a good idea to limit percentages to decimal sequences.
  2462.     // Because I have no idea what 0x93% would mean. Is it under or over 100%?
  2463.     // (If we DID do that, I'd be tempted to interpret 0x100% as equaling 1.000, and 0x80% as equaling 0.500)
  2464.     //
  2465.     // Sidenote: although I'm hoping to allow + and - signs to be used on
  2466.     // all types of literals (including binary, hex, octal, base-64),
  2467.     // I feel it IS important that it goes before any encoding prefix, ex: `0b, 0o, 0x, 0s64c_-n`.
  2468.     // E.g. this is OK: `-0xFF` while this is NOT ok: `0x-FF`.
  2469.     // (Because - is not a valid character in a hexadecimal sequence.)
  2470.  
  2471.     /**
  2472.     * The `WideFraction::from_string(...)` method constructs a WideFraction
  2473.     * by using strings to represent the `$numerator` and `$denominator`.
  2474.     *
  2475.     * If the `$denominator` is not specified, then the fractional part
  2476.     * of the value may be described using point notation, like so:
  2477.     * ```
  2478.     * // Decimal points
  2479.     * Testing::_assert(WideFraction::from_string(32, "1.24")->denominator_to_int(), 100);
  2480.     * Testing::_assert(WideFraction::from_string(32, "1.2")->denominator_to_int(), 10);
  2481.     * Testing::_assert(WideFraction::from_string(32, "1.")->denominator_to_int(), 1);
  2482.     *
  2483.     * // Hexadecimal points
  2484.     * Testing::_assert(WideFraction::from_string(32, "0x1B.F3")->denominator_to_int(), 256); // 0x100
  2485.     * Testing::_assert(WideFraction::from_string(32, "0x1B.F")->denominator_to_int(), 16);   // 0x10
  2486.     * Testing::_assert(WideFraction::from_string(32, "0x1B.")->denominator_to_int(), 1);     // 0x1
  2487.     *
  2488.     * // Binary points
  2489.     * Testing::_assert(WideFraction::from_string(32, "0b10.01")->denominator_to_int(), 4); // 0b100
  2490.     * Testing::_assert(WideFraction::from_string(32, "0b10.0")->denominator_to_int(), 2);  // 0b10
  2491.     * Testing::_assert(WideFraction::from_string(32, "0b10.")->denominator_to_int(), 1);   // 0b1
  2492.     * ```
  2493.     *
  2494.     * If the `$denominator` _is_ specified, then the fractional portion of
  2495.     * the numerator's string must not exceed the precision of the denominator.
  2496.     * Attempting to store something too precise will result in an exception being thrown. (TODO: define the exception. Pobably UnderflowSomethingSomething)
  2497.     *
  2498.     * The `$denominator`'s string may not use point notation. Putting a point
  2499.     * into the denominator string will result in an exception being thrown. (TODO: define the exception.)
  2500.     *
  2501.     * Future directions:
  2502.     * If it ever becomes convenient to store WideFractions as Base-64 encoded
  2503.     * strings, then it is entirely possible to expand the ::from_string method
  2504.     * to have that functionality.
  2505.     *
  2506.     * I envision base-64 functionality looking like this:
  2507.     *
  2508.     * In addition to PHP-style integer literals, this method supports
  2509.     * using base-64 encoded strings. The prefix for base-64 string literals
  2510.     * is as follows:
  2511.     *  "0s64cXXYn"
  2512.     * Where the two characters XX represent the two characters used in the base-64
  2513.     * encoding to represent values beyond the reach of the 62 digits and
  2514.     * (English) latin characters. The Y represents the character used as padding
  2515.     * at the end of the base-64 encoding. All padding characters at the end
  2516.     * of the literal will be ignored, and it is not necessary to pad the literal.
  2517.     * The Y character may be omitted, in which case the padding character is
  2518.     * assumed to be '='.
  2519.     *
  2520.     * Examples of valid base-64 literals are as such:
  2521.     * ```
  2522.     * "0s64c,-=nGL0srrt-FV,sdemLeQ"
  2523.     * "0s64c,-=nGL0srrt-FV,sdemLeQ=="
  2524.     * "0s64c,-nGL0srrt-FV,sdemLeQ=="
  2525.     * "0s64c,-#nGL0srrt-FV,sdemLeQ##"
  2526.     * "0s64c-_#nGL0srrt_FV-sdemLeQ##"
  2527.     * "0s64c-&#nGL0srrt_FV&sdemLeQ##"
  2528.     * "0s64c-&#nGL0srrt_FV&sd.emLeQ##" // The dot represents a decimal point.
  2529.     * "0s64c.&#nGL0srrt_FV&sd.emLeQ##" // The dot is a base64 character, not a decimal point.
  2530.     * ```
  2531.     *
  2532.     * Note: using '.' as an encoding character will prevent it from being used
  2533.     * to represent fractional quantities in the literal. Such encodings can
  2534.     * still be used to construct WideFractions as long as the denominator
  2535.     * is specified. And depending on how the data is defined, this might
  2536.     * be the best way to do things; likewise, being able to represent fractional
  2537.     * quantities in base64 literals is of limited value, given that such strings
  2538.     * are likely to be difficult to understand with human intuition and sense
  2539.     * of scale.
  2540.     *
  2541.     * (Reminder: All of this stuff about base-64 is unimplemented,
  2542.     * and may remain that way until there is a reason to implement it.)
  2543.     */
  2544.     public static function from_string(
  2545.         // required template parameters:
  2546.         int  $numerator_bit_width,
  2547.         int  $denominator_bit_width = 0, // defaults to being the same thing as the numerator.
  2548.  
  2549.         // runtime parameter(s):
  2550.         string  $numerator = "0",
  2551.         string  $denominator = "", // May be elided if the `$numerator` string contains a point (ex: decimal point).
  2552.  
  2553.         // optional template parameters:
  2554.         bool $has_constant_config = false,
  2555.         int  $signedness = Signedness::SIGNED,
  2556.         int  $rounding_mode = RoundingMode::DEFAULT,
  2557.  
  2558.     )
  2559.     {
  2560.         if ( 0 === $denominator_bit_width ) {
  2561.             $denominator_bit_width = $numerator_bit_width;
  2562.         }
  2563.  
  2564.         // TODO: Check to ensure the bitwidths are consistent with the numerator/denominator arguments.
  2565.  
  2566.         $template = WideFractionTemplate::instantiate(
  2567.             __NAMESPACE__,__CLASS__,
  2568.             numerator_width:       $numerator_bit_width,
  2569.             denominator_bit_width: $denominator_bit_width,
  2570.             has_constant_config:   $has_constant_config,
  2571.             signedness:            $signedness,
  2572.             rounding_mode:         $rounding_mode
  2573.         );
  2574.  
  2575.         $template_class_path = $template->class_path();
  2576.         $result = new $template_class_path(signedness:$signedness, rounding_mode:$rounding_mode);
  2577.         // TODO: String parsing functions
  2578.         $result->numerator_from_string($numerator);
  2579.         $result->denominator_from_string($denominator);
  2580.         return $result;
  2581.     }
  2582.  
  2583.     // TODO: Should I just dictate that the contents of the array always be 32-bit integers?
  2584.     // (I mean, PHP doesn't have a dedicated type for that, but they'll fit in 64-bit ints,
  2585.     // and it would mean that the caller's code doesn't have to special-path for the
  2586.     // different host system integer types.)
  2587.     /**
  2588.     * The intended use-case for this method is to allow the caller to construct
  2589.     * a WideFraction using binary data that was read from another data source.
  2590.     *
  2591.     * This method of construction will assume that the $numerator and $denominator's
  2592.     * elements are stored with native endianness (e.g. NO endianness conversions
  2593.     * will be performed inside this constructor).
  2594.     *
  2595.     * The caller should ensure that their data source's endianness agrees
  2596.     * with native endianness, or if it doesn't, perform an endiannes conversion
  2597.     * before calling this method.
  2598.     */
  2599.     public static function from_spl_array(
  2600.         // required template parameters:
  2601.         int  $numerator_bit_width,
  2602.         int  $denominator_bit_width = 0, // defaults to being the same thing as the numerator.
  2603.  
  2604.         // runtime parameter(s):
  2605.         int  elem_width_bytes,
  2606.         \SplFixedArray  $numerator,   // Array of `int`, each element shall span `elem_width_bytes` bytes (upper bits are ignored, if they exist)
  2607.         \SplFixedArray  $denominator, // Array of `int`, each element shall span `elem_width_bytes` bytes (upper bits are ignored, if they exist)
  2608.  
  2609.         // optional template parameters:
  2610.         bool $has_constant_config = false,
  2611.         int  $signedness = Signedness::SIGNED,
  2612.         int  $rounding_mode = RoundingMode::DEFAULT,
  2613.  
  2614.     )
  2615.     {
  2616.         if ( 0 === $denominator_bit_width ) {
  2617.             $denominator_bit_width = $numerator_bit_width;
  2618.         }
  2619.  
  2620.         // TODO: Check to ensure the bitwidths are consistent with the numerator/denominator arguments.
  2621.  
  2622.         $template = WideFractionTemplate::instantiate(
  2623.             __NAMESPACE__,__CLASS__,
  2624.             numerator_width:       $numerator_bit_width,
  2625.             denominator_bit_width: $denominator_bit_width,
  2626.             has_constant_config:   $has_constant_config,
  2627.             signedness:            $signedness,
  2628.             rounding_mode:         $rounding_mode
  2629.         );
  2630.  
  2631.         $template_class_path = $template->class_path();
  2632.         $result = new $template_class_path(signedness:$signedness, rounding_mode:$rounding_mode);
  2633.         // TODO: Array unpacking functions
  2634.         $result->numerator_from_spl_array(elem_width_bytes, $numerator);
  2635.         $result->denominator_from_spl_array(elem_width_bytes, $denominator);
  2636.         return $result;
  2637.     }
  2638.  
  2639.     // Below `make` functions are obsolete.
  2640.     // I am hoping to name these things much nicer things, like
  2641.     // ::from_int, ::from_string, and ::from_spl_array.
  2642.     /**
  2643.     * Convenience function for constructing WideFractions that have a constant
  2644.     * denominator.
  2645.     *
  2646.     * The given `$bit_width` will become the numerator's bit width.
  2647.     * The denominator will not occupy any bits because it is constant.
  2648.     *
  2649.     * This version also accepts a numerator as an initial value.
  2650.     *
  2651.     * This function calls `make` after calculating the appropriate parameters.
  2652.     *
  2653.     * @see make
  2654.     */
  2655.     public static function make_fixed_N(
  2656.         // Runtime parameters:
  2657.         int $bit_width, int $numerator,
  2658.  
  2659.         // Constant that will inform template params:
  2660.         int $denominator,
  2661.  
  2662.         // Template parameters:
  2663.         bool $has_constant_config = false,
  2664.         int  $signedness = Signedness::SIGNED,
  2665.         int  $rounding_mode = RoundingMode::DEFAULT,
  2666.  
  2667.     ) : WideFraction
  2668.     {
  2669.         return self::make(
  2670.             numerator:$numerator,
  2671.             numerator_bit_width:$bit_width,
  2672.             constant_denominator_int:$denominator,
  2673.             has_constant_config:$has_constant_config,
  2674.             signedness:$signedness,
  2675.             rounding_mode:$rounding_mode,
  2676.         );
  2677.     }
  2678.  
  2679.     /**
  2680.     * Convenience function for constructing WideFractions that have a constant
  2681.     * denominator.
  2682.     *
  2683.     * The given `$bit_width` will become the numerator's bit width.
  2684.     * The denominator will not occupy any bits because it is constant.
  2685.     *
  2686.     * This version of `make_fixed_*` will yield a WideFraction with
  2687.     * a numerator equal to 0.
  2688.     *
  2689.     * This function calls `make` after calculating the appropriate parameters.
  2690.     *
  2691.     * @see make
  2692.     */
  2693.     public static function make_fixed_0(
  2694.         // Runtime parameter:
  2695.         int $bit_width,
  2696.  
  2697.         // Constant that will inform template params:
  2698.         int $denominator,
  2699.  
  2700.         // Template parameters:
  2701.         bool $has_constant_config = false,
  2702.         int  $signedness = Signedness::SIGNED,
  2703.         int  $rounding_mode = RoundingMode::DEFAULT,
  2704.  
  2705.     ) : WideFraction
  2706.     {
  2707.         return self::make(
  2708.             numerator:0,
  2709.             numerator_bit_width:$bit_width,
  2710.             constant_denominator_int:$denominator,
  2711.             has_constant_config:$has_constant_config,
  2712.             signedness:$signedness,
  2713.             rounding_mode:$rounding_mode,
  2714.         );
  2715.     }
  2716.  
  2717.     // ---=== Configuration properties ===---
  2718.  
  2719.     /**
  2720.     * Constant property that returns whether the WideFraction's template instance
  2721.     * was instantiated with a constant denominator.
  2722.     *
  2723.     * If true, then attempting to alter the WideFraction's denominator will
  2724.     * result in a thrown exception.
  2725.     */
  2726.     public abstract function has_constant_denominator() : bool;
  2727.  
  2728.     /**
  2729.     * Constant property that returns whether the WideFraction's template instance
  2730.     * was instantiated with all configuration parameters being constants.
  2731.     *
  2732.     * If true, then properties like `signedness()` and `rounding_mode()` will
  2733.     * be considered constant, and attempt to set them will throw an exception.
  2734.     */
  2735.     public abstract function has_constant_config() : bool;
  2736.  
  2737.     /**
  2738.     * Returns the number of bits used to represent the numerator in this
  2739.     * WideFraction.
  2740.     *
  2741.     * This total will include the sign bit for fractions that are defined as signed.
  2742.     *
  2743.     * This is value is set at the time of template instantiation and may
  2744.     * not be changed (e.g. it is always constant).
  2745.     */
  2746.     public abstract function numerator_bit_width() : int;
  2747.  
  2748.     /**
  2749.     * Returns the number of bits used to represent the denominator in this
  2750.     * WideFraction.
  2751.     *
  2752.     * In the case of a constant denominator, the returned value will be
  2753.     * the minimum number of bits required to store the denominator.
  2754.     *
  2755.     * This is value is set at the time of template instantiation and may
  2756.     * not be changed (e.g. it is always constant).
  2757.     */
  2758.     public abstract function denominator_bit_width() : int;
  2759.  
  2760.     // (Implementations of config properties will vary depending on template parameters.)
  2761.  
  2762.     /**
  2763.     * Property for getting or setting the signedness of the WideFraction.
  2764.     *
  2765.     * The possible values for this property are enumerated
  2766.     * in the `Signedness` constant class.
  2767.     *
  2768.     * If the WideFraction's template instance uses constant configuration,
  2769.     * then attempting to set this will result in a thrown exception.
  2770.     *
  2771.     * This is always safe to call as a getter, to retrieve the WideFraction's
  2772.     * currently defined signedness.
  2773.     *
  2774.     * @See Signedness
  2775.     */
  2776.     public abstract function signedness(int? $new_signedness = null) : int;
  2777.  
  2778.     /**
  2779.     * Property for getting or setting the default rounding mode of the WideFraction.
  2780.     *
  2781.     * The possible values for this property are enumerated
  2782.     * in the `RoundingMode` constant class.
  2783.     *
  2784.     * If this is anything besides RoundingMode::DEFAULT, then passing
  2785.     * eliding the rounding mode argument from methods that take, or
  2786.     * passing RoundingMode::DEFAULT to said methods, will result in
  2787.     * the RoundingMode from this property being used instead.
  2788.     *
  2789.     * Passing a RoundingMode argument to individual methods/operations
  2790.     * will always override this.
  2791.     *
  2792.     * Graphically, the precedence for rounding modes goes like this:
  2793.     * ```
  2794.     * template parameter < class property < parameter default < explicit argument at method call
  2795.     * ```
  2796.     *
  2797.     * If the WideFraction's template instance uses constant configuration,
  2798.     * then attempting to set this will result in a thrown exception.
  2799.     *
  2800.     * This is always safe to call as a getter, to retrieve the WideFraction's
  2801.     * currently defined RoundingMode.
  2802.     */
  2803.     public abstract function rounding_mode(int? $new_rounding_mode = null) : int;
  2804.  
  2805.     // ---=== Internal Accessors ===---
  2806.  
  2807.     /**
  2808.     * Returns the number of PHP `int` members that are used to represent
  2809.     * this WideFraction's numerator.
  2810.     *
  2811.     * If the WideFraction is signed, then the most significant integer will be
  2812.     * the one that stores signing information. All of the others will be
  2813.     * treated internally as if they are unsigned.
  2814.     *
  2815.     * While this property is foundational for implementing arithmetic
  2816.     * operations, it is also very problematic to use in any code
  2817.     * that isn't explicitly aware of this particular template's
  2818.     * internal representation. As such, it is marked as `protected`,
  2819.     * so that various template instances may transit this information
  2820.     * between themselves, but it is guaranteed that this implementation
  2821.     * detail is not used anywhere else.
  2822.     */
  2823.     protected abstract function numerator_phpint_width() : int;
  2824.  
  2825.     /**
  2826.     * Returns the number of PHP `int` members that are used to represent
  2827.     * this WideFraction's denominator.
  2828.     *
  2829.     * In the case of a constant denominator, the returned value will be
  2830.     * the minimum number of PHP `int` variables required to store the denominator.
  2831.     * (This is actually an important choice, because it allows the template
  2832.     * to generate code that enumerates the WideFraction's denominator
  2833.     * dynamically whenever there is a width mismatch during arithmetic operations.)
  2834.     *
  2835.     * While this property is foundational for implementing arithmetic
  2836.     * operations, it is also very problematic to use in any code
  2837.     * that isn't explicitly aware of this particular template's
  2838.     * internal representation. As such, it is marked as `protected`,
  2839.     * so that various template instances may transit this information
  2840.     * between themselves, but it is guaranteed that this implementation
  2841.     * detail is not used anywhere else.
  2842.     */
  2843.     protected abstract function denominator_phpint_width() : int;
  2844.  
  2845.     /**
  2846.     * Returns and/or sets this WideFraction's `int` at the given index.
  2847.     *
  2848.     * The least significant `int` has index 0.
  2849.     * The most significant `int` has an index that is one less than `(numerator|denominator)_phpint_width()`.
  2850.     *
  2851.     * Attempting to get or set an `int` that is out of bounds (less than 0
  2852.     * or greater than or equal to `*_phpint_width()`) will result
  2853.     * in undefined behavior. (It is possible that no attempt will be made
  2854.     * to check for this condition, if it is efficient to do it that way.)
  2855.     */
  2856.     protected abstract function get_numerator_phpint_at(int $index) : int;
  2857.     protected abstract function set_numerator_phpint_at(int $index, int $value) : int; /** ditto */
  2858.     protected abstract function get_denominator_phpint_at(int $index) : int; /** ditto */
  2859.     protected abstract function set_denominator_phpint_at(int $index, int $value) : int; /** ditto */
  2860.  
  2861.     // ---=== Comparison operations ===---
  2862.  
  2863.     // TODO: Should there be convenience functions for operations between
  2864.     // WideFractions and floating point numbers?
  2865.     //
  2866.     // It would certainly make the WideFraction type more versatile,
  2867.     // but I fear that this will lead to computational inaccuracies as
  2868.     // it encourages the use of float literals, which tend to be decimal
  2869.     // formatted despite the type being unable to represent most decimal
  2870.     // fractions (ugh why).
  2871.     //
  2872.     // Perhaps a better approach would be to allow string literals on
  2873.     // one side of the operation. This would then be convenience syntax
  2874.     // for constructing a WideFraction with the same template instance
  2875.     // and other attributes as one of the WideFractions involved
  2876.     // (probably just use the $this fraction to have a simple rule?)
  2877.     // but with a numerator as given by the string.
  2878.     // The denominator would be some power of 10, and would, by default,
  2879.     // be inherited from the ($this) fraction, as speculated above.
  2880.     // However, if the precision in the string literal is lower, then
  2881.     // the integer will be assumed to have the lower precision.
  2882.     // (That probably usually won't help anything, but for narrowing
  2883.     // operations it will allow the string literal to have a higher
  2884.     // whole number magnitude whenever the possibility is avialable.)
  2885.  
  2886.     /**
  2887.     *  `cmp` returns -1, 0, or 1 based on a comparing this WideFraction
  2888.     *  against another number whose parameter is named "$other".
  2889.     *
  2890.     *  `cmp` is defined such that, in shorthand notation, these are true:
  2891.     *  * a < b implies cmp(a,b) < 0
  2892.     *  * a > b implies cmp(a,b) > 0
  2893.     *  * a == b implies cmp(a,b) == 0.
  2894.     *  In the case of the below comparison methods, the `a` is this WideFraction
  2895.     *  object and `b` is the `$other` parameter.
  2896.     *
  2897.     *  Usage of `cmp` looks like this:
  2898.     *  ```PHP
  2899.     *  $foo = WideFraction::make_fixed_s(32, "4.45");
  2900.     *  $bar = 4;
  2901.     *  $qux = 5;
  2902.     *  Testing::_assert($foo->cmp_int($bar) > 0); // 4.45 > 4
  2903.     *  Testing::_assert($foo->cmp_int($qux) < 0); // 4.45 < 5
  2904.     *
  2905.     *  $foo = WideFraction::make_fixed_s(32, "4.45");
  2906.     *  $bar = "4.0";
  2907.     *  $baz = "4.5";
  2908.     *  $qux = "5.0";
  2909.     *
  2910.     *  Testing::_assert($foo->cmp_str($bar) > 0); // 4.45 > 4.0
  2911.     *  Testing::_assert($foo->cmp_str($baz) > 0); // 4.45 < 4.5
  2912.     *  Testing::_assert($foo->cmp_str($qux) < 0); // 4.45 < 5.0
  2913.     *
  2914.     *  $foo = WideFraction::make_fixed_s(32, "4.45");
  2915.     *  $bar = WideFraction::make_fixed_s(32, "4.0");
  2916.     *  $baz = WideFraction::make_fixed_s(32, "4.5");
  2917.     *  $qux = WideFraction::make_fixed_s(32, "5.0");
  2918.     *
  2919.     *  Testing::_assert($foo->cmp($bar) > 0); // 4.45 > 4.0
  2920.     *  Testing::_assert($foo->cmp($baz) > 0); // 4.45 < 4.5
  2921.     *  Testing::_assert($foo->cmp($qux) < 0); // 4.45 < 5.0
  2922.     *  ```
  2923.     *
  2924.     *  The `cmp` method has variations that accept different right-hand-side (RHS)
  2925.     *  and variations that assert or inform signdedness. These variations are
  2926.     *  notated with letters in the prefixes of the method names.
  2927.     *
  2928.     *  The notation for prefixes is as follows:
  2929.     *  * 'i': The operation accepts an integer (`int` type) argument.
  2930.     *  * 'w': The operation accepts a (W)ideFraction argument.
  2931.     *  * 'l': The operation accepts a string (L)iteral argument. ('l' is used instead of 's' to avoid ambiguity with the signed prefix.)
  2932.     *  * 'u': The operation is unsigned. Values (of the numerator) between `0x8000...0000` and `0xFFFF...FFFF` are assumed to be positive.
  2933.     *  * 's': The operation is signed. Values (of the numerator) between `0x8000...0000` and `0xFFFF...FFFF` are assumed to be negative.
  2934.     *
  2935.     *  The other comparison operations are `eq`, `ne`, `lt`, `gt`, `lte`, and `gte`,
  2936.     *  which respectively stand for "EQuals", "Not Equals", "Less Than",
  2937.     *  "Greater Than", "Less Than or Equal to", and "Greater Than or Equal to".
  2938.     *
  2939.     *  These comparisons simply work as one might expect and directly
  2940.     *  return a boolean value, so they are more convenient than calling
  2941.     *  `cmp` in most cases (at the expense of making it more difficult to
  2942.     *  forward all comparison information into other operations).
  2943.     *
  2944.     *  As with `cmp`, there are variations that take different right-hand-side (RHS)
  2945.     *  operand types and variations that assert or inform signdedness.
  2946.     *
  2947.     *  The non-prefixed versions of these methods are defined as the "default"
  2948.     *  methods for comparison, in the sense that they will choose a reasonable
  2949.     *  default when they are called. Specifically, they use some logic to choose
  2950.     *  an appropriate underlying prefixed version to use, based on the
  2951.     *  signedness setting of the operands.
  2952.     *
  2953.     *  The logic used to determine which comparison is used, goes as follows:
  2954.     *  These methods will perform a signed comparison if both operands are signed.
  2955.     *  And each will perform an unsigned comparison if both operands are unsigned.
  2956.     *  If operands do not match in signedness (type-wise), then their sign bits
  2957.     *  are examined:
  2958.     *  If both are equal, then a comparison is performed (sign doesn't matter).
  2959.     *  If one sign bit is set and another not, then a WideOverflowException is thrown.
  2960.     *  If both operands are ambiguously signed WideFractions, then these will act
  2961.     *  as signed comparisons.
  2962.     *  If one operand is ambiguously signed, the comparison done will have
  2963.     *  the signedness of the non-ambiguous type.
  2964.     */
  2965.     public abstract function cmp(WideFraction $other) : int;
  2966.     public abstract function eq(WideFraction $other) : bool; /** @see cmp */
  2967.     public abstract function ne(WideFraction $other) : bool; /** @see cmp */
  2968.     public abstract function lt(WideFraction $other) : bool; /** @see cmp */
  2969.     public abstract function gt(WideFraction $other) : bool; /** @see cmp */
  2970.     public abstract function lte(WideFraction $other) : bool; /** @see cmp */
  2971.     public abstract function gte(WideFraction $other) : bool; /** @see cmp */
  2972.  
  2973.     /**
  2974.     * These comparisons are default comparisons that allow convenient comparing
  2975.     * of the WideFraction type against the builtin `int` type.
  2976.     *
  2977.     * In these comparisons, the `int` operand is treated as being ambiguously signed.
  2978.     * This means that the comparison will have the signedness of the left operand
  2979.     * (the WideFraction or $this/self object).
  2980.     * If the left operand is sign-ambiguous, then the comparison will
  2981.     * be performed as if both operands were signed.
  2982.     *
  2983.     * @see cmp
  2984.     */
  2985.     public abstract function cmp_int(int $other) : int;
  2986.     public abstract function eq_int(int $other) :  bool; /** @see cmp_int */
  2987.     public abstract function ne_int(int $other) :  bool; /** @see cmp_int */
  2988.     public abstract function lt_int(int $other) :  bool; /** @see cmp_int */
  2989.     public abstract function gt_int(int $other) :  bool; /** @see cmp_int */
  2990.     public abstract function lte_int(int $other) : bool; /** @see cmp_int */
  2991.     public abstract function gte_int(int $other) : bool; /** @see cmp_int */
  2992.  
  2993.     /**
  2994.     * These comparisons do a default comparison of this WideFraction object
  2995.     * against string literals that are parsed as being a WideFraction of the
  2996.     * same type as the left operand (the WideFraction or $this/self object).
  2997.     *
  2998.     * The `l` prefix is used instead of `s` to prevent confusion with
  2999.     * signed versions of the comparison operators. It stands for (L)iteral,
  3000.     * as in "string Literal".
  3001.     *
  3002.     * In these comparisons:
  3003.     * The string operand will be treated as ambiguously-signed if there is no
  3004.     * sign present in the string and the string is a decimal string (not hex, octal, or binary).
  3005.     * The string operand will be treated as signed if the string leads with
  3006.     * a sign (either the '-' or the '+' character). (Signs on exponents do not count.)
  3007.     * The string operand will be treated as unsigned if the string is given
  3008.     * as any non-decimal literal (such as hexadecimals starting with '0x',
  3009.     * octals starting with '0o', or binary literals starting with '0b')
  3010.     * and does not have a leading sign character.
  3011.     *
  3012.     * The comparison then proceeds as it would for the default WideFraction
  3013.     * to WideFraction comparisons.
  3014.     *
  3015.     * This means that the comparison will have the signedness of the left operand
  3016.     * (the WideFraction, $this/self).
  3017.     * If the left operand is sign-ambiguous, then the comparison will
  3018.     * be performed as if both operands were signed.
  3019.     *
  3020.     * @see cmp
  3021.     */
  3022.     public abstract function cmp_str(string $other) : int;
  3023.     public abstract function eq_str(string $other) : bool;  /** @see cmp_str */
  3024.     public abstract function ne_str(string $other) : bool;  /** @see cmp_str */
  3025.     public abstract function lt_str(string $other) : bool;  /** @see cmp_str */
  3026.     public abstract function gt_str(string $other) : bool;  /** @see cmp_str */
  3027.     public abstract function lte_str(string $other) : bool; /** @see cmp_str */
  3028.     public abstract function gte_str(string $other) : bool; /** @see cmp_str */
  3029.  
  3030.     // TODO: versions with string-typed $other.
  3031.  
  3032.     /** (U)nsigned WideFraction comparisons */
  3033.     public abstract function ucmp(WideFraction &$other) : int;
  3034.     public abstract function ueq(WideFraction &$other) : bool;  /** @see ucmp */
  3035.     public abstract function une(WideFraction &$other) : bool;  /** @see ucmp */
  3036.     public abstract function ult(WideFraction &$other) : bool;  /** @see ucmp */
  3037.     public abstract function ugt(WideFraction &$other) : bool;  /** @see ucmp */
  3038.     public abstract function ulte(WideFraction &$other) : bool; /** @see ucmp */
  3039.     public abstract function ugte(WideFraction &$other) : bool; /** @see ucmp */
  3040.  
  3041.     /** (U)nsigned integer comparisons */
  3042.     public abstract function ucmp_int(int $other) : int;
  3043.     public abstract function ueq_int(int $other) : bool;  /** @see ucmp_int */
  3044.     public abstract function une_int(int $other) : bool;  /** @see ucmp_int */
  3045.     public abstract function ult_int(int $other) : bool;  /** @see ucmp_int */
  3046.     public abstract function ugt_int(int $other) : bool;  /** @see ucmp_int */
  3047.     public abstract function ulte_int(int $other) : bool; /** @see ucmp_int */
  3048.     public abstract function ugte_int(int $other) : bool; /** @see ucmp_int */
  3049.  
  3050.     /** (U)nsigned string comparisons */
  3051.     public abstract function ucmp_str(string $other) : int;
  3052.     public abstract function ueq_str(string $other) : bool;  /** @see ucmp_str */
  3053.     public abstract function une_str(string $other) : bool;  /** @see ucmp_str */
  3054.     public abstract function ult_str(string $other) : bool;  /** @see ucmp_str */
  3055.     public abstract function ugt_str(string $other) : bool;  /** @see ucmp_str */
  3056.     public abstract function ulte_str(string $other) : bool; /** @see ucmp_str */
  3057.     public abstract function ugte_str(string $other) : bool; /** @see ucmp_str */
  3058.  
  3059.     /** (S)igned WideFraction comparisons */
  3060.     public abstract function scmp(WideFraction &$other) : int;
  3061.     public abstract function seq(WideFraction &$other) : bool;  /** @see scmp */
  3062.     public abstract function sne(WideFraction &$other) : bool;  /** @see scmp */
  3063.     public abstract function slt(WideFraction &$other) : bool;  /** @see scmp */
  3064.     public abstract function sgt(WideFraction &$other) : bool;  /** @see scmp */
  3065.     public abstract function slte(WideFraction &$other) : bool; /** @see scmp */
  3066.     public abstract function sgte(WideFraction &$other) : bool; /** @see scmp */
  3067.  
  3068.     /** (S)igned integer comparisons */
  3069.     public abstract function scmp_int(int $other) : int;
  3070.     public abstract function seq_int(int $other) : bool;  /** @see scmp_int */
  3071.     public abstract function sne_int(int $other) : bool;  /** @see scmp_int */
  3072.     public abstract function slt_int(int $other) : bool;  /** @see scmp_int */
  3073.     public abstract function sgt_int(int $other) : bool;  /** @see scmp_int */
  3074.     public abstract function slte_int(int $other) : bool; /** @see scmp_int */
  3075.     public abstract function sgte_int(int $other) : bool; /** @see scmp_int */
  3076.  
  3077.     /** (S)igned string comparisons */
  3078.     public abstract function scmp_str(string $other) : int;
  3079.     public abstract function seq_str(string $other) : bool;  /** @see scmp_str */
  3080.     public abstract function sne_str(string $other) : bool;  /** @see scmp_str */
  3081.     public abstract function slt_str(string $other) : bool;  /** @see scmp_str */
  3082.     public abstract function sgt_str(string $other) : bool;  /** @see scmp_str */
  3083.     public abstract function slte_str(string $other) : bool; /** @see scmp_str */
  3084.     public abstract function sgte_str(string $other) : bool; /** @see scmp_str */
  3085.  
  3086.     // ---=== Arithmetic operations ===---
  3087.  
  3088.     public abstract function add(WideFraction &$a, WideFraction &$b, WideFraction? &$c = null, WideFraction? &$d = null) : self;
  3089.     public abstract function add_ww(WideFraction &$a, WideFraction &$b, WideFraction? &$c = null, WideFraction? &$d = null) : self;
  3090.     public abstract function add_wi(WideFraction &$a, int $b) : self;
  3091.     public abstract function add_iw(int $a, WideFraction &$b) : self;
  3092.     public abstract function add_ii(int $a, int $b) : self;
  3093.     public abstract function increment_by(WideFraction &$b) : void;
  3094.     public abstract function increment() : void;
  3095.     public abstract function incr_by(int $b) : void;
  3096.     public abstract function incr() : void; // Should do same thing as `increment()`.
  3097.     public abstract function subtract(WideFraction &$a, WideFraction &$b) : self;
  3098.     public abstract function decrement_by(WideFraction &$b) : void;
  3099.     public abstract function decrement() : void;
  3100.     public abstract function decr_by(int $b) : void;
  3101.     public abstract function decr() : void;
  3102.     public abstract function negate() : void;
  3103.     public abstract function multiply(WideFraction &$a, WideFraction &$b, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3104.     public abstract function mult(WideFraction &$a, int $b, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3105.     public abstract function multiply_by(WideFraction &$b, int $rounding_mode = RoundingMode::DEFAULT) : void;
  3106.     public abstract function mult_by(int $b, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3107.     public abstract function divide(WideFraction &$numerator, WideFraction &$denominator, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3108.     public abstract function div(WideFraction &$numerator, int $denominator, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3109.     public abstract function divide_by(WideFraction &$denominator, int $rounding_mode = RoundingMode::DEFAULT) : void;
  3110.     public abstract function div_by(int $denominator, int $rounding_mode = RoundingMode::DEFAULT) : void;
  3111.     public abstract function modulus(WideFraction &$numerator, WideFraction &$denominator, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3112.     public abstract function mod(WideFraction &$numerator, int $denominator, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3113.     public abstract function modulus_by(WideFraction &$denominator, int $rounding_mode = RoundingMode::DEFAULT) : void;
  3114.     public abstract function mod_by(int $denominator, int $rounding_mode = RoundingMode::DEFAULT) : void;
  3115.     public abstract function divide_and_modulus(WideFraction &$numerator, WideFraction &$denominator, WideFraction &$out_remainder, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3116.     public abstract function div_n_mod(WideFraction &$numerator, int $denominator, int &$out_remainder, int $rounding_mode = RoundingMode::DEFAULT) : self;
  3117.     public abstract function divide_and_modulus_by(WideFraction &$denominator, WideFraction &$out_remainder, int $rounding_mode = RoundingMode::DEFAULT) : void;
  3118.     public abstract function div_n_mod_by(int $denominator, int &$out_remainder, int $rounding_mode = RoundingMode::DEFAULT) : void;
  3119.     public abstract function inverse_of(WideFraction &$a) : self;
  3120.     public abstract function invert() : self;
  3121.  
  3122.     // ---=== Logical operations ===---
  3123.     /**
  3124.     * Extracts the sign bit of the numerator.
  3125.     *
  3126.     * Note that WideFraction is defined in such a way that the denominator
  3127.     * is never negative. The entire fraction is what has a sign, and the
  3128.     * sign is stored in the numerator.
  3129.     */
  3130.     public abstract function sign() : int
  3131.  
  3132.     // TODO: This documentation really belongs on the `divide` method.
  3133.     // It was written for an earlier version of the method too, so it
  3134.     // probably needs editing and correction to make it accurate to the
  3135.     // current divide method.
  3136.     /*
  3137.     * Performs a fixed-point division to evaluate `$numerator / $denominator`.
  3138.     *
  3139.     * The sense of "fixed-point" means that the intended use-case for this
  3140.     * method is for when its operands are being used like "fixed-point"
  3141.     * numbers, albeit in an arbitrary base decided by the caller.
  3142.     *
  3143.     * Examples of fixed-point behavior:
  3144.     *
  3145.     * $n = WideFraction::make_fixed_0i(64, 100); // 64-bit wide number with 2 decimal digits of precision.
  3146.     * $d = WideFraction::make_fixed_0i(64, 100); // ditto
  3147.     * $q = WideFraction::make_fixed_0i(64, 100); // ditto
  3148.     * $t = WideFraction::make_fixed_0i(64, 100); // ditto
  3149.     *
  3150.     * $q->divide($n->from_decimal("560.56"), $d->from_decimal("12.32"), $q);
  3151.     * Testing::_assert(WideFraction::equals($q, $t->from_decimal("45.50"));
  3152.     *
  3153.     * $q->divide($n->from_decimal("1.01"), $d->from_decimal("1.01"), $q);
  3154.     * Testing::_assert(WideFraction::equals($q, $t->from_decimal("1.02")); // Truncated from 1.0201
  3155.     *
  3156.     * $q->divide($n->from_decimal("1.09"), $d->from_decimal("1.09"), $q);
  3157.     * Testing::_assert(WideFraction::equals($q, $t->from_decimal("1.18")); // Truncated from 1.1881
  3158.     *
  3159.     * $q->divide($n->from_decimal("1.09"), $d->from_decimal("1.09"), RoundingMode::BANKERS);
  3160.     * Testing::_assert(WideFraction::equals($q, $t->from_decimal("1.19")); // Rounded from 1.1881
  3161.     *
  3162.     * It works for other bases too:
  3163.     *
  3164.     * $n = WideFraction::make_fixed_0i(64, 0x100 ); // 0x100 == 256: 64-bit wide number with 2 HEXadecimal digits of precision.
  3165.     * $d = WideFraction::make_fixed_0i(64, 0x100 ); // 0x100 == 256, ditto
  3166.     * $q = WideFraction::make_fixed_0i(64, 0x100 ); // 0x100 == 256, ditto
  3167.     * $t = WideFraction::make_fixed_0i(64, 0x100 ); // 0x100 == 256, ditto
  3168.     *
  3169.     * $q->divide($n->from_hexadecimal("DC40A.17"), $d->from_hexadecimal("348.C7"));
  3170.     * Testing::_assert(WideFraction::equals($q, $t->from_hexadecimal("4.31"));
  3171.     *
  3172.     * $q->divide($n->from_decimal("1.01"), $d->from_decimal("1.01"));
  3173.     * Testing::_assert(WideFraction::equals($q, $t->from_decimal("1.02")); // Truncated from 1.0201
  3174.     *
  3175.     * $q->divide($n->from_decimal("1.0F"), $d->from_decimal("1.0F"));
  3176.     * Testing::_assert(WideFraction::equals($q, $t->from_decimal("1.1E")); // Truncated from 1.1EE1
  3177.     *
  3178.     * $q->divide($n->from_decimal("1.0F"), $d->from_decimal("1.0F"), RoundingMode::BANKERS);
  3179.     * Testing::_assert(WideFraction::equals($q, $t->from_decimal("1.1F")); // Rounded from 1.1EE1
  3180.     */
  3181. }
  3182.  
  3183. ?>
  3184.  
  3185. <?php
  3186. /*
  3187. declare(strict_types=1);
  3188.  
  3189. namespace Kickback\Common\Math\Types;
  3190.  
  3191. use \Kickback\Common\Math\Types\WideFraction;
  3192. use \Kickback\Common\Math\RoundingMode;
  3193. */
  3194. // TODO: Would this even be abstract?
  3195. // I mean, the WideFraction template might end up with things like
  3196. // compile-time signedness or default rounding mode, so it would make sense
  3197. // to templatize this class with those parameters as well (just not denominator).
  3198. // But if we needed a WideInteger type in a hurry, we could chose some
  3199. // mandatory parameters initially, and then implement the template later.
  3200. abstract class WideInteger extends WideFraction
  3201. {
  3202.     // TODO:
  3203.     // * Restrict inherited constructors to only ones that don't accept fractional elements.
  3204.     // * Somehow ensure that all other default construction will not have a denominator?
  3205.     // * Will there even be any integer-specific operations?
  3206.     // * Implement WideInteger template that overrides some WideFraction
  3207.     //     methods whenever they can be optimized for the denominator-of-1 case.
  3208.     // * This class would presumably be for allowing functions to declare
  3209.     //     WideInteger parameters (thus rejecting anything with fractional quantities).
  3210.     //     This would allow the caller to declare enforcable intent in their
  3211.     //     own functions and methods.
  3212.     // * The other use for this class, secondary to the above, is for
  3213.     //     opportunistic optimization of the D=1 case.
  3214.     //     This is, to say the least, pretty low priority (at the moment).
  3215.     // * [There was something that was going to be put here, but brain did not complete the operation. Darn.]
  3216. }
  3217. ?>
  3218.  
  3219. <?php
  3220. //declare(strict_types=1);
  3221.  
  3222. // Unittest driver to be run from command-line interface.
  3223. /*
  3224. use \Kickback\Common\Math\LowLevel\WideInt; // TODO: Make this template exist.
  3225. use \Kickback\Common\Math\Types\WideFraction;
  3226. */
  3227.  
  3228. function unittest_all() : void
  3229. {
  3230.     WideInt::unittest();
  3231.     WideFraction::unittest();
  3232. }
  3233.  
  3234. unittest_all();
  3235. ?>
  3236.  
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!