2 * @brief Classes to encode/decode a bitstream.
4 /* Copyright (C) 2004,2005,2006,2008,2013,2014,2016,2017 Olly Betts
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.
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.
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
24 #include "bitstream.h"
26 #include <xapian/types.h>
35 // Highly optimised fls() implementation.
36 inline int highest_order_bit(unsigned mask
)
38 #if HAVE_DECL___BUILTIN_CLZ
39 return mask
? 32 - __builtin_clz(mask
) : 0;
41 static const unsigned char flstab
[256] = {
42 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
43 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
44 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
45 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
46 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
47 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
48 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
49 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
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 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
53 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
54 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
55 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
56 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
57 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
61 if (mask
>= 0x10000u
) {
69 return result
+ flstab
[mask
];
75 /// Shift left that's safe for shifts wider than the type.
76 template<typename T
, typename U
>
78 T
safe_shl(T x
, U shift
)
80 return (shift
>= sizeof(T
) * 8 ? 0 : x
<< shift
);
84 BitWriter::encode(Xapian::termpos value
, Xapian::termpos outof
)
86 Assert(value
< outof
);
87 unsigned bits
= highest_order_bit(outof
- 1);
88 const Xapian::termpos spare
= safe_shl(Xapian::termpos(1), bits
) - outof
;
90 /* If we have spare values, we can use one fewer bit to encode some
91 * values. We shorten the values in the middle of the range, as
92 * testing (on positional data) shows this works best. "Managing
93 * Gigabytes" suggests reversing this for the lowest level and encoding
94 * the end values of the range shorter, which is contrary to our
95 * testing (MG is talking about posting lists, which probably have
96 * different characteristics).
98 * For example, if outof is 11, the codes emitted are:
113 * Note the LSB comes first in the bitstream, so these codes need to be
114 * suffix-free to be decoded.
116 const Xapian::termpos mid_start
= (outof
- spare
) / 2;
117 if (value
>= mid_start
+ spare
) {
118 value
= (value
- (mid_start
+ spare
)) | (1u << (bits
- 1));
119 } else if (value
>= mid_start
) {
124 if (bits
+ n_bits
> 32) {
125 // We need to write more bits than there's empty room for in
126 // the accumulator. So we arrange to shift out 8 bits, then
127 // adjust things so we're adding 8 fewer bits.
129 acc
|= (value
<< n_bits
);
135 acc
|= (value
<< n_bits
);
137 while (n_bits
>= 8) {
145 BitWriter::encode_interpolative(const Xapian::VecCOW
<Xapian::termpos
> &pos
, int j
, int k
)
147 // "Interpolative code" - for an algorithm description, see "Managing
148 // Gigabytes" - pages 126-127 in the second edition. You can probably
149 // view those pages in google books.
151 const Xapian::termpos mid
= j
+ (k
- j
) / 2;
152 // Encode one out of (pos[k] - pos[j] + 1) values
153 // (less some at either end because we must be able to fit
154 // all the intervening pos in)
155 const Xapian::termpos outof
= pos
[k
] - pos
[j
] + j
- k
+ 1;
156 const Xapian::termpos lowest
= pos
[j
] + mid
- j
;
157 encode(pos
[mid
] - lowest
, outof
);
158 encode_interpolative(pos
, j
, mid
);
164 BitReader::decode(Xapian::termpos outof
, bool force
)
167 Assert(force
== di_current
.is_initialized());
168 Xapian::termpos bits
= highest_order_bit(outof
- 1);
169 const Xapian::termpos spare
= safe_shl(Xapian::termpos(1), bits
) - outof
;
170 const Xapian::termpos mid_start
= (outof
- spare
) / 2;
173 pos
= read_bits(bits
- 1);
174 if (pos
< mid_start
) {
175 if (read_bits(1)) pos
+= mid_start
+ spare
;
178 pos
= read_bits(bits
);
185 BitReader::read_bits(int count
)
189 // If we need more than 25 bits, read in two goes to ensure that we
190 // don't overflow acc. This is a little more conservative than it
191 // needs to be, but such large values will inevitably be rare (because
192 // you can't fit very many of them into 2^32!)
194 result
= read_bits(16);
195 return result
| (read_bits(count
- 16) << 16);
197 while (n_bits
< count
) {
199 acc
|= static_cast<unsigned char>(*p
++) << n_bits
;
202 result
= acc
& ((1u << count
) - 1);
209 BitReader::decode_interpolative(int j
, int k
,
210 Xapian::termpos pos_j
, Xapian::termpos pos_k
)
212 Assert(!di_current
.is_initialized());
213 di_stack
.reserve(highest_order_bit(pos_k
- pos_j
));
214 di_current
.set_j(j
, pos_j
);
215 di_current
.set_k(k
, pos_k
);
219 BitReader::decode_interpolative_next()
221 Assert(di_current
.is_initialized());
222 while (!di_stack
.empty() || di_current
.is_next()) {
223 if (!di_current
.is_next()) {
224 Xapian::termpos pos_ret
= di_current
.pos_k
;
225 di_current
= di_stack
.back();
227 int mid
= (di_current
.j
+ di_current
.k
) / 2;
228 di_current
.set_j(mid
, pos_ret
);
231 di_stack
.push_back(di_current
);
232 int mid
= (di_current
.j
+ di_current
.k
) / 2;
233 Xapian::termpos pos_mid
= decode(di_current
.outof(), true) +
234 (di_current
.pos_j
+ mid
- di_current
.j
);
235 di_current
.set_k(mid
, pos_mid
);
237 #ifdef XAPIAN_ASSERTIONS
240 return di_current
.pos_k
;