client/src/imgutils.c

   1
   2 #include <assert.h>
   3 #include "imgutils.h"
   4
   5 struct ycbcr_t {
   6     int y;
   7     int cb;
   8     int cr;
   9 };
  10
  11 static void rgb_to_ycbcr(int rgb, struct ycbcr_t *ycbcr) {
  12     int r = gdTrueColorGetRed(rgb);
  13     int g = gdTrueColorGetGreen(rgb);
  14     int b = gdTrueColorGetBlue(rgb);
  15
  16     /*
  17      * Below is a fixed-point version of the following code:
  18      * ycbcr->y  = r *  0.29900 + g *  0.58700 + b *  0.11400;
  19      * ycbcr->cb = r * -0.16874 + g * -0.33126 + b *  0.50000 + 128;
  20      * ycbcr->cr = r *  0.50000 + g * -0.41869 + b * -0.08131 + 128;
  21      */
  22
  23     ycbcr->y  = (r *  19595 + g *  38470 + b *  7471) / 65536;
  24     ycbcr->cb = (r * -11059 + g * -21709 + b * 32768) / 65536 + 128;
  25     ycbcr->cr = (r *  32768 + g * -27439 + b * -5329) / 65536 + 128;
  26 }
  27
  28 static inline void cap_comp(int *x) {
  29     if (*x < 0) {
  30         *x = 0;
  31     } else if (*x > 255) {
  32         *x = 255;
  33     }
  34 }
  35
  36 gdImagePtr img_palettize(gdImagePtr rgb, int *palette, int palette_size) {
  37     assert(rgb != NULL);
  38     assert(palette != NULL);
  39     assert(palette_size >= 2 && palette_size < 256);
  40
  41     // Create paletized image
  42     gdImagePtr res = gdImageCreate(gdImageSX(rgb), gdImageSY(rgb));
  43     if (!res) {
  44         return NULL;
  45     }
  46
  47     // Allocate space for palette in YCbCr
  48     struct ycbcr_t *pal_ycbcr = calloc(palette_size, sizeof(struct ycbcr_t));
  49     if (!pal_ycbcr) {
  50         gdImageDestroy(res);
  51         return NULL;
  52     }
  53
  54     /*
  55      * Initialize the column's error array.
  56      *
  57      * Note that we are storing two extra values so we don't have to do boundary checking at
  58      * the left and right edges of the image.
  59      *
  60      * To reduce shifts and increase accuracy, each entry is stored with 16x times the error,
  61      * and gets divided by that amount when it is read.
  62      */
  63     struct ycbcr_t *forward = calloc(gdImageSX(rgb) + 2, sizeof(struct ycbcr_t));
  64     if (!forward) {
  65         free(pal_ycbcr);
  66         gdImageDestroy(res);
  67         return NULL;
  68     }
  69
  70     // Convert palette to YCbCr and allocate in image
  71     for (int i = 0; i < palette_size; i++) {
  72         int c = palette[i];
  73         rgb_to_ycbcr(c, pal_ycbcr + i);
  74         gdImageColorAllocate(res, gdTrueColorGetRed(c), gdTrueColorGetGreen(c), gdTrueColorGetBlue(c));
  75     }
  76
  77     for (int y = 0; y < gdImageSY(rgb); y++) {
  78         // Load current row error and reset its storage
  79         struct ycbcr_t row_err = forward[1];
  80         forward[1].y = forward[1].cb = forward[1].cr = 0;
  81
  82         for (int x = 0; x < gdImageSX(rgb); x++) {
  83             struct ycbcr_t pix;
  84             rgb_to_ycbcr(gdImageGetTrueColorPixel(rgb, x, y), &pix);
  85
  86             // Add error for current pixel
  87             pix.y  += row_err.y  / 16;
  88             pix.cb += row_err.cb / 16;
  89             pix.cr += row_err.cr / 16;
  90
  91             // Cap in case it went to imaginary color territory
  92             cap_comp(&pix.y);
  93             cap_comp(&pix.cb);
  94             cap_comp(&pix.cr);
  95
  96             /*
  97              * Iterate through all candidate colors and find the nearest one using the
  98              * squared Euclidean distance.
  99              */
 100             int best_idx = 0;
 101             struct ycbcr_t best_err = { 0 };
 102             int best_score = 0x7FFFFFFF;
 103             for (int can_idx = 0; can_idx < palette_size; can_idx++) {
 104                 struct ycbcr_t can_err = {
 105                     .y  = pix.y  - pal_ycbcr[can_idx].y,
 106                     .cb = pix.cb - pal_ycbcr[can_idx].cb,
 107                     .cr = pix.cr - pal_ycbcr[can_idx].cr,
 108                 };
 109
 110                 int can_score = (
 111                                     can_err.y  * can_err.y  +
 112                                     can_err.cb * can_err.cb +
 113                                     can_err.cr * can_err.cr
 114                                 );
 115
 116                 if (can_score < best_score) {
 117                     best_idx   = can_idx;
 118                     best_score = can_score;
 119                     best_err   = can_err;
 120                 }
 121             }
 122
 123             // Set current pixel
 124             gdImageSetPixel(res, x, y, best_idx);
 125
 126             // Propagate error within the current row, to the pixel to the right
 127             row_err.y  = best_err.y  * 7 + forward[x + 2].y;
 128             row_err.cb = best_err.cb * 7 + forward[x + 2].cb;
 129             row_err.cr = best_err.cr * 7 + forward[x + 2].cr;
 130
 131             // Add error to bottom left
 132             forward[x + 0].y  += best_err.y  * 3;
 133             forward[x + 0].cb += best_err.cb * 3;
 134             forward[x + 0].cr += best_err.cr * 3;
 135
 136             // Add error to bottom center
 137             forward[x + 1].y  += best_err.y  * 5;
 138             forward[x + 1].cb += best_err.cb * 5;
 139             forward[x + 1].cr += best_err.cr * 5;
 140
 141             // Set error to bottom right
 142             forward[x + 2].y   = best_err.y  * 1;
 143             forward[x + 2].cb  = best_err.cb * 1;
 144             forward[x + 2].cr  = best_err.cr * 1;
 145         }
 146     }
 147
 148     free(forward);
 149     free(pal_ycbcr);
 150     return res;
 151 }
 152
 153 gdImagePtr img_crop_to_fit(gdImagePtr orig, int width, int height) {
 154     assert(orig != NULL);
 155     assert(width >= 1);
 156     assert(height >= 1);
 157
 158     gdImagePtr res;
 159     if (gdImageTrueColor(orig)) {
 160         res = gdImageCreateTrueColor(width, height);
 161     } else {
 162         res = gdImageCreate(width, height);
 163     }
 164
 165     if (!res) {
 166         return NULL;
 167     }
 168
 169     if (gdImageSY(orig) * width <= gdImageSX(orig) * height) {
 170         // Image is wider than expected, so we will crop the left and right sides
 171
 172         int crop_width = gdImageSY(orig) * width / height;
 173         int crop_sx = gdImageSX(orig) / 2 - crop_width / 2;
 174         gdImageCopyResampled(
 175             res,             // Dest img
 176             orig,            // Src image
 177             0,               // Dest X
 178             0,               // Dest Y
 179             crop_sx,         // Src X
 180             0,               // Src Y
 181             width,           // Dest width
 182             height,          // Dest height
 183             crop_width,      // Src width
 184             gdImageSY(orig)  // Src height
 185         );
 186     } else {
 187         // Image is taller than expected, so we will crop the top and bottom sides
 188
 189         int crop_height = gdImageSX(orig) * height / width;
 190         int crop_sy = gdImageSY(orig) / 2 - crop_height / 2;
 191         gdImageCopyResampled(
 192             res,             // Dest img
 193             orig,            // Src image
 194             0,               // Dest X
 195             0,               // Dest Y
 196             0,               // Src X
 197             crop_sy,         // Src Y
 198             width,           // Dest width
 199             height,          // Dest height
 200             gdImageSX(orig), // Src width
 201             crop_height      // Src height
 202         );
 203     }
 204
 205     return res;
 206 }