Zoltan Szabadka | 1571db3 | 2013-11-15 19:02:17 +0100 | [diff] [blame] | 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_ |