1 /** @file bitfield_elements.cpp Bit field elements.
2 *
3 * @authors Copyright (c) 2014-2017 Jaakko Keränen <jaakko.keranen@iki.fi>
4 *
5 * @par License
6 * LGPL: http://www.gnu.org/licenses/lgpl.html
7 *
8 * <small>This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as published by
10 * the Free Software Foundation; either version 3 of the License, or (at your
11 * option) any later version. This program is distributed in the hope that it
12 * will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty
13 * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser
14 * General Public License for more details. You should have received a copy of
15 * the GNU Lesser General Public License along with this program; if not, see:
16 * http://www.gnu.org/licenses</small>
17 */
18
19 #include "de/BitField"
20
21 #include <QMap>
22 #include <QList>
23
24 namespace de {
25
DENG2_PIMPL(BitField::Elements)26 DENG2_PIMPL(BitField::Elements)
27 {
28 struct Element
29 {
30 int numBits;
31 int firstBit;
32 };
33 typedef QMap<Id, Element> Elements; // needs to be ordered
34
35 Elements elements;
36 dsize totalBits;
37
38 /**
39 * Lookup table for quickly finding out which elements are on which bytes of
40 * the packed data. Indexed using the packed data byte index; size ==
41 * packed size.
42 */
43 QList<Ids> lookup;
44
45 Impl(Public *i)
46 : Base(i)
47 , totalBits(0)
48 {}
49
50 Impl(Public *i, Impl const &other)
51 : Base (i)
52 , elements (other.elements)
53 , totalBits(other.totalBits)
54 , lookup (other.lookup)
55 {}
56
57 Element const &element(Id id) const
58 {
59 DENG2_ASSERT(elements.contains(id));
60 return elements.constFind(id).value();
61 }
62 };
63
Elements()64 BitField::Elements::Elements() : d(new Impl(this))
65 {}
66
Elements(Spec const * elements,dsize count)67 BitField::Elements::Elements(Spec const *elements, dsize count)
68 : d(new Impl(this))
69 {
70 add(elements, count);
71 }
72
clear()73 void BitField::Elements::clear()
74 {
75 d->totalBits = 0;
76 d->elements.clear();
77 d->lookup.clear();
78 }
79
add(Id id,dsize numBits)80 BitField::Elements &BitField::Elements::add(Id id, dsize numBits)
81 {
82 DENG2_ASSERT(numBits >= 1);
83
84 Impl::Element elem;
85 elem.numBits = numBits;
86 elem.firstBit = d->totalBits;
87 d->elements.insert(id, elem);
88 d->totalBits += numBits;
89
90 // Update the lookup table.
91 int pos = elem.firstBit / 8;
92 int endPos = (elem.firstBit + (numBits - 1)) / 8;
93 while (d->lookup.size() <= endPos)
94 {
95 d->lookup.append(Ids());
96 }
97 for (int i = pos; i <= endPos; ++i)
98 {
99 d->lookup[i].insert(id);
100 }
101
102 return *this;
103 }
104
add(Spec const * elements,dsize count)105 void BitField::Elements::add(Spec const *elements, dsize count)
106 {
107 while (count-- > 0)
108 {
109 add(elements->id, elements->numBits);
110 elements++;
111 }
112 }
113
add(QList<Spec> const & elements)114 void BitField::Elements::add(QList<Spec> const &elements)
115 {
116 foreach (Spec spec, elements)
117 {
118 add(spec.id, spec.numBits);
119 }
120 }
121
size() const122 int BitField::Elements::size() const
123 {
124 return d->elements.size();
125 }
126
at(int index) const127 BitField::Spec BitField::Elements::at(int index) const
128 {
129 DENG2_ASSERT(index >= 0);
130 DENG2_ASSERT(index < size());
131
132 Impl::Element elem = d->elements.values()[index];
133 Spec spec;
134 spec.id = d->elements.keys()[index];
135 spec.numBits = elem.numBits;
136 return spec;
137 }
138
elementLayout(Id const & id,int & firstBit,int & numBits) const139 void BitField::Elements::elementLayout(Id const &id, int &firstBit, int &numBits) const
140 {
141 Impl::Element const &elem = d->element(id);
142 firstBit = elem.firstBit;
143 numBits = elem.numBits;
144 }
145
bitCount() const146 int BitField::Elements::bitCount() const
147 {
148 return d->totalBits;
149 }
150
ids() const151 BitField::Ids BitField::Elements::ids() const
152 {
153 Ids ids;
154 foreach (Id id, d->elements.keys())
155 {
156 ids.insert(id);
157 }
158 return ids;
159 }
160
idsLaidOutOnByte(int index) const161 BitField::Ids BitField::Elements::idsLaidOutOnByte(int index) const
162 {
163 return d.getConst()->lookup.at(index);
164 }
165
166 } // namespace de
167