I'm about to take on the task of reimplementing an already defined interface (a set of C++ header files) in a relatively large and old code base. Before doing this, I would like to have as complete test coverage as possible, so I can detect reimplementation errors as early and easily as possible. The problem is that the already existing code base was not designed to be easily testable, with (very) large classes and functions, a high degree of coupling, functions with (many) side effects, etc.
It would be nice to hear of any previous experience with similar tasks, and some good and concrete tips on how you went about retrofitting automated tests (unit, integrations, regression, etc.) to your legacy code.