]> git.sesse.net Git - ffmpeg/blob - libavcodec/vmdav.c
Merge commit '399663be9d4a839b894c48a21b62926eb8497d72'
[ffmpeg] / libavcodec / vmdav.c
1 /*
2  * Sierra VMD Audio & Video Decoders
3  * Copyright (C) 2004 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  * Sierra VMD audio & video decoders
25  * by Vladimir "VAG" Gneushev (vagsoft at mail.ru)
26  * for more information on the Sierra VMD format, visit:
27  *   http://www.pcisys.net/~melanson/codecs/
28  *
29  * The video decoder outputs PAL8 colorspace data. The decoder expects
30  * a 0x330-byte VMD file header to be transmitted via extradata during
31  * codec initialization. Each encoded frame that is sent to this decoder
32  * is expected to be prepended with the appropriate 16-byte frame
33  * information record from the VMD file.
34  *
35  * The audio decoder, like the video decoder, expects each encoded data
36  * chunk to be prepended with the appropriate 16-byte frame information
37  * record from the VMD file. It does not require the 0x330-byte VMD file
38  * header, but it does need the audio setup parameters passed in through
39  * normal libavcodec API means.
40  */
41
42 #include <stdio.h>
43 #include <stdlib.h>
44 #include <string.h>
45
46 #include "libavutil/channel_layout.h"
47 #include "libavutil/common.h"
48 #include "libavutil/intreadwrite.h"
49 #include "avcodec.h"
50 #include "internal.h"
51
52 #define VMD_HEADER_SIZE 0x330
53 #define PALETTE_COUNT 256
54
55 /*
56  * Video Decoder
57  */
58
59 typedef struct VmdVideoContext {
60
61     AVCodecContext *avctx;
62     AVFrame frame;
63     AVFrame prev_frame;
64
65     const unsigned char *buf;
66     int size;
67
68     unsigned char palette[PALETTE_COUNT * 4];
69     unsigned char *unpack_buffer;
70     int unpack_buffer_size;
71
72     int x_off, y_off;
73 } VmdVideoContext;
74
75 #define QUEUE_SIZE 0x1000
76 #define QUEUE_MASK 0x0FFF
77
78 static void lz_unpack(const unsigned char *src, int src_len,
79                       unsigned char *dest, int dest_len)
80 {
81     const unsigned char *s;
82     const unsigned char *s_end;
83     unsigned char *d;
84     unsigned char *d_end;
85     unsigned char queue[QUEUE_SIZE];
86     unsigned int qpos;
87     unsigned int dataleft;
88     unsigned int chainofs;
89     unsigned int chainlen;
90     unsigned int speclen;
91     unsigned char tag;
92     unsigned int i, j;
93
94     s = src;
95     s_end = src + src_len;
96     d = dest;
97     d_end = d + dest_len;
98
99     if (s_end - s < 8)
100         return;
101     dataleft = AV_RL32(s);
102     s += 4;
103     memset(queue, 0x20, QUEUE_SIZE);
104     if (AV_RL32(s) == 0x56781234) {
105         s += 4;
106         qpos = 0x111;
107         speclen = 0xF + 3;
108     } else {
109         qpos = 0xFEE;
110         speclen = 100;  /* no speclen */
111     }
112
113     while (s_end - s > 0 && dataleft > 0) {
114         tag = *s++;
115         if ((tag == 0xFF) && (dataleft > 8)) {
116             if (d_end - d < 8 || s_end - s < 8)
117                 return;
118             for (i = 0; i < 8; i++) {
119                 queue[qpos++] = *d++ = *s++;
120                 qpos &= QUEUE_MASK;
121             }
122             dataleft -= 8;
123         } else {
124             for (i = 0; i < 8; i++) {
125                 if (dataleft == 0)
126                     break;
127                 if (tag & 0x01) {
128                     if (d_end - d < 1 || s_end - s < 1)
129                         return;
130                     queue[qpos++] = *d++ = *s++;
131                     qpos &= QUEUE_MASK;
132                     dataleft--;
133                 } else {
134                     if (s_end - s < 2)
135                         return;
136                     chainofs = *s++;
137                     chainofs |= ((*s & 0xF0) << 4);
138                     chainlen = (*s++ & 0x0F) + 3;
139                     if (chainlen == speclen) {
140                         if (s_end - s < 1)
141                             return;
142                         chainlen = *s++ + 0xF + 3;
143                     }
144                     if (d_end - d < chainlen)
145                         return;
146                     for (j = 0; j < chainlen; j++) {
147                         *d = queue[chainofs++ & QUEUE_MASK];
148                         queue[qpos++] = *d++;
149                         qpos &= QUEUE_MASK;
150                     }
151                     dataleft -= chainlen;
152                 }
153                 tag >>= 1;
154             }
155         }
156     }
157 }
158
159 static int rle_unpack(const unsigned char *src, int src_len, int src_count,
160                       unsigned char *dest, int dest_len)
161 {
162     const unsigned char *ps;
163     const unsigned char *ps_end;
164     unsigned char *pd;
165     int i, l;
166     unsigned char *dest_end = dest + dest_len;
167
168     ps = src;
169     ps_end = src + src_len;
170     pd = dest;
171     if (src_count & 1) {
172         if (ps_end - ps < 1)
173             return 0;
174         *pd++ = *ps++;
175     }
176
177     src_count >>= 1;
178     i = 0;
179     do {
180         if (ps_end - ps < 1)
181             break;
182         l = *ps++;
183         if (l & 0x80) {
184             l = (l & 0x7F) * 2;
185             if (dest_end - pd < l || ps_end - ps < l)
186                 return ps - src;
187             memcpy(pd, ps, l);
188             ps += l;
189             pd += l;
190         } else {
191             if (dest_end - pd < i || ps_end - ps < 2)
192                 return ps - src;
193             for (i = 0; i < l; i++) {
194                 *pd++ = ps[0];
195                 *pd++ = ps[1];
196             }
197             ps += 2;
198         }
199         i += l;
200     } while (i < src_count);
201
202     return ps - src;
203 }
204
205 static void vmd_decode(VmdVideoContext *s)
206 {
207     int i;
208     unsigned int *palette32;
209     unsigned char r, g, b;
210
211     /* point to the start of the encoded data */
212     const unsigned char *p = s->buf + 16;
213     const unsigned char *p_end = s->buf + s->size;
214
215     const unsigned char *pb;
216     const unsigned char *pb_end;
217     unsigned char meth;
218     unsigned char *dp;   /* pointer to current frame */
219     unsigned char *pp;   /* pointer to previous frame */
220     unsigned char len;
221     int ofs;
222
223     int frame_x, frame_y;
224     int frame_width, frame_height;
225
226     frame_x = AV_RL16(&s->buf[6]);
227     frame_y = AV_RL16(&s->buf[8]);
228     frame_width = AV_RL16(&s->buf[10]) - frame_x + 1;
229     frame_height = AV_RL16(&s->buf[12]) - frame_y + 1;
230     if (frame_x < 0 || frame_width < 0 ||
231         frame_x >= s->avctx->width ||
232         frame_width > s->avctx->width ||
233         frame_x + frame_width > s->avctx->width)
234         return;
235     if (frame_y < 0 || frame_height < 0 ||
236         frame_y >= s->avctx->height ||
237         frame_height > s->avctx->height ||
238         frame_y + frame_height > s->avctx->height)
239         return;
240
241     if ((frame_width == s->avctx->width && frame_height == s->avctx->height) &&
242         (frame_x || frame_y)) {
243
244         s->x_off = frame_x;
245         s->y_off = frame_y;
246     }
247     frame_x -= s->x_off;
248     frame_y -= s->y_off;
249
250     /* if only a certain region will be updated, copy the entire previous
251      * frame before the decode */
252     if (s->prev_frame.data[0] &&
253         (frame_x || frame_y || (frame_width != s->avctx->width) ||
254         (frame_height != s->avctx->height))) {
255
256         memcpy(s->frame.data[0], s->prev_frame.data[0],
257             s->avctx->height * s->frame.linesize[0]);
258     }
259
260     /* check if there is a new palette */
261     if (s->buf[15] & 0x02) {
262         if (p_end - p < 2 + 3 * PALETTE_COUNT)
263             return;
264         p += 2;
265         palette32 = (unsigned int *)s->palette;
266         for (i = 0; i < PALETTE_COUNT; i++) {
267             r = *p++ * 4;
268             g = *p++ * 4;
269             b = *p++ * 4;
270             palette32[i] = 0xFFU << 24 | r << 16 | g << 8 | b;
271             palette32[i] |= palette32[i] >> 6 & 0x30303;
272         }
273     }
274     if (p < p_end) {
275         /* originally UnpackFrame in VAG's code */
276         pb = p;
277         pb_end = p_end;
278         meth = *pb++;
279         if (meth & 0x80) {
280             lz_unpack(pb, p_end - pb, s->unpack_buffer, s->unpack_buffer_size);
281             meth &= 0x7F;
282             pb = s->unpack_buffer;
283             pb_end = s->unpack_buffer + s->unpack_buffer_size;
284         }
285
286         dp = &s->frame.data[0][frame_y * s->frame.linesize[0] + frame_x];
287         pp = &s->prev_frame.data[0][frame_y * s->prev_frame.linesize[0] + frame_x];
288         switch (meth) {
289         case 1:
290             for (i = 0; i < frame_height; i++) {
291                 ofs = 0;
292                 do {
293                     if (pb_end - pb < 1)
294                         return;
295                     len = *pb++;
296                     if (len & 0x80) {
297                         len = (len & 0x7F) + 1;
298                         if (ofs + len > frame_width || pb_end - pb < len)
299                             return;
300                         memcpy(&dp[ofs], pb, len);
301                         pb += len;
302                         ofs += len;
303                     } else {
304                         /* interframe pixel copy */
305                         if (ofs + len + 1 > frame_width || !s->prev_frame.data[0])
306                             return;
307                         memcpy(&dp[ofs], &pp[ofs], len + 1);
308                         ofs += len + 1;
309                     }
310                 } while (ofs < frame_width);
311                 if (ofs > frame_width) {
312                     av_log(s->avctx, AV_LOG_ERROR, "offset > width (%d > %d)\n",
313                         ofs, frame_width);
314                     break;
315                 }
316                 dp += s->frame.linesize[0];
317                 pp += s->prev_frame.linesize[0];
318             }
319             break;
320
321         case 2:
322             for (i = 0; i < frame_height; i++) {
323                 if (pb_end -pb < frame_width)
324                     return;
325                 memcpy(dp, pb, frame_width);
326                 pb += frame_width;
327                 dp += s->frame.linesize[0];
328                 pp += s->prev_frame.linesize[0];
329             }
330             break;
331
332         case 3:
333             for (i = 0; i < frame_height; i++) {
334                 ofs = 0;
335                 do {
336                     if (pb_end - pb < 1)
337                         return;
338                     len = *pb++;
339                     if (len & 0x80) {
340                         len = (len & 0x7F) + 1;
341                         if (pb_end - pb < 1)
342                             return;
343                         if (*pb++ == 0xFF)
344                             len = rle_unpack(pb, pb_end - pb, len, &dp[ofs], frame_width - ofs);
345                         else {
346                         if (pb_end - pb < len)
347                             return;
348                             memcpy(&dp[ofs], pb, len);
349                         }
350                         pb += len;
351                         ofs += len;
352                     } else {
353                         /* interframe pixel copy */
354                         if (ofs + len + 1 > frame_width || !s->prev_frame.data[0])
355                             return;
356                         memcpy(&dp[ofs], &pp[ofs], len + 1);
357                         ofs += len + 1;
358                     }
359                 } while (ofs < frame_width);
360                 if (ofs > frame_width) {
361                     av_log(s->avctx, AV_LOG_ERROR, "offset > width (%d > %d)\n",
362                         ofs, frame_width);
363                 }
364                 dp += s->frame.linesize[0];
365                 pp += s->prev_frame.linesize[0];
366             }
367             break;
368         }
369     }
370 }
371
372 static av_cold int vmdvideo_decode_init(AVCodecContext *avctx)
373 {
374     VmdVideoContext *s = avctx->priv_data;
375     int i;
376     unsigned int *palette32;
377     int palette_index = 0;
378     unsigned char r, g, b;
379     unsigned char *vmd_header;
380     unsigned char *raw_palette;
381
382     s->avctx = avctx;
383     avctx->pix_fmt = AV_PIX_FMT_PAL8;
384
385     /* make sure the VMD header made it */
386     if (s->avctx->extradata_size != VMD_HEADER_SIZE) {
387         av_log(s->avctx, AV_LOG_ERROR, "expected extradata size of %d\n",
388             VMD_HEADER_SIZE);
389         return -1;
390     }
391     vmd_header = (unsigned char *)avctx->extradata;
392
393     s->unpack_buffer_size = AV_RL32(&vmd_header[800]);
394     s->unpack_buffer = av_malloc(s->unpack_buffer_size);
395     if (!s->unpack_buffer)
396         return -1;
397
398     /* load up the initial palette */
399     raw_palette = &vmd_header[28];
400     palette32 = (unsigned int *)s->palette;
401     for (i = 0; i < PALETTE_COUNT; i++) {
402         r = raw_palette[palette_index++] * 4;
403         g = raw_palette[palette_index++] * 4;
404         b = raw_palette[palette_index++] * 4;
405         palette32[i] = (r << 16) | (g << 8) | (b);
406     }
407
408     avcodec_get_frame_defaults(&s->frame);
409     avcodec_get_frame_defaults(&s->prev_frame);
410
411     return 0;
412 }
413
414 static int vmdvideo_decode_frame(AVCodecContext *avctx,
415                                  void *data, int *got_frame,
416                                  AVPacket *avpkt)
417 {
418     const uint8_t *buf = avpkt->data;
419     int buf_size = avpkt->size;
420     VmdVideoContext *s = avctx->priv_data;
421
422     s->buf = buf;
423     s->size = buf_size;
424
425     if (buf_size < 16)
426         return buf_size;
427
428     s->frame.reference = 3;
429     if (ff_get_buffer(avctx, &s->frame)) {
430         av_log(s->avctx, AV_LOG_ERROR, "get_buffer() failed\n");
431         return -1;
432     }
433
434     vmd_decode(s);
435
436     /* make the palette available on the way out */
437     memcpy(s->frame.data[1], s->palette, PALETTE_COUNT * 4);
438
439     /* shuffle frames */
440     FFSWAP(AVFrame, s->frame, s->prev_frame);
441     if (s->frame.data[0])
442         avctx->release_buffer(avctx, &s->frame);
443
444     *got_frame      = 1;
445     *(AVFrame*)data = s->prev_frame;
446
447     /* report that the buffer was completely consumed */
448     return buf_size;
449 }
450
451 static av_cold int vmdvideo_decode_end(AVCodecContext *avctx)
452 {
453     VmdVideoContext *s = avctx->priv_data;
454
455     if (s->prev_frame.data[0])
456         avctx->release_buffer(avctx, &s->prev_frame);
457     av_free(s->unpack_buffer);
458
459     return 0;
460 }
461
462
463 /*
464  * Audio Decoder
465  */
466
467 #define BLOCK_TYPE_AUDIO    1
468 #define BLOCK_TYPE_INITIAL  2
469 #define BLOCK_TYPE_SILENCE  3
470
471 typedef struct VmdAudioContext {
472     int out_bps;
473     int chunk_size;
474 } VmdAudioContext;
475
476 static const uint16_t vmdaudio_table[128] = {
477     0x000, 0x008, 0x010, 0x020, 0x030, 0x040, 0x050, 0x060, 0x070, 0x080,
478     0x090, 0x0A0, 0x0B0, 0x0C0, 0x0D0, 0x0E0, 0x0F0, 0x100, 0x110, 0x120,
479     0x130, 0x140, 0x150, 0x160, 0x170, 0x180, 0x190, 0x1A0, 0x1B0, 0x1C0,
480     0x1D0, 0x1E0, 0x1F0, 0x200, 0x208, 0x210, 0x218, 0x220, 0x228, 0x230,
481     0x238, 0x240, 0x248, 0x250, 0x258, 0x260, 0x268, 0x270, 0x278, 0x280,
482     0x288, 0x290, 0x298, 0x2A0, 0x2A8, 0x2B0, 0x2B8, 0x2C0, 0x2C8, 0x2D0,
483     0x2D8, 0x2E0, 0x2E8, 0x2F0, 0x2F8, 0x300, 0x308, 0x310, 0x318, 0x320,
484     0x328, 0x330, 0x338, 0x340, 0x348, 0x350, 0x358, 0x360, 0x368, 0x370,
485     0x378, 0x380, 0x388, 0x390, 0x398, 0x3A0, 0x3A8, 0x3B0, 0x3B8, 0x3C0,
486     0x3C8, 0x3D0, 0x3D8, 0x3E0, 0x3E8, 0x3F0, 0x3F8, 0x400, 0x440, 0x480,
487     0x4C0, 0x500, 0x540, 0x580, 0x5C0, 0x600, 0x640, 0x680, 0x6C0, 0x700,
488     0x740, 0x780, 0x7C0, 0x800, 0x900, 0xA00, 0xB00, 0xC00, 0xD00, 0xE00,
489     0xF00, 0x1000, 0x1400, 0x1800, 0x1C00, 0x2000, 0x3000, 0x4000
490 };
491
492 static av_cold int vmdaudio_decode_init(AVCodecContext *avctx)
493 {
494     VmdAudioContext *s = avctx->priv_data;
495
496     if (avctx->channels < 1 || avctx->channels > 2) {
497         av_log(avctx, AV_LOG_ERROR, "invalid number of channels\n");
498         return AVERROR(EINVAL);
499     }
500     if (avctx->block_align < 1 || avctx->block_align % avctx->channels) {
501         av_log(avctx, AV_LOG_ERROR, "invalid block align\n");
502         return AVERROR(EINVAL);
503     }
504
505     avctx->channel_layout = avctx->channels == 1 ? AV_CH_LAYOUT_MONO :
506                                                    AV_CH_LAYOUT_STEREO;
507
508     if (avctx->bits_per_coded_sample == 16)
509         avctx->sample_fmt = AV_SAMPLE_FMT_S16;
510     else
511         avctx->sample_fmt = AV_SAMPLE_FMT_U8;
512     s->out_bps = av_get_bytes_per_sample(avctx->sample_fmt);
513
514     s->chunk_size = avctx->block_align + avctx->channels * (s->out_bps == 2);
515
516     av_log(avctx, AV_LOG_DEBUG, "%d channels, %d bits/sample, "
517            "block align = %d, sample rate = %d\n",
518            avctx->channels, avctx->bits_per_coded_sample, avctx->block_align,
519            avctx->sample_rate);
520
521     return 0;
522 }
523
524 static void decode_audio_s16(int16_t *out, const uint8_t *buf, int buf_size,
525                              int channels)
526 {
527     int ch;
528     const uint8_t *buf_end = buf + buf_size;
529     int predictor[2];
530     int st = channels - 1;
531
532     /* decode initial raw sample */
533     for (ch = 0; ch < channels; ch++) {
534         predictor[ch] = (int16_t)AV_RL16(buf);
535         buf += 2;
536         *out++ = predictor[ch];
537     }
538
539     /* decode DPCM samples */
540     ch = 0;
541     while (buf < buf_end) {
542         uint8_t b = *buf++;
543         if (b & 0x80)
544             predictor[ch] -= vmdaudio_table[b & 0x7F];
545         else
546             predictor[ch] += vmdaudio_table[b];
547         predictor[ch] = av_clip_int16(predictor[ch]);
548         *out++ = predictor[ch];
549         ch ^= st;
550     }
551 }
552
553 static int vmdaudio_decode_frame(AVCodecContext *avctx, void *data,
554                                  int *got_frame_ptr, AVPacket *avpkt)
555 {
556     AVFrame *frame     = data;
557     const uint8_t *buf = avpkt->data;
558     const uint8_t *buf_end;
559     int buf_size = avpkt->size;
560     VmdAudioContext *s = avctx->priv_data;
561     int block_type, silent_chunks, audio_chunks;
562     int ret;
563     uint8_t *output_samples_u8;
564     int16_t *output_samples_s16;
565
566     if (buf_size < 16) {
567         av_log(avctx, AV_LOG_WARNING, "skipping small junk packet\n");
568         *got_frame_ptr = 0;
569         return buf_size;
570     }
571
572     block_type = buf[6];
573     if (block_type < BLOCK_TYPE_AUDIO || block_type > BLOCK_TYPE_SILENCE) {
574         av_log(avctx, AV_LOG_ERROR, "unknown block type: %d\n", block_type);
575         return AVERROR(EINVAL);
576     }
577     buf      += 16;
578     buf_size -= 16;
579
580     /* get number of silent chunks */
581     silent_chunks = 0;
582     if (block_type == BLOCK_TYPE_INITIAL) {
583         uint32_t flags;
584         if (buf_size < 4) {
585             av_log(avctx, AV_LOG_ERROR, "packet is too small\n");
586             return AVERROR(EINVAL);
587         }
588         flags         = AV_RB32(buf);
589         silent_chunks = av_popcount(flags);
590         buf      += 4;
591         buf_size -= 4;
592     } else if (block_type == BLOCK_TYPE_SILENCE) {
593         silent_chunks = 1;
594         buf_size = 0; // should already be zero but set it just to be sure
595     }
596
597     /* ensure output buffer is large enough */
598     audio_chunks = buf_size / s->chunk_size;
599
600     /* get output buffer */
601     frame->nb_samples = ((silent_chunks + audio_chunks) * avctx->block_align) /
602                         avctx->channels;
603     if ((ret = ff_get_buffer(avctx, frame)) < 0) {
604         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
605         return ret;
606     }
607     output_samples_u8  =            frame->data[0];
608     output_samples_s16 = (int16_t *)frame->data[0];
609
610     /* decode silent chunks */
611     if (silent_chunks > 0) {
612         int silent_size = avctx->block_align * silent_chunks;
613         if (s->out_bps == 2) {
614             memset(output_samples_s16, 0x00, silent_size * 2);
615             output_samples_s16 += silent_size;
616         } else {
617             memset(output_samples_u8,  0x80, silent_size);
618             output_samples_u8 += silent_size;
619         }
620     }
621
622     /* decode audio chunks */
623     if (audio_chunks > 0) {
624         buf_end = buf + buf_size;
625         while ( buf_end - buf >= s->chunk_size) {
626             if (s->out_bps == 2) {
627                 decode_audio_s16(output_samples_s16, buf, s->chunk_size,
628                                  avctx->channels);
629                 output_samples_s16 += avctx->block_align;
630             } else {
631                 memcpy(output_samples_u8, buf, s->chunk_size);
632                 output_samples_u8  += avctx->block_align;
633             }
634             buf += s->chunk_size;
635         }
636     }
637
638     *got_frame_ptr = 1;
639
640     return avpkt->size;
641 }
642
643
644 /*
645  * Public Data Structures
646  */
647
648 AVCodec ff_vmdvideo_decoder = {
649     .name           = "vmdvideo",
650     .type           = AVMEDIA_TYPE_VIDEO,
651     .id             = AV_CODEC_ID_VMDVIDEO,
652     .priv_data_size = sizeof(VmdVideoContext),
653     .init           = vmdvideo_decode_init,
654     .close          = vmdvideo_decode_end,
655     .decode         = vmdvideo_decode_frame,
656     .capabilities   = CODEC_CAP_DR1,
657     .long_name      = NULL_IF_CONFIG_SMALL("Sierra VMD video"),
658 };
659
660 AVCodec ff_vmdaudio_decoder = {
661     .name           = "vmdaudio",
662     .type           = AVMEDIA_TYPE_AUDIO,
663     .id             = AV_CODEC_ID_VMDAUDIO,
664     .priv_data_size = sizeof(VmdAudioContext),
665     .init           = vmdaudio_decode_init,
666     .decode         = vmdaudio_decode_frame,
667     .capabilities   = CODEC_CAP_DR1,
668     .long_name      = NULL_IF_CONFIG_SMALL("Sierra VMD audio"),
669 };