fork download 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <iterator>
  6. #include <vector>
  7. #include <cstdlib> 
  8. #include <cstddef>
  9. #include <stdint.h>
  10. #include <iomanip>
  11.  
  12. enum {
  13.   // Config
  14.   ZERO_POS = 2,
  15.   INDEX_SIZE = 5,
  16.   VALUE_LIMIT = -100,
  17.  
  18.   // Constants"Internal error: nibble buffer overflow\n";
  19. 	      exit(1);
  20. 	    }
  21.  
  22. 	    *stream++ = block;
  23. 	  }
  24.  
  25. 	  block = 0;
  26. 	  pos = 0;
  27. 	}
  28.       };
  29.  
  30.       class ArWriter
  31.       { // http://w...content-available-to-author-only...s.com/ac_arithmetic.html
  32. 	uint16_t* stream;
  33. 	uint16_t* table;
  34. 	uint16_t* tableEnd;
  35. 	uint16_t high;
  36. 	uint16_t low;
  37. 	uint16_t result;
  38. 	uint16_t resultUsed;
  39. 	uint16_t underflows;
  40.       public:
  41. 	ArWriter(uint16_t* p, uint16_t* t, uint16_t* e)
  42. 	: stream(p)
  43. 	, table(t) // Zero value in *(t-1) expected
  44. 	, tableEnd(e)
  45. 	, high(0xFFFF)
  46. 	, low(0)
  47. 	, result(0)
  48. 	, resultUsed(0)
  49. 	, underflows(0)
  50. 	{}
  51. 	void write(uint16_t value)
  52. 	{
  53. 	  uint32_t range = static_cast<uint32_t>(high) - low + 1;
  54. 	  high = low + ((range * table[value]) / *(tableEnd - 1)) - 1;
  55. 	  low = low + (range * table[value - 1]) / *(tableEnd - 1);
  56.  
  57. 	  while (true) {
  58. 	    if ((high ^ low) & 0x8000) // different msb
  59. 	    {
  60. 	      if ((high & 0x4000) < (low & 0x4000))
  61. 	      {
  62. 		++underflows;
  63. 		low &= 0x3FFF;
  64. 		high |= 0x4000;
  65. 		shift();
  66. 	      }
  67. 	      else
  68. 	      {
  69. 		break;
  70. 	      }
  71. 	    }
  72. 	    else // equal msb
  73. 	    {
  74. 	      writeBit((low >> 15) & 1);
  75. 	      while (underflows)
  76. 	      {
  77. 		writeBit((~low >> 15) & 1);
  78. 		--underflows;
  79. 	      }
  80. 	      shift();
  81. 	    }
  82. 	  }
  83. 	}
  84. 	void shift()
  85. 	{
  86. 	  low <<= 1;
  87. 	  high <<= 1;
  88. 	  high |= 1;
  89. 	}
  90. 	void writeBit(uint16_t bit)
  91. 	{
  92. 	  result <<= 1;
  93. 	  result |= bit;
  94. 	  ++resultUsed;
  95. 	  if (resultUsed == 16)
  96. 	    flushResult();
  97. 	}
  98. 	void flushResult()
  99. 	{
  100. 	  *stream++ = result;
  101. 	  result = 0;
  102. 	  resultUsed = 0;
  103. 	}
  104. 	void flush()
  105. 	{
  106. 	  writeBit((low >> 14) & 1);
  107. 	  ++underflows;
  108.  
  109. 	  while (underflows--)
  110. 	    writeBit((~low >> 14) & 1);
  111.  
  112. 	  while (resultUsed)
  113. 	    writeBit(0);
  114. 	}
  115. 	uint16_t* getStreamPos() const
  116. 	{
  117. 	  return stream;
  118. 	}
  119.       };
  120.  
  121.       void encoder()
  122.       {
  123. 	// Pass 1: calculate frequencies
  124. 	vector<uint16_t> freq(1024);
  125. 	uint16_t binary4 = 0;
  126. 	uint16_t binary12 = 0;
  127. 	Taylor lastTaylor;
  128.  
  129. 	for (size_t row = 0; row < NUM_ROWS; ++row)
  130. 	{
  131. 	  for (size_t col = 0; col < NUM_COLUMNS - 1; ++col)
  132. 	    { // last column is not encoded
  133. 	    Taylor taylor(my_array[row][col], lastTaylor);
  134. 	    int16_t fixup = taylor.d[0] - lastTaylor.predict();
  135.  
  136. 	    // Hack for values, jumping from -100 to 100
  137. 	    if (taylor.d[0] >= VALUE_LIMIT_POS && lastTaylor.d[0] < 0)
  138. 	      fixup -= 2 * taylor.d[0];
  139.  
  140. 	    // Value too big for arithmetic codec, use nibbles
  141. 	    if (fixup > INDEX_PLUS + NUM_BIN_OUTLIERS ||
  142. 		fixup < -ZERO_POS - NUM_BIN_OUTLIERS)
  143. 	    {
  144. 	      ++binary12;
  145. 	    }
  146. 	    else if (fixup > INDEX_PLUS || fixup < -ZERO_POS)
  147. 	    {
  148. 	      ++binary4;
  149. 	    }
  150.  
  151. 	    // Hack for values, jumping from -100 to 100
  152. 	    if (taylor.d[0] >= VALUE_LIMIT_POS && lastTaylor.d[0] < 0)
  153. 	    {
  154. 	      lastTaylor.negate();
  155. 	      taylor.update(lastTaylor);
  156. 	    }
  157.  
  158. 	    // This will be used to predict the next value
  159. 	    // (derivative is not updated for the first column)
  160. 	    lastTaylor.copyFrom(taylor, col? 3: 1);
  161.  
  162. 	    // Update table of frequencies
  163. 	    ++freq[512 + fixup];
  164. 	  }
  165. 	}
  166.  
  167. 	cout << "fixup: ";
  168. 	ostream_iterator<int> out_it (cout, " ");
  169. 	std::copy(freq.begin()+480, freq.end()-480, out_it);
  170. 	cout << "\n";
  171. 	cout << "binary4=" << binary4 << "\n";
  172. 	cout << "binary12=" << binary12 << "\n";
  173. 	cout << "-----------\n";
  174.  
  175. 	double bitsPerValue =
  176. 	  accumulate(freq.begin(), freq.end(), 0., Entropy(0));
  177.  
  178. 	cout
  179. 	  << " Entropy=" << NUM_VALUES * bitsPerValue / 8.
  180. 	  << " bits=" << bitsPerValue << "\n";
  181.  
  182. 	Entropy entropy(binary4 + binary12);
  183.  
  184. 	cout << "Static="
  185. 	     << 2 * (INDEX_FULL_SIZE +
  186. 		     (2 + binary4 + binary12*3 + 3) / 4)
  187. 	     << "\n";
  188.  
  189. 	// Add nibble frequencies
  190. 	freq[512 - ZERO_POS + INDEX_SIZE] = binary4;
  191. 	freq[512 - ZERO_POS + INDEX_SIZE + 1] = binary12;
  192.  
  193. 	bitsPerValue =
  194. 	  accumulate(freq.begin() + 512 - ZERO_POS,
  195. 		     freq.begin() + 512 - ZERO_POS + INDEX_FULL_SIZE,
  196. 		     0., entropy);
  197. 	cout
  198. 	  << "Entropy2=" << NUM_VALUES * bitsPerValue / 8.
  199. 	  << " bits=" << bitsPerValue << "\n";
  200.  
  201. 	// Pass 2: encode arithmetic coder bitstream & nibbles
  202. 	vector<uint16_t> compacted(1024);
  203.  
  204. 	// Cumulative sum of frequencies
  205. 	partial_sum(freq.begin() + 512 - ZERO_POS,
  206. 	     freq.begin() + 512 - ZERO_POS + INDEX_FULL_SIZE,
  207. 	     compacted.begin() + 1);
  208.  
  209. 	// Configure nibble writer
  210. 	uint16_t* pNibbles = &compacted[INDEX_FULL_SIZE + 1];
  211. 	uint16_t nibbles = (3 + binary4 + binary12*3 + 3) / 4;
  212. 	NibbleWriter nibbleWriter(pNibbles, nibbles);
  213. 	uint16_t* pData = pNibbles + nibbles;
  214.  
  215. 	// Configure arithmetic coder
  216. 	ArWriter arWriter(pData,
  217. 			  &compacted[1],
  218. 			  &compacted[1 + INDEX_FULL_SIZE]);
  219.  
  220. 	lastTaylor.clear();
  221.  
  222. 	for (size_t row = 0; row < NUM_ROWS; ++row)
  223. 	{
  224. 	  for (size_t col = 0; col < NUM_COLUMNS - 1; ++col)
  225. 	  { // last column is not encoded
  226. 	    Taylor taylor(my_array[row][col], lastTaylor);
  227. 	    int16_t fixup = taylor.d[0] - lastTaylor.predict();
  228.  
  229. 	    // Hack for values, jumping from -100 to 100
  230. 	    if (taylor.d[0] >= VALUE_LIMIT_POS && lastTaylor.d[0] < 0)
  231. 	      fixup -= 2 * taylor.d[0];
  232.  
  233. 	    // Value too big for arithmetic codec, use nibbles
  234. 	    if (fixup > INDEX_PLUS + NUM_BIN_OUTLIERS ||
  235. 		fixup < -ZERO_POS - NUM_BIN_OUTLIERS)
  236. 	    {
  237. 	      nibbleWriter.write12(fixup);
  238. 	      arWriter.write(INDEX_SIZE + BIN12);
  239. 	    }
  240. 	    else if (fixup > INDEX_PLUS || fixup < -ZERO_POS)
  241. 	    {
  242. 	      if (fixup > 0)
  243. 		nibbleWriter.write4(fixup - INDEX_PLUS - 1);
  244. 	      else
  245. 		nibbleWriter.write4((-fixup - ZERO_POS - 1) | 0x8);
  246.  
  247. 	      arWriter.write(INDEX_SIZE + BIN4);
  248. 	    }
  249. 	    else
  250. 	    {
  251. 	      arWriter.write(ZERO_POS + fixup);
  252. 	    }
  253.  
  254. 	    // Hack for values, jumping from -100 to 100
  255. 	    if (taylor.d[0] >= VALUE_LIMIT_POS && lastTaylor.d[0] < 0)
  256. 	    {
  257. 	      lastTaylor.negate();
  258. 	      taylor.update(lastTaylor);
  259. 	    }
  260.  
  261. 	    // This will be used to predict the next value
  262. 	    // (derivative is not updated for the first column)
  263. 	    lastTaylor.copyFrom(taylor, col? 3: 1);
  264. 	  }
  265. 	}
  266.  
  267. 	nibbleWriter.flush();
  268. 	arWriter.flush();
  269.  
  270. 	size_t size = arWriter.getStreamPos() - &compacted[0];
  271.  
  272. 	cout
  273. 	  << "ArEnc="
  274. 	  << (arWriter.getStreamPos() - pNibbles - nibbles) * 2
  275. 	  << "\nTotal=" << size * 2 << "\n---------\n";
  276.  
  277. 	for (size_t i = 0; i < size; i += 8)
  278. 	{
  279. 	  cout << "    " << hex << showbase;
  280. 	  ostream_iterator<int> out_it (cout, ", ");
  281.  
  282. 	  std::copy(compacted.begin() + i,
  283. 		    (i + 8 < size)?
  284. 		    compacted.begin() + i + 8: compacted.begin() + size,
  285. 		    out_it);
  286.  
  287. 	  cout << "\n";
  288. 	}
  289.       }
  290.  
  291.       int main()
  292.       {
  293. 	encoder();
  294. 	return 0;
  295.       }
  296.  
Success #stdin #stdout 0.01s 2864KB
comments (?)
stdin 
Standard input is empty
stdout 
fixup: 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 1 1 0 0 1 0 1 4 0 4 3 4 7 12 75 583 1252 600 74 11 11 1 1 0 1 0 1 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 
binary4=61
binary12=19
-----------
 Entropy=680.231 bits=2.04274
Static=74
Entropy2=641.075 bits=1.92515
ArEnc=648
Total=726
---------
    0, 0x4b, 0x292, 0x776, 0x9ce, 0xa18, 0xa55, 0xa68, 
    0x601f, 0xea09, 0x4e8c, 0xafff, 0xbfed, 0x6ff1, 0x10fe, 0xfdb1, 
    0xa100, 0xd1fe, 0xd800, 0x129f, 0xf010, 0x730f, 0x9ec1, 0x80e9, 
    0x9a9c, 0x8888, 0x9880, 0x1, 0x2ab9, 0x8105, 0x101, 0xdfb8, 
    0xfeaf, 0xc030, 0x8100, 0x930, 0x8c1, 0xcaf4, 0, 0xfff6, 
    0xefb9, 0x416, 0x78eb, 0xe5d2, 0xeaf7, 0x597e, 0x8a50, 0xf278, 
    0x30c, 0xad5a, 0x7f2a, 0x96cd, 0x860a, 0xbad7, 0x2145, 0x1b7, 
    0x807f, 0xba8f, 0x8b22, 0x40c9, 0xcfe5, 0x43c, 0x56a9, 0x75e4, 
    0x6b43, 0x23e, 0x3db4, 0xac48, 0x71bf, 0xeaf9, 0x4a9a, 0xe927, 
    0x855, 0xe54, 0xd56f, 0xe170, 0x1c88, 0x57c, 0x99b2, 0xfd79, 
    0xa8c8, 0xf5f6, 0xcd89, 0xfd66, 0x9815, 0xc126, 0x32e1, 0x56f, 
    0xfe7a, 0xd86d, 0x155b, 0x4a22, 0x62d2, 0x36b8, 0x877e, 0xbd70, 
    0x2746, 0xa87f, 0x169d, 0x4af0, 0xe059, 0x6cfb, 0xb27a, 0x49a6, 
    0xae32, 0xd0ab, 0x14b1, 0xa498, 0xb5e9, 0xae0e, 0x9427, 0x9b4f, 
    0x4957, 0xebd5, 0xf1fa, 0xf288, 0xff72, 0xc29f, 0x475e, 0xf4ca, 
    0xaa0e, 0xd455, 0x1b1f, 0xeaee, 0xf2ba, 0xaee, 0x96d2, 0xa942, 
    0xaeed, 0x8a5a, 0xdfda, 0x3ce7, 0x31d2, 0x60cb, 0xe98d, 0x8162, 
    0xb0c, 0x27af, 0x6e6c, 0xd2e5, 0x6022, 0xe421, 0xe7f7, 0x394a, 
    0x173b, 0xed47, 0xaef7, 0x4b78, 0x283b, 0x9d78, 0x3e13, 0x4a6, 
    0xa6e, 0xcda6, 0x3bb0, 0x62b7, 0x2b9a, 0xee3f, 0xda27, 0x88ee, 
    0x8280, 0xe658, 0x1668, 0xb701, 0x4e70, 0x147, 0xe058, 0xa1a0, 
    0x3455, 0x5994, 0xd390, 0x1fac, 0xb58c, 0x3680, 0x3d42, 0xf12, 
    0xba9e, 0x949f, 0x51df, 0x9603, 0x52af, 0x74d8, 0xbdc7, 0xefe9, 
    0x3b5e, 0xe273, 0xbae, 0x13c4, 0x5844, 0x3c6d, 0xf045, 0x52ba, 
    0x6ef2, 0xa428, 0x67b7, 0x91f7, 0x31ee, 0xbcb9, 0xfe7f, 0xefd3, 
    0x367e, 0x4308, 0x2b58, 0xbd30, 0xc4bd, 0xa28f, 0xca5d, 0x2230, 
    0x8f65, 0x134e, 0xaaa8, 0x6499, 0x4a14, 0x15ec, 0xf83f, 0x8c92, 
    0x3928, 0x2d35, 0x176f, 0x1080, 0xc982, 0x1bae, 0xfb7a, 0x616a, 
    0xc069, 0x8177, 0xe7f3, 0x70e3, 0x5d99, 0x8dfa, 0xdf80, 0x364b, 
    0x6b3f, 0x1aec, 0x66c8, 0x87cc, 0xd62f, 0x687, 0x9a3d, 0x3704, 
    0xe486, 0xa47e, 0xa87a, 0x1bd, 0xd8e2, 0x9f6d, 0xdd2, 0xd150, 
    0xcdf3, 0xb4e4, 0x9bd7, 0xabc9, 0x52e8, 0x553c, 0xa2ab, 0x18b8, 
    0x70fb, 0xa594, 0xd34c, 0x9450, 0xd928, 0xd581, 0x54a, 0x3096, 
    0x30c7, 0x6899, 0xcfd0, 0x5a37, 0xa664, 0xfe0, 0x4b1a, 0x616c, 
    0x9eba, 0x591a, 0xfa80, 0x2911, 0x2c5b, 0xe310, 0x32e1, 0x3680, 
    0x55a8, 0x7e, 0xd7fd, 0xe81d, 0x13f2, 0x919d, 0x972f, 0x5c52, 
    0xdf86, 0x4576, 0xd6ea, 0x2afd, 0x1759, 0xcf24, 0x1b0e, 0xc73f, 
    0x75aa, 0x7f2, 0x7432, 0x8691, 0x389c, 0xb9a4, 0xf1ad, 0xb21a, 
    0xa644, 0x2b0f, 0x8e52, 0x8a81, 0x9558, 0xed0a, 0xcff4, 0x217, 
    0x5e98, 0x1d53, 0x59f2, 0x9b70, 0xb4b1, 0x2bd9, 0xbbec, 0xfa03, 
    0xbf55, 0x3651, 0x6d8, 0xcdc0, 0x132d, 0x9c88, 0x349b, 0x4ac9, 
    0x89c6, 0x5cc1, 0x7826, 0xc599, 0x763f, 0x735f, 0x1e1, 0xc668, 
    0x67b6, 0xc22, 0xbc5, 0x2324, 0x9c9c, 0xc8fe, 0xf55a, 0x5218, 
    0x4406, 0x2fff, 0xfffb, 0xe0e6, 0x12b0, 0xc3e9, 0xc119, 0x883c, 
    0xd877, 0x8973, 0xf93f, 0x3684, 0xfffb, 0x7eeb, 0x730c, 0x7cbb, 
    0xcea, 0x856, 0x8000,
https://ideone.com/xBvLO
language:
C++ (gcc 8.3)
created:
14 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!