In-place sequence de-interleaving

deinterleave.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// In response to watching Casey Muratori think about in-place de-interleaving of audio samples
// in Handmade Hero ep 138, here's a solution for sequences with power-of-two length.
// 
// Algorithm swaps the 2 internal elements in blocks of 4 elems, then grows block size to 8, 16, etc
// For example, for a sequence of length 8:
// a,1,b,2,c,3,d,4 --> a,b,1,2,c,d,3,4 --> a,b,c,d,1,2,3,4
//            blockSize = 4       blockSize = 8

void swap(int *a, int *b) {
    int t = *b;
    *b = *a;
    *a = t;
}

void reverseSequence(int *seq, int seqLen, int elemsPerBlock) {
    assert((elemsPerBlock % 4) == 0); // This should actually check that elemsPerBlock is POT, but oh well

    for(int i = 0; i < seqLen / elemsPerBlock; i++) {
        int start = i * elemsPerBlock;
        for(int j = 0; j < elemsPerBlock / 4; j++) {
            swap(seq + start + elemsPerBlock / 4 + j, seq + start + elemsPerBlock / 2 + j);
        }
    }
}

int main() {

    int numCnt = 1024;

    int *nums = (int *)malloc(sizeof(int) * numCnt);
    for(int i = 0; i < numCnt; i++) {
        nums[i] = i;
    }

    int chunkSize = 4;
    while(chunkSize <= numCnt) {
        reverseSequence(nums, numCnt, chunkSize);
        chunkSize *= 2;
    }

    for(int i = 0; i < numCnt; i++) {
        printf((nums[i] % 2) ? "R%04d, " : "L%04d, ", nums[i] / 2);
        if((i + 1) % 8 == 0) {
            printf("\n");
        }
    }

    return 0;
}