more fail-safe FLAC parser

I submitted my FLAC parser (as mentioned in my last post) to the ffmpeg-devel mailing list and got a suggestion (a.k.a. requirement) from Michael for decreasing the likelihood of false-positive frame detection. Basically it would analyze a sequence of potential frame headers and pick the most likely sub-sequence based on concurrent non-overlapping CRC matches. It would also take header parameter changes into account. I am currently working on an implementation of this idea.

more FLAC parsing

As noted in my previous post, I was able to make a working FLAC parser, but I was not completely happy with it. I just had a feeling if I kept trying I could get it to work without buffering max_frame_size bytes and use a state variable instead.

Well, after many hours I finally got it working! At least it works for all samples I've tried so far. I still want to do more tests just to be sure though. Here is how it works:

• The FLACParseContext has a 31-byte state buffer and state size.
• I had to modify ff_combine_frame() to pad the parser buffer with 16 bytes instead of 8 bytes to accommodate negative values for start of frame less than -8.
  

1. If state buffer has data, copy data from current buffer to fill state buffer (or as much as possible). Search the first 16 bytes of the state buffer for start of frame and CRC of previous frame. If it passes, return start position within the buffer (will be negative).
   
2. Search the current buffer, up to 16 bytes before the end, for start of frame and CRC of previous frame. If the next frame is found, return the start position with the buffer. If none is found, check last 16 bytes for a frame sync word and if found, store in the state buffer. Return END_NOT_FOUND.
3. There are 2 exceptions to the CRC check. One is if an inline header is found since it will not have a CRC match. The other is if there are 10 CRC mismatches in a single frame. The reason for that is to abort the frame search for damaged files. It is extremely unlikely that a valid frame will have 10 CRC mismatches.
   

FLAC parsing

Let me start by saying that I very much dislike the raw FLAC format! After a lot of failed attempts I finally got a parser working. Part of the frustration was due to FLAC, and the other part was the way FFmpeg's parsing works.

First issue: reliable frame detection

• Using only the 16-bit frame header gives many many false positive frame start matches.
• Using the frame header + frame CRC-16 gives a handful of false positives.
• The only reliable way seems to be a full frame header validation including the header CRC-8, along with checking the CRC-16 for the whole frame.

Second issue: using FFmpeg's parser to combine pieces of frames from chunks of data

• Frame headers are variable-sized from 6 bytes to 16 bytes.
• The whole frame can be as small as 11 bytes, and silent frames are often less than 16 bytes.
  
• ff_combine_frame() only keeps up to 8 bytes of state information

So, the way I finally ended up with a working parser was to basically use the same strategy as the buffering that's done currently in the FLAC decoder, but do it with ff_combine_frame().

1. read first header to get starting point for block size/channels/bps
2. estimate maximum frame size
3. buffer enough data for maximum frame
4. detect next header
5. update maximum frame size with header info
   
6. update buffer
   
7. return frame start and size
8. goto 3

There are special cases for when there is no more data to read and for checking up to 11 bytes from the end of the buffer to make sure there isn't a small frame that's not being detected due to the 16-byte state size.

Flake updates

I decided to do some work on Flake recently. Among other things, I've tweaked the compression level settings, modified the API, added the pcm_io library from Aften and got rid of the internal WAVE reader, changed the build system to CMake. I added more stuff to the TODO list as well, so more changes will be forthcoming.

flake vs flac comparison

Today I did some speed/compression tests to compare Flake 0.11 to FLAC 1.2.0. The compression ratio for FLAC -8 has gotten a bit better since my last tests, so it currently beats Flake -8 in compression, but is still nowhere close to it in speed. I would recommend using Flake -9 now, which is still better than FLAC in both speed and compression.

I also included 2 high compression Flake modes in the tests. Both modes use large/variable frame size and high prediction orders, which makes them non-Subset-compliant. Flake -99 gives the highest possible compression without regard to speed. Flake -99 -v1 gives almost as good compression and is significantly faster. Just for fun I also included summary tests using WavPack, Monkey's Audio, and La.

All 6 Tests
Playing Time: 26:47.0
File Size: 270.34 MiB

               enc time    rate    size    compression
              ----------  ------  ------  -------------
FLAC  -8         0:34.7      46x   161.61     59.78%
Flake -8         0:17.4      92x   161.86     59.87%
Flake -9         0:20.1      80x   158.95     58.80%
Flake -99 -v 1   1:25.0      19x   152.73     56.50%
Flake -99        7:27.2       4x   151.22     55.94%

FLAC  -0         0:05.1     315x   188.32     69.66%
WavPack -hh      0:24.3      66x   157.15     58.13%
WavPack -hhx3    4:37.7       6x   153.83     56.90%
MAC -c3000       0:26.4      61x   152.81     56.53%
MAC -c4000       0:44.8      36x   145.92     53.98%
La -high         6:29.5       4x   143.06     52.92%