TODO 2020-07-17: tidy up this Gist. Binary search for size in bits adapted from source code for WebRTC project.
import numpy as np
import matplotlib.pyplot as plt
def log2Q10_xQ12(x_Q12):
"""
Using the approximation log2(1 + x) ~= x for 1 <= x < 2:
- | x_frac = x_Q12 & 0xFFF
- | x = (2 ** -lshifts) * (2 ** 12 + x_frac)
- | => log2(x) = -lshifts + log2(2 ** 12 + x_frac)
- | = -lshifts + log2(2 ** 12 * (1 + x_frac * 2 ** -12))
- | = -lshifts + 12 + log2(1 + x_frac * 2 ** -12)
- | ~= -lshifts + 12 + x_frac * 2 ** -12
- | In Q10:
- | = ((-lshifts + 12) << 10) + (x_frac >> 2)
"""
lshifts = 12
while x_Q12 >= (1 << 13):
x_Q12 >>= 1
lshifts -= 1
while x_Q12 < (1 << 12):
x_Q12 <<= 1
lshifts += 1
x_frac = x_Q12 & ((1 << 12) - 1)
# x_frac = x_Q12 - (1 << 12)
return ((-lshifts + 12) << 10) + (x_frac >> 2)
log2 = lambda x: log2Q10_xQ12(int(x * (1 << 12))) / (1 << 10)
def get_size_in_bits_bs(x):
"""
Returns the number of bits that are needed at the most to represent x using
a binary search. In a valid range:
WebRtcSpl_GetSizeInBits(n) == int(np.log2(n)) + 1
"""
if (0xFFFF0000 & x):
bits = 16
else:
bits = 0
if (0x0000FF00 & (x >> bits)): bits += 8
if (0x000000F0 & (x >> bits)): bits += 4
if (0x0000000C & (x >> bits)): bits += 2
if (0x00000002 & (x >> bits)): bits += 1
if (0x00000001 & (x >> bits)): bits += 1
return bits
def plot_data(x, y1, y2, name="plot"):
plt.figure(figsize=[8, 6])
plt.plot(x, y1, "r")
plt.plot(x, y2, "b")
plt.grid(True)
plt.title(name)
plt.tight_layout()
plt.savefig(name)
plt.close()
# x = np.arange(0.1, 4.1, 0.1)
# x = np.arange(1, 2.1, 0.1)
x = np.arange(0.1, 32.1, 0.1)
y1 = np.log2(x)
y2 = [log2(xi) for xi in x]
plot_data(x, y1, y2, "log2 approximation")