For the cost of a small amount of metadata the offsets of every MiB or so could be stored. I did something like this with pigz as I was implementing multithread

For the cost of a small amount of metadata the offsets of every MiB or so could be stored. I did something like this with pigz as I was implementing multithreaded compressed and encrypted kernel zone suspend and resume for Solaris.