Pillow

1
/* Copyright (c) 2010 Oliver Tonnhofer <olt@bogosoft.com>, Omniscale
2
//
3
// Permission is hereby granted, free of charge, to any person obtaining a copy
4
// of this software and associated documentation files (the "Software"), to deal
5
// in the Software without restriction, including without limitation the rights
6
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
7
// copies of the Software, and to permit persons to whom the Software is
8
// furnished to do so, subject to the following conditions:
9
//
10
// The above copyright notice and this permission notice shall be included in
11
// all copies or substantial portions of the Software.
12
//
13
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
14
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
18
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
19
// THE SOFTWARE.
20
*/
21

22
/*
23
// This file implements a variation of the octree color quantization algorithm.
24
*/
25

26
#include <stdio.h>
27
#include <stdlib.h>
28
#include <string.h>
29
#include <limits.h>
30

31
#include "ImagingUtils.h"
32
#include "QuantOctree.h"
33

34
typedef struct _ColorBucket {
35
    /* contains palette index when used for look up cube */
36
    uint32_t count;
37
    uint64_t r;
38
    uint64_t g;
39
    uint64_t b;
40
    uint64_t a;
41
} *ColorBucket;
42

43
typedef struct _ColorCube {
44
    unsigned int rBits, gBits, bBits, aBits;
45
    unsigned int rWidth, gWidth, bWidth, aWidth;
46
    unsigned int rOffset, gOffset, bOffset, aOffset;
47

48
    unsigned long size;
49
    ColorBucket buckets;
50
} *ColorCube;
51

52
#define MAX(a, b) (a) > (b) ? (a) : (b)
53

54
static ColorCube
55
new_color_cube(int r, int g, int b, int a) {
56
    ColorCube cube;
57

58
    /* malloc check ok, small constant allocation */
59
    cube = malloc(sizeof(struct _ColorCube));
60
    if (!cube) {
61
        return NULL;
62
    }
63

64
    cube->rBits = MAX(r, 0);
65
    cube->gBits = MAX(g, 0);
66
    cube->bBits = MAX(b, 0);
67
    cube->aBits = MAX(a, 0);
68

69
    /* overflow check for size multiplication below */
70
    if (cube->rBits + cube->gBits + cube->bBits + cube->aBits > 31) {
71
        free(cube);
72
        return NULL;
73
    }
74

75
    /* the width of the cube for each dimension */
76
    cube->rWidth = 1 << cube->rBits;
77
    cube->gWidth = 1 << cube->gBits;
78
    cube->bWidth = 1 << cube->bBits;
79
    cube->aWidth = 1 << cube->aBits;
80

81
    /* the offsets of each color */
82

83
    cube->rOffset = cube->gBits + cube->bBits + cube->aBits;
84
    cube->gOffset = cube->bBits + cube->aBits;
85
    cube->bOffset = cube->aBits;
86
    cube->aOffset = 0;
87

88
    /* the number of color buckets */
89
    cube->size = cube->rWidth * cube->gWidth * cube->bWidth * cube->aWidth;
90
    /* malloc check ok, overflow checked above */
91
    cube->buckets = calloc(cube->size, sizeof(struct _ColorBucket));
92

93
    if (!cube->buckets) {
94
        free(cube);
95
        return NULL;
96
    }
97
    return cube;
98
}
99

100
static void
101
free_color_cube(ColorCube cube) {
102
    if (cube != NULL) {
103
        free(cube->buckets);
104
        free(cube);
105
    }
106
}
107

108
static long
109
color_bucket_offset_pos(
110
    const ColorCube cube, unsigned int r, unsigned int g, unsigned int b, unsigned int a
111
) {
112
    return r << cube->rOffset | g << cube->gOffset | b << cube->bOffset |
113
           a << cube->aOffset;
114
}
115

116
static long
117
color_bucket_offset(const ColorCube cube, const Pixel *p) {
118
    unsigned int r = p->c.r >> (8 - cube->rBits);
119
    unsigned int g = p->c.g >> (8 - cube->gBits);
120
    unsigned int b = p->c.b >> (8 - cube->bBits);
121
    unsigned int a = p->c.a >> (8 - cube->aBits);
122
    return color_bucket_offset_pos(cube, r, g, b, a);
123
}
124

125
static ColorBucket
126
color_bucket_from_cube(const ColorCube cube, const Pixel *p) {
127
    unsigned int offset = color_bucket_offset(cube, p);
128
    return &cube->buckets[offset];
129
}
130

131
static void
132
add_color_to_color_cube(const ColorCube cube, const Pixel *p) {
133
    ColorBucket bucket = color_bucket_from_cube(cube, p);
134
    bucket->count += 1;
135
    bucket->r += p->c.r;
136
    bucket->g += p->c.g;
137
    bucket->b += p->c.b;
138
    bucket->a += p->c.a;
139
}
140

141
static unsigned long
142
count_used_color_buckets(const ColorCube cube) {
143
    unsigned long usedBuckets = 0;
144
    unsigned long i;
145
    for (i = 0; i < cube->size; i++) {
146
        if (cube->buckets[i].count > 0) {
147
            usedBuckets += 1;
148
        }
149
    }
150
    return usedBuckets;
151
}
152

153
static void
154
avg_color_from_color_bucket(const ColorBucket bucket, Pixel *dst) {
155
    float count = bucket->count;
156
    if (count != 0) {
157
        dst->c.r = CLIP8((int)(bucket->r / count));
158
        dst->c.g = CLIP8((int)(bucket->g / count));
159
        dst->c.b = CLIP8((int)(bucket->b / count));
160
        dst->c.a = CLIP8((int)(bucket->a / count));
161
    } else {
162
        dst->c.r = 0;
163
        dst->c.g = 0;
164
        dst->c.b = 0;
165
        dst->c.a = 0;
166
    }
167
}
168

169
static int
170
compare_bucket_count(const ColorBucket a, const ColorBucket b) {
171
    return b->count - a->count;
172
}
173

174
static ColorBucket
175
create_sorted_color_palette(const ColorCube cube) {
176
    ColorBucket buckets;
177
    if (cube->size > LONG_MAX / sizeof(struct _ColorBucket)) {
178
        return NULL;
179
    }
180
    /* malloc check ok, calloc + overflow check above for memcpy */
181
    buckets = calloc(cube->size, sizeof(struct _ColorBucket));
182
    if (!buckets) {
183
        return NULL;
184
    }
185
    memcpy(buckets, cube->buckets, sizeof(struct _ColorBucket) * cube->size);
186

187
    qsort(
188
        buckets,
189
        cube->size,
190
        sizeof(struct _ColorBucket),
191
        (int (*)(void const *, void const *)) & compare_bucket_count
192
    );
193

194
    return buckets;
195
}
196

197
void
198
add_bucket_values(ColorBucket src, ColorBucket dst) {
199
    dst->count += src->count;
200
    dst->r += src->r;
201
    dst->g += src->g;
202
    dst->b += src->b;
203
    dst->a += src->a;
204
}
205

206
/* expand or shrink a given cube to level */
207
static ColorCube
208
copy_color_cube(
209
    const ColorCube cube,
210
    unsigned int rBits,
211
    unsigned int gBits,
212
    unsigned int bBits,
213
    unsigned int aBits
214
) {
215
    unsigned int r, g, b, a;
216
    long src_pos, dst_pos;
217
    unsigned int src_reduce[4] = {0}, dst_reduce[4] = {0};
218
    unsigned int width[4];
219
    ColorCube result;
220

221
    result = new_color_cube(rBits, gBits, bBits, aBits);
222
    if (!result) {
223
        return NULL;
224
    }
225

226
    if (cube->rBits > rBits) {
227
        dst_reduce[0] = cube->rBits - result->rBits;
228
        width[0] = cube->rWidth;
229
    } else {
230
        src_reduce[0] = result->rBits - cube->rBits;
231
        width[0] = result->rWidth;
232
    }
233
    if (cube->gBits > gBits) {
234
        dst_reduce[1] = cube->gBits - result->gBits;
235
        width[1] = cube->gWidth;
236
    } else {
237
        src_reduce[1] = result->gBits - cube->gBits;
238
        width[1] = result->gWidth;
239
    }
240
    if (cube->bBits > bBits) {
241
        dst_reduce[2] = cube->bBits - result->bBits;
242
        width[2] = cube->bWidth;
243
    } else {
244
        src_reduce[2] = result->bBits - cube->bBits;
245
        width[2] = result->bWidth;
246
    }
247
    if (cube->aBits > aBits) {
248
        dst_reduce[3] = cube->aBits - result->aBits;
249
        width[3] = cube->aWidth;
250
    } else {
251
        src_reduce[3] = result->aBits - cube->aBits;
252
        width[3] = result->aWidth;
253
    }
254

255
    for (r = 0; r < width[0]; r++) {
256
        for (g = 0; g < width[1]; g++) {
257
            for (b = 0; b < width[2]; b++) {
258
                for (a = 0; a < width[3]; a++) {
259
                    src_pos = color_bucket_offset_pos(
260
                        cube,
261
                        r >> src_reduce[0],
262
                        g >> src_reduce[1],
263
                        b >> src_reduce[2],
264
                        a >> src_reduce[3]
265
                    );
266
                    dst_pos = color_bucket_offset_pos(
267
                        result,
268
                        r >> dst_reduce[0],
269
                        g >> dst_reduce[1],
270
                        b >> dst_reduce[2],
271
                        a >> dst_reduce[3]
272
                    );
273
                    add_bucket_values(
274
                        &cube->buckets[src_pos], &result->buckets[dst_pos]
275
                    );
276
                }
277
            }
278
        }
279
    }
280
    return result;
281
}
282

283
void
284
subtract_color_buckets(ColorCube cube, ColorBucket buckets, long nBuckets) {
285
    ColorBucket minuend, subtrahend;
286
    long i;
287
    Pixel p;
288
    for (i = 0; i < nBuckets; i++) {
289
        subtrahend = &buckets[i];
290

291
        // If the subtrahend contains no buckets, there is nothing to subtract.
292
        if (subtrahend->count == 0) {
293
            continue;
294
        }
295

296
        avg_color_from_color_bucket(subtrahend, &p);
297
        minuend = color_bucket_from_cube(cube, &p);
298
        minuend->count -= subtrahend->count;
299
        minuend->r -= subtrahend->r;
300
        minuend->g -= subtrahend->g;
301
        minuend->b -= subtrahend->b;
302
        minuend->a -= subtrahend->a;
303
    }
304
}
305

306
static void
307
set_lookup_value(const ColorCube cube, const Pixel *p, long value) {
308
    ColorBucket bucket = color_bucket_from_cube(cube, p);
309
    bucket->count = value;
310
}
311

312
uint64_t
313
lookup_color(const ColorCube cube, const Pixel *p) {
314
    ColorBucket bucket = color_bucket_from_cube(cube, p);
315
    return bucket->count;
316
}
317

318
void
319
add_lookup_buckets(ColorCube cube, ColorBucket palette, long nColors, long offset) {
320
    long i;
321
    Pixel p;
322
    for (i = offset + nColors - 1; i >= offset; i--) {
323
        avg_color_from_color_bucket(&palette[i], &p);
324
        set_lookup_value(cube, &p, i);
325
    }
326
}
327

328
ColorBucket
329
combined_palette(
330
    ColorBucket bucketsA,
331
    unsigned long nBucketsA,
332
    ColorBucket bucketsB,
333
    unsigned long nBucketsB
334
) {
335
    ColorBucket result;
336
    if (nBucketsA > LONG_MAX - nBucketsB ||
337
        (nBucketsA + nBucketsB) > LONG_MAX / sizeof(struct _ColorBucket)) {
338
        return NULL;
339
    }
340
    /* malloc check ok, overflow check above */
341
    result = calloc(nBucketsA + nBucketsB, sizeof(struct _ColorBucket));
342
    if (!result) {
343
        return NULL;
344
    }
345
    memcpy(result, bucketsA, sizeof(struct _ColorBucket) * nBucketsA);
346
    memcpy(&result[nBucketsA], bucketsB, sizeof(struct _ColorBucket) * nBucketsB);
347
    return result;
348
}
349

350
static Pixel *
351
create_palette_array(const ColorBucket palette, unsigned int paletteLength) {
352
    Pixel *paletteArray;
353
    unsigned int i;
354

355
    /* malloc check ok, calloc for overflow */
356
    paletteArray = calloc(paletteLength, sizeof(Pixel));
357
    if (!paletteArray) {
358
        return NULL;
359
    }
360

361
    for (i = 0; i < paletteLength; i++) {
362
        avg_color_from_color_bucket(&palette[i], &paletteArray[i]);
363
    }
364
    return paletteArray;
365
}
366

367
static void
368
map_image_pixels(
369
    const Pixel *pixelData,
370
    uint32_t nPixels,
371
    const ColorCube lookupCube,
372
    uint32_t *pixelArray
373
) {
374
    long i;
375
    for (i = 0; i < nPixels; i++) {
376
        pixelArray[i] = lookup_color(lookupCube, &pixelData[i]);
377
    }
378
}
379

380
const unsigned int CUBE_LEVELS[8] = {4, 4, 4, 0, 2, 2, 2, 0};
381
const unsigned int CUBE_LEVELS_ALPHA[8] = {3, 4, 3, 3, 2, 2, 2, 2};
382

383
int
384
quantize_octree(
385
    Pixel *pixelData,
386
    uint32_t nPixels,
387
    uint32_t nQuantPixels,
388
    Pixel **palette,
389
    uint32_t *paletteLength,
390
    uint32_t **quantizedPixels,
391
    int withAlpha
392
) {
393
    ColorCube fineCube = NULL;
394
    ColorCube coarseCube = NULL;
395
    ColorCube lookupCube = NULL;
396
    ColorCube coarseLookupCube = NULL;
397
    ColorBucket paletteBucketsCoarse = NULL;
398
    ColorBucket paletteBucketsFine = NULL;
399
    ColorBucket paletteBuckets = NULL;
400
    uint32_t *qp = NULL;
401
    long i;
402
    unsigned long nCoarseColors, nFineColors, nAlreadySubtracted;
403
    const unsigned int *cubeBits;
404

405
    if (withAlpha) {
406
        cubeBits = CUBE_LEVELS_ALPHA;
407
    } else {
408
        cubeBits = CUBE_LEVELS;
409
    }
410

411
    /*
412
    Create two color cubes, one fine grained with 8x16x8=1024
413
    colors buckets and a coarse with 4x4x4=64 color buckets.
414
    The coarse one guarantees that there are color buckets available for
415
    the whole color range (assuming nQuantPixels > 64).
416

417
    For a quantization to 256 colors all 64 coarse colors will be used
418
    plus the 192 most used color buckets from the fine color cube.
419
    The average of all colors within one bucket is used as the actual
420
    color for that bucket.
421

422
     For images with alpha the cubes gets a forth dimension,
423
     8x16x8x8 and 4x4x4x4.
424
    */
425

426
    /* create fine cube */
427
    fineCube = new_color_cube(cubeBits[0], cubeBits[1], cubeBits[2], cubeBits[3]);
428
    if (!fineCube) {
429
        goto error;
430
    }
431
    for (i = 0; i < nPixels; i++) {
432
        add_color_to_color_cube(fineCube, &pixelData[i]);
433
    }
434

435
    /* create coarse cube */
436
    coarseCube =
437
        copy_color_cube(fineCube, cubeBits[4], cubeBits[5], cubeBits[6], cubeBits[7]);
438
    if (!coarseCube) {
439
        goto error;
440
    }
441
    nCoarseColors = count_used_color_buckets(coarseCube);
442

443
    /* limit to nQuantPixels */
444
    if (nCoarseColors > nQuantPixels) {
445
        nCoarseColors = nQuantPixels;
446
    }
447

448
    /* how many space do we have in our palette for fine colors? */
449
    nFineColors = nQuantPixels - nCoarseColors;
450

451
    /* create fine color palette */
452
    paletteBucketsFine = create_sorted_color_palette(fineCube);
453
    if (!paletteBucketsFine) {
454
        goto error;
455
    }
456

457
    /* remove the used fine colors from the coarse cube */
458
    subtract_color_buckets(coarseCube, paletteBucketsFine, nFineColors);
459

460
    /* did the subtraction cleared one or more coarse bucket? */
461
    while (nCoarseColors > count_used_color_buckets(coarseCube)) {
462
        /* then we can use the free buckets for fine colors */
463
        nAlreadySubtracted = nFineColors;
464
        nCoarseColors = count_used_color_buckets(coarseCube);
465
        nFineColors = nQuantPixels - nCoarseColors;
466
        subtract_color_buckets(
467
            coarseCube,
468
            &paletteBucketsFine[nAlreadySubtracted],
469
            nFineColors - nAlreadySubtracted
470
        );
471
    }
472

473
    /* create our palette buckets with fine and coarse combined */
474
    paletteBucketsCoarse = create_sorted_color_palette(coarseCube);
475
    if (!paletteBucketsCoarse) {
476
        goto error;
477
    }
478
    paletteBuckets = combined_palette(
479
        paletteBucketsCoarse, nCoarseColors, paletteBucketsFine, nFineColors
480
    );
481

482
    free(paletteBucketsFine);
483
    paletteBucketsFine = NULL;
484
    free(paletteBucketsCoarse);
485
    paletteBucketsCoarse = NULL;
486
    if (!paletteBuckets) {
487
        goto error;
488
    }
489

490
    /* add all coarse colors to our coarse lookup cube. */
491
    coarseLookupCube =
492
        new_color_cube(cubeBits[4], cubeBits[5], cubeBits[6], cubeBits[7]);
493
    if (!coarseLookupCube) {
494
        goto error;
495
    }
496
    add_lookup_buckets(coarseLookupCube, paletteBuckets, nCoarseColors, 0);
497

498
    /* expand coarse cube (64) to larger fine cube (4k). the value of each
499
       coarse bucket is then present in the according 64 fine buckets. */
500
    lookupCube = copy_color_cube(
501
        coarseLookupCube, cubeBits[0], cubeBits[1], cubeBits[2], cubeBits[3]
502
    );
503
    if (!lookupCube) {
504
        goto error;
505
    }
506

507
    /* add fine colors to the lookup cube */
508
    add_lookup_buckets(lookupCube, paletteBuckets, nFineColors, nCoarseColors);
509

510
    /* create result pixels and map palette indices */
511
    /* malloc check ok, calloc for overflow */
512
    qp = calloc(nPixels, sizeof(Pixel));
513
    if (!qp) {
514
        goto error;
515
    }
516
    map_image_pixels(pixelData, nPixels, lookupCube, qp);
517

518
    /* convert palette buckets to RGB pixel palette */
519
    *palette = create_palette_array(paletteBuckets, nQuantPixels);
520
    if (!(*palette)) {
521
        goto error;
522
    }
523

524
    *quantizedPixels = qp;
525
    *paletteLength = nQuantPixels;
526

527
    free_color_cube(coarseCube);
528
    free_color_cube(fineCube);
529
    free_color_cube(lookupCube);
530
    free_color_cube(coarseLookupCube);
531
    free(paletteBuckets);
532
    return 1;
533

534
error:
535
    /* everything is initialized to NULL
536
       so we are safe to call free */
537
    free(qp);
538
    free_color_cube(lookupCube);
539
    free_color_cube(coarseLookupCube);
540
    free(paletteBuckets);
541
    free(paletteBucketsCoarse);
542
    free(paletteBucketsFine);
543
    free_color_cube(coarseCube);
544
    free_color_cube(fineCube);
545
    return 0;
546
}
547