Debian Codegraph @

modules/lsp-runtime-lib/src/main/runtime/buffer.cpp

raw
1 /*
2 * Copyright (C) 2025 Linux Studio Plugins Project <https://lsp-plug.in/>
3 * (C) 2025 Vladimir Sadovnikov <[email protected]>
4 *
5 * This file is part of lsp-runtime-lib
6 * Created on: 13 мар. 2021 г.
7 *
8 * lsp-runtime-lib is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU Lesser General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * any later version.
12 *
13 * lsp-runtime-lib is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public License
19 * along with lsp-runtime-lib. If not, see <https://www.gnu.org/licenses/>.
20 */
21
22 #include <lsp-plug.in/common/alloc.h>
23 #include <lsp-plug.in/stdlib/string.h>
24 #include <lsp-plug.in/resource/buffer.h>
25
26 namespace lsp
27 {
28 namespace resource
29 {
30 cbuffer_t::cbuffer_t()
31 {
32 data = NULL;
33 index = NULL;
34 root = NULL;
35 head = 0;
36 length = 0;
37 cap = 0;
38 }
39
40 cbuffer_t::~cbuffer_t()
41 {
42 destroy();
43 }
44
45 status_t cbuffer_t::init(size_t log_capacity)
46 {
47 const size_t capacity = 1 << log_capacity;
48 const size_t dbuf = capacity * sizeof(uint8_t);
49 const size_t ibuf = capacity * sizeof(uint32_t);
50 const size_t rbuf = 0x100 * sizeof(uint32_t);
51
52 uint8_t *ptr = static_cast<uint8_t *>(realloc(data, dbuf + ibuf + rbuf));
53 if (ptr == NULL)
54 return STATUS_NO_MEM;
55
56 data = advance_ptr_bytes<uint8_t>(ptr, dbuf);
57 index = advance_ptr_bytes<uint32_t>(ptr, ibuf);
58 root = advance_ptr_bytes<uint32_t>(ptr, rbuf);
59 head = 0;
60 length = 0;
61 cap = uint32_t(capacity);
62
63 for (size_t i=0; i < 0x100; ++i)
64 root[i] = -1;
65
66 return STATUS_OK;
67 }
68
69 void cbuffer_t::destroy()
70 {
71 if (data != NULL)
72 free(data);
73 data = NULL;
74 index = NULL;
75 root = NULL;
76 head = 0;
77 length = 0;
78 cap = 0;
79 }
80
81 void cbuffer_t::append(const void *src, size_t count)
82 {
83 const uint8_t *v = static_cast<const uint8_t *>(src);
84 if (count >= cap)
85 {
86 // Cleanup root index and reset head
87 for (size_t i=0; i<0x100; ++i)
88 root[i] = -1;
89 length = 0;
90 head = 0;
91
92 // Append tail only
93 v += count - cap;
94 count = cap;
95 }
96
97 // Fill the buffer
98 const size_t mask = cap - 1;
99 const size_t ohead = head;
100 head = (head + count) & mask;
101 if (head < ohead)
102 {
103 const size_t split = cap - ohead;
104 memcpy(&data[ohead], v, split * sizeof(uint8_t));
105 memcpy(&data[0], &v[split], (count - split) * sizeof(uint8_t));
106 }
107 else
108 memcpy(&data[ohead], v, count * sizeof(uint8_t));
109
110 // Update index
111 uint32_t new_length = length;
112 for (size_t i=0; i<count; ++i)
113 {
114 const size_t off = (ohead + i) & mask; // Compute offset
115 const uint8_t b = v[i]; // Fetch byte
116 index[off] = root[b]; // Store offset of previous element
117 root[b] = new_length++; // Update absolute root offset
118 }
119
120 // Update buffer length and sequence counter
121 length = new_length;
122 }
123
124 void cbuffer_t::append(uint8_t b)
125 {
126 // Append byte
127 data[head] = b; // Data byte
128 index[head] = root[b]; // Store offset of previous element
129 root[b] = length++; // Update length
130 head = (head + 1) & (cap - 1); // Update head
131 }
132
133 size_t cbuffer_t::lookup(size_t *out, const void *src, size_t avail)
134 {
135 const uint8_t *v = static_cast<const uint8_t *>(src);
136 const size_t dmax = size();
137
138 size_t len = 0;
139 ssize_t offset = 0;
140
141 // We can not find sequence larger than 'length' bytes
142 avail = lsp_min(avail, dmax);
143
144 // Lookup among all matches
145 uint32_t delta = length - root[*v];
146 const size_t mask = cap - 1;
147 while (delta <= dmax)
148 {
149 // Byte matched, do some heuristics
150 const size_t soff = (head + cap - delta) & mask;
151 if ((len > 1) && (data[(soff + len - 1) & mask] != v[len-1]))
152 {
153 delta = length - index[soff];
154 continue;
155 }
156
157 // Compute the length of the sub-sequence
158 const size_t lookup = lsp_min(avail, delta);
159 size_t slen = 1;
160 for (size_t i=1; i<lookup; ++i)
161 {
162 if (v[i] != data[(soff + i) & mask])
163 break;
164 ++slen;
165 }
166
167 // Update lookup result
168 if (len < slen)
169 {
170 offset = delta;
171 len = slen;
172 if (len >= avail)
173 break;
174 }
175
176 // Update search position
177 delta = length - index[soff];
178 }
179
180 *out = offset - 1;
181 return len;
182 }
183
184 uint8_t cbuffer_t::byte_at(size_t offset)
185 {
186 return (offset < cap) ? data[(head + cap - offset - 1) & (cap - 1)] : 0;
187 }
188
189 void cbuffer_t::clear()
190 {
191 head = 0;
192 length = 0;
193
194 if (root != NULL)
195 {
196 for (size_t i=0; i < 0x100; ++i)
197 root[i] = -1;
198 }
199 }
200
201 dbuffer_t::dbuffer_t()
202 {
203 data = NULL;
204 length = 0;
205 head = 0;
206 cap = 0;
207 }
208
209 dbuffer_t::~dbuffer_t()
210 {
211 destroy();
212 }
213
214 status_t dbuffer_t::init(size_t log_capacity)
215 {
216 size_t dbuf = sizeof(uint8_t) << log_capacity;
217 uint8_t *ptr = static_cast<uint8_t *>(realloc(data, dbuf));
218 if (ptr == NULL)
219 return STATUS_NO_MEM;
220
221 data = ptr;
222 length = 0;
223 head = 0;
224 cap = uint32_t(1 << log_capacity);
225
226 return STATUS_OK;
227 }
228
229 void dbuffer_t::destroy()
230 {
231 if (data != NULL)
232 free(data);
233 data = NULL;
234 length = 0;
235 head = 0;
236 cap = 0;
237 }
238
239 void dbuffer_t::append(const void *src, size_t count)
240 {
241 const uint8_t *v = static_cast<const uint8_t *>(src);
242 if (count >= cap)
243 {
244 // Replace data in the buffer
245 memcpy(data, &v[count - cap], cap * sizeof(uint8_t));
246 length = cap;
247 head = 0;
248 return;
249 }
250
251 // Copy data to the buffer
252 size_t ohead = head;
253 head = (head + count) & (cap-1);
254 if (head < ohead)
255 {
256 const size_t split = cap - ohead;
257 memcpy(&data[ohead], v, split * sizeof(uint8_t));
258 memcpy(&data[0], &v[split], head * sizeof(uint8_t));
259 }
260 else
261 memcpy(&data[ohead], v, count * sizeof(uint8_t));
262
263 length = uint32_t(lsp_min(length + count, cap));
264 }
265
266 status_t dbuffer_t::extract(void *dst, size_t offset, size_t count)
267 {
268 if (offset >= length)
269 return STATUS_UNDERFLOW;
270
271 const size_t shift = offset + 1;
272 if (count > shift)
273 return STATUS_UNDERFLOW;
274
275 uint8_t *dptr = static_cast<uint8_t *>(dst);
276 uint32_t soff = (head + cap - shift) & (cap-1);
277
278 if ((soff + count) > cap)
279 {
280 const size_t split = cap - soff;
281 memcpy(dptr, &data[soff], split * sizeof(uint8_t));
282 memcpy(&dptr[split], data, (count - split) * sizeof(uint8_t));
283 }
284 else
285 memcpy(dptr, &data[soff], count * sizeof(uint8_t));
286
287 return STATUS_OK;
288 }
289
290 void dbuffer_t::append(uint8_t v)
291 {
292 data[head] = v;
293 head = (head + 1) & (cap - 1);
294 length = lsp_min(length + 1, cap);
295 }
296
297 void dbuffer_t::clear()
298 {
299 length = 0;
300 head = 0;
301 }
302
303 } /* namespace resource */
304 } /* namespace lsp */
305
306