Celtic did a superb job of remapping my 406 HDi 2.2 - the results were stunning, taking a lively car and turning it into a fast one.
When my car was 'done' they were almost a 'diesel only' outfit. This was in 2006.
In the meantime Celtic has expanded it's range of services and now offers support for many petrol cars as well. The S4 should be well within Celtic's grasp.