September 6, 2016
Quite a while ago I discussed using flat arrays and address calculations to store a tree in a simple array. The trick wasn’t new (I think it’s due to Williams, 1964 [1]), but is only really practical when we consider heaps, or otherwise very well balanced trees. If you have a misshapen tree, that trick doesn’t help you. It doesn’t help you either if you try to serialize a misshapen tree to disk.

But what if we do want to serialize arbitrarily-shaped trees to disk? Is it painful? Fortunately, no! Let’s see how.

Read the rest of this entry »

Leave a Comment » | algorithms, C-plus-plus, data structures, programming | Tagged: bit, C, Deserialization, Pointers, serialization, Standish, Tree | Permalink

Posted by Steven Pigeon

April 5, 2016
I am still experimenting with hash functions, and I was toying with the Zobrist hash function[1] that is best known for its use in chess engines. The hash function is conceptually simple: you need a large table of random numbers, indexed, in a chess application, by the position on the board of the piece and by the piece itself. To compute a hash for a whole board configuration, you simply xor all the random numbers together. The hard part is choosing the random numbers.

Read the rest of this entry »

Leave a Comment » | C-plus-plus, Cryptography, programming | Tagged: /dev/urandom, hash, hash function, pseudo-random number generator, random, Zobrist | Permalink

Posted by Steven Pigeon

March 29, 2016
Last week, we had a look at the computation of Log2 using templates and `constexpr`. Of course, I had ulterior motives. In particular, I was interested in allocating just the right number of bits for a field in a bit field, but rather than hard-coding it, having it deduced from a template argument. Let’s see how we can do that.

Read the rest of this entry »

Leave a Comment » | C-plus-plus | Tagged: Bits, storage, template, template argument, uint16_t, uint32_t, uint64_t, uint8_t | Permalink

Posted by Steven Pigeon

March 22, 2016
C++ meta-programming a powerful tool. Not only can you use it to build generic types (such as the STL’s `std::list`), you can also use it to have compile-time evaluation. Let’s have a look at a simple problem that can be solved in two very different ways: computing the Log base 2 of an integer.

Read the rest of this entry »

3 Comments | algorithms, C-plus-plus | Tagged: Bits, C, C++11, Log2, template, template argument, typename | Permalink

Posted by Steven Pigeon