How do you introduce unit testing into a large, legacy (C/C++) codebase?
we have not found anything to ease the transition from "hairball of code with no unit tests" to "unit-testable code".
How sad -- no miraculous solution -- just a lot of hard work correcting years of accumulated technical debt.
There is no easy transition. You have a large, complex, serious problem.
You can only solve it in tiny steps. Each tiny step involves the following.
Pick a discrete piece of code that's absolutely essential. (Don't nibble around the edges at junk.) Pick a component that's important and -- somehow -- can be carved out of the rest. While a single function is ideal, it might be a tangled cluster of functions or maybe a whole file of functions. It's okay to start with something less than perfect for your testable components.
Figure out what it's supposed to do. Figure out what it's interface is supposed to be. To do this, you may have to do some initial refactoring to make your target piece actually discrete.
Write an "overall" integration test that -- for now -- tests your discrete piece of code more-or-less as it was found. Get this to pass before you try and change anything significant.
Refactor the code into tidy, testable units that make better sense than your current hairball. You're going to have to maintain some backward compatibility (for now) with your overall integration test.
Write unit tests for the new units.
Once it all passes, decommission the old API and fix what will be broken by the change. If necessary, rework the original integration test; it tests the old API, you want to test the new API.
Iterate.
My little experience with legacy code and introducing testing would be to create the "Characterization tests". You start creating tests with known input and then get the output. These tests are useful for methods/classes that you don't know what they really do, but you know that they are working.
However, there are sometimes when it's nearly impossible to create unit tests (even characterization tests). On that case I attack the problem through acceptance tests (Fitnesse in this case).
You create the whole bunch of classes needed to test one feature and check it on fitnesse. It's similar to "characterization tests" but it's one level higher.