Pillow

1
/*
2
 * The Python Imaging Library
3
 *
4
 * decoder for DXTn-compressed data
5
 *
6
 * Format documentation:
7
 *   https://web.archive.org/web/20170802060935/http://oss.sgi.com/projects/ogl-sample/registry/EXT/texture_compression_s3tc.txt
8
 *
9
 * The contents of this file are in the public domain (CC0)
10
 * Full text of the CC0 license:
11
 *   https://creativecommons.org/publicdomain/zero/1.0/
12
 */
13

14
#include "Imaging.h"
15

16
#include "Bcn.h"
17

18
typedef struct {
19
    UINT8 r, g, b, a;
20
} rgba;
21

22
typedef struct {
23
    UINT8 l;
24
} lum;
25

26
typedef struct {
27
    UINT16 c0, c1;
28
    UINT32 lut;
29
} bc1_color;
30

31
typedef struct {
32
    UINT8 a0, a1;
33
    UINT8 lut[6];
34
} bc3_alpha;
35

36
typedef struct {
37
    INT8 a0, a1;
38
    UINT8 lut[6];
39
} bc5s_alpha;
40

41
#define LOAD16(p) (p)[0] | ((p)[1] << 8)
42

43
#define LOAD32(p) (p)[0] | ((p)[1] << 8) | ((p)[2] << 16) | ((p)[3] << 24)
44

45
static void
46
bc1_color_load(bc1_color *dst, const UINT8 *src) {
47
    dst->c0 = LOAD16(src);
48
    dst->c1 = LOAD16(src + 2);
49
    dst->lut = LOAD32(src + 4);
50
}
51

52
static rgba
53
decode_565(UINT16 x) {
54
    rgba c;
55
    int r, g, b;
56
    r = (x & 0xf800) >> 8;
57
    r |= r >> 5;
58
    c.r = r;
59
    g = (x & 0x7e0) >> 3;
60
    g |= g >> 6;
61
    c.g = g;
62
    b = (x & 0x1f) << 3;
63
    b |= b >> 5;
64
    c.b = b;
65
    c.a = 0xff;
66
    return c;
67
}
68

69
static void
70
decode_bc1_color(rgba *dst, const UINT8 *src, int separate_alpha) {
71
    bc1_color col;
72
    rgba p[4];
73
    int n, cw;
74
    UINT16 r0, g0, b0, r1, g1, b1;
75
    bc1_color_load(&col, src);
76

77
    p[0] = decode_565(col.c0);
78
    r0 = p[0].r;
79
    g0 = p[0].g;
80
    b0 = p[0].b;
81
    p[1] = decode_565(col.c1);
82
    r1 = p[1].r;
83
    g1 = p[1].g;
84
    b1 = p[1].b;
85

86
    /* NOTE: BC2 and BC3 reuse BC1 color blocks but always act like c0 > c1 */
87
    if (col.c0 > col.c1 || separate_alpha) {
88
        p[2].r = (2 * r0 + 1 * r1) / 3;
89
        p[2].g = (2 * g0 + 1 * g1) / 3;
90
        p[2].b = (2 * b0 + 1 * b1) / 3;
91
        p[2].a = 0xff;
92
        p[3].r = (1 * r0 + 2 * r1) / 3;
93
        p[3].g = (1 * g0 + 2 * g1) / 3;
94
        p[3].b = (1 * b0 + 2 * b1) / 3;
95
        p[3].a = 0xff;
96
    } else {
97
        p[2].r = (r0 + r1) / 2;
98
        p[2].g = (g0 + g1) / 2;
99
        p[2].b = (b0 + b1) / 2;
100
        p[2].a = 0xff;
101
        p[3].r = 0;
102
        p[3].g = 0;
103
        p[3].b = 0;
104
        p[3].a = 0;
105
    }
106
    for (n = 0; n < 16; n++) {
107
        cw = 3 & (col.lut >> (2 * n));
108
        dst[n] = p[cw];
109
    }
110
}
111

112
static void
113
decode_bc3_alpha(char *dst, const UINT8 *src, int stride, int o, int sign) {
114
    UINT16 a0, a1;
115
    UINT8 a[8];
116
    int n, lut1, lut2, aw;
117
    if (sign == 1) {
118
        bc5s_alpha b;
119
        memcpy(&b, src, sizeof(bc5s_alpha));
120
        a0 = b.a0 + 128;
121
        a1 = b.a1 + 128;
122
        lut1 = b.lut[0] | (b.lut[1] << 8) | (b.lut[2] << 16);
123
        lut2 = b.lut[3] | (b.lut[4] << 8) | (b.lut[5] << 16);
124
    } else {
125
        bc3_alpha b;
126
        memcpy(&b, src, sizeof(bc3_alpha));
127
        a0 = b.a0;
128
        a1 = b.a1;
129
        lut1 = b.lut[0] | (b.lut[1] << 8) | (b.lut[2] << 16);
130
        lut2 = b.lut[3] | (b.lut[4] << 8) | (b.lut[5] << 16);
131
    }
132

133
    a[0] = (UINT8)a0;
134
    a[1] = (UINT8)a1;
135
    if (a0 > a1) {
136
        a[2] = (6 * a0 + 1 * a1) / 7;
137
        a[3] = (5 * a0 + 2 * a1) / 7;
138
        a[4] = (4 * a0 + 3 * a1) / 7;
139
        a[5] = (3 * a0 + 4 * a1) / 7;
140
        a[6] = (2 * a0 + 5 * a1) / 7;
141
        a[7] = (1 * a0 + 6 * a1) / 7;
142
    } else {
143
        a[2] = (4 * a0 + 1 * a1) / 5;
144
        a[3] = (3 * a0 + 2 * a1) / 5;
145
        a[4] = (2 * a0 + 3 * a1) / 5;
146
        a[5] = (1 * a0 + 4 * a1) / 5;
147
        a[6] = 0;
148
        a[7] = 0xff;
149
    }
150
    for (n = 0; n < 8; n++) {
151
        aw = 7 & (lut1 >> (3 * n));
152
        dst[stride * n + o] = a[aw];
153
    }
154
    for (n = 0; n < 8; n++) {
155
        aw = 7 & (lut2 >> (3 * n));
156
        dst[stride * (8 + n) + o] = a[aw];
157
    }
158
}
159

160
static void
161
decode_bc1_block(rgba *col, const UINT8 *src) {
162
    decode_bc1_color(col, src, 0);
163
}
164

165
static void
166
decode_bc2_block(rgba *col, const UINT8 *src) {
167
    int n, bitI, byI, av;
168
    decode_bc1_color(col, src + 8, 1);
169
    for (n = 0; n < 16; n++) {
170
        bitI = n * 4;
171
        byI = bitI >> 3;
172
        av = 0xf & (src[byI] >> (bitI & 7));
173
        av = (av << 4) | av;
174
        col[n].a = av;
175
    }
176
}
177

178
static void
179
decode_bc3_block(rgba *col, const UINT8 *src) {
180
    decode_bc1_color(col, src + 8, 1);
181
    decode_bc3_alpha((char *)col, src, sizeof(col[0]), 3, 0);
182
}
183

184
static void
185
decode_bc4_block(lum *col, const UINT8 *src) {
186
    decode_bc3_alpha((char *)col, src, sizeof(col[0]), 0, 0);
187
}
188

189
static void
190
decode_bc5_block(rgba *col, const UINT8 *src, int sign) {
191
    decode_bc3_alpha((char *)col, src, sizeof(col[0]), 0, sign);
192
    decode_bc3_alpha((char *)col, src + 8, sizeof(col[0]), 1, sign);
193
}
194

195
/* BC6 and BC7 are described here:
196
   https://www.khronos.org/registry/OpenGL/extensions/ARB/ARB_texture_compression_bptc.txt
197
 */
198

199
static UINT8
200
get_bit(const UINT8 *src, int bit) {
201
    int by = bit >> 3;
202
    bit &= 7;
203
    return (src[by] >> bit) & 1;
204
}
205

206
static UINT8
207
get_bits(const UINT8 *src, int bit, int count) {
208
    UINT8 v;
209
    int x;
210
    int by = bit >> 3;
211
    bit &= 7;
212
    if (!count) {
213
        return 0;
214
    }
215
    if (bit + count <= 8) {
216
        v = (src[by] >> bit) & ((1 << count) - 1);
217
    } else {
218
        x = src[by] | (src[by + 1] << 8);
219
        v = (x >> bit) & ((1 << count) - 1);
220
    }
221
    return v;
222
}
223

224
/* BC7 */
225
typedef struct {
226
    char ns;
227
    char pb;
228
    char rb;
229
    char isb;
230
    char cb;
231
    char ab;
232
    char epb;
233
    char spb;
234
    char ib;
235
    char ib2;
236
} bc7_mode_info;
237

238
static const bc7_mode_info bc7_modes[] = {
239
    {3, 4, 0, 0, 4, 0, 1, 0, 3, 0},
240
    {2, 6, 0, 0, 6, 0, 0, 1, 3, 0},
241
    {3, 6, 0, 0, 5, 0, 0, 0, 2, 0},
242
    {2, 6, 0, 0, 7, 0, 1, 0, 2, 0},
243
    {1, 0, 2, 1, 5, 6, 0, 0, 2, 3},
244
    {1, 0, 2, 0, 7, 8, 0, 0, 2, 2},
245
    {1, 0, 0, 0, 7, 7, 1, 0, 4, 0},
246
    {2, 6, 0, 0, 5, 5, 1, 0, 2, 0}
247
};
248

249
/* Subset indices:
250
   Table.P2, 1 bit per index */
251
static const UINT16 bc7_si2[] = {
252
    0xcccc, 0x8888, 0xeeee, 0xecc8, 0xc880, 0xfeec, 0xfec8, 0xec80, 0xc800, 0xffec,
253
    0xfe80, 0xe800, 0xffe8, 0xff00, 0xfff0, 0xf000, 0xf710, 0x008e, 0x7100, 0x08ce,
254
    0x008c, 0x7310, 0x3100, 0x8cce, 0x088c, 0x3110, 0x6666, 0x366c, 0x17e8, 0x0ff0,
255
    0x718e, 0x399c, 0xaaaa, 0xf0f0, 0x5a5a, 0x33cc, 0x3c3c, 0x55aa, 0x9696, 0xa55a,
256
    0x73ce, 0x13c8, 0x324c, 0x3bdc, 0x6996, 0xc33c, 0x9966, 0x0660, 0x0272, 0x04e4,
257
    0x4e40, 0x2720, 0xc936, 0x936c, 0x39c6, 0x639c, 0x9336, 0x9cc6, 0x817e, 0xe718,
258
    0xccf0, 0x0fcc, 0x7744, 0xee22
259
};
260

261
/* Table.P3, 2 bits per index */
262
static const UINT32 bc7_si3[] = {
263
    0xaa685050, 0x6a5a5040, 0x5a5a4200, 0x5450a0a8, 0xa5a50000, 0xa0a05050, 0x5555a0a0,
264
    0x5a5a5050, 0xaa550000, 0xaa555500, 0xaaaa5500, 0x90909090, 0x94949494, 0xa4a4a4a4,
265
    0xa9a59450, 0x2a0a4250, 0xa5945040, 0x0a425054, 0xa5a5a500, 0x55a0a0a0, 0xa8a85454,
266
    0x6a6a4040, 0xa4a45000, 0x1a1a0500, 0x0050a4a4, 0xaaa59090, 0x14696914, 0x69691400,
267
    0xa08585a0, 0xaa821414, 0x50a4a450, 0x6a5a0200, 0xa9a58000, 0x5090a0a8, 0xa8a09050,
268
    0x24242424, 0x00aa5500, 0x24924924, 0x24499224, 0x50a50a50, 0x500aa550, 0xaaaa4444,
269
    0x66660000, 0xa5a0a5a0, 0x50a050a0, 0x69286928, 0x44aaaa44, 0x66666600, 0xaa444444,
270
    0x54a854a8, 0x95809580, 0x96969600, 0xa85454a8, 0x80959580, 0xaa141414, 0x96960000,
271
    0xaaaa1414, 0xa05050a0, 0xa0a5a5a0, 0x96000000, 0x40804080, 0xa9a8a9a8, 0xaaaaaa44,
272
    0x2a4a5254
273
};
274

275
/* Anchor indices:
276
   Table.A2 */
277
static const char bc7_ai0[] = {15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
278
                               15, 15, 15, 15, 2,  8,  2,  2,  8,  8,  15, 2,  8,
279
                               2,  2,  8,  8,  2,  2,  15, 15, 6,  8,  2,  8,  15,
280
                               15, 2,  8,  2,  2,  2,  15, 15, 6,  6,  2,  6,  8,
281
                               15, 15, 2,  2,  15, 15, 15, 15, 15, 2,  2,  15};
282

283
/* Table.A3a */
284
static const char bc7_ai1[] = {3,  3,  15, 15, 8,  3,  15, 15, 8,  8,  6,  6,  6,
285
                               5,  3,  3,  3,  3,  8,  15, 3,  3,  6,  10, 5,  8,
286
                               8,  6,  8,  5,  15, 15, 8,  15, 3,  5,  6,  10, 8,
287
                               15, 15, 3,  15, 5,  15, 15, 15, 15, 3,  15, 5,  5,
288
                               5,  8,  5,  10, 5,  10, 8,  13, 15, 12, 3,  3};
289

290
/* Table.A3b */
291
static const char bc7_ai2[] = {15, 8,  8,  3,  15, 15, 3,  8,  15, 15, 15, 15, 15,
292
                               15, 15, 8,  15, 8,  15, 3,  15, 8,  15, 8,  3,  15,
293
                               6,  10, 15, 15, 10, 8,  15, 3,  15, 10, 10, 8,  9,
294
                               10, 6,  15, 8,  15, 3,  6,  6,  8,  15, 3,  15, 15,
295
                               15, 15, 15, 15, 15, 15, 15, 15, 3,  15, 15, 8};
296

297
/* Interpolation weights */
298
static const char bc7_weights2[] = {0, 21, 43, 64};
299
static const char bc7_weights3[] = {0, 9, 18, 27, 37, 46, 55, 64};
300
static const char bc7_weights4[] = {
301
    0, 4, 9, 13, 17, 21, 26, 30, 34, 38, 43, 47, 51, 55, 60, 64
302
};
303

304
static const char *
305
bc7_get_weights(int n) {
306
    if (n == 2) {
307
        return bc7_weights2;
308
    }
309
    if (n == 3) {
310
        return bc7_weights3;
311
    }
312
    return bc7_weights4;
313
}
314

315
static int
316
bc7_get_subset(int ns, int partition, int n) {
317
    if (ns == 2) {
318
        return 1 & (bc7_si2[partition] >> n);
319
    }
320
    if (ns == 3) {
321
        return 3 & (bc7_si3[partition] >> (2 * n));
322
    }
323
    return 0;
324
}
325

326
static UINT8
327
expand_quantized(UINT8 v, int bits) {
328
    v = v << (8 - bits);
329
    return v | (v >> bits);
330
}
331

332
static void
333
bc7_lerp(rgba *dst, const rgba *e, int s0, int s1) {
334
    int t0 = 64 - s0;
335
    int t1 = 64 - s1;
336
    dst->r = (UINT8)((t0 * e[0].r + s0 * e[1].r + 32) >> 6);
337
    dst->g = (UINT8)((t0 * e[0].g + s0 * e[1].g + 32) >> 6);
338
    dst->b = (UINT8)((t0 * e[0].b + s0 * e[1].b + 32) >> 6);
339
    dst->a = (UINT8)((t1 * e[0].a + s1 * e[1].a + 32) >> 6);
340
}
341

342
static void
343
decode_bc7_block(rgba *col, const UINT8 *src) {
344
    rgba endpoints[6];
345
    int bit = 0, cibit, aibit;
346
    int mode = src[0];
347
    int i, j;
348
    int numep, cb, ab, ib, ib2, i0, i1, s;
349
    UINT8 index_sel, partition, rotation, val;
350
    const char *cw, *aw;
351
    const bc7_mode_info *info;
352

353
    /* mode is the number of unset bits before the first set bit: */
354
    if (!mode) {
355
        /* degenerate case when no bits set */
356
        for (i = 0; i < 16; i++) {
357
            col[i].r = col[i].g = col[i].b = 0;
358
            col[i].a = 255;
359
        }
360
        return;
361
    }
362
    while (!(mode & (1 << bit++)));
363
    mode = bit - 1;
364
    info = &bc7_modes[mode];
365
    /* color selection bits: {subset}{endpoint} */
366
    cb = info->cb;
367
    ab = info->ab;
368
    cw = bc7_get_weights(info->ib);
369
    aw = bc7_get_weights((ab && info->ib2) ? info->ib2 : info->ib);
370

371
#define LOAD(DST, N)             \
372
    DST = get_bits(src, bit, N); \
373
    bit += N;
374
    LOAD(partition, info->pb);
375
    LOAD(rotation, info->rb);
376
    LOAD(index_sel, info->isb);
377
    numep = info->ns << 1;
378

379
    /* red */
380
    for (i = 0; i < numep; i++) {
381
        LOAD(val, cb);
382
        endpoints[i].r = val;
383
    }
384

385
    /* green */
386
    for (i = 0; i < numep; i++) {
387
        LOAD(val, cb);
388
        endpoints[i].g = val;
389
    }
390

391
    /* blue */
392
    for (i = 0; i < numep; i++) {
393
        LOAD(val, cb);
394
        endpoints[i].b = val;
395
    }
396

397
    /* alpha */
398
    for (i = 0; i < numep; i++) {
399
        if (ab) {
400
            LOAD(val, ab);
401
        } else {
402
            val = 255;
403
        }
404
        endpoints[i].a = val;
405
    }
406

407
    /* p-bits */
408
#define ASSIGN_P(x) x = (x << 1) | val
409
    if (info->epb) {
410
        /* per endpoint */
411
        cb++;
412
        if (ab) {
413
            ab++;
414
        }
415
        for (i = 0; i < numep; i++) {
416
            LOAD(val, 1);
417
            ASSIGN_P(endpoints[i].r);
418
            ASSIGN_P(endpoints[i].g);
419
            ASSIGN_P(endpoints[i].b);
420
            if (ab) {
421
                ASSIGN_P(endpoints[i].a);
422
            }
423
        }
424
    }
425
    if (info->spb) {
426
        /* per subset */
427
        cb++;
428
        if (ab) {
429
            ab++;
430
        }
431
        for (i = 0; i < numep; i += 2) {
432
            LOAD(val, 1);
433
            for (j = 0; j < 2; j++) {
434
                ASSIGN_P(endpoints[i + j].r);
435
                ASSIGN_P(endpoints[i + j].g);
436
                ASSIGN_P(endpoints[i + j].b);
437
                if (ab) {
438
                    ASSIGN_P(endpoints[i + j].a);
439
                }
440
            }
441
        }
442
    }
443
#undef ASSIGN_P
444
#define EXPAND(x, b) x = expand_quantized(x, b)
445
    for (i = 0; i < numep; i++) {
446
        EXPAND(endpoints[i].r, cb);
447
        EXPAND(endpoints[i].g, cb);
448
        EXPAND(endpoints[i].b, cb);
449
        if (ab) {
450
            EXPAND(endpoints[i].a, ab);
451
        }
452
    }
453
#undef EXPAND
454
#undef LOAD
455
    cibit = bit;
456
    aibit = cibit + 16 * info->ib - info->ns;
457
    for (i = 0; i < 16; i++) {
458
        s = bc7_get_subset(info->ns, partition, i) << 1;
459
        ib = info->ib;
460
        if (i == 0) {
461
            ib--;
462
        } else if (info->ns == 2) {
463
            if (i == bc7_ai0[partition]) {
464
                ib--;
465
            }
466
        } else if (info->ns == 3) {
467
            if (i == bc7_ai1[partition]) {
468
                ib--;
469
            } else if (i == bc7_ai2[partition]) {
470
                ib--;
471
            }
472
        }
473
        i0 = get_bits(src, cibit, ib);
474
        cibit += ib;
475

476
        if (ab && info->ib2) {
477
            ib2 = info->ib2;
478
            if (ib2 && i == 0) {
479
                ib2--;
480
            }
481
            i1 = get_bits(src, aibit, ib2);
482
            aibit += ib2;
483
            if (index_sel) {
484
                bc7_lerp(&col[i], &endpoints[s], aw[i1], cw[i0]);
485
            } else {
486
                bc7_lerp(&col[i], &endpoints[s], cw[i0], aw[i1]);
487
            }
488
        } else {
489
            bc7_lerp(&col[i], &endpoints[s], cw[i0], cw[i0]);
490
        }
491
#define ROTATE(x, y) \
492
    val = x;         \
493
    x = y;           \
494
    y = val
495
        if (rotation == 1) {
496
            ROTATE(col[i].r, col[i].a);
497
        } else if (rotation == 2) {
498
            ROTATE(col[i].g, col[i].a);
499
        } else if (rotation == 3) {
500
            ROTATE(col[i].b, col[i].a);
501
        }
502
#undef ROTATE
503
    }
504
}
505

506
/* BC6 */
507
typedef struct {
508
    char ns;  /* number of subsets (also called regions) */
509
    char tr;  /* whether endpoints are delta-compressed */
510
    char pb;  /* partition bits */
511
    char epb; /* endpoint bits */
512
    char rb;  /* red bits (delta) */
513
    char gb;  /* green bits (delta) */
514
    char bb;  /* blue bits (delta) */
515
} bc6_mode_info;
516

517
static const bc6_mode_info bc6_modes[] = {
518
    // 00
519
    {2, 1, 5, 10, 5, 5, 5},
520
    // 01
521
    {2, 1, 5, 7, 6, 6, 6},
522
    // 10
523
    {2, 1, 5, 11, 5, 4, 4},
524
    {2, 1, 5, 11, 4, 5, 4},
525
    {2, 1, 5, 11, 4, 4, 5},
526
    {2, 1, 5, 9, 5, 5, 5},
527
    {2, 1, 5, 8, 6, 5, 5},
528
    {2, 1, 5, 8, 5, 6, 5},
529
    {2, 1, 5, 8, 5, 5, 6},
530
    {2, 0, 5, 6, 6, 6, 6},
531
    // 11
532
    {1, 0, 0, 10, 10, 10, 10},
533
    {1, 1, 0, 11, 9, 9, 9},
534
    {1, 1, 0, 12, 8, 8, 8},
535
    {1, 1, 0, 16, 4, 4, 4}
536
};
537

538
/* Table.F, encoded as a sequence of bit indices */
539
static const UINT8 bc6_bit_packings[][75] = {
540
    {116, 132, 180, 0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   16,  17,
541
     18,  19,  20,  21,  22,  23,  24,  25,  32,  33,  34,  35,  36,  37,  38,
542
     39,  40,  41,  48,  49,  50,  51,  52,  164, 112, 113, 114, 115, 64,  65,
543
     66,  67,  68,  176, 160, 161, 162, 163, 80,  81,  82,  83,  84,  177, 128,
544
     129, 130, 131, 96,  97,  98,  99,  100, 178, 144, 145, 146, 147, 148, 179},
545
    {117, 164, 165, 0,  1,   2,   3,   4,   5,   6,   176, 177, 132, 16,  17,
546
     18,  19,  20,  21, 22,  133, 178, 116, 32,  33,  34,  35,  36,  37,  38,
547
     179, 181, 180, 48, 49,  50,  51,  52,  53,  112, 113, 114, 115, 64,  65,
548
     66,  67,  68,  69, 160, 161, 162, 163, 80,  81,  82,  83,  84,  85,  128,
549
     129, 130, 131, 96, 97,  98,  99,  100, 101, 144, 145, 146, 147, 148, 149},
550
    {0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   16,  17,  18,  19,  20,
551
     21,  22,  23,  24,  25,  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,
552
     48,  49,  50,  51,  52,  10,  112, 113, 114, 115, 64,  65,  66,  67,  26,
553
     176, 160, 161, 162, 163, 80,  81,  82,  83,  42,  177, 128, 129, 130, 131,
554
     96,  97,  98,  99,  100, 178, 144, 145, 146, 147, 148, 179},
555
    {0,  1,   2,   3,   4,   5,   6,   7,   8,   9,   16,  17,  18,  19,  20,
556
     21, 22,  23,  24,  25,  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,
557
     48, 49,  50,  51,  10,  164, 112, 113, 114, 115, 64,  65,  66,  67,  68,
558
     26, 160, 161, 162, 163, 80,  81,  82,  83,  42,  177, 128, 129, 130, 131,
559
     96, 97,  98,  99,  176, 178, 144, 145, 146, 147, 116, 179},
560
    {0,   1,   2,   3,   4,   5,   6,   7,   8,   9,   16,  17,  18,  19,  20,
561
     21,  22,  23,  24,  25,  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,
562
     48,  49,  50,  51,  10,  132, 112, 113, 114, 115, 64,  65,  66,  67,  26,
563
     176, 160, 161, 162, 163, 80,  81,  82,  83,  84,  42,  128, 129, 130, 131,
564
     96,  97,  98,  99,  177, 178, 144, 145, 146, 147, 180, 179},
565
    {0,   1,   2,   3,   4,   5,   6,   7,   8,   132, 16,  17,  18,  19,  20,
566
     21,  22,  23,  24,  116, 32,  33,  34,  35,  36,  37,  38,  39,  40,  180,
567
     48,  49,  50,  51,  52,  164, 112, 113, 114, 115, 64,  65,  66,  67,  68,
568
     176, 160, 161, 162, 163, 80,  81,  82,  83,  84,  177, 128, 129, 130, 131,
569
     96,  97,  98,  99,  100, 178, 144, 145, 146, 147, 148, 179},
570
    {0,   1,   2,   3,   4,   5,   6,   7,   164, 132, 16,  17,  18,  19,  20,
571
     21,  22,  23,  178, 116, 32,  33,  34,  35,  36,  37,  38,  39,  179, 180,
572
     48,  49,  50,  51,  52,  53,  112, 113, 114, 115, 64,  65,  66,  67,  68,
573
     176, 160, 161, 162, 163, 80,  81,  82,  83,  84,  177, 128, 129, 130, 131,
574
     96,  97,  98,  99,  100, 101, 144, 145, 146, 147, 148, 149},
575
    {0,  1,   2,   3,   4,   5,   6,   7,   176, 132, 16,  17,  18,  19,  20,
576
     21, 22,  23,  117, 116, 32,  33,  34,  35,  36,  37,  38,  39,  165, 180,
577
     48, 49,  50,  51,  52,  164, 112, 113, 114, 115, 64,  65,  66,  67,  68,
578
     69, 160, 161, 162, 163, 80,  81,  82,  83,  84,  177, 128, 129, 130, 131,
579
     96, 97,  98,  99,  100, 178, 144, 145, 146, 147, 148, 179},
580
    {0,   1,   2,   3,   4,   5,   6,   7,   177, 132, 16,  17,  18,  19,  20,
581
     21,  22,  23,  133, 116, 32,  33,  34,  35,  36,  37,  38,  39,  181, 180,
582
     48,  49,  50,  51,  52,  164, 112, 113, 114, 115, 64,  65,  66,  67,  68,
583
     176, 160, 161, 162, 163, 80,  81,  82,  83,  84,  85,  128, 129, 130, 131,
584
     96,  97,  98,  99,  100, 178, 144, 145, 146, 147, 148, 179},
585
    {0,  1,   2,   3,   4,   5,   164, 176, 177, 132, 16,  17,  18,  19,  20,
586
     21, 117, 133, 178, 116, 32,  33,  34,  35,  36,  37,  165, 179, 181, 180,
587
     48, 49,  50,  51,  52,  53,  112, 113, 114, 115, 64,  65,  66,  67,  68,
588
     69, 160, 161, 162, 163, 80,  81,  82,  83,  84,  85,  128, 129, 130, 131,
589
     96, 97,  98,  99,  100, 101, 144, 145, 146, 147, 148, 149},
590
    {0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
591
     32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57,
592
     64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89},
593
    {0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
594
     32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 48, 49, 50, 51, 52, 53, 54, 55, 56, 10,
595
     64, 65, 66, 67, 68, 69, 70, 71, 72, 26, 80, 81, 82, 83, 84, 85, 86, 87, 88, 42},
596
    {0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
597
     32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 48, 49, 50, 51, 52, 53, 54, 55, 11, 10,
598
     64, 65, 66, 67, 68, 69, 70, 71, 27, 26, 80, 81, 82, 83, 84, 85, 86, 87, 43, 42},
599
    {0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
600
     32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 48, 49, 50, 51, 15, 14, 13, 12, 11, 10,
601
     64, 65, 66, 67, 31, 30, 29, 28, 27, 26, 80, 81, 82, 83, 47, 46, 45, 44, 43, 42}
602
};
603

604
static void
605
bc6_sign_extend(UINT16 *v, int prec) {
606
    int x = *v;
607
    if (x & (1 << (prec - 1))) {
608
        x |= -1 << prec;
609
    }
610
    *v = (UINT16)x;
611
}
612

613
static int
614
bc6_unquantize(UINT16 v, int prec, int sign) {
615
    int s = 0;
616
    int x;
617
    if (!sign) {
618
        x = v;
619
        if (prec >= 15) {
620
            return x;
621
        }
622
        if (x == 0) {
623
            return 0;
624
        }
625
        if (x == ((1 << prec) - 1)) {
626
            return 0xffff;
627
        }
628
        return ((x << 15) + 0x4000) >> (prec - 1);
629
    } else {
630
        x = (INT16)v;
631
        if (prec >= 16) {
632
            return x;
633
        }
634
        if (x < 0) {
635
            s = 1;
636
            x = -x;
637
        }
638

639
        if (x != 0) {
640
            if (x >= ((1 << (prec - 1)) - 1)) {
641
                x = 0x7fff;
642
            } else {
643
                x = ((x << 15) + 0x4000) >> (prec - 1);
644
            }
645
        }
646

647
        if (s) {
648
            return -x;
649
        }
650
        return x;
651
    }
652
}
653

654
static float
655
half_to_float(UINT16 h) {
656
    /* https://gist.github.com/rygorous/2144712 */
657
    union {
658
        UINT32 u;
659
        float f;
660
    } o, m;
661
    m.u = 0x77800000;
662
    o.u = (h & 0x7fff) << 13;
663
    o.f *= m.f;
664
    m.u = 0x47800000;
665
    if (o.f >= m.f) {
666
        o.u |= 255 << 23;
667
    }
668
    o.u |= (h & 0x8000) << 16;
669
    return o.f;
670
}
671

672
static float
673
bc6_finalize(int v, int sign) {
674
    if (sign) {
675
        if (v < 0) {
676
            v = ((-v) * 31) / 32;
677
            return half_to_float((UINT16)(0x8000 | v));
678
        } else {
679
            return half_to_float((UINT16)((v * 31) / 32));
680
        }
681
    } else {
682
        return half_to_float((UINT16)((v * 31) / 64));
683
    }
684
}
685

686
static UINT8
687
bc6_clamp(float value) {
688
    if (value < 0.0f) {
689
        return 0;
690
    } else if (value > 1.0f) {
691
        return 255;
692
    } else {
693
        return (UINT8)(value * 255.0f);
694
    }
695
}
696

697
static void
698
bc6_lerp(rgba *col, int *e0, int *e1, int s, int sign) {
699
    int r, g, b;
700
    int t = 64 - s;
701
    r = (e0[0] * t + e1[0] * s) >> 6;
702
    g = (e0[1] * t + e1[1] * s) >> 6;
703
    b = (e0[2] * t + e1[2] * s) >> 6;
704
    col->r = bc6_clamp(bc6_finalize(r, sign));
705
    col->g = bc6_clamp(bc6_finalize(g, sign));
706
    col->b = bc6_clamp(bc6_finalize(b, sign));
707
}
708

709
static void
710
decode_bc6_block(rgba *col, const UINT8 *src, int sign) {
711
    UINT16 endpoints[12]; /* storage for r0, g0, b0, r1, ... */
712
    int ueps[12];
713
    int i, i0, ib2, di, dw, mask, numep, s;
714
    UINT8 partition;
715
    const bc6_mode_info *info;
716
    const char *cw;
717
    int bit = 5;
718
    int epbits = 75;
719
    int ib = 3;
720
    int mode = src[0] & 0x1f;
721
    if ((mode & 3) == 0 || (mode & 3) == 1) {
722
        mode &= 3;
723
        bit = 2;
724
    } else if ((mode & 3) == 2) {
725
        mode = 2 + (mode >> 2);
726
        epbits = 72;
727
    } else {
728
        mode = 10 + (mode >> 2);
729
        epbits = 60;
730
        ib = 4;
731
    }
732
    if (mode >= 14) {
733
        /* invalid block */
734
        memset(col, 0, 16 * sizeof(col[0]));
735
        return;
736
    }
737
    info = &bc6_modes[mode];
738
    cw = bc7_get_weights(ib);
739
    numep = info->ns == 2 ? 12 : 6;
740
    for (i = 0; i < 12; i++) {
741
        endpoints[i] = 0;
742
    }
743
    for (i = 0; i < epbits; i++) {
744
        di = bc6_bit_packings[mode][i];
745
        dw = di >> 4;
746
        di &= 15;
747
        endpoints[dw] |= (UINT16)get_bit(src, bit + i) << di;
748
    }
749
    bit += epbits;
750
    partition = get_bits(src, bit, info->pb);
751
    bit += info->pb;
752
    mask = (1 << info->epb) - 1;
753
    if (sign) { /* sign-extend e0 if signed */
754
        bc6_sign_extend(&endpoints[0], info->epb);
755
        bc6_sign_extend(&endpoints[1], info->epb);
756
        bc6_sign_extend(&endpoints[2], info->epb);
757
    }
758
    if (sign || info->tr) { /* sign-extend e1,2,3 if signed or deltas */
759
        for (i = 3; i < numep; i += 3) {
760
            bc6_sign_extend(&endpoints[i], info->rb);
761
            bc6_sign_extend(&endpoints[i + 1], info->gb);
762
            bc6_sign_extend(&endpoints[i + 2], info->bb);
763
        }
764
    }
765
    if (info->tr) { /* apply deltas */
766
        for (i = 3; i < numep; i += 3) {
767
            endpoints[i] = (endpoints[i] + endpoints[0]) & mask;
768
            endpoints[i + 1] = (endpoints[i + 1] + endpoints[1]) & mask;
769
            endpoints[i + 2] = (endpoints[i + 2] + endpoints[2]) & mask;
770
        }
771
    }
772
    for (i = 0; i < numep; i++) {
773
        ueps[i] = bc6_unquantize(endpoints[i], info->epb, sign);
774
    }
775
    for (i = 0; i < 16; i++) {
776
        s = bc7_get_subset(info->ns, partition, i) * 6;
777
        ib2 = ib;
778
        if (i == 0) {
779
            ib2--;
780
        } else if (info->ns == 2) {
781
            if (i == bc7_ai0[partition]) {
782
                ib2--;
783
            }
784
        }
785
        i0 = get_bits(src, bit, ib2);
786
        bit += ib2;
787

788
        bc6_lerp(&col[i], &ueps[s], &ueps[s + 3], cw[i0], sign);
789
    }
790
}
791

792
static void
793
put_block(Imaging im, ImagingCodecState state, const char *col, int sz, int C) {
794
    int width = state->xsize;
795
    int height = state->ysize;
796
    int xmax = width + state->xoff;
797
    int ymax = height + state->yoff;
798
    int j, i, y, x;
799
    char *dst;
800
    for (j = 0; j < 4; j++) {
801
        y = state->y + j;
802
        if (C) {
803
            if (y >= height) {
804
                continue;
805
            }
806
            if (state->ystep < 0) {
807
                y = state->yoff + ymax - y - 1;
808
            }
809
            dst = im->image[y];
810
            for (i = 0; i < 4; i++) {
811
                x = state->x + i;
812
                if (x >= width) {
813
                    continue;
814
                }
815
                memcpy(dst + sz * x, col + sz * (j * 4 + i), sz);
816
            }
817
        } else {
818
            if (state->ystep < 0) {
819
                y = state->yoff + ymax - y - 1;
820
            }
821
            x = state->x;
822
            dst = im->image[y] + sz * x;
823
            memcpy(dst, col + sz * (j * 4), 4 * sz);
824
        }
825
    }
826
    state->x += 4;
827
    if (state->x >= xmax) {
828
        state->y += 4;
829
        state->x = state->xoff;
830
    }
831
}
832

833
static int
834
decode_bcn(
835
    Imaging im,
836
    ImagingCodecState state,
837
    const UINT8 *src,
838
    int bytes,
839
    int N,
840
    int C,
841
    char *pixel_format
842
) {
843
    int ymax = state->ysize + state->yoff;
844
    const UINT8 *ptr = src;
845
    switch (N) {
846
#define DECODE_LOOP(NN, SZ, TY, ...)                                    \
847
    case NN:                                                            \
848
        while (bytes >= SZ) {                                           \
849
            TY col[16];                                                 \
850
            memset(col, 0, 16 * sizeof(col[0]));                        \
851
            decode_bc##NN##_block(col, ptr);                            \
852
            put_block(im, state, (const char *)col, sizeof(col[0]), C); \
853
            ptr += SZ;                                                  \
854
            bytes -= SZ;                                                \
855
            if (state->y >= ymax) {                                     \
856
                return -1;                                              \
857
            }                                                           \
858
        }                                                               \
859
        break
860

861
        DECODE_LOOP(1, 8, rgba);
862
        DECODE_LOOP(2, 16, rgba);
863
        DECODE_LOOP(3, 16, rgba);
864
        DECODE_LOOP(4, 8, lum);
865
        case 5: {
866
            int sign = strcmp(pixel_format, "BC5S") == 0 ? 1 : 0;
867
            while (bytes >= 16) {
868
                rgba col[16];
869
                memset(col, sign ? 128 : 0, 16 * sizeof(col[0]));
870
                decode_bc5_block(col, ptr, sign);
871
                put_block(im, state, (const char *)col, sizeof(col[0]), C);
872
                ptr += 16;
873
                bytes -= 16;
874
                if (state->y >= ymax) {
875
                    return -1;
876
                }
877
            }
878
            break;
879
        }
880
        case 6: {
881
            int sign = strcmp(pixel_format, "BC6HS") == 0 ? 1 : 0;
882
            while (bytes >= 16) {
883
                rgba col[16];
884
                decode_bc6_block(col, ptr, sign);
885
                put_block(im, state, (const char *)col, sizeof(col[0]), C);
886
                ptr += 16;
887
                bytes -= 16;
888
                if (state->y >= ymax) {
889
                    return -1;
890
                }
891
            }
892
            break;
893
        }
894
            DECODE_LOOP(7, 16, rgba);
895
#undef DECODE_LOOP
896
    }
897
    return (int)(ptr - src);
898
}
899

900
int
901
ImagingBcnDecode(Imaging im, ImagingCodecState state, UINT8 *buf, Py_ssize_t bytes) {
902
    int N = state->state & 0xf;
903
    int width = state->xsize;
904
    int height = state->ysize;
905
    int C = (width & 3) | (height & 3) ? 1 : 0;
906
    char *pixel_format = ((BCNSTATE *)state->context)->pixel_format;
907
    return decode_bcn(im, state, buf, bytes, N, C, pixel_format);
908
}
909