Add support for compressed ota updates

[davisonja]

A useful improvement to the OTA system would be to transfer the update in a compressed format that is expanded as part of the final flash process.

This issue is to provide a place to discuss, plan and exchange clever ideas.

The very first discussion points appeared initially on #905

[devyte]

From #905:

The idea was floated at some point to add support for compressed images, i.e.: receive an image that is compressed.

The following possibilities for implementation have shown up:

Try for full (de)compression, i.e.: deflate, possibly use code from miniz from the flash_stub, which is already known to work on the ESP (because the flash_stub is used by esptool.py). Take the absolute minimum code to deflate and add it to eboot. There is a bit of space left between the end of the eboot bin and the start of the current sketch in the flash. This should be the best solution, because it would allow writing the received image in fully compressed form, then after reboot it could get decompressed on the fly while copying. Also, if the code fits, it would not increase bin size.
Pros:
would allow writing of larger images, thereby relaxing a bit the restriction of bin size for boards with smaller flash size
faster transfer speed
known algorithm and code
wouldn't increase bin size
Cons:
may not fit after eboot due to bin size
Try for some variation of RLE (run-length encoding). Similar idea as above, but with a simpler algorithm instead of miniz. If the above doesn't fit in the available eboot space, maybe this will.
Pros:
would allow writing of larger images, although less so than point 1 above
faster transfer speed, although less so than point 1 above
wouldn't increase bin size
more likely to fit in the available space after eboot
Cons:
less compression than deflate
likely custom compression/decompression code
Put all of miniz into Updater. That would allow receiving a fully compressed image, but it would require deflating it before writing it to the empty space area.
Pros:
smaller transfer size (faster transfer speed) like point 1 above
the eboot code would remain as-is
Cons:
bin size restrictions remain as current (decompress on receive instead of on copy)
bin size increment

[devyte]

@earlephilhower said:

MiniZ inflator alone takes 0x14b2 = 5298 bytes pf code when built with -Os.

I just patched in a naive version into the bootloader and updated the makefile to -Os and function/data_sections with gc-sections to drop everything that's not needed.

earle@server:~/Arduino/hardware/esp8266com/esp8266/bootloaders/eboot$ make
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-gcc -std=gnu99 -Os -g -Wpointer-arith -Wno-implicit-function-declaration -Wl,-EL -fno-inline-functions -nostdlib -mlongcalls -mno-text-section-literals -I../../tools/sdk/include -mtext-section-literals -mlongcalls -nostdlib -fno-builtin -flto -Wl,-static -g -fdata-sections -ffunction-sections -Wl,--gc-sections   -c -o eboot.o eboot.c
eboot.c: In function 'copy_raw':
eboot.c:119:10: warning: type defaults to 'int' in declaration of 'status' [enabled by default]
     auto status = tinfl_decompress(&inflator, buffer, &in_bytes,
          ^
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-gcc -std=gnu99 -Os -g -Wpointer-arith -Wno-implicit-function-declaration -Wl,-EL -fno-inline-functions -nostdlib -mlongcalls -mno-text-section-literals -I../../tools/sdk/include -mtext-section-literals -mlongcalls -nostdlib -fno-builtin -flto -Wl,-static -g -fdata-sections -ffunction-sections -Wl,--gc-sections   -c -o eboot_command.o eboot_command.c
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-gcc -std=gnu99 -Os -g -Wpointer-arith -Wno-implicit-function-declaration -Wl,-EL -fno-inline-functions -nostdlib -mlongcalls -mno-text-section-literals -I../../tools/sdk/include -mtext-section-literals -mlongcalls -nostdlib -fno-builtin -flto -Wl,-static -g -fdata-sections -ffunction-sections -Wl,--gc-sections   -c -o miniz.o miniz.c
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-ar cru eboot.a eboot.o eboot_command.o miniz.o
../../tools/xtensa-lx106-elf/bin/xtensa-lx106-elf-gcc -Teboot.ld -Wl,--gc-sections -nostdlib -Wl,--no-check-sections -umain eboot.a -o eboot.elf
earle@server:~/Arduino/hardware/esp8266com/esp8266/bootloaders/eboot$ objdump -t eboot.elf  | grep .text | sort -k1
4010f000 g       *ABS*	00000000 _text_start
4010f000 g       .text	00000000 _stext
4010f000 l    d  .text	00000000 .text
4010f010 g     F .text	00000079 print_version
4010f0a0 g     F .text	0000009b load_app_from_flash_raw
4010f168 g     F .text	00000114 copy_raw
4010f290 g     F .text	000000ea main
4010f380 g     F .text	00000038 crc_update
4010f3b8 g     F .text	00000019 eboot_command_calculate_crc32
4010f3e0 g     F .text	00000049 eboot_command_read
4010f430 g     F .text	00000014 eboot_command_clear
4010f4b8 g     F .text	0000129b tinfl_decompress
40110753 g       *ABS*	00000000 _text_end
40110753 g       .text	00000000 _etext
40110770 l     O .text	00000080 s_dist_base$2064
401107f0 l     O .text	00000080 s_dist_extra$2065
40110870 l     O .text	0000007c s_length_base$2062
401108ec l     O .text	0000007c s_length_extra$2063
40110968 l     O .text	00000013 s_length_dezigzag$2066
4011097c l     O .text	0000000c s_min_table_sizes$2067
40240000 g       *ABS*	00000000 _irom0_text_end
40240000 g       *ABS*	00000000 _irom0_text_start

[devyte]

@davisonja said:

That's a more comprehensive assessment. I commented out the compressor code and built it to get an absolute upper bound, which was about 15k (with eboot, but no optimisations). It seemed like a viable prospect even at that size.

[devyte]

@earlephilhower said:

For eboot, the makefile needs ti go from -O0 to -Os, since at 0 it won't even do simple optimizations.

Then, the problem is that minigz has compress and decompress in one file and the linker will include the entire file even if compression is unused (-flto doesn't work on GCC 4.8). So add in -f(data|function)-sections and -fgc-sections (check exact syntax in our platform.txt) and it'll finally drop the compression bits and you'll be left with the minimum needed.

Granted, I did not test the resulting ELF, just looked at sizes. The eboot.c might have some code that's busted in a way to require no optimization to work.

[devyte]

Alright, let's continue the compressed OTA discussion here.

[TD-er]

Is the typical gain in size comparable with the compression levels reported by the flash tool?

[earlephilhower]

Using the 5.5k miniz would give exactly the same compression as the uploader. The simpler RLE would give about 0 compression on binaries, but close to the same on sparse filesystems.

[davisonja]

While I've certainly encountered obscure optimisation issues with bootloaders in other places, it's been fairly irrelevant for eboot.
It's currently less than a single 4k page in size.

[davisonja]

Iirc lzw ends up being fairly small and does better than rle. It's been a while since I built it in C, tho.

With only a little thought we should be able to expose inflator code in eboot for use in main code meaning it would save additional space in images.

[d-a-v]

Very interesting, lzw

[TD-er]

Just a question/thought I have.
If the image can already be compressed significantly using run-length-encoding, can't the linker/compiler do something to create a smaller image which is still able to be executed by the ESP?
I understand offsets to functions and data have to be re-calculated, but what may be the reason it cannot be done at compile time? (just assuming it cannot be done, otherwise it has already been done, so what am I missing here :) )

Is it only RLE, or is it also using some very basic dictionary and thus able to compress English words/texts by a significant factor?

[earlephilhower]

@TD-er ... RLE + dictionary ~= LZW. :) I thought zlib was LZW, too, but maybe I'm thinking of original AT&T compress or something...

GNU LD or GCC are not going to do any kind of exe compression like that. The CPU already has variable-length instructions, helping minimize code size vs. a nice, clean, 32b insn word like in the Hennessy and Patterson everyone starts with.

There's really no runs of constant values in the executable portion of a binary, so RLE won't affect size there.

[TD-er]

What part of the binary is then compressed/compressible using RLE?
Thing is, I'm a bit amazed by the amount of compression achieved using just RLE.

[earlephilhower]

RLE will compress ~0% of the executable. On a 1MB filesystem with 100k of files, RLE will compress a heck of a lot.

zlib/miniz gives maybe 20-30% compression on the binaries, and great #s on a sparse FS (the long runs of 0s will give ~ same as RLE, while the data pages will get whatever miniz can do on them)

[TD-er]

But when I do an OTA of the sketch, I don't have the filesystem included, right?
0% compression on the executable is what I would expect. Maybe even slightly larger when attempted to compress using RLE.
So what is then being compressed using RLE that would allow for smaller space requirements for OTA and also done by esptool.py?