The Voss-McCartney algorithm in Rust lang

The implementation to the Voss McCartney algorithm to generating Pink Noise is shown here. At first, I haven’t really understood it because it was quite vague. I went searching for answers in forums, and I had to piece together bits of knowledge to get a grasp of the algorithm. In this article, I will make it so that you don’t have to do that.

I will use rust for code examples, you can see the original algorithm implemented in c here.

const PINK_RANDOM_BITS: usize = 24;
const PINK_RANDOM_SHIFT: usize = (std::mem::size_of::<i32>() * 8) - PINK_RANDOM_BITS;

pub struct PinkNoiseGenerator {
    rows: Vec<f32>,
    running_sum: f32,
    index: usize,
    index_mask: usize,
    scalar: f32,
}

impl PinkNoiseGenerator {
    pub fn new(num_rows: usize) -> Self {
        let index_mask = (1 << num_rows) - 1;
        let pmax = (num_rows + 1) * (1 << (PINK_RANDOM_BITS - 1));
        let rows = vec![0.0; num_rows];
        Self {
            rows,
            running_sum: 0.0,
            index: 0,
            index_mask,
            scalar: 1.0 / pmax as f32,
        }
    }

    pub fn sample(&mut self) -> f32 {
        self.index = (self.index + 1) & self.index_mask;

        if self.index != 0 {
            let mut num_zeros = 0;
            let mut n = self.index;
            while (n & 1) == 0 {
                n >>= 1;
                num_zeros += 1;
            }

            self.running_sum -= self.rows[num_zeros];
            let new_random = (fastrand::u32(..) >> PINK_RANDOM_SHIFT) as f32;
            self.running_sum += new_random;
            self.rows[num_zeros] = new_random;
        }

        let new_random = (fastrand::u32(..) >> PINK_RANDOM_SHIFT) as f32;
        let sum = self.running_sum + new_random;
        self.scalar * sum - 1.0
    }
}

I’ll dissect this code step by step, but the most important part of this code is the sample() function.

let mut num_zeros = 0;
let mut n = self.index;
while (n & 1) == 0 {
    n >>= 1;
    num_zeros += 1;
}

The algorithm works by updating samples at different layers of samples at different times. Basically, the algorithm takes existing random values and stacks random values on top of it, with some updated more frequently than others.

The code above, counts number of zeroes in the index digit. For example, when you count up, you reach 1 zero every time you count 10. And then again. This might sound confusing, but it is crucial to understanding the algorithm.

To help, visually, it will be updated like this:

x x x x x x x x x x x x x x x x
 x   x   x   x   x   x   x   x
   x       x       x       x
       x               x
               x

The algorithm does sum completely separate random values at once otherwise there would be inconsistencies. Say, in one scenario, you generate 1, 1, 1, 1, 1 and on the other you get 0, 0, 0, 0, 0. That may not seem like a big difference, but when you’ll hear it.

if self.index != 0 {
    let mut num_zeros = 0;
    let mut n = self.index;
    while (n & 1) == 0 {
        n >>= 1;
        num_zeros += 1;
    }

    self.running_sum -= self.rows[num_zeros];
    let new_random = (fastrand::u32(..) >> PINK_RANDOM_SHIFT) as f32;
    self.running_sum += new_random;
    self.rows[num_zeros] = new_random;
}

The running sum then subtracts the previous value in the same layer (aka row). The running sum subtracts the previous value so that it doesn’t add up / stack and you can safely place a new random value. The new random is bitshifted by PINK_RANDOM_SHIFT for efficiency.

pub fn sample(&mut self) -> f32 {
    self.index = (self.index + 1) & self.index_mask;

    if self.index != 0 {
        let mut num_zeros = 0;
        let mut n = self.index;
        while (n & 1) == 0 {
            n >>= 1;
            num_zeros += 1;
        }

        self.running_sum -= self.rows[num_zeros];
        let new_random = (fastrand::u32(..) >> PINK_RANDOM_SHIFT) as f32;
        self.running_sum += new_random;
        self.rows[num_zeros] = new_random;
    }

    let new_random = (fastrand::u32(..) >> PINK_RANDOM_SHIFT) as f32;
    let sum = self.running_sum + new_random;
    self.scalar * sum - 1.0
}

They add that random value to the running_sum, then they create another new random and add that to the running sum again. This is to add extra white noise value, possibly for quality purposes.

That is all.

---

Try it out here: https://nate10j.github.io/colorful-ambience/app

https://github.com/nate10j/colorful-ambience/blob/main/noise_generator/src/pink_noise_generator.rs