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
    737
    Thanks
    230
    Thanked 233 Times in 143 Posts

    List of Asymmetric Numeral Systems implementations

    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, 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.
    Some my materials: slides, preprint, PCS2015 paper, toolkit, simulator, lecture (Polish), 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
    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 in progress (ANS+AC): discussion, draft: https://arxiv.org/pdf/1908.03565, SPIE September paper 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


    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

    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:	1545 
Size:	116.7 KB 
ID:	3319   Click image for larger version. 

Name:	ANSexample.png 
Views:	833 
Size:	117.0 KB 
ID:	3322  
    Last edited by Jarek; 9th February 2020 at 15:35. Reason: WebP v2

  2. Thanks (19):

    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
    143
    Thanks
    46
    Thanked 40 Times in 29 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. Thanks:

    Jarek (13th November 2014)

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

  6. #4
    Member
    Join Date
    Aug 2014
    Location
    Argentina
    Posts
    536
    Thanks
    236
    Thanked 90 Times in 70 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
    737
    Thanks
    230
    Thanked 233 Times in 143 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 72 Times in 56 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. Thanks:

    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
    737
    Thanks
    230
    Thanked 233 Times in 143 Posts
    Nania, please use a different thread for such a question - I will reply here: http://encode.su/threads/1821-Asymet...l-System/page7

  12. #9
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 72 Times in 56 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
    536
    Thanks
    236
    Thanked 90 Times in 70 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
    737
    Thanks
    230
    Thanked 233 Times in 143 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. Thanks:

    Bulat Ziganshin (26th May 2015)

  16. #12
    Member
    Join Date
    Nov 2013
    Location
    Kraków, Poland
    Posts
    737
    Thanks
    230
    Thanked 233 Times in 143 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 10:14.

  17. Thanks:

    Bulat Ziganshin (1st March 2018)

  18. #13
    Member
    Join Date
    Apr 2012
    Location
    Denmark
    Posts
    65
    Thanks
    21
    Thanked 17 Times in 15 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. Thanks (3):

    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. Thanks (5):

    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, 17:11
  4. DEFLATE/zlib implementations
    By GerryB in forum Data Compression
    Replies: 10
    Last Post: 7th May 2009, 18:03
  5. Memory Limits for Windows Operating Systems
    By LovePimple in forum The Off-Topic Lounge
    Replies: 1
    Last Post: 13th July 2008, 00: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
  •