A few weekends ago, I decided to break my hiatus of recreational programming and play a bit with Serenity OS. What I decided to play with was the SoundPlayer application, to avoid working on the kind of stuff that I'm usually drawn to – and learn a few things in the process.
The first thing I ended up doing was implementing the necessary to load and apply an WinAmp skin to the SoundPlayer application. Serenity OS's GUI is very inspired by the Windows interfaces from mid-to-late 90s, so having a skinnable sound player kind of makes sense.
This isn't really WinAmp, but SoundPlayer masquerading as one
This was surprisingly easy to do, even for someone that's not familiar with C++: the libraries are well-designed, and for someone that spent a lot of time writing GTK+ and EFL applications in the past, they were a joy to use.
The lack of comprehensive documentation is made up by the clear implementation, coherent style, and lack of third-party libraries; if just reading the headers isn't sufficient to understand an API, it's usually sufficient to just grep around. APIs often work the way you expect them to, and if they don't, the code is just a hop away. Changing some things in the system is also trivial, as everything is developed under the same hood.
While there's a lot of work to be done to have a completely skinned SoundPlayer application that works and functions as the quintessential 90s music player, I ended up doing some peripheral work in the application to prepare it for the task ahead.
After refactoring and cleaning up the code, I started implementing one of the things I'd need; today I'd like to talk about the playlist, more specifically about its ability to play entries in a random order.
There are many articles out there explaining how to create a good playlist shuffling feature, that balances not using a lot of memory and still managing avoiding repeating recently played songs. None of the ones I found does it the way I ended up implementing it; hence this blog post.
Instead of modifying the playlist itself (with something like Fisher-Yates shuffle), or having a set with the most recently played titles, I ended up using a Bloom Filter.
Bloom Filters are one of those data structures that once you learn about them, you desperately want to use them for something – probabilistic data structures aren't that common, and those that aren't as trivially implementable even less so. After a while, you realize that its uses are very limited, and you're usually better off without it.
For a playlist, however, it makes sense to use one: it doesn't require precision (if a song ends up being repeated, it's not the end of the world), and it doesn't require a lot of memory for its state. This is the version I wrote for Serenity:
class BloomFilter {
public:
void reset()
{
m_bitmap = 0;
}
void add(const StringView key)
{
m_bitmap |= mask_for_key(key);
}
bool maybe_contains(const StringView key) const
{
auto mask = mask_for_key(key);
return (m_bitmap & mask) == mask;
}
private:
u64 mask_for_key(StringView key) const
{
auto key_chars = key.characters_without_null_termination();
auto hash1 = string_hash(key_chars, key.length(), 0xdeadbeef);
auto hash2 = string_hash(key_chars, key.length(), 0xbebacafe);
return 1ULL << (hash1 & 63) | 1ULL << (hash2 & 63);
}
u64 m_bitmap { 0 };
};
With something like this, it's possible to write an algorithm that tries getting a new song to play a few times, and checking if it's definitely not in the "previously played" bloom filter. If it's not there, then that can be returned; if it's probably there, try again before giving up and ultimately resetting the Bloom Filter and starting all over again. Something like this:
auto next = m_model->items().at(m_next_index_to_play).path;
if (!shuffling()) {
m_next_index_to_play++;
return next;
}
int shuffle_try;
int const max_times_to_try = min(4, size());
for (shuffle_try = 0; shuffle_try < max_times_to_try; shuffle_try++) {
if (!m_previously_played_paths.maybe_contains(next))
break;
m_next_index_to_play = get_random_uniform(size());
next = m_model->items().at(m_next_index_to_play).path;
}
if (shuffle_try == max_times_to_try) {
// If we tried too much, maybe it's time to try resetting
// the bloom filter and start over.
m_previously_played_paths.reset();
}
m_previously_played_paths.add(next);
return next;
Right now, the only thing that ends up in the Bloom Filter is the song filename, but other things could be added here as well, such as any of the metadata from the audio files themselves (e.g. you could make something that tried to play things released in different years, shuffling on genres, try hard to play things from different artits, you name it.) For now, this does the job quite nicely.
I'm quite happy with the result, especially because this is cheap (only 64 bits of state!), it is efficient, and works as I expected it to. It's also trivial to expand as the need grows. On top of it all, I finally got to solve a problem using a bloom filter.
I intend to implement other things in the SoundPlayer application, including an equalizer, which I'm pretty excited about – I've never done any kind of audio processing before. I do remember some things from university related to signal processing, and so far they've been quite helpful, but I've been reading a few things after work and a lot of it is still going way over my head.