garymm / starflate

deflate on GPU

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

• Get SYCL building with bazel. Already have OpenSYCL building for CPU only here. Would be nicer to use intel's LLVM which supports lots of GPUs.
• (maybe?) Implement LZ77 with C++ std lib.
• Implement Deflate decompression with C++ std lib.
• Port Deflate to SYCL.
• Benchmark it on CPU.
• Build system work to get it to run on GPU.
• Benchmark it on GPU.

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

starflate's Issues

Allow use of arrow `operator->` on return value of `huffman::table::find`

Minimal reproducer of what I think is the issue: https://godbolt.org/z/3sEq5z4ro
ChatGPT's opinion:
https://chat.openai.com/share/b99fc143-1870-4f94-b604-2fd4c56e9c49

unrelated, but you should switch to `-fsanitize-link-c++-runtime`, as we found some issues with `--driver-mode=g++`. It also is much more obvious what the flag is supposed to do.

          unrelated, but you should switch to `-fsanitize-link-c++-runtime`, as we found some issues with `--driver-mode=g++`. It also is much more obvious what the flag is supposed to do.

Originally posted by @garymm in #54 (comment)

remove non-squash merge options for prs

we haven't been using rebase or merge commit so let's disable those options so we need to click less

rename project

gpu-deflate -> starflate

Will do it once there aren't any pending PRs.

change huffman::table to always be canonical

And optimize table::find to take advantage of that.

add constructor to huffman::table that takes symbols and bit lengths

As explained in RFC, consecutive symbols and their bit lengths are enough to construct a table in canonical form.

enhance bit_span for deflate decoding

• consume header
• read off extra bits in the order useful for decoding distances etc in RFC

I must have missed the notifications for this. I can try to write something that does this. It will speed up the debugging process which will we probably encounter again.

I must have missed the notifications for this. I can try to write something that does this. It will speed up the debugging process which will we probably encounter again.

Originally posted by @oliverlee in #83 (comment)