Google group varint無損圧縮解凍アルゴリズムの効率的な実現改善版
28483 ワード
以前はgoogle group varint無損圧縮解凍アルゴリズムの効率的な実現を実現した.
最近、性能が20%向上し、テストデータは以下の通りである:100万個の整数(4 M)の新しいバージョンを圧縮し、解凍する:encode time consumed:0.003252 s;decode time consumed:0.003769 s旧バージョン:encode time consumed:0.005198 s;decode time consumed: 0.004909 s
これで1秒で1 Gのデータを解凍できるなんて、驚くべきことでしょう.
くだらないことを言わないで、コードをつけて、興味のある自分で見て、もし私の注釈がはっきりしていないならば、私に連絡して修正してください
最近、性能が20%向上し、テストデータは以下の通りである:100万個の整数(4 M)の新しいバージョンを圧縮し、解凍する:encode time consumed:0.003252 s;decode time consumed:0.003769 s旧バージョン:encode time consumed:0.005198 s;decode time consumed: 0.004909 s
これで1秒で1 Gのデータを解凍できるなんて、驚くべきことでしょう.
くだらないことを言わないで、コードをつけて、興味のある自分で見て、もし私の注釈がはっきりしていないならば、私に連絡して修正してください
/******************************************************************
* Created on: 2011-4-26
* Author: [email protected] [email protected]
*
* Desc : uint32 varint
* group varint
*
******************************************************************/
#ifndef VARINT_H_
#define VARINT_H_
#include <stdint.h>
#include <stddef.h>
#include "common.h"
namespace ups_util
{
#pragma pack(1)
typedef struct
{
uint32_t value : 24;
}UINT24_T;
#pragma pack()
/**
* group varint ， ：(byte)
*
* 0 ： 2
* 1 ： 3
* 2 ： 4
* 3 ： 1
* 4 ： 2
* 5 ： 3
* 6 ： 4
* 7 ： （4 ）
*
* 1
*/
static const uint8_t GROUP_VARINT_IDX_ARR[256][8] =
{
/* 00 00 00 00 */ { 2, 3, 4, 1, 1, 1, 1, 5},
/* 00 00 00 01 */ { 2, 3, 4, 1, 1, 1, 2, 6},
/* 00 00 00 10 */ { 2, 3, 4, 1, 1, 1, 3, 7},
/* 00 00 00 11 */ { 2, 3, 4, 1, 1, 1, 4, 8},
/* 00 00 01 00 */ { 2, 3, 5, 1, 1, 2, 1, 6},
/* 00 00 01 01 */ { 2, 3, 5, 1, 1, 2, 2, 7},
/* 00 00 01 10 */ { 2, 3, 5, 1, 1, 2, 3, 8},
/* 00 00 01 11 */ { 2, 3, 5, 1, 1, 2, 4, 9},
/* 00 00 10 00 */ { 2, 3, 6, 1, 1, 3, 1, 7},
/* 00 00 10 01 */ { 2, 3, 6, 1, 1, 3, 2, 8},
/* 00 00 10 10 */ { 2, 3, 6, 1, 1, 3, 3, 9},
/* 00 00 10 11 */ { 2, 3, 6, 1, 1, 3, 4, 10},
/* 00 00 11 00 */ { 2, 3, 7, 1, 1, 4, 1, 8},
/* 00 00 11 01 */ { 2, 3, 7, 1, 1, 4, 2, 9},
/* 00 00 11 10 */ { 2, 3, 7, 1, 1, 4, 3, 10},
/* 00 00 11 11 */ { 2, 3, 7, 1, 1, 4, 4, 11},
/* 00 01 00 00 */ { 2, 4, 5, 1, 2, 1, 1, 6},
/* 00 01 00 01 */ { 2, 4, 5, 1, 2, 1, 2, 7},
/* 00 01 00 10 */ { 2, 4, 5, 1, 2, 1, 3, 8},
/* 00 01 00 11 */ { 2, 4, 5, 1, 2, 1, 4, 9},
/* 00 01 01 00 */ { 2, 4, 6, 1, 2, 2, 1, 7},
/* 00 01 01 01 */ { 2, 4, 6, 1, 2, 2, 2, 8},
/* 00 01 01 10 */ { 2, 4, 6, 1, 2, 2, 3, 9},
/* 00 01 01 11 */ { 2, 4, 6, 1, 2, 2, 4, 10},
/* 00 01 10 00 */ { 2, 4, 7, 1, 2, 3, 1, 8},
/* 00 01 10 01 */ { 2, 4, 7, 1, 2, 3, 2, 9},
/* 00 01 10 10 */ { 2, 4, 7, 1, 2, 3, 3, 10},
/* 00 01 10 11 */ { 2, 4, 7, 1, 2, 3, 4, 11},
/* 00 01 11 00 */ { 2, 4, 8, 1, 2, 4, 1, 9},
/* 00 01 11 01 */ { 2, 4, 8, 1, 2, 4, 2, 10},
/* 00 01 11 10 */ { 2, 4, 8, 1, 2, 4, 3, 11},
/* 00 01 11 11 */ { 2, 4, 8, 1, 2, 4, 4, 12},
/* 00 10 00 00 */ { 2, 5, 6, 1, 3, 1, 1, 7},
/* 00 10 00 01 */ { 2, 5, 6, 1, 3, 1, 2, 8},
/* 00 10 00 10 */ { 2, 5, 6, 1, 3, 1, 3, 9},
/* 00 10 00 11 */ { 2, 5, 6, 1, 3, 1, 4, 10},
/* 00 10 01 00 */ { 2, 5, 7, 1, 3, 2, 1, 8},
/* 00 10 01 01 */ { 2, 5, 7, 1, 3, 2, 2, 9},
/* 00 10 01 10 */ { 2, 5, 7, 1, 3, 2, 3, 10},
/* 00 10 01 11 */ { 2, 5, 7, 1, 3, 2, 4, 11},
/* 00 10 10 00 */ { 2, 5, 8, 1, 3, 3, 1, 9},
/* 00 10 10 01 */ { 2, 5, 8, 1, 3, 3, 2, 10},
/* 00 10 10 10 */ { 2, 5, 8, 1, 3, 3, 3, 11},
/* 00 10 10 11 */ { 2, 5, 8, 1, 3, 3, 4, 12},
/* 00 10 11 00 */ { 2, 5, 9, 1, 3, 4, 1, 10},
/* 00 10 11 01 */ { 2, 5, 9, 1, 3, 4, 2, 11},
/* 00 10 11 10 */ { 2, 5, 9, 1, 3, 4, 3, 12},
/* 00 10 11 11 */ { 2, 5, 9, 1, 3, 4, 4, 13},
/* 00 11 00 00 */ { 2, 6, 7, 1, 4, 1, 1, 8},
/* 00 11 00 01 */ { 2, 6, 7, 1, 4, 1, 2, 9},
/* 00 11 00 10 */ { 2, 6, 7, 1, 4, 1, 3, 10},
/* 00 11 00 11 */ { 2, 6, 7, 1, 4, 1, 4, 11},
/* 00 11 01 00 */ { 2, 6, 8, 1, 4, 2, 1, 9},
/* 00 11 01 01 */ { 2, 6, 8, 1, 4, 2, 2, 10},
/* 00 11 01 10 */ { 2, 6, 8, 1, 4, 2, 3, 11},
/* 00 11 01 11 */ { 2, 6, 8, 1, 4, 2, 4, 12},
/* 00 11 10 00 */ { 2, 6, 9, 1, 4, 3, 1, 10},
/* 00 11 10 01 */ { 2, 6, 9, 1, 4, 3, 2, 11},
/* 00 11 10 10 */ { 2, 6, 9, 1, 4, 3, 3, 12},
/* 00 11 10 11 */ { 2, 6, 9, 1, 4, 3, 4, 13},
/* 00 11 11 00 */ { 2, 6, 10 , 1, 4, 4, 1, 11},
/* 00 11 11 01 */ { 2, 6, 10 , 1, 4, 4, 2, 12 },
/* 00 11 11 10 */ { 2, 6, 10 , 1, 4, 4, 3, 13 },
/* 00 11 11 11 */ { 2, 6, 10 , 1, 4, 4, 4, 14 },
/* 01 00 00 00 */ { 3, 4, 5, 2, 1, 1, 1, 6},
/* 01 00 00 01 */ { 3, 4, 5, 2, 1, 1, 2, 7},
/* 01 00 00 10 */ { 3, 4, 5, 2, 1, 1, 3, 8},
/* 01 00 00 11 */ { 3, 4, 5, 2, 1, 1, 4, 9},
/* 01 00 01 00 */ { 3, 4, 6, 2, 1, 2, 1, 7},
/* 01 00 01 01 */ { 3, 4, 6, 2, 1, 2, 2, 8},
/* 01 00 01 10 */ { 3, 4, 6, 2, 1, 2, 3, 9},
/* 01 00 01 11 */ { 3, 4, 6, 2, 1, 2, 4, 10},
/* 01 00 10 00 */ { 3, 4, 7, 2, 1, 3, 1, 8},
/* 01 00 10 01 */ { 3, 4, 7, 2, 1, 3, 2, 9},
/* 01 00 10 10 */ { 3, 4, 7, 2, 1, 3, 3, 10},
/* 01 00 10 11 */ { 3, 4, 7, 2, 1, 3, 4, 11},
/* 01 00 11 00 */ { 3, 4, 8, 2, 1, 4, 1, 9},
/* 01 00 11 01 */ { 3, 4, 8, 2, 1, 4, 2, 10},
/* 01 00 11 10 */ { 3, 4, 8, 2, 1, 4, 3, 11},
/* 01 00 11 11 */ { 3, 4, 8, 2, 1, 4, 4, 12},
/* 01 01 00 00 */ { 3, 5, 6, 2, 2, 1, 1, 7},
/* 01 01 00 01 */ { 3, 5, 6, 2, 2, 1, 2, 8},
/* 01 01 00 10 */ { 3, 5, 6, 2, 2, 1, 3, 9},
/* 01 01 00 11 */ { 3, 5, 6, 2, 2, 1, 4, 10},
/* 01 01 01 00 */ { 3, 5, 7, 2, 2, 2, 1, 8},
/* 01 01 01 01 */ { 3, 5, 7, 2, 2, 2, 2, 9},
/* 01 01 01 10 */ { 3, 5, 7, 2, 2, 2, 3, 10},
/* 01 01 01 11 */ { 3, 5, 7, 2, 2, 2, 4, 11},
/* 01 01 10 00 */ { 3, 5, 8, 2, 2, 3, 1, 9},
/* 01 01 10 01 */ { 3, 5, 8, 2, 2, 3, 2, 10},
/* 01 01 10 10 */ { 3, 5, 8, 2, 2, 3, 3, 11},
/* 01 01 10 11 */ { 3, 5, 8, 2, 2, 3, 4, 12},
/* 01 01 11 00 */ { 3, 5, 9, 2, 2, 4, 1, 10},
/* 01 01 11 01 */ { 3, 5, 9, 2, 2, 4, 2, 11},
/* 01 01 11 10 */ { 3, 5, 9, 2, 2, 4, 3, 12},
/* 01 01 11 11 */ { 3, 5, 9, 2, 2, 4, 4, 13},
/* 01 10 00 00 */ { 3, 6, 7, 2, 3, 1, 1, 8},
/* 01 10 00 01 */ { 3, 6, 7, 2, 3, 1, 2, 9},
/* 01 10 00 10 */ { 3, 6, 7, 2, 3, 1, 3, 10},
/* 01 10 00 11 */ { 3, 6, 7, 2, 3, 1, 4, 11},
/* 01 10 01 00 */ { 3, 6, 8, 2, 3, 2, 1, 9},
/* 01 10 01 01 */ { 3, 6, 8, 2, 3, 2, 2, 10},
/* 01 10 01 10 */ { 3, 6, 8, 2, 3, 2, 3, 11},
/* 01 10 01 11 */ { 3, 6, 8, 2, 3, 2, 4, 12},
/* 01 10 10 00 */ { 3, 6, 9, 2, 3, 3, 1, 10},
/* 01 10 10 01 */ { 3, 6, 9, 2, 3, 3, 2, 11},
/* 01 10 10 10 */ { 3, 6, 9, 2, 3, 3, 3, 12},
/* 01 10 10 11 */ { 3, 6, 9, 2, 3, 3, 4, 13},
/* 01 10 11 00 */ { 3, 6, 10 , 2, 3, 4, 1 , 11},
/* 01 10 11 01 */ { 3, 6, 10 , 2, 3, 4, 2 , 12},
/* 01 10 11 10 */ { 3, 6, 10 , 2, 3, 4, 3 , 13},
/* 01 10 11 11 */ { 3, 6, 10 , 2, 3, 4, 4 , 14},
/* 01 11 00 00 */ { 3, 7, 8, 2, 4, 1, 1, 9},
/* 01 11 00 01 */ { 3, 7, 8, 2, 4, 1, 2, 10},
/* 01 11 00 10 */ { 3, 7, 8, 2, 4, 1, 3, 11},
/* 01 11 00 11 */ { 3, 7, 8, 2, 4, 1, 4, 12},
/* 01 11 01 00 */ { 3, 7, 9, 2, 4, 2, 1, 10},
/* 01 11 01 01 */ { 3, 7, 9, 2, 4, 2, 2, 11},
/* 01 11 01 10 */ { 3, 7, 9, 2, 4, 2, 3, 12},
/* 01 11 01 11 */ { 3, 7, 9, 2, 4, 2, 4, 13},
/* 01 11 10 00 */ { 3, 7, 10 , 2, 4, 3, 1 , 11},
/* 01 11 10 01 */ { 3, 7, 10 , 2, 4, 3, 2 , 12},
/* 01 11 10 10 */ { 3, 7, 10 , 2, 4, 3, 3 , 13},
/* 01 11 10 11 */ { 3, 7, 10 , 2, 4, 3, 4 , 14},
/* 01 11 11 00 */ { 3, 7, 11 , 2, 4, 4, 1 , 12},
/* 01 11 11 01 */ { 3, 7, 11 , 2, 4, 4, 2 , 13},
/* 01 11 11 10 */ { 3, 7, 11 , 2, 4, 4, 3 , 14},
/* 01 11 11 11 */ { 3, 7, 11 , 2, 4, 4, 4 , 15},
/* 10 00 00 00 */ { 4, 5, 6, 3, 1, 1, 1, 7},
/* 10 00 00 01 */ { 4, 5, 6, 3, 1, 1, 2, 8},
/* 10 00 00 10 */ { 4, 5, 6, 3, 1, 1, 3, 9},
/* 10 00 00 11 */ { 4, 5, 6, 3, 1, 1, 4, 10},
/* 10 00 01 00 */ { 4, 5, 7, 3, 1, 2, 1, 8},
/* 10 00 01 01 */ { 4, 5, 7, 3, 1, 2, 2, 9},
/* 10 00 01 10 */ { 4, 5, 7, 3, 1, 2, 3, 10},
/* 10 00 01 11 */ { 4, 5, 7, 3, 1, 2, 4, 11},
/* 10 00 10 00 */ { 4, 5, 8, 3, 1, 3, 1, 9},
/* 10 00 10 01 */ { 4, 5, 8, 3, 1, 3, 2, 10},
/* 10 00 10 10 */ { 4, 5, 8, 3, 1, 3, 3, 11},
/* 10 00 10 11 */ { 4, 5, 8, 3, 1, 3, 4, 12},
/* 10 00 11 00 */ { 4, 5, 9, 3, 1, 4, 1, 10},
/* 10 00 11 01 */ { 4, 5, 9, 3, 1, 4, 2, 11},
/* 10 00 11 10 */ { 4, 5, 9, 3, 1, 4, 3, 12},
/* 10 00 11 11 */ { 4, 5, 9, 3, 1, 4, 4, 13},
/* 10 01 00 00 */ { 4, 6, 7, 3, 2, 1, 1, 8},
/* 10 01 00 01 */ { 4, 6, 7, 3, 2, 1, 2, 9},
/* 10 01 00 10 */ { 4, 6, 7, 3, 2, 1, 3, 10},
/* 10 01 00 11 */ { 4, 6, 7, 3, 2, 1, 4, 11},
/* 10 01 01 00 */ { 4, 6, 8, 3, 2, 2, 1, 9},
/* 10 01 01 01 */ { 4, 6, 8, 3, 2, 2, 2, 10},
/* 10 01 01 10 */ { 4, 6, 8, 3, 2, 2, 3, 11},
/* 10 01 01 11 */ { 4, 6, 8, 3, 2, 2, 4, 12},
/* 10 01 10 00 */ { 4, 6, 9, 3, 2, 3, 1, 10},
/* 10 01 10 01 */ { 4, 6, 9, 3, 2, 3, 2, 11},
/* 10 01 10 10 */ { 4, 6, 9, 3, 2, 3, 3, 12},
/* 10 01 10 11 */ { 4, 6, 9, 3, 2, 3, 4, 13},
/* 10 01 11 00 */ { 4, 6, 10 , 3, 2, 4, 1, 11 },
/* 10 01 11 01 */ { 4, 6, 10 , 3, 2, 4, 2, 12 },
/* 10 01 11 10 */ { 4, 6, 10 , 3, 2, 4, 3, 13 },
/* 10 01 11 11 */ { 4, 6, 10 , 3, 2, 4, 4, 14 },
/* 10 10 00 00 */ { 4, 7, 8, 3, 3, 1, 1, 9},
/* 10 10 00 01 */ { 4, 7, 8, 3, 3, 1, 2, 10},
/* 10 10 00 10 */ { 4, 7, 8, 3, 3, 1, 3, 11},
/* 10 10 00 11 */ { 4, 7, 8, 3, 3, 1, 4, 12},
/* 10 10 01 00 */ { 4, 7, 9, 3, 3, 2, 1, 10},
/* 10 10 01 01 */ { 4, 7, 9, 3, 3, 2, 2, 11},
/* 10 10 01 10 */ { 4, 7, 9, 3, 3, 2, 3, 12},
/* 10 10 01 11 */ { 4, 7, 9, 3, 3, 2, 4, 13},
/* 10 10 10 00 */ { 4, 7, 10 , 3, 3, 3, 1, 11 },
/* 10 10 10 01 */ { 4, 7, 10 , 3, 3, 3, 2, 12 },
/* 10 10 10 10 */ { 4, 7, 10 , 3, 3, 3, 3, 13 },
/* 10 10 10 11 */ { 4, 7, 10 , 3, 3, 3, 4, 14 },
/* 10 10 11 00 */ { 4, 7, 11 , 3, 3, 4, 1, 12 },
/* 10 10 11 01 */ { 4, 7, 11 , 3, 3, 4, 2, 13 },
/* 10 10 11 10 */ { 4, 7, 11 , 3, 3, 4, 3, 14 },
/* 10 10 11 11 */ { 4, 7, 11 , 3, 3, 4, 4, 15 },
/* 10 11 00 00 */ { 4, 8, 9, 3, 4, 1, 1, 10},
/* 10 11 00 01 */ { 4, 8, 9, 3, 4, 1, 2, 11},
/* 10 11 00 10 */ { 4, 8, 9, 3, 4, 1, 3, 12},
/* 10 11 00 11 */ { 4, 8, 9, 3, 4, 1, 4, 13},
/* 10 11 01 00 */ { 4, 8, 10 , 3, 4, 2, 1, 11 },
/* 10 11 01 01 */ { 4, 8, 10 , 3, 4, 2, 2, 12 },
/* 10 11 01 10 */ { 4, 8, 10 , 3, 4, 2, 3, 13 },
/* 10 11 01 11 */ { 4, 8, 10 , 3, 4, 2, 4, 14 },
/* 10 11 10 00 */ { 4, 8, 11 , 3, 4, 3, 1, 12 },
/* 10 11 10 01 */ { 4, 8, 11 , 3, 4, 3, 2, 13 },
/* 10 11 10 10 */ { 4, 8, 11 , 3, 4, 3, 3, 14 },
/* 10 11 10 11 */ { 4, 8, 11 , 3, 4, 3, 4, 15 },
/* 10 11 11 00 */ { 4, 8, 12 , 3, 4, 4, 1, 13 },
/* 10 11 11 01 */ { 4, 8, 12 , 3, 4, 4, 2, 14 },
/* 10 11 11 10 */ { 4, 8, 12 , 3, 4, 4, 3, 15 },
/* 10 11 11 11 */ { 4, 8, 12 , 3, 4, 4, 4, 16 },
/* 11 00 00 00 */ { 5, 6, 7, 4, 1, 1, 1, 8},
/* 11 00 00 01 */ { 5, 6, 7, 4, 1, 1, 2, 9},
/* 11 00 00 10 */ { 5, 6, 7, 4, 1, 1, 3, 10},
/* 11 00 00 11 */ { 5, 6, 7, 4, 1, 1, 4, 11},
/* 11 00 01 00 */ { 5, 6, 8, 4, 1, 2, 1, 9},
/* 11 00 01 01 */ { 5, 6, 8, 4, 1, 2, 2, 10},
/* 11 00 01 10 */ { 5, 6, 8, 4, 1, 2, 3, 11},
/* 11 00 01 11 */ { 5, 6, 8, 4, 1, 2, 4, 12},
/* 11 00 10 00 */ { 5, 6, 9, 4, 1, 3, 1, 10},
/* 11 00 10 01 */ { 5, 6, 9, 4, 1, 3, 2, 11},
/* 11 00 10 10 */ { 5, 6, 9, 4, 1, 3, 3, 12},
/* 11 00 10 11 */ { 5, 6, 9, 4, 1, 3, 4, 13},
/* 11 00 11 00 */ { 5, 6, 10 , 4, 1, 4, 1, 11 },
/* 11 00 11 01 */ { 5, 6, 10 , 4, 1, 4, 2, 12 },
/* 11 00 11 10 */ { 5, 6, 10 , 4, 1, 4, 3, 13 },
/* 11 00 11 11 */ { 5, 6, 10 , 4, 1, 4, 4, 14 },
/* 11 01 00 00 */ { 5, 7, 8, 4, 2, 1, 1, 9},
/* 11 01 00 01 */ { 5, 7, 8, 4, 2, 1, 2, 10},
/* 11 01 00 10 */ { 5, 7, 8, 4, 2, 1, 3, 11},
/* 11 01 00 11 */ { 5, 7, 8, 4, 2, 1, 4, 12},
/* 11 01 01 00 */ { 5, 7, 9, 4, 2, 2, 1, 10},
/* 11 01 01 01 */ { 5, 7, 9, 4, 2, 2, 2, 11},
/* 11 01 01 10 */ { 5, 7, 9, 4, 2, 2, 3, 12},
/* 11 01 01 11 */ { 5, 7, 9, 4, 2, 2, 4, 13},
/* 11 01 10 00 */ { 5, 7, 10 , 4, 2, 3, 1 , 11},
/* 11 01 10 01 */ { 5, 7, 10 , 4, 2, 3, 2 , 12},
/* 11 01 10 10 */ { 5, 7, 10 , 4, 2, 3, 3 , 13},
/* 11 01 10 11 */ { 5, 7, 10 , 4, 2, 3, 4 , 14},
/* 11 01 11 00 */ { 5, 7, 11 , 4, 2, 4, 1 , 12},
/* 11 01 11 01 */ { 5, 7, 11 , 4, 2, 4, 2 , 13},
/* 11 01 11 10 */ { 5, 7, 11 , 4, 2, 4, 3 , 14},
/* 11 01 11 11 */ { 5, 7, 11 , 4, 2, 4, 4 , 15},
/* 11 10 00 00 */ { 5, 8, 9, 4, 3, 1, 1, 10},
/* 11 10 00 01 */ { 5, 8, 9, 4, 3, 1, 2, 11},
/* 11 10 00 10 */ { 5, 8, 9, 4, 3, 1, 3, 12},
/* 11 10 00 11 */ { 5, 8, 9, 4, 3, 1, 4, 13},
/* 11 10 01 00 */ { 5, 8, 10 , 4, 3, 2, 1 , 11},
/* 11 10 01 01 */ { 5, 8, 10 , 4, 3, 2, 2 , 12},
/* 11 10 01 10 */ { 5, 8, 10 , 4, 3, 2, 3 , 13},
/* 11 10 01 11 */ { 5, 8, 10 , 4, 3, 2, 4 , 14},
/* 11 10 10 00 */ { 5, 8, 11 , 4, 3, 3, 1 , 12},
/* 11 10 10 01 */ { 5, 8, 11 , 4, 3, 3, 2 , 13},
/* 11 10 10 10 */ { 5, 8, 11 , 4, 3, 3, 3 , 14},
/* 11 10 10 11 */ { 5, 8, 11 , 4, 3, 3, 4 , 15},
/* 11 10 11 00 */ { 5, 8, 12 , 4, 3, 4, 1, 13 },
/* 11 10 11 01 */ { 5, 8, 12 , 4, 3, 4, 2, 14 },
/* 11 10 11 10 */ { 5, 8, 12 , 4, 3, 4, 3, 15 },
/* 11 10 11 11 */ { 5, 8, 12 , 4, 3, 4, 4, 16 },
/* 11 11 00 00 */ { 5, 9, 10 , 4, 4, 1, 1, 11 },
/* 11 11 00 01 */ { 5, 9, 10 , 4, 4, 1, 2, 12 },
/* 11 11 00 10 */ { 5, 9, 10 , 4, 4, 1, 3, 13 },
/* 11 11 00 11 */ { 5, 9, 10 , 4, 4, 1, 4, 14 },
/* 11 11 01 00 */ { 5, 9, 11 , 4, 4, 2, 1, 12 },
/* 11 11 01 01 */ { 5, 9, 11 , 4, 4, 2, 2, 13 },
/* 11 11 01 10 */ { 5, 9, 11 , 4, 4, 2, 3, 14 },
/* 11 11 01 11 */ { 5, 9, 11 , 4, 4, 2, 4, 15 },
/* 11 11 10 00 */ { 5, 9, 12 , 4, 4, 3, 1, 13 },
/* 11 11 10 01 */ { 5, 9, 12 , 4, 4, 3, 2, 14 },
/* 11 11 10 10 */ { 5, 9, 12 , 4, 4, 3, 3, 15 },
/* 11 11 10 11 */ { 5, 9, 12 , 4, 4, 3, 4, 16 },
/* 11 11 11 00 */ { 5, 9, 13 , 4, 4, 4, 1, 14 },
/* 11 11 11 01 */ { 5, 9, 13 , 4, 4, 4, 2, 15 },
/* 11 11 11 10 */ { 5, 9, 13 , 4, 4, 4, 3, 16 },
/* 11 11 11 11 */ { 5, 9, 13 , 4, 4, 4, 4, 17}
};
/**
* uint32 varint buf
*
* @param value
* @param target , buf
*
* @return target
*/
inline uint8_t *
varint_encode_uint32 ( uint32_t value, uint8_t * target )
{
if ( value >= (1 << 7) )
{
target[0] = (uint8_t)(value | 0x80); // 7 ， 1
if ( value >= (1 << 14) )
{
target[1] = (uint8_t)( (value >> 7) | 0x80 ); // 7 ， 1
if ( value >= (1 << 21) )
{
// 3 7 ， 1
target[2] = (uint8_t)( (value >> 14) | 0x80 );
if ( value >= (1 << 28) )
{
// 4 7 ， 1
target[3] = (uint8_t)((value >> 21) | 0x80);
// 4
target[4] = (uint8_t)(value >> 28);
return target + 5;
}
else
{
target[3] = (uint8_t)( value >> 21 );
return target + 4;
}
}
else
{
target[2] = (uint8_t)( value >> 14 );
return target + 3;
}
}
else
{
target[1] = (uint8_t)( value >> 7 );
return target + 2;
}
}
else
{
target[0] = (uint8_t) value;
return target + 1;
}
}
/**
* buf varint
* buf 5 byte, core
*
*
* @param buffer buf
* @param value
*
* @return target
*/
inline const uint8_t *
varint_decode_uint32( const uint8_t * buffer, uint32_t & value )
{
register const uint8_t * ptr = buffer;
// 7 ， 128
register uint8_t b0 = ptr[ 0 ];
register uint32_t r0 = (b0 & 0x7F);
if (UNLIKELY( !(b0 & 0x80) ))
{
value = r0;
return ptr + 1;
}
// 14 , 16384
register uint8_t b1 = ptr[ 1 ];
register uint32_t r1 = (b1 & 0x7F) << 7;
if (UNLIKELY( !(b1 & 0x80) ))
{
value = ( r1 | r0 );
return ptr + 2;
}
// 21 , 2097152
register uint8_t b2 = ptr[ 2 ];
register uint32_t r2 = (b2 & 0x7F) << 14;
if (UNLIKELY( !(b2 & 0x80) ))
{
value = ( r2 | r1 | r0 );
return ptr + 3;
}
// 28 , 268435456
register uint8_t b3 = ptr[ 3 ];
register uint32_t r3 = (b3 & 0x7F) << 21;
if ( !(b3 & 0x80) )
{
value = ( r3 | r2 | r1 | r0 );
return ptr + 4;
}
// 32
value = ( ((ptr[ 4 ]) << 28) | r3 | r2 | r1 | r0 );
return ptr + 5;
}
/**
* buf varint
* ， ： ， NULL
*
* @param buffer buf
* @param value
*
* @return target , buffer NULL
*/
inline const uint8_t *
varint_decode_uint32( const uint8_t * buffer, uint32_t len, uint32_t & value )
{
if ( len >= 5 ) // len == 0
return varint_decode_uint32( buffer, value );
register const uint8_t * ptr = buffer;
// 7 ， 128
register uint8_t b0 = ptr[ 0 ];
register uint32_t r0 = (b0 & 0x7F);
if (UNLIKELY( !(b0 & 0x80) ))
{
value = r0;
return ptr + 1;
}
if (UNLIKELY( len < 2 )) return NULL;
// 14 , 16384
register uint8_t b1 = ptr[ 1 ];
register uint32_t r1 = (b1 & 0x7F) << 7;
if (UNLIKELY( !(b1 & 0x80) ))
{
value = ( r1 | r0 );
return ptr + 2;
}
if (UNLIKELY( len < 3 )) return NULL;
// 21 , 2097152
register uint8_t b2 = ptr[ 2 ];
register uint32_t r2 = (b2 & 0x7F) << 14;
if (UNLIKELY( !(b2 & 0x80) ))
{
value = ( r2 | r1 | r0 );
return ptr + 3;
}
if (UNLIKELY( len < 4 )) return NULL;
// 28 , 268435456
register uint8_t b3 = ptr[ 3 ];
register uint32_t r3 = (b3 & 0x7F) << 21;
if ( !(b3 & 0x80) )
{
value = ( r3 | r2 | r1 | r0 );
return ptr + 4;
}
if ( len < 5 ) return NULL;
// 32
value = ( ((ptr[ 4 ]) << 28) | r3 | r2 | r1 | r0 );
return ptr + 5;
}
/** ， , 1 uint32 */
inline const uint8_t *
varint_decode_uint32_skip( const uint8_t * buffer )
{
if (UNLIKELY( !(buffer[ 0 ] & 0x80) )) return buffer + 1;
if (UNLIKELY( !(buffer[ 1 ] & 0x80) )) return buffer + 2;
if (UNLIKELY( !(buffer[ 2 ] & 0x80) )) return buffer + 3;
if ( !(buffer[ 3 ] & 0x80) ) return buffer + 4;
return buffer + 5;
}
/**
* uint64 varint buf
*
* @param value
* @param target , buf
*
* @return target
*/
inline uint8_t *
varint_encode_uint64 ( uint64_t value, uint8_t * target )
{
// 32 32
target = varint_encode_uint32( value >> 32, target );
return varint_encode_uint32( value & 0xFFFFFFFF, target );
}
/**
* buf varint
* buf 5 byte, core
*
*
* @param buffer buf
* @param value
*
* @return target
*/
inline const uint8_t *
varint_decode_uint64(const uint8_t * buffer, uint64_t & value)
{
uint32_t high = 0;
uint32_t low = 0;
buffer = varint_decode_uint32( buffer, high );
buffer = varint_decode_uint32( buffer, low );
value = ((uint64_t)high << 32) + low ;
return buffer;
}
/** ， , 1 uint64 */
inline const uint8_t *
varint_decode_uint64_skip( const uint8_t * buffer )
{
buffer = varint_decode_uint32_skip( buffer );
return varint_decode_uint32_skip( buffer );
}
/**
* group varint , 4
*
* @param valueArr ， 4 。
* @param target buf . ， 4 17 byte
*
* @return target byte
*/
inline uint8_t *
group_varint_encode_uint32( const uint32_t * valueArr, uint8_t * target)
{
register uint8_t len1; // 1
register uint8_t len2; // 2
register uint8_t len3; // 3
register uint8_t len4; // 4
register uint32_t val1 = valueArr[0];
register uint32_t val2 = valueArr[1];
register uint32_t val3 = valueArr[2];
register uint32_t val4 = valueArr[3];
register uint8_t * buf = target + 1;
if ( val1 > UINT24_MAX )
{
len1 = 4;
((uint32_t *)(buf))[0] = val1;
}
else if ( val1 > UINT16_MAX )
{
len1 = 3;
((uint32_t *)(buf))[0] = val1;
}
else if ( val1 > UINT8_MAX )
{
len1 = 2;
((uint16_t *)(buf))[0] = (uint16_t) val1;
}
else
{
len1 = 1;
buf[0] = (uint8_t) val1;
}
register uint8_t len = len1; // 4
/* */
if (UNLIKELY( val2 > UINT24_MAX ))
{
len2 = 4;
((uint32_t *)(buf + len))[0] = val2;
}
else if ( val2 > UINT16_MAX )
{
len2 = 3;
((uint32_t *)(buf + len))[0] = val2;
}
else if ( val2 > UINT8_MAX )
{
len2 = 2;
((uint16_t *)(buf + len))[0] = (uint16_t) val2;
}
else
{
len2 = 1;
buf[len] = (uint8_t) val2;
}
len += len2;
/* 3 */
if (UNLIKELY( val3 > UINT24_MAX ))
{
len3 = 4;
((uint32_t *)(buf + len))[0] = val3;
}
else if ( val3 > UINT16_MAX )
{
len3 = 3;
((uint32_t *)(buf + len))[0] = val3;
}
else if ( val3 > UINT8_MAX )
{
len3 = 2;
((uint16_t *)(buf + len))[0] = (uint16_t) val3;
}
else
{
len3 = 1;
buf[len] = (uint8_t) val3;
}
len += len3;
/* 4 */
if (UNLIKELY( val4 > UINT24_MAX ))
{
len4 = 4;
((uint32_t *)(buf + len))[0] = val4;
}
else if ( val4 > UINT16_MAX )
{
len4 = 3;
((uint32_t *)(buf + len))[0] = val4;
}
else if ( val4 > UINT8_MAX )
{
len4 = 2;
((uint16_t *)(buf + len))[0] = (uint16_t) val4;
}
else
{
len4 = 1;
buf[len] = (uint8_t) val4;
}
len += len4;
/* */
target[0] = ((len1 - 1) << 6) | ((len2 - 1) << 4) | ((len3 - 1) << 2) | (len4 - 1);
return buf + len;
}
/**
* buf ， 4
*
* @param buf buf
* @param valueArr ， 4
*
* @return target byte
*/
inline const uint8_t *
group_varint_decode_uint32 ( const uint8_t * buf, uint32_t * valueArr)
{
register uint8_t idx = buf[ 0 ];
const uint8_t * star1 = buf + 1;
const uint8_t * star2 = buf + GROUP_VARINT_IDX_ARR[idx][0];
const uint8_t * star3 = buf + GROUP_VARINT_IDX_ARR[idx][1];
const uint8_t * star4 = buf + GROUP_VARINT_IDX_ARR[idx][2];
switch ( GROUP_VARINT_IDX_ARR[idx][3] )
{
case 1 : valueArr[ 0 ] = *(uint8_t *) star1; break;
case 2 : valueArr[ 0 ] = *(uint16_t *) star1; break;
case 3 : valueArr[ 0 ] = (*(UINT24_T *)star1).value ; break;
default:
valueArr[ 0 ] = *(uint32_t *) star1;
}
switch ( GROUP_VARINT_IDX_ARR[idx][4] )
{
case 1 : valueArr[ 1 ] = *(uint8_t *) star2; break;
case 2 : valueArr[ 1 ] = *(uint16_t *) star2; break;
case 3 : valueArr[ 1 ] = (*(UINT24_T *)star2).value; break;
default:
valueArr[ 1 ] = *(uint32_t *) star2;
}
switch ( GROUP_VARINT_IDX_ARR[idx][5] )
{
case 1 : valueArr[ 2 ] = *(uint8_t *) star3; break;
case 2 : valueArr[ 2 ] = *(uint16_t *) star3; break;
case 3 : valueArr[ 2 ] = (*(UINT24_T *)star3).value; break;
default:
valueArr[ 2 ] = *(uint32_t *) star3;
}
switch ( GROUP_VARINT_IDX_ARR[idx][6] )
{
case 1 : valueArr[ 3 ] = *(uint8_t *) star4; break;
case 2 : valueArr[ 3 ] = *(uint16_t *) star4; break;
case 3 : valueArr[ 3 ] = (*(UINT24_T *)star4).value; break;
default:
valueArr[ 3 ] = *(uint32_t *) star4;
}
return buf + GROUP_VARINT_IDX_ARR[ idx ][ 7 ];
}
/** ， , 4 uint32 */
inline const uint8_t *
group_varint_decode_uint32_skip ( const uint8_t * buf )
{
return buf + GROUP_VARINT_IDX_ARR[ buf[ 0 ] ][ 7 ];
}
/**
* group varint , 2 uint64
*
* @param valueArr ， 2 。
* @param target buf . ， 2 uint64 17 byte
*
* @return target byte
*/
inline uint8_t *
group_varint_encode_uint64 ( const uint64_t * valueArr, uint8_t * target)
{
uint32_t arr[ 4 ] = { valueArr[0] >> 32,
(valueArr[0] << 32) >> 32,
valueArr[1] >> 32,
(valueArr[1] << 32) >> 32 };
return group_varint_encode_uint32( arr, target);
}
inline uint8_t *
group_varint_encode_uint32 ( uint32_t v1,uint32_t v2, uint32_t v3, uint32_t v4, uint8_t * target)
{
uint32_t valueArr[ 4 ] = {v1, v2 ,v3 ,v4};
return group_varint_encode_uint32( valueArr, target);
}
inline uint8_t *
group_varint_encode_uint64 ( uint64_t v1, uint64_t v2, uint8_t * target)
{
uint32_t valueArr[ 4 ] = { v1 >> 32, (v1 << 32) >> 32, v2 >> 32, (v2 << 32) >> 32 };
return group_varint_encode_uint32( valueArr, target);
}
/**
* buf ， 2 uint64
*
* @param buf buf
* @param valueArr ， 2 uint64
*
* @return buf byte
*/
inline const uint8_t *
group_varint_decode_uint64 ( const uint8_t * buf, uint64_t * valueArr )
{
uint32_t int_arr[ 4 ] = {0};
buf = group_varint_decode_uint32 ( buf, int_arr );
valueArr[ 0 ] = (((uint64_t)(int_arr[0])) << 32) + int_arr[1];
valueArr[ 1 ] = (((uint64_t)(int_arr[2])) << 32) + int_arr[3];
return buf;
}
/** ， , 2 uint64 */
inline const uint8_t *
group_varint_decode_uint64_skip( const uint8_t * buf )
{
return group_varint_decode_uint32_skip ( buf );
}
/**
* zigZag ，
*
* @param n
*
* @return
*/
inline uint32_t zigZag_encode32(int32_t n) { return (n << 1) ^ (n >> 31); }
inline uint64_t zigZag_encode64(int64_t n) { return (n << 1) ^ (n >> 63); }
/**
* zigZag ，
*
* @param n
*
* @return
*/
inline int32_t zigZag_decode32(uint32_t n) { return (n >> 1) ^ -(int32_t)(n & 1); }
inline int64_t zigZag_decode64(uint64_t n) { return (n >> 1) ^ -(int64_t)(n & 1); }
}
#endif /* VARINT_H_ */