Coverage Report

Created: 2025-06-09 07:07

/src/gdal/alg/gdalmediancut.cpp
Line
Count
Source (jump to first uncovered line)
1
/******************************************************************************
2
 *
3
 * Project:  CIETMap Phase 2
4
 * Purpose:  Use median cut algorithm to generate an near-optimal PCT for a
5
 *           given RGB image.  Implemented as function GDALComputeMedianCutPCT.
6
 * Author:   Frank Warmerdam, warmerdam@pobox.com
7
 *
8
 ******************************************************************************
9
 * Copyright (c) 2001, Frank Warmerdam
10
 * Copyright (c) 2007-2010, Even Rouault <even dot rouault at spatialys.com>
11
 *
12
 * SPDX-License-Identifier: MIT
13
 ******************************************************************************
14
 *
15
 * This code was based on the tiffmedian.c code from libtiff (www.libtiff.org)
16
 * which was based on a paper by Paul Heckbert:
17
 *
18
 *      "Color  Image Quantization for Frame Buffer Display", Paul
19
 *      Heckbert, SIGGRAPH proceedings, 1982, pp. 297-307.
20
 *
21
 */
22
23
#include "cpl_port.h"
24
#include "gdal_alg.h"
25
#include "gdal_alg_priv.h"
26
27
#include <climits>
28
#include <cstring>
29
30
#include <algorithm>
31
#include <limits>
32
33
#include "cpl_conv.h"
34
#include "cpl_error.h"
35
#include "cpl_float.h"
36
#include "cpl_progress.h"
37
#include "cpl_vsi.h"
38
#include "gdal.h"
39
#include "gdal_priv.h"
40
41
template <typename T> static T *HISTOGRAM(T *h, int n, int r, int g, int b)
42
0
{
43
0
    const int index = (r * n + g) * n + b;
44
0
    return &h[index];
45
0
}
Unexecuted instantiation: gdalmediancut.cpp:unsigned int* HISTOGRAM<unsigned int>(unsigned int*, int, int, int, int)
Unexecuted instantiation: gdalmediancut.cpp:unsigned int const* HISTOGRAM<unsigned int const>(unsigned int const*, int, int, int, int)
Unexecuted instantiation: gdalmediancut.cpp:unsigned long long* HISTOGRAM<unsigned long long>(unsigned long long*, int, int, int, int)
Unexecuted instantiation: gdalmediancut.cpp:unsigned long long const* HISTOGRAM<unsigned long long const>(unsigned long long const*, int, int, int, int)
46
47
#ifndef MAKE_COLOR_CODE_defined
48
#define MAKE_COLOR_CODE_defined
49
50
static int MAKE_COLOR_CODE(int r, int g, int b)
51
0
{
52
0
    return r | (g << 8) | (b << 16);
53
0
}
54
#endif
55
56
// NOTE: If changing the size of this structure, edit
57
// MEDIAN_CUT_AND_DITHER_BUFFER_SIZE_65536 in gdal_alg_priv.h and take into
58
// account ColorIndex in gdaldither.cpp.
59
typedef struct
60
{
61
    GUInt32 nColorCode;
62
    int nCount;
63
    GUInt32 nColorCode2;
64
    int nCount2;
65
    GUInt32 nColorCode3;
66
    int nCount3;
67
} HashHistogram;
68
69
typedef struct colorbox
70
{
71
    struct colorbox *next, *prev;
72
    int rmin, rmax;
73
    int gmin, gmax;
74
    int bmin, bmax;
75
    GUIntBig total;
76
} Colorbox;
77
78
template <class T>
79
static void splitbox(Colorbox *ptr, const T *histogram,
80
                     const HashHistogram *psHashHistogram, int nCLevels,
81
                     Colorbox **pfreeboxes, Colorbox **pusedboxes,
82
                     GByte *pabyRedBand, GByte *pabyGreenBand,
83
                     GByte *pabyBlueBand, T nPixels);
84
85
template <class T>
86
static void shrinkbox(Colorbox *box, const T *histogram, int nCLevels);
87
88
static Colorbox *largest_box(Colorbox *usedboxes);
89
90
/************************************************************************/
91
/*                      GDALComputeMedianCutPCT()                       */
92
/************************************************************************/
93
94
/**
95
 * Compute optimal PCT for RGB image.
96
 *
97
 * This function implements a median cut algorithm to compute an "optimal"
98
 * pseudocolor table for representing an input RGB image.  This PCT could
99
 * then be used with GDALDitherRGB2PCT() to convert a 24bit RGB image into
100
 * an eightbit pseudo-colored image.
101
 *
102
 * This code was based on the tiffmedian.c code from libtiff (www.libtiff.org)
103
 * which was based on a paper by Paul Heckbert:
104
 *
105
 * \verbatim
106
 *   "Color  Image Quantization for Frame Buffer Display", Paul
107
 *   Heckbert, SIGGRAPH proceedings, 1982, pp. 297-307.
108
 * \endverbatim
109
 *
110
 * The red, green and blue input bands do not necessarily need to come
111
 * from the same file, but they must be the same width and height.  They will
112
 * be clipped to 8bit during reading, so non-eight bit bands are generally
113
 * inappropriate.
114
 *
115
 * @param hRed Red input band.
116
 * @param hGreen Green input band.
117
 * @param hBlue Blue input band.
118
 * @param pfnIncludePixel function used to test which pixels should be included
119
 * in the analysis.  At this time this argument is ignored and all pixels are
120
 * utilized.  This should normally be NULL.
121
 * @param nColors the desired number of colors to be returned (2-256).
122
 * @param hColorTable the colors will be returned in this color table object.
123
 * @param pfnProgress callback for reporting algorithm progress matching the
124
 * GDALProgressFunc() semantics.  May be NULL.
125
 * @param pProgressArg callback argument passed to pfnProgress.
126
 *
127
 * @return returns CE_None on success or CE_Failure if an error occurs.
128
 */
129
130
extern "C" int CPL_STDCALL GDALComputeMedianCutPCT(
131
    GDALRasterBandH hRed, GDALRasterBandH hGreen, GDALRasterBandH hBlue,
132
    int (*pfnIncludePixel)(int, int, void *), int nColors,
133
    GDALColorTableH hColorTable, GDALProgressFunc pfnProgress,
134
    void *pProgressArg)
135
136
0
{
137
0
    VALIDATE_POINTER1(hRed, "GDALComputeMedianCutPCT", CE_Failure);
138
0
    const int nXSize = GDALGetRasterBandXSize(hRed);
139
0
    const int nYSize = GDALGetRasterBandYSize(hRed);
140
0
    if (nYSize == 0)
141
0
        return CE_Failure;
142
0
    if (static_cast<GUInt32>(nXSize) <
143
0
        std::numeric_limits<GUInt32>::max() / static_cast<GUInt32>(nYSize))
144
0
    {
145
0
        return GDALComputeMedianCutPCTInternal(
146
0
            hRed, hGreen, hBlue, nullptr, nullptr, nullptr, pfnIncludePixel,
147
0
            nColors, 5, static_cast<GUInt32 *>(nullptr), hColorTable,
148
0
            pfnProgress, pProgressArg);
149
0
    }
150
0
    else
151
0
    {
152
0
        return GDALComputeMedianCutPCTInternal(
153
0
            hRed, hGreen, hBlue, nullptr, nullptr, nullptr, pfnIncludePixel,
154
0
            nColors, 5, static_cast<GUIntBig *>(nullptr), hColorTable,
155
0
            pfnProgress, pProgressArg);
156
0
    }
157
0
}
158
159
#ifndef IsColorCodeSet_defined
160
#define IsColorCodeSet_defined
161
162
static inline bool IsColorCodeSet(GUInt32 nColorCode)
163
0
{
164
0
    return (nColorCode >> 31) == 0;
165
0
}
166
#endif
167
168
static inline int FindColorCount(const HashHistogram *psHashHistogram,
169
                                 GUInt32 nColorCode)
170
0
{
171
172
0
    GUInt32 nIdx = nColorCode % PRIME_FOR_65536;
173
0
    while (true)
174
0
    {
175
0
        if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode))
176
0
        {
177
0
            return 0;
178
0
        }
179
0
        if (psHashHistogram[nIdx].nColorCode == nColorCode)
180
0
        {
181
0
            return psHashHistogram[nIdx].nCount;
182
0
        }
183
0
        if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode2))
184
0
        {
185
0
            return 0;
186
0
        }
187
0
        if (psHashHistogram[nIdx].nColorCode2 == nColorCode)
188
0
        {
189
0
            return psHashHistogram[nIdx].nCount2;
190
0
        }
191
0
        if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode3))
192
0
        {
193
0
            return 0;
194
0
        }
195
0
        if (psHashHistogram[nIdx].nColorCode3 == nColorCode)
196
0
        {
197
0
            return psHashHistogram[nIdx].nCount3;
198
0
        }
199
200
0
        do
201
0
        {
202
0
            nIdx += 257;
203
0
            if (nIdx >= PRIME_FOR_65536)
204
0
                nIdx -= PRIME_FOR_65536;
205
0
        } while (IsColorCodeSet(psHashHistogram[nIdx].nColorCode) &&
206
0
                 psHashHistogram[nIdx].nColorCode != nColorCode &&
207
0
                 IsColorCodeSet(psHashHistogram[nIdx].nColorCode2) &&
208
0
                 psHashHistogram[nIdx].nColorCode2 != nColorCode &&
209
0
                 IsColorCodeSet(psHashHistogram[nIdx].nColorCode3) &&
210
0
                 psHashHistogram[nIdx].nColorCode3 != nColorCode);
211
0
    }
212
0
}
213
214
static inline int *FindAndInsertColorCount(HashHistogram *psHashHistogram,
215
                                           GUInt32 nColorCode)
216
0
{
217
0
    GUInt32 nIdx = nColorCode % PRIME_FOR_65536;
218
0
    while (true)
219
0
    {
220
0
        if (psHashHistogram[nIdx].nColorCode == nColorCode)
221
0
        {
222
0
            return &(psHashHistogram[nIdx].nCount);
223
0
        }
224
0
        if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode))
225
0
        {
226
0
            psHashHistogram[nIdx].nColorCode = nColorCode;
227
0
            psHashHistogram[nIdx].nCount = 0;
228
0
            return &(psHashHistogram[nIdx].nCount);
229
0
        }
230
0
        if (psHashHistogram[nIdx].nColorCode2 == nColorCode)
231
0
        {
232
0
            return &(psHashHistogram[nIdx].nCount2);
233
0
        }
234
0
        if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode2))
235
0
        {
236
0
            psHashHistogram[nIdx].nColorCode2 = nColorCode;
237
0
            psHashHistogram[nIdx].nCount2 = 0;
238
0
            return &(psHashHistogram[nIdx].nCount2);
239
0
        }
240
0
        if (psHashHistogram[nIdx].nColorCode3 == nColorCode)
241
0
        {
242
0
            return &(psHashHistogram[nIdx].nCount3);
243
0
        }
244
0
        if (!IsColorCodeSet(psHashHistogram[nIdx].nColorCode3))
245
0
        {
246
0
            psHashHistogram[nIdx].nColorCode3 = nColorCode;
247
0
            psHashHistogram[nIdx].nCount3 = 0;
248
0
            return &(psHashHistogram[nIdx].nCount3);
249
0
        }
250
251
0
        do
252
0
        {
253
0
            nIdx += 257;
254
0
            if (nIdx >= PRIME_FOR_65536)
255
0
                nIdx -= PRIME_FOR_65536;
256
0
        } while (IsColorCodeSet(psHashHistogram[nIdx].nColorCode) &&
257
0
                 psHashHistogram[nIdx].nColorCode != nColorCode &&
258
0
                 IsColorCodeSet(psHashHistogram[nIdx].nColorCode2) &&
259
0
                 psHashHistogram[nIdx].nColorCode2 != nColorCode &&
260
0
                 IsColorCodeSet(psHashHistogram[nIdx].nColorCode3) &&
261
0
                 psHashHistogram[nIdx].nColorCode3 != nColorCode);
262
0
    }
263
0
}
264
265
template <class T>
266
int GDALComputeMedianCutPCTInternal(
267
    GDALRasterBandH hRed, GDALRasterBandH hGreen, GDALRasterBandH hBlue,
268
    GByte *pabyRedBand, GByte *pabyGreenBand, GByte *pabyBlueBand,
269
    int (*pfnIncludePixel)(int, int, void *), int nColors, int nBits,
270
    T *panHistogram,  // NULL, or >= size (1<<nBits)^3 * sizeof(T) bytes.
271
    GDALColorTableH hColorTable, GDALProgressFunc pfnProgress,
272
    void *pProgressArg)
273
274
0
{
275
0
    VALIDATE_POINTER1(hRed, "GDALComputeMedianCutPCT", CE_Failure);
276
0
    VALIDATE_POINTER1(hGreen, "GDALComputeMedianCutPCT", CE_Failure);
277
0
    VALIDATE_POINTER1(hBlue, "GDALComputeMedianCutPCT", CE_Failure);
278
279
0
    CPLErr err = CE_None;
280
281
    /* -------------------------------------------------------------------- */
282
    /*      Validate parameters.                                            */
283
    /* -------------------------------------------------------------------- */
284
0
    const int nXSize = GDALGetRasterBandXSize(hRed);
285
0
    const int nYSize = GDALGetRasterBandYSize(hRed);
286
287
0
    if (GDALGetRasterBandXSize(hGreen) != nXSize ||
288
0
        GDALGetRasterBandYSize(hGreen) != nYSize ||
289
0
        GDALGetRasterBandXSize(hBlue) != nXSize ||
290
0
        GDALGetRasterBandYSize(hBlue) != nYSize)
291
0
    {
292
0
        CPLError(CE_Failure, CPLE_IllegalArg,
293
0
                 "Green or blue band doesn't match size of red band.");
294
295
0
        return CE_Failure;
296
0
    }
297
298
0
    if (pfnIncludePixel != nullptr)
299
0
    {
300
0
        CPLError(CE_Failure, CPLE_IllegalArg,
301
0
                 "GDALComputeMedianCutPCT() doesn't currently support "
302
0
                 "pfnIncludePixel function.");
303
304
0
        return CE_Failure;
305
0
    }
306
307
0
    if (nColors <= 0)
308
0
    {
309
0
        CPLError(CE_Failure, CPLE_IllegalArg,
310
0
                 "GDALComputeMedianCutPCT(): "
311
0
                 "nColors must be strictly greater than 1.");
312
313
0
        return CE_Failure;
314
0
    }
315
316
0
    if (nColors > 256)
317
0
    {
318
0
        CPLError(CE_Failure, CPLE_IllegalArg,
319
0
                 "GDALComputeMedianCutPCT(): "
320
0
                 "nColors must be lesser than or equal to 256.");
321
322
0
        return CE_Failure;
323
0
    }
324
325
0
    if (pfnProgress == nullptr)
326
0
        pfnProgress = GDALDummyProgress;
327
328
    /* ==================================================================== */
329
    /*      STEP 1: create empty boxes.                                     */
330
    /* ==================================================================== */
331
0
    if (static_cast<GUInt32>(nXSize) >
332
0
        cpl::NumericLimits<T>::max() / static_cast<GUInt32>(nYSize))
333
0
    {
334
0
        CPLError(CE_Warning, CPLE_AppDefined,
335
0
                 "GDALComputeMedianCutPCTInternal() not called "
336
0
                 "with large enough type");
337
0
    }
338
339
0
    T nPixels = 0;
340
0
    if (nBits == 8 && pabyRedBand != nullptr && pabyGreenBand != nullptr &&
341
0
        pabyBlueBand != nullptr &&
342
0
        static_cast<GUInt32>(nXSize) <=
343
0
            cpl::NumericLimits<T>::max() / static_cast<GUInt32>(nYSize))
344
0
    {
345
0
        nPixels = static_cast<T>(nXSize) * static_cast<T>(nYSize);
346
0
    }
347
348
0
    const int nCLevels = 1 << nBits;
349
0
    const int nCLevelsCube = nCLevels * nCLevels * nCLevels;
350
0
    T *histogram = nullptr;
351
0
    HashHistogram *psHashHistogram = nullptr;
352
0
    if (panHistogram)
353
0
    {
354
0
        if (nBits == 8 && static_cast<GUIntBig>(nXSize) * nYSize <= 65536)
355
0
        {
356
            // If the image is small enough, then the number of colors
357
            // will be limited and using a hashmap, rather than a full table
358
            // will be more efficient.
359
0
            histogram = nullptr;
360
0
            psHashHistogram = reinterpret_cast<HashHistogram *>(panHistogram);
361
0
            memset(psHashHistogram, 0xFF,
362
0
                   sizeof(HashHistogram) * PRIME_FOR_65536);
363
0
        }
364
0
        else
365
0
        {
366
0
            histogram = panHistogram;
367
0
            memset(histogram, 0, nCLevelsCube * sizeof(T));
368
0
        }
369
0
    }
370
0
    else
371
0
    {
372
0
        histogram =
373
0
            static_cast<T *>(VSI_CALLOC_VERBOSE(nCLevelsCube, sizeof(T)));
374
0
        if (histogram == nullptr)
375
0
        {
376
0
            return CE_Failure;
377
0
        }
378
0
    }
379
0
    Colorbox *box_list =
380
0
        static_cast<Colorbox *>(CPLMalloc(nColors * sizeof(Colorbox)));
381
0
    Colorbox *freeboxes = box_list;
382
0
    freeboxes[0].next = &freeboxes[1];
383
0
    freeboxes[0].prev = nullptr;
384
0
    for (int i = 1; i < nColors - 1; ++i)
385
0
    {
386
0
        freeboxes[i].next = &freeboxes[i + 1];
387
0
        freeboxes[i].prev = &freeboxes[i - 1];
388
0
    }
389
0
    freeboxes[nColors - 1].next = nullptr;
390
0
    freeboxes[nColors - 1].prev = &freeboxes[nColors - 2];
391
392
    /* ==================================================================== */
393
    /*      Build histogram.                                                */
394
    /* ==================================================================== */
395
396
    /* -------------------------------------------------------------------- */
397
    /*      Initialize the box datastructures.                              */
398
    /* -------------------------------------------------------------------- */
399
0
    Colorbox *freeboxes_before = freeboxes;
400
0
    freeboxes = freeboxes_before->next;
401
0
    if (freeboxes)
402
0
        freeboxes->prev = nullptr;
403
404
0
    Colorbox *usedboxes = freeboxes_before;
405
0
    usedboxes->next = nullptr;
406
0
    usedboxes->rmin = 999;
407
0
    usedboxes->gmin = 999;
408
0
    usedboxes->bmin = 999;
409
0
    usedboxes->rmax = -1;
410
0
    usedboxes->gmax = -1;
411
0
    usedboxes->bmax = -1;
412
0
    usedboxes->total =
413
0
        static_cast<GUIntBig>(nXSize) * static_cast<GUIntBig>(nYSize);
414
415
    /* -------------------------------------------------------------------- */
416
    /*      Collect histogram.                                              */
417
    /* -------------------------------------------------------------------- */
418
419
    // TODO(schwehr): Move these closer to usage after removing gotos.
420
0
    const int nColorShift = 8 - nBits;
421
0
    int nColorCounter = 0;
422
0
    GByte anRed[256] = {};
423
0
    GByte anGreen[256] = {};
424
0
    GByte anBlue[256] = {};
425
426
0
    GByte *pabyRedLine = static_cast<GByte *>(VSI_MALLOC_VERBOSE(nXSize));
427
0
    GByte *pabyGreenLine = static_cast<GByte *>(VSI_MALLOC_VERBOSE(nXSize));
428
0
    GByte *pabyBlueLine = static_cast<GByte *>(VSI_MALLOC_VERBOSE(nXSize));
429
430
0
    if (pabyRedLine == nullptr || pabyGreenLine == nullptr ||
431
0
        pabyBlueLine == nullptr)
432
0
    {
433
0
        err = CE_Failure;
434
0
        goto end_and_cleanup;
435
0
    }
436
437
0
    for (int iLine = 0; iLine < nYSize; iLine++)
438
0
    {
439
0
        if (!pfnProgress(iLine / static_cast<double>(nYSize),
440
0
                         "Generating Histogram", pProgressArg))
441
0
        {
442
0
            CPLError(CE_Failure, CPLE_UserInterrupt, "User Terminated");
443
0
            err = CE_Failure;
444
0
            goto end_and_cleanup;
445
0
        }
446
447
0
        err = GDALRasterIO(hRed, GF_Read, 0, iLine, nXSize, 1, pabyRedLine,
448
0
                           nXSize, 1, GDT_Byte, 0, 0);
449
0
        if (err == CE_None)
450
0
            err = GDALRasterIO(hGreen, GF_Read, 0, iLine, nXSize, 1,
451
0
                               pabyGreenLine, nXSize, 1, GDT_Byte, 0, 0);
452
0
        if (err == CE_None)
453
0
            err = GDALRasterIO(hBlue, GF_Read, 0, iLine, nXSize, 1,
454
0
                               pabyBlueLine, nXSize, 1, GDT_Byte, 0, 0);
455
0
        if (err != CE_None)
456
0
            goto end_and_cleanup;
457
458
0
        for (int iPixel = 0; iPixel < nXSize; iPixel++)
459
0
        {
460
0
            const int nRed = pabyRedLine[iPixel] >> nColorShift;
461
0
            const int nGreen = pabyGreenLine[iPixel] >> nColorShift;
462
0
            const int nBlue = pabyBlueLine[iPixel] >> nColorShift;
463
464
0
            usedboxes->rmin = std::min(usedboxes->rmin, nRed);
465
0
            usedboxes->gmin = std::min(usedboxes->gmin, nGreen);
466
0
            usedboxes->bmin = std::min(usedboxes->bmin, nBlue);
467
0
            usedboxes->rmax = std::max(usedboxes->rmax, nRed);
468
0
            usedboxes->gmax = std::max(usedboxes->gmax, nGreen);
469
0
            usedboxes->bmax = std::max(usedboxes->bmax, nBlue);
470
471
0
            bool bFirstOccurrence;
472
0
            if (psHashHistogram)
473
0
            {
474
0
                int *pnColor = FindAndInsertColorCount(
475
0
                    psHashHistogram, MAKE_COLOR_CODE(nRed, nGreen, nBlue));
476
0
                bFirstOccurrence = (*pnColor == 0);
477
0
                (*pnColor)++;
478
0
            }
479
0
            else
480
0
            {
481
0
                T *pnColor =
482
0
                    HISTOGRAM(histogram, nCLevels, nRed, nGreen, nBlue);
483
0
                bFirstOccurrence = (*pnColor == 0);
484
0
                (*pnColor)++;
485
0
            }
486
0
            if (bFirstOccurrence)
487
0
            {
488
0
                if (nColorShift == 0 && nColorCounter < nColors)
489
0
                {
490
0
                    anRed[nColorCounter] = static_cast<GByte>(nRed);
491
0
                    anGreen[nColorCounter] = static_cast<GByte>(nGreen);
492
0
                    anBlue[nColorCounter] = static_cast<GByte>(nBlue);
493
0
                }
494
0
                nColorCounter++;
495
0
            }
496
0
        }
497
0
    }
498
499
0
    if (!pfnProgress(1.0, "Generating Histogram", pProgressArg))
500
0
    {
501
0
        CPLError(CE_Failure, CPLE_UserInterrupt, "User Terminated");
502
0
        err = CE_Failure;
503
0
        goto end_and_cleanup;
504
0
    }
505
506
0
    if (nColorShift == 0 && nColorCounter <= nColors)
507
0
    {
508
#if DEBUG_VERBOSE
509
        CPLDebug("MEDIAN_CUT", "%d colors found <= %d", nColorCounter, nColors);
510
#endif
511
0
        for (int iColor = 0; iColor < nColorCounter; iColor++)
512
0
        {
513
0
            const GDALColorEntry sEntry = {static_cast<GByte>(anRed[iColor]),
514
0
                                           static_cast<GByte>(anGreen[iColor]),
515
0
                                           static_cast<GByte>(anBlue[iColor]),
516
0
                                           255};
517
0
            GDALSetColorEntry(hColorTable, iColor, &sEntry);
518
0
        }
519
0
        goto end_and_cleanup;
520
0
    }
521
522
    /* ==================================================================== */
523
    /*      STEP 3: continually subdivide boxes until no more free          */
524
    /*      boxes remain or until all colors assigned.                      */
525
    /* ==================================================================== */
526
0
    while (freeboxes != nullptr)
527
0
    {
528
0
        auto ptr = largest_box(usedboxes);
529
0
        if (ptr != nullptr)
530
0
            splitbox(ptr, histogram, psHashHistogram, nCLevels, &freeboxes,
531
0
                     &usedboxes, pabyRedBand, pabyGreenBand, pabyBlueBand,
532
0
                     nPixels);
533
0
        else
534
0
            freeboxes = nullptr;
535
0
    }
536
537
    /* ==================================================================== */
538
    /*      STEP 4: assign colors to all boxes                              */
539
    /* ==================================================================== */
540
0
    {
541
0
        Colorbox *ptr = usedboxes;
542
0
        for (int i = 0; ptr != nullptr; ++i, ptr = ptr->next)
543
0
        {
544
0
            const GDALColorEntry sEntry = {
545
0
                static_cast<GByte>(((ptr->rmin + ptr->rmax) << nColorShift) /
546
0
                                   2),
547
0
                static_cast<GByte>(((ptr->gmin + ptr->gmax) << nColorShift) /
548
0
                                   2),
549
0
                static_cast<GByte>(((ptr->bmin + ptr->bmax) << nColorShift) /
550
0
                                   2),
551
0
                255};
552
0
            GDALSetColorEntry(hColorTable, i, &sEntry);
553
0
        }
554
0
    }
555
556
0
end_and_cleanup:
557
0
    CPLFree(pabyRedLine);
558
0
    CPLFree(pabyGreenLine);
559
0
    CPLFree(pabyBlueLine);
560
561
    // We're done with the boxes now.
562
0
    CPLFree(box_list);
563
0
    freeboxes = nullptr;
564
0
    usedboxes = nullptr;
565
566
0
    if (panHistogram == nullptr)
567
0
        CPLFree(histogram);
568
569
0
    return err;
570
0
}
Unexecuted instantiation: int GDALComputeMedianCutPCTInternal<unsigned int>(void*, void*, void*, unsigned char*, unsigned char*, unsigned char*, int (*)(int, int, void*), int, int, unsigned int*, void*, int (*)(double, char const*, void*), void*)
Unexecuted instantiation: int GDALComputeMedianCutPCTInternal<unsigned long long>(void*, void*, void*, unsigned char*, unsigned char*, unsigned char*, int (*)(int, int, void*), int, int, unsigned long long*, void*, int (*)(double, char const*, void*), void*)
571
572
/************************************************************************/
573
/*                            largest_box()                             */
574
/************************************************************************/
575
576
static Colorbox *largest_box(Colorbox *usedboxes)
577
0
{
578
0
    Colorbox *b = nullptr;
579
580
0
    for (Colorbox *p = usedboxes; p != nullptr; p = p->next)
581
0
    {
582
0
        if ((p->rmax > p->rmin || p->gmax > p->gmin || p->bmax > p->bmin) &&
583
0
            (b == nullptr || p->total > b->total))
584
0
        {
585
0
            b = p;
586
0
        }
587
0
    }
588
0
    return b;
589
0
}
590
591
static void shrinkboxFromBand(Colorbox *ptr, const GByte *pabyRedBand,
592
                              const GByte *pabyGreenBand,
593
                              const GByte *pabyBlueBand, GUIntBig nPixels)
594
0
{
595
0
    int rmin_new = 255;
596
0
    int rmax_new = 0;
597
0
    int gmin_new = 255;
598
0
    int gmax_new = 0;
599
0
    int bmin_new = 255;
600
0
    int bmax_new = 0;
601
0
    for (GUIntBig i = 0; i < nPixels; i++)
602
0
    {
603
0
        const int iR = pabyRedBand[i];
604
0
        const int iG = pabyGreenBand[i];
605
0
        const int iB = pabyBlueBand[i];
606
0
        if (iR >= ptr->rmin && iR <= ptr->rmax && iG >= ptr->gmin &&
607
0
            iG <= ptr->gmax && iB >= ptr->bmin && iB <= ptr->bmax)
608
0
        {
609
0
            if (iR < rmin_new)
610
0
                rmin_new = iR;
611
0
            if (iR > rmax_new)
612
0
                rmax_new = iR;
613
0
            if (iG < gmin_new)
614
0
                gmin_new = iG;
615
0
            if (iG > gmax_new)
616
0
                gmax_new = iG;
617
0
            if (iB < bmin_new)
618
0
                bmin_new = iB;
619
0
            if (iB > bmax_new)
620
0
                bmax_new = iB;
621
0
        }
622
0
    }
623
624
0
    CPLAssert(rmin_new >= ptr->rmin && rmin_new <= rmax_new &&
625
0
              rmax_new <= ptr->rmax);
626
0
    CPLAssert(gmin_new >= ptr->gmin && gmin_new <= gmax_new &&
627
0
              gmax_new <= ptr->gmax);
628
0
    CPLAssert(bmin_new >= ptr->bmin && bmin_new <= bmax_new &&
629
0
              bmax_new <= ptr->bmax);
630
0
    ptr->rmin = rmin_new;
631
0
    ptr->rmax = rmax_new;
632
0
    ptr->gmin = gmin_new;
633
0
    ptr->gmax = gmax_new;
634
0
    ptr->bmin = bmin_new;
635
0
    ptr->bmax = bmax_new;
636
0
}
637
638
static void shrinkboxFromHashHistogram(Colorbox *box,
639
                                       const HashHistogram *psHashHistogram)
640
0
{
641
0
    if (box->rmax > box->rmin)
642
0
    {
643
0
        for (int ir = box->rmin; ir <= box->rmax; ++ir)
644
0
        {
645
0
            for (int ig = box->gmin; ig <= box->gmax; ++ig)
646
0
            {
647
0
                for (int ib = box->bmin; ib <= box->bmax; ++ib)
648
0
                {
649
0
                    if (FindColorCount(psHashHistogram,
650
0
                                       MAKE_COLOR_CODE(ir, ig, ib)) != 0)
651
0
                    {
652
0
                        box->rmin = ir;
653
0
                        goto have_rmin;
654
0
                    }
655
0
                }
656
0
            }
657
0
        }
658
0
    }
659
0
have_rmin:
660
0
    if (box->rmax > box->rmin)
661
0
    {
662
0
        for (int ir = box->rmax; ir >= box->rmin; --ir)
663
0
        {
664
0
            for (int ig = box->gmin; ig <= box->gmax; ++ig)
665
0
            {
666
0
                for (int ib = box->bmin; ib <= box->bmax; ++ib)
667
0
                {
668
0
                    if (FindColorCount(psHashHistogram,
669
0
                                       MAKE_COLOR_CODE(ir, ig, ib)) != 0)
670
0
                    {
671
0
                        box->rmax = ir;
672
0
                        goto have_rmax;
673
0
                    }
674
0
                }
675
0
            }
676
0
        }
677
0
    }
678
679
0
have_rmax:
680
0
    if (box->gmax > box->gmin)
681
0
    {
682
0
        for (int ig = box->gmin; ig <= box->gmax; ++ig)
683
0
        {
684
0
            for (int ir = box->rmin; ir <= box->rmax; ++ir)
685
0
            {
686
0
                for (int ib = box->bmin; ib <= box->bmax; ++ib)
687
0
                {
688
0
                    if (FindColorCount(psHashHistogram,
689
0
                                       MAKE_COLOR_CODE(ir, ig, ib)) != 0)
690
0
                    {
691
0
                        box->gmin = ig;
692
0
                        goto have_gmin;
693
0
                    }
694
0
                }
695
0
            }
696
0
        }
697
0
    }
698
699
0
have_gmin:
700
0
    if (box->gmax > box->gmin)
701
0
    {
702
0
        for (int ig = box->gmax; ig >= box->gmin; --ig)
703
0
        {
704
0
            for (int ir = box->rmin; ir <= box->rmax; ++ir)
705
0
            {
706
0
                int ib = box->bmin;
707
0
                for (; ib <= box->bmax; ++ib)
708
0
                {
709
0
                    if (FindColorCount(psHashHistogram,
710
0
                                       MAKE_COLOR_CODE(ir, ig, ib)) != 0)
711
0
                    {
712
0
                        box->gmax = ig;
713
0
                        goto have_gmax;
714
0
                    }
715
0
                }
716
0
            }
717
0
        }
718
0
    }
719
720
0
have_gmax:
721
0
    if (box->bmax > box->bmin)
722
0
    {
723
0
        for (int ib = box->bmin; ib <= box->bmax; ++ib)
724
0
        {
725
0
            for (int ir = box->rmin; ir <= box->rmax; ++ir)
726
0
            {
727
0
                for (int ig = box->gmin; ig <= box->gmax; ++ig)
728
0
                {
729
0
                    if (FindColorCount(psHashHistogram,
730
0
                                       MAKE_COLOR_CODE(ir, ig, ib)) != 0)
731
0
                    {
732
0
                        box->bmin = ib;
733
0
                        goto have_bmin;
734
0
                    }
735
0
                }
736
0
            }
737
0
        }
738
0
    }
739
740
0
have_bmin:
741
0
    if (box->bmax > box->bmin)
742
0
    {
743
0
        for (int ib = box->bmax; ib >= box->bmin; --ib)
744
0
        {
745
0
            for (int ir = box->rmin; ir <= box->rmax; ++ir)
746
0
            {
747
0
                for (int ig = box->gmin; ig <= box->gmax; ++ig)
748
0
                {
749
0
                    if (FindColorCount(psHashHistogram,
750
0
                                       MAKE_COLOR_CODE(ir, ig, ib)) != 0)
751
0
                    {
752
0
                        box->bmax = ib;
753
0
                        goto have_bmax;
754
0
                    }
755
0
                }
756
0
            }
757
0
        }
758
0
    }
759
760
0
have_bmax:;
761
0
}
762
763
/************************************************************************/
764
/*                              splitbox()                              */
765
/************************************************************************/
766
template <class T>
767
static void splitbox(Colorbox *ptr, const T *histogram,
768
                     const HashHistogram *psHashHistogram, int nCLevels,
769
                     Colorbox **pfreeboxes, Colorbox **pusedboxes,
770
                     GByte *pabyRedBand, GByte *pabyGreenBand,
771
                     GByte *pabyBlueBand, T nPixels)
772
0
{
773
0
    T hist2[256] = {};
774
0
    int first = 0;
775
0
    int last = 0;
776
777
0
    enum
778
0
    {
779
0
        RED,
780
0
        GREEN,
781
0
        BLUE
782
0
    } axis;
783
784
    // See which axis is the largest, do a histogram along that axis.  Split at
785
    // median point.  Contract both new boxes to fit points and return.
786
0
    {
787
0
        int i = ptr->rmax - ptr->rmin;
788
0
        if (i >= ptr->gmax - ptr->gmin && i >= ptr->bmax - ptr->bmin)
789
0
            axis = RED;
790
0
        else if (ptr->gmax - ptr->gmin >= ptr->bmax - ptr->bmin)
791
0
            axis = GREEN;
792
0
        else
793
0
            axis = BLUE;
794
0
    }
795
    // Get histogram along longest axis.
796
0
    const GUInt32 nIters = (ptr->rmax - ptr->rmin + 1) *
797
0
                           (ptr->gmax - ptr->gmin + 1) *
798
0
                           (ptr->bmax - ptr->bmin + 1);
799
800
0
    switch (axis)
801
0
    {
802
0
        case RED:
803
0
        {
804
0
            if (nPixels != 0 && nIters > nPixels)
805
0
            {
806
0
                const int rmin = ptr->rmin;
807
0
                const int rmax = ptr->rmax;
808
0
                const int gmin = ptr->gmin;
809
0
                const int gmax = ptr->gmax;
810
0
                const int bmin = ptr->bmin;
811
0
                const int bmax = ptr->bmax;
812
0
                for (T iPixel = 0; iPixel < nPixels; iPixel++)
813
0
                {
814
0
                    int iR = pabyRedBand[iPixel];
815
0
                    int iG = pabyGreenBand[iPixel];
816
0
                    int iB = pabyBlueBand[iPixel];
817
0
                    if (iR >= rmin && iR <= rmax && iG >= gmin && iG <= gmax &&
818
0
                        iB >= bmin && iB <= bmax)
819
0
                    {
820
0
                        hist2[iR]++;
821
0
                    }
822
0
                }
823
0
            }
824
0
            else if (psHashHistogram)
825
0
            {
826
0
                T *histp = &hist2[ptr->rmin];
827
0
                for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir)
828
0
                {
829
0
                    *histp = 0;
830
0
                    for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig)
831
0
                    {
832
0
                        for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib)
833
0
                        {
834
0
                            *histp += FindColorCount(
835
0
                                psHashHistogram, MAKE_COLOR_CODE(ir, ig, ib));
836
0
                        }
837
0
                    }
838
0
                    histp++;
839
0
                }
840
0
            }
841
0
            else
842
0
            {
843
0
                T *histp = &hist2[ptr->rmin];
844
0
                for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir)
845
0
                {
846
0
                    *histp = 0;
847
0
                    for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig)
848
0
                    {
849
0
                        const T *iptr =
850
0
                            HISTOGRAM(histogram, nCLevels, ir, ig, ptr->bmin);
851
0
                        for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib)
852
0
                            *histp += *iptr++;
853
0
                    }
854
0
                    histp++;
855
0
                }
856
0
            }
857
0
            first = ptr->rmin;
858
0
            last = ptr->rmax;
859
0
            break;
860
0
        }
861
0
        case GREEN:
862
0
        {
863
0
            if (nPixels != 0 && nIters > nPixels)
864
0
            {
865
0
                const int rmin = ptr->rmin;
866
0
                const int rmax = ptr->rmax;
867
0
                const int gmin = ptr->gmin;
868
0
                const int gmax = ptr->gmax;
869
0
                const int bmin = ptr->bmin;
870
0
                const int bmax = ptr->bmax;
871
0
                for (T iPixel = 0; iPixel < nPixels; iPixel++)
872
0
                {
873
0
                    const int iR = pabyRedBand[iPixel];
874
0
                    const int iG = pabyGreenBand[iPixel];
875
0
                    const int iB = pabyBlueBand[iPixel];
876
0
                    if (iR >= rmin && iR <= rmax && iG >= gmin && iG <= gmax &&
877
0
                        iB >= bmin && iB <= bmax)
878
0
                    {
879
0
                        hist2[iG]++;
880
0
                    }
881
0
                }
882
0
            }
883
0
            else if (psHashHistogram)
884
0
            {
885
0
                T *histp = &hist2[ptr->gmin];
886
0
                for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig)
887
0
                {
888
0
                    *histp = 0;
889
0
                    for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir)
890
0
                    {
891
0
                        for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib)
892
0
                        {
893
0
                            *histp += FindColorCount(
894
0
                                psHashHistogram, MAKE_COLOR_CODE(ir, ig, ib));
895
0
                        }
896
0
                    }
897
0
                    histp++;
898
0
                }
899
0
            }
900
0
            else
901
0
            {
902
0
                T *histp = &hist2[ptr->gmin];
903
0
                for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig)
904
0
                {
905
0
                    *histp = 0;
906
0
                    for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir)
907
0
                    {
908
0
                        const T *iptr =
909
0
                            HISTOGRAM(histogram, nCLevels, ir, ig, ptr->bmin);
910
0
                        for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib)
911
0
                            *histp += *iptr++;
912
0
                    }
913
0
                    histp++;
914
0
                }
915
0
            }
916
0
            first = ptr->gmin;
917
0
            last = ptr->gmax;
918
0
            break;
919
0
        }
920
0
        case BLUE:
921
0
        {
922
0
            if (nPixels != 0 && nIters > nPixels)
923
0
            {
924
0
                const int rmin = ptr->rmin;
925
0
                const int rmax = ptr->rmax;
926
0
                const int gmin = ptr->gmin;
927
0
                const int gmax = ptr->gmax;
928
0
                const int bmin = ptr->bmin;
929
0
                const int bmax = ptr->bmax;
930
0
                for (T iPixel = 0; iPixel < nPixels; iPixel++)
931
0
                {
932
0
                    const int iR = pabyRedBand[iPixel];
933
0
                    const int iG = pabyGreenBand[iPixel];
934
0
                    const int iB = pabyBlueBand[iPixel];
935
0
                    if (iR >= rmin && iR <= rmax && iG >= gmin && iG <= gmax &&
936
0
                        iB >= bmin && iB <= bmax)
937
0
                    {
938
0
                        hist2[iB]++;
939
0
                    }
940
0
                }
941
0
            }
942
0
            else if (psHashHistogram)
943
0
            {
944
0
                T *histp = &hist2[ptr->bmin];
945
0
                for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib)
946
0
                {
947
0
                    *histp = 0;
948
0
                    for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir)
949
0
                    {
950
0
                        for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig)
951
0
                        {
952
0
                            *histp += FindColorCount(
953
0
                                psHashHistogram, MAKE_COLOR_CODE(ir, ig, ib));
954
0
                        }
955
0
                    }
956
0
                    histp++;
957
0
                }
958
0
            }
959
0
            else
960
0
            {
961
0
                T *histp = &hist2[ptr->bmin];
962
0
                for (int ib = ptr->bmin; ib <= ptr->bmax; ++ib)
963
0
                {
964
0
                    *histp = 0;
965
0
                    for (int ir = ptr->rmin; ir <= ptr->rmax; ++ir)
966
0
                    {
967
0
                        const T *iptr =
968
0
                            HISTOGRAM(histogram, nCLevels, ir, ptr->gmin, ib);
969
0
                        for (int ig = ptr->gmin; ig <= ptr->gmax; ++ig)
970
0
                        {
971
0
                            *histp += *iptr;
972
0
                            iptr += nCLevels;
973
0
                        }
974
0
                    }
975
0
                    histp++;
976
0
                }
977
0
            }
978
0
            first = ptr->bmin;
979
0
            last = ptr->bmax;
980
0
            break;
981
0
        }
982
0
    }
983
    // Find median point.
984
0
    T *histp = &hist2[first];
985
0
    int i = first;  // TODO(schwehr): Rename i.
986
0
    {
987
0
        T sum = 0;
988
0
        T sum2 = static_cast<T>(ptr->total / 2);
989
0
        for (; i <= last && (sum += *histp++) < sum2; ++i)
990
0
        {
991
0
        }
992
0
    }
993
0
    if (i == first)
994
0
        i++;
995
996
    // Create new box, re-allocate points.
997
0
    Colorbox *new_cb = *pfreeboxes;
998
0
    *pfreeboxes = new_cb->next;
999
0
    if (*pfreeboxes)
1000
0
        (*pfreeboxes)->prev = nullptr;
1001
0
    if (*pusedboxes)
1002
0
        (*pusedboxes)->prev = new_cb;
1003
0
    new_cb->next = *pusedboxes;
1004
0
    *pusedboxes = new_cb;
1005
1006
0
    histp = &hist2[first];
1007
0
    {
1008
0
        T sum1 = 0;
1009
0
        for (int j = first; j < i; j++)
1010
0
            sum1 += *histp++;
1011
0
        T sum2 = 0;
1012
0
        for (int j = i; j <= last; j++)
1013
0
            sum2 += *histp++;
1014
0
        new_cb->total = sum1;
1015
0
        ptr->total = sum2;
1016
0
    }
1017
0
    new_cb->rmin = ptr->rmin;
1018
0
    new_cb->rmax = ptr->rmax;
1019
0
    new_cb->gmin = ptr->gmin;
1020
0
    new_cb->gmax = ptr->gmax;
1021
0
    new_cb->bmin = ptr->bmin;
1022
0
    new_cb->bmax = ptr->bmax;
1023
0
    switch (axis)
1024
0
    {
1025
0
        case RED:
1026
0
            new_cb->rmax = i - 1;
1027
0
            ptr->rmin = i;
1028
0
            break;
1029
0
        case GREEN:
1030
0
            new_cb->gmax = i - 1;
1031
0
            ptr->gmin = i;
1032
0
            break;
1033
0
        case BLUE:
1034
0
            new_cb->bmax = i - 1;
1035
0
            ptr->bmin = i;
1036
0
            break;
1037
0
    }
1038
1039
0
    if (nPixels != 0 &&
1040
0
        static_cast<T>(new_cb->rmax - new_cb->rmin + 1) *
1041
0
                static_cast<T>(new_cb->gmax - new_cb->gmin + 1) *
1042
0
                static_cast<T>(new_cb->bmax - new_cb->bmin + 1) >
1043
0
            nPixels)
1044
0
    {
1045
0
        shrinkboxFromBand(new_cb, pabyRedBand, pabyGreenBand, pabyBlueBand,
1046
0
                          nPixels);
1047
0
    }
1048
0
    else if (psHashHistogram != nullptr)
1049
0
    {
1050
0
        shrinkboxFromHashHistogram(new_cb, psHashHistogram);
1051
0
    }
1052
0
    else
1053
0
    {
1054
0
        shrinkbox(new_cb, histogram, nCLevels);
1055
0
    }
1056
1057
0
    if (nPixels != 0 && static_cast<T>(ptr->rmax - ptr->rmin + 1) *
1058
0
                                static_cast<T>(ptr->gmax - ptr->gmin + 1) *
1059
0
                                static_cast<T>(ptr->bmax - ptr->bmin + 1) >
1060
0
                            nPixels)
1061
0
    {
1062
0
        shrinkboxFromBand(ptr, pabyRedBand, pabyGreenBand, pabyBlueBand,
1063
0
                          nPixels);
1064
0
    }
1065
0
    else if (psHashHistogram != nullptr)
1066
0
    {
1067
0
        shrinkboxFromHashHistogram(ptr, psHashHistogram);
1068
0
    }
1069
0
    else
1070
0
    {
1071
0
        shrinkbox(ptr, histogram, nCLevels);
1072
0
    }
1073
0
}
Unexecuted instantiation: gdalmediancut.cpp:void splitbox<unsigned int>(colorbox*, unsigned int const*, HashHistogram const*, int, colorbox**, colorbox**, unsigned char*, unsigned char*, unsigned char*, unsigned int)
Unexecuted instantiation: gdalmediancut.cpp:void splitbox<unsigned long long>(colorbox*, unsigned long long const*, HashHistogram const*, int, colorbox**, colorbox**, unsigned char*, unsigned char*, unsigned char*, unsigned long long)
1074
1075
/************************************************************************/
1076
/*                             shrinkbox()                              */
1077
/************************************************************************/
1078
template <class T>
1079
static void shrinkbox(Colorbox *box, const T *histogram, int nCLevels)
1080
0
{
1081
0
    if (box->rmax > box->rmin)
1082
0
    {
1083
0
        for (int ir = box->rmin; ir <= box->rmax; ++ir)
1084
0
        {
1085
0
            for (int ig = box->gmin; ig <= box->gmax; ++ig)
1086
0
            {
1087
0
                const T *histp =
1088
0
                    HISTOGRAM(histogram, nCLevels, ir, ig, box->bmin);
1089
0
                for (int ib = box->bmin; ib <= box->bmax; ++ib)
1090
0
                {
1091
0
                    if (*histp++ != 0)
1092
0
                    {
1093
0
                        box->rmin = ir;
1094
0
                        goto have_rmin;
1095
0
                    }
1096
0
                }
1097
0
            }
1098
0
        }
1099
0
    }
1100
0
have_rmin:
1101
0
    if (box->rmax > box->rmin)
1102
0
    {
1103
0
        for (int ir = box->rmax; ir >= box->rmin; --ir)
1104
0
        {
1105
0
            for (int ig = box->gmin; ig <= box->gmax; ++ig)
1106
0
            {
1107
0
                const T *histp =
1108
0
                    HISTOGRAM(histogram, nCLevels, ir, ig, box->bmin);
1109
0
                for (int ib = box->bmin; ib <= box->bmax; ++ib)
1110
0
                {
1111
0
                    if (*histp++ != 0)
1112
0
                    {
1113
0
                        box->rmax = ir;
1114
0
                        goto have_rmax;
1115
0
                    }
1116
0
                }
1117
0
            }
1118
0
        }
1119
0
    }
1120
1121
0
have_rmax:
1122
0
    if (box->gmax > box->gmin)
1123
0
    {
1124
0
        for (int ig = box->gmin; ig <= box->gmax; ++ig)
1125
0
        {
1126
0
            for (int ir = box->rmin; ir <= box->rmax; ++ir)
1127
0
            {
1128
0
                const T *histp =
1129
0
                    HISTOGRAM(histogram, nCLevels, ir, ig, box->bmin);
1130
0
                for (int ib = box->bmin; ib <= box->bmax; ++ib)
1131
0
                {
1132
0
                    if (*histp++ != 0)
1133
0
                    {
1134
0
                        box->gmin = ig;
1135
0
                        goto have_gmin;
1136
0
                    }
1137
0
                }
1138
0
            }
1139
0
        }
1140
0
    }
1141
1142
0
have_gmin:
1143
0
    if (box->gmax > box->gmin)
1144
0
    {
1145
0
        for (int ig = box->gmax; ig >= box->gmin; --ig)
1146
0
        {
1147
0
            for (int ir = box->rmin; ir <= box->rmax; ++ir)
1148
0
            {
1149
0
                const T *histp =
1150
0
                    HISTOGRAM(histogram, nCLevels, ir, ig, box->bmin);
1151
0
                for (int ib = box->bmin; ib <= box->bmax; ++ib)
1152
0
                {
1153
0
                    if (*histp++ != 0)
1154
0
                    {
1155
0
                        box->gmax = ig;
1156
0
                        goto have_gmax;
1157
0
                    }
1158
0
                }
1159
0
            }
1160
0
        }
1161
0
    }
1162
1163
0
have_gmax:
1164
0
    if (box->bmax > box->bmin)
1165
0
    {
1166
0
        for (int ib = box->bmin; ib <= box->bmax; ++ib)
1167
0
        {
1168
0
            for (int ir = box->rmin; ir <= box->rmax; ++ir)
1169
0
            {
1170
0
                const T *histp =
1171
0
                    HISTOGRAM(histogram, nCLevels, ir, box->gmin, ib);
1172
0
                for (int ig = box->gmin; ig <= box->gmax; ++ig)
1173
0
                {
1174
0
                    if (*histp != 0)
1175
0
                    {
1176
0
                        box->bmin = ib;
1177
0
                        goto have_bmin;
1178
0
                    }
1179
0
                    histp += nCLevels;
1180
0
                }
1181
0
            }
1182
0
        }
1183
0
    }
1184
1185
0
have_bmin:
1186
0
    if (box->bmax > box->bmin)
1187
0
    {
1188
0
        for (int ib = box->bmax; ib >= box->bmin; --ib)
1189
0
        {
1190
0
            for (int ir = box->rmin; ir <= box->rmax; ++ir)
1191
0
            {
1192
0
                const T *histp =
1193
0
                    HISTOGRAM(histogram, nCLevels, ir, box->gmin, ib);
1194
0
                for (int ig = box->gmin; ig <= box->gmax; ++ig)
1195
0
                {
1196
0
                    if (*histp != 0)
1197
0
                    {
1198
0
                        box->bmax = ib;
1199
0
                        goto have_bmax;
1200
0
                    }
1201
0
                    histp += nCLevels;
1202
0
                }
1203
0
            }
1204
0
        }
1205
0
    }
1206
1207
0
have_bmax:;
1208
0
}
Unexecuted instantiation: gdalmediancut.cpp:void shrinkbox<unsigned int>(colorbox*, unsigned int const*, int)
Unexecuted instantiation: gdalmediancut.cpp:void shrinkbox<unsigned long long>(colorbox*, unsigned long long const*, int)
1209
1210
// Explicitly instantiate template functions.
1211
template int GDALComputeMedianCutPCTInternal<GUInt32>(
1212
    GDALRasterBandH hRed, GDALRasterBandH hGreen, GDALRasterBandH hBlue,
1213
    GByte *pabyRedBand, GByte *pabyGreenBand, GByte *pabyBlueBand,
1214
    int (*pfnIncludePixel)(int, int, void *), int nColors, int nBits,
1215
    GUInt32 *panHistogram, GDALColorTableH hColorTable,
1216
    GDALProgressFunc pfnProgress, void *pProgressArg);
1217
1218
template int GDALComputeMedianCutPCTInternal<GUIntBig>(
1219
    GDALRasterBandH hRed, GDALRasterBandH hGreen, GDALRasterBandH hBlue,
1220
    GByte *pabyRedBand, GByte *pabyGreenBand, GByte *pabyBlueBand,
1221
    int (*pfnIncludePixel)(int, int, void *), int nColors, int nBits,
1222
    GUIntBig *panHistogram, GDALColorTableH hColorTable,
1223
    GDALProgressFunc pfnProgress, void *pProgressArg);