2/18/2014

02-18-14 - Understanding ANS - Conclusion

I think we can finally say that we understand ANS pretty well, so this series will end. I may cover some more ANS topics but they won't be "Understanding ANS".

Here is the index of all posts on this topic :

cbloom rants 1-30-14 - Understanding ANS - 1
cbloom rants 1-31-14 - Understanding ANS - 2
cbloom rants 02-01-14 - Understanding ANS - 3
cbloom rants 02-02-14 - Understanding ANS - 4
cbloom rants 02-03-14 - Understanding ANS - 5
cbloom rants 02-04-14 - Understanding ANS - 6
cbloom rants 02-05-14 - Understanding ANS - 7
cbloom rants 02-06-14 - Understanding ANS - 8
cbloom rants 02-10-14 - Understanding ANS - 9
cbloom rants 02-11-14 - Understanding ANS - 10
cbloom rants 02-14-14 - Understanding ANS - 11
cbloom rants 02-18-14 - Understanding ANS - 12

And here is some source code for my ANS implementation : (v2 02/21/2014)

ans_learning.cpp
ans_fast.cpp
ans.zip - contains ans_fast and ans_learning
cblib.zip is required to build my code

My home code is MSVC 2005/2008. Port if you like. Email me if you need help.

NOTE : this release is not a library you just download and use. It is intended as documentation of research. If you want some ANS code you can just use off the shelf, go get FiniteStateEntropy . You may also want ryg_rans .

I think I'll do a followup post with the performance of ans_fast and some optimization notes so it doesn't crud up this index post. Please put implementation speed discussion in that followup post .

3 comments:

Yann Collet said...

I've tried to compile your project, but so far no luck. GCC complains about a missing crtdef.h, so I believe it means it must be compiled using MSVC.

But MSVC has problem too. I'm using VS 2012 express. Here is the "debug" output ("release" is a lot more worse)

1>------ Début de la génération : Projet : ans, Configuration : Debug x64 ------
1> ans_fast.cpp
1>C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\include\xtgmath.h(86): error C2244: 'cb::acos_asserting' : impossible de faire correspondre la définition de fonction avec une déclaration existante
1> c:\my program files\dev\compression\entropy\bloom\ans\cblib/FloatUtil.h(964) : voir la déclaration de 'cb::acos_asserting'
1>C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\include\xtgmath.h(87): error C2244: 'cb::asin_asserting' : impossible de faire correspondre la définition de fonction avec une déclaration existante
1> c:\my program files\dev\compression\entropy\bloom\ans\cblib/FloatUtil.h(963) : voir la déclaration de 'cb::asin_asserting'
1>C:\Program Files (x86)\Microsoft Visual Studio 11.0\VC\include\xtgmath.h(105): error C2244: 'cb::sqrt_asserting' : impossible de faire correspondre la définition de fonction avec une déclaration existante
1> c:\my program files\dev\compression\entropy\bloom\ans\cblib/FloatUtil.h(962) : voir la déclaration de 'cb::sqrt_asserting'
========== Génération : 0 a réussi, 1 a échoué, 0 mis à jour, 0 a été ignoré ==========

Yann Collet said...

Is there any chance to have or build a "reduced dependency" version of fast ANS ?

I'm trying to get your code included into an open source portable program, but the amount of dependency with cblib is quite deep (and afaik cblib is only for Windows).

cbloom said...

I'd love to do nice open source versions of lots of stuff. (LZ-ANS anyone?) But I just don't have free time and noone is paying me to do it.

I think it should be pretty easy though. I would just take the core functions and only port those. (you don't need string or fileenum)

vector_s can be replaced with just a C array and a 'size' variable.

cb::sum is trivial

check_value_cast can be replaced with static_cast

You have to use STL or write a heap.

etc.

old rants