fork download
copy 
  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
  19.   NUM_ROWS = 37,
  20.   NUM_COLUMNS = 73,
  21.   VALUE_LIMIT_POS = -VALUE_LIMIT,
  22.   NUM_BIN_OUTLIERS = 8,
  23.   NUM_VALUES = NUM_ROWS * (NUM_COLUMNS - 1),
  24.   INDEX_PLUS = INDEX_SIZE - ZERO_POS - 1,
  25.   BIN4 = 0,
  26.   BIN12 = 1,
  27.   INDEX_FULL_SIZE = INDEX_SIZE + 2
  28. };
  29.  
  30. int16_t my_array[NUM_ROWS][NUM_COLUMNS] = {
  31. {150,145,140,135,130,125,120,115,110,105,100,95,90,85,80,75,70,65,60,55,50,45,40,35,30,25,20,15,10,5,0,-4,-9,-14,-19,-24,-29,-34,-39,-44,-49,-54,-59,-64,-69,-74,-79,-84,-89,-94,-99,104,109,114,119,124,129,134,139,144,149,154,159,164,169,174,179,175,170,165,160,155,150}, \
  32. {143,137,131,126,120,115,110,105,100,95,90,85,80,75,71,66,62,57,53,48,44,39,35,31,27,22,18,14,9,5,1,-3,-7,-11,-16,-20,-25,-29,-34,-38,-43,-47,-52,-57,-61,-66,-71,-76,-81,-86,-91,-96,101,107,112,117,123,128,134,140,146,151,157,163,169,175,178,172,166,160,154,148,143}, \
  33. {130,124,118,112,107,101,96,92,87,82,78,74,70,65,61,57,54,50,46,42,38,34,31,27,23,19,16,12,8,4,1,-2,-6,-10,-14,-18,-22,-26,-30,-34,-38,-43,-47,-51,-56,-61,-65,-70,-75,-79,-84,-89,-94,100,105,111,116,122,128,135,141,148,155,162,170,177,174,166,159,151,144,137,130}, \
  34. {111,104,99,94,89,85,81,77,73,70,66,63,60,56,53,50,46,43,40,36,33,30,26,23,20,16,13,10,6,3,0,-3,-6,-9,-13,-16,-20,-24,-28,-32,-36,-40,-44,-48,-52,-57,-61,-65,-70,-74,-79,-84,-88,-93,-98,103,109,115,121,128,135,143,152,162,172,176,165,154,144,134,125,118,111}, \
  35. {85,81,77,74,71,68,65,63,60,58,56,53,51,49,46,43,41,38,35,32,29,26,23,19,16,13,10,7,4,1,-1,-3,-6,-9,-13,-16,-19,-23,-26,-30,-34,-38,-42,-46,-50,-54,-58,-62,-66,-70,-74,-78,-83,-87,-91,-95,100,105,110,117,124,133,144,159,178,160,141,125,112,103,96,90,85}, \
  36. {62,60,58,57,55,54,52,51,50,48,47,46,44,42,41,39,36,34,31,28,25,22,19,16,13,10,7,4,2,0,-3,-5,-8,-10,-13,-16,-19,-22,-26,-29,-33,-37,-41,-45,-49,-53,-56,-60,-64,-67,-70,-74,-77,-80,-83,-86,-89,-91,-94,-97,101,105,111,130,109,84,77,74,71,68,66,64,62}, \
  37. {46,46,45,44,44,43,42,42,41,41,40,39,38,37,36,35,33,31,28,26,23,20,16,13,10,7,4,1,-1,-3,-5,-7,-9,-12,-14,-16,-19,-22,-26,-29,-33,-36,-40,-44,-48,-51,-55,-58,-61,-64,-66,-68,-71,-72,-74,-74,-75,-74,-72,-68,-61,-48,-25,2,22,33,40,43,45,46,47,46,46}, \
  38. {36,36,36,36,36,35,35,35,35,34,34,34,34,33,32,31,30,28,26,23,20,17,14,10,6,3,0,-2,-4,-7,-9,-10,-12,-14,-15,-17,-20,-23,-26,-29,-32,-36,-40,-43,-47,-50,-53,-56,-58,-60,-62,-63,-64,-64,-63,-62,-59,-55,-49,-41,-30,-17,-4,6,15,22,27,31,33,34,35,36,36}, \
  39. {30,30,30,30,30,30,30,29,29,29,29,29,29,29,29,28,27,26,24,21,18,15,11,7,3,0,-3,-6,-9,-11,-12,-14,-15,-16,-17,-19,-21,-23,-26,-29,-32,-35,-39,-42,-45,-48,-51,-53,-55,-56,-57,-57,-56,-55,-53,-49,-44,-38,-31,-23,-14,-6,0,7,13,17,21,24,26,27,29,29,30}, \
  40. {25,25,26,26,26,25,25,25,25,25,25,25,25,26,25,25,24,23,21,19,16,12,8,4,0,-3,-7,-10,-13,-15,-16,-17,-18,-19,-20,-21,-22,-23,-25,-28,-31,-34,-37,-40,-43,-46,-48,-49,-50,-51,-51,-50,-48,-45,-42,-37,-32,-26,-19,-13,-7,-1,3,7,11,14,17,19,21,23,24,25,25}, \
  41. {21,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,21,20,18,16,13,9,5,1,-3,-7,-11,-14,-17,-18,-20,-21,-21,-22,-22,-22,-23,-23,-25,-27,-29,-32,-35,-37,-40,-42,-44,-45,-45,-45,-44,-42,-40,-36,-32,-27,-22,-17,-12,-7,-3,0,3,7,9,12,14,16,18,19,20,21,21}, \
  42. {18,19,19,19,19,19,19,19,19,19,19,19,19,19,19,19,18,17,16,14,10,7,2,-1,-6,-10,-14,-17,-19,-21,-22,-23,-24,-24,-24,-24,-23,-23,-23,-24,-26,-28,-30,-33,-35,-37,-38,-39,-39,-38,-36,-34,-31,-28,-24,-19,-15,-10,-6,-3,0,1,4,6,8,10,12,14,15,16,17,18,18}, \
  43. {16,16,17,17,17,17,17,17,17,17,17,16,16,16,16,16,16,15,13,11,8,4,0,-4,-9,-13,-16,-19,-21,-23,-24,-25,-25,-25,-25,-24,-23,-21,-20,-20,-21,-22,-24,-26,-28,-30,-31,-32,-31,-30,-29,-27,-24,-21,-17,-13,-9,-6,-3,-1,0,2,4,5,7,9,10,12,13,14,15,16,16}, \
  44. {14,14,14,15,15,15,15,15,15,15,14,14,14,14,14,14,13,12,11,9,5,2,-2,-6,-11,-15,-18,-21,-23,-24,-25,-25,-25,-25,-24,-22,-21,-18,-16,-15,-15,-15,-17,-19,-21,-22,-24,-24,-24,-23,-22,-20,-18,-15,-12,-9,-5,-3,-1,0,1,2,4,5,6,8,9,10,11,12,13,14,14}, \
  45. {12,13,13,13,13,13,13,13,13,13,13,13,12,12,12,12,11,10,9,6,3,0,-4,-8,-12,-16,-19,-21,-23,-24,-24,-24,-24,-23,-22,-20,-17,-15,-12,-10,-9,-9,-10,-12,-13,-15,-17,-17,-18,-17,-16,-15,-13,-11,-8,-5,-3,-1,0,1,1,2,3,4,6,7,8,9,10,11,12,12,12}, \
  46. {11,11,11,11,11,12,12,12,12,12,11,11,11,11,11,10,10,9,7,5,2,-1,-5,-9,-13,-17,-20,-22,-23,-23,-23,-23,-22,-20,-18,-16,-14,-11,-9,-6,-5,-4,-5,-6,-8,-9,-11,-12,-12,-12,-12,-11,-9,-8,-6,-3,-1,0,0,1,1,2,3,4,5,6,7,8,9,10,11,11,11}, \
  47. {10,10,10,10,10,10,10,10,10,10,10,10,10,10,9,9,9,7,6,3,0,-3,-6,-10,-14,-17,-20,-21,-22,-22,-22,-21,-19,-17,-15,-13,-10,-8,-6,-4,-2,-2,-2,-2,-4,-5,-7,-8,-8,-9,-8,-8,-7,-5,-4,-2,0,0,1,1,1,2,2,3,4,5,6,7,8,9,10,10,10}, \
  48. {9,9,9,9,9,9,9,10,10,9,9,9,9,9,9,8,8,6,5,2,0,-4,-7,-11,-15,-17,-19,-21,-21,-21,-20,-18,-16,-14,-12,-10,-8,-6,-4,-2,-1,0,0,0,-1,-2,-4,-5,-5,-6,-6,-5,-5,-4,-3,-1,0,0,1,1,1,1,2,3,3,5,6,7,8,8,9,9,9}, \
  49. {9,9,9,9,9,9,9,9,9,9,9,9,8,8,8,8,7,5,4,1,-1,-5,-8,-12,-15,-17,-19,-20,-20,-19,-18,-16,-14,-11,-9,-7,-5,-4,-2,-1,0,0,1,1,0,0,-2,-3,-3,-4,-4,-4,-3,-3,-2,-1,0,0,0,0,0,1,1,2,3,4,5,6,7,8,8,9,9}, \
  50. {9,9,9,8,8,8,9,9,9,9,9,8,8,8,8,7,6,5,3,0,-2,-5,-9,-12,-15,-17,-18,-19,-19,-18,-16,-14,-12,-9,-7,-5,-4,-2,-1,0,0,1,1,1,1,0,0,-1,-2,-2,-3,-3,-2,-2,-1,-1,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8,9}, \
  51. {8,8,8,8,8,8,9,9,9,9,9,9,8,8,8,7,6,4,2,0,-3,-6,-9,-12,-15,-17,-18,-18,-17,-16,-14,-12,-10,-8,-6,-4,-2,-1,0,0,1,2,2,2,2,1,0,0,-1,-1,-1,-2,-2,-1,-1,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8}, \
  52. {8,8,8,8,9,9,9,9,9,9,9,9,9,8,8,7,5,3,1,-1,-4,-7,-10,-13,-15,-16,-17,-17,-16,-15,-13,-11,-9,-6,-5,-3,-2,0,0,0,1,2,2,2,2,1,1,0,0,0,-1,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,-1,0,0,1,3,4,5,7,7,8}, \
  53. {8,8,9,9,9,9,10,10,10,10,10,10,10,9,8,7,5,3,0,-2,-5,-8,-11,-13,-15,-16,-16,-16,-15,-13,-12,-10,-8,-6,-4,-2,-1,0,0,1,2,2,3,3,2,2,1,0,0,0,0,0,0,0,0,0,0,-1,-1,-2,-2,-2,-2,-2,-1,0,0,1,3,4,6,7,8}, \
  54. {7,8,9,9,9,10,10,11,11,11,11,11,10,10,9,7,5,3,0,-2,-6,-9,-11,-13,-15,-16,-16,-15,-14,-13,-11,-9,-7,-5,-3,-2,0,0,1,1,2,3,3,3,3,2,2,1,1,0,0,0,0,0,0,0,-1,-1,-2,-3,-3,-4,-4,-4,-3,-2,-1,0,1,3,5,6,7}, \
  55. {6,8,9,9,10,11,11,12,12,12,12,12,11,11,9,7,5,2,0,-3,-7,-10,-12,-14,-15,-16,-15,-15,-13,-12,-10,-8,-7,-5,-3,-1,0,0,1,2,2,3,3,4,3,3,3,2,2,1,1,1,0,0,0,0,-1,-2,-3,-4,-4,-5,-5,-5,-5,-4,-2,-1,0,2,3,5,6}, \
  56. {6,7,8,10,11,12,12,13,13,14,14,13,13,11,10,8,5,2,0,-4,-8,-11,-13,-15,-16,-16,-16,-15,-13,-12,-10,-8,-6,-5,-3,-1,0,0,1,2,3,3,4,4,4,4,4,3,3,3,2,2,1,1,0,0,-1,-2,-3,-5,-6,-7,-7,-7,-6,-5,-4,-3,-1,0,2,4,6}, \
  57. {5,7,8,10,11,12,13,14,15,15,15,14,14,12,11,8,5,2,-1,-5,-9,-12,-14,-16,-17,-17,-16,-15,-14,-12,-11,-9,-7,-5,-3,-1,0,0,1,2,3,4,4,5,5,5,5,5,5,4,4,3,3,2,1,0,-1,-2,-4,-6,-7,-8,-8,-8,-8,-7,-6,-4,-2,0,1,3,5}, \
  58. {4,6,8,10,12,13,14,15,16,16,16,16,15,13,11,9,5,2,-2,-6,-10,-13,-16,-17,-18,-18,-17,-16,-15,-13,-11,-9,-7,-5,-4,-2,0,0,1,3,3,4,5,6,6,7,7,7,7,7,6,5,4,3,2,0,-1,-3,-5,-7,-8,-9,-10,-10,-10,-9,-7,-5,-4,-1,0,2,4}, \
  59. {4,6,8,10,12,14,15,16,17,18,18,17,16,15,12,9,5,1,-3,-8,-12,-15,-18,-19,-20,-20,-19,-18,-16,-15,-13,-11,-8,-6,-4,-2,-1,0,1,3,4,5,6,7,8,9,9,9,9,9,9,8,7,5,3,1,-1,-3,-6,-8,-10,-11,-12,-12,-11,-10,-9,-7,-5,-2,0,1,4}, \
  60. {4,6,8,11,13,15,16,18,19,19,19,19,18,16,13,10,5,0,-5,-10,-15,-18,-21,-22,-23,-22,-22,-20,-18,-17,-14,-12,-10,-8,-5,-3,-1,0,1,3,5,6,8,9,10,11,12,12,13,12,12,11,9,7,5,2,0,-3,-6,-9,-11,-12,-13,-13,-12,-11,-10,-8,-6,-3,-1,1,4}, \
  61. {3,6,9,11,14,16,17,19,20,21,21,21,19,17,14,10,4,-1,-8,-14,-19,-22,-25,-26,-26,-26,-25,-23,-21,-19,-17,-14,-12,-9,-7,-4,-2,0,1,3,5,7,9,11,13,14,15,16,16,16,16,15,13,10,7,4,0,-3,-7,-10,-12,-14,-15,-14,-14,-12,-11,-9,-6,-4,-1,1,3}, \
  62. {4,6,9,12,14,17,19,21,22,23,23,23,21,19,15,9,2,-5,-13,-20,-25,-28,-30,-31,-31,-30,-29,-27,-25,-22,-20,-17,-14,-11,-9,-6,-3,0,1,4,6,9,11,13,15,17,19,20,21,21,21,20,18,15,11,6,2,-2,-7,-11,-13,-15,-16,-16,-15,-13,-11,-9,-7,-4,-1,1,4}, \
  63. {4,7,10,13,15,18,20,22,24,25,25,25,23,20,15,7,-2,-12,-22,-29,-34,-37,-38,-38,-37,-36,-34,-31,-29,-26,-23,-20,-17,-13,-10,-7,-4,-1,2,5,8,11,13,16,18,21,23,24,26,26,26,26,24,21,17,12,5,0,-6,-10,-14,-16,-16,-16,-15,-14,-12,-10,-7,-4,-1,1,4}, \
  64. {4,7,10,13,16,19,22,24,26,27,27,26,24,19,11,-1,-15,-28,-37,-43,-46,-47,-47,-45,-44,-41,-39,-36,-32,-29,-26,-22,-19,-15,-11,-8,-4,-1,2,5,9,12,15,19,22,24,27,29,31,33,33,33,32,30,26,21,14,6,0,-6,-11,-14,-15,-16,-15,-14,-12,-9,-7,-4,-1,1,4}, \
  65. {6,9,12,15,18,21,23,25,27,28,27,24,17,4,-14,-34,-49,-56,-60,-60,-60,-58,-56,-53,-50,-47,-43,-40,-36,-32,-28,-25,-21,-17,-13,-9,-5,-1,2,6,10,14,17,21,24,28,31,34,37,39,41,42,43,43,41,38,33,25,17,8,0,-4,-8,-10,-10,-10,-8,-7,-4,-2,0,3,6}, \
  66. {22,24,26,28,30,32,33,31,23,-18,-81,-96,-99,-98,-95,-93,-89,-86,-82,-78,-74,-70,-66,-62,-57,-53,-49,-44,-40,-36,-32,-27,-23,-19,-14,-10,-6,-1,2,6,10,15,19,23,27,31,35,38,42,45,49,52,55,57,60,61,63,63,62,61,57,53,47,40,33,28,23,21,19,19,19,20,22}, \
  67. {168,173,178,176,171,166,161,156,151,146,141,136,131,126,121,116,111,106,101,-96,-91,-86,-81,-76,-71,-66,-61,-56,-51,-46,-41,-36,-31,-26,-21,-16,-11,-6,-1,3,8,13,18,23,28,33,38,43,48,53,58,63,68,73,78,83,88,93,98,103,108,113,118,123,128,133,138,143,148,153,158,163,168}};
  68.  
  69.       using namespace std;
  70.  
  71.       class Entropy
  72.       {
  73.         uint16_t total;
  74.       public:
  75.         Entropy(uint16_t add): total(add + NUM_VALUES) {}
  76.         double operator ()(double acc, uint16_t val)
  77.         {
  78. 	  double part = static_cast<double>(val) / total;
  79. 	  return acc - (part? part * log(part) / log(2.): 0.);
  80.         }
  81.       };
  82.  
  83.       struct Taylor
  84.       {
  85. 	int16_t d[2];
  86. 	Taylor()
  87. 	{
  88. 	  fill(d, d + 2, 0);
  89. 	}
  90. 	Taylor(int16_t val, const Taylor& other)
  91. 	{
  92. 	  d[0] = val;
  93. 	  update(other);
  94. 	}
  95. 	int16_t predict()
  96. 	{
  97. 	  return accumulate(d, d + 2, 0);
  98. 	}
  99. 	void copyFrom(const Taylor& other, size_t end = 2)
  100. 	{
  101. 	  copy(other.d, other.d + end, d);
  102. 	}
  103. 	void update(const Taylor& other)
  104. 	{
  105. 	  d[1] = d[0] - other.d[0];
  106. 	}
  107. 	void negate()
  108. 	{
  109. 	  d[0] = -d[0];
  110. 	  d[1] = -d[1];
  111. 	}
  112. 	void clear()
  113. 	{
  114. 	  fill(d, d + 2, 0);
  115. 	}
  116.       };
  117.  
  118.       class NibbleWriter
  119.       {
  120. 	uint16_t* stream;
  121. 	uint16_t* limit;
  122. 	uint16_t block;
  123. 	uint16_t pos;
  124.       public:
  125. 	NibbleWriter(uint16_t* p, uint16_t x)
  126. 	{
  127. 	  x &= 0x0FFF;
  128. 	  stream = p;
  129. 	  block = x;
  130. 	  limit = p + x;
  131. 	  pos = 12;
  132. 	}
  133. 	void write4(uint16_t x)
  134. 	{
  135. 	  block |= (x & 15) << pos;
  136. 	  pos += 4;
  137. 	  if (pos == 16)
  138. 	    flush();
  139. 	}
  140. 	void write12(uint16_t x)
  141. 	{
  142. 	  write4(x);
  143. 	  write4(x >> 4);
  144. 	  write4(x >> 8);
  145. 	}
  146. 	void flush()
  147. 	{
  148. 	  if (pos)
  149. 	  {
  150. 	    if (stream >= limit)
  151. 	    {
  152. 	      cerr << "Internal error: nibble buffer overflow\n";
  153. 	      exit(1);
  154. 	    }
  155.  
  156. 	    *stream++ = block;
  157. 	  }
  158.  
  159. 	  block = 0;
  160. 	  pos = 0;
  161. 	}
  162.       };
  163.  
  164.       class ArWriter
  165.       { // http://w...content-available-to-author-only...s.com/ac_arithmetic.html
  166. 	uint16_t* stream;
  167. 	uint16_t* table;
  168. 	uint16_t* tableEnd;
  169. 	uint16_t high;
  170. 	uint16_t low;
  171. 	uint16_t result;
  172. 	uint16_t resultUsed;
  173. 	uint16_t underflows;
  174.       public:
  175. 	ArWriter(uint16_t* p, uint16_t* t, uint16_t* e)
  176. 	: stream(p)
  177. 	, table(t) // Zero value in *(t-1) expected
  178. 	, tableEnd(e)
  179. 	, high(0xFFFF)
  180. 	, low(0)
  181. 	, result(0)
  182. 	, resultUsed(0)
  183. 	, underflows(0)
  184. 	{}
  185. 	void write(uint16_t value)
  186. 	{
  187. 	  uint32_t range = static_cast<uint32_t>(high) - low + 1;
  188. 	  high = low + ((range * table[value]) / *(tableEnd - 1)) - 1;
  189. 	  low = low + (range * table[value - 1]) / *(tableEnd - 1);
  190.  
  191. 	  while (true) {
  192. 	    if ((high ^ low) & 0x8000) // different msb
  193. 	    {
  194. 	      if ((high & 0x4000) < (low & 0x4000))
  195. 	      {
  196. 		++underflows;
  197. 		low &= 0x3FFF;
  198. 		high |= 0x4000;
  199. 		shift();
  200. 	      }
  201. 	      else
  202. 	      {
  203. 		break;
  204. 	      }
  205. 	    }
  206. 	    else // equal msb
  207. 	    {
  208. 	      writeBit((low >> 15) & 1);
  209. 	      while (underflows)
  210. 	      {
  211. 		writeBit((~low >> 15) & 1);
  212. 		--underflows;
  213. 	      }
  214. 	      shift();
  215. 	    }
  216. 	  }
  217. 	}
  218. 	void shift()
  219. 	{
  220. 	  low <<= 1;
  221. 	  high <<= 1;
  222. 	  high |= 1;
  223. 	}
  224. 	void writeBit(uint16_t bit)
  225. 	{
  226. 	  result <<= 1;
  227. 	  result |= bit;
  228. 	  ++resultUsed;
  229. 	  if (resultUsed == 16)
  230. 	    flushResult();
  231. 	}
  232. 	void flushResult()
  233. 	{
  234. 	  *stream++ = result;
  235. 	  result = 0;
  236. 	  resultUsed = 0;
  237. 	}
  238. 	void flush()
  239. 	{
  240. 	  writeBit((low >> 14) & 1);
  241. 	  ++underflows;
  242.  
  243. 	  while (underflows--)
  244. 	    writeBit((~low >> 14) & 1);
  245.  
  246. 	  while (resultUsed)
  247. 	    writeBit(0);
  248. 	}
  249. 	uint16_t* getStreamPos() const
  250. 	{
  251. 	  return stream;
  252. 	}
  253.       };
  254.  
  255.       void encoder()
  256.       {
  257. 	// Pass 1: calculate frequencies
  258. 	vector<uint16_t> freq(1024);
  259. 	uint16_t binary4 = 0;
  260. 	uint16_t binary12 = 0;
  261. 	Taylor lastTaylor;
  262.  
  263. 	for (size_t row = 0; row < NUM_ROWS; ++row)
  264. 	{
  265. 	  for (size_t col = 0; col < NUM_COLUMNS - 1; ++col)
  266. 	    { // last column is not encoded
  267. 	    Taylor taylor(my_array[row][col], lastTaylor);
  268. 	    int16_t fixup = taylor.d[0] - lastTaylor.predict();
  269.  
  270. 	    // Hack for values, jumping from -100 to 100
  271. 	    if (taylor.d[0] >= VALUE_LIMIT_POS && lastTaylor.d[0] < 0)
  272. 	      fixup -= 2 * taylor.d[0];
  273.  
  274. 	    // Value too big for arithmetic codec, use nibbles
  275. 	    if (fixup > INDEX_PLUS + NUM_BIN_OUTLIERS ||
  276. 		fixup < -ZERO_POS - NUM_BIN_OUTLIERS)
  277. 	    {
  278. 	      ++binary12;
  279. 	    }
  280. 	    else if (fixup > INDEX_PLUS || fixup < -ZERO_POS)
  281. 	    {
  282. 	      ++binary4;
  283. 	    }
  284.  
  285. 	    // Hack for values, jumping from -100 to 100
  286. 	    if (taylor.d[0] >= VALUE_LIMIT_POS && lastTaylor.d[0] < 0)
  287. 	    {
  288. 	      lastTaylor.negate();
  289. 	      taylor.update(lastTaylor);
  290. 	    }
  291.  
  292. 	    // This will be used to predict the next value
  293. 	    // (derivative is not updated for the first column)
  294. 	    lastTaylor.copyFrom(taylor, col? 3: 1);
  295.  
  296. 	    // Update table of frequencies
  297. 	    ++freq[512 + fixup];
  298. 	  }
  299. 	}
  300.  
  301. 	cout << "fixup: ";
  302. 	ostream_iterator<int> out_it (cout, " ");
  303. 	std::copy(freq.begin()+480, freq.end()-480, out_it);
  304. 	cout << "\n";
  305. 	cout << "binary4=" << binary4 << "\n";
  306. 	cout << "binary12=" << binary12 << "\n";
  307. 	cout << "-----------\n";
  308.  
  309. 	double bitsPerValue =
  310. 	  accumulate(freq.begin(), freq.end(), 0., Entropy(0));
  311.  
  312. 	cout
  313. 	  << " Entropy=" << NUM_VALUES * bitsPerValue / 8.
  314. 	  << " bits=" << bitsPerValue << "\n";
  315.  
  316. 	Entropy entropy(binary4 + binary12);
  317.  
  318. 	cout << "Static="
  319. 	     << 2 * (INDEX_FULL_SIZE +
  320. 		     (2 + binary4 + binary12*3 + 3) / 4)
  321. 	     << "\n";
  322.  
  323. 	// Add nibble frequencies
  324. 	freq[512 - ZERO_POS + INDEX_SIZE] = binary4;
  325. 	freq[512 - ZERO_POS + INDEX_SIZE + 1] = binary12;
  326.  
  327. 	bitsPerValue =
  328. 	  accumulate(freq.begin() + 512 - ZERO_POS,
  329. 		     freq.begin() + 512 - ZERO_POS + INDEX_FULL_SIZE,
  330. 		     0., entropy);
  331. 	cout
  332. 	  << "Entropy2=" << NUM_VALUES * bitsPerValue / 8.
  333. 	  << " bits=" << bitsPerValue << "\n";
  334.  
  335. 	// Pass 2: encode arithmetic coder bitstream & nibbles
  336. 	vector<uint16_t> compacted(1024);
  337.  
  338. 	// Cumulative sum of frequencies
  339. 	partial_sum(freq.begin() + 512 - ZERO_POS,
  340. 	     freq.begin() + 512 - ZERO_POS + INDEX_FULL_SIZE,
  341. 	     compacted.begin() + 1);
  342.  
  343. 	// Configure nibble writer
  344. 	uint16_t* pNibbles = &compacted[INDEX_FULL_SIZE + 1];
  345. 	uint16_t nibbles = (3 + binary4 + binary12*3 + 3) / 4;
  346. 	NibbleWriter nibbleWriter(pNibbles, nibbles);
  347. 	uint16_t* pData = pNibbles + nibbles;
  348.  
  349. 	// Configure arithmetic coder
  350. 	ArWriter arWriter(pData,
  351. 			  &compacted[1],
  352. 			  &compacted[1 + INDEX_FULL_SIZE]);
  353.  
  354. 	lastTaylor.clear();
  355.  
  356. 	for (size_t row = 0; row < NUM_ROWS; ++row)
  357. 	{
  358. 	  for (size_t col = 0; col < NUM_COLUMNS - 1; ++col)
  359. 	  { // last column is not encoded
  360. 	    Taylor taylor(my_array[row][col], lastTaylor);
  361. 	    int16_t fixup = taylor.d[0] - lastTaylor.predict();
  362.  
  363. 	    // Hack for values, jumping from -100 to 100
  364. 	    if (taylor.d[0] >= VALUE_LIMIT_POS && lastTaylor.d[0] < 0)
  365. 	      fixup -= 2 * taylor.d[0];
  366.  
  367. 	    // Value too big for arithmetic codec, use nibbles
  368. 	    if (fixup > INDEX_PLUS + NUM_BIN_OUTLIERS ||
  369. 		fixup < -ZERO_POS - NUM_BIN_OUTLIERS)
  370. 	    {
  371. 	      nibbleWriter.write12(fixup);
  372. 	      arWriter.write(INDEX_SIZE + BIN12);
  373. 	    }
  374. 	    else if (fixup > INDEX_PLUS || fixup < -ZERO_POS)
  375. 	    {
  376. 	      if (fixup > 0)
  377. 		nibbleWriter.write4(fixup - INDEX_PLUS - 1);
  378. 	      else
  379. 		nibbleWriter.write4((-fixup - ZERO_POS - 1) | 0x8);
  380.  
  381. 	      arWriter.write(INDEX_SIZE + BIN4);
  382. 	    }
  383. 	    else
  384. 	    {
  385. 	      arWriter.write(ZERO_POS + fixup);
  386. 	    }
  387.  
  388. 	    // Hack for values, jumping from -100 to 100
  389. 	    if (taylor.d[0] >= VALUE_LIMIT_POS && lastTaylor.d[0] < 0)
  390. 	    {
  391. 	      lastTaylor.negate();
  392. 	      taylor.update(lastTaylor);
  393. 	    }
  394.  
  395. 	    // This will be used to predict the next value
  396. 	    // (derivative is not updated for the first column)
  397. 	    lastTaylor.copyFrom(taylor, col? 3: 1);
  398. 	  }
  399. 	}
  400.  
  401. 	nibbleWriter.flush();
  402. 	arWriter.flush();
  403.  
  404. 	size_t size = arWriter.getStreamPos() - &compacted[0];
  405.  
  406. 	cout
  407. 	  << "ArEnc="
  408. 	  << (arWriter.getStreamPos() - pNibbles - nibbles) * 2
  409. 	  << "\nTotal=" << size * 2 << "\n---------\n";
  410.  
  411. 	for (size_t i = 0; i < size; i += 8)
  412. 	{
  413. 	  cout << "    " << hex << showbase;
  414. 	  ostream_iterator<int> out_it (cout, ", ");
  415.  
  416. 	  std::copy(compacted.begin() + i,
  417. 		    (i + 8 < size)?
  418. 		    compacted.begin() + i + 8: compacted.begin() + size,
  419. 		    out_it);
  420.  
  421. 	  cout << "\n";
  422. 	}
  423.       }
  424.  
  425.       int main()
  426.       {
  427. 	encoder();
  428. 	return 0;
  429.       }
  430.  
Success #stdin #stdout 0.01s 2864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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:
12 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!