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

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