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