[FFmpeg-devel] [PATCH] FLAC parser

Michael Chinen mchinen
Mon Oct 11 01:42:09 CEST 2010


Hi,

On Sat, Oct 9, 2010 at 10:14 AM, Justin Ruggles
<justin.ruggles at gmail.com> wrote:
>[...]
>> From b5890854908d6032819cf77aec0524da3ba352fb Mon Sep 17 00:00:00 2001
>> From: Michael Chinen <mchinen at gmail.com>
>> Date: Thu, 7 Oct 2010 17:47:52 +0200
>> Subject: [PATCH 2/3] Add error codes for FLAC header parsing and move log errors to flacdec.c
>>
>> ---
>> ?libavcodec/flac.c ? ?| ? 45 +++++++++++++++++++--------------------------
>> ?libavcodec/flac.h ? ?| ? 20 ++++++++++++++++----
>> ?libavcodec/flacdec.c | ? 33 ++++++++++++++++++++++++++++++---
>> ?3 files changed, 65 insertions(+), 33 deletions(-)
>>
>> diff --git a/libavcodec/flac.c b/libavcodec/flac.c
>> index f6b65ce..5e97564 100644
>> --- a/libavcodec/flac.c
>> +++ b/libavcodec/flac.c
>> @@ -32,13 +32,16 @@ static int64_t get_utf8(GetBitContext *gb)
>> ? ? ?return val;
>> [...]
>> + ? ?/* uses fixed size stream code */
>> + ? ?fi->is_var_size = get_bits1(gb);
>
> /* variable block size stream code */

done.

>
>> ? ? ?/* reserved bit */
>> - ? ?if (get_bits1(gb)) {
>> - ? ? ? ?av_log(avctx, AV_LOG_ERROR, "broken stream, invalid padding\n");
>> - ? ? ? ?return -1;
>> - ? ?}
>> + ? ?if (get_bits1(gb))
>> + ? ? ? ?return FLAC_FRAME_HEADER_ERROR_PADDING;
>> [...]
>> ? ? ?/* header CRC-8 check */
>> ? ? ?skip_bits(gb, 8);
>> ? ? ?if (av_crc(av_crc_get_table(AV_CRC_8_ATM), 0, gb->buffer,
>> - ? ? ? ? ? ? ? get_bits_count(gb)/8)) {
>> - ? ? ? ?av_log(avctx, AV_LOG_ERROR, "header crc mismatch\n");
>> - ? ? ? ?return -1;
>> - ? ?}
>> + ? ? ? ? ? ? ? get_bits_count(gb)/8))
>> + ? ? ? ?return FLAC_FRAME_HEADER_ERROR_CRC;
>
>
> This is just a nit-pick, but changing from using braces to not using
> braces in these 2 places is a cosmetic change.

done.

>
>>
>> ? ? ?return 0;
>> ?}
>> diff --git a/libavcodec/flac.h b/libavcodec/flac.h
>> index fe38463..bb29676 100644
>> --- a/libavcodec/flac.h
>> +++ b/libavcodec/flac.h
>> @@ -81,6 +92,8 @@ typedef struct FLACFrameInfo {
>> ? ? ?FLACCOMMONINFO
>> ? ? ?int blocksize; ? ? ? ? ?/**< block size of the frame ? ? ? ? ? ? ? ? */
>> ? ? ?int ch_mode; ? ? ? ? ? ?/**< channel decorrelation mode ? ? ? ? ? ? ?*/
>> + ? ?int64_t frame_or_sample_num; ?/**< frame number or sample number ? ? ? ? ? ? ? ? ? ? ? ? */
>> + ? ?int is_var_size; ? ? ? ? ? ? ?/**< determines if the above variable is frames or samples */
>
>
> I think the documentation of is_var_size could be better. ?It specifies
> if the stream uses variable block sizes or a fixed block size, and it
> determines the meaning of frame_or_sample_num.

done.

>
>
>> From ecd062d8bf5f00da470bde387c641c50004239d9 Mon Sep 17 00:00:00 2001
>> From: Michael Chinen <mchinen at gmail.com>
>> Date: Thu, 7 Oct 2010 17:49:22 +0200
>> Subject: [PATCH 3/3] Add FLAC Parser
>> ?flac_parser.c verifies all possible chains within a certain header radius and scores them based on changes in sample rate, bit depth, channels.
>> ?Update new flac seek test reference file.
>> [...]
>> diff --git a/libavcodec/flac_parser.c b/libavcodec/flac_parser.c
>> new file mode 100644
>> index 0000000..5c2d806
>> --- /dev/null
>> +++ b/libavcodec/flac_parser.c
>> @@ -0,0 +1,545 @@
>> +/**
>> + * @file
>> + * FLAC parser
>> + *
>> + * The FLAC parser buffers input until FLAC_MIN_HEADERS has been found.
>> + * Each time it finds a CRC-8 verified header it sees which of the
>> + * FLAC_MAX_SEQUENTIAL_HEADERS that came before it have a valid CRC-16 footer
>> + * that ends at the newly found header.
>> + * Headers are scored by FLAC_HEADER_BASE_SCORE plus the max of it's crc-verified
>> + * children, penalized by changes in sample rate, frame number, etc.
>> + * The parser returns the header with the highest score.
>> + **/
>
>
> The parser returns the *frame* whose header has the highest score.

done.

>
>
>> + ? ?int max_score; ? ?/**< maximum score found after checking each child that
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ?has a valid CRC ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? */
>
>
> vertical alignment
>
>> +typedef struct FLACParseContext {
>> + ? ?AVCodecContext *avctx; ? ? ? ? /**< codec context pointer for logging ? ? */
>> + ? ?AVFifoBuffer *fifo_buf; ? ? ? ?/**< buffer to store all data until headers
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?can be verified ? ? ? ? ? ? ? ? ? ? ? */
>> + ? ?uint8_t *wrap_buf; ? ? ? ? ? ? /**< general fifo read buffer when wrapped */
>> + ? ?int wrap_buf_allocated_size; ? /**< actual allocated size of the buffer ? */
>> + ? ?uint8_t *crc_buf; ? ? ? ? ? ? ?/**< update_sequences_header's fifo read
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?buffer when the request wraps ? ? ? ? */
>> + ? ?int crc_buf_allocated_size; ? ?/**< actual allocated size of the buffer ? */
>> + ? ?FLACHeaderMarker *headers; ? ? /**< linked-list that starts at the first
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?CRC-8 verified header within buffer ? */
>> + ? ?FLACHeaderMarker *best_header; /**< highest scoring header within buffer ?*/
>> + ? ?int nb_headers_found; ? ? ? ? ?/**< number of headers found in the last
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?flac_parse() call ? ? ? ? ? ? ? ? ? ? */
>> + ? ?int best_header_valid; ? ? ? ? /**< flag set when the parser returns junk;
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if set return best_header next time ? */
>> + ? ?int end_padded; ? ? ? ? ? ? ? ?/**< if 1 then buffer end was padded ? ? ? */
>> +} FLACParseContext;
>
> Can you separate the buffer-specific stuff from the parser-specific
> stuff? ?That would make it easier to read I think.

Ok, I moved them together at the end.

>
>> +/**
>> + * Non-destructive fast fifo pointer fetching
>> + * Returns a pointer from the specified offset.
>> + * If possible the pointer points within the fifo buffer.
>> + * Otherwise (if it would cause a wrap around,) a temporary
>> + * buffer is used which is valid till the next call to
>> + * flac_fifo_read
>> + */
>> +static uint8_t* flac_fifo_read(FLACParseContext *fpc, int offset, int len,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? uint8_t** wrap_buf, int* allocated_size)
>> +{
>> + ? ?AVFifoBuffer *f ? = fpc->fifo_buf;
>> + ? ?uint8_t *start ? ?= f->rptr + offset;
>> + ? ?uint8_t *tmp_buf;
>> +
>> + ? ?if (start > f->end)
>> + ? ? ? ?start -= f->end - f->buffer;
>> + ? ?if(f->end - start >= len)
>> + ? ? ? ?return start;
>> +
>> + ? ?tmp_buf = av_fast_realloc(*wrap_buf, allocated_size,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?len + *allocated_size);
>> + ? ?if (!tmp_buf) {
>> + ? ? ? ?av_log(fpc->avctx, AV_LOG_ERROR,
>> + ? ? ? ? ? ? ? "couldn't reallocate wrap buffer of size addition %d"
>> + ? ? ? ? ? ? ? " to exisiting size %d\n", len, *allocated_size);
>> + ? ? ? ?return NULL;
>> + ? ?}
>> + ? ?*wrap_buf = tmp_buf;
>> + ? ?do {
>> + ? ? ? ?int seg_len = FFMIN(f->end - start, len);
>> + ? ? ? ?memcpy(tmp_buf, start, seg_len);
>> + ? ? ? ?tmp_buf = (uint8_t*)tmp_buf + seg_len;
>> +// memory barrier needed for SMP here in theory
>> +
>> + ? ? ? ?start += seg_len - (f->end - f->buffer);
>> + ? ? ? ?len -= seg_len;
>> + ? ?} while (len > 0);
>> +
>> + ? ?return *wrap_buf;
>> +}
>
>
> Do you have any tests to show whether using the FIFO makes the parser
> faster and/or use less memory? ?It certainly seems more complicated.
> Also, it uses a lot of pointer math. ?Have you checked that it is safe
> from integer overflow?

I just guessed it is faster because the old one used memmove which
would mean shifting of 20 frames every time a frame is returned.
The fifo version has a few extra buffers sitting around, but uses at
most a frame's worth more memory.

But you're right, speed should be tested.  I ran tests of fifo vs. the
old memmove sliding version.

I used the START_TIMER/STOP_TIMER macros to profile flac_parse().

4 runs on a four minute flac file (with fifo):
236920 dezicycles in with fifo, 14541 runs, 1843 skips
237042 dezicycles in with fifo, 14544 runs, 1840 skips
237761 dezicycles in with fifo, 14537 runs, 1847 skips
241054 dezicycles in with fifo, 14543 runs, 1841 skips

4 runs on the same file (without fifo):
273416 dezicycles in without fifo, 14551 runs, 1833 skips
272648 dezicycles in without fifo, 14562 runs, 1822 skips
273739 dezicycles in without fifo, 14544 runs, 1840 skips
275199 dezicycles in without fifo, 14545 runs, 1839 skips

There is about 15% faster overall in the function. I suspect the
actual parsing to be the real bottleneck, but because the buffer
access is scattered throughout the parsing code I didn't try to figure
out exactly how much the actual buffer code speed differences is. I
interpreted it to mean it is likely much better than 15%.

>
>> + ? ? ? ?/* Remove headers in list until the end of the best_header. */
>> + ? ? ? ?for (curr = fpc->headers; curr != best_child; curr = temp) {
>> + ? ? ? ? ? ?if (curr != fpc->best_header) {
>> + ? ? ? ? ? ? ? ?av_log(avctx, AV_LOG_DEBUG,
>> + ? ? ? ? ? ? ? ? ? ? ? "dropping low score %i frame header from offset %i "
>> + ? ? ? ? ? ? ? ? ? ? ? "to %i\n",
>> + ? ? ? ? ? ? ? ? ? ? ? curr->max_score, curr->offset, curr->next->offset);
>
> weird alignment/wrapping

Please clarify what's weird if I didn't get it.
The string wrapping is to adhere to the under 80 rule.
The alignment is to the first parameter for av_log.
I took a guess and made each parameter on it's own line.

>
>> + ? ? ? ? ? ?/* Set frame_size to 0. It is unknown or invalid in a junk frame. */
>> + ? ? ? ? ? ?avctx->frame_size = 0;
>> + ? ? ? ? ? ?*poutbuf_size ? ? = fpc->best_header->offset;
>> + ? ? ? ? ? ?*poutbuf ? ? ? ? ?= flac_fifo_read(fpc, 0,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?*poutbuf_size,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?&fpc->crc_buf,
>> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?&fpc->crc_buf_allocated_size);
>
>
> weird alignment/wrapping

fixed alignment.  Also put the 0 on its own line (is this desired?)

>
>> +static int flac_parse_init(AVCodecParserContext *c)
>> +{
>> + ? ?FLACParseContext *fpc = c->priv_data;
>> + ? ?fpc->fifo_buf = av_fifo_alloc(1024);
>
> Why 1024? ?A nearby power of 2 for one average 16-bit stereo FLAC frame
> would be closer to 8192.

You are right.  I changed it to 8192 * FLAC_MIN_HEADERS because there
are FLAC_MIN_HEADERS expected to be in it.

>
>> diff --git a/libavcodec/flacdec.c b/libavcodec/flacdec.c
>> index 133adbb..77b548e 100644
>> --- a/libavcodec/flacdec.c
>> +++ b/libavcodec/flacdec.c
>>[...]
>> ? ? ?/* check that there is at least the smallest decodable amount of data.
>> ? ? ? ? this amount corresponds to the smallest valid FLAC frame possible.
>> ? ? ? ? FF F8 69 02 00 00 9A 00 00 34 46 */
>> - ? ?if (buf_size < 11)
>> - ? ? ? ?goto end;
>> + ? ? if (buf_size < FLAC_MIN_FRAME_SIZE)
>> + ? ? ? ? return buf_size;
>
> extra space?

Good eye!

Michael
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-move-decode_frame_header-from-flacdec.c-to-flac.c-h.patch
Type: application/octet-stream
Size: 8119 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101011/59302f0c/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-Add-error-codes-for-FLAC-header-parsing-and-move-log.patch
Type: application/octet-stream
Size: 7589 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101011/59302f0c/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0003-Add-FLAC-Parser.patch
Type: application/octet-stream
Size: 35050 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20101011/59302f0c/attachment-0002.obj>



More information about the ffmpeg-devel mailing list