Я думаю, что релоцируемость распаковщика - это расточительство. Нужно просто спросить пользователя о желаемом адресе размещения распаковщика, и настроить его код на этот адрес. Хоть пара байт - а будет сэкономлена.

Если есть возможность уменьшить размер распаковщика, пусть даже ценой его замедления - надо использовать. Для 1к/4к интр это существенно. Малый размер файлов сделает замедление незаметным. Если кому-то не нравится медленное и неравномерное появление картинки - то можно распаковать не в экран, а в другое место, а потом перекинуть данные лдиром.

И вообще, назревает радикальный подход - генерация кода распаковщика. С учетом пожеланий пользователя, характера сжимаемых данных и т.д. Хотя бы компоновка распаковщика из заранее нарезанных кусков.

В режиме "минимизации размера брутто" компрессор может пробовать сжимать файл с отключением некоторых особенностей кодирования, если это приводит к уменьшению размера распаковщика, и сравнивать друг с другом размеры данных+распаковщика, и выбирать наиболее выгодный вариант с точки зрения суммарной длины.