Mercurial > dedupe

annotate FastBitDecoder.cpp @ 62:247adcbbaf8b

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