Mercurial > dedupe

annotate 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
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 <QtCore/QDebug>
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 #include <cassert>
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 FastBitDecoder::getPaddedChar(const QBitArray& bits, uint offset)
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 unsigned char retVal = 0;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 size_t n = std::min(8u, bits.size() - offset);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13 for (size_t i = 0; i < n; ++i) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14 retVal |= (bits.testBit(i + offset) ? 1 : 0) << (7 - i) ;
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 return retVal;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17 }
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 QBitArray FastBitDecoder::removeFirst(const QBitArray& bits)
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 size_t N = bits.size();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22 assert(N - 8 > 0);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23 size_t n = N - 8;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 QBitArray retVal(n);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 for (size_t i = 0; i < n; ++i) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 retVal.setBit(i, bits.at(i + 8));
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 return retVal;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
31
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
32 void FastBitDecoder::fill()
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34 for (size_t i = 0; i < N; ++i) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
35 if (decoder[i] != 0) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 decoder[i]->fill();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
37 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38 else if (data[i] == 0) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 assert(data[i - 1]);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
40 data[i] = data[i - 1];
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41 numBits[i] = numBits[i - 1];
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 }
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
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
46 void FastBitDecoder::blank()
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 for (size_t i = 0; i < N; ++i) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
49 decoder[i] = 0;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
50 data[i] = 0;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
51 numBits[i] = 0;
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 }
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 FastBitDecoder::FastBitDecoder()
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57 blank();
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
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
61 FastBitDecoder::FastBitDecoder(const QMap<QString, QBitArray>& encoder)
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
62 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
63 blank();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
64 for(QMap<QString, QBitArray>::const_iterator it = encoder.begin();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
65 it != encoder.end(); ++it) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66 insert(it.value(), it.key());
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 fill();
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
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
71
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
72 void FastBitDecoder::insert(const QBitArray& key, const QString& value)
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
73 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
74 unsigned char l = getPaddedChar(key);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
75 if (key.size() <= 8) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
76 data[l] = new QString(value);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
77 numBits[l] = key.size();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
78 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
79 else {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
80 if (!decoder[l])
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
81 decoder[l] = new FastBitDecoder();
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
82 decoder[l]->insert(removeFirst(key), value);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
83 numBits[l] = 8;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
84 }
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
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
87
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
88 uint FastBitDecoder::decode(QString& resString, const QBitArray& bits, uint offset) const
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
89 {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
90 unsigned char l = getPaddedChar(bits, offset);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
91 if (data[l]) {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
92 resString.append(*data[l]);
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
93 return numBits[l];
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
94 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
95 else {
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
96 return decoder[l]->decode(resString, bits, offset + 8) + 8;
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
97 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
98 }
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
99
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
100 QString FastBitDecoder::decode(const QString& bits) const
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 return decode(BitDecoder::bitsFromString(bits));
877327e9061a N-Tree for decoding.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
103 }