19541344273

Committed 20 Nov 2025 03:02PM UTC coverage: 40.773% (-0.4%) from 41.21%

Build # 19541344273

Build Type

push

github

Committed by

saitoha

Commit Message

feat: initial prototyping for parallel dithering

Run Details

9711 of 33880 branches covered (28.66%)

55 of 483 new or added lines in 10 files covered. (11.39%)

12 existing lines in 4 files now uncovered.

12720 of 31197 relevant lines covered (40.77%)

656879.66 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/src/dither-varcoeff-float32.c

/*
 * SPDX-License-Identifier: MIT
 *
 * Copyright (c) 2025 libsixel developers. See `AUTHORS`.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

/*
 * Adaptive diffusion backend operating on RGBFLOAT32 buffers.  The worker
 * mirrors the 8bit implementation but keeps intermediate values in float so
 * rounding happens only at palette lookups.
 */

#include "config.h"

#include <stdlib.h>
#include <string.h>

#if HAVE_MATH_H
# include <math.h>
#endif  /* HAVE_MATH_H */

#include "dither-varcoeff-float32.h"
#include "dither-common-pipeline.h"
#include "pixelformat.h"

static void
sixel_dither_scanline_params(int serpentine,
                             int index,
                             int limit,
                             int *start,
                             int *end,
                             int *step,
                             int *direction)
{
    if (serpentine && (index & 1)) {
        *start = limit - 1;
        *end = -1;
        *step = -1;
        *direction = -1;
    } else {
        *start = 0;
        *end = limit;
        *step = 1;
        *direction = 1;
    }
}

static const int (*
lso2_table(void))[7]
{
#include "lso2.h"
    return var_coefs;
}

typedef void (*diffuse_varerr_mode_float)(float *data,
                                          int width,
                                          int height,
                                          int x,
                                          int y,
                                          int depth,
                                          float error,
                                          int index,
                                          int direction,
                                          int pixelformat,
                                          int channel);

typedef void (*diffuse_varerr_carry_mode_float)(float *carry_curr,
                                                 float *carry_next,
                                                 float *carry_far,
                                                 int width,
                                                 int height,
                                                 int depth,
                                                 int x,
                                                 int y,
                                                 float error,
                                                 int index,
                                                 int direction,
                                                 int channel);

static int
sixel_varcoeff_safe_denom(int value)
{
    if (value == 0) {
        return 1;
    }
    return value;
}

static float
diffuse_varerr_term_float(float error, int weight, int denom)
{
    float factor;

    factor = (float)weight / (float)denom;
    return error * factor;
}

static void
diffuse_varerr_apply_direct_float(float *target,
                                  int depth,
                                  size_t offset,
                                  float delta,
                                  int pixelformat,
                                  int channel)
{
    size_t index;

    index = offset * (size_t)depth;
    target[index] += delta;
    target[index] = sixel_pixelformat_float_channel_clamp(pixelformat,
                                                          channel,
                                                          target[index]);
}

static void
diffuse_lso2_float(float *data,
                    int width,
                    int height,
                    int x,
                    int y,
                    int depth,
                    float error,
                    int index,
                    int direction,
                    int pixelformat,
                    int channel)
{
    const int (*table)[7];
    const int *entry;
    int denom;
    float term_r;
    float term_r2;
    float term_dl;
    float term_d;
    float term_dr;
    float term_d2;
    size_t offset;

    if (error == 0.0f) {
        return;
    }
    if (index < 0) {
        index = 0;
    }
    if (index > 255) {
        index = 255;
    }

    table = lso2_table();
    entry = table[index];
    denom = sixel_varcoeff_safe_denom(entry[6]);

    term_r = diffuse_varerr_term_float(error, entry[0], denom);
    term_r2 = diffuse_varerr_term_float(error, entry[1], denom);
    term_dl = diffuse_varerr_term_float(error, entry[2], denom);
    term_d = diffuse_varerr_term_float(error, entry[3], denom);
    term_dr = diffuse_varerr_term_float(error, entry[4], denom);
    term_d2 = diffuse_varerr_term_float(error, entry[5], denom);

    if (direction >= 0) {
        if (x + 1 < width) {
            offset = (size_t)y * (size_t)width + (size_t)(x + 1);
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_r,
                                              pixelformat,
                                              channel);
        }
        if (x + 2 < width) {
            offset = (size_t)y * (size_t)width + (size_t)(x + 2);
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_r2,
                                              pixelformat,
                                              channel);
        }
        if (y + 1 < height && x - 1 >= 0) {
            offset = (size_t)(y + 1) * (size_t)width;
            offset += (size_t)(x - 1);
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_dl,
                                              pixelformat,
                                              channel);
        }
        if (y + 1 < height) {
            offset = (size_t)(y + 1) * (size_t)width + (size_t)x;
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_d,
                                              pixelformat,
                                              channel);
        }
        if (y + 1 < height && x + 1 < width) {
            offset = (size_t)(y + 1) * (size_t)width;
            offset += (size_t)(x + 1);
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_dr,
                                              pixelformat,
                                              channel);
        }
        if (y + 2 < height) {
            offset = (size_t)(y + 2) * (size_t)width + (size_t)x;
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_d2,
                                              pixelformat,
                                              channel);
        }
    } else {
        if (x - 1 >= 0) {
            offset = (size_t)y * (size_t)width + (size_t)(x - 1);
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_r,
                                              pixelformat,
                                              channel);
        }
        if (x - 2 >= 0) {
            offset = (size_t)y * (size_t)width + (size_t)(x - 2);
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_r2,
                                              pixelformat,
                                              channel);
        }
        if (y + 1 < height && x + 1 < width) {
            offset = (size_t)(y + 1) * (size_t)width;
            offset += (size_t)(x + 1);
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_dl,
                                              pixelformat,
                                              channel);
        }
        if (y + 1 < height) {
            offset = (size_t)(y + 1) * (size_t)width + (size_t)x;
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_d,
                                              pixelformat,
                                              channel);
        }
        if (y + 1 < height && x - 1 >= 0) {
            offset = (size_t)(y + 1) * (size_t)width;
            offset += (size_t)(x - 1);
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_dr,
                                              pixelformat,
                                              channel);
        }
        if (y + 2 < height) {
            offset = (size_t)(y + 2) * (size_t)width + (size_t)x;
            diffuse_varerr_apply_direct_float(data,
                                              depth,
                                              offset,
                                              term_d2,
                                              pixelformat,
                                              channel);
        }
    }
}

static void
diffuse_lso2_carry_float(float *carry_curr,
                          float *carry_next,
                          float *carry_far,
                          int width,
                          int height,
                          int depth,
                          int x,
                          int y,
                          float error,
                          int index,
                          int direction,
                          int channel)
{
    const int (*table)[7];
    const int *entry;
    int denom;
    float term_r;
    float term_r2;
    float term_dl;
    float term_d;
    float term_dr;
    float term_d2;
    size_t base;

    if (error == 0.0f) {
        return;
    }
    if (index < 0) {
        index = 0;
    }
    if (index > 255) {
        index = 255;
    }

    table = lso2_table();
    entry = table[index];
    denom = sixel_varcoeff_safe_denom(entry[6]);

    term_r = diffuse_varerr_term_float(error, entry[0], denom);
    term_r2 = diffuse_varerr_term_float(error, entry[1], denom);
    term_dl = diffuse_varerr_term_float(error, entry[2], denom);
    term_d = diffuse_varerr_term_float(error, entry[3], denom);
    term_dr = diffuse_varerr_term_float(error, entry[4], denom);
    term_d2 = error - term_r - term_r2 - term_dl - term_d - term_dr;

    if (direction >= 0) {
        if (x + 1 < width) {
            base = ((size_t)(x + 1) * (size_t)depth)
                 + (size_t)channel;
            carry_curr[base] += term_r;
        }
        if (x + 2 < width) {
            base = ((size_t)(x + 2) * (size_t)depth)
                 + (size_t)channel;
            carry_curr[base] += term_r2;
        }
        if (y + 1 < height && x - 1 >= 0) {
            base = ((size_t)(x - 1) * (size_t)depth)
                 + (size_t)channel;
            carry_next[base] += term_dl;
        }
        if (y + 1 < height) {
            base = ((size_t)x * (size_t)depth) + (size_t)channel;
            carry_next[base] += term_d;
        }
        if (y + 1 < height && x + 1 < width) {
            base = ((size_t)(x + 1) * (size_t)depth)
                 + (size_t)channel;
            carry_next[base] += term_dr;
        }
        if (y + 2 < height) {
            base = ((size_t)x * (size_t)depth) + (size_t)channel;
            carry_far[base] += term_d2;
        }
    } else {
        if (x - 1 >= 0) {
            base = ((size_t)(x - 1) * (size_t)depth)
                 + (size_t)channel;
            carry_curr[base] += term_r;
        }
        if (x - 2 >= 0) {
            base = ((size_t)(x - 2) * (size_t)depth)
                 + (size_t)channel;
            carry_curr[base] += term_r2;
        }
        if (y + 1 < height && x + 1 < width) {
            base = ((size_t)(x + 1) * (size_t)depth)
                 + (size_t)channel;
            carry_next[base] += term_dl;
        }
        if (y + 1 < height) {
            base = ((size_t)x * (size_t)depth) + (size_t)channel;
            carry_next[base] += term_d;
        }
        if (y + 1 < height && x - 1 >= 0) {
            base = ((size_t)(x - 1) * (size_t)depth)
                 + (size_t)channel;
            carry_next[base] += term_dr;
        }
        if (y + 2 < height) {
            base = ((size_t)x * (size_t)depth) + (size_t)channel;
            carry_far[base] += term_d2;
        }
    }
}

SIXELSTATUS
sixel_dither_apply_varcoeff_float32(sixel_dither_t *dither,
                                    sixel_dither_context_t *context)
{
#if _MSC_VER
    enum { max_channels = 4 };
#else
    const int max_channels = 4;
#endif
    SIXELSTATUS status;
    float *data;
    unsigned char *palette;
    unsigned char *new_palette;
    float *source_pixel;
    float corrected[max_channels];
    float quantized_float;
    unsigned char quantized[max_channels];
    float *carry_curr;
    float *carry_next;
    float *carry_far;
    float palette_value_float;
    unsigned char palette_value;
    float error;
    int serpentine;
    int use_carry;
    size_t carry_len;
    int method_for_diffuse;
    int method_for_carry;
    int method_for_scan;
    diffuse_varerr_mode_float varerr_diffuse;
    diffuse_varerr_carry_mode_float varerr_diffuse_carry;
    int optimize_palette;
    int y;
    int absolute_y;
    int start;
    int end;
    int step;
    int direction;
    int x;
    int pos;
    size_t base;
    size_t carry_base;
    int depth;
    int reqcolor;
    int n;
    int color_index;
    int output_index;
    int diff;
    int table_index;
    unsigned short *indextable;
    unsigned short *migration_map;
    int *ncolors;
    int (*lookup)(const unsigned char *,
                  int,
                  const unsigned char *,
                  int,
                  unsigned short *,
                  int);
    float *palette_float;
    float *new_palette_float;
    int float_depth;
    int float_index;
    float lookup_pixel_float[max_channels];
    unsigned char const *lookup_pixel;
    int lookup_wants_float;
    int use_palette_float_lookup;
    int need_float_pixel;
    int have_palette_float;
    int have_new_palette_float;

    if (dither == NULL || context == NULL) {
        return SIXEL_BAD_ARGUMENT;
    }

    status = SIXEL_BAD_ARGUMENT;
    data = context->pixels_float;
    palette = context->palette;
    new_palette = context->new_palette;
    indextable = context->indextable;
    migration_map = context->migration_map;
    ncolors = context->ncolors;
    depth = context->depth;
    reqcolor = context->reqcolor;
    lookup = context->lookup;
    optimize_palette = context->optimize_palette;
    method_for_diffuse = context->method_for_diffuse;
    method_for_carry = context->method_for_carry;
    method_for_scan = context->method_for_scan;
    palette_float = context->palette_float;
    new_palette_float = context->new_palette_float;
    float_depth = context->float_depth;
    /*
     * Track float palette availability separately for the original palette
     * and the palette-optimization buffer so later loops can skip
     * byte-to-float round-trips when computing the quantization error.
     */
    if (palette_float != NULL && float_depth >= depth) {
        have_palette_float = 1;
    } else {
        have_palette_float = 0;
    }
    if (new_palette_float != NULL && float_depth >= depth) {
        have_new_palette_float = 1;
    } else {
        have_new_palette_float = 0;
    }

    if (data == NULL || palette == NULL || context->result == NULL) {
        return SIXEL_BAD_ARGUMENT;
    }
    if (lookup == NULL) {
        return SIXEL_BAD_ARGUMENT;
    }
    if (optimize_palette) {
        if (new_palette == NULL || migration_map == NULL || ncolors == NULL) {
            return SIXEL_BAD_ARGUMENT;
        }
    } else if (ncolors == NULL) {
        return SIXEL_BAD_ARGUMENT;
    }

    if (depth <= 0 || depth > max_channels) {
        return SIXEL_BAD_ARGUMENT;
    }

    switch (method_for_diffuse) {
    case SIXEL_DIFFUSE_LSO2:
    default:
        varerr_diffuse = diffuse_lso2_float;
        varerr_diffuse_carry = diffuse_lso2_carry_float;
        break;
    }

    use_carry = (method_for_carry == SIXEL_CARRY_ENABLE);
    carry_curr = NULL;
    carry_next = NULL;
    carry_far = NULL;
    carry_len = 0;

    if (use_carry) {
        carry_len = (size_t)context->width * (size_t)depth;
        carry_curr = (float *)calloc(carry_len, sizeof(float));
        carry_next = (float *)calloc(carry_len, sizeof(float));
        carry_far = (float *)calloc(carry_len, sizeof(float));
        if (carry_curr == NULL || carry_next == NULL || carry_far == NULL) {
            goto end;
        }
    }

    serpentine = (method_for_scan == SIXEL_SCAN_SERPENTINE);
    lookup_wants_float = (context->lookup_source_is_float != 0);
    use_palette_float_lookup = 0;
    if (context->prefer_palette_float_lookup != 0
            && palette_float != NULL
            && float_depth >= depth) {
        use_palette_float_lookup = 1;
    }
    need_float_pixel = lookup_wants_float || use_palette_float_lookup;
    if (optimize_palette) {
        *ncolors = 0;
        memset(new_palette, 0x00,
               (size_t)SIXEL_PALETTE_MAX * (size_t)depth);
        if (new_palette_float != NULL && float_depth > 0) {
            memset(new_palette_float, 0x00,
                   (size_t)SIXEL_PALETTE_MAX
                       * (size_t)float_depth * sizeof(float));
        }
        memset(migration_map, 0x00,
               sizeof(unsigned short) * (size_t)SIXEL_PALETTE_MAX);
    }

    for (y = 0; y < context->height; ++y) {
        absolute_y = context->band_origin + y;
        sixel_dither_scanline_params(serpentine,
                                     absolute_y,
                                     context->width,
                                     &start,
                                     &end,
                                     &step,
                                     &direction);
        for (x = start; x != end; x += step) {
            pos = y * context->width + x;
            base = (size_t)pos * (size_t)depth;
            carry_base = (size_t)x * (size_t)depth;
            if (use_carry) {
                for (n = 0; n < depth; ++n) {
                    float accum;

                    accum = data[base + (size_t)n]
                           + carry_curr[carry_base + (size_t)n];
                    carry_curr[carry_base + (size_t)n] = 0.0f;
                    accum = sixel_pixelformat_float_channel_clamp(
                        context->pixelformat,
                        n,
                        accum);
                    corrected[n] = accum;
                }
                source_pixel = corrected;
            } else {
                source_pixel = data + base;
            }

            for (n = 0; n < depth; ++n) {
                quantized_float = source_pixel[n];
                quantized_float = sixel_pixelformat_float_channel_clamp(
                    context->pixelformat,
                    n,
                    quantized_float);
                if (source_pixel == data + base) {
                    source_pixel[n] = quantized_float;
                }
                if (need_float_pixel) {
                    lookup_pixel_float[n] = quantized_float;
                }
                if (!lookup_wants_float && !use_palette_float_lookup) {
                    quantized[n] = sixel_pixelformat_float_channel_to_byte(
                        context->pixelformat,
                        n,
                        quantized_float);
                }
            }
            if (lookup_wants_float) {
                lookup_pixel = (unsigned char const *)(void const *)
                    lookup_pixel_float;
                color_index = lookup(lookup_pixel,
                                     depth,
                                     palette,
                                     reqcolor,
                                     indextable,
                                     context->complexion);
            } else if (use_palette_float_lookup) {
                color_index = sixel_dither_lookup_palette_float32(
                    lookup_pixel_float,
                    depth,
                    palette_float,
                    reqcolor,
                    context->complexion);
            } else {
                lookup_pixel = quantized;
                color_index = lookup(lookup_pixel,
                                     depth,
                                     palette,
                                     reqcolor,
                                     indextable,
                                     context->complexion);
            }

            if (optimize_palette) {
                if (migration_map[color_index] == 0) {
                    output_index = *ncolors;
                    for (n = 0; n < depth; ++n) {
                        new_palette[output_index * depth + n]
                            = palette[color_index * depth + n];
                    }
                    if (palette_float != NULL
                            && new_palette_float != NULL
                            && float_depth > 0) {
                        for (float_index = 0;
                                float_index < float_depth;
                                ++float_index) {
                            new_palette_float[output_index * float_depth
                                              + float_index]
                                = palette_float[color_index * float_depth
                                                + float_index];
                        }
                    }
                    ++*ncolors;
                    migration_map[color_index] = *ncolors;
                } else {
                    output_index = migration_map[color_index] - 1;
                }
                if (absolute_y >= context->output_start) {
                    context->result[pos] = output_index;
                }
            } else {
                output_index = color_index;
                if (absolute_y >= context->output_start) {
                    context->result[pos] = output_index;
                }
            }

            for (n = 0; n < depth; ++n) {
                if (optimize_palette) {
                    if (have_new_palette_float) {
                        palette_value_float =
                            new_palette_float[output_index * float_depth
                                              + n];
                    } else {
                        palette_value =
                            new_palette[output_index * depth + n];
                        palette_value_float
                            = sixel_pixelformat_byte_to_float(
                                  context->pixelformat,
                                  n,
                                  palette_value);
                    }
                } else {
                    if (have_palette_float) {
                        palette_value_float =
                            palette_float[color_index * float_depth + n];
                    } else {
                        palette_value =
                            palette[color_index * depth + n];
                        palette_value_float
                            = sixel_pixelformat_byte_to_float(
                                  context->pixelformat,
                                  n,
                                  palette_value);
                    }
                }
                error = source_pixel[n] - palette_value_float;
                if (error < 0.0f) {
                    diff = (int)(-error * 255.0f + 0.5f);
                } else {
                    diff = (int)(error * 255.0f + 0.5f);
                }
                if (diff > 255) {
                    diff = 255;
                }
                table_index = diff;
                if (use_carry) {
                    varerr_diffuse_carry(carry_curr,
                                         carry_next,
                                         carry_far,
                                         context->width,
                                         context->height,
                                         depth,
                                         x,
                                         y,
                                         error,
                                         table_index,
                                         direction,
                                         n);
                } else {
                    varerr_diffuse(data + n,
                                   context->width,
                                   context->height,
                                   x,
                                   y,
                                   depth,
                                   error,
                                   table_index,
                                   direction,
                                   context->pixelformat,
                                   n);
                }
            }
        }

        if (use_carry) {
            float *tmp;

            tmp = carry_curr;
            carry_curr = carry_next;
            carry_next = carry_far;
            carry_far = tmp;
            if (carry_len > 0) {
                memset(carry_far, 0x00, carry_len * sizeof(float));
            }
        }
        if (absolute_y >= context->output_start) {
            sixel_dither_pipeline_row_notify(dither, absolute_y);
        }
    }

    if (optimize_palette) {
        memcpy(palette, new_palette, (size_t)(*ncolors * depth));
        if (palette_float != NULL
                && new_palette_float != NULL
                && float_depth > 0) {
            memcpy(palette_float,
                   new_palette_float,
                   (size_t)(*ncolors * float_depth)
                       * sizeof(float));
        }
    } else {
        *ncolors = reqcolor;
    }

    status = SIXEL_OK;

end:
    free(carry_curr);
    free(carry_next);
    free(carry_far);
    return status;
}

/* emacs Local Variables:      */
/* emacs mode: c               */
/* emacs tab-width: 4          */
/* emacs indent-tabs-mode: nil */
/* emacs c-basic-offset: 4     */
/* emacs End:                  */
/* vim: set expandtab ts=4 sts=4 sw=4 : */
/* EOF */

1	/*
2	* SPDX-License-Identifier: MIT
3	*
4	* Copyright (c) 2025 libsixel developers. See `AUTHORS`.
5	*
6	* Permission is hereby granted, free of charge, to any person obtaining a copy
7	* of this software and associated documentation files (the "Software"), to deal
8	* in the Software without restriction, including without limitation the rights
9	* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10	* copies of the Software, and to permit persons to whom the Software is
11	* furnished to do so, subject to the following conditions:
12	*
13	* The above copyright notice and this permission notice shall be included in
14	* all copies or substantial portions of the Software.
15	*
16	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19	* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21	* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22	* SOFTWARE.
23	*/
24
25	/*
26	* Adaptive diffusion backend operating on RGBFLOAT32 buffers. The worker
27	* mirrors the 8bit implementation but keeps intermediate values in float so
28	* rounding happens only at palette lookups.
29	*/
30
31	#include "config.h"
32
33	#include <stdlib.h>
34	#include <string.h>
35
36	#if HAVE_MATH_H
37	# include <math.h>
38	#endif /* HAVE_MATH_H */
39
40	#include "dither-varcoeff-float32.h"
41	#include "dither-common-pipeline.h"
42	#include "pixelformat.h"
43
44	static void
45	sixel_dither_scanline_params(int serpentine,	×
46	int index,
47	int limit,
48	int *start,
49	int *end,
50	int *step,
51	int *direction)
52	{
53	if (serpentine && (index & 1)) {	×
54	*start = limit - 1;	×
55	*end = -1;	×
56	*step = -1;	×
57	*direction = -1;	×
58	} else {
59	*start = 0;	×
60	*end = limit;	×
61	*step = 1;	×
62	*direction = 1;	×
63	}
64	}	×
65
66	static const int (*
67	lso2_table(void))[7]	×
68	{
69	#include "lso2.h"
70	return var_coefs;	×
71	}
72
73	typedef void (diffuse_varerr_mode_float)(float data,
74	int width,
75	int height,
76	int x,
77	int y,
78	int depth,
79	float error,
80	int index,
81	int direction,
82	int pixelformat,
83	int channel);
84
85	typedef void (diffuse_varerr_carry_mode_float)(float carry_curr,
86	float *carry_next,
87	float *carry_far,
88	int width,
89	int height,
90	int depth,
91	int x,
92	int y,
93	float error,
94	int index,
95	int direction,
96	int channel);
97
98	static int
99	sixel_varcoeff_safe_denom(int value)	×
100	{
101	if (value == 0) {	×
102	return 1;	×
103	}
104	return value;	×
105	}
106
107	static float
108	diffuse_varerr_term_float(float error, int weight, int denom)	×
109	{
110	float factor;
111
112	factor = (float)weight / (float)denom;	×
113	return error * factor;	×
114	}
115
116	static void
117	diffuse_varerr_apply_direct_float(float *target,	×
118	int depth,
119	size_t offset,
120	float delta,
121	int pixelformat,
122	int channel)
123	{
124	size_t index;
125
126	index = offset * (size_t)depth;	×
127	target[index] += delta;	×
128	target[index] = sixel_pixelformat_float_channel_clamp(pixelformat,	×
129	channel,
130	target[index]);	×
131	}	×
132
133	static void
134	diffuse_lso2_float(float *data,	×
135	int width,
136	int height,
137	int x,
138	int y,
139	int depth,
140	float error,
141	int index,
142	int direction,
143	int pixelformat,
144	int channel)
145	{
146	const int (*table)[7];
147	const int *entry;
148	int denom;
149	float term_r;
150	float term_r2;
151	float term_dl;
152	float term_d;
153	float term_dr;
154	float term_d2;
155	size_t offset;
156
157	if (error == 0.0f) {	×
158	return;	×
159	}
160	if (index < 0) {	×
161	index = 0;	×
162	}
163	if (index > 255) {	×
164	index = 255;	×
165	}
166
167	table = lso2_table();	×
168	entry = table[index];	×
169	denom = sixel_varcoeff_safe_denom(entry[6]);	×
170
171	term_r = diffuse_varerr_term_float(error, entry[0], denom);	×
172	term_r2 = diffuse_varerr_term_float(error, entry[1], denom);	×
173	term_dl = diffuse_varerr_term_float(error, entry[2], denom);	×
174	term_d = diffuse_varerr_term_float(error, entry[3], denom);	×
175	term_dr = diffuse_varerr_term_float(error, entry[4], denom);	×
176	term_d2 = diffuse_varerr_term_float(error, entry[5], denom);	×
177
178	if (direction >= 0) {	×
179	if (x + 1 < width) {	×
180	offset = (size_t)y * (size_t)width + (size_t)(x + 1);	×
181	diffuse_varerr_apply_direct_float(data,	×
182	depth,
183	offset,
184	term_r,
185	pixelformat,
186	channel);
187	}
188	if (x + 2 < width) {	×
189	offset = (size_t)y * (size_t)width + (size_t)(x + 2);	×
190	diffuse_varerr_apply_direct_float(data,	×
191	depth,
192	offset,
193	term_r2,
194	pixelformat,
195	channel);
196	}
197	if (y + 1 < height && x - 1 >= 0) {	×
198	offset = (size_t)(y + 1) * (size_t)width;	×
199	offset += (size_t)(x - 1);	×
200	diffuse_varerr_apply_direct_float(data,	×
201	depth,
202	offset,
203	term_dl,
204	pixelformat,
205	channel);
206	}
207	if (y + 1 < height) {	×
208	offset = (size_t)(y + 1) * (size_t)width + (size_t)x;	×
209	diffuse_varerr_apply_direct_float(data,	×
210	depth,
211	offset,
212	term_d,
213	pixelformat,
214	channel);
215	}
216	if (y + 1 < height && x + 1 < width) {	×
217	offset = (size_t)(y + 1) * (size_t)width;	×
218	offset += (size_t)(x + 1);	×
219	diffuse_varerr_apply_direct_float(data,	×
220	depth,
221	offset,
222	term_dr,
223	pixelformat,
224	channel);
225	}
226	if (y + 2 < height) {	×
227	offset = (size_t)(y + 2) * (size_t)width + (size_t)x;	×
228	diffuse_varerr_apply_direct_float(data,	×
229	depth,
230	offset,
231	term_d2,
232	pixelformat,
233	channel);
234	}
235	} else {
236	if (x - 1 >= 0) {	×
237	offset = (size_t)y * (size_t)width + (size_t)(x - 1);	×
238	diffuse_varerr_apply_direct_float(data,	×
239	depth,
240	offset,
241	term_r,
242	pixelformat,
243	channel);
244	}
245	if (x - 2 >= 0) {	×
246	offset = (size_t)y * (size_t)width + (size_t)(x - 2);	×
247	diffuse_varerr_apply_direct_float(data,	×
248	depth,
249	offset,
250	term_r2,
251	pixelformat,
252	channel);
253	}
254	if (y + 1 < height && x + 1 < width) {	×
255	offset = (size_t)(y + 1) * (size_t)width;	×
256	offset += (size_t)(x + 1);	×
257	diffuse_varerr_apply_direct_float(data,	×
258	depth,
259	offset,
260	term_dl,
261	pixelformat,
262	channel);
263	}
264	if (y + 1 < height) {	×
265	offset = (size_t)(y + 1) * (size_t)width + (size_t)x;	×
266	diffuse_varerr_apply_direct_float(data,	×
267	depth,
268	offset,
269	term_d,
270	pixelformat,
271	channel);
272	}
273	if (y + 1 < height && x - 1 >= 0) {	×
274	offset = (size_t)(y + 1) * (size_t)width;	×
275	offset += (size_t)(x - 1);	×
276	diffuse_varerr_apply_direct_float(data,	×
277	depth,
278	offset,
279	term_dr,
280	pixelformat,
281	channel);
282	}
283	if (y + 2 < height) {	×
284	offset = (size_t)(y + 2) * (size_t)width + (size_t)x;	×
285	diffuse_varerr_apply_direct_float(data,	×
286	depth,
287	offset,
288	term_d2,
289	pixelformat,
290	channel);
291	}
292	}
293	}
294
295	static void
296	diffuse_lso2_carry_float(float *carry_curr,	×
297	float *carry_next,
298	float *carry_far,
299	int width,
300	int height,
301	int depth,
302	int x,
303	int y,
304	float error,
305	int index,
306	int direction,
307	int channel)
308	{
309	const int (*table)[7];
310	const int *entry;
311	int denom;
312	float term_r;
313	float term_r2;
314	float term_dl;
315	float term_d;
316	float term_dr;
317	float term_d2;
318	size_t base;
319
320	if (error == 0.0f) {	×
321	return;	×
322	}
323	if (index < 0) {	×
324	index = 0;	×
325	}
326	if (index > 255) {	×
327	index = 255;	×
328	}
329
330	table = lso2_table();	×
331	entry = table[index];	×
332	denom = sixel_varcoeff_safe_denom(entry[6]);	×
333
334	term_r = diffuse_varerr_term_float(error, entry[0], denom);	×
335	term_r2 = diffuse_varerr_term_float(error, entry[1], denom);	×
336	term_dl = diffuse_varerr_term_float(error, entry[2], denom);	×
337	term_d = diffuse_varerr_term_float(error, entry[3], denom);	×
338	term_dr = diffuse_varerr_term_float(error, entry[4], denom);	×
339	term_d2 = error - term_r - term_r2 - term_dl - term_d - term_dr;	×
340
341	if (direction >= 0) {	×
342	if (x + 1 < width) {	×
343	base = ((size_t)(x + 1) * (size_t)depth)	×
344	+ (size_t)channel;	×
345	carry_curr[base] += term_r;	×
346	}
347	if (x + 2 < width) {	×
348	base = ((size_t)(x + 2) * (size_t)depth)	×
349	+ (size_t)channel;	×
350	carry_curr[base] += term_r2;	×
351	}
352	if (y + 1 < height && x - 1 >= 0) {	×
353	base = ((size_t)(x - 1) * (size_t)depth)	×
354	+ (size_t)channel;	×
355	carry_next[base] += term_dl;	×
356	}
357	if (y + 1 < height) {	×
358	base = ((size_t)x * (size_t)depth) + (size_t)channel;	×
359	carry_next[base] += term_d;	×
360	}
361	if (y + 1 < height && x + 1 < width) {	×
362	base = ((size_t)(x + 1) * (size_t)depth)	×
363	+ (size_t)channel;	×
364	carry_next[base] += term_dr;	×
365	}
366	if (y + 2 < height) {	×
367	base = ((size_t)x * (size_t)depth) + (size_t)channel;	×
368	carry_far[base] += term_d2;	×
369	}
370	} else {
371	if (x - 1 >= 0) {	×
372	base = ((size_t)(x - 1) * (size_t)depth)	×
373	+ (size_t)channel;	×
374	carry_curr[base] += term_r;	×
375	}
376	if (x - 2 >= 0) {	×
377	base = ((size_t)(x - 2) * (size_t)depth)	×
378	+ (size_t)channel;	×
379	carry_curr[base] += term_r2;	×
380	}
381	if (y + 1 < height && x + 1 < width) {	×
382	base = ((size_t)(x + 1) * (size_t)depth)	×
383	+ (size_t)channel;	×
384	carry_next[base] += term_dl;	×
385	}
386	if (y + 1 < height) {	×
387	base = ((size_t)x * (size_t)depth) + (size_t)channel;	×
388	carry_next[base] += term_d;	×
389	}
390	if (y + 1 < height && x - 1 >= 0) {	×
391	base = ((size_t)(x - 1) * (size_t)depth)	×
392	+ (size_t)channel;	×
393	carry_next[base] += term_dr;	×
394	}
395	if (y + 2 < height) {	×
396	base = ((size_t)x * (size_t)depth) + (size_t)channel;	×
397	carry_far[base] += term_d2;	×
398	}
399	}
400	}
401
402	SIXELSTATUS
403	sixel_dither_apply_varcoeff_float32(sixel_dither_t *dither,	×
404	sixel_dither_context_t *context)
405	{	×
406	#if _MSC_VER
407	enum { max_channels = 4 };
408	#else
409	const int max_channels = 4;	×
410	#endif
411	SIXELSTATUS status;
412	float *data;
413	unsigned char *palette;
414	unsigned char *new_palette;
415	float *source_pixel;
416	float corrected[max_channels];	×
417	float quantized_float;
418	unsigned char quantized[max_channels];	×
419	float *carry_curr;
420	float *carry_next;
421	float *carry_far;
422	float palette_value_float;
423	unsigned char palette_value;
424	float error;
425	int serpentine;
426	int use_carry;
427	size_t carry_len;
428	int method_for_diffuse;
429	int method_for_carry;
430	int method_for_scan;
431	diffuse_varerr_mode_float varerr_diffuse;
432	diffuse_varerr_carry_mode_float varerr_diffuse_carry;
433	int optimize_palette;
434	int y;
435	int absolute_y;
436	int start;
437	int end;
438	int step;
439	int direction;
440	int x;
441	int pos;
442	size_t base;
443	size_t carry_base;
444	int depth;
445	int reqcolor;
446	int n;
447	int color_index;
448	int output_index;
449	int diff;
450	int table_index;
451	unsigned short *indextable;
452	unsigned short *migration_map;
453	int *ncolors;
454	int (lookup)(const unsigned char ,
455	int,
456	const unsigned char *,
457	int,
458	unsigned short *,
459	int);
460	float *palette_float;
461	float *new_palette_float;
462	int float_depth;
463	int float_index;
464	float lookup_pixel_float[max_channels];	×
465	unsigned char const *lookup_pixel;
466	int lookup_wants_float;
467	int use_palette_float_lookup;
468	int need_float_pixel;
469	int have_palette_float;
470	int have_new_palette_float;
471
472	if (dither == NULL \|\| context == NULL) {	×
473	return SIXEL_BAD_ARGUMENT;	×
474	}
475
476	status = SIXEL_BAD_ARGUMENT;	×
477	data = context->pixels_float;	×
478	palette = context->palette;	×
479	new_palette = context->new_palette;	×
480	indextable = context->indextable;	×
481	migration_map = context->migration_map;	×
482	ncolors = context->ncolors;	×
483	depth = context->depth;	×
484	reqcolor = context->reqcolor;	×
485	lookup = context->lookup;	×
486	optimize_palette = context->optimize_palette;	×
487	method_for_diffuse = context->method_for_diffuse;	×
488	method_for_carry = context->method_for_carry;	×
489	method_for_scan = context->method_for_scan;	×
490	palette_float = context->palette_float;	×
491	new_palette_float = context->new_palette_float;	×
492	float_depth = context->float_depth;	×
493	/*
494	* Track float palette availability separately for the original palette
495	* and the palette-optimization buffer so later loops can skip
496	* byte-to-float round-trips when computing the quantization error.
497	*/
498	if (palette_float != NULL && float_depth >= depth) {	×
499	have_palette_float = 1;	×
500	} else {
501	have_palette_float = 0;	×
502	}
503	if (new_palette_float != NULL && float_depth >= depth) {	×
504	have_new_palette_float = 1;	×
505	} else {
506	have_new_palette_float = 0;	×
507	}
508
509	if (data == NULL \|\| palette == NULL \|\| context->result == NULL) {	×
510	return SIXEL_BAD_ARGUMENT;	×
511	}
512	if (lookup == NULL) {	×
513	return SIXEL_BAD_ARGUMENT;	×
514	}
515	if (optimize_palette) {	×
516	if (new_palette == NULL \|\| migration_map == NULL \|\| ncolors == NULL) {	×
517	return SIXEL_BAD_ARGUMENT;	×
518	}
519	} else if (ncolors == NULL) {	×
520	return SIXEL_BAD_ARGUMENT;	×
521	}
522
523	if (depth <= 0 \|\| depth > max_channels) {	×
524	return SIXEL_BAD_ARGUMENT;	×
525	}
526
527	switch (method_for_diffuse) {	×
528	case SIXEL_DIFFUSE_LSO2:	×
529	default:
530	varerr_diffuse = diffuse_lso2_float;	×
531	varerr_diffuse_carry = diffuse_lso2_carry_float;	×
532	break;	×
533	}
534
535	use_carry = (method_for_carry == SIXEL_CARRY_ENABLE);	×
536	carry_curr = NULL;	×
537	carry_next = NULL;	×
538	carry_far = NULL;	×
539	carry_len = 0;	×
540
541	if (use_carry) {	×
542	carry_len = (size_t)context->width * (size_t)depth;	×
543	carry_curr = (float *)calloc(carry_len, sizeof(float));	×
544	carry_next = (float *)calloc(carry_len, sizeof(float));	×
545	carry_far = (float *)calloc(carry_len, sizeof(float));	×
546	if (carry_curr == NULL \|\| carry_next == NULL \|\| carry_far == NULL) {	×
547	goto end;	×
548	}
549	}
550
551	serpentine = (method_for_scan == SIXEL_SCAN_SERPENTINE);	×
552	lookup_wants_float = (context->lookup_source_is_float != 0);	×
553	use_palette_float_lookup = 0;	×
554	if (context->prefer_palette_float_lookup != 0	×
555	&& palette_float != NULL	×
556	&& float_depth >= depth) {	×
557	use_palette_float_lookup = 1;	×
558	}
559	need_float_pixel = lookup_wants_float \|\| use_palette_float_lookup;	×
560	if (optimize_palette) {	×
561	*ncolors = 0;	×
562	memset(new_palette, 0x00,	×
563	(size_t)SIXEL_PALETTE_MAX * (size_t)depth);	×
564	if (new_palette_float != NULL && float_depth > 0) {	×
565	memset(new_palette_float, 0x00,	×
566	(size_t)SIXEL_PALETTE_MAX
567	* (size_t)float_depth * sizeof(float));	×
568	}
569	memset(migration_map, 0x00,	×
570	sizeof(unsigned short) * (size_t)SIXEL_PALETTE_MAX);
571	}
572
573	for (y = 0; y < context->height; ++y) {	×
NEW 574	absolute_y = context->band_origin + y;	×
UNCOV 575	sixel_dither_scanline_params(serpentine,	×
576	absolute_y,
577	context->width,
578	&start,
579	&end,
580	&step,
581	&direction);
582	for (x = start; x != end; x += step) {	×
583	pos = y * context->width + x;	×
584	base = (size_t)pos * (size_t)depth;	×
585	carry_base = (size_t)x * (size_t)depth;	×
586	if (use_carry) {	×
587	for (n = 0; n < depth; ++n) {	×
588	float accum;
589
590	accum = data[base + (size_t)n]	×
591	+ carry_curr[carry_base + (size_t)n];	×
592	carry_curr[carry_base + (size_t)n] = 0.0f;	×
593	accum = sixel_pixelformat_float_channel_clamp(	×
594	context->pixelformat,
595	n,
596	accum);
597	corrected[n] = accum;	×
598	}
599	source_pixel = corrected;	×
600	} else {
601	source_pixel = data + base;	×
602	}
603
604	for (n = 0; n < depth; ++n) {	×
605	quantized_float = source_pixel[n];	×
606	quantized_float = sixel_pixelformat_float_channel_clamp(	×
607	context->pixelformat,
608	n,
609	quantized_float);
610	if (source_pixel == data + base) {	×
611	source_pixel[n] = quantized_float;	×
612	}
613	if (need_float_pixel) {	×
614	lookup_pixel_float[n] = quantized_float;	×
615	}
616	if (!lookup_wants_float && !use_palette_float_lookup) {	×
617	quantized[n] = sixel_pixelformat_float_channel_to_byte(	×
618	context->pixelformat,
619	n,
620	quantized_float);
621	}
622	}
623	if (lookup_wants_float) {	×
624	lookup_pixel = (unsigned char const )(void const )	×
625	lookup_pixel_float;
626	color_index = lookup(lookup_pixel,	×
627	depth,
628	palette,
629	reqcolor,
630	indextable,
631	context->complexion);
632	} else if (use_palette_float_lookup) {	×
633	color_index = sixel_dither_lookup_palette_float32(	×
634	lookup_pixel_float,
635	depth,
636	palette_float,
637	reqcolor,
638	context->complexion);
639	} else {
640	lookup_pixel = quantized;	×
641	color_index = lookup(lookup_pixel,	×
642	depth,
643	palette,
644	reqcolor,
645	indextable,
646	context->complexion);
647	}
648
649	if (optimize_palette) {	×
650	if (migration_map[color_index] == 0) {	×
651	output_index = *ncolors;	×
652	for (n = 0; n < depth; ++n) {	×
653	new_palette[output_index * depth + n]	×
654	= palette[color_index * depth + n];	×
655	}
656	if (palette_float != NULL	×
657	&& new_palette_float != NULL	×
658	&& float_depth > 0) {	×
659	for (float_index = 0;	×
660	float_index < float_depth;	×
661	++float_index) {	×
662	new_palette_float[output_index * float_depth	×
663	+ float_index]	×
664	= palette_float[color_index * float_depth	×
665	+ float_index];	×
666	}
667	}
668	++*ncolors;	×
669	migration_map[color_index] = *ncolors;	×
670	} else {
671	output_index = migration_map[color_index] - 1;	×
672	}
NEW 673	if (absolute_y >= context->output_start) {	×
NEW 674	context->result[pos] = output_index;	×
675	}
676	} else {
677	output_index = color_index;	×
NEW 678	if (absolute_y >= context->output_start) {	×
NEW 679	context->result[pos] = output_index;	×
680	}
681	}
682
683	for (n = 0; n < depth; ++n) {	×
684	if (optimize_palette) {	×
685	if (have_new_palette_float) {	×
686	palette_value_float =	×
687	new_palette_float[output_index * float_depth	×
688	+ n];	×
689	} else {
690	palette_value =	×
691	new_palette[output_index * depth + n];	×
692	palette_value_float
693	= sixel_pixelformat_byte_to_float(	×
694	context->pixelformat,
695	n,
696	palette_value);
697	}
698	} else {
699	if (have_palette_float) {	×
700	palette_value_float =	×
701	palette_float[color_index * float_depth + n];	×
702	} else {
703	palette_value =	×
704	palette[color_index * depth + n];	×
705	palette_value_float
706	= sixel_pixelformat_byte_to_float(	×
707	context->pixelformat,
708	n,
709	palette_value);
710	}
711	}
712	error = source_pixel[n] - palette_value_float;	×
713	if (error < 0.0f) {	×
714	diff = (int)(-error * 255.0f + 0.5f);	×
715	} else {
716	diff = (int)(error * 255.0f + 0.5f);	×
717	}
718	if (diff > 255) {	×
719	diff = 255;	×
720	}
721	table_index = diff;	×
722	if (use_carry) {	×
723	varerr_diffuse_carry(carry_curr,	×
724	carry_next,
725	carry_far,
726	context->width,
727	context->height,
728	depth,
729	x,
730	y,
731	error,
732	table_index,
733	direction,
734	n);
735	} else {
736	varerr_diffuse(data + n,	×
737	context->width,
738	context->height,
739	x,
740	y,
741	depth,
742	error,
743	table_index,
744	direction,
745	context->pixelformat,
746	n);
747	}
748	}
749	}
750
751	if (use_carry) {	×
752	float *tmp;
753
754	tmp = carry_curr;	×
755	carry_curr = carry_next;	×
756	carry_next = carry_far;	×
757	carry_far = tmp;	×
758	if (carry_len > 0) {	×
759	memset(carry_far, 0x00, carry_len * sizeof(float));	×
760	}
761	}
NEW 762	if (absolute_y >= context->output_start) {	×
NEW 763	sixel_dither_pipeline_row_notify(dither, absolute_y);	×
764	}
765	}
766
767	if (optimize_palette) {	×
768	memcpy(palette, new_palette, (size_t)(ncolors depth));	×
769	if (palette_float != NULL	×
770	&& new_palette_float != NULL	×
771	&& float_depth > 0) {	×
772	memcpy(palette_float,	×
773	new_palette_float,
774	(size_t)(ncolors float_depth)	×
775	* sizeof(float));
776	}
777	} else {
778	*ncolors = reqcolor;	×
779	}
780
781	status = SIXEL_OK;	×
782
783	end:	×
784	free(carry_curr);	×
785	free(carry_next);	×
786	free(carry_far);	×
787	return status;	×
788	}
789
790	/* emacs Local Variables: */
791	/* emacs mode: c */
792	/* emacs tab-width: 4 */
793	/* emacs indent-tabs-mode: nil */
794	/* emacs c-basic-offset: 4 */
795	/* emacs End: */
796	/* vim: set expandtab ts=4 sts=4 sw=4 : */
797	/* EOF */

saitoha / libsixel / 19541344273

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous