113 std::vector<CompactEntry> compactEntries;
114 std::vector<FullEntry> fullEntries;
115 std::vector<IndexEntry> indices;
116 for (
size_t s = 0;
s < states; ++
s) {
120 TransitionSet transitionSet;
121 std::vector<int> data(numTransitions);
122 for (
int t = 0; t < numTransitions; ++t) {
127 transitionSet.insert(
value);
131 transitionSet.erase(0);
132 if (transitionSet.size() <= kNumValues) {
135 int index = add_compact_entry(transitionSet, data, &compactEntries);
136 indices.push_back(IndexEntry{kCompactEntry, index});
139 int index = add_full_entry(transitionSet, data, &fullEntries);
140 indices.push_back(IndexEntry{kFullEntry, index});
146 for (
const CompactEntry& entry : compactEntries) {
147 for (
int index=0; index < kNumValues; ++index) {
148 maxValue = std::max(maxValue, entry.v[index]);
153 int bitsPerValue = std::ceil(std::log2(maxValue));
154 maxValue = (1 << bitsPerValue) - 1;
158 assert(bitsPerValue <= 10);
161 out <<
"using IndexEntry = int16_t;\n"
162 <<
"struct FullEntry {\n"
163 <<
" State data[" << numTransitions <<
"];\n"
168 static_assert(kNumBits == 2);
169 out <<
"struct CompactEntry {\n"
170 <<
" uint32_t values;\n"
171 <<
" uint8_t data[" << std::ceil(
float(numTransitions) /
float(kDataPerByte)) <<
"];\n"
175 out <<
"static constexpr FullEntry kFull[] = {\n";
176 for (
const FullEntry& entry : fullEntries) {
178 for (
int value : entry.data) {
179 out <<
value <<
", ";
186 out <<
"static constexpr CompactEntry kCompact[] = {\n";
187 for (
const CompactEntry& entry : compactEntries) {
192 static_assert(kNumBits == 2);
195 out <<
" | (" << entry.v[1] <<
" << " << bitsPerValue <<
")";
198 out <<
" | (" << entry.v[2] <<
" << " << (2 * bitsPerValue) <<
")";
202 unsigned int shiftBits = 0, combinedBits = 0;
203 for (
int index = 0; index < numTransitions; index++) {
204 combinedBits |= entry.data[index] << shiftBits;
205 shiftBits += kNumBits;
206 assert(shiftBits <= 8);
207 if (shiftBits == 8) {
208 out << combinedBits <<
", ";
220 <<
"static constexpr IndexEntry kIndices[] = {\n";
221 for (
const IndexEntry& entry : indices) {
222 if (entry.type == kFullEntry) {
224 out << ~entry.pos <<
", ";
227 out << entry.pos <<
", ";
231 <<
"static State get_transition(uint8_t transition, State state) {\n"
232 <<
" IndexEntry index = kIndices[state];\n"
233 <<
" if (index < 0) { return kFull[~index].data[transition]; }\n"
234 <<
" const CompactEntry& entry = kCompact[index];\n"
235 <<
" int v = entry.data[transition >> " << std::log2(kDataPerByte) <<
"];\n"
236 <<
" v >>= " << kNumBits <<
" * (transition & " << kDataPerByte - 1 <<
");\n"
237 <<
" v &= " << kNumValues <<
";\n"
238 <<
" v *= " << bitsPerValue <<
";\n"
239 <<
" return (entry.values >> v) & " << maxValue <<
";\n"