find_max_char() returns 0x10000 instead of 0x10FFFF, which may be wrong (or at least, surprising). You may add a max_char variable using other macros like MAX_CHAR_ASCII, MAX_CHAR_UCS1, ..., which will be set at the same time than mask. Or restore your if (ret >= 0x10000) return 0x10ffff; else return ret;.

Constants look inconsistent:

+    const STRINGLIB_CHAR *unrolled_end = begin + (n & ~ (Py_ssize_t) 7);
+        p += 4;

You may use STRINGLIB_CHAR in:

+        Py_UCS4 bits = p[0] | p[1] | p[2] | p[3];