白峯のソース

IT なことのメモなど

可変長バイト列表現

セーブデータ、BLE等通信処理、データベース…などなど、現在でも数値をなるべく小さなバイト列で扱いたいときはあるもの。
そんな中で、「たいていは小さい自然数なんだけど、たまに大きな値もある」というときに数値の可変長バイト列表現というのは便利。

筆者がはじめてこの類に出会ったのは、SMF（Standard MIDI File）で、たいていは 0x7f 以下なんだよね、ってときに効率がアップし、大変有用だと感じた。
一般的なところで言えば、utf-8 なんかもその類で、似たようなビットフラグで可変長表現を行っている。

しかし、意外とこのアルゴリズムのソースコードを探すと無く（実はある？）、しかも、短時間で書けちゃうので毎回書いてしまう。
意外と使い回さない。

ということで、自部用にメモっておく。
SMF に似たフラグ表現を行っている。

注意事項は以下の通り。
・リトルエンディアン的配列である（SMF はビックエンディアンだったか？）
・Java/Kotlin の Byte は符号付である
・自然数のみ扱える

◆ Kotlin

/**
 * 数値を可変長バイト列に変換した時のバイト列長を計算する
 *
 * @param value 変換元となる数値
 * @return 変換後のバイト列長
 */
fun measureIntToVariableBytes(value: Int): Int {
	// バイト列の長さを求める
	var w = value
	var len = 0
	while (w > 0) {
		len += 1
		w = w.ushr(7)    // >>>
	}
	if(len <= 0) {
		len = 1
	}
	return len
}

/**
 * 数値を可変長バイト列に変換する
 *
 * @param dstBytes 可変長バイト列の結果を入れるバイト列
 * @param dstOffset 結果を入れる dstBytes の開始インデックス
 * @param value 変換元となる数値
 * @return 変換後の dstBytes 終了インデックス (exclusive)
 */
fun convIntToVariableBytes(dstBytes: ByteArray, dstOffset: Int, value: Int): Int {
	// バイト列の書き込み
	if(value <= 0) {
		if(0 >= dstBytes.count()) {
			return 0	// 失敗（もっとわかりやすく -1 を返す、などでも良いだろう）
		}
		dstBytes[dstOffset + 0] = 0
		return dstOffset + 1
	}
	var w = value
	var i = dstOffset
	while(w > 0) {
		if(i >= dstBytes.count()) {
			return 0	// 失敗
		}
		dstBytes[i] = (w and 0x7f).toByte()
		i += 1
		w = w.ushr(7)
		if(w > 0)	// 後続バイトがある
		{
			dstBytes[i - 1] = (dstBytes[i - 1].toInt() or 0x80).toByte()	// 後続フラグとして先頭１ビットを立てる
		}
	}
	return i
}

/**
 * 可変長バイト列に数値に変換する
 *
 * @param srcBytes 変換前の可変長バイト列
 * @param srcOffset srcOffset の開始インデックス
 * @return [0] 変換後の数値, [1] 変換後の srcBytes 終了インデックス (exclusive)
 */
fun convVariableBytesToInt(srcBytes: ByteArray, srcOffset: Int): Pair<Int, Int> {
	var r = 0
	var i = srcOffset
	var s = 0
	while(i < srcBytes.count()) {
		val n = srcBytes[i].toInt()
		r = r or (n and 0x7f).shl(s)	// <<
		i += 1
		s += 7
		if((n and 0x80) == 0) {	// 後続フラグなし
			break
		}
	}
	return Pair(r, i)
}

/**
 * 数値を可変長バイト列に変換する（単体版）
 *
 * @param value 変換元となる数値
 * @return 変換後のバイト列長
 */
fun intToVariableBytes(value: Int): ByteArray {
	val len = measureIntToVariableBytes(value)
	val bytes = ByteArray(len)
	convIntToVariableBytes(bytes, 0, value)
	return bytes
}

/**
 * 可変長バイト列に数値に変換する（単体版）
 *
 * @param bytes 変換前の可変長バイト列
 * @return 変換後の数値
 */
fun variableBytesToInt(bytes: ByteArray): Int {
	val (value, _) = convVariableBytesToInt(bytes, 0)
	return value
}


◆ Swift

/**
 * 数値を可変長バイト値に変換した時のバイト列長を計算する
 *
 * @param value 変換元となる数値
 * @return 変換後のバイト列長
 */
static func measureIntToVariableBytes(_ value: Int)-> Int {
	// バイト列の長さを求める
	var w = value
	var len = 0
	while (w > 0) {
		len += 1
		w >>= 7
	}
	if(len <= 0) {
		len = 1
	}
	return len
}

/**
 * 数値を可変長バイト列に変換する
 *
 * @param dstBytes 可変長バイト列の結果を入れるバイト列
 * @param dstOffset 結果を入れる dstBytes の開始インデックス
 * @param value 変換元となる数値
 * @return 変換後の dstBytes 終了インデックス (exclusive)
 */
static func convIntToVariableBytes(_ dstBytes: inout [UInt8], _ dstOffset: Int, _ value: Int)-> Int {
	// バイト列の書き込み
	if(value <= 0) {
		if(0 >= dstBytes.count) {
			return 0	// 失敗（もっとわかりやすく -1 を返す、などでも良いだろう）
		}
		dstBytes[dstOffset + 0] = 0
		return dstOffset + 1
	}
	var w = value
	var i = dstOffset
	while(w > 0) {
		if(i >= dstBytes.count) {
			return 0	// 失敗
		}
		dstBytes[i] = UInt8(w & 0x7f)
		i += 1
		w >>= 7
		if(w > 0)	// 後続バイトがある
		{
			dstBytes[i - 1] = dstBytes[i - 1] | 0x80	// 後続フラグとして先頭１ビットを立てる
		}
	}
	return i
}

/**
 * 可変長バイト列に数値に変換する
 *
 * @param srcBytes 変換前の可変長バイト列
 * @param srcOffset srcOffset の開始インデックス
 * @return [0] 変換後の数値, [1] 変換後の srcBytes 終了インデックス (exclusive)
 */
static func convVariableBytesToInt(_ srcBytes: [UInt8], _ srcOffset: Int)-> (Int, Int) {
	var r = 0
	var i = srcOffset
	var s = 0
	while(i < srcBytes.count) {
		let n = Int(srcBytes[i])
		r |= (n & 0x7f) << s
		i += 1
		s += 7
		if((n & 0x80) == 0) {	// 後続フラグなし
			break
		}
	}
	return (r, i)
}

/**
 * 数値を可変長バイト列に変換する（単体版）
 *
 * @param value 変換元となる数値
 * @return 変換後のバイト列長
 */
static func intToVariableBytes(_ value: Int)-> [UInt8] {
	let len = measureIntToVariableBytes(value)
	var bytes = [UInt8](repeating: 0, count: len)
	_ = convIntToVariableBytes(&bytes, 0, value)
	return bytes
}

/**
 * 可変長バイト列に数値に変換する（単体版）
 *
 * @param bytes 変換前の可変長バイト列
 * @return 変換後の数値
 */
static func variableBytesToInt(_ bytes: [UInt8])-> Int {
	let r = convVariableBytesToInt(bytes, 0)
	return r.0
}

このソースをまとめてクラス化してもよいと思ふ。
また、Long とか Int64 とかに対応してみるのもいいかも。

ついでに、テストコードも添付（Kotlin+Android のみ）。

var n: Long = 0	// Int だと上限を確認できないので Long で
var p: Long = n
var r: Long
while (n <= 0xffffffff) {	// unsigned int 最大値まで回すが、理論上上限の 0x7fffffff まで正常かを確認
	val bytes = Utils.intToVariableBytes(n.toInt())
	r = Utils.variableBytesToInt(bytes).toLong()
	if (n != r) {
		android.util.Log.d("A", "variable-bytes test: break! n=${"0x%x".format(n)}($n), r=$r, p=${"0x%x".format(p)}($p)")
		break
	}
	p = n
	n += 1
	if(n == 0x1fff.toLong()) { n = 0x7ffffffe }	// 全部はやってられないのでジャンプ
}