God bless whoever wrote tests before you. Whether it be a rewrite or working on the current code base, those who have the time and resources and don't write tests are inexcusable and bad stewards
This is exactly what I went through during that four month period. The existing tests weren't very useful and I was completely changing the structure of how the program was architected, but the input v output could be measured. I, like you, also discovered critical bugs in the existing implementation because I needed to cover the entire combinatorial set or possible inputs whilst the original implementers presumably went through them as they came up.