/
BitMap.h
181 lines (181 loc) · 4.79 KB
/
BitMap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#ifndef WT_NODE_H
#define WT_NODE_H
#include <string.h>
#include "loadkit.h"
#include "savekit.h"
#include "InArray.h"
#include "BaseClass.h"
#include <math.h>
#include <iostream>
#include <bitset>
using namespace std;
class Dmap
{
public:
Dmap();
u64 GetMemorySize()
{
return SBd->GetMemorySize() + Bd->GetMemorySize() + datanum * datawidth / 8;
};
Dmap(u64 data_num, u32 data_width);
Dmap(u64 len, u32 size, int Blength, int SBlength);
void write(savekit &s)
{
s.writeu64(datanum);
s.writeu32(datawidth);
s.writei32(Blength);
s.writei32(SBlength);
SBd->write(s);
Bd->write(s);
};
void load(loadkit &s)
{
s.loadu64(this->datanum);
s.loadu32(this->datawidth);
s.loadi32(this->Blength);
s.loadi32(this->SBlength);
this->SBd = new InArray();
this->Bd = new InArray();
this->SBd->load(s);
this->Bd->load(s);
};
~Dmap(void);
void SetValue(u64 index, u64 v);
void constructrank(int Blength, int SBlength, int offrate = 5);
u64 rank(u64 i)
{
u64 Mdnum = i >> Blength;
u64 SBnum = Mdnum >> SBlength;
u64 Sbdbefore = SBd->GetValue(SBnum);
u64 Sdnowi = Sbdbefore + Bd->GetValue(Mdnum);
u32 popc_n = (i - (i & 0xffffff00)) >> 5;
u32 temp = i & 0xffffffe0;
u32 left_s = i - temp;
u32 d_s = Mdnum * (1 << (Blength - 5));
for (u32 j = 0; j < popc_n; j++)
Sdnowi += (u32)__builtin_popcount(data[d_s + j]);
if (left_s != 0)
{
u32 left1 = data[d_s + popc_n] & (0xffffffff << (32 - left_s));
Sdnowi += (u32)__builtin_popcount(left1);
}
return Sdnowi + 1;
}
int Save(savekit &s)
{
s.writei32(Blength);
s.writei32(SBlength);
SBd->write(s);
Bd->write(s);
s.writeu64(datanum);
s.writeu32(datawidth);
u64 len = (datanum * datawidth);
if (len % 32 == 0)
len = len / 32 + 1;
else
len = len / 32 + 2;
s.writeu64(len);
s.writeu32array(data, len);
return 0;
}
int Load(loadkit &s)
{
s.loadi32(this->Blength);
s.loadi32(this->SBlength);
SBd = new InArray();
SBd->load(s);
Bd = new InArray();
Bd->load(s);
s.loadu64(datanum);
s.loadu32(datawidth);
u64 len = 0;
s.loadu64(len);
s.loadu32array(data, len);
return 0;
}
private:
u64 mask;
u32 *data;
u64 datanum;
u32 datawidth;
InArray *SBd;
InArray *Bd;
int SBlength;
int Blength;
};
class BitMap
{
public:
BitMap(unsigned long long int *bitbuff, i64 bit_len, int level, int block_size = 1024, unsigned char label = '\0', uchar **tables = NULL);
BitMap(){};
BitMap(uchar **tables) : Z(tables[0]), R(tables[1]) {}
~BitMap();
i64 Rank(i64 pos);
i64 Rank(i64 pos, int &bit);
void Rank(i64 pos_left, i64 pos_right, i64 &rank_left, i64 &rank_right);
void Left(BitMap *left);
BitMap *Left() { return left; };
void Right(BitMap *right);
BitMap *Right() { return right; };
void testselect();
unsigned char Label();
i64 GetBitLen();
int Getlevel();
int Load(loadkit &s);
int Save(savekit &S);
u64 SizeInByte();
u64 All01Nums() { return all01; };
u64 PlainNums() { return plain; };
u64 RlgNums() { return rlg01; };
u64 PlainSizeInByte() { return plainsize; };
u64 RlgSizeInByte() { return rlgsize; };
private:
uchar *Z;
uchar *R;
BitMap(const BitMap &);
BitMap &operator=(const BitMap &right);
void Coding();
int GetBit(u64 *data, i64 index);
u16 Zeros(u16 x) { return (Z[x >> 8] == 8) ? Z[x >> 8] + Z[(uchar)x] : Z[x >> 8]; }
u64 GetBits(u64 *buff, i64 &index, int bits);
int GetZerosRuns(u64 *buff, i64 &index);
int FixedDecode(u64 *buff, i64 &index);
int GammaDecode(u64 *buff, i64 &index);
int GetRuns(u64 *data, i64 &index, int &bit);
void Append_g(u64 *temp, i64 &index, u32 value);
void BitCopy(u64 *temp, i64 &index, u64 value);
void BitCopy(u64 *temp, i64 &index, u64 *data, i64 index1, int len);
void RL_Rank(u64 *buff, i64 &index, int bits_left, int bits_right, i64 &rank_left, i64 &rank_right, int rl_type);
i64 RL_Rank(u64 *buff, i64 &index, int bits_num, int rl_type);
i64 RL_Rank(u64 *buff, i64 &index, int bits_num, int rl_type, int &bit);
i64 RL0_Rank(u64 *buff, i64 &index, int bits_num);
int RL0_Bit(u64 *buff, i64 &index, int bits);
i64 RL0_Rank(u64 *buff, i64 &index, int bits, int &bit);
i64 RL1_Rank(u64 *buff, i64 &index, int bits);
int RL1_Bit(u64 *buff, i64 &index, int bits);
i64 RL1_Rank(u64 *buff, i64 &index, int bits, int &bit);
void Plain_Rank(u64 *buff, i64 &index, int bits_left, int bits_right, i64 &rank_left, i64 &rank_right);
i64 Plain_Rank(u64 *buff, i64 &index, int bits);
int Plain_Bit(u64 *buff, i64 &index, int bits);
i64 Plain_Rank(u64 *buff, i64 &index, int bits, int &bit);
int level;
unsigned char label;
unsigned long long int *data;
i64 bitLen;
u64 memorysize;
int block_size;
int block_width;
int super_block_size;
BitMap *left;
BitMap *right;
InArray *superblock;
InArray *block;
InArray *coding_style;
u64 all01 = 0;
u64 plain = 0;
u64 rlg01 = 0;
u64 plainsize = 0;
u64 rlgsize = 0;
unsigned long long int *buff;
};
#endif