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

Last change on this file since 958 was 958, checked in by Sam Hocevar, 14 years ago
  • Changed cucul_putchar's prototype so that it accepts a 32-bit unsigned int which shall be used as an UTF-32 character. We do not have any casting problems due to the signedness of chars because all characters were ASCII (ie. <= 0x7f) beforehands.
  • Property svn:keywords set to Id
File size: 38.4 KB
Line 
1/*
2 *  libcucul      Canvas for ultrafast compositing of Unicode letters
3 *  Copyright (c) 2002-2006 Sam Hocevar <sam@zoy.org>
4 *                All Rights Reserved
5 *
6 *  $Id: dither.c 958 2006-05-18 06:23:47Z 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 *
493 *  \li \c "none": no antialiasing.
494 *
495 *  \li \c "prefilter" or \c "default": simple prefilter antialiasing. This
496 *      is the default value.
497 *
498 *  If an error occurs, -1 is returned and \b errno is set accordingly:
499 *  - \c EINVAL Invalid antialiasing mode.
500 *
501 *  \param d Dither object.
502 *  \param str A string describing the antialiasing method that will be used
503 *         for the dithering.
504 *  \return 0 in case of success, -1 if an error occurred.
505 */
506int cucul_set_dither_antialias(cucul_dither_t *d, char const *str)
507{
508    if(!strcasecmp(str, "none"))
509        d->antialias = 0;
510    else if(!strcasecmp(str, "prefilter") || !strcasecmp(str, "default"))
511        d->antialias = 1;
512    else
513    {
514#if defined(HAVE_ERRNO_H)
515        errno = EINVAL;
516#endif
517        return -1;
518    }
519
520    return 0;
521}
522
523/** \brief Get available antialiasing methods
524 *
525 *  Return a list of available antialiasing methods for a given dither. The
526 *  list is a NULL-terminated array of strings, interleaving a string
527 *  containing the internal value for the antialiasing method to be used with
528 *  cucul_set_dither_antialias(), and a string containing the natural
529 *  language description for that antialiasing method.
530 *
531 *  This function never fails.
532 *
533 *  \param d Dither object.
534 *  \return An array of strings.
535 */
536char const * const *
537    cucul_get_dither_antialias_list(cucul_dither_t const *d)
538{
539    static char const * const list[] =
540    {
541        "none", "No antialiasing",
542        "prefilter", "Prefilter antialiasing",
543        NULL, NULL
544    };
545
546    return list;
547}
548
549/** \brief Choose colours used for dithering
550 *
551 *  Tell the renderer which colours should be used to render the
552 *  bitmap. Valid values for \c str are:
553 *
554 *  \li \c "mono": use light gray on a black background.
555 *
556 *  \li \c "gray": use white and two shades of gray on a black background.
557 *
558 *  \li \c "8": use the 8 ANSI colours on a black background.
559 *
560 *  \li \c "16": use the 16 ANSI colours on a black background.
561 *
562 *  \li \c "fullgray": use black, white and two shades of gray for both the
563 *      characters and the background.
564 *
565 *  \li \c "full8": use the 8 ANSI colours for both the characters and the
566 *      background.
567 *
568 *  \li \c "full16" or \c "default": use the 16 ANSI colours for both the
569 *      characters and the background. This is the default value.
570 *
571 *  If an error occurs, -1 is returned and \b errno is set accordingly:
572 *  - \c EINVAL Invalid colour set.
573 *
574 *  \param d Dither object.
575 *  \param str A string describing the colour set that will be used
576 *         for the dithering.
577 *  \return 0 in case of success, -1 if an error occurred.
578 */
579int cucul_set_dither_color(cucul_dither_t *d, char const *str)
580{
581    if(!strcasecmp(str, "mono"))
582        d->color_mode = COLOR_MODE_MONO;
583    else if(!strcasecmp(str, "gray"))
584        d->color_mode = COLOR_MODE_GRAY;
585    else if(!strcasecmp(str, "8"))
586        d->color_mode = COLOR_MODE_8;
587    else if(!strcasecmp(str, "16"))
588        d->color_mode = COLOR_MODE_16;
589    else if(!strcasecmp(str, "fullgray"))
590        d->color_mode = COLOR_MODE_FULLGRAY;
591    else if(!strcasecmp(str, "full8"))
592        d->color_mode = COLOR_MODE_FULL8;
593    else if(!strcasecmp(str, "full16") || !strcasecmp(str, "default"))
594        d->color_mode = COLOR_MODE_FULL16;
595    else
596    {
597#if defined(HAVE_ERRNO_H)
598        errno = EINVAL;
599#endif
600        return -1;
601    }
602
603    return 0;
604}
605
606/** \brief Get available colour modes
607 *
608 *  Return a list of available colour modes for a given dither. The list
609 *  is a NULL-terminated array of strings, interleaving a string containing
610 *  the internal value for the colour mode, to be used with
611 *  cucul_set_dither_color(), and a string containing the natural
612 *  language description for that colour mode.
613 *
614 *  This function never fails.
615 *
616 *  \param d Dither object.
617 *  \return An array of strings.
618 */
619char const * const *
620    cucul_get_dither_color_list(cucul_dither_t const *d)
621{
622    static char const * const list[] =
623    {
624        "mono", "white on black",
625        "gray", "grayscale on black",
626        "8", "8 colours on black",
627        "16", "16 colours on black",
628        "fullgray", "full grayscale",
629        "full8", "full 8 colours",
630        "full16", "full 16 colours",
631        NULL, NULL
632    };
633
634    return list;
635}
636
637/** \brief Choose characters used for dithering
638 *
639 *  Tell the renderer which characters should be used to render the
640 *  dither. Valid values for \c str are:
641 *
642 *  \li \c "ascii" or "default": use only ASCII characters. This is the
643 *      default value.
644 *
645 *  \li \c "shades": use Unicode characters "U+2591 LIGHT SHADE", "U+2592
646 *      MEDIUM SHADE" and "U+2593 DARK SHADE". These characters are also
647 *      present in the CP437 codepage available on DOS and VGA.
648 *
649 *  \li \c "blocks": use Unicode quarter-cell block combinations. These
650 *      characters are only found in the Unicode set.
651 *
652 *  If an error occurs, -1 is returned and \b errno is set accordingly:
653 *  - \c EINVAL Invalid character set.
654 *
655 *  \param d Dither object.
656 *  \param str A string describing the characters that need to be used
657 *         for the dithering.
658 *  \return 0 in case of success, -1 if an error occurred.
659 */
660int cucul_set_dither_charset(cucul_dither_t *d, char const *str)
661{
662    if(!strcasecmp(str, "shades"))
663    {
664        d->glyphs = shades_glyphs;
665        d->glyph_count = sizeof(shades_glyphs) / sizeof(*shades_glyphs);
666    }
667    else if(!strcasecmp(str, "blocks"))
668    {
669        d->glyphs = blocks_glyphs;
670        d->glyph_count = sizeof(blocks_glyphs) / sizeof(*blocks_glyphs);
671    }
672    else if(!strcasecmp(str, "ascii") || !strcasecmp(str, "default"))
673    {
674        d->glyphs = ascii_glyphs;
675        d->glyph_count = sizeof(ascii_glyphs) / sizeof(*ascii_glyphs);
676    }
677    else
678    {
679#if defined(HAVE_ERRNO_H)
680        errno = EINVAL;
681#endif
682        return -1;
683    }
684
685    return 0;
686}
687
688/** \brief Get available dither character sets
689 *
690 *  Return a list of available character sets for a given dither. The list
691 *  is a NULL-terminated array of strings, interleaving a string containing
692 *  the internal value for the character set, to be used with
693 *  cucul_set_dither_charset(), and a string containing the natural
694 *  language description for that character set.
695 *
696 *  This function never fails.
697 *
698 *  \param d Dither object.
699 *  \return An array of strings.
700 */
701char const * const * cucul_get_dither_charset_list(cucul_dither_t const *d)
702{
703    static char const * const list[] =
704    {
705        "ascii", "plain ASCII",
706        "shades", "CP437 shades",
707        "blocks", "Unicode blocks",
708        NULL, NULL
709    };
710
711    return list;
712}
713
714/** \brief Set dithering method
715 *
716 *  Tell the renderer which dithering method should be used. Dithering is
717 *  necessary because the picture being rendered has usually far more colours
718 *  than the available palette. Valid values for \c str are:
719 *
720 *  \li \c "none": no dithering is used, the nearest matching colour is used.
721 *
722 *  \li \c "ordered2": use a 2x2 Bayer matrix for dithering.
723 *
724 *  \li \c "ordered4": use a 4x4 Bayer matrix for dithering.
725 *
726 *  \li \c "ordered8": use a 8x8 Bayer matrix for dithering.
727 *
728 *  \li \c "random": use random dithering.
729 *
730 *  \li \c "fstein": use Floyd-Steinberg dithering. This is the default value.
731 *
732 *  If an error occurs, -1 is returned and \b errno is set accordingly:
733 *  - \c EINVAL Unknown dithering mode.
734 *
735 *  \param d Dither object.
736 *  \param str A string describing the method that needs to be used
737 *         for the dithering.
738 *  \return 0 in case of success, -1 if an error occurred.
739 */
740int cucul_set_dither_mode(cucul_dither_t *d, char const *str)
741{
742    if(!strcasecmp(str, "none"))
743    {
744        d->init_dither = init_no_dither;
745        d->get_dither = get_no_dither;
746        d->increment_dither = increment_no_dither;
747    }
748    else if(!strcasecmp(str, "ordered2"))
749    {
750        d->init_dither = init_ordered2_dither;
751        d->get_dither = get_ordered2_dither;
752        d->increment_dither = increment_ordered2_dither;
753    }
754    else if(!strcasecmp(str, "ordered4"))
755    {
756        d->init_dither = init_ordered4_dither;
757        d->get_dither = get_ordered4_dither;
758        d->increment_dither = increment_ordered4_dither;
759    }
760    else if(!strcasecmp(str, "ordered4"))
761    {
762        d->init_dither = init_ordered8_dither;
763        d->get_dither = get_ordered8_dither;
764        d->increment_dither = increment_ordered8_dither;
765    }
766    else if(!strcasecmp(str, "random"))
767    {
768        d->init_dither = init_random_dither;
769        d->get_dither = get_random_dither;
770        d->increment_dither = increment_random_dither;
771    }
772    else if(!strcasecmp(str, "fstein") || !strcasecmp(str, "default"))
773    {
774        d->init_dither = init_fstein_dither;
775        d->get_dither = get_fstein_dither;
776        d->increment_dither = increment_fstein_dither;
777    }
778    else
779    {
780#if defined(HAVE_ERRNO_H)
781        errno = EINVAL;
782#endif
783        return -1;
784    }
785
786    return 0;
787}
788
789/** \brief Get dithering methods
790 *
791 *  Return a list of available dithering methods for a given dither. The list
792 *  is a NULL-terminated array of strings, interleaving a string containing
793 *  the internal value for the dithering method, to be used with
794 *  cucul_set_dither_dithering(), and a string containing the natural
795 *  language description for that dithering method.
796 *
797 *  This function never fails.
798 *
799 *  \param d Dither object.
800 *  \return An array of strings.
801 */
802char const * const * cucul_get_dither_mode_list(cucul_dither_t const *d)
803{
804    static char const * const list[] =
805    {
806        "none", "no dithering",
807        "ordered2", "2x2 ordered dithering",
808        "ordered2", "2x2 ordered dithering",
809        "ordered2", "2x2 ordered dithering",
810        "random", "random dithering",
811        "fstein", "Floyd-Steinberg dithering",
812        NULL, NULL
813    };
814
815    return list;
816}
817
818/** \brief Dither a bitmap on the canvas.
819 *
820 *  Dither a bitmap at the given coordinates. The dither can be of any size
821 *  and will be stretched to the text area.
822 *
823 *  This function never fails.
824 *
825 *  \param cv A handle to the libcucul canvas.
826 *  \param x X coordinate of the upper-left corner of the drawing area.
827 *  \param y Y coordinate of the upper-left corner of the drawing area.
828 *  \param w Width of the drawing area.
829 *  \param h Height of the drawing area.
830 *  \param d Dither object to be drawn.
831 *  \param pixels Bitmap's pixels.
832 *  \return This function always returns 0.
833 */
834int cucul_dither_bitmap(cucul_canvas_t *cv, int x, int y, int w, int h,
835                        cucul_dither_t const *d, void *pixels)
836{
837    int *floyd_steinberg, *fs_r, *fs_g, *fs_b;
838    int fs_length;
839    int x1, y1, x2, y2, pitch, deltax, deltay;
840    unsigned int dchmax;
841
842    if(!d || !pixels)
843        return 0;
844
845    x1 = x; x2 = x + w - 1;
846    y1 = y; y2 = y + h - 1;
847
848    /* FIXME: do not overwrite arguments */
849    w = d->w;
850    h = d->h;
851    pitch = d->pitch;
852
853    deltax = x2 - x1 + 1;
854    deltay = y2 - y1 + 1;
855    dchmax = d->glyph_count;
856
857    fs_length = ((int)cv->width <= x2 ? (int)cv->width : x2) + 1;
858    floyd_steinberg = malloc(3 * (fs_length + 2) * sizeof(int));
859    memset(floyd_steinberg, 0, 3 * (fs_length + 2) * sizeof(int));
860    fs_r = floyd_steinberg + 1;
861    fs_g = fs_r + fs_length + 2;
862    fs_b = fs_g + fs_length + 2;
863
864    for(y = y1 > 0 ? y1 : 0; y <= y2 && y <= (int)cv->height; y++)
865    {
866        int remain_r = 0, remain_g = 0, remain_b = 0;
867
868        for(x = x1 > 0 ? x1 : 0, d->init_dither(y);
869            x <= x2 && x <= (int)cv->width;
870            x++)
871    {
872        unsigned int i;
873        int ch = 0, distmin;
874        unsigned int rgba[4];
875        int fg_r = 0, fg_g = 0, fg_b = 0, bg_r, bg_g, bg_b;
876        int fromx, fromy, tox, toy, myx, myy, dots, dist;
877        int error[3];
878
879        unsigned int outfg = 0, outbg = 0;
880        uint32_t outch;
881
882        rgba[0] = rgba[1] = rgba[2] = rgba[3] = 0;
883
884        /* First get RGB */
885        if(d->antialias)
886        {
887            fromx = (x - x1) * w / deltax;
888            fromy = (y - y1) * h / deltay;
889            tox = (x - x1 + 1) * w / deltax;
890            toy = (y - y1 + 1) * h / deltay;
891
892            /* We want at least one pixel */
893            if(tox == fromx) tox++;
894            if(toy == fromy) toy++;
895
896            dots = 0;
897
898            for(myx = fromx; myx < tox; myx++)
899                for(myy = fromy; myy < toy; myy++)
900            {
901                dots++;
902                get_rgba_default(d, pixels, myx, myy, rgba);
903            }
904
905            /* Normalize */
906            rgba[0] /= dots;
907            rgba[1] /= dots;
908            rgba[2] /= dots;
909            rgba[3] /= dots;
910        }
911        else
912        {
913            fromx = (x - x1) * w / deltax;
914            fromy = (y - y1) * h / deltay;
915            tox = (x - x1 + 1) * w / deltax;
916            toy = (y - y1 + 1) * h / deltay;
917
918            /* tox and toy can overflow the canvas, but they cannot overflow
919             * when averaged with fromx and fromy because these are guaranteed
920             * to be within the pixel boundaries. */
921            myx = (fromx + tox) / 2;
922            myy = (fromy + toy) / 2;
923
924            get_rgba_default(d, pixels, myx, myy, rgba);
925        }
926
927        if(d->has_alpha && rgba[3] < 0x800)
928        {
929            remain_r = remain_g = remain_b = 0;
930            fs_r[x] = 0;
931            fs_g[x] = 0;
932            fs_b[x] = 0;
933            continue;
934        }
935
936        /* XXX: OMG HAX */
937        if(d->init_dither == init_fstein_dither)
938        {
939            rgba[0] += remain_r;
940            rgba[1] += remain_g;
941            rgba[2] += remain_b;
942        }
943        else
944        {
945            rgba[0] += (d->get_dither() - 0x80) * 4;
946            rgba[1] += (d->get_dither() - 0x80) * 4;
947            rgba[2] += (d->get_dither() - 0x80) * 4;
948        }
949
950        distmin = INT_MAX;
951        for(i = 0; i < 16; i++)
952        {
953            dist = sq(rgba[0] - rgb_palette[i * 3])
954                 + sq(rgba[1] - rgb_palette[i * 3 + 1])
955                 + sq(rgba[2] - rgb_palette[i * 3 + 2]);
956            dist *= rgb_weight[i];
957            if(dist < distmin)
958            {
959                outbg = i;
960                distmin = dist;
961            }
962        }
963        bg_r = rgb_palette[outbg * 3];
964        bg_g = rgb_palette[outbg * 3 + 1];
965        bg_b = rgb_palette[outbg * 3 + 2];
966
967        /* FIXME: we currently only honour "full16" */
968        if(d->color_mode == COLOR_MODE_FULL16)
969        {
970            distmin = INT_MAX;
971            for(i = 0; i < 16; i++)
972            {
973                if(i == outbg)
974                    continue;
975                dist = sq(rgba[0] - rgb_palette[i * 3])
976                     + sq(rgba[1] - rgb_palette[i * 3 + 1])
977                     + sq(rgba[2] - rgb_palette[i * 3 + 2]);
978                dist *= rgb_weight[i];
979                if(dist < distmin)
980                {
981                    outfg = i;
982                    distmin = dist;
983                }
984            }
985            fg_r = rgb_palette[outfg * 3];
986            fg_g = rgb_palette[outfg * 3 + 1];
987            fg_b = rgb_palette[outfg * 3 + 2];
988
989            distmin = INT_MAX;
990            for(i = 0; i < dchmax - 1; i++)
991            {
992                int newr = i * fg_r + ((2*dchmax-1) - i) * bg_r;
993                int newg = i * fg_g + ((2*dchmax-1) - i) * bg_g;
994                int newb = i * fg_b + ((2*dchmax-1) - i) * bg_b;
995                dist = abs(rgba[0] * (2*dchmax-1) - newr)
996                     + abs(rgba[1] * (2*dchmax-1) - newg)
997                     + abs(rgba[2] * (2*dchmax-1) - newb);
998
999                if(dist < distmin)
1000                {
1001                    ch = i;
1002                    distmin = dist;
1003                }
1004            }
1005            outch = d->glyphs[ch];
1006
1007            /* XXX: OMG HAX */
1008            if(d->init_dither == init_fstein_dither)
1009            {
1010                error[0] = rgba[0] - (fg_r * ch + bg_r * ((2*dchmax-1) - ch)) / (2*dchmax-1);
1011                error[1] = rgba[1] - (fg_g * ch + bg_g * ((2*dchmax-1) - ch)) / (2*dchmax-1);
1012                error[2] = rgba[2] - (fg_b * ch + bg_b * ((2*dchmax-1) - ch)) / (2*dchmax-1);
1013            }
1014        }
1015        else
1016        {
1017            unsigned int lum = rgba[0];
1018            if(rgba[1] > lum) lum = rgba[1];
1019            if(rgba[2] > lum) lum = rgba[2];
1020            outfg = outbg;
1021            outbg = CUCUL_COLOR_BLACK;
1022
1023            ch = lum * dchmax / 0x1000;
1024            if(ch < 0)
1025                ch = 0;
1026            else if(ch > (int)(dchmax - 1))
1027                ch = dchmax - 1;
1028            outch = d->glyphs[ch];
1029
1030            /* XXX: OMG HAX */
1031            if(d->init_dither == init_fstein_dither)
1032            {
1033                error[0] = rgba[0] - bg_r * ch / (dchmax-1);
1034                error[1] = rgba[1] - bg_g * ch / (dchmax-1);
1035                error[2] = rgba[2] - bg_b * ch / (dchmax-1);
1036            }
1037        }
1038
1039        /* XXX: OMG HAX */
1040        if(d->init_dither == init_fstein_dither)
1041        {
1042            remain_r = fs_r[x+1] + 7 * error[0] / 16;
1043            remain_g = fs_g[x+1] + 7 * error[1] / 16;
1044            remain_b = fs_b[x+1] + 7 * error[2] / 16;
1045            fs_r[x-1] += 3 * error[0] / 16;
1046            fs_g[x-1] += 3 * error[1] / 16;
1047            fs_b[x-1] += 3 * error[2] / 16;
1048            fs_r[x] = 5 * error[0] / 16;
1049            fs_g[x] = 5 * error[1] / 16;
1050            fs_b[x] = 5 * error[2] / 16;
1051            fs_r[x+1] = 1 * error[0] / 16;
1052            fs_g[x+1] = 1 * error[1] / 16;
1053            fs_b[x+1] = 1 * error[2] / 16;
1054        }
1055
1056        if(d->invert)
1057        {
1058            outfg = 15 - outfg;
1059            outbg = 15 - outbg;
1060        }
1061
1062        /* Now output the character */
1063        cucul_set_color(cv, outfg, outbg);
1064        cucul_putchar(cv, x, y, outch);
1065
1066       d->increment_dither();
1067    }
1068        /* end loop */
1069    }
1070
1071    free(floyd_steinberg);
1072
1073    return 0;
1074}
1075
1076/** \brief Free the memory associated with a dither.
1077 *
1078 *  Free the memory allocated by cucul_create_dither().
1079 *
1080 *  This function never fails.
1081 *
1082 *  \param d Dither object.
1083 *  \return This function always returns 0.
1084 */
1085int cucul_free_dither(cucul_dither_t *d)
1086{
1087    if(!d)
1088        return 0;
1089
1090    free(d);
1091
1092    return 0;
1093}
1094
1095/*
1096 * XXX: The following functions are local.
1097 */
1098
1099/* Convert a mask, eg. 0x0000ff00, to shift values, eg. 8 and -4. */
1100static void mask2shift(unsigned long int mask, int *right, int *left)
1101{
1102    int rshift = 0, lshift = 0;
1103
1104    if(!mask)
1105    {
1106        *right = *left = 0;
1107        return;
1108    }
1109
1110    while(!(mask & 1))
1111    {
1112        mask >>= 1;
1113        rshift++;
1114    }
1115    *right = rshift;
1116
1117    while(mask & 1)
1118    {
1119        mask >>= 1;
1120        lshift++;
1121    }
1122    *left = 12 - lshift;
1123}
1124
1125/* Compute x^y without relying on the math library */
1126static float gammapow(float x, float y)
1127{
1128#ifdef HAVE_FLDLN2
1129    register double logx;
1130    register long double v, e;
1131#else
1132    register float tmp, t, t2, r;
1133    int i;
1134#endif
1135
1136    if(x == 0.0)
1137        return y == 0.0 ? 1.0 : 0.0;
1138
1139#ifdef HAVE_FLDLN2
1140    /* FIXME: this can be optimised by directly calling fyl2x for x and y */
1141    asm volatile("fldln2; fxch; fyl2x"
1142                 : "=t" (logx) : "0" (x) : "st(1)");
1143
1144    asm volatile("fldl2e\n\t"
1145                 "fmul %%st(1)\n\t"
1146                 "fst %%st(1)\n\t"
1147                 "frndint\n\t"
1148                 "fxch\n\t"
1149                 "fsub %%st(1)\n\t"
1150                 "f2xm1\n\t"
1151                 : "=t" (v), "=u" (e) : "0" (y * logx));
1152    v += 1.0;
1153    asm volatile("fscale"
1154                 : "=t" (v) : "0" (v), "u" (e));
1155    return v;
1156#else
1157    /* Compute ln(x) for x ∈ ]0,1]
1158     *   ln(x) = 2 * (t + t^3/3 + t^5/5 + ...) with t = (x-1)/(x+1)
1159     * The convergence is a bit slow, especially when x is near 0. */
1160    t = (x - 1.0) / (x + 1.0);
1161    t2 = t * t;
1162    tmp = r = t;
1163    for(i = 3; i < 20; i += 2)
1164    {
1165        r *= t2;
1166        tmp += r / i;
1167    }
1168
1169    /* Compute -y*ln(x) */
1170    tmp = - y * 2.0 * tmp;
1171
1172    /* Compute x^-y as e^t where t = -y*ln(x):
1173     *   e^t = 1 + t/1! + t^2/2! + t^3/3! + t^4/4! + t^5/5! ...
1174     * The convergence is quite faster here, thanks to the factorial. */
1175    r = t = tmp;
1176    tmp = 1.0 + t;
1177    for(i = 2; i < 16; i++)
1178    {
1179        r = r * t / i;
1180        tmp += r;
1181    }
1182
1183    /* Return x^y as 1/(x^-y) */
1184    return 1.0 / tmp;
1185#endif
1186}
1187
1188static void get_rgba_default(cucul_dither_t const *d, uint8_t *pixels,
1189                             int x, int y, unsigned int *rgba)
1190{
1191    uint32_t bits;
1192
1193    pixels += (d->bpp / 8) * x + d->pitch * y;
1194
1195    switch(d->bpp / 8)
1196    {
1197        case 4:
1198            bits = *(uint32_t *)pixels;
1199            break;
1200        case 3:
1201        {
1202#if defined(HAVE_ENDIAN_H)
1203            if(__BYTE_ORDER == __BIG_ENDIAN)
1204#else
1205            /* This is compile-time optimised with at least -O1 or -Os */
1206            uint32_t const tmp = 0x12345678;
1207            if(*(uint8_t const *)&tmp == 0x12)
1208#endif
1209                bits = ((uint32_t)pixels[0] << 16) |
1210                       ((uint32_t)pixels[1] << 8) |
1211                       ((uint32_t)pixels[2]);
1212            else
1213                bits = ((uint32_t)pixels[2] << 16) |
1214                       ((uint32_t)pixels[1] << 8) |
1215                       ((uint32_t)pixels[0]);
1216            break;
1217        }
1218        case 2:
1219            bits = *(uint16_t *)pixels;
1220            break;
1221        case 1:
1222        default:
1223            bits = pixels[0];
1224            break;
1225    }
1226
1227    if(d->has_palette)
1228    {
1229        rgba[0] += d->gammatab[d->red[bits]];
1230        rgba[1] += d->gammatab[d->green[bits]];
1231        rgba[2] += d->gammatab[d->blue[bits]];
1232        rgba[3] += d->alpha[bits];
1233    }
1234    else
1235    {
1236        rgba[0] += d->gammatab[((bits & d->rmask) >> d->rright) << d->rleft];
1237        rgba[1] += d->gammatab[((bits & d->gmask) >> d->gright) << d->gleft];
1238        rgba[2] += d->gammatab[((bits & d->bmask) >> d->bright) << d->bleft];
1239        rgba[3] += ((bits & d->amask) >> d->aright) << d->aleft;
1240    }
1241}
1242
1243/*
1244 * No dithering
1245 */
1246static void init_no_dither(int line)
1247{
1248    ;
1249}
1250
1251static unsigned int get_no_dither(void)
1252{
1253    return 0x80;
1254}
1255
1256static void increment_no_dither(void)
1257{
1258    return;
1259}
1260
1261/*
1262 * Floyd-Steinberg dithering
1263 */
1264static void init_fstein_dither(int line)
1265{
1266    ;
1267}
1268
1269static unsigned int get_fstein_dither(void)
1270{
1271    return 0x80;
1272}
1273
1274static void increment_fstein_dither(void)
1275{
1276    return;
1277}
1278
1279/*
1280 * Ordered 2 dithering
1281 */
1282static unsigned int const *ordered2_table;
1283static unsigned int ordered2_index;
1284
1285static void init_ordered2_dither(int line)
1286{
1287    static unsigned int const dither2x2[] =
1288    {
1289        0x00, 0x80,
1290        0xc0, 0x40,
1291    };
1292
1293    ordered2_table = dither2x2 + (line % 2) * 2;
1294    ordered2_index = 0;
1295}
1296
1297static unsigned int get_ordered2_dither(void)
1298{
1299    return ordered2_table[ordered2_index];
1300}
1301
1302static void increment_ordered2_dither(void)
1303{
1304    ordered2_index = (ordered2_index + 1) % 2;
1305}
1306
1307/*
1308 * Ordered 4 dithering
1309 */
1310/*static int dither4x4[] = { 5,  0,  1,  6,
1311                          -1, -6, -5,  2,
1312                          -2, -7, -8,  3,
1313                           4, -3, -4, -7};*/
1314static unsigned int const *ordered4_table;
1315static unsigned int ordered4_index;
1316
1317static void init_ordered4_dither(int line)
1318{
1319    static unsigned int const dither4x4[] =
1320    {
1321        0x00, 0x80, 0x20, 0xa0,
1322        0xc0, 0x40, 0xe0, 0x60,
1323        0x30, 0xb0, 0x10, 0x90,
1324        0xf0, 0x70, 0xd0, 0x50
1325    };
1326
1327    ordered4_table = dither4x4 + (line % 4) * 4;
1328    ordered4_index = 0;
1329}
1330
1331static unsigned int get_ordered4_dither(void)
1332{
1333    return ordered4_table[ordered4_index];
1334}
1335
1336static void increment_ordered4_dither(void)
1337{
1338    ordered4_index = (ordered4_index + 1) % 4;
1339}
1340
1341/*
1342 * Ordered 8 dithering
1343 */
1344static unsigned int const *ordered8_table;
1345static unsigned int ordered8_index;
1346
1347static void init_ordered8_dither(int line)
1348{
1349    static unsigned int const dither8x8[] =
1350    {
1351        0x00, 0x80, 0x20, 0xa0, 0x08, 0x88, 0x28, 0xa8,
1352        0xc0, 0x40, 0xe0, 0x60, 0xc8, 0x48, 0xe8, 0x68,
1353        0x30, 0xb0, 0x10, 0x90, 0x38, 0xb8, 0x18, 0x98,
1354        0xf0, 0x70, 0xd0, 0x50, 0xf8, 0x78, 0xd8, 0x58,
1355        0x0c, 0x8c, 0x2c, 0xac, 0x04, 0x84, 0x24, 0xa4,
1356        0xcc, 0x4c, 0xec, 0x6c, 0xc4, 0x44, 0xe4, 0x64,
1357        0x3c, 0xbc, 0x1c, 0x9c, 0x34, 0xb4, 0x14, 0x94,
1358        0xfc, 0x7c, 0xdc, 0x5c, 0xf4, 0x74, 0xd4, 0x54,
1359    };
1360
1361    ordered8_table = dither8x8 + (line % 8) * 8;
1362    ordered8_index = 0;
1363}
1364
1365static unsigned int get_ordered8_dither(void)
1366{
1367    return ordered8_table[ordered8_index];
1368}
1369
1370static void increment_ordered8_dither(void)
1371{
1372    ordered8_index = (ordered8_index + 1) % 8;
1373}
1374
1375/*
1376 * Random dithering
1377 */
1378static void init_random_dither(int line)
1379{
1380    ;
1381}
1382
1383static unsigned int get_random_dither(void)
1384{
1385    return cucul_rand(0x00, 0x100);
1386}
1387
1388static void increment_random_dither(void)
1389{
1390    return;
1391}
1392
1393#if !defined(_DOXYGEN_SKIP_ME)
1394int _cucul_init_dither(void)
1395{
1396    unsigned int v, s, h;
1397
1398    /* These ones are constant */
1399    lookup_colors[0] = CUCUL_COLOR_BLACK;
1400    lookup_colors[1] = CUCUL_COLOR_DARKGRAY;
1401    lookup_colors[2] = CUCUL_COLOR_LIGHTGRAY;
1402    lookup_colors[3] = CUCUL_COLOR_WHITE;
1403
1404    /* These ones will be overwritten */
1405    lookup_colors[4] = CUCUL_COLOR_MAGENTA;
1406    lookup_colors[5] = CUCUL_COLOR_LIGHTMAGENTA;
1407    lookup_colors[6] = CUCUL_COLOR_RED;
1408    lookup_colors[7] = CUCUL_COLOR_LIGHTRED;
1409
1410    for(v = 0; v < LOOKUP_VAL; v++)
1411        for(s = 0; s < LOOKUP_SAT; s++)
1412            for(h = 0; h < LOOKUP_HUE; h++)
1413    {
1414        int i, distbg, distfg, dist;
1415        int val, sat, hue;
1416        unsigned char outbg, outfg;
1417
1418        val = 0xfff * v / (LOOKUP_VAL - 1);
1419        sat = 0xfff * s / (LOOKUP_SAT - 1);
1420        hue = 0xfff * h / (LOOKUP_HUE - 1);
1421
1422        /* Initialise distances to the distance between pure black HSV
1423         * coordinates and our white colour (3) */
1424        outbg = outfg = 3;
1425        distbg = distfg = HSV_DISTANCE(0, 0, 0, 3);
1426
1427        /* Calculate distances to eight major colour values and store the
1428         * two nearest points in our lookup table. */
1429        for(i = 0; i < 8; i++)
1430        {
1431            dist = HSV_DISTANCE(hue, sat, val, i);
1432            if(dist <= distbg)
1433            {
1434                outfg = outbg;
1435                distfg = distbg;
1436                outbg = i;
1437                distbg = dist;
1438            }
1439            else if(dist <= distfg)
1440            {
1441                outfg = i;
1442                distfg = dist;
1443            }
1444        }
1445
1446        hsv_distances[v][s][h] = (outfg << 4) | outbg;
1447    }
1448
1449    return 0;
1450}
1451
1452int _cucul_end_dither(void)
1453{
1454    return 0;
1455}
1456#endif /* _DOXYGEN_SKIP_ME */
1457
1458
Note: See TracBrowser for help on using the repository browser.