Advertisement
dan-masek

Draft of using FastAC to code -256 .. 255 with Laplace dist.

Feb 14th, 2018
275
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Using FastAC by Amir Said -- http://www.cipr.rpi.edu/research/SPIHT/EW_Code/FastAC.zip
  2. #include "arithmetic_codec.h"
  3.  
  4. #include <boost/random/mersenne_twister.hpp>
  5. #include <boost/random/laplace_distribution.hpp>
  6.  
  7. #include <vector>
  8.  
  9. std::size_t const N_VAL(1 << 20);
  10.  
  11. // ============================================================================
  12. // Generate some random data with distribution similar to what's in the question
  13.  
  14. std::vector<int32_t> gen_data(std::size_t n)
  15. {
  16.     boost::random::mt19937 rng;
  17.     boost::random::laplace_distribution<> dist(0, 20);
  18.  
  19.     std::vector<int32_t> data;
  20.     data.reserve(n);
  21.  
  22.     for (; data.size() < n;) {
  23.         int32_t v = static_cast<int32_t>(std::round(dist(rng)));
  24.         if ((v >= -256) && (v <= 255)) {
  25.             data.push_back(v);
  26.         }
  27.     }
  28.  
  29.     return data;
  30. }
  31.  
  32. // ============================================================================
  33. // Ziz-Zag Coding
  34. //
  35. // Maps signed integers into unsigned integers
  36. // 0 => 0, -1 => 1, 1 => 2, -2 => 3, 2 => 4 ...
  37.  
  38. uint32_t zigzag_encode(int32_t v)
  39. {
  40.     return static_cast<uint32_t>((v >> 31) ^ (v << 1));
  41. }
  42.  
  43. std::vector<uint32_t> zigzag_encode(std::vector<int32_t> const& data)
  44. {
  45.     std::vector<uint32_t> result(data.size());
  46.     std::transform(data.begin(), data.end(), result.begin(),
  47.         [](int32_t v) -> uint32_t { return zigzag_encode(v); });
  48.     return result;
  49. }
  50.  
  51. int32_t zigzag_decode(uint32_t v)
  52. {
  53.     return (static_cast<int32_t>(v) >> 1) ^ -(static_cast<int32_t>(v)& 1);
  54. }
  55.  
  56. std::vector<int32_t> zigzag_decode(std::vector<uint32_t> const& data)
  57. {
  58.     std::vector<int32_t> result(data.size());
  59.     std::transform(data.begin(), data.end(), result.begin(),
  60.         [](uint32_t v) -> int32_t { return zigzag_decode(v); });
  61.     return result;
  62. }
  63.  
  64. // ============================================================================
  65. // Simple approach with 1 adaptive model for 512 symbols
  66. // Processes zig-zag coded 9-bit values
  67.  
  68. template<typename ModelT, typename CodecT = Arithmetic_Codec>
  69. uint32_t encode(std::vector<uint32_t> const& buffer
  70.     , ModelT& model
  71.     , CodecT& encoder)
  72. {
  73.     encoder.start_encoder();
  74.     for (uint32_t v : buffer) {
  75.         encoder.encode(v, model);
  76.     }
  77.     return 8 * encoder.stop_encoder();
  78. }
  79.  
  80. template<typename ModelT, typename CodecT = Arithmetic_Codec>
  81. void decode(std::vector<uint32_t>& buffer
  82.     , ModelT& model
  83.     , CodecT& decoder)
  84. {
  85.     decoder.start_decoder();
  86.     for (uint32_t i(0); i < buffer.size(); ++i) {
  87.         buffer[i] = decoder.decode(model);
  88.     }
  89.     decoder.stop_decoder();
  90. }
  91.  
  92. void test_simple(std::vector<uint32_t> const& zdata)
  93. {
  94.     Arithmetic_Codec codec(N_VAL * 2);
  95.     Adaptive_Data_Model adaptive_model(512);
  96.  
  97.     std::size_t raw_size_bits(N_VAL * 9);
  98.     std::size_t packed_size_bits(encode(zdata, adaptive_model, codec));
  99.     double ratio(double(packed_size_bits) / raw_size_bits * 100);
  100.     std::cout << "Ratio = " << ratio << " %\n";
  101.  
  102.     std::vector<uint32_t> dzdata(N_VAL);
  103.  
  104.     adaptive_model.reset();
  105.  
  106.     decode(dzdata, adaptive_model, codec);
  107.  
  108.     std::cout << "Match = " << ((zdata == dzdata) ? "true" : "false") << "\n";
  109. }
  110.  
  111. // ============================================================================
  112. // Split approach with 3 adaptive models (1*2 and 2*256 symbols)
  113. // Processes zig-zag coded 9-bit values
  114. //
  115. // First the MSB is coded using the 2 symbol model_msb
  116. // If MSB == 0 then LSB is coded using the 256 symbold model_lsb0
  117. // If MSB == 1 then LSB is coded using the 256 symbold model_lsb1
  118.  
  119. template<typename ModelT, typename CodecT = Arithmetic_Codec>
  120. uint32_t encode(std::vector<uint32_t> const& buffer
  121.     , ModelT& model_msb
  122.     , ModelT& model_lsb0
  123.     , ModelT& model_lsb1
  124.     , CodecT& encoder)
  125. {
  126.     encoder.start_encoder();
  127.     for (uint32_t v : buffer) {
  128.         uint32_t msb(v >> 8);
  129.         uint32_t lsb(v & 0xFF);
  130.  
  131.         encoder.encode(msb, model_msb);
  132.         if (msb == 0) {
  133.             encoder.encode(lsb, model_lsb0);
  134.         } else {
  135.             encoder.encode(lsb, model_lsb1);
  136.         }
  137.     }
  138.     return 8 * encoder.stop_encoder();
  139. }
  140.  
  141. template<typename ModelT, typename CodecT = Arithmetic_Codec>
  142. void decode(std::vector<uint32_t>& buffer
  143.     , ModelT& model_msb
  144.     , ModelT& model_lsb0
  145.     , ModelT& model_lsb1
  146.     , CodecT& decoder)
  147. {
  148.     decoder.start_decoder();
  149.     for (uint32_t i(0); i < buffer.size(); ++i) {
  150.         uint32_t msb(decoder.decode(model_msb));
  151.         uint32_t lsb;
  152.         if (msb == 0) {
  153.             lsb = decoder.decode(model_lsb0);
  154.         } else {
  155.             lsb = decoder.decode(model_lsb1);
  156.         }
  157.         buffer[i] = (msb << 8) | lsb;
  158.     }
  159.     decoder.stop_decoder();
  160. }
  161.  
  162. void test_split(std::vector<uint32_t> const& zdata)
  163. {
  164.  
  165.     Arithmetic_Codec codec(N_VAL * 2);
  166.     Adaptive_Data_Model adaptive_model_msb(2);
  167.     Adaptive_Data_Model adaptive_model_lsb0(256);
  168.     Adaptive_Data_Model adaptive_model_lsb1(256);
  169.  
  170.     std::size_t raw_size_bits(N_VAL * 9);
  171.     std::size_t packed_size_bits(encode(zdata, adaptive_model_msb
  172.         , adaptive_model_lsb0, adaptive_model_lsb1, codec));
  173.     double ratio(double(packed_size_bits) / raw_size_bits * 100);
  174.     std::cout << "Ratio = " << ratio << " %\n";
  175.  
  176.     std::vector<uint32_t> dzdata(N_VAL);
  177.  
  178.     adaptive_model_msb.reset();
  179.     adaptive_model_lsb0.reset();
  180.     adaptive_model_lsb1.reset();
  181.  
  182.     decode(dzdata, adaptive_model_msb
  183.         , adaptive_model_lsb0, adaptive_model_lsb1, codec);
  184.  
  185.     std::cout << "Match = " << ((zdata == dzdata) ? "true" : "false") << "\n";
  186. }
  187.  
  188. // ============================================================================
  189. // PN approach with 3 adaptive models (1*2 and 2*256 symbols)
  190. // Processes signed 9-bit values
  191. //
  192. // First the sign is coded using the 2 symbol model_sign
  193. // If sign positive then abs value is coded using the 256 symbol model_valuep
  194. // If sign negative then abs value - 1 is coded using the 256 symbol model_valuen
  195.  
  196. template<typename ModelT, typename CodecT = Arithmetic_Codec>
  197. uint32_t encode(std::vector<int32_t> const& buffer
  198.     , ModelT& model_sign
  199.     , ModelT& model_valuep
  200.     , ModelT& model_valuen
  201.     , CodecT& encoder)
  202. {
  203.     encoder.start_encoder();
  204.     for (int32_t v : buffer) {
  205.         uint32_t sign, value;
  206.         if (v >= 0) {
  207.             sign = 0;
  208.             value = v;
  209.         } else {
  210.             sign = 1;
  211.             value = std::abs(v) - 1;
  212.         }
  213.  
  214.         encoder.encode(sign, model_sign);
  215.         if (sign == 0) {
  216.             encoder.encode(value, model_valuep);
  217.         } else {
  218.             encoder.encode(value, model_valuen);
  219.         }
  220.     }
  221.     return 8 * encoder.stop_encoder();
  222. }
  223.  
  224. template<typename ModelT, typename CodecT = Arithmetic_Codec>
  225. void decode(std::vector<int32_t>& buffer
  226.     , ModelT& model_sign
  227.     , ModelT& model_valuep
  228.     , ModelT& model_valuen
  229.     , CodecT& decoder)
  230. {
  231.     decoder.start_decoder();
  232.     for (uint32_t i(0); i < buffer.size(); ++i) {
  233.         uint32_t sign(decoder.decode(model_sign));
  234.         int32_t value;
  235.         if (sign == 0) {
  236.             value = decoder.decode(model_valuep);
  237.             buffer[i] = value;
  238.         } else {
  239.             value = decoder.decode(model_valuen);
  240.             buffer[i] = -(value + 1);
  241.         }
  242.     }
  243.     decoder.stop_decoder();
  244. }
  245.  
  246. void test_split_pn(std::vector<int32_t> const& data)
  247. {
  248.  
  249.     Arithmetic_Codec codec(N_VAL * 2);
  250.     Adaptive_Data_Model adaptive_model_sign(2);
  251.     Adaptive_Data_Model adaptive_model_valuep(256);
  252.     Adaptive_Data_Model adaptive_model_valuen(256);
  253.  
  254.     std::size_t raw_size_bits(N_VAL * 9);
  255.     std::size_t packed_size_bits(encode(data, adaptive_model_sign
  256.         , adaptive_model_valuep, adaptive_model_valuen, codec));
  257.     double ratio(double(packed_size_bits) / raw_size_bits * 100);
  258.     std::cout << "Ratio = " << ratio << " %\n";
  259.  
  260.     std::vector<int32_t> ddata(N_VAL);
  261.  
  262.     adaptive_model_sign.reset();
  263.     adaptive_model_valuep.reset();
  264.     adaptive_model_valuen.reset();
  265.  
  266.     decode(ddata, adaptive_model_sign
  267.         , adaptive_model_valuep, adaptive_model_valuen, codec);
  268.  
  269.     std::cout << "Match = " << ((data == ddata) ? "true" : "false") << "\n";
  270. }
  271.  
  272. // ============================================================================
  273.  
  274. int main()
  275. {
  276.     std::vector<int32_t> data(gen_data(N_VAL));
  277.     std::vector<uint32_t> zdata(zigzag_encode(data));
  278.  
  279.     test_simple(zdata);
  280.     test_split(zdata);
  281.     test_split_pn(data);
  282.  
  283.     return 0;
  284. }
  285.  
  286. // ============================================================================
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement