| // Copyright 2024 Google LLC | |
| // SPDX-License-Identifier: BSD-2-Clause | |
| #include "avif/internal.h" | |
| #include <assert.h> | |
| #include <stdint.h> | |
| #include <string.h> | |
| //------------------------------------------------------------------------------ | |
| // Convenience functions | |
| avifBool avifSampleTransformExpressionIsValid(const avifSampleTransformExpression * tokens, uint32_t numInputImageItems) | |
| { | |
| uint32_t stackSize = 0; | |
| for (uint32_t t = 0; t < tokens->count; ++t) { | |
| const avifSampleTransformToken * token = &tokens->tokens[t]; | |
| AVIF_CHECK(token->type < AVIF_SAMPLE_TRANSFORM_RESERVED); | |
| if (token->type == AVIF_SAMPLE_TRANSFORM_INPUT_IMAGE_ITEM_INDEX) { | |
| // inputImageItemIndex is 1-based. | |
| AVIF_CHECK(token->inputImageItemIndex != 0); | |
| AVIF_CHECK(token->inputImageItemIndex <= numInputImageItems); | |
| } | |
| if (token->type < AVIF_SAMPLE_TRANSFORM_FIRST_UNARY_OPERATOR) { | |
| // Likely an operand. | |
| ++stackSize; | |
| } else if (token->type < AVIF_SAMPLE_TRANSFORM_FIRST_BINARY_OPERATOR) { | |
| // Likely a unary operator. | |
| AVIF_CHECK(stackSize >= 1); | |
| // Pop one and push one. | |
| } else { | |
| // Likely a binary operator. | |
| AVIF_CHECK(stackSize >= 2); | |
| --stackSize; // Pop two and push one. | |
| } | |
| } | |
| AVIF_CHECK(stackSize == 1); | |
| return AVIF_TRUE; | |
| } | |
| avifBool avifSampleTransformExpressionIsEquivalentTo(const avifSampleTransformExpression * a, const avifSampleTransformExpression * b) | |
| { | |
| if (a->count != b->count) { | |
| return AVIF_FALSE; | |
| } | |
| for (uint32_t t = 0; t < a->count; ++t) { | |
| const avifSampleTransformToken * aToken = &a->tokens[t]; | |
| const avifSampleTransformToken * bToken = &b->tokens[t]; | |
| if (aToken->type != bToken->type || (aToken->type == AVIF_SAMPLE_TRANSFORM_CONSTANT && aToken->constant != bToken->constant)) { | |
| return AVIF_FALSE; | |
| } | |
| // For AVIF_SAMPLE_TRANSFORM_INPUT_IMAGE_ITEM_INDEX, no need to compare inputImageItemIndex | |
| // because these are variables in the expression. | |
| } | |
| return AVIF_TRUE; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // Recipe to expression | |
| static avifBool avifPushConstant(avifSampleTransformExpression * expression, int32_t constant) | |
| { | |
| avifSampleTransformToken * token = (avifSampleTransformToken *)avifArrayPush(expression); | |
| if (token == NULL) { | |
| return AVIF_FALSE; | |
| } | |
| token->type = AVIF_SAMPLE_TRANSFORM_CONSTANT; | |
| token->constant = constant; | |
| return AVIF_TRUE; | |
| } | |
| static avifBool avifPushInputImageItem(avifSampleTransformExpression * expression, uint8_t inputImageItemIndex) | |
| { | |
| avifSampleTransformToken * token = (avifSampleTransformToken *)avifArrayPush(expression); | |
| if (token == NULL) { | |
| return AVIF_FALSE; | |
| } | |
| token->type = AVIF_SAMPLE_TRANSFORM_INPUT_IMAGE_ITEM_INDEX; | |
| token->inputImageItemIndex = inputImageItemIndex; | |
| return AVIF_TRUE; | |
| } | |
| static avifBool avifPushOperator(avifSampleTransformExpression * expression, avifSampleTransformTokenType operator) | |
| { | |
| avifSampleTransformToken * token = (avifSampleTransformToken *)avifArrayPush(expression); | |
| if (token == NULL) { | |
| return AVIF_FALSE; | |
| } | |
| token->type = (uint8_t)operator; | |
| return AVIF_TRUE; | |
| } | |
| avifResult avifSampleTransformRecipeToExpression(avifSampleTransformRecipe recipe, avifSampleTransformExpression * expression) | |
| { | |
| // Postfix (or Reverse Polish) notation. Brackets to highlight sub-expressions. | |
| if (recipe == AVIF_SAMPLE_TRANSFORM_BIT_DEPTH_EXTENSION_8B_8B) { | |
| // reference_count is two: two 8-bit input images. | |
| // (base_sample << 8) | hidden_sample | |
| // Note: base_sample is encoded losslessly. hidden_sample is encoded lossily or losslessly. | |
| AVIF_CHECKERR(avifArrayCreate(expression, sizeof(avifSampleTransformToken), 5), AVIF_RESULT_OUT_OF_MEMORY); | |
| { | |
| // The base image represents the 8 most significant bits of the reconstructed, bit-depth-extended output image. | |
| // Left shift the base image (which is also the primary item, or the auxiliary alpha item of the primary item) | |
| // by 8 bits. This is equivalent to multiplying by 2^8. | |
| AVIF_ASSERT_OR_RETURN(avifPushConstant(expression, 256)); | |
| AVIF_ASSERT_OR_RETURN(avifPushInputImageItem(expression, 1)); | |
| AVIF_ASSERT_OR_RETURN(avifPushOperator(expression, AVIF_SAMPLE_TRANSFORM_PRODUCT)); | |
| } | |
| { | |
| // The second image represents the 8 least significant bits of the reconstructed, bit-depth-extended output image. | |
| AVIF_ASSERT_OR_RETURN(avifPushInputImageItem(expression, 2)); | |
| } | |
| AVIF_ASSERT_OR_RETURN(avifPushOperator(expression, AVIF_SAMPLE_TRANSFORM_OR)); | |
| return AVIF_RESULT_OK; | |
| } | |
| if (recipe == AVIF_SAMPLE_TRANSFORM_BIT_DEPTH_EXTENSION_12B_4B) { | |
| // reference_count is two: one 12-bit input image and one 8-bit input image (because AV1 does not support 4-bit samples). | |
| // (base_sample << 4) | (hidden_sample >> 4) | |
| // Note: base_sample is encoded losslessly. hidden_sample is encoded lossily or losslessly. | |
| AVIF_CHECKERR(avifArrayCreate(expression, sizeof(avifSampleTransformToken), 7), AVIF_RESULT_OUT_OF_MEMORY); | |
| { | |
| // The base image represents the 12 most significant bits of the reconstructed, bit-depth-extended output image. | |
| // Left shift the base image (which is also the primary item, or the auxiliary alpha item of the primary item) | |
| // by 4 bits. This is equivalent to multiplying by 2^4. | |
| AVIF_ASSERT_OR_RETURN(avifPushConstant(expression, 16)); | |
| AVIF_ASSERT_OR_RETURN(avifPushInputImageItem(expression, 1)); | |
| AVIF_ASSERT_OR_RETURN(avifPushOperator(expression, AVIF_SAMPLE_TRANSFORM_PRODUCT)); | |
| } | |
| { | |
| // The second image represents the 4 least significant bits of the reconstructed, bit-depth-extended output image. | |
| AVIF_ASSERT_OR_RETURN(avifPushInputImageItem(expression, 2)); | |
| AVIF_ASSERT_OR_RETURN(avifPushConstant(expression, 16)); | |
| AVIF_ASSERT_OR_RETURN(avifPushOperator(expression, AVIF_SAMPLE_TRANSFORM_QUOTIENT)); | |
| } | |
| AVIF_ASSERT_OR_RETURN(avifPushOperator(expression, AVIF_SAMPLE_TRANSFORM_SUM)); | |
| return AVIF_RESULT_OK; | |
| } | |
| if (recipe == AVIF_SAMPLE_TRANSFORM_BIT_DEPTH_EXTENSION_12B_8B_OVERLAP_4B) { | |
| // reference_count is two: one 12-bit input image and one 8-bit input image. | |
| // (base_sample << 4) + hidden_sample | |
| // Note: Both base_sample and hidden_sample are encoded lossily or losslessly. hidden_sample overlaps | |
| // with base_sample by 4 bits to alleviate the loss caused by the quantization of base_sample. | |
| AVIF_CHECKERR(avifArrayCreate(expression, sizeof(avifSampleTransformToken), 7), AVIF_RESULT_OUT_OF_MEMORY); | |
| // The base image represents the 12 most significant bits of the reconstructed, bit-depth-extended output image. | |
| // Left shift the base image (which is also the primary item, or the auxiliary alpha item of the primary item) | |
| // by 4 bits. This is equivalent to multiplying by 2^4. | |
| AVIF_ASSERT_OR_RETURN(avifPushConstant(expression, 16)); | |
| AVIF_ASSERT_OR_RETURN(avifPushInputImageItem(expression, 1)); | |
| AVIF_ASSERT_OR_RETURN(avifPushOperator(expression, AVIF_SAMPLE_TRANSFORM_PRODUCT)); | |
| // The second image represents the offset to apply to the shifted base image to retrieve | |
| // the original image, with some loss due to quantization. | |
| AVIF_ASSERT_OR_RETURN(avifPushInputImageItem(expression, 2)); | |
| AVIF_ASSERT_OR_RETURN(avifPushOperator(expression, AVIF_SAMPLE_TRANSFORM_SUM)); | |
| // The second image is offset by 128 to have unsigned values to encode. | |
| // Correct that last to always work with unsigned values in the operations above. | |
| AVIF_ASSERT_OR_RETURN(avifPushConstant(expression, 128)); | |
| AVIF_ASSERT_OR_RETURN(avifPushOperator(expression, AVIF_SAMPLE_TRANSFORM_DIFFERENCE)); | |
| // Sample values are clamped to [0:1<<depth[ at that point. | |
| return AVIF_RESULT_OK; | |
| } | |
| return AVIF_RESULT_INVALID_ARGUMENT; | |
| } | |
| avifResult avifSampleTransformExpressionToRecipe(const avifSampleTransformExpression * expression, avifSampleTransformRecipe * recipe) | |
| { | |
| *recipe = AVIF_SAMPLE_TRANSFORM_NONE; | |
| const avifSampleTransformRecipe kAllRecipes[] = { AVIF_SAMPLE_TRANSFORM_BIT_DEPTH_EXTENSION_8B_8B, | |
| AVIF_SAMPLE_TRANSFORM_BIT_DEPTH_EXTENSION_12B_4B, | |
| AVIF_SAMPLE_TRANSFORM_BIT_DEPTH_EXTENSION_12B_8B_OVERLAP_4B }; | |
| for (size_t i = 0; i < sizeof(kAllRecipes) / sizeof(kAllRecipes[0]); ++i) { | |
| avifSampleTransformRecipe candidateRecipe = kAllRecipes[i]; | |
| avifSampleTransformExpression candidateExpression = { 0 }; | |
| AVIF_CHECKRES(avifSampleTransformRecipeToExpression(candidateRecipe, &candidateExpression)); | |
| const avifBool equivalence = avifSampleTransformExpressionIsEquivalentTo(expression, &candidateExpression); | |
| avifArrayDestroy(&candidateExpression); | |
| if (equivalence) { | |
| *recipe = candidateRecipe; | |
| return AVIF_RESULT_OK; | |
| } | |
| } | |
| return AVIF_RESULT_OK; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // Operators | |
| static int32_t avifSampleTransformClamp32b(int64_t value) | |
| { | |
| return value <= INT32_MIN ? INT32_MIN : value >= INT32_MAX ? INT32_MAX : (int32_t)value; | |
| } | |
| static int32_t avifSampleTransformOperation32bOneOperand(int32_t operand, uint8_t operator) | |
| { | |
| switch (operator) { | |
| case AVIF_SAMPLE_TRANSFORM_NEGATION: | |
| return avifSampleTransformClamp32b(-(int64_t)operand); | |
| case AVIF_SAMPLE_TRANSFORM_ABSOLUTE: | |
| return operand >= 0 ? operand : avifSampleTransformClamp32b(-(int64_t)operand); | |
| case AVIF_SAMPLE_TRANSFORM_NOT: | |
| return ~operand; | |
| case AVIF_SAMPLE_TRANSFORM_BSR: { | |
| if (operand <= 0) { | |
| return 0; | |
| } | |
| int32_t log2 = 0; | |
| operand >>= 1; | |
| for (; operand != 0; ++log2) { | |
| operand >>= 1; | |
| } | |
| return log2; | |
| } | |
| default: | |
| assert(AVIF_FALSE); | |
| } | |
| return 0; | |
| } | |
| static int32_t avifSampleTransformOperation32bTwoOperands(int32_t leftOperand, int32_t rightOperand, uint8_t operator) | |
| { | |
| switch (operator) { | |
| case AVIF_SAMPLE_TRANSFORM_SUM: | |
| return avifSampleTransformClamp32b((int64_t)leftOperand + rightOperand); | |
| case AVIF_SAMPLE_TRANSFORM_DIFFERENCE: | |
| return avifSampleTransformClamp32b((int64_t)leftOperand - rightOperand); | |
| case AVIF_SAMPLE_TRANSFORM_PRODUCT: | |
| return avifSampleTransformClamp32b((int64_t)leftOperand * rightOperand); | |
| case AVIF_SAMPLE_TRANSFORM_QUOTIENT: | |
| return rightOperand == 0 ? leftOperand : avifSampleTransformClamp32b((int64_t)leftOperand / rightOperand); | |
| case AVIF_SAMPLE_TRANSFORM_AND: | |
| return leftOperand & rightOperand; | |
| case AVIF_SAMPLE_TRANSFORM_OR: | |
| return leftOperand | rightOperand; | |
| case AVIF_SAMPLE_TRANSFORM_XOR: | |
| return leftOperand ^ rightOperand; | |
| case AVIF_SAMPLE_TRANSFORM_POW: { | |
| if (leftOperand == 0 || leftOperand == 1) { | |
| return leftOperand; | |
| } | |
| if (leftOperand == -1) { | |
| return (rightOperand % 2 == 0) ? 1 : -1; | |
| } | |
| if (rightOperand == 0) { | |
| return 1; | |
| } | |
| if (rightOperand == 1) { | |
| return leftOperand; | |
| } | |
| if (rightOperand < 0) { | |
| // L^R is in ]-1:1[ here, so truncating it always gives 0. | |
| return 0; | |
| } | |
| int64_t result = leftOperand; | |
| for (int32_t i = 1; i < rightOperand; ++i) { | |
| result *= leftOperand; | |
| if (result < INT32_MIN || result > INT32_MAX) { | |
| return (leftOperand > 0 || rightOperand % 2 == 0) ? INT32_MAX : INT32_MIN; | |
| } | |
| } | |
| return (int32_t)result; | |
| } | |
| case AVIF_SAMPLE_TRANSFORM_MIN: | |
| return leftOperand <= rightOperand ? leftOperand : rightOperand; | |
| case AVIF_SAMPLE_TRANSFORM_MAX: | |
| return leftOperand <= rightOperand ? rightOperand : leftOperand; | |
| default: | |
| assert(AVIF_FALSE); | |
| } | |
| return 0; | |
| } | |
| //------------------------------------------------------------------------------ | |
| // Expression | |
| AVIF_ARRAY_DECLARE(avifSampleTransformStack32b, int32_t, elements); | |
| static avifResult avifImageApplyExpression32b(avifImage * dstImage, | |
| const avifSampleTransformExpression * expression, | |
| const avifImage * inputImageItems[], | |
| avifPlanesFlags planes, | |
| int32_t * stack, | |
| uint32_t stackCapacity) | |
| { | |
| // This slow path could be avoided by recognizing the recipe thanks to avifSampleTransformExpressionToRecipe() | |
| // and having a dedicated optimized implementation for each recipe. | |
| const int32_t minValue = 0; | |
| const int32_t maxValue = (1 << dstImage->depth) - 1; | |
| const avifBool skipColor = !(planes & AVIF_PLANES_YUV); | |
| const avifBool skipAlpha = !(planes & AVIF_PLANES_A); | |
| for (int c = AVIF_CHAN_Y; c <= AVIF_CHAN_A; ++c) { | |
| const avifBool alpha = c == AVIF_CHAN_A; | |
| if ((skipColor && !alpha) || (skipAlpha && alpha)) { | |
| continue; | |
| } | |
| const uint32_t planeWidth = avifImagePlaneWidth(dstImage, c); | |
| const uint32_t planeHeight = avifImagePlaneHeight(dstImage, c); | |
| for (uint32_t y = 0; y < planeHeight; ++y) { | |
| for (uint32_t x = 0; x < planeWidth; ++x) { | |
| uint32_t stackSize = 0; | |
| for (uint32_t t = 0; t < expression->count; ++t) { | |
| const avifSampleTransformToken * token = &expression->tokens[t]; | |
| if (token->type == AVIF_SAMPLE_TRANSFORM_CONSTANT) { | |
| AVIF_ASSERT_OR_RETURN(stackSize < stackCapacity); | |
| stack[stackSize++] = token->constant; | |
| } else if (token->type == AVIF_SAMPLE_TRANSFORM_INPUT_IMAGE_ITEM_INDEX) { | |
| const avifImage * image = inputImageItems[token->inputImageItemIndex - 1]; // 1-based | |
| const uint8_t * row = avifImagePlane(image, c); | |
| AVIF_ASSERT_OR_RETURN(row != NULL); | |
| row += (size_t)avifImagePlaneRowBytes(image, c) * y; | |
| AVIF_ASSERT_OR_RETURN(stackSize < stackCapacity); | |
| stack[stackSize++] = avifImageUsesU16(image) ? ((const uint16_t *)row)[x] : row[x]; | |
| } else if (token->type == AVIF_SAMPLE_TRANSFORM_NEGATION || token->type == AVIF_SAMPLE_TRANSFORM_ABSOLUTE || | |
| token->type == AVIF_SAMPLE_TRANSFORM_NOT || token->type == AVIF_SAMPLE_TRANSFORM_BSR) { | |
| AVIF_ASSERT_OR_RETURN(stackSize >= 1); | |
| stack[stackSize - 1] = avifSampleTransformOperation32bOneOperand(stack[stackSize - 1], token->type); | |
| // Pop one and push one. | |
| } else { | |
| AVIF_ASSERT_OR_RETURN(stackSize >= 2); | |
| stack[stackSize - 2] = | |
| avifSampleTransformOperation32bTwoOperands(stack[stackSize - 2], stack[stackSize - 1], token->type); | |
| stackSize--; // Pop two and push one. | |
| } | |
| } | |
| AVIF_ASSERT_OR_RETURN(stackSize == 1); | |
| // Fit to the range defined by the PixelInformationProperty. | |
| // The limited/full range is ignored, like in other libavif encoding and decoding paths. | |
| stack[0] = AVIF_CLAMP(stack[0], minValue, maxValue); | |
| uint8_t * row = avifImagePlane(dstImage, c); | |
| AVIF_ASSERT_OR_RETURN(row != NULL); | |
| row += (size_t)avifImagePlaneRowBytes(dstImage, c) * y; | |
| if (avifImageUsesU16(dstImage)) { | |
| ((uint16_t *)row)[x] = (uint16_t)stack[0]; | |
| } else { | |
| row[x] = (uint8_t)stack[0]; | |
| } | |
| } | |
| } | |
| } | |
| return AVIF_RESULT_OK; | |
| } | |
| avifResult avifImageApplyExpression(avifImage * dstImage, | |
| avifSampleTransformBitDepth bitDepth, | |
| const avifSampleTransformExpression * expression, | |
| uint8_t numInputImageItems, | |
| const avifImage * inputImageItems[], | |
| avifPlanesFlags planes) | |
| { | |
| // Check that the expression is valid. | |
| AVIF_ASSERT_OR_RETURN(avifSampleTransformExpressionIsValid(expression, numInputImageItems)); | |
| const avifBool skipColor = !(planes & AVIF_PLANES_YUV); | |
| const avifBool skipAlpha = !(planes & AVIF_PLANES_A); | |
| for (int c = AVIF_CHAN_Y; c <= AVIF_CHAN_A; ++c) { | |
| const avifBool alpha = c == AVIF_CHAN_A; | |
| if ((skipColor && !alpha) || (skipAlpha && alpha)) { | |
| continue; | |
| } | |
| const uint32_t planeWidth = avifImagePlaneWidth(dstImage, c); | |
| const uint32_t planeHeight = avifImagePlaneHeight(dstImage, c); | |
| for (uint32_t i = 0; i < numInputImageItems; ++i) { | |
| AVIF_CHECKERR(avifImagePlaneWidth(inputImageItems[i], c) == planeWidth, AVIF_RESULT_BMFF_PARSE_FAILED); | |
| AVIF_CHECKERR(avifImagePlaneHeight(inputImageItems[i], c) == planeHeight, AVIF_RESULT_BMFF_PARSE_FAILED); | |
| } | |
| } | |
| // Then apply it. This part should not fail except for memory shortage reasons. | |
| if (bitDepth == AVIF_SAMPLE_TRANSFORM_BIT_DEPTH_32) { | |
| uint32_t stackCapacity = expression->count / 2 + 1; | |
| int32_t * stack = avifAlloc(stackCapacity * sizeof(int32_t)); | |
| AVIF_CHECKERR(stack != NULL, AVIF_RESULT_OUT_OF_MEMORY); | |
| const avifResult result = avifImageApplyExpression32b(dstImage, expression, inputImageItems, planes, stack, stackCapacity); | |
| avifFree(stack); | |
| return result; | |
| } | |
| return AVIF_RESULT_NOT_IMPLEMENTED; | |
| } | |
| avifResult avifImageApplyOperations(avifImage * dstImage, | |
| avifSampleTransformBitDepth bitDepth, | |
| uint32_t numTokens, | |
| const avifSampleTransformToken tokens[], | |
| uint8_t numInputImageItems, | |
| const avifImage * inputImageItems[], | |
| avifPlanesFlags planes) | |
| { | |
| avifSampleTransformExpression expression = { 0 }; | |
| AVIF_CHECKERR(avifArrayCreate(&expression, sizeof(avifSampleTransformToken), numTokens), AVIF_RESULT_OUT_OF_MEMORY); | |
| for (uint32_t t = 0; t < numTokens; ++t) { | |
| avifSampleTransformToken * token = (avifSampleTransformToken *)avifArrayPush(&expression); | |
| AVIF_ASSERT_OR_RETURN(token != NULL); | |
| *token = tokens[t]; | |
| } | |
| const avifResult result = avifImageApplyExpression(dstImage, bitDepth, &expression, numInputImageItems, inputImageItems, planes); | |
| avifArrayDestroy(&expression); | |
| return result; | |
| } |