In PCM audio processing, each sample is an integer of at most 32 bits. This blog post is about finding the number of bytes (octets) that can hold a sample, which is nontrivial when the number of bytes is restricted to match an integer type.
Easy case: 1, 2, 3, 4
The smallest number of bytes that can hold \(i\) bits is of course \(\lceil i/8 \rceil\). In programming, ceiling is usually not a native operation, but the floor of a division is, so the number of bytes is easier to compute as \(\lfloor (i+7)/8 \rfloor\):
(i+7)/8
If you, like me, learned the ropes around CPUs where division was a potential bottleneck, you might be tempted to replace the division by a power of two with a shift operation:
(i+7) >> 3
But any modern compiler would make this substitution, so there is no need to make the code harder to read in this way, unless you are writing Javascript or some other language where division is always in floating point, while shift produces an integer.
Interesting case: 1, 2, 4
When \(i\) is 17 to 24, \(\lfloor (i+7)/8 \rfloor\) is 3, which is sometimes what you want, but there is no integer data type with three bytes, so to compute the integer size, we need an expression that goes directly from 2 to 4 when \(i\) goes from 16 to 17. We could do:
i > 16 ? 4 : (i > 8 ? 2 : 1)
But I worry (perhaps unjustifiably) that the compiler might make this into a branch operation (an if-then-jump-else construct), and unlike division, branching is a bottleneck on current CPUs. It’s still fine as long as this computation is not in any tight loop (and it’s unlikely to be), but it’s an interesting exercise to find an expression that produces the right answer without any conditional.
Divide-and-compensate approach
The first working expression I came up with was 1 + i/9 + i/17*2 - i/18 - i/27, which probably needs an explanation. Let’s start from the beginning with a simplistic expression that is correct for the smallest numbers in the range:
1
This is correct up to \(i=8\), but starting from \(i=9\) we should add 1, which we can get as \(\lfloor i/9\rfloor\):
1 + i/9
This works up to \(i=16\), but at \(i=17\) we need to add 2, so add \(2\lfloor i/17\rfloor\):
1 + i/9 + i/17*2
(Placing *2 at the end rather than 2* at the beginning of the term avoids having to put a parenthesis around i/17.) But this goes wrong almost immediately, because i/9 is 2 for \(i=18\), making the experssion 3. So we compensate for this by subtracting \(\lfloor i/18\rfloor\):
1 + i/9 + i/17*2 - i/18
Now it comes out right all the way to \(i=26\), but at \(i=27\), i/9 turns 3, so we need to subtract another 1:
1 + i/9 + i/17*2 - i/18 - i/27
This works, but I wondered if it was possible to make it simpler. When I couldn’t come up with anything myself, I posted my expression on social media, asking if anyone could beat it.
And-by-one approach
The first useful comment came from my old fellow computer science student Lars, who started with this slightly cheaty expression:
1 + (1 > 8) + (i > 16)*2
This works in C, because a boolean value turns into 0 (false) or 1 (true) when treated as an integer. But I wanted it to work in Java, which doesn’t allow treating booleans as integers (and there is at least a microscopic chance that some compiler might produce branching code for the compare operations), so Lars did this:
1 + ((i-1)/8 & 1) + 3*((i-1)/16) - (i-1)/24
The last two terms use essentially the same idea as above, that \(\lfloor (i-1)/d\rfloor\) (for some \(d\)) is 0 for \(i\le d\) and 1 for \(d < i \le 2d\). The term before those introduces a bitwise and operation, and exploits the fact that x & 1 (for some \(x\)) is 1 if \(x\) is odd, and 0 if it’s even. It’s nice that the first two divisions are by powers of two, so they can be made into shift right. To get rid of the division by 24, we can add 8 to the nominator to push it to the next power of two, and divide by 32 instead. So a division-free version would be:
1 + ((i-1) >> 3 & 1) + 3*((i-1) >> 4) - ((i+7) >> 5)
This would be quite fast even on a RISC processor, since the compiler would know to eliminate the multiplication by 3 by computing \(3x\) (for some \(x\)) as x + (x << 1). But to a human reader, none of these expressions are simpler than my first attempt. As Lars pointed out: “This is awful code.”
Shift-left approach
An idea that led to more simplification came from my old colleague Thore, who pointed out that \(2^{\lfloor (i-1)/8\rfloor}\) goes immediately from 2 to 4 when \(i\) goes from 16 to 17, so this formula produces the right value up to \(i=24\). At \(i=25\) it turns 8, which we can compensate for by subtracting \(4\lfloor i/25\rfloor\) or, even simpler, we can subtract \(\lfloor i/25\rfloor\) from the exponent, ending up with \(2^{\lfloor (i-1)/8 \rfloor- \lfloor i/25\rfloor}\):
1 << (i-1)/8 - i/25
That’s rather pretty! A division-free version, using the same ideas as above, is
1 << ((i-1) >> 3) - ((i+7) >> 5)
but I would prefer the version with division unless this is in a critical loop. I don’t expect it to get any simpler than that, but if you come up with something, please write a comment below!
Update
Håkan came up with the arguably simpler 1 + 3/(32/i), see his comment!
Cliffhanger
There are more decisions than the integer size to make about sample representation: a sample can be a signed or unsigned integer; its byte sequence can be big- or little-endian; samples in the range 17 to 24 bits can be packed into three bytes or occupy four; unused bits can be in the most significant or least significant positions, and they can be set to 0 or 1.
How does audio processing software (and hardware) deal with these choices? The frustrating but interesting answer is: in all conceivable ways, including not at all!
For exploration of this fascinating topic, stay tuned to this blog! I have recently started going closer to the hardware in Klipspringer code, which has had me discover the sparsely documented ways that samples are stored and transferred, and how to convert between the various formats. You may have to wait a while for the next post, though, because I also have some compelling parts of programming left to do.
I thought of a solution with as few arithmetic operations as possible and implemented it in glorious 8-bit Z80 assembly.
The answers of 4, 2 or 1 are given by the following statements:
4 = and((i-1),16)>>2
2 = and(not(and((i-1),16)>>3),and((i-1),8)>>2)
1 = and(not(and((i-1),16)>>4),not(and((i-1),8)>>3)
Once those are processed just or them together.
The code will likely look like junk without formatting capabilities so have mercy.
To avoid arithmetic operations the input is 0-31 instead of 1-32. 🙂
The input is in B and the result is in A.
ld b, 31 ; n = n-1
;and((i-1),16)>>2
ld a, b
and 16
srl a ; >1
srl a ; >2
ld c, a ; 4: c = (and(n-1),16)>>2
;not(and((i-1),16)>>3
xor 4
srl a
ld d, a ; d = (not(and(n-1),16))>>3
;and((i-1),8)>>2
ld a, b
and 8
srl a ; >>1
srl a ; >>2
ld e, a ; e = (and(n-1),8)>>2
;not(and((i-1),8>>3
xor 2
srl a ; >>3
ld h, a ; h = not(and((i-1),8>>3
;and(not(and((i-1),16)>>3),and((i-1),8)>>2)
ld a, d ; (not(and(n-1),16))>>3
and e ; (and(n-1),8)>>2
ld l, a ; 2: l
;and(not(and((i-1),16)>>4),not(and((i-1),8)>>3)
ld a, d ; (not(and(n-1),16))>>3
srl a ; >>4
and h ; 1
or l ; 2
or c ; 4
I suppose there can be some optimisations to shave off some clock cycles but, as Donald Knuth wrote in The Art of Computer Programming:
“The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.”
/me 🧠³ | architect | problem solver | 8-bit geek | baker | historic reenactor
Cool! I think the remark about spending too much time worrying about efficiency is a bit uncalled for in this context, though, because that’s what we’re doing here in the first place, not because it’s necessary but because it’s fun! (What has discouraged me from hand-optimizing assembly code is that usually a compiler will do all that I come up with and more.)
The faster and shorter option when including comparisons and an arithmetic operation, with the input i-1 in A, is:
ld b,0
cp 16 ; carry flag is set to 0 if >=16 and 1 if <16
rl b ; rotate it into LSB of register b
cp 8 ; carry flag is set to 0 if >=8 and 1 if <8
rl b ; b is now %11 for a in [0,7], %10 for [8,15] %00 for [16,31]
ld a,4 ; guess what, the bits 100
sub b ; b is now %01 for a in [0,7], %10 for [8,15] %100 for inputs [16,31]
The following function was found using a symbolic regression program:
1 + 3 / (32 / i)
(The symbolic regression program is my Picat program http://hakank.org/picat/symbolic_regression.pi with the data file http://hakank.org/picat/symbolic_regression_jesper_bits.pi )
Nice! Looks simpler than the shift solution in human terms, but more difficult to RISC-optimize. I’m not sure which I prefer. And I wonder if it’s possible to get rid of the divisions here…