starflate

Deflate on various hardware platforms

Set up

Should work on Linux and MacOS.

• Install bazel or bazelisk

• Verify that you can build and test:

bazel test //...

VS Code

Install the recommended extensions. See .vscode/extensions.json.

Auto-completion

Create a compilation database:

bazel build //... && bazel run @hedron_compile_commands//:refresh_all && bazel build //...

Then configure clangd. If you're using VS Code, the .vscode/settings does this for you, and .vscode/extensions.json already recommends installing the clangd extension.

Otherwise, copy the clangd args from the .vscode/settings.json.

Status

Done

• Build Huffman code tables from given symbol frequencies.
• Huffman decoding with C++ std lib.

TODO

Basic

• Implement Deflate decompression with C++ std lib.
• Benchmark it on CPU.
• Build system work to get it to run on GPU.
• Port Deflate to GPU.
• Benchmark it on GPU.

Nice to have

• Support chunked output. Started in 2e6a83d622e , but removed because it was adding too much complexity and I wanted to focus on getting the basics working.

References

• DEFLATE Compressed Data Format Specification version 1.3
• Simple-DEFLATE-decompressor
• pyflate
• An Explanation of the Deflate Algorithm
• Parallel lossless compression using GPUs
• GPU implementations of deflate encoding and decoding