Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 1 | // Copyright 2019 Joe Drago. All rights reserved. |
| 2 | // SPDX-License-Identifier: BSD-2-Clause |
| 3 | |
| 4 | #include "avif/internal.h" |
| 5 | |
Wan-Teh Chang | 1ccd438 | 2022-02-10 20:24:19 -0800 | [diff] [blame] | 6 | #include <assert.h> |
Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 7 | #include <math.h> |
| 8 | #include <string.h> |
| 9 | |
| 10 | float 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 | |
| 17 | uint16_t avifHTONS(uint16_t s) |
| 18 | { |
Vincent Rabaud | 4865c1c | 2023-12-18 11:56:56 +0100 | [diff] [blame] | 19 | uint16_t result = 0; |
Yannis Guyon | d36a3a0 | 2022-03-28 16:09:12 +0200 | [diff] [blame] | 20 | uint8_t * data = (uint8_t *)&result; |
Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 21 | data[0] = (s >> 8) & 0xff; |
| 22 | data[1] = (s >> 0) & 0xff; |
Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 23 | return result; |
| 24 | } |
| 25 | |
| 26 | uint16_t avifNTOHS(uint16_t s) |
| 27 | { |
Yannis Guyon | d36a3a0 | 2022-03-28 16:09:12 +0200 | [diff] [blame] | 28 | const uint8_t * data = (const uint8_t *)&s; |
Joe Drago | 7a9a661 | 2019-07-17 11:21:24 -0700 | [diff] [blame] | 29 | return (uint16_t)((data[1] << 0) | (data[0] << 8)); |
Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 30 | } |
| 31 | |
Yannis Guyon | 1fa47f2 | 2022-09-18 14:03:53 +0200 | [diff] [blame] | 32 | uint16_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 Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 38 | uint32_t avifHTONL(uint32_t l) |
| 39 | { |
Vincent Rabaud | 4865c1c | 2023-12-18 11:56:56 +0100 | [diff] [blame] | 40 | uint32_t result = 0; |
Yannis Guyon | d36a3a0 | 2022-03-28 16:09:12 +0200 | [diff] [blame] | 41 | uint8_t * data = (uint8_t *)&result; |
Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 42 | data[0] = (l >> 24) & 0xff; |
| 43 | data[1] = (l >> 16) & 0xff; |
| 44 | data[2] = (l >> 8) & 0xff; |
| 45 | data[3] = (l >> 0) & 0xff; |
Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 46 | return result; |
| 47 | } |
| 48 | |
| 49 | uint32_t avifNTOHL(uint32_t l) |
| 50 | { |
Yannis Guyon | d36a3a0 | 2022-03-28 16:09:12 +0200 | [diff] [blame] | 51 | const uint8_t * data = (const uint8_t *)&l; |
Joe Drago | 7a9a661 | 2019-07-17 11:21:24 -0700 | [diff] [blame] | 52 | return ((uint32_t)data[3] << 0) | ((uint32_t)data[2] << 8) | ((uint32_t)data[1] << 16) | ((uint32_t)data[0] << 24); |
Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 53 | } |
| 54 | |
Yannis Guyon | 1fa47f2 | 2022-09-18 14:03:53 +0200 | [diff] [blame] | 55 | uint32_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 Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 61 | uint64_t avifHTON64(uint64_t l) |
| 62 | { |
Vincent Rabaud | 4865c1c | 2023-12-18 11:56:56 +0100 | [diff] [blame] | 63 | uint64_t result = 0; |
Yannis Guyon | d36a3a0 | 2022-03-28 16:09:12 +0200 | [diff] [blame] | 64 | uint8_t * data = (uint8_t *)&result; |
Joe Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 65 | 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 Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 73 | return result; |
| 74 | } |
| 75 | |
| 76 | uint64_t avifNTOH64(uint64_t l) |
| 77 | { |
Yannis Guyon | d36a3a0 | 2022-03-28 16:09:12 +0200 | [diff] [blame] | 78 | const uint8_t * data = (const uint8_t *)&l; |
Joe Drago | 97b071c | 2019-07-17 14:24:56 -0700 | [diff] [blame] | 79 | 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 Drago | 444f051 | 2019-01-23 17:03:24 -0800 | [diff] [blame] | 81 | } |
Joe Drago | 05559c9 | 2019-07-17 16:33:38 -0700 | [diff] [blame] | 82 | |
| 83 | AVIF_ARRAY_DECLARE(avifArrayInternal, uint8_t, ptr); |
| 84 | |
Wan-Teh Chang | f732a4d | 2022-01-21 15:56:35 -0800 | [diff] [blame] | 85 | // On error, this function must set arr->ptr to NULL and both arr->count and arr->capacity to 0. |
| 86 | avifBool avifArrayCreate(void * arrayStruct, uint32_t elementSize, uint32_t initialCapacity) |
Joe Drago | 05559c9 | 2019-07-17 16:33:38 -0700 | [diff] [blame] | 87 | { |
| 88 | avifArrayInternal * arr = (avifArrayInternal *)arrayStruct; |
| 89 | arr->elementSize = elementSize ? elementSize : 1; |
| 90 | arr->count = 0; |
| 91 | arr->capacity = initialCapacity; |
Wan-Teh Chang | 620f491 | 2021-03-19 13:13:52 -0700 | [diff] [blame] | 92 | size_t byteCount = (size_t)arr->elementSize * arr->capacity; |
| 93 | arr->ptr = (uint8_t *)avifAlloc(byteCount); |
Wan-Teh Chang | f732a4d | 2022-01-21 15:56:35 -0800 | [diff] [blame] | 94 | if (!arr->ptr) { |
| 95 | arr->capacity = 0; |
| 96 | return AVIF_FALSE; |
| 97 | } |
Wan-Teh Chang | 620f491 | 2021-03-19 13:13:52 -0700 | [diff] [blame] | 98 | memset(arr->ptr, 0, byteCount); |
Wan-Teh Chang | f732a4d | 2022-01-21 15:56:35 -0800 | [diff] [blame] | 99 | return AVIF_TRUE; |
Joe Drago | 05559c9 | 2019-07-17 16:33:38 -0700 | [diff] [blame] | 100 | } |
| 101 | |
Yannis Guyon | 1fbea62 | 2023-10-18 20:21:33 +0200 | [diff] [blame] | 102 | void * avifArrayPush(void * arrayStruct) |
Joe Drago | 05559c9 | 2019-07-17 16:33:38 -0700 | [diff] [blame] | 103 | { |
| 104 | avifArrayInternal * arr = (avifArrayInternal *)arrayStruct; |
| 105 | if (arr->count == arr->capacity) { |
| 106 | uint8_t * oldPtr = arr->ptr; |
Wan-Teh Chang | 620f491 | 2021-03-19 13:13:52 -0700 | [diff] [blame] | 107 | size_t oldByteCount = (size_t)arr->elementSize * arr->capacity; |
| 108 | arr->ptr = (uint8_t *)avifAlloc(oldByteCount * 2); |
Yannis Guyon | 1fbea62 | 2023-10-18 20:21:33 +0200 | [diff] [blame] | 109 | if (arr->ptr == NULL) { |
| 110 | return NULL; |
| 111 | } |
Joe Drago | 05559c9 | 2019-07-17 16:33:38 -0700 | [diff] [blame] | 112 | memset(arr->ptr + oldByteCount, 0, oldByteCount); |
| 113 | memcpy(arr->ptr, oldPtr, oldByteCount); |
| 114 | arr->capacity *= 2; |
| 115 | avifFree(oldPtr); |
| 116 | } |
| 117 | ++arr->count; |
Yannis Guyon | 1fbea62 | 2023-10-18 20:21:33 +0200 | [diff] [blame] | 118 | return &arr->ptr[(arr->count - 1) * (size_t)arr->elementSize]; |
Joe Drago | 05559c9 | 2019-07-17 16:33:38 -0700 | [diff] [blame] | 119 | } |
| 120 | |
Wan-Teh Chang | f732a4d | 2022-01-21 15:56:35 -0800 | [diff] [blame] | 121 | void avifArrayPop(void * arrayStruct) |
| 122 | { |
| 123 | avifArrayInternal * arr = (avifArrayInternal *)arrayStruct; |
Wan-Teh Chang | 1ccd438 | 2022-02-10 20:24:19 -0800 | [diff] [blame] | 124 | assert(arr->count > 0); |
Wan-Teh Chang | f732a4d | 2022-01-21 15:56:35 -0800 | [diff] [blame] | 125 | --arr->count; |
Wan-Teh Chang | 1ccd438 | 2022-02-10 20:24:19 -0800 | [diff] [blame] | 126 | memset(&arr->ptr[arr->count * (size_t)arr->elementSize], 0, arr->elementSize); |
Wan-Teh Chang | f732a4d | 2022-01-21 15:56:35 -0800 | [diff] [blame] | 127 | } |
| 128 | |
Joe Drago | 05559c9 | 2019-07-17 16:33:38 -0700 | [diff] [blame] | 129 | void 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 Tong | 5d16f1f | 2023-01-21 01:23:25 +0800 | [diff] [blame] | 138 | |
| 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. |
| 141 | static 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 | |
| 157 | void 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 | |
| 166 | static avifBool overflowsInt32(int64_t x) |
| 167 | { |
| 168 | return (x < INT32_MIN) || (x > INT32_MAX); |
| 169 | } |
| 170 | |
Yuan Tong | 5d16f1f | 2023-01-21 01:23:25 +0800 | [diff] [blame] | 171 | avifBool 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 | |
| 193 | avifBool 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 | |
| 210 | avifBool 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-uc | bc6c2c5 | 2023-09-06 11:29:06 +0200 | [diff] [blame] | 226 | |
maryla-uc | bdf8349 | 2023-11-02 14:55:50 +0100 | [diff] [blame] | 227 | static avifBool avifDoubleToUnsignedFractionImpl(double v, uint32_t maxNumerator, uint32_t * numerator, uint32_t * denominator) |
maryla-uc | bc6c2c5 | 2023-09-06 11:29:06 +0200 | [diff] [blame] | 228 | { |
maryla-uc | bdf8349 | 2023-11-02 14:55:50 +0100 | [diff] [blame] | 229 | if (isnan(v) || v < 0 || v > maxNumerator) { |
maryla-uc | bc6c2c5 | 2023-09-06 11:29:06 +0200 | [diff] [blame] | 230 | return AVIF_FALSE; |
| 231 | } |
| 232 | |
maryla-uc | bdf8349 | 2023-11-02 14:55:50 +0100 | [diff] [blame] | 233 | // 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-uc | bc6c2c5 | 2023-09-06 11:29:06 +0200 | [diff] [blame] | 235 | |
| 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-uc | bdf8349 | 2023-11-02 14:55:50 +0100 | [diff] [blame] | 248 | assert(numeratorDouble <= maxNumerator); |
maryla-uc | bc6c2c5 | 2023-09-06 11:29:06 +0200 | [diff] [blame] | 249 | *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-uc | bdf8349 | 2023-11-02 14:55:50 +0100 | [diff] [blame] | 271 | |
| 272 | avifBool 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 | |
| 285 | avifBool avifDoubleToUnsignedFraction(double v, uint32_t * numerator, uint32_t * denominator) |
| 286 | { |
| 287 | return avifDoubleToUnsignedFractionImpl(v, UINT32_MAX, numerator, denominator); |
| 288 | } |