Skip to content

Instantly share code, notes, and snippets.

@uucidl uucidl/00ctztree.md
Last active Oct 24, 2018

Embed
What would you like to do?
Octave Tree

CTZTree

A tree can be produced by counting the number of trailing zeros from an input integer index.

This count ('c') of trailing zeros (or position of the lowest bit) comes back every 2^c sample, i.e. corresponds to a frequency of 2^-c

Furthermore every sample corresponds with one and only one octave.

I first encountered this contruction in pink noise generator in audio, using this tree of octaves to downsample a source of white noise into many down-octaves with a gain of 2^{-Octave}

One advantage is that the downsampled octaves pull from the white noise generator at most once per sample, so there's an even load on the generator and no "bursts" of randomness.

//
// A tree can be produced by counting the number of trailing zeros
// from an input integer index.
//
// This count ('c') of trailing zeros (or position of the lowest bit)
// comes back every 2^c sample, i.e. corresponds to a frequency of 2^-c
//
// Furthermore every sample corresponds with one and only one octave.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
// Example C standard implementation, replace with your favorite
// compiler's intrinsic or the CTZ/BSF instruction of your target
// CPU.
int count_trailing_zeros(unsigned int x) {
int c = 0;
for (int o = 0; o < sizeof(unsigned int)*8; o++) {
unsigned int mask = 1U << o;
if (x & mask) break;
c++;
}
return c;
}
int globals_length = 16;
int parse_args(int argc, char **argv);
int main(int argc, char **argv) {
if (parse_args(argc, argv) < 0) {
return -1;
}
int const length = globals_length;
for (int x = 0; x < length; x++) {
int y = count_trailing_zeros(x + 1);
printf("%0*x:%0*x %*sx\n", 4, x, 4, y, y, "");
}
}
int parse_args(int argc, char **argv)
{
int argi = 1;
if (argi != argc) {
if (argv[argi][0] == '-') {
fprintf(stderr, "USAGE: %s <length>\n", argv[0]);
}
}
if (argi != argc) {
char *end;
long y = strtol(argv[argi], &end, 10);
if (y < 0) {
fprintf(stderr, "ERROR:%s:argv[%d]:length: expected positive number\n", argv[0], argi);
return -1;
} else if (y > INT_MAX) {
fprintf(stderr, "ERROR:%s:argv[%d]:length: too large number\n", argv[0], argi);
return -1;
}
globals_length = (int) y;
argi++;
}
if (argi != argc) {
fprintf(stderr, "ERROR:%s:argv[%d]: too many arguments\n", argv[0], argi);
}
return 0;
}
nicolass-mini:CTZTree nicolas$ ./ctztree 16
0000:0000 x
0001:0001 x
0002:0000 x
0003:0002 x
0004:0000 x
0005:0001 x
0006:0000 x
0007:0003 x
0008:0000 x
0009:0001 x
000a:0000 x
000b:0002 x
000c:0000 x
000d:0001 x
000e:0000 x
000f:0004 x
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.