ringbuffer.h revision b820c39bd9cf61dc6efd91ad74972540870072b0
1771eb107985566d2e458e3f06f2c7bd1b21c2dcaEugene Klyuchnikov/* Copyright 2013 Google Inc. All Rights Reserved. 2771eb107985566d2e458e3f06f2c7bd1b21c2dcaEugene Klyuchnikov 324ffa78414663b545b66be392caff7eb5574a62cEugene Klyuchnikov Distributed under MIT license. 4771eb107985566d2e458e3f06f2c7bd1b21c2dcaEugene Klyuchnikov See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 5771eb107985566d2e458e3f06f2c7bd1b21c2dcaEugene Klyuchnikov*/ 6771eb107985566d2e458e3f06f2c7bd1b21c2dcaEugene Klyuchnikov 7c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka// Sliding window over the input data. 8c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 9c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka#ifndef BROTLI_ENC_RINGBUFFER_H_ 10c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka#define BROTLI_ENC_RINGBUFFER_H_ 11c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 1225e3796f83edcaeec3c2f1a34dec30f0e7efe0aeEugene Kliuchnikov#include <cstdlib> /* free, realloc */ 13485ad82e94b3f1335fd41fe7f64b9b25f35fbf94Zoltan Szabadka 14d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka#include "./port.h" 154a7024dcde1aaf30d824ade299e70711a30f4399Zoltan Szabadka#include "./types.h" 16d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 17d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadkanamespace brotli { 18d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 19c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka// A RingBuffer(window_bits, tail_bits) contains `1 << window_bits' bytes of 208844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka// data in a circular manner: writing a byte writes it to: 218844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka// `position() % (1 << window_bits)'. 228844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka// For convenience, the RingBuffer array contains another copy of the 238844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka// first `1 << tail_bits' bytes: 248844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka// buffer_[i] == buffer_[i + (1 << window_bits)], if i < (1 << tail_bits), 258844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka// and another copy of the last two bytes: 268844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka// buffer_[-1] == buffer_[(1 << window_bits) - 1] and 278844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka// buffer_[-2] == buffer_[(1 << window_bits) - 2]. 28c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadkaclass RingBuffer { 29c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka public: 30c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka RingBuffer(int window_bits, int tail_bits) 318844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka : size_(1u << window_bits), 328844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka mask_((1u << window_bits) - 1), 338844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka tail_size_(1u << tail_bits), 34b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka total_size_(size_ + tail_size_), 35b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka cur_size_(0), 36b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka pos_(0), 37b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka data_(0), 38b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka buffer_(0) {} 39b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka 40b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka ~RingBuffer(void) { 41b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka free(data_); 42b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka } 43b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka 44b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // Allocates or re-allocates data_ to the given length + plus some slack 45b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // region before and after. Fills the slack regions with zeros. 46b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka inline void InitBuffer(const uint32_t buflen) { 478844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka static const size_t kSlackForEightByteHashingEverywhere = 7; 48b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka cur_size_ = buflen; 49b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka data_ = static_cast<uint8_t*>(realloc( 50b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka data_, 2 + buflen + kSlackForEightByteHashingEverywhere)); 518844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka buffer_ = data_ + 2; 52b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka buffer_[-2] = buffer_[-1] = 0; 538844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka for (size_t i = 0; i < kSlackForEightByteHashingEverywhere; ++i) { 54b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka buffer_[cur_size_ + i] = 0; 55c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } 56c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } 57c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 58c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // Push bytes into the ring buffer. 59c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka void Write(const uint8_t *bytes, size_t n) { 60b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka if (pos_ == 0 && n < tail_size_) { 61b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // Special case for the first write: to process the first block, we don't 62b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // need to allocate the whole ringbuffer and we don't need the tail 63b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // either. However, we do this memory usage optimization only if the 64b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // first write is less than the tail size, which is also the input block 65b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // size, otherwise it is likely that other blocks will follow and we 66b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // will need to reallocate to the full size anyway. 67b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka pos_ = static_cast<uint32_t>(n); 68b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka InitBuffer(pos_); 69b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka memcpy(buffer_, bytes, n); 70b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka return; 71b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka } 72b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka if (cur_size_ < total_size_) { 73b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // Lazily allocate the full buffer. 74b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka InitBuffer(total_size_); 75b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // Initialize the last two bytes to zero, so that we don't have to worry 76b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka // later when we copy the last two bytes to the first two positions. 77b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka buffer_[size_ - 2] = 0; 78b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka buffer_[size_ - 1] = 0; 79b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka } 80d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka const size_t masked_pos = pos_ & mask_; 81c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // The length of the writes is limited so that we do not need to worry 82c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // about a write 83c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka WriteTail(bytes, n); 84152e33c3a0a58a306d2ec208e0c71c92b11f99f6Eugene Klyuchnikov if (PREDICT_TRUE(masked_pos + n <= size_)) { 85c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // A single write fits. 86c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka memcpy(&buffer_[masked_pos], bytes, n); 87c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } else { 88c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // Split into two writes. 89c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // Copy into the end of the buffer, including the tail buffer. 90c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka memcpy(&buffer_[masked_pos], bytes, 91b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka std::min(n, total_size_ - masked_pos)); 9221ac39f7c8ca61c855be0bc38900abe7b5a0f67fMarcin Karpinski // Copy into the beginning of the buffer 93152e33c3a0a58a306d2ec208e0c71c92b11f99f6Eugene Klyuchnikov memcpy(&buffer_[0], bytes + (size_ - masked_pos), 94152e33c3a0a58a306d2ec208e0c71c92b11f99f6Eugene Klyuchnikov n - (size_ - masked_pos)); 95c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } 968844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka buffer_[-2] = buffer_[size_ - 2]; 978844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka buffer_[-1] = buffer_[size_ - 1]; 988844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka pos_ += static_cast<uint32_t>(n); 998844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka if (pos_ > (1u << 30)) { /* Wrap, but preserve not-a-first-lap feature. */ 1008844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka pos_ = (pos_ & ((1u << 30) - 1)) | (1u << 30); 1018844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka } 102c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } 103c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 10425e3796f83edcaeec3c2f1a34dec30f0e7efe0aeEugene Kliuchnikov void Reset(void) { 105d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka pos_ = 0; 106d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka } 107d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 108c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // Logical cursor position in the ring buffer. 10925e3796f83edcaeec3c2f1a34dec30f0e7efe0aeEugene Kliuchnikov uint32_t position(void) const { return pos_; } 110c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 111d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka // Bit mask for getting the physical position for a logical position. 11225e3796f83edcaeec3c2f1a34dec30f0e7efe0aeEugene Kliuchnikov uint32_t mask(void) const { return mask_; } 113d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 11425e3796f83edcaeec3c2f1a34dec30f0e7efe0aeEugene Kliuchnikov uint8_t *start(void) { return &buffer_[0]; } 11525e3796f83edcaeec3c2f1a34dec30f0e7efe0aeEugene Kliuchnikov const uint8_t *start(void) const { return &buffer_[0]; } 116c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 117c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka private: 118c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka void WriteTail(const uint8_t *bytes, size_t n) { 119d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka const size_t masked_pos = pos_ & mask_; 120d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka if (PREDICT_FALSE(masked_pos < tail_size_)) { 121c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // Just fill the tail buffer with the beginning data. 122152e33c3a0a58a306d2ec208e0c71c92b11f99f6Eugene Klyuchnikov const size_t p = size_ + masked_pos; 123d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka memcpy(&buffer_[p], bytes, std::min(n, tail_size_ - masked_pos)); 124c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } 125c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } 126c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 127d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka // Size of the ringbuffer is (1 << window_bits) + tail_size_. 1288844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka const uint32_t size_; 1298844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka const uint32_t mask_; 1308844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka const uint32_t tail_size_; 131b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka const uint32_t total_size_; 132c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 133b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka uint32_t cur_size_; 134c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka // Position to write in the ring buffer. 1358844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka uint32_t pos_; 1368844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka // The actual ring buffer containing the copy of the last two bytes, the data, 1378844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka // and the copy of the beginning as a tail. 1388844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka uint8_t *data_; 1398844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka // The start of the ringbuffer. 140c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka uint8_t *buffer_; 141c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka}; 142c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 143d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka} // namespace brotli 144d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 145c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka#endif // BROTLI_ENC_RINGBUFFER_H_ 146