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).
25class 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_
90