List of Asymmetric Numeral Systems implementations

2 Attachment(s)

Wikipedia article, benchmarks by Hamid Buzidi and by Przemysław Skibiński.
Video: basics by Feldhoffer Gergely, introduction by Ajay Sankalkar, Berkeley DL lecture by Pieter Abbeel: 2019, 2020, promotional animation by Jagiellonian Universiy
Materials by: Matt Mahoney (uABS), Andrew Polar (tANS), first of many posts by Yann Collet (tANS/FSE), gathered posts of Charles Bloom (tANS), first post of Fabian Giesen (rANS in practice), James K. Bonfield (rANS, page 20+), chapter of Colt McAnlis "Understanding compression" book (tANS), StackExchange, post by Roman Cheplyaka (Haskell), Juha Kärkkäinen slides from course at University of Helsinki, Moffat-Petri paper, post by Jeremy Gibbons (Haskell) and article, interactive post by Kedar Tatwawadi, posts by Andrey Smachev: tANS/FSE Rus/Eng, rANS Rus/Eng, ALICE LHC poster (Michael Lettirch), rANS tutorial by James Townsend, long post by Brian Keng (Python).
Some my materials: slides, preprint, PCS2015 paper, toolkit, simulator, video lecture, 2019 poster.

Compressors using ANS:
2013:
- zhuff (Dec 23, Yann Collet, LZ+tANS) - extremely fast: http://fastcompression.blogspot.com/p/zhuff.html
2014:
- lzturbo (Hamid Buzidi, LZ+tANS)- focused on speed in large range of compression levels: https://sites.google.com/site/powturbo/
- LZA (Nania Francesco, LZ+adaptive rANS) - quick decoding for great compression: http://encode.su/threads/1969-LZA-archiver
- lzmax (Przemysław Skibiński, tANS) - quick LZ + FSE: http://encode.su/threads/1845-Finite...ll=1#post41561
- CRAM 3.0 DNA compressor from SAMtools (Nov 24, James K. Bonfield, European Bioinformatics Institute, order 1 rANS): http://www.ebi.ac.uk/ena/software/cram-toolkit (benchmarks),
2015:
- Facebook Zstandard/ZSTD (Yann Collet et al., LZ + FSE/tANS) - gzip/zlib replacement (e.g. in the Guardian) with much better compression and speed: https://github.com/facebook/zstd, already used in many places beside Facebook like Linux kernel, Android, Instagram, Amazon Redshift, Apache Hadoop, standardization for MIME (email/html),
- Oodle LZNA (Charles Bloom, Fabian Giesen, RAD Game Tools, LZ+adaptive rANS) - http://cbloomrants.blogspot.com/2015...odle-lzna.html
- Apple LZFSE (Eric Bainville, Lempel-Ziv + Finite State Entropy, tANS) - https://github.com/lzfse/lzfse, thesis by Martin Hron
- Oodle BitKnit (Fabian Giesen, Charles Bloom, RAD Game Tools, LZ+adaptive rANS) - https://fgiesen.wordpress.com/2015/1...s-in-practice/
- (in development) Google VP10 video compressor (Alex Converse, rANS+uABS) - https://chromium-review.googlesource.com/#/c/318743
2016:
- experimental branch of Google WebP image compressor (Pascal Massimino, rANS+uABS) - https://chromium-review.googlesource.com/#/c/338781/
- XPACK (Eric Biggers, LZ77 + FSE/tANS): https://github.com/ebiggers/xpack
- (in development) AV1 video codec of Alliance for Open Media (Amazon, Cisco, Google, Intel, Microsoft, Mozilla, Netflix, AMD, ARM, NVIDIA) (Alex Converse, Pascal Massimino rANS+uABS): aomedia.googlesource.com/aom/+/master/aom_dsp/ans.h
- parallel ZSTD (Nick Terell) and Blosc ZSTD (Francesc Alted) - multithreading, cache optimizations, bithuffle filters : http://blosc.org/blog/zstd-has-just-...-in-blosc.html
- GST: GPU-decodable Supercompressed Textures (Pavel Krajcevski, Srihari Pratapa, Dinesh Manocha, rANS): http://gamma.cs.unc.edu/GST/
2017:
- Google Draco 3D geometric meshes and point clouds compression library (Ondrej Stava, Lou Quillo, rANS): https://github.com/google/draco
- Google PIK "lossy image format for the internet" (Jan Wassenberg, Zoltan Szabatka, rANS): https://github.com/google/pik
- RAZOR (Christian Martelock, adaptive rANS) - revolutionary super-strong LZ-based archiver (some details)
- lolz (adaptive rANS, LZNA derivative) used in game repacks (?): https://encode.su/threads/3281-copy-...ll=1#post62781
- pingo (Cédric Louvrier, tANS) fast webimage optimizer: https://css-ig.net/pingo
2018:
- Oodle Leviathan, Kraken, Mermaid (Charles Bloom, Fabian Giesen, selectively tANS): https://encode.su/threads/2078-List-...ll=1#post56059
- Dropbox DivANS (Daniel Reiter Horn, Jongmin Baek, adaptive rANS): https://blogs.dropbox.com/tech/2018/...r-with-divans/
- zchunk (Jonathan Dieter) - zstd based default compressor for Fedora 29+ : https://www.phoronix.com/scan.php?pa...etadata-Zchunk
- Google's image compression via triangulation (David Marwood, Pascal Massimino, Michele Covell, Shumeet Baluja): https://arxiv.org/pdf/1809.02257.pdf
- index compression
- Volumetric Approach to Point Cloud Compression (8i, rANS): https://arxiv.org/pdf/1810.00484.pdf
- Bits-back coding (image, variational autoencoder + LIFO ANS): https://openreview.net/pdf?id=ryE98iR5tm https://github.com/bits-back/bits-back
- M99 BWT compressor (Michael Maniscalco, experimental tANS): https://encode.su/threads/2801-M99?p...ll=1#post58582
2019:
- Google Brunsli JPEG repacker in JPEG XL (rANS): https://github.com/google/brunsli/
- JPEG XL (alias rANS): discussion, draft: https://arxiv.org/pdf/1908.03565, SPIE September 2019 paper, April 2020 benchmark paper, implementation: https://gitlab.com/wg1/jpeg-xl
- Bit-Swap coding (image, hierarchical variational autoencoder + LIFO ANS) extension of Bits-Back (ICML 2019):
https://arxiv.org/pdf/1905.06845 https://fhkingma.com/bitswap/bitswap.pdf https://bair.berkeley.edu/blog/2019/09/19/bit-swap/
- Integer Discrete Flows and Lossless Compression (image, rANS): https://arxiv.org/pdf/1905.07376
- Compression with Flows via Local Bits-Back Coding: https://arxiv.org/pdf/1905.08500
- NAF - Nucleotide Archival Format (preprocessor + zstd): https://www.ncbi.nlm.nih.gov/pubmed/30799504
- Scientific dataset compression (preprocessor + zstd): https://www.geosci-model-dev.net/12/...-4099-2019.pdf
- Tampering-resistant image compression (FSE/tANS): https://openreview.net/pdf?id=HyxG3p4twS
- electrocardiogram (ECG) data: https://www.sciencedirect.com/scienc...46809419302861
- video compression wavelets (tANS): https://link.springer.com/chapter/10...030-36614-8_10
- hierarchical latent variable models (LIFO ANS): https://openreview.net/forum?id=r1lZgyBYwS
- Google WebP v2 image compressor (adaptive rANS): https://youtu.be/zogxpP2lm-o?t=411 https://chromium.googlesource.com/codecs/libwebp2/
2020:
- Oodle Kraken (tANS) hardware decoder in Sony PlayStation 5: https://www.eurogamer.net/articles/d...ext-gen-vision
- Improving Integer Discrete Flows (rANS, Google): https://arxiv.org/pdf/2006.12459
- CSPRNG using rANS, tANS: https://github.com/REgonLevy/shady-crypt
- NLZM (LZMA-style compressor with nibbled rANS and optimal parsing): https://github.com/nauful/NLZM
- Inpainting-based Video Compression in FullHD (tANS in FSE): https://arxiv.org/pdf/2008.10273
- Zuckerli - compression format and data structures for large graphs (rANS, Google): https://github.com/google/zuckerli https://arxiv.org/pdf/2009.01353
- learned video codec (rANS): https://arxiv.org/pdf/2012.07462
2021:
- Learning Non-linear Wavelet Transformation via Normalizing Flow (rANS): https://arxiv.org/pdf/2101.11306 https://github.com/li012589/NeuralWavelet
- Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding (rANS): https://arxiv.org/pdf/2102.11086

Implementations:
2007:
- Matt Mahoney - fpaqa, fpaqb (tabled uABS), fpaqc (uABS): http://mattmahoney.net/dc/dce.html#Section_33 ,
2008:
- Andrew Polar - tANS: http://www.ezcodesample.com/abs/abs_article.html
2013:
- Yann Collet - Finite State Entropy (FSE) - fast implementation of tANS (introducing fast symbol spread): https://github.com/Cyan4973/FiniteStateEntropy
2014:
- Fabian Giesen - rANS - introducing interleaving, SIMD variants, alias method: https://github.com/rygorous/ryg_rans
- Charles Bloom - rANS/tANS: http://cbloomrants.blogspot.com/2014...ion-notes.html
- Hamid Buzidi - turboANS (tANS) - extraordinary claims but no confirmation (closed source), used in lzturbo compressor: https://sites.google.com/site/powturbo/
- Pascal Massimino - FSC - rANS/tANS (also alias method): https://github.com/skal65535/fsc
- James K. Bonfield - ultra fast, order1 rANS: https://github.com/jkbonfield/rans_static
- Fredric Langlet - java implementation of rANS (kanzi library): https://code.google.com/p/kanzi/sour...kanzi/entropy/
- Nania Francesco - adaptive rANS: http://encode.su/threads/2079-nARANS...iant-of-ANS%29
2018: BareRose nibble adaptive rANS: https://github.com/BareRose/nibrans discussion: https://encode.su/threads/3073-BareRose-nibrans
2019: Massively Parallel ANS Decoding on GPUs ( https://dl.acm.org/citation.cfm?id=3337888 ): https://github.com/weissenberger/multians
- C64 demo rABS: https://yupferris.github.io/blog/201...S-on-6502.html https://youtu.be/-lJDJgBaOAw

Also: approximations of ANS (implementation of nburns), uABS/rABS discussion, Google video codec discussion (FSC), SIMD rANS implementations, fighting patent for basic ANS applications (PAP, bleepingcomputer, Arstechnica), lightweight compression+encryption with ANS.

Jarek,

One more implementation in Java and one in Go here: https://code.google.com/p/kanzi or, for the cool kids, on Github here: https://github.com/flanglet/kanzi
Code is here https://code.google.com/p/kanzi/sour...geEncoder.java and here https://code.google.com/p/kanzi/sour...SRangeCodec.go.
ANS is one of the algorithms implemented for the entropy coding part of the block compressor.
One can see the similarities in the code of the ANSRangeCoder and a classic RangeCoder: the 2 implementations are very much alike.

I guess the mini one I posted here doesn't count... :)

Let's put a bit of order here! :_good2:Well done.

Edit: Thanks for the clarification.

-----------------------------------

Thanks hexagone - added.
nburns, ok let's add also some additional sources to the first post, but only really interesting ones.
Gonzalo, "Polar Code" is prefix code not ANS.

Quote:

Originally Posted by Jarek

Thanks hexagone - added.
nburns, ok let's add also some additional sources to the first post, but only really interesting ones.

Gotcha. :_shame2:

J/k. I really didn't spend that much time on it, but someone might find it interesting, as the only (known) implementation of that particular variant of ANS.

I was wondering if it is possible to apply also rANS algorithms to guess the bit compression (like fpaq and not fpaqA) and whether it is necessary to encode at the back even the bits!

Nania, please use a different thread for such a question - I will reply here: http://encode.su/threads/1821-Asymet...l-System/page7

Has anyone else ever dreamed of a compression wiki as a place to put stuff like this?

Quote:

Originally Posted by nburns

Has anyone else ever dreamed of a compression wiki as a place to put stuff like this?

YESSSS!!! You've read my mind.

Charles and Fabian advertise their new LZNA compressor (LZ-nibbled-ANS, rANS) as much faster decompressing and usually having better compression ratio than LZMA:
http://cbloomrants.blogspot.com/2015...odle-lzna.html
https://fgiesen.wordpress.com/2015/0...distributions/
https://fgiesen.wordpress.com/2015/0...hmetic-coding/
Have anybody seen some independent tests?

Interesting paper about texture decompression (GST) with vectorized rANS on GPU: "GST: GPU-decodable Supercompressed Textures"
http://gamma.cs.unc.edu/GST/gst.pdf

Code:

Format JPEG PNG DXT1 Crunch GST Time (ms) 848.6 1190.2 85.8 242.3 93.4 Disk size (MB) 6.46 58.7 16.8 8.50 8.91 CPU size (MB) 100 100 16.8 16.8 8.91

github: https://github.com/GammaUNC/GST

I have ported FSE as used in zstd to Go: https://github.com/klauspost/compress/tree/master/fse

Speed is close enough to the c reference (~30% slower) considering there are some forced bound checks and memory can't be aliased to different types. It was a fun learning experience - now I think I finally "get it" :)

Oodle 2.6.0 adds a tANS implementation as an entropy coding option for Leviathan (new codec), Kraken and Mermaid, as one of the new features in Oodle v6 bitstreams. Whether it's used or not depends on a space/speed tradeoff decision: our fast tANS decoder is slower than our fast Huffman decoders, and the tANS count transmission is somewhat more expensive than Huffman code length transmission, so tANS only gets chosen when it saves enough bits and the somewhat slower decode rate is acceptable for the chosen space/speed target. In practice, Leviathan (targeting higher ratio) picks tANS a lot (around 50% of the time), Kraken rarely, Mermaid very rarely.

Our tANS count transmission is an offshoot of our Huffman code length coder, and we use a novel (as far as we can tell) table initialization algorithm to speed up setup. This was an issue because we don't generally use any given table very long. Our new method is slightly coarser than e.g. FSE's method but was significantly faster in our tests, enough so to be easily worth the slight loss in ratio.