If you reduce the problem statement to an ELF x86 program written in C, with a symbol table
and a complete relocation table (not just the one you get when dynamically linking), then sure it's trivial, you have
almost all the information you need to make an object file (issues like switch jump tables can still crop up in that case). If you don't have that relocation table from `cc -r` however, you'll run into problems.
Without this relocation table on hand, you'll have to recreate it in order to make the section bytes relocatable again. This means analyzing code/data and identifying relocation spots, like you've said. But that `0x00400000` integer constant within an instruction or a word data, is it referring to the function at that address or is it the TOSTOP flag value? Who knows, but each time you get it wrong you'll corrupt four bytes in that object file.
I'm dealing with one rather gnarly scenario, which is a PlayStation video game without any source code, symbols [1] or linker map, just a bag of bytes in an a.out-like format. The MIPS architecture also happens to be an absolute nightmare to delink code from (one of the many pitfalls for example is the interaction between HI16/LO16 relocation pairs, branch delay slots and linkers with a peephole optimizer).
I've been at it for two years and I've only recently managed to pull it off on the entire game code [2]. Writing out the object file when you have the program bytes, the symbol table and the relocation tables is the easy part. Writing an analyzer that recreates a missing relocation table for the 80% of easy cases isn't too difficult. Squashing out the remaining 20% of edge cases is hard. All it takes is one mistake that affects a code path that's taken for some very exotic undefined behavior to occur in the delinked code.
Delinking with a missing relocation table (and without manually annotating the relocation spots yourself) is a thing that looks easy at first glance, but is deceptively hard to nail all of the edge cases. I'd gladly be proven wrong, but if you do have the full, original relocation table on hand then you're cheating with `cc -r` on code you just built yourself. Almost no real-world artifact spotted in the wild one would care about is ever built with that flag.
[1] I did end up recovering lots of data out of a leftover debugging symbols file from an early build later on, but that's a story for another time.
[2] Note that I'm working on top of a Ghidra database that contains symbols, type definitions and references, so the bulk of analysis is actually performed upstream of my tooling. Even then, the MIPS relocation synthesizer is a thousand lines of absolute eldritch horrors, but I do acknowledge that the x86 relocation synthesizer I have is quite tame in comparison.
