| // Copyright 2013 Google Inc. All Rights Reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| // Sliding window over the input data. |
| |
| #ifndef BROTLI_ENC_RINGBUFFER_H_ |
| #define BROTLI_ENC_RINGBUFFER_H_ |
| |
| #include <stddef.h> |
| #include <stdint.h> |
| |
| #include "./port.h" |
| |
| namespace brotli { |
| |
| // A RingBuffer(window_bits, tail_bits) contains `1 << window_bits' bytes of |
| // data in a circular manner: writing a byte writes it to |
| // `position() % (1 << window_bits)'. For convenience, the RingBuffer array |
| // contains another copy of the first `1 << tail_bits' bytes: |
| // buffer_[i] == buffer_[i + (1 << window_bits)] if i < (1 << tail_bits). |
| class RingBuffer { |
| public: |
| RingBuffer(int window_bits, int tail_bits) |
| : window_bits_(window_bits), |
| mask_((1 << window_bits) - 1), |
| tail_size_(1 << tail_bits), |
| pos_(0) { |
| static const int kSlackForEightByteHashingEverywhere = 7; |
| const int buflen = (1 << window_bits_) + tail_size_; |
| buffer_ = new uint8_t[buflen + kSlackForEightByteHashingEverywhere]; |
| for (int i = 0; i < kSlackForEightByteHashingEverywhere; ++i) { |
| buffer_[buflen + i] = 0; |
| } |
| } |
| ~RingBuffer() { |
| delete [] buffer_; |
| } |
| |
| // Push bytes into the ring buffer. |
| void Write(const uint8_t *bytes, size_t n) { |
| const size_t masked_pos = pos_ & mask_; |
| // The length of the writes is limited so that we do not need to worry |
| // about a write |
| WriteTail(bytes, n); |
| if (PREDICT_TRUE(masked_pos + n <= (1 << window_bits_))) { |
| // A single write fits. |
| memcpy(&buffer_[masked_pos], bytes, n); |
| } else { |
| // Split into two writes. |
| // Copy into the end of the buffer, including the tail buffer. |
| memcpy(&buffer_[masked_pos], bytes, |
| std::min(n, ((1 << window_bits_) + tail_size_) - masked_pos)); |
| // Copy into the beginning of the buffer |
| memcpy(&buffer_[0], bytes + ((1 << window_bits_) - masked_pos), |
| n - ((1 << window_bits_) - masked_pos)); |
| } |
| pos_ += n; |
| } |
| |
| void Reset() { |
| pos_ = 0; |
| } |
| |
| // Logical cursor position in the ring buffer. |
| size_t position() const { return pos_; } |
| |
| // Bit mask for getting the physical position for a logical position. |
| size_t mask() const { return mask_; } |
| |
| uint8_t *start() { return &buffer_[0]; } |
| const uint8_t *start() const { return &buffer_[0]; } |
| |
| private: |
| void WriteTail(const uint8_t *bytes, size_t n) { |
| const size_t masked_pos = pos_ & mask_; |
| if (PREDICT_FALSE(masked_pos < tail_size_)) { |
| // Just fill the tail buffer with the beginning data. |
| const size_t p = (1 << window_bits_) + masked_pos; |
| memcpy(&buffer_[p], bytes, std::min(n, tail_size_ - masked_pos)); |
| } |
| } |
| |
| // Size of the ringbuffer is (1 << window_bits) + tail_size_. |
| const int window_bits_; |
| const size_t mask_; |
| const size_t tail_size_; |
| |
| // Position to write in the ring buffer. |
| size_t pos_; |
| // The actual ring buffer containing the data and the copy of the beginning |
| // as a tail. |
| uint8_t *buffer_; |
| }; |
| |
| } // namespace brotli |
| |
| #endif // BROTLI_ENC_RINGBUFFER_H_ |