-
Notifications
You must be signed in to change notification settings - Fork 39
/
Copy pathStateTable.hpp
157 lines (148 loc) · 9.01 KB
/
StateTable.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#pragma once
#include "Random.hpp"
#include <cstdint>
/**
* State table:
* nex(state, 0) = next state if bit y is 0, 0 <= state < 256
* nex(state, 1) = next state if bit y is 1
* nex(state, 2) = number of zeros in bit history represented by state
* nex(state, 3) = number of ones represented
*
* States represent a bit history within some context.
* State 0 is the starting state (no bits seen).
* States 1-30 represent all possible sequences of 1-4 bits.
* States 31-252 represent a pair of counts, (n0,n1), the number
* of 0 and 1 bits respectively. If n0+n1 < 16 then there are
* two states for each pair, depending on if a 0 or 1 was the last bit seen.
* If n0 and n1 are too large, then there is no state to represent this
* pair, so another state with about the same ratio of n0/n1 is substituted.
* Also, when a bit is observed and the count of the opposite bit is large,
* then part of this count is discarded to favor newer data over old.
*/
class StateTable {
static constexpr uint8_t stateTable[256][4] = {
{ 1, 2, 0, 0},{ 3, 5, 1, 0},{ 4, 6, 0, 1},{ 7, 10, 2, 0}, // 0-3
{ 8, 12, 1, 1},{ 9, 13, 1, 1},{ 11, 14, 0, 2},{ 15, 19, 3, 0}, // 4-7
{ 16, 23, 2, 1},{ 17, 24, 2, 1},{ 18, 25, 2, 1},{ 20, 27, 1, 2}, // 8-11
{ 21, 28, 1, 2},{ 22, 29, 1, 2},{ 26, 30, 0, 3},{ 31, 33, 4, 0}, // 12-15
{ 32, 35, 3, 1},{ 32, 35, 3, 1},{ 32, 35, 3, 1},{ 32, 35, 3, 1}, // 16-19
{ 34, 37, 2, 2},{ 34, 37, 2, 2},{ 34, 37, 2, 2},{ 34, 37, 2, 2}, // 20-23
{ 34, 37, 2, 2},{ 34, 37, 2, 2},{ 36, 39, 1, 3},{ 36, 39, 1, 3}, // 24-27
{ 36, 39, 1, 3},{ 36, 39, 1, 3},{ 38, 40, 0, 4},{ 41, 43, 5, 0}, // 28-31
{ 42, 45, 4, 1},{ 42, 45, 4, 1},{ 44, 47, 3, 2},{ 44, 47, 3, 2}, // 32-35
{ 46, 49, 2, 3},{ 46, 49, 2, 3},{ 48, 51, 1, 4},{ 48, 51, 1, 4}, // 36-39
{ 50, 52, 0, 5},{ 53, 43, 6, 0},{ 54, 57, 5, 1},{ 54, 57, 5, 1}, // 40-43
{ 56, 59, 4, 2},{ 56, 59, 4, 2},{ 58, 61, 3, 3},{ 58, 61, 3, 3}, // 44-47
{ 60, 63, 2, 4},{ 60, 63, 2, 4},{ 62, 65, 1, 5},{ 62, 65, 1, 5}, // 48-51
{ 50, 66, 0, 6},{ 67, 55, 7, 0},{ 68, 57, 6, 1},{ 68, 57, 6, 1}, // 52-55
{ 70, 73, 5, 2},{ 70, 73, 5, 2},{ 72, 75, 4, 3},{ 72, 75, 4, 3}, // 56-59
{ 74, 77, 3, 4},{ 74, 77, 3, 4},{ 76, 79, 2, 5},{ 76, 79, 2, 5}, // 60-63
{ 62, 81, 1, 6},{ 62, 81, 1, 6},{ 64, 82, 0, 7},{ 83, 69, 8, 0}, // 64-67
{ 84, 71, 7, 1},{ 84, 71, 7, 1},{ 86, 73, 6, 2},{ 86, 73, 6, 2}, // 68-71
{ 44, 59, 5, 3},{ 44, 59, 5, 3},{ 58, 61, 4, 4},{ 58, 61, 4, 4}, // 72-75
{ 60, 49, 3, 5},{ 60, 49, 3, 5},{ 76, 89, 2, 6},{ 76, 89, 2, 6}, // 76-79
{ 78, 91, 1, 7},{ 78, 91, 1, 7},{ 80, 92, 0, 8},{ 93, 69, 9, 0}, // 80-83
{ 94, 87, 8, 1},{ 94, 87, 8, 1},{ 96, 45, 7, 2},{ 96, 45, 7, 2}, // 84-87
{ 48, 99, 2, 7},{ 48, 99, 2, 7},{ 88,101, 1, 8},{ 88,101, 1, 8}, // 88-91
{ 80,102, 0, 9},{103, 69,10, 0},{104, 87, 9, 1},{104, 87, 9, 1}, // 92-95
{106, 57, 8, 2},{106, 57, 8, 2},{ 62,109, 2, 8},{ 62,109, 2, 8}, // 96-99
{ 88,111, 1, 9},{ 88,111, 1, 9},{ 80,112, 0,10},{113, 85,11, 0}, // 100-103
{114, 87,10, 1},{114, 87,10, 1},{116, 57, 9, 2},{116, 57, 9, 2}, // 104-107
{ 62,119, 2, 9},{ 62,119, 2, 9},{ 88,121, 1,10},{ 88,121, 1,10}, // 108-111
{ 90,122, 0,11},{123, 85,12, 0},{124, 97,11, 1},{124, 97,11, 1}, // 112-115
{126, 57,10, 2},{126, 57,10, 2},{ 62,129, 2,10},{ 62,129, 2,10}, // 116-119
{ 98,131, 1,11},{ 98,131, 1,11},{ 90,132, 0,12},{133, 85,13, 0}, // 120-123
{134, 97,12, 1},{134, 97,12, 1},{136, 57,11, 2},{136, 57,11, 2}, // 124-127
{ 62,139, 2,11},{ 62,139, 2,11},{ 98,141, 1,12},{ 98,141, 1,12}, // 128-131
{ 90,142, 0,13},{143, 95,14, 0},{144, 97,13, 1},{144, 97,13, 1}, // 132-135
{ 68, 57,12, 2},{ 68, 57,12, 2},{ 62, 81, 2,12},{ 62, 81, 2,12}, // 136-139
{ 98,147, 1,13},{ 98,147, 1,13},{100,148, 0,14},{149, 95,15, 0}, // 140-143
{150,107,14, 1},{150,107,14, 1},{108,151, 1,14},{108,151, 1,14}, // 144-147
{100,152, 0,15},
// contexts representing strong trend of 0s or 1s start from here
{153, 95,16, 0},{154, 69,15, 1},{ 80,155, 1,15},{100,156, 0,16}, // 149-152
{157, 95,17, 0},{158, 69,16, 1},{ 80,159, 1,16},{100,160, 0,17}, // 153-156
{161, 95,18, 0},{162, 69,17, 1},{ 80,163, 1,17},{100,164, 0,18}, // 157-160
{165, 95,19, 0},{166, 69,18, 1},{ 80,167, 1,18},{100,168, 0,19}, // 161-164
{169, 95,20, 0},{170, 69,19, 1},{ 80,171, 1,19},{100,172, 0,20}, // 165-168
{173, 95,21, 0},{174, 69,20, 1},{ 80,175, 1,20},{100,176, 0,21}, // 169-172
{177, 95,22, 0},{178, 69,21, 1},{ 80,179, 1,21},{100,180, 0,22}, // 173-176
{181, 95,23, 0},{182, 69,22, 1},{ 80,183, 1,22},{100,184, 0,23}, // 177-180
{185, 95,24, 0},{186, 69,23, 1},{ 80,187, 1,23},{100,188, 0,24}, // 181-184
{189, 95,25, 0},{190, 69,24, 1},{ 80,191, 1,24},{100,192, 0,25}, // 185-188
{193, 95,26, 0},{194, 69,25, 1},{ 80,195, 1,25},{100,196, 0,26}, // 189-192
{197, 95,27, 0},{198, 69,26, 1},{ 80,199, 1,26},{100,200, 0,27}, // 193-196
{201, 95,28, 0},{202, 69,27, 1},{ 80,203, 1,27},{100,204, 0,28}, // 197-200
{205, 95,29, 0},{206, 69,28, 1},{ 80,207, 1,28},{100,208, 0,29}, // 201-204
// contexts with incremental counting start from here
{209, 95,30, 0},{210, 69,29, 1},{ 80,211, 1,29},{100,212, 0,30}, // 205-208
{213, 95,31, 0},{214, 69,30, 1},{ 80,215, 1,30},{100,216, 0,31}, // 209-212
{217, 95,32, 0},{218, 69,31, 1},{ 80,219, 1,31},{100,220, 0,32}, // 213-216
{221, 95,33, 0},{222, 69,32, 1},{ 80,223, 1,32},{100,224, 0,33}, // 217-220
{225, 95,34, 0},{226, 69,33, 1},{ 80,227, 1,33},{100,228, 0,34}, // 221-224
{229, 95,35, 0},{230, 69,34, 1},{ 80,231, 1,34},{100,232, 0,35}, // 225-228
{233, 95,36, 0},{234, 69,35, 1},{ 80,235, 1,35},{100,236, 0,36}, // 229-232
{237, 95,37, 0},{238, 69,36, 1},{ 80,239, 1,36},{100,240, 0,37}, // 233-236
{241, 95,38, 0},{242, 69,37, 1},{ 80,243, 1,37},{100,244, 0,38}, // 237-240
{245, 95,39, 0},{246, 69,38, 1},{ 80,247, 1,38},{100,248, 0,39}, // 241-244
{249, 95,40, 0},{250, 69,39, 1},{ 80,251, 1,39},{100,252, 0,40}, // 245-248
{249, 95,41, 0},{250, 69,40, 1},{ 80,251, 1,40},{100,252, 0,41}, // 249-252
{1,2, 0,0},{1,2, 0,0},{1,2, 0,0} // 253-255 are unused (and in case we reach such a state we'll need to restart)
};
static constexpr uint8_t stateGroup[256] = {
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14, // 0-14
18,23,24,24,26,25,27,26,26,25,27,26,28,28,29,15, //15-30
18,23,25,25,26,26,27,27,29,15, //31-40
18,23,25,24,25,26,26,27,28,27,29,15, //41-52
18,23,24,24,24,25,25,27,27,28,28,28,29,15, //53-66
19,22,24,23,24,25,25,26,26,27,27,28,29,28,30,16, //67-82
19,22,24,23,24,28,29,28,30,16, //83-92
19,22,24,23,24,28,29,28,30,16, //93-102
19,22,24,23,24,28,29,28,30,16, //103-112
19,22,24,23,24,28,29,28,30,16, //113-122
19,22,24,22,23,29,30,28,30,16, //123-132
19,22,23,22,23,29,30,29,30,16, //133-142
19,22, 0, 0,30,16, //143-148
19,22,30,16, 19,22,30,16, 19,22,30,16, 19,22,30,16, 19,22,30,16, //149-152 153-156 157-160 161-164 165-168
19,21,31,16, 19,21,31,16, 19,21,31,16, 19,21,31,16, 19,21,31,16, //169-172 173-176 177-180 181-184 185-188
19,21,31,16, 19,21,31,16, 19,21,31,16, 19,21,31,16, 19,21,31,17, //189-192 193-196 197-200 201-204 205-208
20,21,31,17, 20,21,31,17, 20,21,31,17, 20,21,31,17, 20,21,31,17, //209-212 213-216 217-220 221-224 225-228
20,21,31,17, 20,21,31,17, 20,21,31,17, 20,21,31,17, 20,21,31,17, //229-232 233-236 237-240 241-244 245-248
20,21,31,17, 0,0,0, //249-252 253-255
};
// this table needs tuning
static constexpr uint8_t statePrio[256] = {
0,1,1,2,2,2,2,5,3,3,3,3,3,3,5,
6,4,4,4,4,4,4,4,4,4,4,4,4,4,4,6, //15-30
9,7,7,7,7,7,7,7,7,9, //31-40
11,8,8,8,8,8,8,8,8,8,8,11, //41-52
13,10,10,10,10,10,10,10,10,10,10,10,10,13, //53-66
15,12,12,12,12,12,12,12,12,12,12,12,12,12,12,15, //67-82
17,14,14,14,14,14,14,14,14,17, //83-92
19,16,16,16,16,16,16,16,16,19, //93-102
21,18,18,18,18,18,18,18,18,21, //103-112
23,20,20,20,20,20,20,20,20,23, //113-122
25,22,22,22,22,22,22,22,22,25, //123-132
27,24,24,24,24,24,24,24,24,27, //133-142
29,26, 0, 0,26,29, //143-148
31,28,28,31, 33,30,30,33, 35,32,32,35, 37,34,34,37, 39,36,36,39, //149-152 153-156 157-160 161-164 165-168
41,38,38,41, 43,40,40,43, 45,42,42,45, 47,44,44,47, 49,46,46,49, //169-172 173-176 177-180 181-184 185-188
51,48,48,51, 53,50,50,53, 55,52,52,55, 57,54,54,57, 59,56,56,59, //189-192 193-196 197-200 201-204 205-208
61,58,58,61, 63,60,60,63, 65,62,62,65, 67,64,64,67, 69,66,66,69, //209-212 213-216 217-220 221-224 225-228
71,68,68,71, 73,70,70,73, 75,72,72,75, 77,74,74,77, 79,76,76,79, //229-232 233-236 237-240 241-244 245-248
81,78,78,81, 0,0,0, //249-252 253-255
};
public:
static uint8_t getNextState(uint8_t state, int y);
/**
* Next state with probabilistic increment
* @param oldState
* @param y
* @param rnd
* @return
*/
static uint8_t getNextState(uint8_t oldState, int y, Random &rnd);
static void update(uint8_t *state, int y, Random &rnd);
static uint8_t group(uint8_t state) ;
static uint8_t prio(uint8_t state);
};