Branch data Line data Source code
1 : : /** @file bitstream.cc
2 : : * @brief Classes to encode/decode a bitstream.
3 : : */
4 : : /* Copyright (C) 2004,2005,2006,2008 Olly Betts
5 : : *
6 : : * This program is free software; you can redistribute it and/or
7 : : * modify it under the terms of the GNU General Public License as
8 : : * published by the Free Software Foundation; either version 2 of the
9 : : * License, or (at your option) any later version.
10 : : *
11 : : * This program is distributed in the hope that it will be useful,
12 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : : * GNU General Public License for more details.
15 : : *
16 : : * You should have received a copy of the GNU General Public License
17 : : * along with this program; if not, write to the Free Software
18 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
19 : : * USA
20 : : */
21 : :
22 : : #include <config.h>
23 : :
24 : : #include "bitstream.h"
25 : :
26 : : #include <xapian/types.h>
27 : :
28 : : #include "omassert.h"
29 : :
30 : : #include <cmath>
31 : : #include <vector>
32 : :
33 : : using namespace std;
34 : :
35 : : static const unsigned char flstab[256] = {
36 : : 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
37 : : 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
38 : : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
39 : : 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
40 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
41 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
42 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
43 : : 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
44 : : 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
45 : : 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
46 : : 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
47 : : 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
48 : : 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
49 : : 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
50 : : 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
51 : : 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
52 : : };
53 : :
54 : : // Highly optimised fls() implementation.
55 : 293811 : inline int my_fls(unsigned mask)
56 : : {
57 : 293811 : int result = 0;
58 [ + + ]: 293811 : if (mask >= 0x10000u) {
59 : 1512 : mask >>= 16;
60 : 1512 : result = 16;
61 : : }
62 [ + + ]: 293811 : if (mask >= 0x100u) {
63 : 41706 : mask >>= 8;
64 : 41706 : result += 8;
65 : : }
66 : 293811 : return result + flstab[mask];
67 : : }
68 : :
69 : : namespace Xapian {
70 : :
71 : : void
72 : 232005 : BitWriter::encode(size_t value, size_t outof)
73 : : {
74 : : Assert(value < outof);
75 : 232005 : size_t bits = my_fls(outof - 1);
76 : 232005 : const size_t spare = (1 << bits) - outof;
77 [ + + ]: 232005 : if (spare) {
78 : 225015 : const size_t mid_start = (outof - spare) / 2;
79 [ + + ]: 225015 : if (value >= mid_start + spare) {
80 : 23271 : value = (value - (mid_start + spare)) | (1 << (bits - 1));
81 [ + + ]: 201744 : } else if (value >= mid_start) {
82 : 107535 : --bits;
83 : : }
84 : : }
85 : :
86 [ - + ]: 232005 : if (bits + n_bits > 32) {
87 : : // We need to write more bits than there's empty room for in
88 : : // the accumulator. So we arrange to shift out 8 bits, then
89 : : // adjust things so we're adding 8 fewer bits.
90 : : Assert(bits <= 32);
91 : 0 : acc |= (value << n_bits);
92 : 0 : buf += char(acc);
93 : 0 : acc >>= 8;
94 : 0 : value >>= 8;
95 : 0 : bits -= 8;
96 : : }
97 : 232005 : acc |= (value << n_bits);
98 : 232005 : n_bits += bits;
99 [ + + ]: 389745 : while (n_bits >= 8) {
100 : 157740 : buf += char(acc);
101 : 157740 : acc >>= 8;
102 : 157740 : n_bits -= 8;
103 : : }
104 : 232005 : }
105 : :
106 : : void
107 : 175686 : BitWriter::encode_interpolative(const vector<Xapian::termpos> &pos, int j, int k)
108 : : {
109 [ + + ]: 295053 : while (j + 1 < k) {
110 : 119367 : const size_t mid = (j + k) / 2;
111 : : // Encode one out of (pos[k] - pos[j] + 1) values
112 : : // (less some at either end because we must be able to fit
113 : : // all the intervening pos in)
114 : 119367 : const size_t outof = pos[k] - pos[j] + j - k + 1;
115 : 119367 : const size_t lowest = pos[j] + mid - j;
116 : 119367 : encode(pos[mid] - lowest, outof);
117 : 119367 : encode_interpolative(pos, j, mid);
118 : 119367 : j = mid;
119 : : }
120 : 175686 : }
121 : :
122 : : Xapian::termpos
123 : 61806 : BitReader::decode(Xapian::termpos outof)
124 : : {
125 : 61806 : size_t bits = my_fls(outof - 1);
126 : 61806 : const size_t spare = (1 << bits) - outof;
127 : 61806 : const size_t mid_start = (outof - spare) / 2;
128 : : Xapian::termpos p;
129 [ + + ]: 61806 : if (spare) {
130 : 60453 : p = read_bits(bits - 1);
131 [ + + ]: 60453 : if (p < mid_start) {
132 [ + + ]: 7341 : if (read_bits(1)) p += mid_start + spare;
133 : : }
134 : : } else {
135 : 1353 : p = read_bits(bits);
136 : : }
137 : : Assert(p < outof);
138 : 61806 : return p;
139 : : }
140 : :
141 : : unsigned int
142 : 69147 : BitReader::read_bits(int count)
143 : : {
144 : : unsigned int result;
145 [ - + ]: 69147 : if (count > 25) {
146 : : // If we need more than 25 bits, read in two goes to ensure that we
147 : : // don't overflow acc. This is a little more conservative than it
148 : : // needs to be, but such large values will inevitably be rare (because
149 : : // you can't fit very many of them into 2^32!)
150 : : Assert(count <= 32);
151 : 0 : result = read_bits(16);
152 : 0 : return result | (read_bits(count - 16) << 16);
153 : : }
154 [ + + ]: 117213 : while (n_bits < count) {
155 : : Assert(idx < buf.size());
156 : 48066 : acc |= static_cast<unsigned char>(buf[idx++]) << n_bits;
157 : 48066 : n_bits += 8;
158 : : }
159 : 69147 : result = acc & ((1u << count) - 1);
160 : 69147 : acc >>= count;
161 : 69147 : n_bits -= count;
162 : 69147 : return result;
163 : : }
164 : :
165 : : void
166 : 58203 : BitReader::decode_interpolative(vector<Xapian::termpos> & pos, int j, int k)
167 : : {
168 [ + + ]: 113721 : while (j + 1 < k) {
169 : 55518 : const size_t mid = (j + k) / 2;
170 : : // Decode one out of (pos[k] - pos[j] + 1) values
171 : : // (less some at either end because we must be able to fit
172 : : // all the intervening pos in)
173 : 55518 : const size_t outof = pos[k] - pos[j] + j - k + 1;
174 : 55518 : pos[mid] = decode(outof) + (pos[j] + mid - j);
175 : 55518 : decode_interpolative(pos, j, mid);
176 : 55518 : j = mid;
177 : : }
178 : 58203 : }
179 : :
180 : : }
|
