git.sesse.net Git - narabu/blob - ryg_rans/README

   1 This is a public-domain implementation of several rANS variants. rANS is an
   2 entropy coder from the ANS family, as described in Jarek Duda's paper
   3 "Asymmetric numeral systems" (http://arxiv.org/abs/1311.2540).
   4
   5 - "rans_byte.h" has a byte-aligned rANS encoder/decoder and some comments on
   6   how to use it. This implementation should work on all 32-bit architectures.
   7   "main.cpp" is an example program that shows how to use it.
   8 - "rans64.h" is a 64-bit version that emits entire 32-bit words at a time. It
   9   is (usually) a good deal faster than rans_byte on 64-bit architectures, and
  10   also makes for a very precise arithmetic coder (i.e. it gets quite close
  11   to entropy). The trade-off is that this version will be slower on 32-bit
  12   machines, and the output bitstream is not endian-neutral. "main64.cpp" is
  13   the corresponding example.
  14 - "rans_word_sse41.h" has a SIMD decoder (SSE 4.1 to be precise) that does IO
  15   in units of 16-bit words. It has less precision than either rans_byte or
  16   rans64 (meaning that it doesn't get as close to entropy) and requires
  17   at least 4 independent streams of data to be useful; however, it is also a
  18   good deal faster. "main_simd.cpp" shows how to use it.
  19
  20 See my blog http://fgiesen.wordpress.com/ for some notes on the design.
  21
  22 I've also written a paper on interleaving output streams from multiple entropy
  23 coders:
  24
  25   http://arxiv.org/abs/1402.3392
  26
  27 this documents the underlying design for "rans_word_sse41", and also shows how
  28 the same approach generalizes to e.g. GPU implementations, provided there are
  29 enough independent contexts coded at the same time to fill up a warp/wavefront
  30 or whatever your favorite GPU's terminology for its native SIMD width is.
  31
  32 Finally, there's also "main_alias.cpp", which shows how to combine rANS with
  33 the alias method to get O(1) symbol lookup with table size proportional to the
  34 number of symbols. I presented an overview of the underlying idea here:
  35
  36   http://fgiesen.wordpress.com/2014/02/18/rans-with-static-probability-distributions/
  37
  38 Results on my machine (Sandy Bridge i7-2600K) with rans_byte in 64-bit mode:
  39
  40 ----
  41
  42 rANS encode:
  43 12896496 clocks, 16.8 clocks/symbol (192.8MiB/s)
  44 12486912 clocks, 16.2 clocks/symbol (199.2MiB/s)
  45 12511975 clocks, 16.3 clocks/symbol (198.8MiB/s)
  46 12660765 clocks, 16.5 clocks/symbol (196.4MiB/s)
  47 12550285 clocks, 16.3 clocks/symbol (198.2MiB/s)
  48 rANS: 435113 bytes
  49 17023550 clocks, 22.1 clocks/symbol (146.1MiB/s)
  50 18081509 clocks, 23.5 clocks/symbol (137.5MiB/s)
  51 16901632 clocks, 22.0 clocks/symbol (147.1MiB/s)
  52 17166188 clocks, 22.3 clocks/symbol (144.9MiB/s)
  53 17235859 clocks, 22.4 clocks/symbol (144.3MiB/s)
  54 decode ok!
  55
  56 interleaved rANS encode:
  57 9618004 clocks, 12.5 clocks/symbol (258.6MiB/s)
  58 9488277 clocks, 12.3 clocks/symbol (262.1MiB/s)
  59 9460194 clocks, 12.3 clocks/symbol (262.9MiB/s)
  60 9582025 clocks, 12.5 clocks/symbol (259.5MiB/s)
  61 9332017 clocks, 12.1 clocks/symbol (266.5MiB/s)
  62 interleaved rANS: 435117 bytes
  63 10687601 clocks, 13.9 clocks/symbol (232.7MB/s)
  64 10637918 clocks, 13.8 clocks/symbol (233.8MB/s)
  65 10909652 clocks, 14.2 clocks/symbol (227.9MB/s)
  66 10947637 clocks, 14.2 clocks/symbol (227.2MB/s)
  67 10529464 clocks, 13.7 clocks/symbol (236.2MB/s)
  68 decode ok!
  69
  70 ----
  71
  72 And here's rans64 in 64-bit mode:
  73
  74 ----
  75
  76 rANS encode:
  77 10256075 clocks, 13.3 clocks/symbol (242.3MiB/s)
  78 10620132 clocks, 13.8 clocks/symbol (234.1MiB/s)
  79 10043080 clocks, 13.1 clocks/symbol (247.6MiB/s)
  80 9878205 clocks, 12.8 clocks/symbol (251.8MiB/s)
  81 10122645 clocks, 13.2 clocks/symbol (245.7MiB/s)
  82 rANS: 435116 bytes
  83 14244155 clocks, 18.5 clocks/symbol (174.6MiB/s)
  84 15072524 clocks, 19.6 clocks/symbol (165.0MiB/s)
  85 14787604 clocks, 19.2 clocks/symbol (168.2MiB/s)
  86 14736556 clocks, 19.2 clocks/symbol (168.8MiB/s)
  87 14686129 clocks, 19.1 clocks/symbol (169.3MiB/s)
  88 decode ok!
  89
  90 interleaved rANS encode:
  91 7691159 clocks, 10.0 clocks/symbol (323.3MiB/s)
  92 7182692 clocks, 9.3 clocks/symbol (346.2MiB/s)
  93 7060804 clocks, 9.2 clocks/symbol (352.2MiB/s)
  94 6949201 clocks, 9.0 clocks/symbol (357.9MiB/s)
  95 6876415 clocks, 8.9 clocks/symbol (361.6MiB/s)
  96 interleaved rANS: 435120 bytes
  97 8133574 clocks, 10.6 clocks/symbol (305.7MB/s)
  98 8631618 clocks, 11.2 clocks/symbol (288.1MB/s)
  99 8643790 clocks, 11.2 clocks/symbol (287.7MB/s)
 100 8449364 clocks, 11.0 clocks/symbol (294.3MB/s)
 101 8331444 clocks, 10.8 clocks/symbol (298.5MB/s)
 102 decode ok!
 103
 104 ----
 105
 106 Finally, here's the rans_word_sse41 decoder on an 8-way interleaved stream:
 107
 108 ----
 109
 110 SIMD rANS: 435626 bytes
 111 4597641 clocks, 6.0 clocks/symbol (540.8MB/s)
 112 4514356 clocks, 5.9 clocks/symbol (550.8MB/s)
 113 4780918 clocks, 6.2 clocks/symbol (520.1MB/s)
 114 4532913 clocks, 5.9 clocks/symbol (548.5MB/s)
 115 4554527 clocks, 5.9 clocks/symbol (545.9MB/s)
 116 decode ok!
 117
 118 ----
 119
 120 There's also an experimental 16-way interleaved AVX2 version that hits
 121 faster rates still, developed by my colleague Won Chun; I will post it
 122 soon.
 123
 124 Note that this is running "book1" which is a relatively short test, and
 125 the measurement setup is not great, so take the results with a grain
 126 of salt.
 127
 128 -Fabian "ryg" Giesen, Feb 2014.