Mercurial > dedupe

comparison FastBitDecoder.cpp @ 46:877327e9061a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
N-Tree for decoding.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Mon, 10 Sep 2012 21:31:10 +0200
parents
children f8d0ea827db3
comparison
equal deleted inserted replaced
45:41cc0d8ac77f 46:877327e9061a
1 #include "FastBitDecoder.hpp"
2
3 #include "BitDecoder.hpp"
4
5 #include <QtCore/QDebug>
6
7 #include <cassert>
8
9 unsigned char FastBitDecoder::getPaddedChar(const QBitArray& bits, uint offset)
10 {
11 unsigned char retVal = 0;
12 size_t n = std::min(8u, bits.size() - offset);
13 for (size_t i = 0; i < n; ++i) {
14 retVal |= (bits.testBit(i + offset) ? 1 : 0) << (7 - i) ;
15 }
16 return retVal;
17 }
18
19 QBitArray FastBitDecoder::removeFirst(const QBitArray& bits)
20 {
21 size_t N = bits.size();
22 assert(N - 8 > 0);
23 size_t n = N - 8;
24 QBitArray retVal(n);
25 for (size_t i = 0; i < n; ++i) {
26 retVal.setBit(i, bits.at(i + 8));
27 }
28 return retVal;
29 }
30
31
32 void FastBitDecoder::fill()
33 {
34 for (size_t i = 0; i < N; ++i) {
35 if (decoder[i] != 0) {
36 decoder[i]->fill();
37 }
38 else if (data[i] == 0) {
39 assert(data[i - 1]);
40 data[i] = data[i - 1];
41 numBits[i] = numBits[i - 1];
42 }
43 }
44 }
45
46 void FastBitDecoder::blank()
47 {
48 for (size_t i = 0; i < N; ++i) {
49 decoder[i] = 0;
50 data[i] = 0;
51 numBits[i] = 0;
52 }
53 }
54
55 FastBitDecoder::FastBitDecoder()
56 {
57 blank();
58 }
59
60
61 FastBitDecoder::FastBitDecoder(const QMap<QString, QBitArray>& encoder)
62 {
63 blank();
64 for(QMap<QString, QBitArray>::const_iterator it = encoder.begin();
65 it != encoder.end(); ++it) {
66 insert(it.value(), it.key());
67 }
68 fill();
69 }
70
71
72 void FastBitDecoder::insert(const QBitArray& key, const QString& value)
73 {
74 unsigned char l = getPaddedChar(key);
75 if (key.size() <= 8) {
76 data[l] = new QString(value);
77 numBits[l] = key.size();
78 }
79 else {
80 if (!decoder[l])
81 decoder[l] = new FastBitDecoder();
82 decoder[l]->insert(removeFirst(key), value);
83 numBits[l] = 8;
84 }
85 }
86
87
88 uint FastBitDecoder::decode(QString& resString, const QBitArray& bits, uint offset) const
89 {
90 unsigned char l = getPaddedChar(bits, offset);
91 if (data[l]) {
92 resString.append(*data[l]);
93 return numBits[l];
94 }
95 else {
96 return decoder[l]->decode(resString, bits, offset + 8) + 8;
97 }
98 }
99
100 QString FastBitDecoder::decode(const QString& bits) const
101 {
102 return decode(BitDecoder::bitsFromString(bits));
103 }