最近買った「大規模サービス技術入門」で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
