next power of 2

next power of 2.md

JavaScript の ArrayBuffer は生のメモリを扱う都合から fixed length です。つまり後から長さを変更できません。
エンコード/デコード処理の途中でバッファが足りなくなった場合は、ある程度のサイズに expand する必要があります。
一般的には2のべき乗でバッファサイズを拡張するのが良いとされています。(すげぇ面倒なのでここツッコミ禁止ね)

power of 2 を求める方法は、WikiPediaやStackOverflowによると、色々とあるようですが、コードだけみても ?? になるので、多少遅めでも、もうちょっと分かりやすい表現がないかなーと考えてました。

そんなこんなで JavaScript における Next power of 2 を求める方法を考えてみました。

po2 関数は、値nを含む最小の power of 2 を返します。n が負の場合は考慮してません。

function po2(n) {
    return Math.pow(2, n.toString(2).length);
}

仕組みは単純

数値 n を2進数の文字列にすると、
7 は "111" になります。
8 は "1000" ですね。
16 は "10000" です。

つまり、先頭を1に、それ以外は全て0にして、1桁増やせばその数値を含む最小の power of 2 になります。

7("111") ▶ "100" + "0" ▶ 8("1000")

使ってみましょう

po2 を使うとこうなります。

po2(123); // 128
po2(255); // 256
po2(256); // 512
po2(0xff00); // 65536

これを使い、バッファが不足した場合にサイズを2倍に拡張するコードを書くとするとこうなるでしょうか

var bufferSize = 1024 * 16; // 16kb
var buffer = new Uint8Array(bufferSize);
var bufferCursor = 0;
var bufferSizeThreshold = bufferSize * 0.9; // ここは適当に

// なにか処理
for (;;) {
    buffer[bufferCursor++] = xxx;

    if (bufferCursor >= bufferSizeThreshold) { // あー、そろそろカツカツかも …
        var newSize = po2(bufferSize) << 1; // expand by a factor of two.
        buffer = expandBuffer(buffer, newSize);
        bufferSize = newSize;
        bufferSizeThreshold = newSize * 0.9;
    }
}

function _expandBuffer(buffer, newSize) {
    var newBuffer = new Uint8Array(newSize);

    newBuffer.set(buffer, 0); // memcpy
    return newBuffer;
}