Mercurial > dedupe

annotate FastBitDecoder.cpp @ 57:c8111de2e0bb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add functionality to decode directly from bitstring. Use BitArrays getPaddedChar directly.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Thu, 13 Sep 2012 23:53:35 +0200
parents f8d0ea827db3
children 247adcbbaf8b
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
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5 #include <cassert>
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
6
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 46
diff changeset
7 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
8 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9 unsigned char retVal = 0;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 size_t n = std::min(8u, bits.size() - offset);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 for (size_t i = 0; i < n; ++i) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 retVal |= (bits.testBit(i + offset) ? 1 : 0) << (7 - i) ;
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 return retVal;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 46
diff changeset
17 BitArray FastBitDecoder::removeFirst(const BitArray& bits)
46
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
18 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19 size_t N = bits.size();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 assert(N - 8 > 0);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 size_t n = N - 8;
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 46
diff changeset
22 BitArray retVal(n);
46
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23 for (size_t i = 0; i < n; ++i) {
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 46
diff changeset
24 retVal.setBit(i, bits.testBit(i + 8));
46
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 return retVal;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29
57
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
30 FastBitDecoder::~FastBitDecoder()
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
31 {
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
32 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
33 delete decoder[i];
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
34 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
35 delete data[i];
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
36 }
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
37 }
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
38
46
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 void FastBitDecoder::fill()
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
40 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41 for (size_t i = 0; i < N; ++i) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
42 if (decoder[i] != 0) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43 decoder[i]->fill();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
44 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 else if (data[i] == 0) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
46 assert(data[i - 1]);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
47 data[i] = data[i - 1];
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
48 numBits[i] = numBits[i - 1];
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 }
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 void FastBitDecoder::blank()
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
54 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
55 for (size_t i = 0; i < N; ++i) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 decoder[i] = 0;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57 data[i] = 0;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
58 numBits[i] = 0;
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 }
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 FastBitDecoder::FastBitDecoder()
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 blank();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
65 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
67
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 46
diff changeset
68 FastBitDecoder::FastBitDecoder(const QMap<QString, BitArray>& encoder)
46
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
69 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
70 blank();
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 46
diff changeset
71 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
72 it != encoder.end(); ++it) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
73 insert(it.value(), it.key());
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 fill();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
76 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
77
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
78
49
f8d0ea827db3 Use BitArray.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 46
diff changeset
79 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
80 {
57
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
81 unsigned char l = key.getPaddedChar();
46
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
82 if (key.size() <= 8) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
83 data[l] = new QString(value);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
84 numBits[l] = key.size();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
85 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
86 else {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
87 if (!decoder[l])
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
88 decoder[l] = new FastBitDecoder();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
89 decoder[l]->insert(removeFirst(key), value);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
90 numBits[l] = 8;
57
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
91 }
46
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
92 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
93
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
94
57
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
95 uint FastBitDecoder::decode(QString& resString,
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
96 const BitArray& bits,
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
97 uint offset) const
46
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
98 {
57
c8111de2e0bb Add functionality to decode directly from bitstring.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 49
diff changeset
99 unsigned char l = bits.getPaddedChar(offset);
46
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
100 if (data[l]) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
101 resString.append(*data[l]);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
102 return numBits[l];
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
103 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
104 else {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
105 return decoder[l]->decode(resString, bits, offset + 8) + 8;
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 }
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 QString FastBitDecoder::decode(const QString& bits) const
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
110 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
111 return decode(BitDecoder::bitsFromString(bits));
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
112 }