blob: bcb191ae622b5feaa1194027fe81cfe5acef0b74 [file] [log] [blame]
Joe Drago444f0512019-01-23 17:03:24 -08001// Copyright 2019 Joe Drago. All rights reserved.
2// SPDX-License-Identifier: BSD-2-Clause
3
4#include "avif/internal.h"
5
Wan-Teh Chang1ccd4382022-02-10 20:24:19 -08006#include <assert.h>
Joe Drago444f0512019-01-23 17:03:24 -08007#include <math.h>
8#include <string.h>
9
10float avifRoundf(float v)
11{
12 return floorf(v + 0.5f);
13}
14
15// Thanks, Rob Pike! https://commandcenter.blogspot.nl/2012/04/byte-order-fallacy.html
16
17uint16_t avifHTONS(uint16_t s)
18{
Vincent Rabaud4865c1c2023-12-18 11:56:56 +010019 uint16_t result = 0;
Yannis Guyond36a3a02022-03-28 16:09:12 +020020 uint8_t * data = (uint8_t *)&result;
Joe Drago444f0512019-01-23 17:03:24 -080021 data[0] = (s >> 8) & 0xff;
22 data[1] = (s >> 0) & 0xff;
Joe Drago444f0512019-01-23 17:03:24 -080023 return result;
24}
25
26uint16_t avifNTOHS(uint16_t s)
27{
Yannis Guyond36a3a02022-03-28 16:09:12 +020028 const uint8_t * data = (const uint8_t *)&s;
Joe Drago7a9a6612019-07-17 11:21:24 -070029 return (uint16_t)((data[1] << 0) | (data[0] << 8));
Joe Drago444f0512019-01-23 17:03:24 -080030}
31
Yannis Guyon1fa47f22022-09-18 14:03:53 +020032uint16_t avifCTOHS(uint16_t s)
33{
34 const uint8_t * data = (const uint8_t *)&s;
35 return (uint16_t)((data[0] << 0) | (data[1] << 8));
36}
37
Joe Drago444f0512019-01-23 17:03:24 -080038uint32_t avifHTONL(uint32_t l)
39{
Vincent Rabaud4865c1c2023-12-18 11:56:56 +010040 uint32_t result = 0;
Yannis Guyond36a3a02022-03-28 16:09:12 +020041 uint8_t * data = (uint8_t *)&result;
Joe Drago444f0512019-01-23 17:03:24 -080042 data[0] = (l >> 24) & 0xff;
43 data[1] = (l >> 16) & 0xff;
44 data[2] = (l >> 8) & 0xff;
45 data[3] = (l >> 0) & 0xff;
Joe Drago444f0512019-01-23 17:03:24 -080046 return result;
47}
48
49uint32_t avifNTOHL(uint32_t l)
50{
Yannis Guyond36a3a02022-03-28 16:09:12 +020051 const uint8_t * data = (const uint8_t *)&l;
Joe Drago7a9a6612019-07-17 11:21:24 -070052 return ((uint32_t)data[3] << 0) | ((uint32_t)data[2] << 8) | ((uint32_t)data[1] << 16) | ((uint32_t)data[0] << 24);
Joe Drago444f0512019-01-23 17:03:24 -080053}
54
Yannis Guyon1fa47f22022-09-18 14:03:53 +020055uint32_t avifCTOHL(uint32_t l)
56{
57 const uint8_t * data = (const uint8_t *)&l;
58 return ((uint32_t)data[0] << 0) | ((uint32_t)data[1] << 8) | ((uint32_t)data[2] << 16) | ((uint32_t)data[3] << 24);
59}
60
Joe Drago444f0512019-01-23 17:03:24 -080061uint64_t avifHTON64(uint64_t l)
62{
Vincent Rabaud4865c1c2023-12-18 11:56:56 +010063 uint64_t result = 0;
Yannis Guyond36a3a02022-03-28 16:09:12 +020064 uint8_t * data = (uint8_t *)&result;
Joe Drago444f0512019-01-23 17:03:24 -080065 data[0] = (l >> 56) & 0xff;
66 data[1] = (l >> 48) & 0xff;
67 data[2] = (l >> 40) & 0xff;
68 data[3] = (l >> 32) & 0xff;
69 data[4] = (l >> 24) & 0xff;
70 data[5] = (l >> 16) & 0xff;
71 data[6] = (l >> 8) & 0xff;
72 data[7] = (l >> 0) & 0xff;
Joe Drago444f0512019-01-23 17:03:24 -080073 return result;
74}
75
76uint64_t avifNTOH64(uint64_t l)
77{
Yannis Guyond36a3a02022-03-28 16:09:12 +020078 const uint8_t * data = (const uint8_t *)&l;
Joe Drago97b071c2019-07-17 14:24:56 -070079 return ((uint64_t)data[7] << 0) | ((uint64_t)data[6] << 8) | ((uint64_t)data[5] << 16) | ((uint64_t)data[4] << 24) |
80 ((uint64_t)data[3] << 32) | ((uint64_t)data[2] << 40) | ((uint64_t)data[1] << 48) | ((uint64_t)data[0] << 56);
Joe Drago444f0512019-01-23 17:03:24 -080081}
Joe Drago05559c92019-07-17 16:33:38 -070082
83AVIF_ARRAY_DECLARE(avifArrayInternal, uint8_t, ptr);
84
Wan-Teh Changf732a4d2022-01-21 15:56:35 -080085// On error, this function must set arr->ptr to NULL and both arr->count and arr->capacity to 0.
86avifBool avifArrayCreate(void * arrayStruct, uint32_t elementSize, uint32_t initialCapacity)
Joe Drago05559c92019-07-17 16:33:38 -070087{
88 avifArrayInternal * arr = (avifArrayInternal *)arrayStruct;
89 arr->elementSize = elementSize ? elementSize : 1;
90 arr->count = 0;
91 arr->capacity = initialCapacity;
Wan-Teh Chang620f4912021-03-19 13:13:52 -070092 size_t byteCount = (size_t)arr->elementSize * arr->capacity;
93 arr->ptr = (uint8_t *)avifAlloc(byteCount);
Wan-Teh Changf732a4d2022-01-21 15:56:35 -080094 if (!arr->ptr) {
95 arr->capacity = 0;
96 return AVIF_FALSE;
97 }
Wan-Teh Chang620f4912021-03-19 13:13:52 -070098 memset(arr->ptr, 0, byteCount);
Wan-Teh Changf732a4d2022-01-21 15:56:35 -080099 return AVIF_TRUE;
Joe Drago05559c92019-07-17 16:33:38 -0700100}
101
Yannis Guyon1fbea622023-10-18 20:21:33 +0200102void * avifArrayPush(void * arrayStruct)
Joe Drago05559c92019-07-17 16:33:38 -0700103{
104 avifArrayInternal * arr = (avifArrayInternal *)arrayStruct;
105 if (arr->count == arr->capacity) {
106 uint8_t * oldPtr = arr->ptr;
Wan-Teh Chang620f4912021-03-19 13:13:52 -0700107 size_t oldByteCount = (size_t)arr->elementSize * arr->capacity;
108 arr->ptr = (uint8_t *)avifAlloc(oldByteCount * 2);
Yannis Guyon1fbea622023-10-18 20:21:33 +0200109 if (arr->ptr == NULL) {
110 return NULL;
111 }
Joe Drago05559c92019-07-17 16:33:38 -0700112 memset(arr->ptr + oldByteCount, 0, oldByteCount);
113 memcpy(arr->ptr, oldPtr, oldByteCount);
114 arr->capacity *= 2;
115 avifFree(oldPtr);
116 }
117 ++arr->count;
Yannis Guyon1fbea622023-10-18 20:21:33 +0200118 return &arr->ptr[(arr->count - 1) * (size_t)arr->elementSize];
Joe Drago05559c92019-07-17 16:33:38 -0700119}
120
Wan-Teh Changf732a4d2022-01-21 15:56:35 -0800121void avifArrayPop(void * arrayStruct)
122{
123 avifArrayInternal * arr = (avifArrayInternal *)arrayStruct;
Wan-Teh Chang1ccd4382022-02-10 20:24:19 -0800124 assert(arr->count > 0);
Wan-Teh Changf732a4d2022-01-21 15:56:35 -0800125 --arr->count;
Wan-Teh Chang1ccd4382022-02-10 20:24:19 -0800126 memset(&arr->ptr[arr->count * (size_t)arr->elementSize], 0, arr->elementSize);
Wan-Teh Changf732a4d2022-01-21 15:56:35 -0800127}
128
Joe Drago05559c92019-07-17 16:33:38 -0700129void avifArrayDestroy(void * arrayStruct)
130{
131 avifArrayInternal * arr = (avifArrayInternal *)arrayStruct;
132 if (arr->ptr) {
133 avifFree(arr->ptr);
134 arr->ptr = NULL;
135 }
136 memset(arr, 0, sizeof(avifArrayInternal));
137}
Yuan Tong5d16f1f2023-01-21 01:23:25 +0800138
139// |a| and |b| hold int32_t values. The int64_t type is used so that we can negate INT32_MIN without
140// overflowing int32_t.
141static int64_t calcGCD(int64_t a, int64_t b)
142{
143 if (a < 0) {
144 a *= -1;
145 }
146 if (b < 0) {
147 b *= -1;
148 }
149 while (b != 0) {
150 int64_t r = a % b;
151 a = b;
152 b = r;
153 }
154 return a;
155}
156
157void avifFractionSimplify(avifFraction * f)
158{
159 int64_t gcd = calcGCD(f->n, f->d);
160 if (gcd > 1) {
161 f->n = (int32_t)(f->n / gcd);
162 f->d = (int32_t)(f->d / gcd);
163 }
164}
165
166static avifBool overflowsInt32(int64_t x)
167{
168 return (x < INT32_MIN) || (x > INT32_MAX);
169}
170
Yuan Tong5d16f1f2023-01-21 01:23:25 +0800171avifBool avifFractionCD(avifFraction * a, avifFraction * b)
172{
173 avifFractionSimplify(a);
174 avifFractionSimplify(b);
175 if (a->d != b->d) {
176 const int64_t ad = a->d;
177 const int64_t bd = b->d;
178 const int64_t anNew = a->n * bd;
179 const int64_t adNew = a->d * bd;
180 const int64_t bnNew = b->n * ad;
181 const int64_t bdNew = b->d * ad;
182 if (overflowsInt32(anNew) || overflowsInt32(adNew) || overflowsInt32(bnNew) || overflowsInt32(bdNew)) {
183 return AVIF_FALSE;
184 }
185 a->n = (int32_t)anNew;
186 a->d = (int32_t)adNew;
187 b->n = (int32_t)bnNew;
188 b->d = (int32_t)bdNew;
189 }
190 return AVIF_TRUE;
191}
192
193avifBool avifFractionAdd(avifFraction a, avifFraction b, avifFraction * result)
194{
195 if (!avifFractionCD(&a, &b)) {
196 return AVIF_FALSE;
197 }
198
199 const int64_t resultN = (int64_t)a.n + b.n;
200 if (overflowsInt32(resultN)) {
201 return AVIF_FALSE;
202 }
203 result->n = (int32_t)resultN;
204 result->d = a.d;
205
206 avifFractionSimplify(result);
207 return AVIF_TRUE;
208}
209
210avifBool avifFractionSub(avifFraction a, avifFraction b, avifFraction * result)
211{
212 if (!avifFractionCD(&a, &b)) {
213 return AVIF_FALSE;
214 }
215
216 const int64_t resultN = (int64_t)a.n - b.n;
217 if (overflowsInt32(resultN)) {
218 return AVIF_FALSE;
219 }
220 result->n = (int32_t)resultN;
221 result->d = a.d;
222
223 avifFractionSimplify(result);
224 return AVIF_TRUE;
225}
maryla-ucbc6c2c52023-09-06 11:29:06 +0200226
maryla-ucbdf83492023-11-02 14:55:50 +0100227static avifBool avifDoubleToUnsignedFractionImpl(double v, uint32_t maxNumerator, uint32_t * numerator, uint32_t * denominator)
maryla-ucbc6c2c52023-09-06 11:29:06 +0200228{
maryla-ucbdf83492023-11-02 14:55:50 +0100229 if (isnan(v) || v < 0 || v > maxNumerator) {
maryla-ucbc6c2c52023-09-06 11:29:06 +0200230 return AVIF_FALSE;
231 }
232
maryla-ucbdf83492023-11-02 14:55:50 +0100233 // Maximum denominator: makes sure that the numerator is <= maxNumerator and the denominator is <= UINT32_MAX.
234 const uint64_t maxD = (v <= 1) ? UINT32_MAX : (uint64_t)floor(maxNumerator / v);
maryla-ucbc6c2c52023-09-06 11:29:06 +0200235
236 // Find the best approximation of v as a fraction using continued fractions, see
237 // https://en.wikipedia.org/wiki/Continued_fraction
238 *denominator = 1;
239 uint32_t previousD = 0;
240 double currentV = v - floor(v);
241 int iter = 0;
242 // Set a maximum number of iterations to be safe. Most numbers should
243 // converge in less than ~20 iterations.
244 // The golden ratio is the worst case and takes 39 iterations.
245 const int maxIter = 39;
246 while (iter < maxIter) {
247 const double numeratorDouble = (double)(*denominator) * v;
maryla-ucbdf83492023-11-02 14:55:50 +0100248 assert(numeratorDouble <= maxNumerator);
maryla-ucbc6c2c52023-09-06 11:29:06 +0200249 *numerator = (uint32_t)round(numeratorDouble);
250 if (fabs(numeratorDouble - (*numerator)) == 0.0) {
251 return AVIF_TRUE;
252 }
253 currentV = 1.0 / currentV;
254 const double newD = previousD + floor(currentV) * (*denominator);
255 if (newD > maxD) {
256 // This is the best we can do with a denominator <= max_d.
257 return AVIF_TRUE;
258 }
259 previousD = *denominator;
260 assert(newD <= UINT32_MAX);
261 *denominator = (uint32_t)newD;
262 currentV -= floor(currentV);
263 ++iter;
264 }
265 // Maximum number of iterations reached, return what we've found.
266 // For max_iter >= 39 we shouldn't get here. max_iter can be set
267 // to a lower value to speed up the algorithm if needed.
268 *numerator = (uint32_t)round((double)(*denominator) * v);
269 return AVIF_TRUE;
270}
maryla-ucbdf83492023-11-02 14:55:50 +0100271
272avifBool avifDoubleToSignedFraction(double v, int32_t * numerator, uint32_t * denominator)
273{
274 uint32_t positive_numerator;
275 if (!avifDoubleToUnsignedFractionImpl(fabs(v), INT32_MAX, &positive_numerator, denominator)) {
276 return AVIF_FALSE;
277 }
278 *numerator = (int32_t)positive_numerator;
279 if (v < 0) {
280 *numerator *= -1;
281 }
282 return AVIF_TRUE;
283}
284
285avifBool avifDoubleToUnsignedFraction(double v, uint32_t * numerator, uint32_t * denominator)
286{
287 return avifDoubleToUnsignedFractionImpl(v, UINT32_MAX, numerator, denominator);
288}