API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 11th, 2015
252
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 35.74 KB | None | 0 0
raw download clone embed print report
  1. <?php
  2. /**
  3. *
  4. * @ This file is created by deZender.Net
  5. * @ deZender (PHP5 Decoder for ionCube Loader)
  6. *
  7. * @ Version : 2.0.0.3
  8. * @ Author : DeZender
  9. * @ Release on : 06.05.2013
  10. * @ Official site : http://DeZender.Net
  11. *
  12. */
  13.  
  14. function strlen_safe($str) {
  15. return function_exists("mb_strlen") ? mb_strlen($str, "8bit") : strlen($str);
  16. }
  17.  
  18. function strpos_safe($str, $needle, $offset = 0) {
  19. return function_exists("mb_strpos") ? mb_strpos($str, $needle, $offset, "8bit") : strpos($str, $needle, $offset);
  20. }
  21.  
  22. function strrpos_safe($str, $needle, $offset = 0) {
  23. return function_exists("mb_strrpos") ? mb_strrpos($str, $needle, $offset, "8bit") : strrpos($str, $needle, $offset);
  24. }
  25.  
  26. function substr_safe($str, $start, $length = 10000) {
  27. return function_exists("mb_substr") ? mb_substr($str, $start, $length, "8bit") : substr($str, $start, $length);
  28. }
  29.  
  30. /**
  31. * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
  32. * numbers.
  33. *
  34. * @package Math_BigInteger
  35. * @author Jim Wigginton <terrafrost@php.net>
  36. * @access public
  37. */
  38. class Math_BigInteger {
  39.  
  40. /**
  41. * Holds the BigInteger's value.
  42. *
  43. * @var Array
  44. * @access private
  45. */
  46. public $value = null;
  47.  
  48. /**
  49. * Holds the BigInteger's magnitude.
  50. *
  51. * @var Boolean
  52. * @access private
  53. */
  54. public $is_negative = false;
  55.  
  56. /**
  57. * Random number generator function
  58. *
  59. * @see setRandomGenerator()
  60. * @access private
  61. */
  62. public $generator = "mt_rand";
  63.  
  64. /**
  65. * Precision
  66. *
  67. * @see setPrecision()
  68. * @access private
  69. */
  70. public $precision = -1;
  71.  
  72. /**
  73. * Precision Bitmask
  74. *
  75. * @see setPrecision()
  76. * @access private
  77. */
  78. public $bitmask = false;
  79.  
  80. /**
  81. * Mode independent value used for serialization.
  82. *
  83. * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
  84. * a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value,
  85. * however, $this->hex is only calculated when $this->__sleep() is called.
  86. *
  87. * @see __sleep()
  88. * @see __wakeup()
  89. * @var String
  90. * @access private
  91. */
  92. public $hex = null;
  93.  
  94.  
  95. /**
  96. * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
  97. *
  98. * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
  99. * two's compliment. The sole exception to this is -10, which is treated the same as 10 is.
  100. *
  101. * Here's an example:
  102. * <code>
  103. * <?php
  104. * include 'Math/BigInteger.php';
  105. *
  106. * $a = new Math_BigInteger('0x32', 16); // 50 in base-16
  107. *
  108. * echo $a->toString(); // outputs 50
  109. * ?>
  110. * </code>
  111. *
  112. * @param optional $x base-10 number or base-$base number if $base set.
  113. * @param optional integer $base
  114. * @return Math_BigInteger
  115. * @access public
  116. */
  117. public function Math_BigInteger($x = 0, $base = 10) {
  118. if (!(defined("MATH_BIGINTEGER_MODE"))) {
  119. switch (true) {
  120. case extension_loaded("gmp"):
  121. define("MATH_BIGINTEGER_MODE", MATH_BIGINTEGER_MODE_GMP);
  122. break;
  123.  
  124. case extension_loaded("bcmath"):
  125. define("MATH_BIGINTEGER_MODE", MATH_BIGINTEGER_MODE_BCMATH);
  126. break;
  127.  
  128. default:
  129. define("MATH_BIGINTEGER_MODE", MATH_BIGINTEGER_MODE_INTERNAL);
  130.  
  131. }
  132. }
  133. if (function_exists("openssl_public_encrypt") && !(defined("MATH_BIGINTEGER_OPENSSL_DISABLE")) && !(defined("MATH_BIGINTEGER_OPENSSL_ENABLED"))) {
  134. ob_start();
  135. @phpinfo();
  136. $content = ob_get_contents();
  137. ob_end_clean();
  138. preg_match_all("#OpenSSL (Header|Library) Version(.*)#im", $content, $matches);
  139. $versions = array();
  140. if (!(empty($matches[1]))) {
  141. $i = 0;
  142. while ($i < count($matches[1])) {
  143. $versions[$matches[1][$i]] = trim(str_replace("=>", "", strip_tags($matches[2][$i])));
  144. ++$i;
  145. }
  146. }
  147. switch (true) {
  148. case !(isset($versions["Header"])):
  149. case !(isset($versions["Library"])):
  150. case $versions["Header"] == $versions["Library"]:
  151. define("MATH_BIGINTEGER_OPENSSL_ENABLED", true);
  152. break;
  153.  
  154. default:
  155. define("MATH_BIGINTEGER_OPENSSL_DISABLE", true);
  156.  
  157. }
  158. }
  159. if (!(defined("PHP_INT_SIZE"))) {
  160. define("PHP_INT_SIZE", 4);
  161. }
  162. if (!(defined("MATH_BIGINTEGER_BASE")) && MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL) {
  163. switch (PHP_INT_SIZE) {
  164. case 8:
  165. define("MATH_BIGINTEGER_BASE", 31);
  166. define("MATH_BIGINTEGER_BASE_FULL", 2147483648.000000);
  167. define("MATH_BIGINTEGER_MAX_DIGIT", 2147483647);
  168. define("MATH_BIGINTEGER_MSB", 1073741824);
  169. define("MATH_BIGINTEGER_MAX10", 1000000000);
  170. define("MATH_BIGINTEGER_MAX10_LEN", 9);
  171. define("MATH_BIGINTEGER_MAX_DIGIT2", pow(2, 62));
  172. break;
  173.  
  174. default:
  175. define("MATH_BIGINTEGER_BASE", 26);
  176. define("MATH_BIGINTEGER_BASE_FULL", 67108864);
  177. define("MATH_BIGINTEGER_MAX_DIGIT", 67108863);
  178. define("MATH_BIGINTEGER_MSB", 33554432);
  179. define("MATH_BIGINTEGER_MAX10", 10000000);
  180. define("MATH_BIGINTEGER_MAX10_LEN", 7);
  181. define("MATH_BIGINTEGER_MAX_DIGIT2", pow(2, 52));
  182.  
  183. }
  184. }
  185. switch (MATH_BIGINTEGER_MODE) {
  186. case MATH_BIGINTEGER_MODE_GMP:
  187. if (is_resource($x) && get_resource_type($x) == "GMP integer") {
  188. $this->value = $x;
  189. return null;
  190. }
  191. $this->value = gmp_init(0);
  192. break;
  193.  
  194. case MATH_BIGINTEGER_MODE_BCMATH:
  195. $this->value = "0";
  196. break;
  197.  
  198. default:
  199. $this->value = array();
  200.  
  201. }
  202. if (empty($x) && abs($base) != 256 || $x !== "0") {
  203. return null;
  204. }
  205. switch ($base) {
  206. case -256:
  207. if (ord($x[0]) & 128) {
  208. $x = ~$x;
  209. $this->is_negative = true;
  210. }
  211.  
  212. case 256:
  213. switch (MATH_BIGINTEGER_MODE) {
  214. case MATH_BIGINTEGER_MODE_GMP:
  215. $sign = $this->is_negative ? "-" : "";
  216. $this->value = gmp_init($sign . "0x" . bin2hex($x));
  217. break;
  218.  
  219. case MATH_BIGINTEGER_MODE_BCMATH:
  220. $len = strlen_safe($x) + 3 & 4294967292.000000;
  221. $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
  222. $i = 0;
  223. while ($i < $len) {
  224. $this->value = bcmul($this->value, "4294967296", 0);
  225. $this->value = bcadd($this->value, 16777216 * ord($x[$i]) + (ord($x[$i + 1]) << 16 | ord($x[$i + 2]) << 8 | ord($x[$i + 3])), 0);
  226. $i += 4;
  227. }
  228. if ($this->is_negative) {
  229. $this->value = "-" . $this->value;
  230. }
  231. break;
  232.  
  233. label_0:
  234. default:
  235. if (strlen_safe($x)) {
  236. $this->value[] = $this->_bytes2int($this->_base256_rshift($x, MATH_BIGINTEGER_BASE));
  237. goto label_0;
  238. }
  239.  
  240. }
  241. if ($this->is_negative) {
  242. if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
  243. $this->is_negative = false;
  244. }
  245. $temp = $this->add(new Math_BigInteger("-1"));
  246. $this->value = $temp->value;
  247. }
  248. break;
  249.  
  250. case 16:
  251. case -16:
  252. if (0 < $base && $x[0] == "-") {
  253. $this->is_negative = true;
  254. $x = substr_safe($x, 1);
  255. }
  256. $x = preg_replace("#^(?:0x)?([A-Fa-f0-9]*).*#", "\$1", $x);
  257. $is_negative = false;
  258. if ($base < 0 && 8 <= hexdec($x[0])) {
  259. $this->is_negative = $is_negative = true;
  260. $x = bin2hex(~(pack("H*", $x)));
  261. }
  262. switch (MATH_BIGINTEGER_MODE) {
  263. case MATH_BIGINTEGER_MODE_GMP:
  264. $temp = $this->is_negative ? "-0x" . $x : "0x" . $x;
  265. $this->value = gmp_init($temp);
  266. $this->is_negative = false;
  267. break;
  268.  
  269. case MATH_BIGINTEGER_MODE_BCMATH:
  270. $x = strlen_safe($x) & 1 ? "0" . $x : $x;
  271. $temp = new Math_BigInteger(pack("H*", $x), 256);
  272. $this->value = $this->is_negative ? "-" . $temp->value : $temp->value;
  273. $this->is_negative = false;
  274. break;
  275.  
  276. default:
  277. $x = strlen_safe($x) & 1 ? "0" . $x : $x;
  278. $temp = new Math_BigInteger(pack("H*", $x), 256);
  279. $this->value = $temp->value;
  280.  
  281. }
  282. if ($is_negative) {
  283. $temp = $this->add(new Math_BigInteger("-1"));
  284. $this->value = $temp->value;
  285. }
  286. break;
  287.  
  288. case 10:
  289. case -10:
  290. $x = preg_replace("#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#", "", $x);
  291. switch (MATH_BIGINTEGER_MODE) {
  292. case MATH_BIGINTEGER_MODE_GMP:
  293. $this->value = gmp_init($x);
  294. break;
  295.  
  296. case MATH_BIGINTEGER_MODE_BCMATH:
  297. $this->value = $x === "-" ? "0" : (string)$x;
  298. break;
  299.  
  300. default:
  301. $temp = new Math_BigInteger();
  302. $multiplier = new Math_BigInteger();
  303. $multiplier->value = array(MATH_BIGINTEGER_MAX10);
  304. if ($x[0] == "-") {
  305. $this->is_negative = true;
  306. $x = substr_safe($x, 1);
  307. }
  308. $x = str_pad($x, strlen_safe($x) + (MATH_BIGINTEGER_MAX10_LEN - 1) * strlen_safe($x) % MATH_BIGINTEGER_MAX10_LEN, 0, STR_PAD_LEFT);
  309. while (strlen_safe($x)) {
  310. $temp = $temp->multiply($multiplier);
  311. $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr_safe($x, 0, MATH_BIGINTEGER_MAX10_LEN)), 256));
  312. $x = substr_safe($x, MATH_BIGINTEGER_MAX10_LEN);
  313. }
  314. $this->value = $temp->value;
  315.  
  316. }
  317. break;
  318.  
  319. case 2:
  320. case -2:
  321. if (0 < $base && $x[0] == "-") {
  322. $this->is_negative = true;
  323. $x = substr_safe($x, 1);
  324. }
  325. $x = preg_replace("#^([01]*).*#", "\$1", $x);
  326. $x = str_pad($x, strlen_safe($x) + 3 * strlen_safe($x) % 4, 0, STR_PAD_LEFT);
  327. $str = "0x";
  328. while (strlen_safe($x)) {
  329. $part = substr_safe($x, 0, 4);
  330. $str .= dechex(bindec($part));
  331. $x = substr_safe($x, 4);
  332. }
  333. if ($this->is_negative) {
  334. $str = "-" . $str;
  335. }
  336. $temp = new Math_BigInteger($str, 8 * $base);
  337. $this->value = $temp->value;
  338. $this->is_negative = $temp->is_negative;
  339. break;
  340.  
  341. }
  342. }
  343.  
  344.  
  345. /**
  346. * Converts a BigInteger to a byte string (eg. base-256).
  347. *
  348. * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  349. * saved as two's compliment.
  350. *
  351. * Here's an example:
  352. * <code>
  353. * <?php
  354. * include 'Math/BigInteger.php';
  355. *
  356. * $a = new Math_BigInteger('65');
  357. *
  358. * echo $a->toBytes(); // outputs chr(65)
  359. * ?>
  360. * </code>
  361. *
  362. * @param Boolean $twos_compliment
  363. * @return String
  364. * @access public
  365. * @internal Converts a base-2**26 number to base-2**8
  366. */
  367. public function toBytes($twos_compliment = false) {
  368. if ($twos_compliment) {
  369. $comparison = $this->compare(new Math_BigInteger());
  370. if ($comparison == 0) {
  371. return 0 < $this->precision ? str_repeat(chr(0), $this->precision + 1 >> 3) : "";
  372. }
  373. $temp = $comparison < 0 ? $this->add(new Math_BigInteger(1)) : $this->copy();
  374. $bytes = $temp->toBytes();
  375. if (empty($bytes)) {
  376. $bytes = chr(0);
  377. }
  378. if (ord($bytes[0]) & 128) {
  379. $bytes = chr(0) . $bytes;
  380. }
  381. return $comparison < 0 ? ~$bytes : $bytes;
  382. }
  383. switch (MATH_BIGINTEGER_MODE) {
  384. case MATH_BIGINTEGER_MODE_GMP:
  385. if (gmp_cmp($this->value, gmp_init(0)) == 0) {
  386. return 0 < $this->precision ? str_repeat(chr(0), $this->precision + 1 >> 3) : "";
  387. }
  388. $temp = gmp_strval(gmp_abs($this->value), 16);
  389. $temp = strlen_safe($temp) & 1 ? "0" . $temp : $temp;
  390. $temp = pack("H*", $temp);
  391. return 0 < $this->precision ? substr_safe(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), 0 - ($this->precision >> 3)) : ltrim($temp, chr(0));
  392.  
  393. case MATH_BIGINTEGER_MODE_BCMATH:
  394. if ($this->value === "0") {
  395. return 0 < $this->precision ? str_repeat(chr(0), $this->precision + 1 >> 3) : "";
  396. }
  397. $value = "";
  398. $current = $this->value;
  399. if ($current[0] == "-") {
  400. $current = substr_safe($current, 1);
  401. }
  402. while (0 < bccomp($current, "0", 0)) {
  403. $temp = bcmod($current, "16777216");
  404. $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
  405. $current = bcdiv($current, "16777216", 0);
  406. }
  407. return 0 < $this->precision ? substr_safe(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), 0 - ($this->precision >> 3)) : ltrim($value, chr(0));
  408.  
  409. }
  410. if (!(count($this->value))) {
  411. return 0 < $this->precision ? str_repeat(chr(0), $this->precision + 1 >> 3) : "";
  412. }
  413. $result = $this->_int2bytes($this->value[count($this->value) - 1]);
  414. $temp = $this->copy();
  415. $i = count($temp->value) - 2;
  416. while (0 <= $i) {
  417. $temp->_base256_lshift($result, MATH_BIGINTEGER_BASE);
  418. $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen_safe($result), chr(0), STR_PAD_LEFT);
  419. --$i;
  420. }
  421. return 0 < $this->precision ? str_pad(substr_safe($result, 0 - ($this->precision + 7 >> 3)), $this->precision + 7 >> 3, chr(0), STR_PAD_LEFT) : $result;
  422. }
  423.  
  424.  
  425. /**
  426. * Converts a BigInteger to a hex string (eg. base-16)).
  427. *
  428. * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  429. * saved as two's compliment.
  430. *
  431. * Here's an example:
  432. * <code>
  433. * <?php
  434. * include 'Math/BigInteger.php';
  435. *
  436. * $a = new Math_BigInteger('65');
  437. *
  438. * echo $a->toHex(); // outputs '41'
  439. * ?>
  440. * </code>
  441. *
  442. * @param Boolean $twos_compliment
  443. * @return String
  444. * @access public
  445. * @internal Converts a base-2**26 number to base-2**8
  446. */
  447. public function toHex($twos_compliment = false) {
  448. return bin2hex($this->toBytes($twos_compliment));
  449. }
  450.  
  451.  
  452. /**
  453. * Converts a BigInteger to a bit string (eg. base-2).
  454. *
  455. * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
  456. * saved as two's compliment.
  457. *
  458. * Here's an example:
  459. * <code>
  460. * <?php
  461. * include 'Math/BigInteger.php';
  462. *
  463. * $a = new Math_BigInteger('65');
  464. *
  465. * echo $a->toBits(); // outputs '1000001'
  466. * ?>
  467. * </code>
  468. *
  469. * @param Boolean $twos_compliment
  470. * @return String
  471. * @access public
  472. * @internal Converts a base-2**26 number to base-2**2
  473. */
  474. public function toBits($twos_compliment = false) {
  475. $hex = $this->toHex($twos_compliment);
  476. $bits = "";
  477. $i = strlen_safe($hex) - 8;
  478. $start = strlen_safe($hex) & 7;
  479. while ($start <= $i) {
  480. $bits = str_pad(decbin(hexdec(substr_safe($hex, $i, 8))), 32, "0", STR_PAD_LEFT) . $bits;
  481. $i -= 8;
  482. }
  483. if ($start) {
  484. $bits = str_pad(decbin(hexdec(substr_safe($hex, 0, $start))), 8, "0", STR_PAD_LEFT) . $bits;
  485. }
  486. $result = 0 < $this->precision ? substr_safe($bits, 0 - $this->precision) : ltrim($bits, "0");
  487. if ($twos_compliment && 0 < $this->compare(new Math_BigInteger()) && $this->precision <= 0) {
  488. return "0" . $result;
  489. }
  490. return $result;
  491. }
  492.  
  493.  
  494. /**
  495. * Converts a BigInteger to a base-10 number.
  496. *
  497. * Here's an example:
  498. * <code>
  499. * <?php
  500. * include 'Math/BigInteger.php';
  501. *
  502. * $a = new Math_BigInteger('50');
  503. *
  504. * echo $a->toString(); // outputs 50
  505. * ?>
  506. * </code>
  507. *
  508. * @return String
  509. * @access public
  510. * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
  511. */
  512. public function toString() {
  513. switch (MATH_BIGINTEGER_MODE) {
  514. case MATH_BIGINTEGER_MODE_GMP:
  515. return gmp_strval($this->value);
  516.  
  517. case MATH_BIGINTEGER_MODE_BCMATH:
  518. if ($this->value === "0") {
  519. return "0";
  520. }
  521. return ltrim($this->value, "0");
  522.  
  523. }
  524. if (!(count($this->value))) {
  525. return "0";
  526. }
  527. $temp = $this->copy();
  528. $temp->is_negative = false;
  529. $divisor = new Math_BigInteger();
  530. $divisor->value = array(MATH_BIGINTEGER_MAX10);
  531. $result = "";
  532. while (count($temp->value)) {
  533. list($temp, $mod) = $temp->divide($divisor);
  534. $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : "", MATH_BIGINTEGER_MAX10_LEN, "0", STR_PAD_LEFT) . $result;
  535. }
  536. $result = ltrim($result, "0");
  537. if (empty($result)) {
  538. $result = "0";
  539. }
  540. if ($this->is_negative) {
  541. $result = "-" . $result;
  542. }
  543. return $result;
  544. }
  545.  
  546.  
  547. /**
  548. * Copy an object
  549. *
  550. * PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee
  551. * that all objects are passed by value, when appropriate. More information can be found here:
  552. *
  553. * {@link http://php.net/language.oop5.basic#51624}
  554. *
  555. * @access public
  556. * @see __clone()
  557. * @return Math_BigInteger
  558. */
  559. public function copy() {
  560. $temp = new Math_BigInteger();
  561. $temp->value = $this->value;
  562. $temp->is_negative = $this->is_negative;
  563. $temp->generator = $this->generator;
  564. $temp->precision = $this->precision;
  565. $temp->bitmask = $this->bitmask;
  566. return $temp;
  567. }
  568.  
  569.  
  570. /**
  571. * __toString() magic method
  572. *
  573. * Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call
  574. * toString().
  575. *
  576. * @access public
  577. * @internal Implemented per a suggestion by Techie-Michael - thanks!
  578. */
  579. public function __toString() {
  580. return $this->toString();
  581. }
  582.  
  583.  
  584. /**
  585. * __clone() magic method
  586. *
  587. * Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone()
  588. * directly in PHP5. You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5
  589. * only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and PHP5,
  590. * call Math_BigInteger::copy(), instead.
  591. *
  592. * @access public
  593. * @see copy()
  594. * @return Math_BigInteger
  595. */
  596. public function __clone() {
  597. return $this->copy();
  598. }
  599.  
  600.  
  601. /**
  602. * __sleep() magic method
  603. *
  604. * Will be called, automatically, when serialize() is called on a Math_BigInteger object.
  605. *
  606. * @see __wakeup()
  607. * @access public
  608. */
  609. public function __sleep() {
  610. $this->hex = $this->toHex(true);
  611. $vars = array("hex");
  612. if ($this->generator != "mt_rand") {
  613. $vars[] = "generator";
  614. }
  615. if (0 < $this->precision) {
  616. $vars[] = "precision";
  617. }
  618. return $vars;
  619. }
  620.  
  621.  
  622. /**
  623. * __wakeup() magic method
  624. *
  625. * Will be called, automatically, when unserialize() is called on a Math_BigInteger object.
  626. *
  627. * @see __sleep()
  628. * @access public
  629. */
  630. public function __wakeup() {
  631. $temp = new Math_BigInteger($this->hex, -16);
  632. $this->value = $temp->value;
  633. $this->is_negative = $temp->is_negative;
  634. $this->setRandomGenerator($this->generator);
  635. if (0 < $this->precision) {
  636. $this->setPrecision($this->precision);
  637. }
  638. }
  639.  
  640.  
  641. /**
  642. * Adds two BigIntegers.
  643. *
  644. * Here's an example:
  645. * <code>
  646. * <?php
  647. * include 'Math/BigInteger.php';
  648. *
  649. * $a = new Math_BigInteger('10');
  650. * $b = new Math_BigInteger('20');
  651. *
  652. * $c = $a->add($b);
  653. *
  654. * echo $c->toString(); // outputs 30
  655. * ?>
  656. * </code>
  657. *
  658. * @param Math_BigInteger $y
  659. * @return Math_BigInteger
  660. * @access public
  661. * @internal Performs base-2**52 addition
  662. */
  663. public function add($y) {
  664. switch (MATH_BIGINTEGER_MODE) {
  665. case MATH_BIGINTEGER_MODE_GMP:
  666. $temp = new Math_BigInteger();
  667. $temp->value = gmp_add($this->value, $y->value);
  668. return $this->_normalize($temp);
  669.  
  670. case MATH_BIGINTEGER_MODE_BCMATH:
  671. $temp = new Math_BigInteger();
  672. $temp->value = bcadd($this->value, $y->value, 0);
  673. return $this->_normalize($temp);
  674.  
  675. }
  676. $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
  677. $result = new Math_BigInteger();
  678. $result->value = $temp[MATH_BIGINTEGER_VALUE];
  679. $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
  680. return $this->_normalize($result);
  681. }
  682.  
  683.  
  684. /**
  685. * Performs addition.
  686. *
  687. * @param Array $x_value
  688. * @param Boolean $x_negative
  689. * @param Array $y_value
  690. * @param Boolean $y_negative
  691. * @return Array
  692. * @access private
  693. */
  694. public function _add($x_value, $x_negative, $y_value, $y_negative) {
  695. $x_size = count($x_value);
  696. $y_size = count($y_value);
  697. if ($x_size == 0) {
  698. return array(MATH_BIGINTEGER_VALUE => $y_value, MATH_BIGINTEGER_SIGN => $y_negative);
  699. }
  700. if ($y_size == 0) {
  701. return array(MATH_BIGINTEGER_VALUE => $x_value, MATH_BIGINTEGER_SIGN => $x_negative);
  702. }
  703. if ($x_negative != $y_negative) {
  704. if ($x_value == $y_value) {
  705. return array(MATH_BIGINTEGER_VALUE => array(), MATH_BIGINTEGER_SIGN => false);
  706. }
  707. $temp = $this->_subtract($x_value, false, $y_value, false);
  708. $temp[MATH_BIGINTEGER_SIGN] = 0 < $this->_compare($x_value, false, $y_value, false) ? $x_negative : $y_negative;
  709. return $temp;
  710. }
  711. if ($x_size < $y_size) {
  712. $size = $x_size;
  713. $value = $y_value;
  714. }
  715. else {
  716. $size = $y_size;
  717. $value = $x_value;
  718. }
  719. $value[] = 0;
  720. $carry = 0;
  721. $i = 0;
  722. $j = 1;
  723. while ($j < $size) {
  724. $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] + $y_value[$j] * MATH_BIGINTEGER_BASE_FULL + $y_value[$i] + $carry;
  725. $carry = MATH_BIGINTEGER_MAX_DIGIT2 <= $sum;
  726. $sum = $carry ? $sum - MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
  727. $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 67108864) : $sum >> 31;
  728. $value[$i] = (int)$sum - MATH_BIGINTEGER_BASE_FULL * $temp;
  729. $value[$j] = $temp;
  730. $i += 2;
  731. $j += 2;
  732. continue;
  733. }
  734. if ($j == $size) {
  735. $sum = $x_value[$i] + $y_value[$i] + $carry;
  736. $carry = MATH_BIGINTEGER_BASE_FULL <= $sum;
  737. $value[$i] = $carry ? $sum - MATH_BIGINTEGER_BASE_FULL : $sum;
  738. ++$i;
  739. }
  740. if ($carry) {
  741. while ($value[$i] == MATH_BIGINTEGER_MAX_DIGIT) {
  742. $value[$i] = 0;
  743. ++$i;
  744. }
  745. ++$value[$i];
  746. }
  747. return array(MATH_BIGINTEGER_VALUE => $this->_trim($value), MATH_BIGINTEGER_SIGN => $x_negative);
  748. }
  749.  
  750.  
  751. /**
  752. * Subtracts two BigIntegers.
  753. *
  754. * Here's an example:
  755. * <code>
  756. * <?php
  757. * include 'Math/BigInteger.php';
  758. *
  759. * $a = new Math_BigInteger('10');
  760. * $b = new Math_BigInteger('20');
  761. *
  762. * $c = $a->subtract($b);
  763. *
  764. * echo $c->toString(); // outputs -10
  765. * ?>
  766. * </code>
  767. *
  768. * @param Math_BigInteger $y
  769. * @return Math_BigInteger
  770. * @access public
  771. * @internal Performs base-2**52 subtraction
  772. */
  773. public function subtract($y) {
  774. switch (MATH_BIGINTEGER_MODE) {
  775. case MATH_BIGINTEGER_MODE_GMP:
  776. $temp = new Math_BigInteger();
  777. $temp->value = gmp_sub($this->value, $y->value);
  778. return $this->_normalize($temp);
  779.  
  780. case MATH_BIGINTEGER_MODE_BCMATH:
  781. $temp = new Math_BigInteger();
  782. $temp->value = bcsub($this->value, $y->value, 0);
  783. return $this->_normalize($temp);
  784.  
  785. }
  786. $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
  787. $result = new Math_BigInteger();
  788. $result->value = $temp[MATH_BIGINTEGER_VALUE];
  789. $result->is_negative = $temp[MATH_BIGINTEGER_SIGN];
  790. return $this->_normalize($result);
  791. }
  792.  
  793.  
  794. /**
  795. * Performs subtraction.
  796. *
  797. * @param Array $x_value
  798. * @param Boolean $x_negative
  799. * @param Array $y_value
  800. * @param Boolean $y_negative
  801. * @return Array
  802. * @access private
  803. */
  804. public function _subtract($x_value, $x_negative, $y_value, $y_negative) {
  805. $x_size = count($x_value);
  806. $y_size = count($y_value);
  807. if ($x_size == 0) {
  808. return array(MATH_BIGINTEGER_VALUE => $y_value, MATH_BIGINTEGER_SIGN => !$y_negative);
  809. }
  810. if ($y_size == 0) {
  811. return array(MATH_BIGINTEGER_VALUE => $x_value, MATH_BIGINTEGER_SIGN => $x_negative);
  812. }
  813. if ($x_negative != $y_negative) {
  814. $temp = $this->_add($x_value, false, $y_value, false);
  815. $temp[MATH_BIGINTEGER_SIGN] = $x_negative;
  816. return $temp;
  817. }
  818. $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
  819. if (!$diff) {
  820. return array(MATH_BIGINTEGER_VALUE => array(), MATH_BIGINTEGER_SIGN => false);
  821. }
  822. if (!$x_negative && $diff < 0 || $x_negative && 0 < $diff) {
  823. $temp = $x_value;
  824. $x_value = $y_value;
  825. $y_value = $temp;
  826. $x_negative = !$x_negative;
  827. $x_size = count($x_value);
  828. $y_size = count($y_value);
  829. }
  830. $carry = 0;
  831. $i = 0;
  832. $j = 1;
  833. while ($j < $y_size) {
  834. $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] - $y_value[$j] * MATH_BIGINTEGER_BASE_FULL - $y_value[$i] - $carry;
  835. $carry = $sum < 0;
  836. $sum = $carry ? $sum + MATH_BIGINTEGER_MAX_DIGIT2 : $sum;
  837. $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 67108864) : $sum >> 31;
  838. $x_value[$i] = (int)$sum - MATH_BIGINTEGER_BASE_FULL * $temp;
  839. $x_value[$j] = $temp;
  840. $i += 2;
  841. $j += 2;
  842. }
  843. if ($j == $y_size) {
  844. $sum = $x_value[$i] - $y_value[$i] - $carry;
  845. $carry = $sum < 0;
  846. $x_value[$i] = $carry ? $sum + MATH_BIGINTEGER_BASE_FULL : $sum;
  847. ++$i;
  848. }
  849. if ($carry) {
  850. while (!$x_value[$i]) {
  851. $x_value[$i] = MATH_BIGINTEGER_MAX_DIGIT;
  852. ++$i;
  853. }
  854. --$x_value[$i];
  855. }
  856. return array(MATH_BIGINTEGER_VALUE => $this->_trim($x_value), MATH_BIGINTEGER_SIGN => $x_negative);
  857. }
  858.  
  859.  
  860. /**
  861. * Multiplies two BigIntegers
  862. *
  863. * Here's an example:
  864. * <code>
  865. * <?php
  866. * include 'Math/BigInteger.php';
  867. *
  868. * $a = new Math_BigInteger('10');
  869. * $b = new Math_BigInteger('20');
  870. *
  871. * $c = $a->multiply($b);
  872. *
  873. * echo $c->toString(); // outputs 200
  874. * ?>
  875. * </code>
  876. *
  877. * @param Math_BigInteger $x
  878. * @return Math_BigInteger
  879. * @access public
  880. */
  881. public function multiply($x) {
  882. switch (MATH_BIGINTEGER_MODE) {
  883. case MATH_BIGINTEGER_MODE_GMP:
  884. $temp = new Math_BigInteger();
  885. $temp->value = gmp_mul($this->value, $x->value);
  886. return $this->_normalize($temp);
  887.  
  888. case MATH_BIGINTEGER_MODE_BCMATH:
  889. $temp = new Math_BigInteger();
  890. $temp->value = bcmul($this->value, $x->value, 0);
  891. return $this->_normalize($temp);
  892.  
  893. }
  894. $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
  895. $product = new Math_BigInteger();
  896. $product->value = $temp[MATH_BIGINTEGER_VALUE];
  897. $product->is_negative = $temp[MATH_BIGINTEGER_SIGN];
  898. return $this->_normalize($product);
  899. }
  900.  
  901.  
  902. /**
  903. * Performs multiplication.
  904. *
  905. * @param Array $x_value
  906. * @param Boolean $x_negative
  907. * @param Array $y_value
  908. * @param Boolean $y_negative
  909. * @return Array
  910. * @access private
  911. */
  912. public function _multiply($x_value, $x_negative, $y_value, $y_negative) {
  913. $x_length = count($x_value);
  914. $y_length = count($y_value);
  915. if (!$x_length || !$y_length) {
  916. return array(MATH_BIGINTEGER_VALUE => array(), MATH_BIGINTEGER_SIGN => false);
  917. }
  918. return array(MATH_BIGINTEGER_VALUE => min($x_length, $y_length) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ? $this->_trim($this->_regularMultiply($x_value, $y_value)) : $this->_trim($this->_karatsuba($x_value, $y_value)), MATH_BIGINTEGER_SIGN => $x_negative != $y_negative);
  919. }
  920.  
  921.  
  922. /**
  923. * Performs long multiplication on two BigIntegers
  924. *
  925. * Modeled after 'multiply' in MutableBigInteger.java.
  926. *
  927. * @param Array $x_value
  928. * @param Array $y_value
  929. * @return Array
  930. * @access private
  931. */
  932. public function _regularMultiply($x_value, $y_value) {
  933. $x_length = count($x_value);
  934. $y_length = count($y_value);
  935. if (!$x_length || !$y_length) {
  936. return array();
  937. }
  938. if ($x_length < $y_length) {
  939. $temp = $x_value;
  940. $x_value = $y_value;
  941. $y_value = $temp;
  942. $x_length = count($x_value);
  943. $y_length = count($y_value);
  944. }
  945. $product_value = $this->_array_repeat(0, $x_length + $y_length);
  946. $carry = 0;
  947. $j = 0;
  948. while ($j < $x_length) {
  949. $temp = $x_value[$j] * $y_value[0] + $carry;
  950. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 67108864) : $temp >> 31;
  951. $product_value[$j] = (int)$temp - MATH_BIGINTEGER_BASE_FULL * $carry;
  952. ++$j;
  953. }
  954. $product_value[$j] = $carry;
  955. $i = 1;
  956. while ($i < $y_length) {
  957. $carry = 0;
  958. $j = 0;
  959. $k = $i;
  960. while ($j < $x_length) {
  961. $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
  962. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 67108864) : $temp >> 31;
  963. $product_value[$k] = (int)$temp - MATH_BIGINTEGER_BASE_FULL * $carry;
  964. ++$j;
  965. ++$k;
  966. }
  967. $product_value[$k] = $carry;
  968. ++$i;
  969. continue;
  970. }
  971. return $product_value;
  972. }
  973.  
  974.  
  975. /**
  976. * Performs Karatsuba multiplication on two BigIntegers
  977. *
  978. * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
  979. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
  980. *
  981. * @param Array $x_value
  982. * @param Array $y_value
  983. * @return Array
  984. * @access private
  985. */
  986. public function _karatsuba($x_value, $y_value) {
  987. $m = min(count($x_value) >> 1, count($y_value) >> 1);
  988. if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
  989. return $this->_regularMultiply($x_value, $y_value);
  990. }
  991. $x1 = array_slice($x_value, $m);
  992. $x0 = array_slice($x_value, 0, $m);
  993. $y1 = array_slice($y_value, $m);
  994. $y0 = array_slice($y_value, 0, $m);
  995. $z2 = $this->_karatsuba($x1, $y1);
  996. $z0 = $this->_karatsuba($x0, $y0);
  997. $z1 = $this->_add($x1, false, $x0, false);
  998. $temp = $this->_add($y1, false, $y0, false);
  999. $z1 = $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_VALUE]);
  1000. $temp = $this->_add($z2, false, $z0, false);
  1001. $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
  1002. $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
  1003. $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
  1004. $xy = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
  1005. $xy = $this->_add($xy[MATH_BIGINTEGER_VALUE], $xy[MATH_BIGINTEGER_SIGN], $z0, false);
  1006. return $xy[MATH_BIGINTEGER_VALUE];
  1007. }
  1008.  
  1009.  
  1010. /**
  1011. * Performs squaring
  1012. *
  1013. * @param Array $x
  1014. * @return Array
  1015. * @access private
  1016. */
  1017. public function _square($x = false) {
  1018. return count($x) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ? $this->_trim($this->_baseSquare($x)) : $this->_trim($this->_karatsubaSquare($x));
  1019. }
  1020.  
  1021.  
  1022. /**
  1023. * Performs traditional squaring on two BigIntegers
  1024. *
  1025. * Squaring can be done faster than multiplying a number by itself can be. See
  1026. * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
  1027. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
  1028. *
  1029. * @param Array $value
  1030. * @return Array
  1031. * @access private
  1032. */
  1033. public function _baseSquare($value) {
  1034. if (empty($value)) {
  1035. return array();
  1036. }
  1037. $square_value = $this->_array_repeat(0, 2 * count($value));
  1038. $i = 0;
  1039. $max_index = count($value) - 1;
  1040. while ($i <= $max_index) {
  1041. $i2 = $i << 1;
  1042. $temp = $square_value[$i2] + $value[$i] * $value[$i];
  1043. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 67108864) : $temp >> 31;
  1044. $square_value[$i2] = (int)$temp - MATH_BIGINTEGER_BASE_FULL * $carry;
  1045. $j = $i + 1;
  1046. $k = $i2 + 1;
  1047. while ($j <= $max_index) {
  1048. $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
  1049. $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 67108864) : $temp >> 31;
  1050. $square_value[$k] = (int)$temp - MATH_BIGINTEGER_BASE_FULL * $carry;
  1051. ++$j;
  1052. ++$k;
  1053. continue;
  1054. }
  1055. $square_value[$i + $max_index + 1] = $carry;
  1056. ++$i;
  1057. }
  1058. return $square_value;
  1059. }
  1060.  
  1061.  
  1062. /**
  1063. * Performs Karatsuba "squaring" on two BigIntegers
  1064. *
  1065. * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
  1066. * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
  1067. *
  1068. * @param Array $value
  1069. * @return Array
  1070. * @access private
  1071. */
  1072. public function _karatsubaSquare($value) {
  1073. $m = count($value) >> 1;
  1074. if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
  1075. return $this->_baseSquare($value);
  1076. }
  1077. $x1 = array_slice($value, $m);
  1078. $x0 = array_slice($value, 0, $m);
  1079. $z2 = $this->_karatsubaSquare($x1);
  1080. $z0 = $this->_karatsubaSquare($x0);
  1081. $z1 = $this->_add($x1, false, $x0, false);
  1082. $z1 = $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE]);
  1083. $temp = $this->_add($z2, false, $z0, false);
  1084. $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false);
  1085. $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
  1086. $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]);
  1087. $xx = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]);
  1088. $xx = $this->_add($xx[MATH_BIGINTEGER_VALUE], $xx[MATH_BIGINTEGER_SIGN], $z0, false);
  1089. return $xx[MATH_BIGINTEGER_VALUE];
  1090. }
  1091.  
  1092.  
  1093. /**
  1094. * Divides two BigIntegers.
  1095. *
  1096. * Returns an array whose first element contains the quotient and whose second element contains the
  1097. * "common residue". If the remainder would be positive, the "common residue" and the remainder are the
  1098. * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder
  1099. * and the divisor (basically, the "common residue" is the first positive modulo).
  1100. *
  1101. * Here's an example:
  1102. * <code>
  1103. * <?php
  1104. * include 'Math/BigInteger.php';
  1105. *
  1106. * $a = new Math_BigInteger('10');
  1107. * $b = new Math_BigInteger('20');
  1108. *
  1109. * list($quotient, $remainder) = $a->divide($b);
  1110. *
  1111. * echo $quotient->toString(); // outputs 0
  1112. * echo "\r\n";
  1113. * echo $remainder->toString(); // outputs 10
  1114. * ?>
  1115. * </code>
  1116. *
  1117. * @param Math_BigInteger $y
  1118. * @return Array
  1119. * @access public
  1120. * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
  1121. */
  1122. public function divide($y) {
  1123. switch (MATH_BIGINTEGER_MODE) {
  1124. case MATH_BIGINTEGER_MODE_GMP:
  1125. $quotient = new Math_BigInteger();
  1126. $remainder = new Math_BigInteger();
  1127. list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
  1128. if (gmp_sign($remainder->value) < 0) {
  1129. $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
  1130. }
  1131. return array($this->_normalize($quotient), $this->_normalize($remainder));
  1132.  
  1133. case MATH_BIGINTEGER_MODE_BCMATH:
  1134. $quotient = new Math_BigInteger();
  1135. $remainder = new Math_BigInteger();
  1136. $quotient->value = bcdiv($this->value, $y->value, 0);
  1137. $remainder->value = bcmod($this->value, $y->value);
  1138. if ($remainder->value[0] == "-") {
  1139. $remainder->value = bcadd($remainder->value, $y->value[0] == "-" ? substr_safe($y->value, 1) : $y->value, 0);
  1140. }
  1141. return array($this->_normalize($quotient), $this->_normalize($remainder));
  1142.  
  1143. }
  1144. if (count($y->value) == 1) {
  1145. list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
  1146. $quotient = new Math_BigInteger();
  1147. $remainder = new Math_BigInteger();
  1148. $quotient->value = $q;
  1149. $remainder->value = array($r);
  1150. $quotient->is_negative = $this->is_negative != $y->is_negative;
  1151. return array($this->_normalize($quotient), $this->_normalize($remainder));
  1152. }
  1153. static $zero;
  1154. if (!(isset($zero))) {
  1155. $zero = new Math_BigInteger();
  1156. }
  1157. $x = $this->copy();
  1158. $y = $y->copy();
  1159. $x_sign = $x->is_negative;
  1160. $y_sign = $y->is_negative;
  1161. $x->is_negative = $y->is_negative = false;
  1162. $diff = $x->compare($y);
  1163. if (!$diff) {
  1164. $temp = new Math_BigInteger();
  1165. $temp->value = array(1);
  1166. $temp->is_negative = $x_sign != $y_sign;
  1167. return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger()));
  1168. }
  1169. if ($diff < 0) {
  1170. if ($x_sign) {
  1171. $x = $y->subtract($x);
  1172. }
  1173. ..........................................................
  1174. .........................
  1175. ..........
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!