読者です 読者をやめる 読者になる 読者になる

Variable Code Byte.

c++

最近買った「大規模サービス技術入門」でVariable Code Byteが説明されてたので、本に乗ってた擬似コード見つつ書いてみました。だいたいこんな感じでしょうか?

#include <iostream>

#include <vector>

#include <cstdlib>

#include <ctime>

#include <climits>

#include <assert.h>



using namespace std;



typedef vector<int> integers;

typedef unsigned char byte;

typedef vector<byte> bytestream;



static const int magic = 0x80;



void vbEncodeNumber(int number, bytestream &bstream)

{

	while(true) {

		bstream.insert(bstream.begin(), number % magic);

		if (number < magic) {

			break;

		}

		number /= magic;

	}

	

	byte tmp = bstream[bstream.size() - 1] + magic;

	bstream.pop_back();

	bstream.push_back(tmp);

}



void vbEncode(integers &numbers, bytestream &result)

{ 

	for (size_t s = 0; s < numbers.size(); s++) {

		bytestream bstream;

		vbEncodeNumber(numbers[s], bstream);

		for (size_t s = 0; s < bstream.size(); s++) {

			result.push_back(bstream[s]);

		}

	}

}



void vbDecode(bytestream &enc, integers &dec)

{

	int n = 0;

	vector<int> tmp;

	

	for (size_t s = 0; s < enc.size(); s++) {

		if (enc[s] < magic) {

			n = (magic * n) + enc[s];

		} else {

			n = (magic * n) + (enc[s] - magic);

			tmp.push_back(n);

			n = 0;

		}

	

		if (enc[s] & 0x80) {

			int ret = 0;

			for (size_t i = 0, offset = tmp.size() - 1; i < tmp.size(); i++, offset--) {

				ret |= tmp[i] << (offset * 8);

				dec.push_back(ret);

			}

			tmp.clear();

		}

	}



}



// 5 : 10000101

// 130 : 00000001 10000010

int main(int argc, char **argv)

{

	integers test_inputs;

	srand(time(NULL));

	

	for (int i = 0; i < 10; i++) {

		test_inputs.push_back(rand() % INT_MAX);

	}



	integers decoded;	

	bytestream encoded;

	vbEncode(test_inputs, encoded);

	vbDecode(encoded, decoded);



	for (size_t s = 0; s < test_inputs.size(); s++) {

		cout << "Test[" << s << "] Input is " << test_inputs[s] << " : Decoded is " << decoded[s] << endl;

		assert(test_inputs[s] == decoded[s]);

	}

	return 0;

}


}

実行結果はこんな感じです。

[masami@moon]~/experiment/variable_byte_code% g++ variable_byte_code.cc -Wall
[masami@moon]~/experiment/variable_byte_code% ./a.out 
Test input is 2029191024 : Decoded result is 2029191024
Test input is 111558550 : Decoded result is 111558550
Test input is 53774410 : Decoded result is 53774410
Test input is 392813475 : Decoded result is 392813475
Test input is 751761278 : Decoded result is 751761278