• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* Copyright 2013 Google Inc. All Rights Reserved.
2 
3    Distributed under MIT license.
4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5 */
6 
7 /* Sliding window over the input data. */
8 
9 #ifndef BROTLI_ENC_RINGBUFFER_H_
10 #define BROTLI_ENC_RINGBUFFER_H_
11 
12 #include <string.h>  /* memcpy */
13 
14 #include "../common/platform.h"
15 #include <brotli/types.h>
16 #include "./memory.h"
17 #include "./quality.h"
18 
19 #if defined(__cplusplus) || defined(c_plusplus)
20 extern "C" {
21 #endif
22 
23 /* A RingBuffer(window_bits, tail_bits) contains `1 << window_bits' bytes of
24    data in a circular manner: writing a byte writes it to:
25      `position() % (1 << window_bits)'.
26    For convenience, the RingBuffer array contains another copy of the
27    first `1 << tail_bits' bytes:
28      buffer_[i] == buffer_[i + (1 << window_bits)], if i < (1 << tail_bits),
29    and another copy of the last two bytes:
30      buffer_[-1] == buffer_[(1 << window_bits) - 1] and
31      buffer_[-2] == buffer_[(1 << window_bits) - 2]. */
32 typedef struct RingBuffer {
33   /* Size of the ring-buffer is (1 << window_bits) + tail_size_. */
34   const uint32_t size_;
35   const uint32_t mask_;
36   const uint32_t tail_size_;
37   const uint32_t total_size_;
38 
39   uint32_t cur_size_;
40   /* Position to write in the ring buffer. */
41   uint32_t pos_;
42   /* The actual ring buffer containing the copy of the last two bytes, the data,
43      and the copy of the beginning as a tail. */
44   uint8_t* data_;
45   /* The start of the ring-buffer. */
46   uint8_t* buffer_;
47 } RingBuffer;
48 
RingBufferInit(RingBuffer * rb)49 static BROTLI_INLINE void RingBufferInit(RingBuffer* rb) {
50   rb->cur_size_ = 0;
51   rb->pos_ = 0;
52   rb->data_ = 0;
53   rb->buffer_ = 0;
54 }
55 
RingBufferSetup(const BrotliEncoderParams * params,RingBuffer * rb)56 static BROTLI_INLINE void RingBufferSetup(
57     const BrotliEncoderParams* params, RingBuffer* rb) {
58   int window_bits = ComputeRbBits(params);
59   int tail_bits = params->lgblock;
60   *(uint32_t*)&rb->size_ = 1u << window_bits;
61   *(uint32_t*)&rb->mask_ = (1u << window_bits) - 1;
62   *(uint32_t*)&rb->tail_size_ = 1u << tail_bits;
63   *(uint32_t*)&rb->total_size_ = rb->size_ + rb->tail_size_;
64 }
65 
RingBufferFree(MemoryManager * m,RingBuffer * rb)66 static BROTLI_INLINE void RingBufferFree(MemoryManager* m, RingBuffer* rb) {
67   BROTLI_FREE(m, rb->data_);
68 }
69 
70 /* Allocates or re-allocates data_ to the given length + plus some slack
71    region before and after. Fills the slack regions with zeros. */
RingBufferInitBuffer(MemoryManager * m,const uint32_t buflen,RingBuffer * rb)72 static BROTLI_INLINE void RingBufferInitBuffer(
73     MemoryManager* m, const uint32_t buflen, RingBuffer* rb) {
74   static const size_t kSlackForEightByteHashingEverywhere = 7;
75   uint8_t* new_data = BROTLI_ALLOC(
76       m, uint8_t, 2 + buflen + kSlackForEightByteHashingEverywhere);
77   size_t i;
78   if (BROTLI_IS_OOM(m)) return;
79   if (rb->data_) {
80     memcpy(new_data, rb->data_,
81         2 + rb->cur_size_ + kSlackForEightByteHashingEverywhere);
82     BROTLI_FREE(m, rb->data_);
83   }
84   rb->data_ = new_data;
85   rb->cur_size_ = buflen;
86   rb->buffer_ = rb->data_ + 2;
87   rb->buffer_[-2] = rb->buffer_[-1] = 0;
88   for (i = 0; i < kSlackForEightByteHashingEverywhere; ++i) {
89     rb->buffer_[rb->cur_size_ + i] = 0;
90   }
91 }
92 
RingBufferWriteTail(const uint8_t * bytes,size_t n,RingBuffer * rb)93 static BROTLI_INLINE void RingBufferWriteTail(
94     const uint8_t* bytes, size_t n, RingBuffer* rb) {
95   const size_t masked_pos = rb->pos_ & rb->mask_;
96   if (BROTLI_PREDICT_FALSE(masked_pos < rb->tail_size_)) {
97     /* Just fill the tail buffer with the beginning data. */
98     const size_t p = rb->size_ + masked_pos;
99     memcpy(&rb->buffer_[p], bytes,
100         BROTLI_MIN(size_t, n, rb->tail_size_ - masked_pos));
101   }
102 }
103 
104 /* Push bytes into the ring buffer. */
RingBufferWrite(MemoryManager * m,const uint8_t * bytes,size_t n,RingBuffer * rb)105 static BROTLI_INLINE void RingBufferWrite(
106     MemoryManager* m, const uint8_t* bytes, size_t n, RingBuffer* rb) {
107   if (rb->pos_ == 0 && n < rb->tail_size_) {
108     /* Special case for the first write: to process the first block, we don't
109        need to allocate the whole ring-buffer and we don't need the tail
110        either. However, we do this memory usage optimization only if the
111        first write is less than the tail size, which is also the input block
112        size, otherwise it is likely that other blocks will follow and we
113        will need to reallocate to the full size anyway. */
114     rb->pos_ = (uint32_t)n;
115     RingBufferInitBuffer(m, rb->pos_, rb);
116     if (BROTLI_IS_OOM(m)) return;
117     memcpy(rb->buffer_, bytes, n);
118     return;
119   }
120   if (rb->cur_size_ < rb->total_size_) {
121     /* Lazily allocate the full buffer. */
122     RingBufferInitBuffer(m, rb->total_size_, rb);
123     if (BROTLI_IS_OOM(m)) return;
124     /* Initialize the last two bytes to zero, so that we don't have to worry
125        later when we copy the last two bytes to the first two positions. */
126     rb->buffer_[rb->size_ - 2] = 0;
127     rb->buffer_[rb->size_ - 1] = 0;
128   }
129   {
130     const size_t masked_pos = rb->pos_ & rb->mask_;
131     /* The length of the writes is limited so that we do not need to worry
132        about a write */
133     RingBufferWriteTail(bytes, n, rb);
134     if (BROTLI_PREDICT_TRUE(masked_pos + n <= rb->size_)) {
135       /* A single write fits. */
136       memcpy(&rb->buffer_[masked_pos], bytes, n);
137     } else {
138       /* Split into two writes.
139          Copy into the end of the buffer, including the tail buffer. */
140       memcpy(&rb->buffer_[masked_pos], bytes,
141              BROTLI_MIN(size_t, n, rb->total_size_ - masked_pos));
142       /* Copy into the beginning of the buffer */
143       memcpy(&rb->buffer_[0], bytes + (rb->size_ - masked_pos),
144              n - (rb->size_ - masked_pos));
145     }
146   }
147   {
148     BROTLI_BOOL not_first_lap = (rb->pos_ & (1u << 31)) != 0;
149     uint32_t rb_pos_mask = (1u << 31) - 1;
150     rb->buffer_[-2] = rb->buffer_[rb->size_ - 2];
151     rb->buffer_[-1] = rb->buffer_[rb->size_ - 1];
152     rb->pos_ = (rb->pos_ & rb_pos_mask) + (uint32_t)(n & rb_pos_mask);
153     if (not_first_lap) {
154       /* Wrap, but preserve not-a-first-lap feature. */
155       rb->pos_ |= 1u << 31;
156     }
157   }
158 }
159 
160 #if defined(__cplusplus) || defined(c_plusplus)
161 }  /* extern "C" */
162 #endif
163 
164 #endif  /* BROTLI_ENC_RINGBUFFER_H_ */
165