Line data Source code
1 : /******************************************************************************************************
2 :
3 : (C) 2022-2025 IVAS codec Public Collaboration with portions copyright Dolby International AB, Ericsson AB,
4 : Fraunhofer-Gesellschaft zur Foerderung der angewandten Forschung e.V., Huawei Technologies Co. LTD.,
5 : Koninklijke Philips N.V., Nippon Telegraph and Telephone Corporation, Nokia Technologies Oy, Orange,
6 : Panasonic Holdings Corporation, Qualcomm Technologies, Inc., VoiceAge Corporation, and other
7 : contributors to this repository. All Rights Reserved.
8 :
9 : This software is protected by copyright law and by international treaties.
10 : The IVAS codec Public Collaboration consisting of Dolby International AB, Ericsson AB,
11 : Fraunhofer-Gesellschaft zur Foerderung der angewandten Forschung e.V., Huawei Technologies Co. LTD.,
12 : Koninklijke Philips N.V., Nippon Telegraph and Telephone Corporation, Nokia Technologies Oy, Orange,
13 : Panasonic Holdings Corporation, Qualcomm Technologies, Inc., VoiceAge Corporation, and other
14 : contributors to this repository retain full ownership rights in their respective contributions in
15 : the software. This notice grants no license of any kind, including but not limited to patent
16 : license, nor is any license granted by implication, estoppel or otherwise.
17 :
18 : Contributors are required to enter into the IVAS codec Public Collaboration agreement before making
19 : contributions.
20 :
21 : This software is provided "AS IS", without any express or implied warranties. The software is in the
22 : development stage. It is intended exclusively for experts who have experience with such software and
23 : solely for the purpose of inspection. All implied warranties of non-infringement, merchantability
24 : and fitness for a particular purpose are hereby disclaimed and excluded.
25 :
26 : Any dispute, controversy or claim arising under or in relation to providing this software shall be
27 : submitted to and settled by the final, binding jurisdiction of the courts of Munich, Germany in
28 : accordance with the laws of the Federal Republic of Germany excluding its conflict of law rules and
29 : the United Nations Convention on Contracts on the International Sales of Goods.
30 :
31 : *******************************************************************************************************/
32 :
33 : /*====================================================================================
34 : EVS Codec 3GPP TS26.443 Nov 04, 2021. Version 12.14.0 / 13.10.0 / 14.6.0 / 15.4.0 / 16.3.0
35 : ====================================================================================*/
36 :
37 : /** \file jbm_jb4_inputbuffer.c RTP input buffer with fixed capacity. */
38 :
39 : #include <assert.h>
40 : #include <stdint.h>
41 : #include "options.h"
42 : #include "prot.h"
43 : #include "string.h"
44 : #ifdef DEBUGGING
45 : #include "debug.h"
46 : #endif
47 : #include "jbm_jb4_inputbuffer.h"
48 : #include "wmc_auto.h"
49 :
50 : #define WMC_TOOL_SKIP
51 :
52 :
53 : /** input buffer with fixed capacity */
54 : struct JB4_INPUTBUFFER
55 : {
56 : /** elements of input buffer */
57 : JB4_INPUTBUFFER_ELEMENT *data;
58 : /** maximum allowed number of elements plus one free element (to decide between full/empty buffer) */
59 : uint16_t capacity;
60 : /** position of next enque operation */
61 : uint16_t writePos;
62 : /** position of next deque operation */
63 : uint16_t readPos;
64 : /** function to compare two elements */
65 : int16_t ( *compareFunction )( const JB4_INPUTBUFFER_ELEMENT first, const JB4_INPUTBUFFER_ELEMENT second, bool *replaceWithNewElementIfEqual );
66 : };
67 :
68 :
69 : /* Creates a input buffer */
70 105 : ivas_error JB4_INPUTBUFFER_Create(
71 : JB4_INPUTBUFFER_HANDLE *ph )
72 : {
73 : JB4_INPUTBUFFER_HANDLE h;
74 :
75 105 : if ( ( h = malloc( sizeof( struct JB4_INPUTBUFFER ) ) ) == NULL )
76 : {
77 0 : return ( IVAS_ERROR( IVAS_ERR_FAILED_ALLOC, "Can not allocate memory for JBM\n" ) );
78 : }
79 :
80 105 : h->data = NULL;
81 105 : h->capacity = 0;
82 105 : h->writePos = 0;
83 105 : h->readPos = 0;
84 105 : h->compareFunction = NULL;
85 :
86 105 : *ph = h;
87 :
88 105 : return IVAS_ERR_OK;
89 : }
90 :
91 :
92 : /* Destroys the input buffer */
93 105 : void JB4_INPUTBUFFER_Destroy(
94 : JB4_INPUTBUFFER_HANDLE *ph )
95 : {
96 : JB4_INPUTBUFFER_HANDLE h;
97 :
98 105 : if ( !ph )
99 : {
100 0 : return;
101 : }
102 105 : h = *ph;
103 105 : if ( !h )
104 : {
105 0 : return;
106 : }
107 :
108 105 : if ( h->data )
109 : {
110 105 : free( h->data );
111 : }
112 :
113 105 : free( h );
114 105 : *ph = NULL;
115 :
116 105 : return;
117 : }
118 :
119 :
120 : /* Initializes a input buffer with a fixed maximum allowed number of elements */
121 105 : ivas_error JB4_INPUTBUFFER_Init(
122 : JB4_INPUTBUFFER_HANDLE h,
123 : uint16_t capacity,
124 : int16_t ( *compareFunction )( const JB4_INPUTBUFFER_ELEMENT first, const JB4_INPUTBUFFER_ELEMENT second, bool *replaceWithNewElementIfEqual ) )
125 : {
126 :
127 : /* keep one element free to be able to decide between full/empty buffer */
128 105 : ++capacity;
129 105 : if ( ( h->data = malloc( capacity * sizeof( JB4_INPUTBUFFER_ELEMENT ) ) ) == NULL )
130 : {
131 0 : return ( IVAS_ERROR( IVAS_ERR_FAILED_ALLOC, "Can not allocate memory for JBM\n" ) );
132 : }
133 :
134 105 : h->capacity = capacity;
135 105 : h->writePos = 0;
136 105 : h->readPos = 0;
137 105 : h->compareFunction = compareFunction;
138 :
139 105 : return IVAS_ERR_OK;
140 : }
141 :
142 :
143 69921 : int16_t JB4_INPUTBUFFER_Enque(
144 : JB4_INPUTBUFFER_HANDLE h,
145 : JB4_INPUTBUFFER_ELEMENT element,
146 : JB4_INPUTBUFFER_ELEMENT *replacedElement )
147 : {
148 : uint16_t j, size;
149 : int16_t low, high, middle, diff;
150 : uint16_t insertPos;
151 : uint16_t canMoveRight;
152 : uint16_t canMoveLeft;
153 : bool replace;
154 :
155 69921 : *replacedElement = NULL;
156 :
157 69921 : size = JB4_INPUTBUFFER_Size( h );
158 69921 : if ( size >= h->capacity - 1 )
159 : {
160 0 : return -1;
161 : }
162 :
163 : /* appending the first element is straight forward */
164 69921 : if ( size == 0U )
165 : {
166 2025 : h->data[h->writePos] = element;
167 2025 : ++h->writePos;
168 2025 : if ( h->writePos == h->capacity )
169 : {
170 3 : h->writePos = 0;
171 : }
172 2025 : return 0;
173 : }
174 :
175 : /* there's a high probability that the new element can be appended at the back */
176 67896 : if ( h->compareFunction( element, JB4_INPUTBUFFER_Back( h ), &replace ) > 0 )
177 : {
178 67896 : h->data[h->writePos] = element;
179 67896 : ++h->writePos;
180 67896 : if ( h->writePos == h->capacity )
181 : {
182 648 : h->writePos = 0;
183 : }
184 67896 : return 0;
185 : }
186 :
187 : /* out of order: use binary search to get the position to insert */
188 0 : low = 0;
189 0 : high = size - 1;
190 0 : while ( low <= high )
191 : {
192 0 : middle = low + ( high - low ) / 2;
193 0 : diff = h->compareFunction( element, JB4_INPUTBUFFER_Element( h, middle ), &replace );
194 0 : if ( diff < 0 )
195 : {
196 0 : high = middle - 1;
197 : }
198 0 : else if ( diff > 0 )
199 : {
200 0 : low = middle + 1;
201 : }
202 : else /* an element with same index is already stored */
203 : {
204 0 : if ( replace != 0 )
205 : {
206 0 : *replacedElement = h->data[( h->readPos + middle ) % h->capacity];
207 0 : h->data[( h->readPos + middle ) % h->capacity] = element;
208 0 : return 0;
209 : }
210 0 : return 1;
211 : }
212 : }
213 :
214 : #ifdef DEBUGGING
215 : assert( h->compareFunction( element, JB4_INPUTBUFFER_Element( h, low ), &replace ) != 0 );
216 : if ( low > 0 )
217 : assert( h->compareFunction( element, JB4_INPUTBUFFER_Element( h, low - 1 ), &replace ) > 0 );
218 : assert( h->compareFunction( element, JB4_INPUTBUFFER_Element( h, low ), &replace ) < 0 );
219 : if ( (uint16_t) ( low + 1 ) < size )
220 : assert( h->compareFunction( element, JB4_INPUTBUFFER_Element( h, low + 1 ), &replace ) < 0 );
221 : #endif
222 :
223 0 : insertPos = ( h->readPos + low ) % h->capacity;
224 0 : if ( h->readPos < h->writePos )
225 : {
226 0 : canMoveRight = 1;
227 0 : canMoveLeft = h->readPos > 0;
228 : }
229 : else
230 : {
231 0 : canMoveRight = insertPos < h->writePos;
232 0 : canMoveLeft = insertPos > h->writePos;
233 : }
234 :
235 0 : assert( canMoveRight != 0 || canMoveLeft != 0 );
236 :
237 0 : if ( canMoveRight )
238 : {
239 : /* move higher elements to the right and insert at insertPos */
240 0 : for ( j = h->writePos; j > insertPos; --j )
241 : {
242 0 : h->data[j] = h->data[j - 1];
243 : }
244 :
245 0 : h->data[insertPos] = element;
246 0 : ++h->writePos;
247 0 : if ( h->writePos == h->capacity )
248 : {
249 0 : h->writePos = 0;
250 : }
251 : }
252 : else
253 : {
254 : /* move lower elements to the left and insert before insertPos */
255 0 : for ( j = 0; j < low; j++ )
256 : {
257 0 : h->data[h->readPos - 1 + j] = h->data[h->readPos + j];
258 : }
259 :
260 0 : h->data[insertPos - 1] = element;
261 0 : --h->readPos;
262 0 : assert( (int16_t) h->readPos >= 0 );
263 : }
264 :
265 0 : return 0;
266 : }
267 :
268 :
269 69921 : int16_t JB4_INPUTBUFFER_Deque(
270 : JB4_INPUTBUFFER_HANDLE h,
271 : JB4_INPUTBUFFER_ELEMENT *pElement )
272 : {
273 69921 : if ( JB4_INPUTBUFFER_IsEmpty( h ) )
274 : {
275 0 : return -1;
276 : }
277 :
278 69921 : *pElement = h->data[h->readPos];
279 69921 : ++h->readPos;
280 69921 : if ( h->readPos == h->capacity )
281 : {
282 651 : h->readPos = 0;
283 : }
284 :
285 69921 : return 0;
286 : }
287 :
288 :
289 : /* Returns the first element. */
290 151059 : JB4_INPUTBUFFER_ELEMENT JB4_INPUTBUFFER_Front(
291 : const JB4_INPUTBUFFER_HANDLE h )
292 : {
293 : JB4_INPUTBUFFER_ELEMENT ret;
294 :
295 :
296 151059 : ret = h->data[h->readPos];
297 :
298 151059 : return ret;
299 : }
300 :
301 :
302 : /* Returns the last element. */
303 69048 : JB4_INPUTBUFFER_ELEMENT JB4_INPUTBUFFER_Back(
304 : const JB4_INPUTBUFFER_HANDLE h )
305 : {
306 : JB4_INPUTBUFFER_ELEMENT ret;
307 :
308 69048 : if ( h->writePos != 0U )
309 : {
310 68442 : ret = h->data[h->writePos - 1];
311 : }
312 : else
313 : {
314 606 : ret = h->data[h->capacity - 1];
315 : }
316 :
317 69048 : return ret;
318 : }
319 :
320 :
321 : /* Returns the element with the given index (0 means front element). */
322 18462 : JB4_INPUTBUFFER_ELEMENT JB4_INPUTBUFFER_Element(
323 : const JB4_INPUTBUFFER_HANDLE h,
324 : uint16_t index )
325 : {
326 : JB4_INPUTBUFFER_ELEMENT ret;
327 :
328 : /* return h->data[(h->readPos + index) % h->capacity] without error handling */
329 18462 : if ( h->readPos + index < h->capacity )
330 : {
331 18411 : ret = h->data[h->readPos + index];
332 : }
333 : else
334 : {
335 : /* wrap around */
336 51 : ret = h->data[h->readPos + index - h->capacity];
337 : }
338 :
339 18462 : return ret;
340 : }
341 :
342 :
343 224010 : int16_t JB4_INPUTBUFFER_IsEmpty(
344 : const JB4_INPUTBUFFER_HANDLE h )
345 : {
346 : int16_t ret;
347 :
348 224010 : ret = h->readPos == h->writePos;
349 :
350 224010 : return ret;
351 : }
352 :
353 :
354 139842 : int16_t JB4_INPUTBUFFER_IsFull(
355 : const JB4_INPUTBUFFER_HANDLE h )
356 : {
357 : int16_t ret;
358 :
359 139842 : ret = 0;
360 139842 : if ( JB4_INPUTBUFFER_Size( h ) == h->capacity - 1 )
361 : {
362 0 : ret = 1;
363 : }
364 :
365 139842 : return ret;
366 : }
367 :
368 :
369 217472 : uint16_t JB4_INPUTBUFFER_Size(
370 : const JB4_INPUTBUFFER_HANDLE h )
371 : {
372 : uint16_t ret;
373 :
374 217472 : if ( h->readPos <= h->writePos )
375 : {
376 208640 : ret = h->writePos - h->readPos;
377 : }
378 : else
379 : {
380 : /* wrap around */
381 8832 : ret = h->writePos + h->capacity - h->readPos;
382 : }
383 :
384 217472 : return ret;
385 : }
386 :
387 : #undef WMC_TOOL_SKIP
|
