utvideoenc: use ff_generate_len()
[ffmpeg.git] / libavcodec / utvideoenc.c
1 /*
2  * Ut Video encoder
3  * Copyright (c) 2012 Jan Ekström
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  * Ut Video encoder
25  */
26
27 #include "libavutil/intreadwrite.h"
28 #include "avcodec.h"
29 #include "internal.h"
30 #include "bytestream.h"
31 #include "put_bits.h"
32 #include "dsputil.h"
33 #include "mathops.h"
34 #include "utvideo.h"
35 #include "huffman.h"
36
37 /* Compare huffentry symbols */
38 static int huff_cmp_sym(const void *a, const void *b)
39 {
40     const HuffEntry *aa = a, *bb = b;
41     return aa->sym - bb->sym;
42 }
43
44 static av_cold int utvideo_encode_close(AVCodecContext *avctx)
45 {
46     UtvideoContext *c = avctx->priv_data;
47
48     av_freep(&avctx->coded_frame);
49     av_freep(&c->slice_bits);
50     av_freep(&c->slice_buffer);
51
52     return 0;
53 }
54
55 static av_cold int utvideo_encode_init(AVCodecContext *avctx)
56 {
57     UtvideoContext *c = avctx->priv_data;
58
59     uint32_t original_format;
60
61     c->avctx           = avctx;
62     c->frame_info_size = 4;
63
64     switch (avctx->pix_fmt) {
65     case PIX_FMT_RGB24:
66         c->planes        = 3;
67         avctx->codec_tag = MKTAG('U', 'L', 'R', 'G');
68         original_format  = UTVIDEO_RGB;
69         break;
70     case PIX_FMT_RGBA:
71         c->planes        = 4;
72         avctx->codec_tag = MKTAG('U', 'L', 'R', 'A');
73         original_format  = UTVIDEO_RGBA;
74         break;
75     case PIX_FMT_YUV420P:
76         if (avctx->width & 1 || avctx->height & 1) {
77             av_log(avctx, AV_LOG_ERROR,
78                    "4:2:0 video requires even width and height.\n");
79             return AVERROR_INVALIDDATA;
80         }
81         c->planes        = 3;
82         avctx->codec_tag = MKTAG('U', 'L', 'Y', '0');
83         original_format  = UTVIDEO_420;
84         break;
85     case PIX_FMT_YUV422P:
86         if (avctx->width & 1) {
87             av_log(avctx, AV_LOG_ERROR,
88                    "4:2:2 video requires even width.\n");
89             return AVERROR_INVALIDDATA;
90         }
91         c->planes        = 3;
92         avctx->codec_tag = MKTAG('U', 'L', 'Y', '2');
93         original_format  = UTVIDEO_422;
94         break;
95     default:
96         av_log(avctx, AV_LOG_ERROR, "Unknown pixel format: %d\n",
97                avctx->pix_fmt);
98         return AVERROR_INVALIDDATA;
99     }
100
101     ff_dsputil_init(&c->dsp, avctx);
102
103     /* Check the prediction method, and error out if unsupported */
104     if (avctx->prediction_method < 0 || avctx->prediction_method > 4) {
105         av_log(avctx, AV_LOG_WARNING,
106                "Prediction method %d is not supported in Ut Video.\n",
107                avctx->prediction_method);
108         return AVERROR_OPTION_NOT_FOUND;
109     }
110
111     if (avctx->prediction_method == FF_PRED_PLANE) {
112         av_log(avctx, AV_LOG_ERROR,
113                "Plane prediction is not supported in Ut Video.\n");
114         return AVERROR_OPTION_NOT_FOUND;
115     }
116
117     /* Convert from libavcodec prediction type to Ut Video's */
118     c->frame_pred = ff_ut_pred_order[avctx->prediction_method];
119
120     if (c->frame_pred == PRED_GRADIENT) {
121         av_log(avctx, AV_LOG_ERROR, "Gradient prediction is not supported.\n");
122         return AVERROR_OPTION_NOT_FOUND;
123     }
124
125     avctx->coded_frame = avcodec_alloc_frame();
126
127     if (!avctx->coded_frame) {
128         av_log(avctx, AV_LOG_ERROR, "Could not allocate frame.\n");
129         utvideo_encode_close(avctx);
130         return AVERROR(ENOMEM);
131     }
132
133     /* extradata size is 4 * 32bit */
134     avctx->extradata_size = 16;
135
136     avctx->extradata = av_mallocz(avctx->extradata_size +
137                                   FF_INPUT_BUFFER_PADDING_SIZE);
138
139     if (!avctx->extradata) {
140         av_log(avctx, AV_LOG_ERROR, "Could not allocate extradata.\n");
141         utvideo_encode_close(avctx);
142         return AVERROR(ENOMEM);
143     }
144
145     c->slice_buffer = av_malloc(avctx->width * avctx->height +
146                                 FF_INPUT_BUFFER_PADDING_SIZE);
147
148     if (!c->slice_buffer) {
149         av_log(avctx, AV_LOG_ERROR, "Cannot allocate temporary buffer 1.\n");
150         utvideo_encode_close(avctx);
151         return AVERROR(ENOMEM);
152     }
153
154     /*
155      * Set the version of the encoder.
156      * Last byte is "implementation ID", which is
157      * obtained from the creator of the format.
158      * Libavcodec has been assigned with the ID 0xF0.
159      */
160     AV_WB32(avctx->extradata, MKTAG(1, 0, 0, 0xF0));
161
162     /*
163      * Set the "original format"
164      * Not used for anything during decoding.
165      */
166     AV_WL32(avctx->extradata + 4, original_format);
167
168     /* Write 4 as the 'frame info size' */
169     AV_WL32(avctx->extradata + 8, c->frame_info_size);
170
171     /*
172      * Set how many slices are going to be used.
173      * Set one slice for now.
174      */
175     c->slices = 1;
176
177     /* Set compression mode */
178     c->compression = COMP_HUFF;
179
180     /*
181      * Set the encoding flags:
182      * - Slice count minus 1
183      * - Interlaced encoding mode flag, set to zero for now.
184      * - Compression mode (none/huff)
185      * And write the flags.
186      */
187     c->flags  = (c->slices - 1) << 24;
188     c->flags |= 0 << 11; // bit field to signal interlaced encoding mode
189     c->flags |= c->compression;
190
191     AV_WL32(avctx->extradata + 12, c->flags);
192
193     return 0;
194 }
195
196 static void mangle_rgb_planes(uint8_t *src, int step, int stride, int width,
197                               int height)
198 {
199     int i, j;
200     unsigned g;
201
202     for (j = 0; j < height; j++) {
203         for (i = 0; i < width * step; i += step) {
204             g           = src[i + 1] + 0x80;
205             src[i]     -= g;
206             src[i + 2] -= g;
207         }
208         src += stride;
209     }
210 }
211
212 /* Write data to a plane, no prediction applied */
213 static void write_plane(uint8_t *src, uint8_t *dst, int step, int stride,
214                         int width, int height)
215 {
216     int i, j;
217
218     for (j = 0; j < height; j++) {
219         for (i = 0; i < width * step; i += step)
220             *dst++ = src[i];
221
222         src += stride;
223     }
224 }
225
226 /* Write data to a plane with left prediction */
227 static void left_predict(uint8_t *src, uint8_t *dst, int step, int stride,
228                          int width, int height)
229 {
230     int i, j;
231     uint8_t prev;
232
233     prev = 0x80; /* Set the initial value */
234     for (j = 0; j < height; j++) {
235         for (i = 0; i < width * step; i += step) {
236             *dst++ = src[i] - prev;
237             prev   = src[i];
238         }
239         src += stride;
240     }
241 }
242
243 /* Write data to a plane with median prediction */
244 static void median_predict(uint8_t *src, uint8_t *dst, int step, int stride,
245                            int width, int height)
246 {
247     int i, j;
248     int A, B, C;
249     uint8_t prev;
250
251     /* First line uses left neighbour prediction */
252     prev = 0x80; /* Set the initial value */
253     for (i = 0; i < width * step; i += step) {
254         *dst++ = src[i] - prev;
255         prev   = src[i];
256     }
257
258     if (height == 1)
259         return;
260
261     src += stride;
262
263     /*
264      * Second line uses top prediction for the first sample,
265      * and median for the rest.
266      */
267     C      = src[-stride];
268     *dst++ = src[0] - C;
269     A      = src[0];
270     for (i = step; i < width * step; i += step) {
271         B       = src[i - stride];
272         *dst++  = src[i] - mid_pred(A, B, (A + B - C) & 0xFF);
273         C       = B;
274         A       = src[i];
275     }
276
277     src += stride;
278
279     /* Rest of the coded part uses median prediction */
280     for (j = 2; j < height; j++) {
281         for (i = 0; i < width * step; i += step) {
282             B       = src[i - stride];
283             *dst++  = src[i] - mid_pred(A, B, (A + B - C) & 0xFF);
284             C       = B;
285             A       = src[i];
286         }
287         src += stride;
288     }
289 }
290
291 /* Count the usage of values in a plane */
292 static void count_usage(uint8_t *src, int width,
293                         int height, uint64_t *counts)
294 {
295     int i, j;
296
297     for (j = 0; j < height; j++) {
298         for (i = 0; i < width; i++) {
299             counts[src[i]]++;
300         }
301         src += width;
302     }
303 }
304
305 /* Calculate the actual huffman codes from the code lengths */
306 static void calculate_codes(HuffEntry *he)
307 {
308     int last, i;
309     uint32_t code;
310
311     qsort(he, 256, sizeof(*he), ff_ut_huff_cmp_len);
312
313     last = 255;
314     while (he[last].len == 255 && last)
315         last--;
316
317     code = 1;
318     for (i = last; i >= 0; i--) {
319         he[i].code  = code >> (32 - he[i].len);
320         code       += 0x80000000u >> (he[i].len - 1);
321     }
322
323     qsort(he, 256, sizeof(*he), huff_cmp_sym);
324 }
325
326 /* Write huffman bit codes to a memory block */
327 static int write_huff_codes(uint8_t *src, uint8_t *dst, int dst_size,
328                             int width, int height, HuffEntry *he)
329 {
330     PutBitContext pb;
331     int i, j;
332     int count;
333
334     init_put_bits(&pb, dst, dst_size);
335
336     /* Write the codes */
337     for (j = 0; j < height; j++) {
338         for (i = 0; i < width; i++)
339             put_bits(&pb, he[src[i]].len, he[src[i]].code);
340
341         src += width;
342     }
343
344     /* Pad output to a 32bit boundary */
345     count = put_bits_count(&pb) & 0x1F;
346
347     if (count)
348         put_bits(&pb, 32 - count, 0);
349
350     /* Get the amount of bits written */
351     count = put_bits_count(&pb);
352
353     /* Flush the rest with zeroes */
354     flush_put_bits(&pb);
355
356     return count;
357 }
358
359 static int encode_plane(AVCodecContext *avctx, uint8_t *src,
360                         uint8_t *dst, int step, int stride,
361                         int width, int height, PutByteContext *pb)
362 {
363     UtvideoContext *c        = avctx->priv_data;
364     uint8_t  lengths[256];
365     uint64_t counts[256]     = { 0 };
366
367     HuffEntry he[256];
368
369     uint32_t offset = 0, slice_len = 0;
370     int      i, sstart, send = 0;
371     int      symbol;
372
373     /* Do prediction / make planes */
374     switch (c->frame_pred) {
375     case PRED_NONE:
376         for (i = 0; i < c->slices; i++) {
377             sstart = send;
378             send   = height * (i + 1) / c->slices;
379             write_plane(src + sstart * stride, dst + sstart * width,
380                         step, stride, width, send - sstart);
381         }
382         break;
383     case PRED_LEFT:
384         for (i = 0; i < c->slices; i++) {
385             sstart = send;
386             send   = height * (i + 1) / c->slices;
387             left_predict(src + sstart * stride, dst + sstart * width,
388                          step, stride, width, send - sstart);
389         }
390         break;
391     case PRED_MEDIAN:
392         for (i = 0; i < c->slices; i++) {
393             sstart = send;
394             send   = height * (i + 1) / c->slices;
395             median_predict(src + sstart * stride, dst + sstart * width,
396                            step, stride, width, send - sstart);
397         }
398         break;
399     default:
400         av_log(avctx, AV_LOG_ERROR, "Unknown prediction mode: %d\n",
401                c->frame_pred);
402         return AVERROR_OPTION_NOT_FOUND;
403     }
404
405     /* Count the usage of values */
406     count_usage(dst, width, height, counts);
407
408     /* Check for a special case where only one symbol was used */
409     for (symbol = 0; symbol < 256; symbol++) {
410         /* If non-zero count is found, see if it matches width * height */
411         if (counts[symbol]) {
412             /* Special case if only one symbol was used */
413             if (counts[symbol] == width * height) {
414                 /*
415                  * Write a zero for the single symbol
416                  * used in the plane, else 0xFF.
417                  */
418                 for (i = 0; i < 256; i++) {
419                     if (i == symbol)
420                         bytestream2_put_byte(pb, 0);
421                     else
422                         bytestream2_put_byte(pb, 0xFF);
423                 }
424
425                 /* Write zeroes for lengths */
426                 for (i = 0; i < c->slices; i++)
427                     bytestream2_put_le32(pb, 0);
428
429                 /* And that's all for that plane folks */
430                 return 0;
431             }
432             break;
433         }
434     }
435
436     /* Calculate huffman lengths */
437     ff_generate_len_table(lengths, counts);
438
439     /*
440      * Write the plane's header into the output packet:
441      * - huffman code lengths (256 bytes)
442      * - slice end offsets (gotten from the slice lengths)
443      */
444     for (i = 0; i < 256; i++) {
445         bytestream2_put_byte(pb, lengths[i]);
446
447         he[i].len = lengths[i];
448         he[i].sym = i;
449     }
450
451     /* Calculate the huffman codes themselves */
452     calculate_codes(he);
453
454     send = 0;
455     for (i = 0; i < c->slices; i++) {
456         sstart  = send;
457         send    = height * (i + 1) / c->slices;
458
459         /*
460          * Write the huffman codes to a buffer,
461          * get the offset in bits and convert to bytes.
462          */
463         offset += write_huff_codes(dst + sstart * width, c->slice_bits,
464                                    width * (send - sstart), width,
465                                    send - sstart, he) >> 3;
466
467         slice_len = offset - slice_len;
468
469         /* Byteswap the written huffman codes */
470         c->dsp.bswap_buf((uint32_t *) c->slice_bits,
471                          (uint32_t *) c->slice_bits,
472                          slice_len >> 2);
473
474         /* Write the offset to the stream */
475         bytestream2_put_le32(pb, offset);
476
477         /* Seek to the data part of the packet */
478         bytestream2_seek_p(pb, 4 * (c->slices - i - 1) +
479                            offset - slice_len, SEEK_CUR);
480
481         /* Write the slices' data into the output packet */
482         bytestream2_put_buffer(pb, c->slice_bits, slice_len);
483
484         /* Seek back to the slice offsets */
485         bytestream2_seek_p(pb, -4 * (c->slices - i - 1) - offset,
486                            SEEK_CUR);
487
488         slice_len = offset;
489     }
490
491     /* And at the end seek to the end of written slice(s) */
492     bytestream2_seek_p(pb, offset, SEEK_CUR);
493
494     return 0;
495 }
496
497 static int utvideo_encode_frame(AVCodecContext *avctx, AVPacket *pkt,
498                                 const AVFrame *pic, int *got_packet)
499 {
500     UtvideoContext *c = avctx->priv_data;
501     PutByteContext pb;
502
503     uint32_t frame_info;
504
505     uint8_t *dst;
506
507     int width = avctx->width, height = avctx->height;
508     int i, ret = 0;
509
510     /* Allocate a new packet if needed, and set it to the pointer dst */
511     ret = ff_alloc_packet2(avctx, pkt, (256 + 4 * c->slices + width * height) *
512                            c->planes + 4);
513
514     if (ret < 0)
515         return ret;
516
517     dst = pkt->data;
518
519     bytestream2_init_writer(&pb, dst, pkt->size);
520
521     av_fast_malloc(&c->slice_bits, &c->slice_bits_size,
522                    width * height + FF_INPUT_BUFFER_PADDING_SIZE);
523
524     if (!c->slice_bits) {
525         av_log(avctx, AV_LOG_ERROR, "Cannot allocate temporary buffer 2.\n");
526         return AVERROR(ENOMEM);
527     }
528
529     /* In case of RGB, mangle the planes to Ut Video's format */
530     if (avctx->pix_fmt == PIX_FMT_RGBA || avctx->pix_fmt == PIX_FMT_RGB24)
531         mangle_rgb_planes(pic->data[0], c->planes, pic->linesize[0], width,
532                           height);
533
534     /* Deal with the planes */
535     switch (avctx->pix_fmt) {
536     case PIX_FMT_RGB24:
537     case PIX_FMT_RGBA:
538         for (i = 0; i < c->planes; i++) {
539             ret = encode_plane(avctx, pic->data[0] + ff_ut_rgb_order[i],
540                                c->slice_buffer, c->planes, pic->linesize[0],
541                                width, height, &pb);
542
543             if (ret) {
544                 av_log(avctx, AV_LOG_ERROR, "Error encoding plane %d.\n", i);
545                 return ret;
546             }
547         }
548         break;
549     case PIX_FMT_YUV422P:
550         for (i = 0; i < c->planes; i++) {
551             ret = encode_plane(avctx, pic->data[i], c->slice_buffer, 1,
552                                pic->linesize[i], width >> !!i, height, &pb);
553
554             if (ret) {
555                 av_log(avctx, AV_LOG_ERROR, "Error encoding plane %d.\n", i);
556                 return ret;
557             }
558         }
559         break;
560     case PIX_FMT_YUV420P:
561         for (i = 0; i < c->planes; i++) {
562             ret = encode_plane(avctx, pic->data[i], c->slice_buffer, 1,
563                                pic->linesize[i], width >> !!i, height >> !!i,
564                                &pb);
565
566             if (ret) {
567                 av_log(avctx, AV_LOG_ERROR, "Error encoding plane %d.\n", i);
568                 return ret;
569             }
570         }
571         break;
572     default:
573         av_log(avctx, AV_LOG_ERROR, "Unknown pixel format: %d\n",
574                avctx->pix_fmt);
575         return AVERROR_INVALIDDATA;
576     }
577
578     /*
579      * Write frame information (LE 32bit unsigned)
580      * into the output packet.
581      * Contains the prediction method.
582      */
583     frame_info = c->frame_pred << 8;
584     bytestream2_put_le32(&pb, frame_info);
585
586     /*
587      * At least currently Ut Video is IDR only.
588      * Set flags accordingly.
589      */
590     avctx->coded_frame->reference = 0;
591     avctx->coded_frame->key_frame = 1;
592     avctx->coded_frame->pict_type = AV_PICTURE_TYPE_I;
593
594     pkt->size   = bytestream2_tell_p(&pb);
595     pkt->flags |= AV_PKT_FLAG_KEY;
596
597     /* Packet should be done */
598     *got_packet = 1;
599
600     return 0;
601 }
602
603 AVCodec ff_utvideo_encoder = {
604     .name           = "utvideo",
605     .type           = AVMEDIA_TYPE_VIDEO,
606     .id             = CODEC_ID_UTVIDEO,
607     .priv_data_size = sizeof(UtvideoContext),
608     .init           = utvideo_encode_init,
609     .encode2        = utvideo_encode_frame,
610     .close          = utvideo_encode_close,
611     .pix_fmts       = (const enum PixelFormat[]) {
612                           PIX_FMT_RGB24, PIX_FMT_RGBA, PIX_FMT_YUV422P,
613                           PIX_FMT_YUV420P, PIX_FMT_NONE
614                       },
615     .long_name      = NULL_IF_CONFIG_SMALL("Ut Video"),
616 };