2 * @brief Classes to encode/decode a bitstream.
4 /* Copyright (C) 2004,2005,2006,2008,2012,2013,2014,2018 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
22 #ifndef XAPIAN_INCLUDED_BITSTREAM_H
23 #define XAPIAN_INCLUDED_BITSTREAM_H
25 #include <xapian/types.h>
32 /// Create a stream to which non-byte-aligned values can be written.
40 BitWriter() : n_bits(0), acc(0) { }
42 /// Construct with the contents of seed already in the stream.
43 explicit BitWriter(const std::string
& seed
)
44 : buf(seed
), n_bits(0), acc(0) { }
46 /// Encode value, known to be less than outof.
47 void encode(Xapian::termpos value
, Xapian::termpos outof
);
49 /// Finish encoding and return the encoded data as a std::string.
50 std::string
& freeze() {
59 /// Perform interpolative encoding of pos elements between j and k.
60 void encode_interpolative(const std::vector
<Xapian::termpos
>& pos
, int j
, int k
);
63 /// Read a stream created by BitWriter.
70 Xapian::termpos
read_bits(int count
);
74 Xapian::termpos pos_k
;
77 struct DIState
: public DIStack
{
78 Xapian::termpos pos_j
;
80 void set_j(int j_
, Xapian::termpos pos_j_
) {
84 void set_k(int k_
, Xapian::termpos pos_k_
) {
92 DIState() { uninit(); }
93 DIState(int j_
, int k_
,
94 Xapian::termpos pos_j_
, Xapian::termpos pos_k_
) {
98 void operator=(const DIStack
& o
) {
102 bool is_next() const { return j
+ 1 < k
; }
103 bool is_initialized() const {
106 // Given pos[j] = pos_j and pos[k] = pos_k, how many possible position
107 // values are there for the value midway between?
108 Xapian::termpos
outof() const {
109 return pos_k
- pos_j
- Xapian::termpos(k
- j
) + 1;
113 std::vector
<DIStack
> di_stack
;
120 // Construct with the contents of buf_.
121 explicit BitReader(const std::string
&buf_
)
122 : buf(buf_
), idx(0), n_bits(0), acc(0) { }
124 // Construct with the contents of buf_, skipping some bytes.
125 BitReader(const std::string
&buf_
, size_t skip
)
126 : buf(buf_
, skip
), idx(0), n_bits(0), acc(0) { }
128 // Initialise from buf_, optionally skipping some bytes.
129 void init(const std::string
&buf_
, size_t skip
= 0) {
130 buf
.assign(buf_
, skip
, std::string::npos
);
138 // Decode value, known to be less than outof.
139 Xapian::termpos
decode(Xapian::termpos outof
, bool force
= false);
141 // Check all the data has been read. Because it'll be zero padded
142 // to fill a byte, the best we can actually do is check that
143 // there's less than a byte left and that all remaining bits are
145 bool check_all_gone() const {
146 return (idx
== buf
.size() && n_bits
<= 7 && acc
== 0);
149 /// Perform interpolative decoding between elements between j and k.
150 void decode_interpolative(int j
, int k
,
151 Xapian::termpos pos_j
, Xapian::termpos pos_k
);
153 /// Perform on-demand interpolative decoding.
154 Xapian::termpos
decode_interpolative_next();
159 using Xapian::BitWriter
;
160 using Xapian::BitReader
;
162 #endif // XAPIAN_INCLUDED_BITSTREAM_H