Results 1 to 14 of 14

Thread: List of Asymmetric Numeral Systems implementations

  1. #1
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts

    List of Asymmetric Numeral Systems implementations

    Wikipedia article, benchmarks by Hamid Buzidi and by Przemysław Skibiński.
    Video: basics by Feldhoffer Gergely, Berkeley DL lecture by Pieter Abbeel.
    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.
    Some my materials: slides, preprint, PCS2015 paper, toolkit, simulator, lecture (Polish).

    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.ru/threads/1969-LZA-archiver
    - lzmax (Przemysław Skibiński, tANS) - quick LZ + FSE: http://encode.ru/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),
    - CRAM 3.0 DNA compressor from SAMtools (James K. Bonfield, European Bioinformatics Institute, order 1 rANS): http://www.ebi.ac.uk/ena/software/cram-toolkit (benchmarks),
    - 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 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
    2018:
    - Oodle Leviathan, Kraken, Mermaid (Charles Bloom, Fabian Giesen, selectively tANS): https://encode.ru/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.ru/threads/2801-M99?p...ll=1#post58582
    2019:
    - Google Brunsli
    JPEG repacker (rANS): https://github.com/google/brunsli/
    - JPEG XL in progress (ANS+AC): https://encode.ru/threads/3108-Googl...ll=1#post60072
    - Bit-Swap coding (image, hierarchical variational autoencoder + LIFO ANS) extension of Bits-Back (ICML 2019):
    https://arxiv.org/pdf/1905.06845 https://github.com/fhkingma/bitswap
    - 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

    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.ru/threads/2079-nARANS...iant-of-ANS%29
    2018: BareRose nibble adaptive rANS: https://github.com/BareRose/nibrans discussion: https://encode.ru/threads/3073-BareRose-nibrans
    2019: Massively Parallel ANS Decoding on GPUs ( https://dl.acm.org/citation.cfm?id=3337888 ): https://github.com/weissenberger/multians

    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.
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	ANSexample.png 
Views:	1470 
Size:	116.7 KB 
ID:	3319   Click image for larger version. 

Name:	ANSexample.png 
Views:	781 
Size:	117.0 KB 
ID:	3322  
    Last edited by Jarek; 30th July 2019 at 15:00. Reason: Berkeley video lecture

  2. The Following 19 Users Say Thank You to Jarek For This Useful Post:

    Bulat Ziganshin (12th November 2014),Christian (16th September 2017),compgt (15th September 2018),Cyan (4th August 2015),Darek (24th December 2016),encode (19th November 2016),Gonzalo (13th November 2014),lorents17 (14th August 2016),Matt Mahoney (12th November 2014),Mike (12th November 2014),myles (23rd May 2017),Nania Francesco (13th November 2014),nburns (13th November 2014),PAQer (16th December 2014),Razor12911 (7th October 2016),schnaader (13th April 2017),Turtle (15th January 2016),VadimV (13th November 2014),_Bluesman_ (8th December 2017)

  3. #2
    Member
    Join Date
    Nov 2014
    Location
    California
    Posts
    122
    Thanks
    36
    Thanked 33 Times in 24 Posts
    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.

  4. The Following User Says Thank You to hexagone For This Useful Post:

    Jarek (13th November 2014)

  5. #3
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    I guess the mini one I posted here doesn't count...

  6. #4
    Member
    Join Date
    Aug 2014
    Location
    Argentina
    Posts
    464
    Thanks
    202
    Thanked 81 Times in 61 Posts
    Let's put a bit of order here! Well done.

    Edit: Thanks for the clarification.


    -----------------------------------
    Last edited by Gonzalo; 13th November 2014 at 03:11. Reason: Previous post erroneous.

  7. #5
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    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.

  8. #6
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    Quote Originally Posted by Jarek View Post
    Thanks hexagone - added.
    nburns, ok let's add also some additional sources to the first post, but only really interesting ones.
    Gotcha.

    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.
    Last edited by nburns; 13th November 2014 at 08:40.

  9. The Following User Says Thank You to nburns For This Useful Post:

    Jarek (13th November 2014)

  10. #7
    Tester
    Nania Francesco's Avatar
    Join Date
    May 2008
    Location
    Italy
    Posts
    1,565
    Thanks
    220
    Thanked 146 Times in 83 Posts
    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!

  11. #8
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    Nania, please use a different thread for such a question - I will reply here: http://encode.ru/threads/1821-Asymet...l-System/page7

  12. #9
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    Has anyone else ever dreamed of a compression wiki as a place to put stuff like this?

  13. #10
    Member
    Join Date
    Aug 2014
    Location
    Argentina
    Posts
    464
    Thanks
    202
    Thanked 81 Times in 61 Posts
    Quote Originally Posted by nburns View Post
    Has anyone else ever dreamed of a compression wiki as a place to put stuff like this?
    YESSSS!!! You've read my mind.

  14. #11
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    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?

  15. The Following User Says Thank You to Jarek For This Useful Post:

    Bulat Ziganshin (26th May 2015)

  16. #12
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    645
    Thanks
    205
    Thanked 196 Times in 119 Posts
    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
    Last edited by Jarek; 5th November 2016 at 09:14.

  17. The Following User Says Thank You to Jarek For This Useful Post:

    Bulat Ziganshin (1st March 2018)

  18. #13
    Member
    Join Date
    Apr 2012
    Location
    Denmark
    Posts
    65
    Thanks
    21
    Thanked 16 Times in 14 Posts
    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"

  19. The Following 3 Users Say Thank You to sh0dan For This Useful Post:

    Cyan (6th February 2018),JamesB (5th February 2018),Jarek (5th February 2018)

  20. #14
    Member
    Join Date
    Dec 2015
    Location
    US
    Posts
    57
    Thanks
    2
    Thanked 112 Times in 36 Posts
    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.

  21. The Following 5 Users Say Thank You to fgiesen For This Useful Post:

    Bulat Ziganshin (1st March 2018),Cyan (20th May 2018),encode (5th May 2018),JamesB (2nd March 2018),Jarek (1st March 2018)

Similar Threads

  1. Asymetric Numeral System
    By Cyan in forum Data Compression
    Replies: 243
    Last Post: 15th November 2017, 15:17
  2. Replies: 32
    Last Post: 8th January 2016, 10:47
  3. list of different jpeg encoders?
    By Mangix in forum Data Compression
    Replies: 4
    Last Post: 21st October 2013, 16:11
  4. DEFLATE/zlib implementations
    By GerryB in forum Data Compression
    Replies: 10
    Last Post: 7th May 2009, 17:03
  5. Memory Limits for Windows Operating Systems
    By LovePimple in forum The Off-Topic Lounge
    Replies: 1
    Last Post: 12th July 2008, 23:40

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •