libavcodec/smcenc.c

   1 /*
   2  * QuickTime Graphics (SMC) Video Encoder
   3  * Copyright (c) 2021 The FFmpeg project
   4  *
   5  * This file is part of FFmpeg.
   6  *
   7  * FFmpeg is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * FFmpeg is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with FFmpeg; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20  */
  21
  22 /**
  23  * @file smcenc.c
  24  * QT SMC Video Encoder by Paul B. Mahol
  25  */
  26
  27 #include "libavutil/common.h"
  28
  29 #include "avcodec.h"
  30 #include "codec_internal.h"
  31 #include "encode.h"
  32 #include "bytestream.h"
  33
  34 #define CPAIR 2
  35 #define CQUAD 4
  36 #define COCTET 8
  37
  38 #define COLORS_PER_TABLE 256
  39
  40 typedef struct SMCContext {
  41     AVFrame *prev_frame;    // buffer for previous source frame
  42
  43     uint8_t mono_value;
  44     int nb_distinct;
  45     int next_nb_distinct;
  46     uint8_t distinct_values[16];
  47     uint8_t next_distinct_values[16];
  48
  49     uint8_t color_pairs[COLORS_PER_TABLE][CPAIR];
  50     uint8_t color_quads[COLORS_PER_TABLE][CQUAD];
  51     uint8_t color_octets[COLORS_PER_TABLE][COCTET];
  52
  53     int key_frame;
  54 } SMCContext;
  55
  56 #define ADVANCE_BLOCK(pixel_ptr, row_ptr, nb_blocks) \
  57 { \
  58     for (int block = 0; block < nb_blocks && pixel_ptr && row_ptr; block++) { \
  59         pixel_ptr += 4; \
  60         cur_x += 4; \
  61         if (pixel_ptr - row_ptr >= width) \
  62         { \
  63             row_ptr += stride * 4; \
  64             pixel_ptr = row_ptr; \
  65             cur_y += 4; \
  66             cur_x  = 0; \
  67         } \
  68     } \
  69 }
  70
  71 static int smc_cmp_values(const void *a, const void *b)
  72 {
  73     const uint8_t *aa = a, *bb = b;
  74
  75     return FFDIFFSIGN(aa[0], bb[0]);
  76 }
  77
  78 static int count_distinct_items(const uint8_t *block_values,
  79                                 uint8_t *distinct_values,
  80                                 int size)
  81 {
  82     int n = 1;
  83
  84     distinct_values[0] = block_values[0];
  85     for (int i = 1; i < size; i++) {
  86         if (block_values[i] != block_values[i-1]) {
  87             distinct_values[n] = block_values[i];
  88             n++;
  89         }
  90     }
  91
  92     return n;
  93 }
  94
  95 #define CACHE_PAIR(x) \
  96     (s->color_pairs[i][0] == distinct_values[x] || \
  97      s->color_pairs[i][1] == distinct_values[x])
  98
  99 #define CACHE_QUAD(x) \
 100     (s->color_quads[i][0] == distinct_values[x] || \
 101      s->color_quads[i][1] == distinct_values[x] || \
 102      s->color_quads[i][2] == distinct_values[x] || \
 103      s->color_quads[i][3] == distinct_values[x])
 104
 105 #define CACHE_OCTET(x) \
 106     (s->color_octets[i][0] == distinct_values[x] || \
 107      s->color_octets[i][1] == distinct_values[x] || \
 108      s->color_octets[i][2] == distinct_values[x] || \
 109      s->color_octets[i][3] == distinct_values[x] || \
 110      s->color_octets[i][4] == distinct_values[x] || \
 111      s->color_octets[i][5] == distinct_values[x] || \
 112      s->color_octets[i][6] == distinct_values[x] || \
 113      s->color_octets[i][7] == distinct_values[x])
 114
 115 static void smc_encode_stream(SMCContext *s, const AVFrame *frame,
 116                               PutByteContext *pb)
 117 {
 118     const uint8_t *src_pixels = (const uint8_t *)frame->data[0];
 119     const ptrdiff_t stride = frame->linesize[0];
 120     const uint8_t *prev_pixels = (const uint8_t *)s->prev_frame->data[0];
 121     const ptrdiff_t prev_stride = s->prev_frame->linesize[0];
 122     uint8_t *distinct_values = s->distinct_values;
 123     const uint8_t *pixel_ptr, *row_ptr;
 124     const int height = frame->height;
 125     const int width = frame->width;
 126     int block_counter = 0;
 127     int color_pair_index = 0;
 128     int color_quad_index = 0;
 129     int color_octet_index = 0;
 130     int color_table_index;  /* indexes to color pair, quad, or octet tables */
 131     int total_blocks;
 132     int cur_y = 0;
 133     int cur_x = 0;
 134
 135     /* Number of 4x4 blocks in frame. */
 136     total_blocks = ((width + 3) / 4) * ((height + 3) / 4);
 137
 138     pixel_ptr = row_ptr = src_pixels;
 139
 140     while (block_counter < total_blocks) {
 141         const uint8_t *xpixel_ptr = pixel_ptr;
 142         const uint8_t *xrow_ptr = row_ptr;
 143         int intra_skip_blocks = 0;
 144         int inter_skip_blocks = 0;
 145         int coded_distinct = 0;
 146         int coded_blocks = 0;
 147         int cache_index;
 148         int distinct = 0;
 149         int blocks = 0;
 150         int frame_y = cur_y;
 151         int frame_x = cur_x;
 152
 153         while (prev_pixels && s->key_frame == 0 && block_counter + inter_skip_blocks < total_blocks) {
 154             const int y_size = FFMIN(4, height - cur_y);
 155             const int x_size = FFMIN(4, width  - cur_x);
 156             int compare = 0;
 157
 158             for (int y = 0; y < y_size; y++) {
 159                 const uint8_t *prev_pixel_ptr = prev_pixels + (y + cur_y) * prev_stride + cur_x;
 160
 161                 compare |= !!memcmp(prev_pixel_ptr, pixel_ptr + y * stride, x_size);
 162                 if (compare)
 163                     break;
 164             }
 165
 166             if (compare)
 167                 break;
 168
 169             inter_skip_blocks++;
 170             if (inter_skip_blocks >= 256)
 171                 break;
 172
 173             ADVANCE_BLOCK(pixel_ptr, row_ptr, 1)
 174         }
 175
 176         pixel_ptr = xpixel_ptr;
 177         row_ptr = xrow_ptr;
 178         cur_y = frame_y;
 179         cur_x = frame_x;
 180
 181         while (block_counter > 0 && block_counter + intra_skip_blocks < total_blocks) {
 182             const int y_size = FFMIN(4, height - cur_y);
 183             const int x_size = FFMIN(4, width  - cur_x);
 184             const ptrdiff_t offset = xpixel_ptr - src_pixels;
 185             const int sy = offset / stride;
 186             const int sx = offset % stride;
 187             const int ny = sx < 4 ? FFMAX(sy - 4, 0) : sy;
 188             const int nx = sx < 4 ? FFMAX(width - 4 + (width & 3), 0) : sx - 4;
 189             const uint8_t *old_pixel_ptr = src_pixels + nx + ny * stride;
 190             int compare = 0;
 191
 192             for (int y = 0; y < y_size; y++) {
 193                 compare |= !!memcmp(old_pixel_ptr + y * stride, pixel_ptr + y * stride, x_size);
 194                 if (compare)
 195                     break;
 196             }
 197
 198             if (compare)
 199                 break;
 200
 201             intra_skip_blocks++;
 202             if (intra_skip_blocks >= 256)
 203                 break;
 204
 205             ADVANCE_BLOCK(pixel_ptr, row_ptr, 1)
 206         }
 207
 208         pixel_ptr = xpixel_ptr;
 209         row_ptr = xrow_ptr;
 210         cur_y = frame_y;
 211         cur_x = frame_x;
 212
 213         while (block_counter + coded_blocks < total_blocks && coded_blocks < 256) {
 214             const int y_size = FFMIN(4, height - cur_y);
 215             const int x_size = FFMIN(4, width  - cur_x);
 216             const int nb_elements = x_size * y_size;
 217             uint8_t block_values[16] = { 0 };
 218             for (int y = 0; y < y_size; y++)
 219                 memcpy(block_values + y * x_size, pixel_ptr + y * stride, x_size);
 220
 221             qsort(block_values, nb_elements, sizeof(block_values[0]), smc_cmp_values);
 222             s->next_nb_distinct = count_distinct_items(block_values, s->next_distinct_values, nb_elements);
 223             if (coded_blocks == 0) {
 224                 memcpy(distinct_values, s->next_distinct_values, sizeof(s->distinct_values));
 225                 s->nb_distinct = s->next_nb_distinct;
 226             } else {
 227                 if (s->next_nb_distinct != s->nb_distinct ||
 228                     memcmp(distinct_values, s->next_distinct_values, s->nb_distinct)) {
 229                     break;
 230                 }
 231             }
 232             s->mono_value = block_values[0];
 233
 234             coded_distinct = s->nb_distinct;
 235             coded_blocks++;
 236             if (coded_distinct > 1 && coded_blocks >= 16)
 237                 break;
 238
 239             ADVANCE_BLOCK(pixel_ptr, row_ptr, 1)
 240         }
 241
 242         pixel_ptr = xpixel_ptr;
 243         row_ptr = xrow_ptr;
 244         cur_y = frame_y;
 245         cur_x = frame_x;
 246
 247         blocks = coded_distinct <= 8 ? coded_blocks : 0;
 248         distinct = coded_distinct;
 249
 250         if (intra_skip_blocks >= blocks && intra_skip_blocks >= inter_skip_blocks) {
 251             distinct = 17;
 252             blocks = intra_skip_blocks;
 253         }
 254
 255         if (intra_skip_blocks > 16 && intra_skip_blocks >= inter_skip_blocks &&
 256             intra_skip_blocks >= blocks) {
 257             distinct = 18;
 258             blocks = intra_skip_blocks;
 259         }
 260
 261         if (inter_skip_blocks >= blocks && inter_skip_blocks > intra_skip_blocks) {
 262             distinct = 19;
 263             blocks = inter_skip_blocks;
 264         }
 265
 266         if (inter_skip_blocks > 16 && inter_skip_blocks > intra_skip_blocks &&
 267             inter_skip_blocks >= blocks) {
 268             distinct = 20;
 269             blocks = inter_skip_blocks;
 270         }
 271
 272         if (blocks == 0) {
 273             blocks = coded_blocks;
 274             distinct = coded_distinct;
 275         }
 276
 277         switch (distinct) {
 278         case 1:
 279             if (blocks <= 16) {
 280                 bytestream2_put_byte(pb, 0x60 | (blocks - 1));
 281             } else {
 282                 bytestream2_put_byte(pb, 0x70);
 283                 bytestream2_put_byte(pb, blocks - 1);
 284             }
 285             bytestream2_put_byte(pb, s->mono_value);
 286             ADVANCE_BLOCK(pixel_ptr, row_ptr, blocks)
 287             break;
 288         case 2:
 289             cache_index = -1;
 290             for (int i = 0; i < COLORS_PER_TABLE; i++) {
 291                 if (CACHE_PAIR(0) &&
 292                     CACHE_PAIR(1)) {
 293                     cache_index = i;
 294                     break;
 295                 }
 296             }
 297
 298             if (cache_index >= 0) {
 299                 bytestream2_put_byte(pb, 0x90 | (blocks - 1));
 300                 bytestream2_put_byte(pb, cache_index);
 301                 color_table_index = cache_index;
 302             } else {
 303                 bytestream2_put_byte(pb, 0x80 | (blocks - 1));
 304
 305                 color_table_index = color_pair_index;
 306                 for (int i = 0; i < CPAIR; i++) {
 307                     s->color_pairs[color_table_index][i] = distinct_values[i];
 308                     bytestream2_put_byte(pb, distinct_values[i]);
 309                 }
 310
 311                 color_pair_index++;
 312                 if (color_pair_index == COLORS_PER_TABLE)
 313                     color_pair_index = 0;
 314             }
 315
 316             for (int i = 0; i < blocks; i++) {
 317                 const int y_size = FFMIN(4, height - cur_y);
 318                 const int x_size = FFMIN(4, width  - cur_x);
 319                 uint8_t value = s->color_pairs[color_table_index][1];
 320                 uint16_t flags = 0;
 321                 int shift = 15;
 322
 323                 for (int y = 0; y < y_size; y++) {
 324                     for (int x = 0; x < x_size; x++) {
 325                         flags |= (value == pixel_ptr[x + y * stride]) << shift;
 326                         shift--;
 327                     }
 328                     shift -= 4 - x_size;
 329                 }
 330
 331                 bytestream2_put_be16(pb, flags);
 332
 333                 ADVANCE_BLOCK(pixel_ptr, row_ptr, 1)
 334             }
 335             break;
 336         case 3:
 337         case 4:
 338             cache_index = -1;
 339             for (int i = 0; i < COLORS_PER_TABLE; i++) {
 340                 if (CACHE_QUAD(0) &&
 341                     CACHE_QUAD(1) &&
 342                     CACHE_QUAD(2) &&
 343                     CACHE_QUAD(3)) {
 344                     cache_index = i;
 345                     break;
 346                 }
 347             }
 348
 349             if (cache_index >= 0) {
 350                 bytestream2_put_byte(pb, 0xB0 | (blocks - 1));
 351                 bytestream2_put_byte(pb, cache_index);
 352                 color_table_index = cache_index;
 353             } else {
 354                 bytestream2_put_byte(pb, 0xA0 | (blocks - 1));
 355
 356                 color_table_index = color_quad_index;
 357                 for (int i = 0; i < CQUAD; i++) {
 358                     s->color_quads[color_table_index][i] = distinct_values[i];
 359                     bytestream2_put_byte(pb, distinct_values[i]);
 360                 }
 361
 362                 color_quad_index++;
 363                 if (color_quad_index == COLORS_PER_TABLE)
 364                     color_quad_index = 0;
 365             }
 366
 367             for (int i = 0; i < blocks; i++) {
 368                 const int y_size = FFMIN(4, height - cur_y);
 369                 const int x_size = FFMIN(4, width  - cur_x);
 370                 uint32_t flags = 0;
 371                 uint8_t quad[4];
 372                 int shift = 30;
 373
 374                 for (int k = 0; k < 4; k++)
 375                     quad[k] = s->color_quads[color_table_index][k];
 376
 377                 for (int y = 0; y < y_size; y++) {
 378                     for (int x = 0; x < x_size; x++) {
 379                         int pixel = pixel_ptr[x + y * stride];
 380                         uint32_t idx = 0;
 381
 382                         for (int w = 0; w < CQUAD; w++) {
 383                             if (quad[w] == pixel) {
 384                                 idx = w;
 385                                 break;
 386                             }
 387                         }
 388
 389                         flags |= idx << shift;
 390                         shift -= 2;
 391                     }
 392
 393                     shift -= 2 * (4 - x_size);
 394                 }
 395
 396                 bytestream2_put_be32(pb, flags);
 397
 398                 ADVANCE_BLOCK(pixel_ptr, row_ptr, 1)
 399             }
 400             break;
 401         case 5:
 402         case 6:
 403         case 7:
 404         case 8:
 405             cache_index = -1;
 406             for (int i = 0; i < COLORS_PER_TABLE; i++) {
 407                 if (CACHE_OCTET(0) &&
 408                     CACHE_OCTET(1) &&
 409                     CACHE_OCTET(2) &&
 410                     CACHE_OCTET(3) &&
 411                     CACHE_OCTET(4) &&
 412                     CACHE_OCTET(5) &&
 413                     CACHE_OCTET(6) &&
 414                     CACHE_OCTET(7)) {
 415                     cache_index = i;
 416                     break;
 417                 }
 418             }
 419
 420             if (cache_index >= 0) {
 421                 bytestream2_put_byte(pb, 0xD0 | (blocks - 1));
 422                 bytestream2_put_byte(pb, cache_index);
 423                 color_table_index = cache_index;
 424             } else {
 425                 bytestream2_put_byte(pb, 0xC0 | (blocks - 1));
 426
 427                 color_table_index = color_octet_index;
 428                 for (int i = 0; i < COCTET; i++) {
 429                     s->color_octets[color_table_index][i] = distinct_values[i];
 430                     bytestream2_put_byte(pb, distinct_values[i]);
 431                 }
 432
 433                 color_octet_index++;
 434                 if (color_octet_index == COLORS_PER_TABLE)
 435                     color_octet_index = 0;
 436             }
 437
 438             for (int i = 0; i < blocks; i++) {
 439                 const int y_size = FFMIN(4, height - cur_y);
 440                 const int x_size = FFMIN(4, width  - cur_x);
 441                 uint64_t flags = 0;
 442                 uint8_t octet[8];
 443                 int shift = 45;
 444
 445                 for (int k = 0; k < 8; k++)
 446                     octet[k] = s->color_octets[color_table_index][k];
 447
 448                 for (int y = 0; y < y_size; y++) {
 449                     for (int x = 0; x < x_size; x++) {
 450                         int pixel = pixel_ptr[x + y * stride];
 451                         uint64_t idx = 0;
 452
 453                         for (int w = 0; w < COCTET; w++) {
 454                             if (octet[w] == pixel) {
 455                                 idx = w;
 456                                 break;
 457                             }
 458                         }
 459
 460                         flags |= idx << shift;
 461                         shift -= 3;
 462                     }
 463
 464                     shift -= 3 * (4 - x_size);
 465                 }
 466
 467                 bytestream2_put_be16(pb, ((flags >> 32) & 0xFFF0) | ((flags >> 8) & 0xF));
 468                 bytestream2_put_be16(pb, ((flags >> 20) & 0xFFF0) | ((flags >> 4) & 0xF));
 469                 bytestream2_put_be16(pb, ((flags >>  8) & 0xFFF0) | ((flags >> 0) & 0xF));
 470
 471                 ADVANCE_BLOCK(pixel_ptr, row_ptr, 1)
 472             }
 473             break;
 474         default:
 475             bytestream2_put_byte(pb, 0xE0 | (blocks - 1));
 476             for (int i = 0; i < blocks; i++) {
 477                 const int y_size = FFMIN(4, height - cur_y);
 478                 const int x_size = FFMIN(4, width  - cur_x);
 479                 for (int y = 0; y < y_size; y++) {
 480                     for (int x = 0; x < x_size; x++)
 481                         bytestream2_put_byte(pb, pixel_ptr[x + y * stride]);
 482                     for (int x = x_size; x < 4; x++)
 483                         bytestream2_put_byte(pb, 0);
 484                 }
 485
 486                 for (int y = y_size; y < 4; y++) {
 487                     for (int x = 0; x < 4; x++)
 488                         bytestream2_put_byte(pb, 0);
 489                 }
 490
 491                 ADVANCE_BLOCK(pixel_ptr, row_ptr, 1)
 492             }
 493             break;
 494         case 17:
 495             bytestream2_put_byte(pb, 0x20 | (blocks - 1));
 496             ADVANCE_BLOCK(pixel_ptr, row_ptr, blocks)
 497             break;
 498         case 18:
 499             bytestream2_put_byte(pb, 0x30);
 500             bytestream2_put_byte(pb, blocks - 1);
 501             ADVANCE_BLOCK(pixel_ptr, row_ptr, blocks)
 502             break;
 503         case 19:
 504             bytestream2_put_byte(pb, 0x00 | (blocks - 1));
 505             ADVANCE_BLOCK(pixel_ptr, row_ptr, blocks)
 506             break;
 507         case 20:
 508             bytestream2_put_byte(pb, 0x10);
 509             bytestream2_put_byte(pb, blocks - 1);
 510             ADVANCE_BLOCK(pixel_ptr, row_ptr, blocks)
 511             break;
 512         }
 513
 514         block_counter += blocks;
 515     }
 516 }
 517
 518 static int smc_encode_init(AVCodecContext *avctx)
 519 {
 520     SMCContext *s = avctx->priv_data;
 521
 522     avctx->bits_per_coded_sample = 8;
 523
 524     s->prev_frame = av_frame_alloc();
 525     if (!s->prev_frame)
 526         return AVERROR(ENOMEM);
 527
 528     return 0;
 529 }
 530
 531 static int smc_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
 532                                 const AVFrame *frame, int *got_packet)
 533 {
 534     SMCContext *s = avctx->priv_data;
 535     const AVFrame *pict = frame;
 536     PutByteContext pb;
 537     uint8_t *pal;
 538     int ret;
 539
 540     ret = ff_alloc_packet(avctx, pkt, 8LL * avctx->height * avctx->width);
 541     if (ret < 0)
 542         return ret;
 543
 544     if (avctx->gop_size == 0 || !s->prev_frame->data[0] ||
 545         (avctx->frame_num % avctx->gop_size) == 0) {
 546         s->key_frame = 1;
 547     } else {
 548         s->key_frame = 0;
 549     }
 550
 551     bytestream2_init_writer(&pb, pkt->data, pkt->size);
 552
 553     bytestream2_put_be32(&pb, 0x00);
 554
 555     pal = av_packet_new_side_data(pkt, AV_PKT_DATA_PALETTE, AVPALETTE_SIZE);
 556     if (!pal)
 557         return AVERROR(ENOMEM);
 558     memcpy(pal, frame->data[1], AVPALETTE_SIZE);
 559
 560     smc_encode_stream(s, pict, &pb);
 561
 562     av_shrink_packet(pkt, bytestream2_tell_p(&pb));
 563
 564     pkt->data[0] = 0x0;
 565
 566     // write chunk length
 567     AV_WB24(pkt->data + 1, pkt->size);
 568
 569     ret = av_frame_replace(s->prev_frame, frame);
 570     if (ret < 0) {
 571         av_log(avctx, AV_LOG_ERROR, "cannot add reference\n");
 572         return ret;
 573     }
 574
 575     if (s->key_frame)
 576         pkt->flags |= AV_PKT_FLAG_KEY;
 577
 578     *got_packet = 1;
 579
 580     return 0;
 581 }
 582
 583 static int smc_encode_end(AVCodecContext *avctx)
 584 {
 585     SMCContext *s = avctx->priv_data;
 586
 587     av_frame_free(&s->prev_frame);
 588
 589     return 0;
 590 }
 591
 592 const FFCodec ff_smc_encoder = {
 593     .p.name         = "smc",
 594     CODEC_LONG_NAME("QuickTime Graphics (SMC)"),
 595     .p.type         = AVMEDIA_TYPE_VIDEO,
 596     .p.id           = AV_CODEC_ID_SMC,
 597     .p.capabilities = AV_CODEC_CAP_DR1 | AV_CODEC_CAP_ENCODER_REORDERED_OPAQUE,
 598     .priv_data_size = sizeof(SMCContext),
 599     .init           = smc_encode_init,
 600     FF_CODEC_ENCODE_CB(smc_encode_frame),
 601     .close          = smc_encode_end,
 602     .p.pix_fmts     = (const enum AVPixelFormat[]) { AV_PIX_FMT_PAL8,
 603                                                      AV_PIX_FMT_NONE},
 604 };