// 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 #include #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 kSlackForFourByteHashingEverywhere = 3; const int buflen = (1 << window_bits_) + tail_size_; buffer_ = new uint8_t[buflen + kSlackForFourByteHashingEverywhere]; for (int i = 0; i < kSlackForFourByteHashingEverywhere; ++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 begining 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_