git.sesse.net Git - ffmpeg/blob - libavcodec/xan.c

   1 /*
   2  * Wing Commander/Xan Video Decoder
   3  * Copyright (C) 2003 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
  24  * Xan video decoder for Wing Commander III computer game
  25  * by Mario Brito (mbrito@student.dei.uc.pt)
  26  * and Mike Melanson (melanson@pcisys.net)
  27  *
  28  * The xan_wc3 decoder outputs PAL8 data.
  29  */
  30
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #include "libavutil/intreadwrite.h"
  36 #include "avcodec.h"
  37 #include "bytestream.h"
  38 #define ALT_BITSTREAM_READER_LE
  39 #include "get_bits.h"
  40 // for av_memcpy_backptr
  41 #include "libavutil/lzo.h"
  42
  43 #define RUNTIME_GAMMA 0
  44
  45 #define VGA__TAG MKTAG('V', 'G', 'A', ' ')
  46 #define PALT_TAG MKTAG('P', 'A', 'L', 'T')
  47 #define SHOT_TAG MKTAG('S', 'H', 'O', 'T')
  48 #define PALETTE_COUNT 256
  49 #define PALETTE_SIZE (PALETTE_COUNT * 3)
  50 #define PALETTES_MAX 256
  51
  52 typedef struct XanContext {
  53
  54     AVCodecContext *avctx;
  55     AVFrame last_frame;
  56     AVFrame current_frame;
  57
  58     const unsigned char *buf;
  59     int size;
  60
  61     /* scratch space */
  62     unsigned char *buffer1;
  63     int buffer1_size;
  64     unsigned char *buffer2;
  65     int buffer2_size;
  66
  67     unsigned *palettes;
  68     int palettes_count;
  69     int cur_palette;
  70
  71     int frame_size;
  72
  73 } XanContext;
  74
  75 static av_cold int xan_decode_init(AVCodecContext *avctx)
  76 {
  77     XanContext *s = avctx->priv_data;
  78
  79     s->avctx = avctx;
  80     s->frame_size = 0;
  81
  82     avctx->pix_fmt = PIX_FMT_PAL8;
  83
  84     s->buffer1_size = avctx->width * avctx->height;
  85     s->buffer1 = av_malloc(s->buffer1_size);
  86     if (!s->buffer1)
  87         return AVERROR(ENOMEM);
  88     s->buffer2_size = avctx->width * avctx->height;
  89     s->buffer2 = av_malloc(s->buffer2_size + 130);
  90     if (!s->buffer2) {
  91         av_freep(&s->buffer1);
  92         return AVERROR(ENOMEM);
  93     }
  94     avcodec_get_frame_defaults(&s->last_frame);
  95     avcodec_get_frame_defaults(&s->current_frame);
  96
  97     return 0;
  98 }
  99
 100 static int xan_huffman_decode(unsigned char *dest, int dest_len,
 101                               const unsigned char *src, int src_len)
 102 {
 103     unsigned char byte = *src++;
 104     unsigned char ival = byte + 0x16;
 105     const unsigned char * ptr = src + byte*2;
 106     int ptr_len = src_len - 1 - byte*2;
 107     unsigned char val = ival;
 108     unsigned char *dest_end = dest + dest_len;
 109     GetBitContext gb;
 110
 111     if (ptr_len < 0)
 112         return AVERROR_INVALIDDATA;
 113
 114     init_get_bits(&gb, ptr, ptr_len * 8);
 115
 116     while ( val != 0x16 ) {
 117         unsigned idx = val - 0x17 + get_bits1(&gb) * byte;
 118         if (idx >= 2 * byte)
 119             return -1;
 120         val = src[idx];
 121
 122         if ( val < 0x16 ) {
 123             if (dest >= dest_end)
 124                 return 0;
 125             *dest++ = val;
 126             val = ival;
 127         }
 128     }
 129
 130     return 0;
 131 }
 132
 133 /**
 134  * unpack simple compression
 135  *
 136  * @param dest destination buffer of dest_len, must be padded with at least 130 bytes
 137  */
 138 static void xan_unpack(unsigned char *dest, int dest_len,
 139                        const unsigned char *src, int src_len)
 140 {
 141     unsigned char opcode;
 142     int size;
 143     unsigned char *dest_org = dest;
 144     unsigned char *dest_end = dest + dest_len;
 145     const unsigned char *src_end = src + src_len;
 146
 147     while (dest < dest_end && src < src_end) {
 148         opcode = *src++;
 149
 150         if (opcode < 0xe0) {
 151             int size2, back;
 152             if ( (opcode & 0x80) == 0 ) {
 153
 154                 size = opcode & 3;
 155
 156                 back  = ((opcode & 0x60) << 3) + *src++ + 1;
 157                 size2 = ((opcode & 0x1c) >> 2) + 3;
 158
 159             } else if ( (opcode & 0x40) == 0 ) {
 160
 161                 size = *src >> 6;
 162
 163                 back  = (bytestream_get_be16(&src) & 0x3fff) + 1;
 164                 size2 = (opcode & 0x3f) + 4;
 165
 166             } else {
 167
 168                 size = opcode & 3;
 169
 170                 back  = ((opcode & 0x10) << 12) + bytestream_get_be16(&src) + 1;
 171                 size2 = ((opcode & 0x0c) <<  6) + *src++ + 5;
 172             }
 173             if (dest_end - dest < size + size2 ||
 174                 dest + size - dest_org < back ||
 175                 src_end - src < size)
 176                 return;
 177             memcpy(dest, src, size);  dest += size;  src += size;
 178             av_memcpy_backptr(dest, back, size2);
 179             dest += size2;
 180         } else {
 181             int finish = opcode >= 0xfc;
 182             size = finish ? opcode & 3 : ((opcode & 0x1f) << 2) + 4;
 183
 184             if (dest_end - dest < size || src_end - src < size)
 185                 return;
 186             memcpy(dest, src, size);  dest += size;  src += size;
 187             if (finish)
 188                 return;
 189         }
 190     }
 191 }
 192
 193 static inline void xan_wc3_output_pixel_run(XanContext *s,
 194     const unsigned char *pixel_buffer, int x, int y, int pixel_count)
 195 {
 196     int stride;
 197     int line_inc;
 198     int index;
 199     int current_x;
 200     int width = s->avctx->width;
 201     unsigned char *palette_plane;
 202
 203     palette_plane = s->current_frame.data[0];
 204     stride = s->current_frame.linesize[0];
 205     line_inc = stride - width;
 206     index = y * stride + x;
 207     current_x = x;
 208     while(pixel_count && (index < s->frame_size)) {
 209         int count = FFMIN(pixel_count, width - current_x);
 210         memcpy(palette_plane + index, pixel_buffer, count);
 211         pixel_count  -= count;
 212         index        += count;
 213         pixel_buffer += count;
 214         current_x    += count;
 215
 216         if (current_x >= width) {
 217             index += line_inc;
 218             current_x = 0;
 219         }
 220     }
 221 }
 222
 223 static inline void xan_wc3_copy_pixel_run(XanContext *s,
 224     int x, int y, int pixel_count, int motion_x, int motion_y)
 225 {
 226     int stride;
 227     int line_inc;
 228     int curframe_index, prevframe_index;
 229     int curframe_x, prevframe_x;
 230     int width = s->avctx->width;
 231     unsigned char *palette_plane, *prev_palette_plane;
 232
 233     if ( y + motion_y < 0 || y + motion_y >= s->avctx->height ||
 234          x + motion_x < 0 || x + motion_x >= s->avctx->width)
 235         return;
 236
 237     palette_plane = s->current_frame.data[0];
 238     prev_palette_plane = s->last_frame.data[0];
 239     if (!prev_palette_plane)
 240         prev_palette_plane = palette_plane;
 241     stride = s->current_frame.linesize[0];
 242     line_inc = stride - width;
 243     curframe_index = y * stride + x;
 244     curframe_x = x;
 245     prevframe_index = (y + motion_y) * stride + x + motion_x;
 246     prevframe_x = x + motion_x;
 247     while(pixel_count &&
 248           curframe_index  < s->frame_size &&
 249           prevframe_index < s->frame_size) {
 250         int count = FFMIN3(pixel_count, width - curframe_x, width - prevframe_x);
 251
 252         memcpy(palette_plane + curframe_index, prev_palette_plane + prevframe_index, count);
 253         pixel_count     -= count;
 254         curframe_index  += count;
 255         prevframe_index += count;
 256         curframe_x      += count;
 257         prevframe_x     += count;
 258
 259         if (curframe_x >= width) {
 260             curframe_index += line_inc;
 261             curframe_x = 0;
 262         }
 263
 264         if (prevframe_x >= width) {
 265             prevframe_index += line_inc;
 266             prevframe_x = 0;
 267         }
 268     }
 269 }
 270
 271 static int xan_wc3_decode_frame(XanContext *s) {
 272
 273     int width = s->avctx->width;
 274     int height = s->avctx->height;
 275     int total_pixels = width * height;
 276     unsigned char opcode;
 277     unsigned char flag = 0;
 278     int size = 0;
 279     int motion_x, motion_y;
 280     int x, y;
 281
 282     unsigned char *opcode_buffer = s->buffer1;
 283     unsigned char *opcode_buffer_end = s->buffer1 + s->buffer1_size;
 284     int opcode_buffer_size = s->buffer1_size;
 285     const unsigned char *imagedata_buffer = s->buffer2;
 286
 287     /* pointers to segments inside the compressed chunk */
 288     const unsigned char *huffman_segment;
 289     const unsigned char *size_segment;
 290     const unsigned char *vector_segment;
 291     const unsigned char *imagedata_segment;
 292     int huffman_offset, size_offset, vector_offset, imagedata_offset, imagedata_size;
 293
 294     if (s->size < 8)
 295         return AVERROR_INVALIDDATA;
 296
 297     huffman_offset    = AV_RL16(&s->buf[0]);
 298     size_offset       = AV_RL16(&s->buf[2]);
 299     vector_offset     = AV_RL16(&s->buf[4]);
 300     imagedata_offset  = AV_RL16(&s->buf[6]);
 301
 302     if (huffman_offset   >= s->size ||
 303         size_offset      >= s->size ||
 304         vector_offset    >= s->size ||
 305         imagedata_offset >= s->size)
 306         return AVERROR_INVALIDDATA;
 307
 308     huffman_segment   = s->buf + huffman_offset;
 309     size_segment      = s->buf + size_offset;
 310     vector_segment    = s->buf + vector_offset;
 311     imagedata_segment = s->buf + imagedata_offset;
 312
 313     if (xan_huffman_decode(opcode_buffer, opcode_buffer_size,
 314                            huffman_segment, s->size - huffman_offset) < 0)
 315         return AVERROR_INVALIDDATA;
 316
 317     if (imagedata_segment[0] == 2) {
 318         xan_unpack(s->buffer2, s->buffer2_size,
 319                    &imagedata_segment[1], s->size - imagedata_offset - 1);
 320         imagedata_size = s->buffer2_size;
 321     } else {
 322         imagedata_size = s->size - imagedata_offset - 1;
 323         imagedata_buffer = &imagedata_segment[1];
 324     }
 325
 326     /* use the decoded data segments to build the frame */
 327     x = y = 0;
 328     while (total_pixels && opcode_buffer < opcode_buffer_end) {
 329
 330         opcode = *opcode_buffer++;
 331         size = 0;
 332
 333         switch (opcode) {
 334
 335         case 0:
 336             flag ^= 1;
 337             continue;
 338
 339         case 1:
 340         case 2:
 341         case 3:
 342         case 4:
 343         case 5:
 344         case 6:
 345         case 7:
 346         case 8:
 347             size = opcode;
 348             break;
 349
 350         case 12:
 351         case 13:
 352         case 14:
 353         case 15:
 354         case 16:
 355         case 17:
 356         case 18:
 357             size += (opcode - 10);
 358             break;
 359
 360         case 9:
 361         case 19:
 362             size = *size_segment++;
 363             break;
 364
 365         case 10:
 366         case 20:
 367             size = AV_RB16(&size_segment[0]);
 368             size_segment += 2;
 369             break;
 370
 371         case 11:
 372         case 21:
 373             size = AV_RB24(size_segment);
 374             size_segment += 3;
 375             break;
 376         }
 377         if (size > total_pixels)
 378             break;
 379
 380         if (opcode < 12) {
 381             flag ^= 1;
 382             if (flag) {
 383                 /* run of (size) pixels is unchanged from last frame */
 384                 xan_wc3_copy_pixel_run(s, x, y, size, 0, 0);
 385             } else {
 386                 /* output a run of pixels from imagedata_buffer */
 387                 if (imagedata_size < size)
 388                     break;
 389                 xan_wc3_output_pixel_run(s, imagedata_buffer, x, y, size);
 390                 imagedata_buffer += size;
 391                 imagedata_size -= size;
 392             }
 393         } else {
 394             /* run-based motion compensation from last frame */
 395             motion_x = sign_extend(*vector_segment >> 4,  4);
 396             motion_y = sign_extend(*vector_segment & 0xF, 4);
 397             vector_segment++;
 398
 399             /* copy a run of pixels from the previous frame */
 400             xan_wc3_copy_pixel_run(s, x, y, size, motion_x, motion_y);
 401
 402             flag = 0;
 403         }
 404
 405         /* coordinate accounting */
 406         total_pixels -= size;
 407         y += (x + size) / width;
 408         x  = (x + size) % width;
 409     }
 410     return 0;
 411 }
 412
 413 #if RUNTIME_GAMMA
 414 static inline unsigned mul(unsigned a, unsigned b)
 415 {
 416     return (a * b) >> 16;
 417 }
 418
 419 static inline unsigned pow4(unsigned a)
 420 {
 421     unsigned square = mul(a, a);
 422     return mul(square, square);
 423 }
 424
 425 static inline unsigned pow5(unsigned a)
 426 {
 427     return mul(pow4(a), a);
 428 }
 429
 430 static uint8_t gamma_corr(uint8_t in) {
 431     unsigned lo, hi = 0xff40, target;
 432     int i = 15;
 433     in = (in << 2) | (in >> 6);
 434     /*  equivalent float code:
 435     if (in >= 252)
 436         return 253;
 437     return round(pow(in / 256.0, 0.8) * 256);
 438     */
 439     lo = target = in << 8;
 440     do {
 441         unsigned mid = (lo + hi) >> 1;
 442         unsigned pow = pow5(mid);
 443         if (pow > target) hi = mid;
 444         else lo = mid;
 445     } while (--i);
 446     return (pow4((lo + hi) >> 1) + 0x80) >> 8;
 447 }
 448 #else
 449 /**
 450  * This is a gamma correction that xan3 applies to all palette entries.
 451  *
 452  * There is a peculiarity, namely that the values are clamped to 253 -
 453  * it seems likely that this table was calculated by a buggy fixed-point
 454  * implementation, the one above under RUNTIME_GAMMA behaves like this for
 455  * example.
 456  * The exponent value of 0.8 can be explained by this as well, since 0.8 = 4/5
 457  * and thus pow(x, 0.8) is still easy to calculate.
 458  * Also, the input values are first rotated to the left by 2.
 459  */
 460 static const uint8_t gamma_lookup[256] = {
 461     0x00, 0x09, 0x10, 0x16, 0x1C, 0x21, 0x27, 0x2C,
 462     0x31, 0x35, 0x3A, 0x3F, 0x43, 0x48, 0x4C, 0x50,
 463     0x54, 0x59, 0x5D, 0x61, 0x65, 0x69, 0x6D, 0x71,
 464     0x75, 0x79, 0x7D, 0x80, 0x84, 0x88, 0x8C, 0x8F,
 465     0x93, 0x97, 0x9A, 0x9E, 0xA2, 0xA5, 0xA9, 0xAC,
 466     0xB0, 0xB3, 0xB7, 0xBA, 0xBE, 0xC1, 0xC5, 0xC8,
 467     0xCB, 0xCF, 0xD2, 0xD5, 0xD9, 0xDC, 0xDF, 0xE3,
 468     0xE6, 0xE9, 0xED, 0xF0, 0xF3, 0xF6, 0xFA, 0xFD,
 469     0x03, 0x0B, 0x12, 0x18, 0x1D, 0x23, 0x28, 0x2D,
 470     0x32, 0x36, 0x3B, 0x40, 0x44, 0x49, 0x4D, 0x51,
 471     0x56, 0x5A, 0x5E, 0x62, 0x66, 0x6A, 0x6E, 0x72,
 472     0x76, 0x7A, 0x7D, 0x81, 0x85, 0x89, 0x8D, 0x90,
 473     0x94, 0x98, 0x9B, 0x9F, 0xA2, 0xA6, 0xAA, 0xAD,
 474     0xB1, 0xB4, 0xB8, 0xBB, 0xBF, 0xC2, 0xC5, 0xC9,
 475     0xCC, 0xD0, 0xD3, 0xD6, 0xDA, 0xDD, 0xE0, 0xE4,
 476     0xE7, 0xEA, 0xED, 0xF1, 0xF4, 0xF7, 0xFA, 0xFD,
 477     0x05, 0x0D, 0x13, 0x19, 0x1F, 0x24, 0x29, 0x2E,
 478     0x33, 0x38, 0x3C, 0x41, 0x45, 0x4A, 0x4E, 0x52,
 479     0x57, 0x5B, 0x5F, 0x63, 0x67, 0x6B, 0x6F, 0x73,
 480     0x77, 0x7B, 0x7E, 0x82, 0x86, 0x8A, 0x8D, 0x91,
 481     0x95, 0x99, 0x9C, 0xA0, 0xA3, 0xA7, 0xAA, 0xAE,
 482     0xB2, 0xB5, 0xB9, 0xBC, 0xBF, 0xC3, 0xC6, 0xCA,
 483     0xCD, 0xD0, 0xD4, 0xD7, 0xDA, 0xDE, 0xE1, 0xE4,
 484     0xE8, 0xEB, 0xEE, 0xF1, 0xF5, 0xF8, 0xFB, 0xFD,
 485     0x07, 0x0E, 0x15, 0x1A, 0x20, 0x25, 0x2A, 0x2F,
 486     0x34, 0x39, 0x3D, 0x42, 0x46, 0x4B, 0x4F, 0x53,
 487     0x58, 0x5C, 0x60, 0x64, 0x68, 0x6C, 0x70, 0x74,
 488     0x78, 0x7C, 0x7F, 0x83, 0x87, 0x8B, 0x8E, 0x92,
 489     0x96, 0x99, 0x9D, 0xA1, 0xA4, 0xA8, 0xAB, 0xAF,
 490     0xB2, 0xB6, 0xB9, 0xBD, 0xC0, 0xC4, 0xC7, 0xCB,
 491     0xCE, 0xD1, 0xD5, 0xD8, 0xDB, 0xDF, 0xE2, 0xE5,
 492     0xE9, 0xEC, 0xEF, 0xF2, 0xF6, 0xF9, 0xFC, 0xFD
 493 };
 494 #endif
 495
 496 static int xan_decode_frame(AVCodecContext *avctx,
 497                             void *data, int *data_size,
 498                             AVPacket *avpkt)
 499 {
 500     const uint8_t *buf = avpkt->data;
 501     int ret, buf_size = avpkt->size;
 502     XanContext *s = avctx->priv_data;
 503
 504     if (avctx->codec->id == CODEC_ID_XAN_WC3) {
 505         const uint8_t *buf_end = buf + buf_size;
 506         int tag = 0;
 507         while (buf_end - buf > 8 && tag != VGA__TAG) {
 508             unsigned *tmpptr;
 509             uint32_t new_pal;
 510             int size;
 511             int i;
 512             tag  = bytestream_get_le32(&buf);
 513             size = bytestream_get_be32(&buf);
 514             size = FFMIN(size, buf_end - buf);
 515             switch (tag) {
 516             case PALT_TAG:
 517                 if (size < PALETTE_SIZE)
 518                     return AVERROR_INVALIDDATA;
 519                 if (s->palettes_count >= PALETTES_MAX)
 520                     return AVERROR_INVALIDDATA;
 521                 tmpptr = av_realloc(s->palettes, (s->palettes_count + 1) * AVPALETTE_SIZE);
 522                 if (!tmpptr)
 523                     return AVERROR(ENOMEM);
 524                 s->palettes = tmpptr;
 525                 tmpptr += s->palettes_count * AVPALETTE_COUNT;
 526                 for (i = 0; i < PALETTE_COUNT; i++) {
 527 #if RUNTIME_GAMMA
 528                     int r = gamma_corr(*buf++);
 529                     int g = gamma_corr(*buf++);
 530                     int b = gamma_corr(*buf++);
 531 #else
 532                     int r = gamma_lookup[*buf++];
 533                     int g = gamma_lookup[*buf++];
 534                     int b = gamma_lookup[*buf++];
 535 #endif
 536                     *tmpptr++ = (r << 16) | (g << 8) | b;
 537                 }
 538                 s->palettes_count++;
 539                 break;
 540             case SHOT_TAG:
 541                 if (size < 4)
 542                     return AVERROR_INVALIDDATA;
 543                 new_pal = bytestream_get_le32(&buf);
 544                 if (new_pal < s->palettes_count) {
 545                     s->cur_palette = new_pal;
 546                 } else
 547                     av_log(avctx, AV_LOG_ERROR, "Invalid palette selected\n");
 548                 break;
 549             case VGA__TAG:
 550                 break;
 551             default:
 552                 buf += size;
 553                 break;
 554             }
 555         }
 556         buf_size = buf_end - buf;
 557     }
 558     if (s->palettes_count <= 0) {
 559         av_log(s->avctx, AV_LOG_ERROR, "No palette found\n");
 560         return AVERROR_INVALIDDATA;
 561     }
 562
 563     if ((ret = avctx->get_buffer(avctx, &s->current_frame))) {
 564         av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
 565         return ret;
 566     }
 567     s->current_frame.reference = 3;
 568
 569     if (!s->frame_size)
 570         s->frame_size = s->current_frame.linesize[0] * s->avctx->height;
 571
 572     memcpy(s->current_frame.data[1], s->palettes + s->cur_palette * AVPALETTE_COUNT, AVPALETTE_SIZE);
 573
 574     s->buf = buf;
 575     s->size = buf_size;
 576
 577     if (xan_wc3_decode_frame(s) < 0)
 578         return AVERROR_INVALIDDATA;
 579
 580     /* release the last frame if it is allocated */
 581     if (s->last_frame.data[0])
 582         avctx->release_buffer(avctx, &s->last_frame);
 583
 584     *data_size = sizeof(AVFrame);
 585     *(AVFrame*)data = s->current_frame;
 586
 587     /* shuffle frames */
 588     FFSWAP(AVFrame, s->current_frame, s->last_frame);
 589
 590     /* always report that the buffer was completely consumed */
 591     return buf_size;
 592 }
 593
 594 static av_cold int xan_decode_end(AVCodecContext *avctx)
 595 {
 596     XanContext *s = avctx->priv_data;
 597
 598     /* release the frames */
 599     if (s->last_frame.data[0])
 600         avctx->release_buffer(avctx, &s->last_frame);
 601     if (s->current_frame.data[0])
 602         avctx->release_buffer(avctx, &s->current_frame);
 603
 604     av_freep(&s->buffer1);
 605     av_freep(&s->buffer2);
 606     av_freep(&s->palettes);
 607
 608     return 0;
 609 }
 610
 611 AVCodec ff_xan_wc3_decoder = {
 612     .name           = "xan_wc3",
 613     .type           = AVMEDIA_TYPE_VIDEO,
 614     .id             = CODEC_ID_XAN_WC3,
 615     .priv_data_size = sizeof(XanContext),
 616     .init           = xan_decode_init,
 617     .close          = xan_decode_end,
 618     .decode         = xan_decode_frame,
 619     .capabilities   = CODEC_CAP_DR1,
 620     .long_name = NULL_IF_CONFIG_SMALL("Wing Commander III / Xan"),
 621 };