https://github.com/pfalcon/uzlib is highly optimized, minimal library (based on the earlier tinf library), which works with the standard DEFLATE/zlib/gzip compression. It can work in both memory buffer and streaming mode for decompression (in the latter case it can process files of unlimited size). For compression, it implements a simpler compression algorithm, but still formats result as a zlib compatible bitstream, so any other software can decompress it.
The library wouldn't have any problems running on Cortex-M0 (depending on dictionary size used, for small-RAM systems, values less than default 32KB should be used).
It's used in MicroPython https://github.com/pfalcon/micropython , where with ~40KB of free RAM, an application written in Python can download tarballs over TLS connection and decompress them into the filesystem (the "upip" package manager).