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

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