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 7352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov/* Sliding window over the input data. */ 8c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 9c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka#ifndef BROTLI_ENC_RINGBUFFER_H_ 10c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka#define BROTLI_ENC_RINGBUFFER_H_ 11c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 12b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov#include <string.h> /* memcpy */ 13485ad82e94b3f1335fd41fe7f64b9b25f35fbf94Zoltan Szabadka 1481480011581d1bb40e2ed26566a95d060f2767b3Eugene Kliuchnikov#include <brotli/types.h> 15b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov#include "./memory.h" 16d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka#include "./port.h" 172048189048f130b0e8fb60307277379743dc5a2dEugene Kliuchnikov#include "./quality.h" 18d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 19b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov#if defined(__cplusplus) || defined(c_plusplus) 20b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikovextern "C" { 21b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov#endif 22d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 23352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov/* A RingBuffer(window_bits, tail_bits) contains `1 << window_bits' bytes of 24352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov data in a circular manner: writing a byte writes it to: 25352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov `position() % (1 << window_bits)'. 26352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov For convenience, the RingBuffer array contains another copy of the 27352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov first `1 << tail_bits' bytes: 28352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov buffer_[i] == buffer_[i + (1 << window_bits)], if i < (1 << tail_bits), 29352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov and another copy of the last two bytes: 30352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov buffer_[-1] == buffer_[(1 << window_bits) - 1] and 31352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov buffer_[-2] == buffer_[(1 << window_bits) - 2]. */ 32b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikovtypedef struct RingBuffer { 33e9b278ac6e097beb763e8a46eeafcaa3f6f63f18Eugene Kliuchnikov /* Size of the ring-buffer is (1 << window_bits) + tail_size_. */ 34b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov const uint32_t size_; 35b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov const uint32_t mask_; 36b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov const uint32_t tail_size_; 37b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov const uint32_t total_size_; 38b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov 39b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov uint32_t cur_size_; 40b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov /* Position to write in the ring buffer. */ 41b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov uint32_t pos_; 42b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov /* The actual ring buffer containing the copy of the last two bytes, the data, 43b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov and the copy of the beginning as a tail. */ 44b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov uint8_t *data_; 45e9b278ac6e097beb763e8a46eeafcaa3f6f63f18Eugene Kliuchnikov /* The start of the ring-buffer. */ 46b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov uint8_t *buffer_; 47b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov} RingBuffer; 48b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov 49b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikovstatic BROTLI_INLINE void RingBufferInit(RingBuffer* rb) { 50b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->cur_size_ = 0; 51b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->pos_ = 0; 52b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->data_ = 0; 53b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->buffer_ = 0; 54b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov} 55b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov 56b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikovstatic BROTLI_INLINE void RingBufferSetup( 572048189048f130b0e8fb60307277379743dc5a2dEugene Kliuchnikov const BrotliEncoderParams* params, RingBuffer* rb) { 582048189048f130b0e8fb60307277379743dc5a2dEugene Kliuchnikov int window_bits = ComputeRbBits(params); 592048189048f130b0e8fb60307277379743dc5a2dEugene Kliuchnikov int tail_bits = params->lgblock; 60b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov *(uint32_t*)&rb->size_ = 1u << window_bits; 61b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov *(uint32_t*)&rb->mask_ = (1u << window_bits) - 1; 62b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov *(uint32_t*)&rb->tail_size_ = 1u << tail_bits; 63b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov *(uint32_t*)&rb->total_size_ = rb->size_ + rb->tail_size_; 64b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov} 65b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov 66b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikovstatic BROTLI_INLINE void RingBufferFree(MemoryManager* m, RingBuffer* rb) { 67b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov BROTLI_FREE(m, rb->data_); 68b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov} 69b820c39bd9cf61dc6efd91ad74972540870072b0Zoltan Szabadka 70352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov/* Allocates or re-allocates data_ to the given length + plus some slack 71352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov region before and after. Fills the slack regions with zeros. */ 72b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikovstatic BROTLI_INLINE void RingBufferInitBuffer( 73b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov MemoryManager* m, const uint32_t buflen, RingBuffer* rb) { 74b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov static const size_t kSlackForEightByteHashingEverywhere = 7; 75b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov uint8_t* new_data = BROTLI_ALLOC( 76b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov m, uint8_t, 2 + buflen + kSlackForEightByteHashingEverywhere); 77b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov size_t i; 78b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov if (BROTLI_IS_OOM(m)) return; 79b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov if (rb->data_) { 80b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov memcpy(new_data, rb->data_, 81b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov 2 + rb->cur_size_ + kSlackForEightByteHashingEverywhere); 82b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov BROTLI_FREE(m, rb->data_); 83b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov } 84b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->data_ = new_data; 85b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->cur_size_ = buflen; 86b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->buffer_ = rb->data_ + 2; 87b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->buffer_[-2] = rb->buffer_[-1] = 0; 88b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov for (i = 0; i < kSlackForEightByteHashingEverywhere; ++i) { 89b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->buffer_[rb->cur_size_ + i] = 0; 90c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } 91b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov} 92b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov 93b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikovstatic BROTLI_INLINE void RingBufferWriteTail( 94b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov const uint8_t *bytes, size_t n, RingBuffer* rb) { 95b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov const size_t masked_pos = rb->pos_ & rb->mask_; 9669982c25f155e6b5c72782f2c5590ead1b06aa61Eugene Kliuchnikov if (BROTLI_PREDICT_FALSE(masked_pos < rb->tail_size_)) { 97b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov /* Just fill the tail buffer with the beginning data. */ 98b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov const size_t p = rb->size_ + masked_pos; 99b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov memcpy(&rb->buffer_[p], bytes, 100b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov BROTLI_MIN(size_t, n, rb->tail_size_ - masked_pos)); 101b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov } 102b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov} 103c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka 104352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov/* Push bytes into the ring buffer. */ 105b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikovstatic BROTLI_INLINE void RingBufferWrite( 106b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov MemoryManager* m, const uint8_t *bytes, size_t n, RingBuffer* rb) { 107b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov if (rb->pos_ == 0 && n < rb->tail_size_) { 108352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov /* Special case for the first write: to process the first block, we don't 109e9b278ac6e097beb763e8a46eeafcaa3f6f63f18Eugene Kliuchnikov need to allocate the whole ring-buffer and we don't need the tail 110352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov either. However, we do this memory usage optimization only if the 111352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov first write is less than the tail size, which is also the input block 112352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov size, otherwise it is likely that other blocks will follow and we 113352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov will need to reallocate to the full size anyway. */ 114b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->pos_ = (uint32_t)n; 115b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov RingBufferInitBuffer(m, rb->pos_, rb); 116b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov if (BROTLI_IS_OOM(m)) return; 117b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov memcpy(rb->buffer_, bytes, n); 118b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov return; 119b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov } 120b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov if (rb->cur_size_ < rb->total_size_) { 121352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov /* Lazily allocate the full buffer. */ 122b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov RingBufferInitBuffer(m, rb->total_size_, rb); 123b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov if (BROTLI_IS_OOM(m)) return; 124352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov /* Initialize the last two bytes to zero, so that we don't have to worry 125352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov later when we copy the last two bytes to the first two positions. */ 126b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->buffer_[rb->size_ - 2] = 0; 127b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->buffer_[rb->size_ - 1] = 0; 128b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov } 129b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov { 130b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov const size_t masked_pos = rb->pos_ & rb->mask_; 131352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov /* The length of the writes is limited so that we do not need to worry 132352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov about a write */ 133b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov RingBufferWriteTail(bytes, n, rb); 13469982c25f155e6b5c72782f2c5590ead1b06aa61Eugene Kliuchnikov if (BROTLI_PREDICT_TRUE(masked_pos + n <= rb->size_)) { 135352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov /* A single write fits. */ 136b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov memcpy(&rb->buffer_[masked_pos], bytes, n); 137c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } else { 138352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov /* Split into two writes. 139352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov Copy into the end of the buffer, including the tail buffer. */ 140b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov memcpy(&rb->buffer_[masked_pos], bytes, 141b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov BROTLI_MIN(size_t, n, rb->total_size_ - masked_pos)); 142352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov /* Copy into the beginning of the buffer */ 143b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov memcpy(&rb->buffer_[0], bytes + (rb->size_ - masked_pos), 144b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov n - (rb->size_ - masked_pos)); 1458844b7f0d7db79aaf17ba91f0fec3ce3d90c16d4Zoltan Szabadka } 146c6b9c7c5c82684a32931a14dc9785f6cdce8171fZoltan Szabadka } 147b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->buffer_[-2] = rb->buffer_[rb->size_ - 2]; 148b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->buffer_[-1] = rb->buffer_[rb->size_ - 1]; 149b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->pos_ += (uint32_t)n; 150b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov if (rb->pos_ > (1u << 30)) { 151b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov /* Wrap, but preserve not-a-first-lap feature. */ 152b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov rb->pos_ = (rb->pos_ & ((1u << 30) - 1)) | (1u << 30); 153d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka } 154b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov} 155d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 156b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov#if defined(__cplusplus) || defined(c_plusplus) 157b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov} /* extern "C" */ 158b972c67780f03256a3fbf81dc3350a4bf00aa4adEugene Kliuchnikov#endif 159d6d69ec4ac979255360512980ed6300582ed3d2cZoltan Szabadka 160352b0b2836504f59c4915b20eee11a770b415a47Eugene Kliuchnikov#endif /* BROTLI_ENC_RINGBUFFER_H_ */ 161