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

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