source: libcaca/trunk/cucul/dither.c @ 735

Last change on this file since 735 was 735, checked in by Sam Hocevar, 15 years ago
  • Renamed bitmap.c into dither.c.
  • Property svn:keywords set to Id
File size: 35.4 KB
Line 
1/*
2 *  libcucul      Canvas for ultrafast compositing of Unicode letters
3 *  Copyright (c) 2002-2006 Sam Hocevar <sam@zoy.org>
4 *                All Rights Reserved
5 *
6 *  This library is free software; you can redistribute it and/or
7 *  modify it under the terms of the Do What The Fuck You Want To
8 *  Public License, Version 2, as published by Sam Hocevar. See
9 *  http://sam.zoy.org/wtfpl/COPYING for more details.
10 */
11
12/** \file dither.c
13 *  \version \$Id: dither.c 735 2006-04-10 20:24:12Z sam $
14 *  \author Sam Hocevar <sam@zoy.org>
15 *  \brief Bitmap blitting
16 *
17 *  This file contains bitmap dithering functions.
18 */
19
20#include "config.h"
21
22#if !defined(__KERNEL__)
23#   if defined(HAVE_ENDIAN_H)
24#       include <endian.h>
25#   endif
26#   include <stdio.h>
27#   include <stdlib.h>
28#   include <limits.h>
29#   include <string.h>
30#endif
31
32#include "cucul.h"
33#include "cucul_internals.h"
34
35#define CP437 0
36
37/*
38 * Local variables
39 */
40#if !defined(_DOXYGEN_SKIP_ME)
41#   define LOOKUP_VAL 32
42#   define LOOKUP_SAT 32
43#   define LOOKUP_HUE 16
44#endif
45static unsigned char hsv_distances[LOOKUP_VAL][LOOKUP_SAT][LOOKUP_HUE];
46static uint16_t lookup_colors[8];
47
48static int const hsv_palette[] =
49{
50    /* weight, hue, saturation, value */
51    4,    0x0,    0x0,    0x0,   /* black */
52    5,    0x0,    0x0,    0x5ff, /* 30% */
53    5,    0x0,    0x0,    0x9ff, /* 70% */
54    4,    0x0,    0x0,    0xfff, /* white */
55    3,    0x1000, 0xfff,  0x5ff, /* dark yellow */
56    2,    0x1000, 0xfff,  0xfff, /* light yellow */
57    3,    0x0,    0xfff,  0x5ff, /* dark red */
58    2,    0x0,    0xfff,  0xfff  /* light red */
59};
60
61/* RGB palette for the new colour picker */
62static int const rgb_palette[] =
63{
64    0x0,   0x0,   0x0,
65    0x0,   0x0,   0x7ff,
66    0x0,   0x7ff, 0x0,
67    0x0,   0x7ff, 0x7ff,
68    0x7ff, 0x0,   0x0,
69    0x7ff, 0x0,   0x7ff,
70    0x7ff, 0x7ff, 0x0,
71    0xaaa, 0xaaa, 0xaaa,
72    0x555, 0x555, 0x555,
73    0x000, 0x000, 0xfff,
74    0x000, 0xfff, 0x000,
75    0x000, 0xfff, 0xfff,
76    0xfff, 0x000, 0x000,
77    0xfff, 0x000, 0xfff,
78    0xfff, 0xfff, 0x000,
79    0xfff, 0xfff, 0xfff,
80};
81
82static int const rgb_weight[] =
83{
84    //2, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2
85    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
86};
87
88/* List of glyphs */
89static char const * ascii_glyphs[] =
90{
91    " ", ".", ":", ";", "t", "%", "S", "X", "@", "8", "?"
92};
93
94static char const * shades_glyphs[] =
95{
96    " ", ":", "░", "▒", "?"
97};
98
99static char const * blocks_glyphs[] =
100{
101    " ", "▘", "▚", "?"
102};
103
104#if !defined(_DOXYGEN_SKIP_ME)
105enum color_mode
106{
107    COLOR_MODE_MONO,
108    COLOR_MODE_GRAY,
109    COLOR_MODE_8,
110    COLOR_MODE_16,
111    COLOR_MODE_FULLGRAY,
112    COLOR_MODE_FULL8,
113    COLOR_MODE_FULL16,
114};
115
116struct cucul_dither
117{
118    int bpp, has_palette, has_alpha;
119    int w, h, pitch;
120    int rmask, gmask, bmask, amask;
121    int rright, gright, bright, aright;
122    int rleft, gleft, bleft, aleft;
123    void (*get_hsv)(struct cucul_dither *, char *, int, int);
124    int red[256], green[256], blue[256], alpha[256];
125    float gamma;
126    int gammatab[4097];
127
128    /* Bitmap features */
129    int invert, antialias;
130
131    /* Colour mode used for rendering */
132    enum color_mode color_mode;
133
134    /* Glyphs used for rendering */
135    char const * const * glyphs;
136    unsigned glyph_count;
137
138    /* Current dithering method */
139    void (*init_dither) (int);
140    unsigned int (*get_dither) (void);
141    void (*increment_dither) (void);
142};
143
144#define HSV_XRATIO 6
145#define HSV_YRATIO 3
146#define HSV_HRATIO 3
147
148#define HSV_DISTANCE(h, s, v, index) \
149    (hsv_palette[index * 4] \
150     * ((HSV_XRATIO * ((v) - hsv_palette[index * 4 + 3]) \
151                    * ((v) - hsv_palette[index * 4 + 3])) \
152       + (hsv_palette[index * 4 + 3] \
153           ? (HSV_YRATIO * ((s) - hsv_palette[index * 4 + 2]) \
154                         * ((s) - hsv_palette[index * 4 + 2])) \
155           : 0) \
156       + (hsv_palette[index * 4 + 2] \
157           ? (HSV_HRATIO * ((h) - hsv_palette[index * 4 + 1]) \
158                         * ((h) - hsv_palette[index * 4 + 1])) \
159           : 0)))
160#endif
161
162/*
163 * Local prototypes
164 */
165static void mask2shift(unsigned int, int *, int *);
166static float gammapow(float x, float y);
167
168static void get_rgba_default(struct cucul_dither const *, uint8_t *, int, int,
169                             unsigned int *);
170
171/* Dithering methods */
172static void init_no_dither(int);
173static unsigned int get_no_dither(void);
174static void increment_no_dither(void);
175
176static void init_fstein_dither(int);
177static unsigned int get_fstein_dither(void);
178static void increment_fstein_dither(void);
179
180static void init_ordered2_dither(int);
181static unsigned int get_ordered2_dither(void);
182static void increment_ordered2_dither(void);
183
184static void init_ordered4_dither(int);
185static unsigned int get_ordered4_dither(void);
186static void increment_ordered4_dither(void);
187
188static void init_ordered8_dither(int);
189static unsigned int get_ordered8_dither(void);
190static void increment_ordered8_dither(void);
191
192static void init_random_dither(int);
193static unsigned int get_random_dither(void);
194static void increment_random_dither(void);
195
196static inline int sq(int x)
197{
198    return x * x;
199}
200
201static inline void rgb2hsv_default(int r, int g, int b,
202                                   int *hue, int *sat, int *val)
203{
204    int min, max, delta;
205
206    min = r; max = r;
207    if(min > g) min = g; if(max < g) max = g;
208    if(min > b) min = b; if(max < b) max = b;
209
210    delta = max - min; /* 0 - 0xfff */
211    *val = max; /* 0 - 0xfff */
212
213    if(delta)
214    {
215        *sat = 0xfff * delta / max; /* 0 - 0xfff */
216
217        /* Generate *hue between 0 and 0x5fff */
218        if( r == max )
219            *hue = 0x1000 + 0x1000 * (g - b) / delta;
220        else if( g == max )
221            *hue = 0x3000 + 0x1000 * (b - r) / delta;
222        else
223            *hue = 0x5000 + 0x1000 * (r - g) / delta;
224    }
225    else
226    {
227        *sat = 0;
228        *hue = 0;
229    }
230}
231
232/**
233 * \brief Create an internal dither object.
234 *
235 * Create a dither structure from its coordinates (depth, width, height and
236 * pitch) and pixel mask values. If the depth is 8 bits per pixel, the mask
237 * values are ignored and the colour palette should be set using the
238 * cucul_set_dither_palette() function. For depths greater than 8 bits per
239 * pixel, a zero alpha mask causes the alpha values to be ignored.
240 *
241 * \param bpp Bitmap depth in bits per pixel.
242 * \param w Bitmap width in pixels.
243 * \param h Bitmap height in pixels.
244 * \param pitch Bitmap pitch in bytes.
245 * \param rmask Bitmask for red values.
246 * \param gmask Bitmask for green values.
247 * \param bmask Bitmask for blue values.
248 * \param amask Bitmask for alpha values.
249 * \return Dither object, or NULL upon error.
250 */
251struct cucul_dither *cucul_create_dither(unsigned int bpp, unsigned int w,
252                                         unsigned int h, unsigned int pitch,
253                                         unsigned int rmask, unsigned int gmask,
254                                         unsigned int bmask, unsigned int amask)
255{
256    struct cucul_dither *d;
257    int i;
258
259    /* Minor sanity test */
260    if(!w || !h || !pitch || bpp > 32 || bpp < 8)
261        return NULL;
262
263    d = malloc(sizeof(struct cucul_dither));
264    if(!d)
265        return NULL;
266
267    d->bpp = bpp;
268    d->has_palette = 0;
269    d->has_alpha = amask ? 1 : 0;
270
271    d->w = w;
272    d->h = h;
273    d->pitch = pitch;
274
275    d->rmask = rmask;
276    d->gmask = gmask;
277    d->bmask = bmask;
278    d->amask = amask;
279
280    /* Load bitmasks */
281    if(rmask || gmask || bmask || amask)
282    {
283        mask2shift(rmask, &d->rright, &d->rleft);
284        mask2shift(gmask, &d->gright, &d->gleft);
285        mask2shift(bmask, &d->bright, &d->bleft);
286        mask2shift(amask, &d->aright, &d->aleft);
287    }
288
289    /* In 8 bpp mode, default to a grayscale palette */
290    if(bpp == 8)
291    {
292        d->has_palette = 1;
293        d->has_alpha = 0;
294        for(i = 0; i < 256; i++)
295        {
296            d->red[i] = i * 0xfff / 256;
297            d->green[i] = i * 0xfff / 256;
298            d->blue[i] = i * 0xfff / 256;
299        }
300    }
301
302    /* Default features */
303    d->invert = 0;
304    d->antialias = 1;
305
306    /* Default gamma value */
307    for(i = 0; i < 4096; i++)
308        d->gammatab[i] = i;
309
310    /* Default colour mode */
311    d->color_mode = COLOR_MODE_FULL16;
312
313    /* Default character set */
314    d->glyphs = ascii_glyphs;
315    d->glyph_count = sizeof(ascii_glyphs) / sizeof(*ascii_glyphs);
316
317    /* Default dithering mode */
318    d->init_dither = init_fstein_dither;
319    d->get_dither = get_fstein_dither;
320    d->increment_dither = increment_fstein_dither;
321
322    return d;
323}
324
325/**
326 * \brief Set the palette of an 8bpp dither object.
327 *
328 * Set the palette of an 8 bits per pixel bitmap. Values should be between
329 * 0 and 4095 (0xfff).
330 *
331 * \param dither Dither object.
332 * \param red Array of 256 red values.
333 * \param green Array of 256 green values.
334 * \param blue Array of 256 blue values.
335 * \param alpha Array of 256 alpha values.
336 */
337void cucul_set_dither_palette(struct cucul_dither *d,
338                              unsigned int red[], unsigned int green[],
339                              unsigned int blue[], unsigned int alpha[])
340{
341    int i, has_alpha = 0;
342
343    if(d->bpp != 8)
344        return;
345
346    for(i = 0; i < 256; i++)
347    {
348        if(red[i] >= 0 && red[i] < 0x1000 &&
349           green[i] >= 0 && green[i] < 0x1000 &&
350           blue[i] >= 0 && blue[i] < 0x1000 &&
351           alpha[i] >= 0 && alpha[i] < 0x1000)
352        {
353            d->red[i] = red[i];
354            d->green[i] = green[i];
355            d->blue[i] = blue[i];
356            if(alpha[i])
357            {
358                d->alpha[i] = alpha[i];
359                has_alpha = 1;
360            }
361        }
362    }
363
364    d->has_alpha = has_alpha;
365}
366
367/**
368 * \brief Set the brightness of a dither object.
369 *
370 * Set the brightness of dither.
371 *
372 * \param dither Dither object.
373 * \param brightness brightness value.
374 */
375void cucul_set_dither_brightness(struct cucul_dither *d, float brightness)
376{
377    /* FIXME */
378}
379
380/**
381 * \brief Set the gamma of a dither object.
382 *
383 * Set the gamma of dither.
384 *
385 * \param dither Dither object.
386 * \param gamma Gamma value.
387 */
388void cucul_set_dither_gamma(struct cucul_dither *d, float gamma)
389{
390    /* FIXME: we don't need 4096 calls to gammapow(), we can just compute
391     * 128 of them and do linear interpolation for the rest. This will
392     * probably speed up things a lot. */
393    int i;
394
395    if(gamma <= 0.0)
396        return;
397
398    d->gamma = gamma;
399
400    for(i = 0; i < 4096; i++)
401        d->gammatab[i] = 4096.0 * gammapow((float)i / 4096.0, 1.0 / gamma);
402}
403
404/**
405 * \brief Invert colors of dither
406 *
407 * Invert colors of dither
408 *
409 * \param dither Dither object.
410 * \param value 0 for normal behaviour, 1 for invert
411 */
412void cucul_set_dither_invert(struct cucul_dither *d, int value)
413{
414    d->invert = value ? 1 : 0;
415}
416
417/**
418 * \brief Set the contrast of a dither object.
419 *
420 * Set the contrast of dither.
421 *
422 * \param dither Dither object.
423 * \param contrast contrast value.
424 */
425void cucul_set_dither_contrast(struct cucul_dither *d, float contrast)
426{
427    /* FIXME */
428}
429
430/**
431 * \brief Set dither antialiasing
432 *
433 * Tell the renderer whether to antialias the dither. Antialiasing smoothen
434 * the rendered image and avoids the commonly seen staircase effect.
435 *
436 * \li \e "none": no antialiasing.
437 *
438 * \li \e "prefilter": simple prefilter antialiasing. This is the default
439 *     value.
440 *
441 * \param dither Dither object.
442 * \param str A string describing the antialiasing method that will be used
443 *        for the dithering.
444 */
445void cucul_set_dither_antialias(struct cucul_dither *d, char const *str)
446{
447    if(!strcasecmp(str, "none"))
448        d->antialias = 0;
449    else /* "prefilter" is the default */
450        d->antialias = 1;
451}
452
453/**
454 * \brief Get available antialiasing methods
455 *
456 * Return a list of available antialiasing methods for a given dither. The
457 * list is a NULL-terminated array of strings, interleaving a string
458 * containing the internal value for the antialiasing method to be used with
459 * \e cucul_set_dither_antialias(), and a string containing the natural
460 * language description for that antialiasing method.
461 *
462 * \param dither Dither object.
463 * \return An array of strings.
464 */
465char const * const *
466    cucul_get_dither_antialias_list(struct cucul_dither const *d)
467{
468    static char const * const list[] =
469    {
470        "none", "No antialiasing",
471        "prefilter", "Prefilter antialiasing",
472        NULL, NULL
473    };
474
475    return list;
476}
477
478/**
479 * \brief Choose colours used for dithering
480 *
481 * Tell the renderer which colours should be used to render the
482 * bitmap. Valid values for \e str are:
483 *
484 * \li \e "mono": use light gray on a black background.
485 *
486 * \li \e "gray": use white and two shades of gray on a black background.
487 *
488 * \li \e "8": use the 8 ANSI colours on a black background.
489 *
490 * \li \e "16": use the 16 ANSI colours on a black background.
491 *
492 * \li \e "fullgray": use black, white and two shades of gray for both the
493 *     characters and the background.
494 *
495 * \li \e "full8": use the 8 ANSI colours for both the characters and the
496 *     background.
497 *
498 * \li \e "full16": use the 16 ANSI colours for both the characters and the
499 *     background. This is the default value.
500 *
501 * \param dither Dither object.
502 * \param str A string describing the colour set that will be used
503 *        for the dithering.
504 */
505void cucul_set_dither_color(struct cucul_dither *d, char const *str)
506{
507    if(!strcasecmp(str, "mono"))
508        d->color_mode = COLOR_MODE_MONO;
509    else if(!strcasecmp(str, "gray"))
510        d->color_mode = COLOR_MODE_GRAY;
511    else if(!strcasecmp(str, "8"))
512        d->color_mode = COLOR_MODE_8;
513    else if(!strcasecmp(str, "16"))
514        d->color_mode = COLOR_MODE_16;
515    else if(!strcasecmp(str, "fullgray"))
516        d->color_mode = COLOR_MODE_FULLGRAY;
517    else if(!strcasecmp(str, "full8"))
518        d->color_mode = COLOR_MODE_FULL8;
519    else /* "full16" is the default */
520        d->color_mode = COLOR_MODE_FULL16;
521}
522
523/**
524 * \brief Get available colour modes
525 *
526 * Return a list of available colour modes for a given dither. The list
527 * is a NULL-terminated array of strings, interleaving a string containing
528 * the internal value for the colour mode, to be used with
529 * \e cucul_set_dither_color(), and a string containing the natural
530 * language description for that colour mode.
531 *
532 * \param dither Dither object.
533 * \return An array of strings.
534 */
535char const * const *
536    cucul_get_dither_color_list(struct cucul_dither const *d)
537{
538    static char const * const list[] =
539    {
540        "mono", "white on black",
541        "gray", "grayscale on black",
542        "8", "8 colours on black",
543        "16", "16 colours on black",
544        "fullgray", "full grayscale",
545        "full8", "full 8 colours",
546        "full16", "full 16 colours",
547        NULL, NULL
548    };
549
550    return list;
551}
552
553/**
554 * \brief Choose characters used for dithering
555 *
556 * Tell the renderer which characters should be used to render the
557 * dither. Valid values for \e str are:
558 *
559 * \li \e "ascii": use only ASCII characters. This is the default value.
560 *
561 * \li \e "shades": use Unicode characters "U+2591 LIGHT SHADE", "U+2592
562 *     MEDIUM SHADE" and "U+2593 DARK SHADE". These characters are also
563 *     present in the CP437 codepage available on DOS and VGA.
564 *
565 * \li \e "blocks": use Unicode quarter-cell block combinations. These
566 *     characters are only found in the Unicode set.
567 *
568 * \param dither Dither object.
569 * \param str A string describing the characters that need to be used
570 *        for the dithering.
571 */
572void cucul_set_dither_charset(struct cucul_dither *d, char const *str)
573{
574    if(!strcasecmp(str, "shades"))
575    {
576        d->glyphs = shades_glyphs;
577        d->glyph_count = sizeof(shades_glyphs) / sizeof(*shades_glyphs);
578    }
579    else if(!strcasecmp(str, "blocks"))
580    {
581        d->glyphs = blocks_glyphs;
582        d->glyph_count = sizeof(blocks_glyphs) / sizeof(*blocks_glyphs);
583    }
584    else /* "ascii" is the default */
585    {
586        d->glyphs = ascii_glyphs;
587        d->glyph_count = sizeof(ascii_glyphs) / sizeof(*ascii_glyphs);
588    }
589}
590
591/**
592 * \brief Get available dither character sets
593 *
594 * Return a list of available character sets for a given dither. The list
595 * is a NULL-terminated array of strings, interleaving a string containing
596 * the internal value for the character set, to be used with
597 * \e cucul_set_dither_charset(), and a string containing the natural
598 * language description for that character set.
599 *
600 * \param dither Dither object.
601 * \return An array of strings.
602 */
603char const * const *
604    cucul_get_dither_charset_list(struct cucul_dither const *d)
605{
606    static char const * const list[] =
607    {
608        "ascii", "plain ASCII",
609        "shades", "CP437 shades",
610        "blocks", "Unicode blocks",
611        NULL, NULL
612    };
613
614    return list;
615}
616
617/**
618 * \brief Set dithering method
619 *
620 * Tell the renderer which dithering method should be used. Dithering is
621 * necessary because the picture being rendered has usually far more colours
622 * than the available palette. Valid values for \e str are:
623 *
624 * \li \e "none": no dithering is used, the nearest matching colour is used.
625 *
626 * \li \e "ordered2": use a 2x2 Bayer matrix for dithering.
627 *
628 * \li \e "ordered4": use a 4x4 Bayer matrix for dithering.
629 *
630 * \li \e "ordered8": use a 8x8 Bayer matrix for dithering.
631 *
632 * \li \e "random": use random dithering.
633 *
634 * \li \e "fstein": use Floyd-Steinberg dithering. This is the default value.
635 *
636 * \param dither Dither object.
637 * \param str A string describing the method that needs to be used
638 *        for the dithering.
639 */
640void cucul_set_dither_mode(struct cucul_dither *d, char const *str)
641{
642    if(!strcasecmp(str, "none"))
643    {
644        d->init_dither = init_no_dither;
645        d->get_dither = get_no_dither;
646        d->increment_dither = increment_no_dither;
647    }
648    else if(!strcasecmp(str, "ordered2"))
649    {
650        d->init_dither = init_ordered2_dither;
651        d->get_dither = get_ordered2_dither;
652        d->increment_dither = increment_ordered2_dither;
653    }
654    else if(!strcasecmp(str, "ordered4"))
655    {
656        d->init_dither = init_ordered4_dither;
657        d->get_dither = get_ordered4_dither;
658        d->increment_dither = increment_ordered4_dither;
659    }
660    else if(!strcasecmp(str, "ordered4"))
661    {
662        d->init_dither = init_ordered8_dither;
663        d->get_dither = get_ordered8_dither;
664        d->increment_dither = increment_ordered8_dither;
665    }
666    else if(!strcasecmp(str, "random"))
667    {
668        d->init_dither = init_random_dither;
669        d->get_dither = get_random_dither;
670        d->increment_dither = increment_random_dither;
671    }
672    else /* "fstein" is the default */
673    {
674        d->init_dither = init_fstein_dither;
675        d->get_dither = get_fstein_dither;
676        d->increment_dither = increment_fstein_dither;
677    }
678}
679
680/**
681 * \brief Get dithering methods
682 *
683 * Return a list of available dithering methods for a given dither. The list
684 * is a NULL-terminated array of strings, interleaving a string containing
685 * the internal value for the dithering method, to be used with
686 * \e cucul_set_dither_dithering(), and a string containing the natural
687 * language description for that dithering method.
688 *
689 * \param dither Dither object.
690 * \return An array of strings.
691 */
692char const * const *
693    cucul_get_dither_mode_list(struct cucul_dither const *d)
694{
695    static char const * const list[] =
696    {
697        "none", "no dithering",
698        "ordered2", "2x2 ordered dithering",
699        "ordered2", "2x2 ordered dithering",
700        "ordered2", "2x2 ordered dithering",
701        "random", "random dithering",
702        "fstein", "Floyd-Steinberg dithering",
703        NULL, NULL
704    };
705
706    return list;
707}
708
709/**
710 * \brief Draw a dither on the screen.
711 *
712 * Draw a dither at the given coordinates. The dither can be of any size and
713 * will be stretched to the text area.
714 *
715 * \param x1 X coordinate of the upper-left corner of the drawing area.
716 * \param y1 Y coordinate of the upper-left corner of the drawing area.
717 * \param x2 X coordinate of the lower-right corner of the drawing area.
718 * \param y2 Y coordinate of the lower-right corner of the drawing area.
719 * \param dither Dither object to be drawn.
720 * \param pixels Bitmap's pixels.
721 */
722void cucul_dither_bitmap(cucul_t *qq, int x1, int y1, int x2, int y2,
723                         struct cucul_dither const *d, void *pixels)
724{
725    int *floyd_steinberg, *fs_r, *fs_g, *fs_b;
726    int fs_length;
727    int x, y, w, h, pitch, deltax, deltay;
728    unsigned int dchmax;
729
730    if(!d || !pixels)
731        return;
732
733    w = d->w;
734    h = d->h;
735    pitch = d->pitch;
736
737    if(x1 > x2)
738    {
739        int tmp = x2; x2 = x1; x1 = tmp;
740    }
741
742    if(y1 > y2)
743    {
744        int tmp = y2; y2 = y1; y1 = tmp;
745    }
746
747    deltax = x2 - x1 + 1;
748    deltay = y2 - y1 + 1;
749    dchmax = d->glyph_count;
750
751    fs_length = ((int)qq->width <= x2 ? (int)qq->width : x2) + 1;
752    floyd_steinberg = malloc(3 * (fs_length + 2) * sizeof(int));
753    memset(floyd_steinberg, 0, 3 * (fs_length + 2) * sizeof(int));
754    fs_r = floyd_steinberg + 1;
755    fs_g = fs_r + fs_length + 2;
756    fs_b = fs_g + fs_length + 2;
757
758    for(y = y1 > 0 ? y1 : 0; y <= y2 && y <= (int)qq->height; y++)
759    {
760        int remain_r = 0, remain_g = 0, remain_b = 0;
761
762        for(x = x1 > 0 ? x1 : 0, d->init_dither(y);
763            x <= x2 && x <= (int)qq->width;
764            x++)
765    {
766        unsigned int i;
767        int ch = 0, distmin;
768        unsigned int rgba[4];
769        int fg_r = 0, fg_g = 0, fg_b = 0, bg_r, bg_g, bg_b;
770        int fromx, fromy, tox, toy, myx, myy, dots, dist;
771        int error[3];
772
773        unsigned int outfg = 0, outbg = 0;
774        char const *outch;
775
776        rgba[0] = rgba[1] = rgba[2] = rgba[3] = 0;
777
778        /* First get RGB */
779        if(d->antialias)
780        {
781            fromx = (x - x1) * w / deltax;
782            fromy = (y - y1) * h / deltay;
783            tox = (x - x1 + 1) * w / deltax;
784            toy = (y - y1 + 1) * h / deltay;
785
786            /* We want at least one pixel */
787            if(tox == fromx) tox++;
788            if(toy == fromy) toy++;
789
790            dots = 0;
791
792            for(myx = fromx; myx < tox; myx++)
793                for(myy = fromy; myy < toy; myy++)
794            {
795                dots++;
796                get_rgba_default(d, pixels, myx, myy, rgba);
797            }
798
799            /* Normalize */
800            rgba[0] /= dots;
801            rgba[1] /= dots;
802            rgba[2] /= dots;
803            rgba[3] /= dots;
804        }
805        else
806        {
807            fromx = (x - x1) * w / deltax;
808            fromy = (y - y1) * h / deltay;
809            tox = (x - x1 + 1) * w / deltax;
810            toy = (y - y1 + 1) * h / deltay;
811
812            /* tox and toy can overflow the screen, but they cannot overflow
813             * when averaged with fromx and fromy because these are guaranteed
814             * to be within the pixel boundaries. */
815            myx = (fromx + tox) / 2;
816            myy = (fromy + toy) / 2;
817
818            get_rgba_default(d, pixels, myx, myy, rgba);
819        }
820
821        if(d->has_alpha && rgba[3] < 0x800)
822        {
823            remain_r = remain_g = remain_b = 0;
824            fs_r[x] = 0;
825            fs_g[x] = 0;
826            fs_b[x] = 0;
827            continue;
828        }
829
830        /* XXX: OMG HAX */
831        if(d->init_dither == init_fstein_dither)
832        {
833            rgba[0] += remain_r;
834            rgba[1] += remain_g;
835            rgba[2] += remain_b;
836        }
837        else
838        {
839            rgba[0] += (d->get_dither() - 0x80) * 4;
840            rgba[1] += (d->get_dither() - 0x80) * 4;
841            rgba[2] += (d->get_dither() - 0x80) * 4;
842        }
843
844        distmin = INT_MAX;
845        for(i = 0; i < 16; i++)
846        {
847            dist = sq(rgba[0] - rgb_palette[i * 3])
848                 + sq(rgba[1] - rgb_palette[i * 3 + 1])
849                 + sq(rgba[2] - rgb_palette[i * 3 + 2]);
850            dist *= rgb_weight[i];
851            if(dist < distmin)
852            {
853                outbg = i;
854                distmin = dist;
855            }
856        }
857        bg_r = rgb_palette[outbg * 3];
858        bg_g = rgb_palette[outbg * 3 + 1];
859        bg_b = rgb_palette[outbg * 3 + 2];
860
861        /* FIXME: we currently only honour "full16" */
862        if(d->color_mode == COLOR_MODE_FULL16)
863        {
864            distmin = INT_MAX;
865            for(i = 0; i < 16; i++)
866            {
867                if(i == outbg)
868                    continue;
869                dist = sq(rgba[0] - rgb_palette[i * 3])
870                     + sq(rgba[1] - rgb_palette[i * 3 + 1])
871                     + sq(rgba[2] - rgb_palette[i * 3 + 2]);
872                dist *= rgb_weight[i];
873                if(dist < distmin)
874                {
875                    outfg = i;
876                    distmin = dist;
877                }
878            }
879            fg_r = rgb_palette[outfg * 3];
880            fg_g = rgb_palette[outfg * 3 + 1];
881            fg_b = rgb_palette[outfg * 3 + 2];
882
883            distmin = INT_MAX;
884            for(i = 0; i < dchmax - 1; i++)
885            {
886                int newr = i * fg_r + ((2*dchmax-1) - i) * bg_r;
887                int newg = i * fg_g + ((2*dchmax-1) - i) * bg_g;
888                int newb = i * fg_b + ((2*dchmax-1) - i) * bg_b;
889                dist = abs(rgba[0] * (2*dchmax-1) - newr)
890                     + abs(rgba[1] * (2*dchmax-1) - newg)
891                     + abs(rgba[2] * (2*dchmax-1) - newb);
892
893                if(dist < distmin)
894                {
895                    ch = i;
896                    distmin = dist;
897                }
898            }
899            outch = d->glyphs[ch];
900
901            /* XXX: OMG HAX */
902            if(d->init_dither == init_fstein_dither)
903            {
904                error[0] = rgba[0] - (fg_r * ch + bg_r * ((2*dchmax-1) - ch)) / (2*dchmax-1);
905                error[1] = rgba[1] - (fg_g * ch + bg_g * ((2*dchmax-1) - ch)) / (2*dchmax-1);
906                error[2] = rgba[2] - (fg_b * ch + bg_b * ((2*dchmax-1) - ch)) / (2*dchmax-1);
907            }
908        }
909        else
910        {
911            unsigned int lum = rgba[0];
912            if(rgba[1] > lum) lum = rgba[1];
913            if(rgba[2] > lum) lum = rgba[2];
914            outfg = outbg;
915            outbg = CUCUL_COLOR_BLACK;
916
917            ch = lum * dchmax / 0x1000;
918            if(ch < 0)
919                ch = 0;
920            else if(ch > (int)(dchmax - 1))
921                ch = dchmax - 1;
922            outch = d->glyphs[ch];
923
924            /* XXX: OMG HAX */
925            if(d->init_dither == init_fstein_dither)
926            {
927                error[0] = rgba[0] - bg_r * ch / (dchmax-1);
928                error[1] = rgba[1] - bg_g * ch / (dchmax-1);
929                error[2] = rgba[2] - bg_b * ch / (dchmax-1);
930            }
931        }
932
933        /* XXX: OMG HAX */
934        if(d->init_dither == init_fstein_dither)
935        {
936            remain_r = fs_r[x+1] + 7 * error[0] / 16;
937            remain_g = fs_g[x+1] + 7 * error[1] / 16;
938            remain_b = fs_b[x+1] + 7 * error[2] / 16;
939            fs_r[x-1] += 3 * error[0] / 16;
940            fs_g[x-1] += 3 * error[1] / 16;
941            fs_b[x-1] += 3 * error[2] / 16;
942            fs_r[x] = 5 * error[0] / 16;
943            fs_g[x] = 5 * error[1] / 16;
944            fs_b[x] = 5 * error[2] / 16;
945            fs_r[x+1] = 1 * error[0] / 16;
946            fs_g[x+1] = 1 * error[1] / 16;
947            fs_b[x+1] = 1 * error[2] / 16;
948        }
949
950        if(d->invert)
951        {
952            outfg = 15 - outfg;
953            outbg = 15 - outbg;
954        }
955
956        /* Now output the character */
957        cucul_set_color(qq, outfg, outbg);
958        cucul_putstr(qq, x, y, outch);
959
960       d->increment_dither();
961    }
962        /* end loop */
963    }
964
965    free(floyd_steinberg);
966}
967
968/**
969 * \brief Free the memory associated with a dither.
970 *
971 * Free the memory allocated by cucul_create_dither().
972 *
973 * \param dither Dither object.
974 */
975void cucul_free_dither(struct cucul_dither *d)
976{
977    if(!d)
978        return;
979
980    free(d);
981}
982
983/*
984 * XXX: The following functions are local.
985 */
986
987/* Convert a mask, eg. 0x0000ff00, to shift values, eg. 8 and -4. */
988static void mask2shift(unsigned int mask, int *right, int *left)
989{
990    int rshift = 0, lshift = 0;
991
992    if(!mask)
993    {
994        *right = *left = 0;
995        return;
996    }
997
998    while(!(mask & 1))
999    {
1000        mask >>= 1;
1001        rshift++;
1002    }
1003    *right = rshift;
1004
1005    while(mask & 1)
1006    {
1007        mask >>= 1;
1008        lshift++;
1009    }
1010    *left = 12 - lshift;
1011}
1012
1013/* Compute x^y without relying on the math library */
1014static float gammapow(float x, float y)
1015{
1016#ifdef HAVE_FLDLN2
1017    register double logx;
1018    register long double v, e;
1019#else
1020    register float tmp, t, t2, r;
1021    int i;
1022#endif
1023
1024    if(x == 0.0)
1025        return y == 0.0 ? 1.0 : 0.0;
1026
1027#ifdef HAVE_FLDLN2
1028    /* FIXME: this can be optimised by directly calling fyl2x for x and y */
1029    asm volatile("fldln2; fxch; fyl2x"
1030                 : "=t" (logx) : "0" (x) : "st(1)");
1031
1032    asm volatile("fldl2e\n\t"
1033                 "fmul %%st(1)\n\t"
1034                 "fst %%st(1)\n\t"
1035                 "frndint\n\t"
1036                 "fxch\n\t"
1037                 "fsub %%st(1)\n\t"
1038                 "f2xm1\n\t"
1039                 : "=t" (v), "=u" (e) : "0" (y * logx));
1040    v += 1.0;
1041    asm volatile("fscale"
1042                 : "=t" (v) : "0" (v), "u" (e));
1043    return v;
1044#else
1045    /* Compute ln(x) for x ∈ ]0,1]
1046     *   ln(x) = 2 * (t + t^3/3 + t^5/5 + ...) with t = (x-1)/(x+1)
1047     * The convergence is a bit slow, especially when x is near 0. */
1048    t = (x - 1.0) / (x + 1.0);
1049    t2 = t * t;
1050    tmp = r = t;
1051    for(i = 3; i < 20; i += 2)
1052    {
1053        r *= t2;
1054        tmp += r / i;
1055    }
1056
1057    /* Compute -y*ln(x) */
1058    tmp = - y * 2.0 * tmp;
1059
1060    /* Compute x^-y as e^t where t = -y*ln(x):
1061     *   e^t = 1 + t/1! + t^2/2! + t^3/3! + t^4/4! + t^5/5! ...
1062     * The convergence is quite faster here, thanks to the factorial. */
1063    r = t = tmp;
1064    tmp = 1.0 + t;
1065    for(i = 2; i < 16; i++)
1066    {
1067        r = r * t / i;
1068        tmp += r;
1069    }
1070
1071    /* Return x^y as 1/(x^-y) */
1072    return 1.0 / tmp;
1073#endif
1074}
1075
1076static void get_rgba_default(struct cucul_dither const *d, uint8_t *pixels,
1077                             int x, int y, unsigned int *rgba)
1078{
1079    uint32_t bits;
1080
1081    pixels += (d->bpp / 8) * x + d->pitch * y;
1082
1083    switch(d->bpp / 8)
1084    {
1085        case 4:
1086            bits = *(uint32_t *)pixels;
1087            break;
1088        case 3:
1089        {
1090#if defined(HAVE_ENDIAN_H)
1091            if(__BYTE_ORDER == __BIG_ENDIAN)
1092#else
1093            /* This is compile-time optimised with at least -O1 or -Os */
1094            uint32_t const rmask = 0x12345678;
1095            if(*(uint8_t const *)&rmask == 0x12)
1096#endif
1097                bits = ((uint32_t)pixels[0] << 16) |
1098                       ((uint32_t)pixels[1] << 8) |
1099                       ((uint32_t)pixels[2]);
1100            else
1101                bits = ((uint32_t)pixels[2] << 16) |
1102                       ((uint32_t)pixels[1] << 8) |
1103                       ((uint32_t)pixels[0]);
1104            break;
1105        }
1106        case 2:
1107            bits = *(uint16_t *)pixels;
1108            break;
1109        case 1:
1110        default:
1111            bits = pixels[0];
1112            break;
1113    }
1114
1115    if(d->has_palette)
1116    {
1117        rgba[0] += d->gammatab[d->red[bits]];
1118        rgba[1] += d->gammatab[d->green[bits]];
1119        rgba[2] += d->gammatab[d->blue[bits]];
1120        rgba[3] += d->alpha[bits];
1121    }
1122    else
1123    {
1124        rgba[0] += d->gammatab[((bits & d->rmask) >> d->rright) << d->rleft];
1125        rgba[1] += d->gammatab[((bits & d->gmask) >> d->gright) << d->gleft];
1126        rgba[2] += d->gammatab[((bits & d->bmask) >> d->bright) << d->bleft];
1127        rgba[3] += ((bits & d->amask) >> d->aright) << d->aleft;
1128    }
1129}
1130
1131/*
1132 * No dithering
1133 */
1134static void init_no_dither(int line)
1135{
1136    ;
1137}
1138
1139static unsigned int get_no_dither(void)
1140{
1141    return 0x80;
1142}
1143
1144static void increment_no_dither(void)
1145{
1146    return;
1147}
1148
1149/*
1150 * Floyd-Steinberg dithering
1151 */
1152static void init_fstein_dither(int line)
1153{
1154    ;
1155}
1156
1157static unsigned int get_fstein_dither(void)
1158{
1159    return 0x80;
1160}
1161
1162static void increment_fstein_dither(void)
1163{
1164    return;
1165}
1166
1167/*
1168 * Ordered 2 dithering
1169 */
1170static unsigned int const *ordered2_table;
1171static unsigned int ordered2_index;
1172
1173static void init_ordered2_dither(int line)
1174{
1175    static unsigned int const dither2x2[] =
1176    {
1177        0x00, 0x80,
1178        0xc0, 0x40,
1179    };
1180
1181    ordered2_table = dither2x2 + (line % 2) * 2;
1182    ordered2_index = 0;
1183}
1184
1185static unsigned int get_ordered2_dither(void)
1186{
1187    return ordered2_table[ordered2_index];
1188}
1189
1190static void increment_ordered2_dither(void)
1191{
1192    ordered2_index = (ordered2_index + 1) % 2;
1193}
1194
1195/*
1196 * Ordered 4 dithering
1197 */
1198/*static int dither4x4[] = { 5,  0,  1,  6,
1199                          -1, -6, -5,  2,
1200                          -2, -7, -8,  3,
1201                           4, -3, -4, -7};*/
1202static unsigned int const *ordered4_table;
1203static unsigned int ordered4_index;
1204
1205static void init_ordered4_dither(int line)
1206{
1207    static unsigned int const dither4x4[] =
1208    {
1209        0x00, 0x80, 0x20, 0xa0,
1210        0xc0, 0x40, 0xe0, 0x60,
1211        0x30, 0xb0, 0x10, 0x90,
1212        0xf0, 0x70, 0xd0, 0x50
1213    };
1214
1215    ordered4_table = dither4x4 + (line % 4) * 4;
1216    ordered4_index = 0;
1217}
1218
1219static unsigned int get_ordered4_dither(void)
1220{
1221    return ordered4_table[ordered4_index];
1222}
1223
1224static void increment_ordered4_dither(void)
1225{
1226    ordered4_index = (ordered4_index + 1) % 4;
1227}
1228
1229/*
1230 * Ordered 8 dithering
1231 */
1232static unsigned int const *ordered8_table;
1233static unsigned int ordered8_index;
1234
1235static void init_ordered8_dither(int line)
1236{
1237    static unsigned int const dither8x8[] =
1238    {
1239        0x00, 0x80, 0x20, 0xa0, 0x08, 0x88, 0x28, 0xa8,
1240        0xc0, 0x40, 0xe0, 0x60, 0xc8, 0x48, 0xe8, 0x68,
1241        0x30, 0xb0, 0x10, 0x90, 0x38, 0xb8, 0x18, 0x98,
1242        0xf0, 0x70, 0xd0, 0x50, 0xf8, 0x78, 0xd8, 0x58,
1243        0x0c, 0x8c, 0x2c, 0xac, 0x04, 0x84, 0x24, 0xa4,
1244        0xcc, 0x4c, 0xec, 0x6c, 0xc4, 0x44, 0xe4, 0x64,
1245        0x3c, 0xbc, 0x1c, 0x9c, 0x34, 0xb4, 0x14, 0x94,
1246        0xfc, 0x7c, 0xdc, 0x5c, 0xf4, 0x74, 0xd4, 0x54,
1247    };
1248
1249    ordered8_table = dither8x8 + (line % 8) * 8;
1250    ordered8_index = 0;
1251}
1252
1253static unsigned int get_ordered8_dither(void)
1254{
1255    return ordered8_table[ordered8_index];
1256}
1257
1258static void increment_ordered8_dither(void)
1259{
1260    ordered8_index = (ordered8_index + 1) % 8;
1261}
1262
1263/*
1264 * Random dithering
1265 */
1266static void init_random_dither(int line)
1267{
1268    ;
1269}
1270
1271static unsigned int get_random_dither(void)
1272{
1273    return cucul_rand(0x00, 0xff);
1274}
1275
1276static void increment_random_dither(void)
1277{
1278    return;
1279}
1280
1281#if !defined(_DOXYGEN_SKIP_ME)
1282int _cucul_init_dither(void)
1283{
1284    unsigned int v, s, h;
1285
1286    /* These ones are constant */
1287    lookup_colors[0] = CUCUL_COLOR_BLACK;
1288    lookup_colors[1] = CUCUL_COLOR_DARKGRAY;
1289    lookup_colors[2] = CUCUL_COLOR_LIGHTGRAY;
1290    lookup_colors[3] = CUCUL_COLOR_WHITE;
1291
1292    /* These ones will be overwritten */
1293    lookup_colors[4] = CUCUL_COLOR_MAGENTA;
1294    lookup_colors[5] = CUCUL_COLOR_LIGHTMAGENTA;
1295    lookup_colors[6] = CUCUL_COLOR_RED;
1296    lookup_colors[7] = CUCUL_COLOR_LIGHTRED;
1297
1298    for(v = 0; v < LOOKUP_VAL; v++)
1299        for(s = 0; s < LOOKUP_SAT; s++)
1300            for(h = 0; h < LOOKUP_HUE; h++)
1301    {
1302        int i, distbg, distfg, dist;
1303        int val, sat, hue;
1304        unsigned char outbg, outfg;
1305
1306        val = 0xfff * v / (LOOKUP_VAL - 1);
1307        sat = 0xfff * s / (LOOKUP_SAT - 1);
1308        hue = 0xfff * h / (LOOKUP_HUE - 1);
1309
1310        /* Initialise distances to the distance between pure black HSV
1311         * coordinates and our white colour (3) */
1312        outbg = outfg = 3;
1313        distbg = distfg = HSV_DISTANCE(0, 0, 0, 3);
1314
1315        /* Calculate distances to eight major colour values and store the
1316         * two nearest points in our lookup table. */
1317        for(i = 0; i < 8; i++)
1318        {
1319            dist = HSV_DISTANCE(hue, sat, val, i);
1320            if(dist <= distbg)
1321            {
1322                outfg = outbg;
1323                distfg = distbg;
1324                outbg = i;
1325                distbg = dist;
1326            }
1327            else if(dist <= distfg)
1328            {
1329                outfg = i;
1330                distfg = dist;
1331            }
1332        }
1333
1334        hsv_distances[v][s][h] = (outfg << 4) | outbg;
1335    }
1336
1337    return 0;
1338}
1339
1340int _cucul_end_dither(void)
1341{
1342    return 0;
1343}
1344#endif /* _DOXYGEN_SKIP_ME */
1345
1346
Note: See TracBrowser for help on using the repository browser.