I could easily be underestimating the difficulty of integrating C with Python - I've never done it personally, but I gather that's one of its strengths. But this seems like a pretty simple problem, which has a pretty simple implementation in any language (there's an included Python implementation on the linked page, ~20 LOC?), and if it's a critical performance piece it's surely worth the cost to make that piece.
I completely believe that, and good point about Python 2. I wasn't considering that side of things.
Is it a complicated rewrite, or just big? Superficially it seems pretty mechanical, `bytes.format` to `bytes_format` (though finding them might be hard). I never feel like I have free time, but I don't tend to get exhausted from things like that, maybe I can contribute a bit. It would be good to get exposed to some decent, real Python code :)