1 // Copyright 2013 Google Inc. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // Sliding window over the input data. 16 17 #ifndef BROTLI_ENC_RINGBUFFER_H_ 18 #define BROTLI_ENC_RINGBUFFER_H_ 19 20 // A RingBuffer(window_bits, tail_bits) contains `1 << window_bits' bytes of 21 // data in a circular manner: writing a byte writes it to 22 // `position() % (1 << window_bits)'. For convenience, the RingBuffer array 23 // contains another copy of the first `1 << tail_bits' bytes: 24 // buffer_[i] == buffer_[i + (1 << window_bits)] if i < (1 << tail_bits). 25 class RingBuffer { 26 public: 27 RingBuffer(int window_bits, int tail_bits) 28 : window_bits_(window_bits), tail_bits_(tail_bits), pos_(0) { 29 static const int kSlackForThreeByteHashingEverywhere = 2; 30 const int buflen = (1 << window_bits_) + (1 << tail_bits_); 31 buffer_ = new uint8_t[buflen + kSlackForThreeByteHashingEverywhere]; 32 for (int i = 0; i < kSlackForThreeByteHashingEverywhere; ++i) { 33 buffer_[buflen + i] = 0; 34 } 35 } 36 ~RingBuffer() { 37 delete [] buffer_; 38 } 39 40 // Push bytes into the ring buffer. 41 void Write(const uint8_t *bytes, size_t n) { 42 const size_t masked_pos = pos_ & ((1 << window_bits_) - 1); 43 // The length of the writes is limited so that we do not need to worry 44 // about a write 45 WriteTail(bytes, n); 46 if (masked_pos + n <= (1 << window_bits_)) { 47 // A single write fits. 48 memcpy(&buffer_[masked_pos], bytes, n); 49 } else { 50 // Split into two writes. 51 // Copy into the end of the buffer, including the tail buffer. 52 memcpy(&buffer_[masked_pos], bytes, 53 std::min(n, 54 ((1 << window_bits_) + (1 << tail_bits_)) - masked_pos)); 55 // Copy into the begining of the buffer 56 memcpy(&buffer_[0], bytes + ((1 << window_bits_) - masked_pos), 57 n - ((1 << window_bits_) - masked_pos)); 58 } 59 pos_ += n; 60 } 61 62 // Logical cursor position in the ring buffer. 63 size_t position() const { return pos_; } 64 65 uint8_t *start() { return &buffer_[0]; } 66 const uint8_t *start() const { return &buffer_[0]; } 67 68 private: 69 void WriteTail(const uint8_t *bytes, size_t n) { 70 const size_t masked_pos = pos_ & ((1 << window_bits_) - 1); 71 if (masked_pos < (1 << tail_bits_)) { 72 // Just fill the tail buffer with the beginning data. 73 const size_t p = (1 << window_bits_) + masked_pos; 74 memcpy(&buffer_[p], bytes, std::min(n, (1 << tail_bits_) - masked_pos)); 75 } 76 } 77 78 // Size of the ringbuffer is (1 << window_bits) + (1 << tail_bits). 79 const int window_bits_; 80 const int tail_bits_; 81 82 // Position to write in the ring buffer. 83 size_t pos_; 84 // The actual ring buffer containing the data and the copy of the beginning 85 // as a tail. 86 uint8_t *buffer_; 87 }; 88 89 #endif // BROTLI_ENC_RINGBUFFER_H_ 90
