From 856dc4c5c13fb52741de8a2fb124e0d05a553ddb Mon Sep 17 00:00:00 2001
From: data-man <datamanrb@gmail.com>
Date: Fri, 25 May 2018 18:52:04 +0300
Subject: Fixes for parseUntil when until.len == 0 (or nil)

---
 lib/pure/parseutils.nim | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'lib/pure')

diff --git a/lib/pure/parseutils.nim b/lib/pure/parseutils.nim
index d77790fe0..d54f1454b 100644
--- a/lib/pure/parseutils.nim
+++ b/lib/pure/parseutils.nim
@@ -197,6 +197,9 @@ proc parseUntil*(s: string, token: var string, until: string,
   ## parses a token and stores it in ``token``. Returns
   ## the number of the parsed characters or 0 in case of an error. A token
   ## consists of any character that comes before the `until`  token.
+  if until.len == 0:
+    token.setLen(0)
+    return 0
   var i = start
   while i < s.len:
     if s[i] == until[0]:
-- 
cgit 1.4.1-2-gfad0


From 09283bb9399f3eba62d2ce682d25b7b34a4ec135 Mon Sep 17 00:00:00 2001
From: Koki Fushimi <paalon1936@gmail.com>
Date: Sat, 26 May 2018 14:31:45 +0900
Subject: Faster binary gcd algorithm (#7849)

* Faster binary gcd algorithm.

* Use built in countTrailingZeroBits to calculate gcd.

* Add definitions of gcd for integers and other types.

* Unified signed case and unsinged case in one proc by using when syntax.

* Change to faster one.
---
 lib/pure/math.nim | 32 ++++++++++++++++++++++++++++++--
 1 file changed, 30 insertions(+), 2 deletions(-)

(limited to 'lib/pure')

diff --git a/lib/pure/math.nim b/lib/pure/math.nim
index 9e590debc..49d87f007 100644
--- a/lib/pure/math.nim
+++ b/lib/pure/math.nim
@@ -21,6 +21,8 @@ include "system/inclrtl"
 {.push debugger:off .} # the user does not want to trace a part
                        # of the standard library!
 
+import bitops
+
 proc binom*(n, k: int): int {.noSideEffect.} =
   ## Computes the binomial coefficient
   if k <= 0: return 1
@@ -455,16 +457,42 @@ proc `^`*[T](x: T, y: Natural): T =
     x *= x
 
 proc gcd*[T](x, y: T): T =
-  ## Computes the greatest common divisor of ``x`` and ``y``.
+  ## Computes the greatest common (positive) divisor of ``x`` and ``y``.
   ## Note that for floats, the result cannot always be interpreted as
   ## "greatest decimal `z` such that ``z*N == x and z*M == y``
   ## where N and M are positive integers."
-  var (x,y) = (x,y)
+  var (x, y) = (x, y)
   while y != 0:
     x = x mod y
     swap x, y
   abs x
 
+proc gcd*(x, y: SomeInteger): SomeInteger =
+  ## Computes the greatest common (positive) divisor of ``x`` and ``y``.
+  ## Using binary GCD (aka Stein's) algorithm.
+  when x is SomeSignedInt:
+    var x = abs(x)
+  else:
+    var x = x
+  when y is SomeSignedInt:
+    var y = abs(y)
+  else:
+    var y = y
+
+  if x == 0:
+    return y
+  if y == 0:
+    return x
+
+  let shift = countTrailingZeroBits(x or y)
+  y = y shr countTrailingZeroBits(y)
+  while x != 0:
+    x = x shr countTrailingZeroBits(x)
+    if y > x:
+      swap y, x
+    x -= y
+  y shl shift
+
 proc lcm*[T](x, y: T): T =
   ## Computes the least common multiple of ``x`` and ``y``.
   x div gcd(x, y) * y
-- 
cgit 1.4.1-2-gfad0