A method and apparatus is described herein for compressing a binary image in memory and decompressing a portion memory in response to a request, without using a compression index table to find relocated compressed code. A binary image is traversed in windows. Each selected window is compressed to form compressed windows having a compressed portion and an available memory portion. Static data is backfilled in available memory portions to achieve efficient compression. Upon receiving a request to a specific physical address, the compressed portion of that physical location is decompressed and provided for execution without using a compression index table, as the compressed code portion was not relocated from its original physical location.