Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
bit_stream.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * thrill/core/bit_stream.hpp
3  *
4  * Encode bit stream into a BlockWriter and read from BlockReader.
5  *
6  * Part of Project Thrill - http://project-thrill.org
7  *
8  * Copyright (C) 2017 Timo Bingmann <[email protected]>
9  *
10  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
11  ******************************************************************************/
12 
13 #pragma once
14 #ifndef THRILL_CORE_BIT_STREAM_HEADER
15 #define THRILL_CORE_BIT_STREAM_HEADER
16 
17 #include <thrill/common/math.hpp>
20 
21 #include <tlx/die.hpp>
22 
23 namespace thrill {
24 namespace core {
25 
26 template <typename BlockWriter>
28 {
29 protected:
30  //! number of bits in buffer_
31  enum : size_t { buffer_bits_ = sizeof(size_t) * 8 };
32 
33  //! modulo mask of number of bits in buffer for pos_ counter
34  enum : size_t { mask = buffer_bits_ - 1 };
35 
36 public:
37  explicit BitStreamWriter(BlockWriter& block_writer)
38  : block_writer_(block_writer) {
39  die_unless(block_writer.block_size() % sizeof(size_t) == 0);
40  }
41 
42  //! non-copyable: delete copy-constructor
43  BitStreamWriter(const BitStreamWriter&) = delete;
44  //! non-copyable: delete assignment operator
46  //! move-constructor: default
47  BitStreamWriter(BitStreamWriter&&) = default;
48  //! move-assignment operator: default
50 
52  FlushBits();
53  }
54 
55  /*!
56  * Append k bits to the data array.
57  *
58  * \param value new value
59  * \param bits k = size of the new value in bits
60  */
61  void PutBits(const size_t& value, unsigned bits) {
62  // check that only valid bits are set in value
63  assert(bits == 64 || (value & (~size_t(0) << bits)) == 0);
64 
65  if (pos_ + bits > buffer_bits_) {
66  // buffer overflown
67  int length_first = buffer_bits_ - pos_,
68  length_second = bits - length_first;
69 
70  buffer_ |= value >> (bits - length_first);
71  block_writer_.PutRaw(buffer_);
72 
73  buffer_ = value << (buffer_bits_ - length_second);
74  pos_ = (pos_ + bits) & mask;
75  }
76  else if (pos_ + bits == buffer_bits_) {
77  // buffer just filled
78  buffer_ |= value;
79  block_writer_.PutRaw(buffer_);
80 
81  buffer_ = 0;
82  pos_ = 0;
83  }
84  else {
85  // buffer not full
86  buffer_ |= value << (buffer_bits_ - (bits + pos_));
87  pos_ += bits;
88  }
89  }
90 
91  /*!
92  * Flush out buffered bits
93  */
94  void FlushBits() {
95  if (pos_ != 0) {
96  block_writer_.PutRaw(buffer_);
97  buffer_ = 0;
98  pos_ = 0;
99  }
100  }
101 
102 protected:
103  //! Output BlockWriter
104  BlockWriter& block_writer_;
105 
106  //! current buffer of 32/64 bits
107  size_t buffer_ = 0;
108 
109  //! currently filled number of bits
110  size_t pos_ = 0;
111 };
112 
113 template <typename BlockReader>
115 {
116 protected:
117  //! number of bits in buffer_
118  enum : size_t { buffer_bits_ = sizeof(size_t) * 8 };
119 
120  //! modulo mask of number of bits in buffer for pos_ counter
121  enum : size_t { mask = (buffer_bits_ - 1) };
122 
123  //! highest bit set
124  enum : size_t { msb_set = ((size_t)1) << (buffer_bits_ - 1) };
125 
126 public:
127  explicit BitStreamReader(BlockReader& block_reader)
128  : block_reader_(block_reader)
129  { }
130 
131  //! non-copyable: delete copy-constructor
132  BitStreamReader(const BitStreamReader&) = delete;
133  //! non-copyable: delete assignment operator
134  BitStreamReader& operator = (const BitStreamReader&) = delete;
135  //! move-constructor: default
136  BitStreamReader(BitStreamReader&&) = default;
137  //! move-assignment operator: default
139 
140  /*!
141  * Get bits at the cursor.
142  *
143  * \param bits number of bits to return
144  *
145  * \return {bits} at the cursor
146  */
147  size_t GetBits(unsigned bits) {
148  size_t res;
149  if (pos_ + bits > buffer_bits_) {
150  // value continuing in next array element
151  int bits_first = buffer_bits_ - pos_ + 1,
152  bits_second = bits - bits_first;
153 
154  res = buffer_ >> (pos_ - 1) << bits_second;
155  buffer_ = block_reader_.template GetRaw<size_t>();
156 
157  res |= buffer_ >> (2 * buffer_bits_ - bits - pos_);
158 
159  pos_ = (pos_ + bits) & mask;
160  buffer_ <<= pos_;
161  }
162  else {
163  // in single array element
164  res = buffer_ >> (buffer_bits_ - bits);
165  pos_ += bits;
166  buffer_ <<= bits;
167  }
168  return res;
169  }
170 
171  //! Test if the buffer contains a zero or if another item can be read. This
172  //! test is used by the Golomb decoder to check if another value is
173  //! available.
175 
176  if (pos_ == buffer_bits_) {
177  if (!block_reader_.HasNext())
178  return false;
179 
180  pos_ = 0;
181  buffer_ = block_reader_.template GetRaw<size_t>();
182  }
183 
184  // this buffer contains some zero or next available.
185  return (~buffer_ >> pos_) != 0 || block_reader_.HasNext();
186  }
187 
188  /*!
189  * Returns the number of continuous 1 bits at the cursor, followed by a
190  * zero. Used in Golomb decoding.
191  *
192  * \return Number of continuous 1 bits at the cursor, the zero is skipped.
193  */
195  unsigned no_ones = 0;
196 
197  if (pos_ == buffer_bits_) {
198  pos_ = 0;
199  buffer_ = block_reader_.template GetRaw<size_t>();
200  }
201 
202  while (buffer_ & msb_set) {
203  buffer_ <<= 1;
204  pos_++;
205  no_ones++;
206  if (pos_ == buffer_bits_) {
207  pos_ = 0;
208  buffer_ = block_reader_.template GetRaw<size_t>();
209  }
210  }
211 
212  // skip 0
213  buffer_ <<= 1;
214  pos_++;
215  return no_ones;
216  }
217 
218 protected:
219  //! Input BlockReader
220  BlockReader& block_reader_;
221 
222  //! current buffer of 32/64 bits
223  size_t buffer_ = 0;
224 
225  //! currently used number of bits
226  size_t pos_ = buffer_bits_;
227 };
228 
229 } // namespace core
230 } // namespace thrill
231 
232 #endif // !THRILL_CORE_BIT_STREAM_HEADER
233 
234 /******************************************************************************/
size_t buffer_
current buffer of 32/64 bits
Definition: bit_stream.hpp:107
#define die_unless(X)
Definition: die.hpp:27
BitStreamWriter(BlockWriter &block_writer)
Definition: bit_stream.hpp:37
BlockWriter & block_writer_
Output BlockWriter.
Definition: bit_stream.hpp:104
size_t GetBits(unsigned bits)
Get bits at the cursor.
Definition: bit_stream.hpp:147
unsigned GetNumberOfOnesUntilNextZero()
Returns the number of continuous 1 bits at the cursor, followed by a zero.
Definition: bit_stream.hpp:194
int value
Definition: gen_data.py:41
BitStreamReader(BlockReader &block_reader)
Definition: bit_stream.hpp:127
BitStreamWriter & operator=(const BitStreamWriter &)=delete
non-copyable: delete assignment operator
BlockReader & block_reader_
Input BlockReader.
Definition: bit_stream.hpp:220
void PutBits(const size_t &value, unsigned bits)
Append k bits to the data array.
Definition: bit_stream.hpp:61
void FlushBits()
Flush out buffered bits.
Definition: bit_stream.hpp:94
size_t pos_
currently filled number of bits
Definition: bit_stream.hpp:110