fork(1) download
copy 
  1. #include <iostream>
  2. #include <numeric>
  3. #include <cstdlib> 
  4. #include <cstddef>
  5. #include <stdint.h>
  6.  
  7. enum {
  8.   // Config
  9.   ZERO_POS = 2,
  10.   INDEX_SIZE = 5,
  11.   VALUE_LIMIT = -100,
  12.  
  13.   // Constants// http://w...content-available-to-author-only...s.com/ac_arithmetic.html
  14. 	uint16_t* stream;
  15. 	uint16_t* table;
  16. 	uint16_t* tableEnd;
  17. 	uint16_t high;
  18. 	uint16_t low;
  19. 	uint16_t code;
  20. 	uint16_t source;
  21. 	uint16_t sourceUsed;
  22.       public:
  23. 	ArReader(uint16_t* p, uint16_t* t, uint16_t* e)
  24. 	: stream(p + 1)
  25. 	, table(t) // Zero value in *(t-1) expected
  26. 	, tableEnd(e)
  27. 	, high(0xFFFF)
  28. 	, low(0)
  29. 	, code(*p)
  30. 	, source(0)
  31. 	, sourceUsed(0)
  32. 	{}
  33. 	uint16_t read()
  34. 	{
  35. 	  uint32_t range = static_cast<uint32_t>(high) - low + 1;
  36.  
  37. 	  uint16_t temp =
  38. 	    ((static_cast<uint32_t>(code) - low + 1) * *(tableEnd - 1) - 1) /
  39. 	    range;
  40.  
  41. 	  uint16_t result = searchTable(temp);
  42. 	  high = low + ((range * table[result]) / *(tableEnd - 1)) - 1;
  43. 	  low = low + (range * table[result - 1]) / *(tableEnd - 1);
  44.  
  45. 	  while (true) {
  46. 	    if ((high ^ low) & 0x8000) // different msb
  47. 	    {
  48. 	      if ((high & 0x4000) < (low & 0x4000))
  49. 	      {
  50. 		code ^= 0x4000;
  51. 		low &= 0x3FFF;
  52. 		high |= 0x4000;
  53. 		shift();
  54. 	      }
  55. 	      else
  56. 	      {
  57. 		break;
  58. 	      }
  59. 	    }
  60. 	    else // equal msb
  61. 	    {
  62. 	      shift();
  63. 	    }
  64. 	  }
  65.  
  66. 	  return result;
  67. 	}
  68. 	uint16_t searchTable(uint16_t x)
  69. 	{
  70. 	  uint16_t* p = table;
  71. 	  while (x >= *p)
  72. 	    ++p;
  73. 	  return p - table;
  74. 	}
  75. 	void shift()
  76. 	{
  77. 	  low <<= 1;
  78. 	  high <<= 1;
  79. 	  high |= 1;
  80. 	  code <<= 1;
  81. 	  code |= readBit();
  82. 	}
  83.         uint16_t readBit()
  84. 	{
  85. 	  if (sourceUsed == 0)
  86. 	    load();
  87.  
  88. 	  return (source >> --sourceUsed) & 1;
  89. 	}
  90. 	void load()
  91. 	{
  92. 	  source = *stream++;
  93. 	  sourceUsed = 16;
  94. 	}
  95.       };
  96.  
  97.       int16_t get(size_t r, size_t c)
  98.       {
  99. 	if (c == NUM_COLUMNS - 1)
  100. 	  c = 0; // last column is equal to the first one
  101.  
  102. 	Taylor lastTaylor;
  103. 	NibbleReader nibbleReader(compacted + 1 + INDEX_FULL_SIZE);
  104.  
  105. 	ArReader
  106. 	  arReader(compacted + 1 + INDEX_FULL_SIZE + nibbleReader.read12(),
  107. 		   compacted + 1,
  108. 		   compacted + 1 + INDEX_FULL_SIZE);
  109.  
  110. 	for (size_t row = 0; row < NUM_ROWS; ++row)
  111. 	{
  112. 	  for (size_t col = 0; col < NUM_COLUMNS - 1; ++col)
  113. 	  { // last column is not encoded
  114. 	    uint16_t value = arReader.read();
  115. 	    int16_t fixup = static_cast<int16_t>(value) - ZERO_POS;
  116.  
  117. 	    // Value was encoded in nibbles
  118. 	    if (value == INDEX_SIZE + BIN4)
  119. 	    {
  120. 	      uint16_t x16 = nibbleReader.read4();
  121.  
  122. 	      if (x16 & 0x8)
  123. 		fixup = -ZERO_POS - 1 - (x16 & ~0x8);
  124. 	      else
  125. 		fixup = INDEX_PLUS + 1 + x16;
  126. 	    }
  127. 	    else if (value == INDEX_SIZE + BIN12)
  128. 	    {
  129. 	      fixup = static_cast<int16_t>(nibbleReader.read12());
  130. 	      fixup |= -(fixup & (1 << 11));
  131. 	    }
  132.  
  133. 	    // Restore original value (extrapolate and add a correction)
  134. 	    Taylor taylor(lastTaylor.predict() + fixup, lastTaylor);
  135.  
  136. 	    // Hack for values, jumping from -100 to 100
  137. 	    if (taylor.d[0] <= VALUE_LIMIT)
  138. 	    {
  139. 	      taylor.d[0] = -taylor.d[0];
  140. 	      lastTaylor.negate();
  141. 	      taylor.update(lastTaylor);
  142. 	    }
  143.  
  144. 	    // Got the result
  145. 	    if (row == r && col == c)
  146. 	      return taylor.d[0];
  147.  
  148. 	    // This will be used to predict the next value
  149. 	    // (derivative is not updated for the first column)
  150. 	    lastTaylor.copyFrom(taylor, col? 3: 1);
  151. 	  }
  152. 	}
  153.  
  154. 	return 0; // Out of range
  155.       }
  156.  
  157.       int main()
  158.       {
  159. 	for (int row = 0; row < NUM_ROWS; ++row)
  160. 	  for (int col = 0; col < NUM_COLUMNS; ++col)
  161. 	    if (get(row, col) != my_array[row][col])
  162. 	    {
  163. 	      cerr
  164. 		<< "Mismatch in row " << row << ", column " << col
  165. 		<< "; got " << get(row, col)
  166. 		<< ", must be " << my_array[row][col]
  167. 		<< "\n";
  168. 	      exit(1);
  169. 	    }
  170.  
  171. 	return 0;
  172.       }
  173.  
Success #stdin #stdout 0.42s 2724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xJ9QI
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!