1 // Copyright (c) the JPEG XL Project Authors. All rights reserved.
2 //
3 // Use of this source code is governed by a BSD-style
4 // license that can be found in the LICENSE file.
5
6 #ifndef LIB_JXL_BASE_PADDED_BYTES_H_
7 #define LIB_JXL_BASE_PADDED_BYTES_H_
8
9 // std::vector replacement with padding to reduce bounds checks in WriteBits
10
11 #include <stddef.h>
12 #include <stdint.h>
13 #include <string.h> // memcpy
14
15 #include <algorithm> // max
16 #include <initializer_list>
17 #include <utility> // swap
18
19 #include "lib/jxl/base/cache_aligned.h"
20 #include "lib/jxl/base/compiler_specific.h"
21 #include "lib/jxl/base/status.h"
22
23 namespace jxl {
24
25 // Provides a subset of the std::vector interface with some differences:
26 // - allows BitWriter to write 64 bits at a time without bounds checking;
27 // - ONLY zero-initializes the first byte (required by BitWriter);
28 // - ensures cache-line alignment.
29 class PaddedBytes {
30 public:
31 // Required for output params.
PaddedBytes()32 PaddedBytes() : size_(0), capacity_(0) {}
33
PaddedBytes(size_t size)34 explicit PaddedBytes(size_t size) : size_(size), capacity_(0) {
35 if (size != 0) IncreaseCapacityTo(size);
36 }
37
PaddedBytes(size_t size,uint8_t value)38 PaddedBytes(size_t size, uint8_t value) : size_(size), capacity_(0) {
39 if (size != 0) {
40 IncreaseCapacityTo(size);
41 }
42 if (size_ != 0) {
43 memset(data(), value, size);
44 }
45 }
46
PaddedBytes(const PaddedBytes & other)47 PaddedBytes(const PaddedBytes& other) : size_(other.size_), capacity_(0) {
48 if (size_ != 0) IncreaseCapacityTo(size_);
49 if (data() != nullptr) memcpy(data(), other.data(), size_);
50 }
51 PaddedBytes& operator=(const PaddedBytes& other) {
52 // Self-assignment is safe.
53 resize(other.size());
54 if (data() != nullptr) memmove(data(), other.data(), size_);
55 return *this;
56 }
57
58 // default is not OK - need to set other.size_ to 0!
PaddedBytes(PaddedBytes && other)59 PaddedBytes(PaddedBytes&& other) noexcept
60 : size_(other.size_),
61 capacity_(other.capacity_),
62 data_(std::move(other.data_)) {
63 other.size_ = other.capacity_ = 0;
64 }
65 PaddedBytes& operator=(PaddedBytes&& other) noexcept {
66 size_ = other.size_;
67 capacity_ = other.capacity_;
68 data_ = std::move(other.data_);
69
70 if (&other != this) {
71 other.size_ = other.capacity_ = 0;
72 }
73 return *this;
74 }
75
swap(PaddedBytes & other)76 void swap(PaddedBytes& other) {
77 std::swap(size_, other.size_);
78 std::swap(capacity_, other.capacity_);
79 std::swap(data_, other.data_);
80 }
81
reserve(size_t capacity)82 void reserve(size_t capacity) {
83 if (capacity > capacity_) IncreaseCapacityTo(capacity);
84 }
85
86 // NOTE: unlike vector, this does not initialize the new data!
87 // However, we guarantee that write_bits can safely append after
88 // the resize, as we zero-initialize the first new byte of data.
89 // If size < capacity(), does not invalidate the memory.
resize(size_t size)90 void resize(size_t size) {
91 if (size > capacity_) IncreaseCapacityTo(size);
92 size_ = (data() == nullptr) ? 0 : size;
93 }
94
95 // resize(size) plus explicit initialization of the new data with `value`.
resize(size_t size,uint8_t value)96 void resize(size_t size, uint8_t value) {
97 size_t old_size = size_;
98 resize(size);
99 if (size_ > old_size) {
100 memset(data() + old_size, value, size_ - old_size);
101 }
102 }
103
104 // Amortized constant complexity due to exponential growth.
push_back(uint8_t x)105 void push_back(uint8_t x) {
106 if (size_ == capacity_) {
107 IncreaseCapacityTo(capacity_ + 1);
108 if (data() == nullptr) return;
109 }
110
111 data_[size_++] = x;
112 }
113
size()114 size_t size() const { return size_; }
capacity()115 size_t capacity() const { return capacity_; }
116
data()117 uint8_t* data() { return data_.get(); }
data()118 const uint8_t* data() const { return data_.get(); }
119
120 // std::vector operations implemented in terms of the public interface above.
121
clear()122 void clear() { resize(0); }
empty()123 bool empty() const { return size() == 0; }
124
assign(std::initializer_list<uint8_t> il)125 void assign(std::initializer_list<uint8_t> il) {
126 resize(il.size());
127 memcpy(data(), il.begin(), il.size());
128 }
129
130 // Replaces data() with [new_begin, new_end); potentially reallocates.
131 void assign(const uint8_t* new_begin, const uint8_t* new_end);
132
begin()133 uint8_t* begin() { return data(); }
begin()134 const uint8_t* begin() const { return data(); }
end()135 uint8_t* end() { return begin() + size(); }
end()136 const uint8_t* end() const { return begin() + size(); }
137
138 uint8_t& operator[](const size_t i) {
139 BoundsCheck(i);
140 return data()[i];
141 }
142 const uint8_t& operator[](const size_t i) const {
143 BoundsCheck(i);
144 return data()[i];
145 }
146
back()147 uint8_t& back() {
148 JXL_ASSERT(size() != 0);
149 return data()[size() - 1];
150 }
back()151 const uint8_t& back() const {
152 JXL_ASSERT(size() != 0);
153 return data()[size() - 1];
154 }
155
156 template <typename T>
append(const T & other)157 void append(const T& other) {
158 append(reinterpret_cast<const uint8_t*>(other.data()),
159 reinterpret_cast<const uint8_t*>(other.data()) + other.size());
160 }
161
append(const uint8_t * begin,const uint8_t * end)162 void append(const uint8_t* begin, const uint8_t* end) {
163 size_t old_size = size();
164 resize(size() + (end - begin));
165 memcpy(data() + old_size, begin, end - begin);
166 }
167
168 private:
BoundsCheck(size_t i)169 void BoundsCheck(size_t i) const {
170 // <= is safe due to padding and required by BitWriter.
171 JXL_ASSERT(i <= size());
172 }
173
174 // Copies existing data to newly allocated "data_". If allocation fails,
175 // data() == nullptr and size_ = capacity_ = 0.
176 // The new capacity will be at least 1.5 times the old capacity. This ensures
177 // that we avoid quadratic behaviour.
178 void IncreaseCapacityTo(size_t capacity);
179
180 size_t size_;
181 size_t capacity_;
182 CacheAlignedUniquePtr data_;
183 };
184
185 template <typename T>
Append(const T & s,PaddedBytes * out,size_t * JXL_RESTRICT byte_pos)186 static inline void Append(const T& s, PaddedBytes* out,
187 size_t* JXL_RESTRICT byte_pos) {
188 memcpy(out->data() + *byte_pos, s.data(), s.size());
189 *byte_pos += s.size();
190 JXL_CHECK(*byte_pos <= out->size());
191 }
192
193 } // namespace jxl
194
195 #endif // LIB_JXL_BASE_PADDED_BYTES_H_
196