Christian:  I don't think this code is safe:

-    nd0 = nd = s - s1;
+    tmp = s - s1;
+    nd0 = nd = Py_SAFE_DOWNCAST(tmp, Py_SSIZE_T, int);

The result of the Py_SAFE_DOWNCAST could be almost anything, and in particular could be negative.  It would take a careful examination of the code to guarantee that a negative nd or nd0 won't lead to difficulties further down the algorithm.  I think we need to raise an error if tmp is too large, *before* the downcast.