| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <stdint.h> | |
| #include <string.h> | |
| #include <smmintrin.h> | |
| #ifdef __RADAVX__ | |
| #include <immintrin.h> | |
| #endif |
| // Returns 8 bit fields at the given positions (in bits) and of the | |
| // given widths as 16-bit integers, with the values aligned with the | |
| // MSB at the top and garbage in the lower-order bits. | |
| // | |
| // The individual lens must be <=8, the positions are bit offsets | |
| // into the 128-bit "bytes". | |
| template< | |
| int pos0, int len0, | |
| int pos1, int len1, | |
| int pos2, int len2, |
| // if 'f' is the 64-bit input CRC32-C (with 'incoming' 32-bit value of zero) then | |
| // there are 50 bijections (invertiable functions) which are a sum of f | |
| // and a simple xorshift. So the follow two forms: | |
| // | |
| // f(x) ^ (x ^ (x << S)) | |
| // f(x) ^ (x ^ (x >> S)) | |
| // | |
| // and 23 using a rotate instead of a shift: | |
| // |
A traditional table-based DFA implementation looks like this:
uint8_t table[NUM_STATES][256]
uint8_t run(const uint8_t *start, const uint8_t *end, uint8_t state) {
for (const uint8_t *s = start; s != end; s++)
state = table[state][*s];
return state;
}
| // We have five kinds of nodes: literal, negate, not, add, xor. | |
| // In this case we only need 3 bits for the tag but you can use as many as you need. | |
| enum Tag { | |
| LIT, | |
| NEG, | |
| NOT, | |
| ADD, | |
| XOR, | |
| }; |
| # Hash, displace, and compress: http://cmph.sourceforge.net/papers/esa09.pdf | |
| # This is expected linear time for any seeded hash function that acts like a random hash function (universality isn't enough). | |
| # (Actually, the code as written is O(n log n) when targeting 100% load. It's O(n) when targeting any smaller load factor.) | |
| # You can make keys_per_bucket higher than the default of 4 but construction time will start to increase dramatically. | |
| # The paper this is based on compresses the seeds (so the fact that the algorithm tries seeds in increasing order is important) | |
| # which brings the representation size close to the information-theoretical minimum. I don't do any of that here, but it could | |
| # be done as a postprocess. | |
| def make_perfect_hash(keys, load_factor=1.0, keys_per_bucket=4, rhash=murmurhash, max_seed=1000000): | |
| m = int(len(keys) / load_factor) | |
| r = int(len(keys) / keys_per_bucket) |
| # Here's a probably-not-new data structure I discovered after implementing weight-balanced trees with | |
| # amortized subtree rebuilds (e.g. http://jeffe.cs.illinois.edu/teaching/algorithms/notes/10-scapegoat-splay.pdf) | |
| # and realizing it was silly to turn a subtree into a sorted array with an in-order traversal only as an | |
| # aid in constructing a balanced subtree in linear time. Why not replace the subtree by the sorted array and | |
| # use binary search when hitting that leaf array? Then you'd defer any splitting of the array until inserts and | |
| # deletes hit that leaf array. Only in hindsight did I realize this is similar to the rope data structure for strings. | |
| # Unlike ropes, it's a key-value search tree for arbitrary ordered keys. | |
| # | |
| # The main attraction of this data structure is its simplicity (on par with a standard weight-balanced tree) and that it | |
| # coalesces subtrees into contiguous arrays, which reduces memory overhead and boosts the performance of in-order traversals |
A couple of weeks ago I played (and finished) A Plague Tale, a game by Asobo Studio. I was really captivated by the game, not only by the beautiful graphics but also by the story and the locations in the game. I decided to investigate a bit about the game tech and I was surprised to see it was developed with a custom engine by a relatively small studio. I know there are some companies using custom engines but it's very difficult to find a detailed market study with that kind of information curated and updated. So this article.
Nowadays lots of companies choose engines like Unreal or Unity for their games (or that's what lot of people think) because d
TL;DR: play as long as you can without help, until you get frustrated. At that point, the recommended region order helps a lot without spoiling anything but region names. If you can't find the next region, the world map (only showing region connections, no detail) will tell you what direction to look in.
Rain World is a masterpiece — equal parts metroidvania, movement puzzler, immersive rat in Manhattan sim — but its strangeness makes it hard to appreciate. Some things that turned players and reviewers off were fixed in [patches](https:/
| // Baseline version without prefetch | |
| static const LRMEntry * lrm_search_one_basic(const LRM * lrm, const U8 * ptr) | |
| { | |
| LRM_hash_t hash = lrm_hash8(ptr); | |
| // Jump-in: narrow down the search interval using the jump table | |
| LRM_hash_t ji = hash >> lrm->jumpInShift; | |
| S32 jump1 = lrm->jumpIn[ji]; | |
| S32 jump2 = lrm->jumpIn[ji + 1]; |