Lair Of The Multimedia Guru

You need to choose a checksum and dunno which, well the 2 most popular ones are the CRC and Adler32 checksum

Speed / innermost loop

CRC32:

while(buffer<end -3){
    crc ^= le2me_32(*(uint32_t*)buffer); buffer+=4;
    crc =  tab[3][ crc     &0xFF]
          ^tab[2][(crc>>8 )&0xFF]
          ^tab[1][(crc>>16)&0xFF]
          ^tab[0][(crc>>24)     ];
}

Adler32:

while(buffer<end -3){
    s1 += *buffer++; s2+=s1;
    s1 += *buffer++; s2+=s1;
    s1 += *buffer++; s2+=s1;
    s1 += *buffer++; s2+=s1;
}

as we can see adler needs 12 adds and 4 1byte reads and crc needs 1 4byte read, 4 xor, 4 table lookups, 1 add, 3 and, 3 shift, without benchmarking i would say adler should be faster

Burst error detecting capabilities

CRC-32 can detect every burst error of 32 or less bits
Adler-32 will fail with at least one 17bit burst error (0 00000010 00000000 vs. 1 00000000 00000001)

Bit error detecting capabilities

CRC-32 differs depening upon generator polynom see misusing-crcs-for-error-correction
Adler-32 can detect every 2bit error within 65521 byte or so but will fail with some 3 bit errors

Random error detecting capabilities

CRC-32 will produce a evenly distributed checksum for messages >4byte
Adler-32 will produce a quite unevenly distributed checksum for small mesages so that the effective number of bits in the checksum is significantly reduced for short messags

adler32
len=     1, collisions=488296949(0.390637%), effective bits=7.999957
len=     2, collisions=  1903788(0.001523%), effective bits=16.002699
len=     4, collisions=   372789(0.000298%), effective bits=18.355140
len=     8, collisions=    94799(0.000076%), effective bits=20.330556
len=    16, collisions=    23902(0.000019%), effective bits=22.318296
len=    32, collisions=     6068(0.000005%), effective bits=24.296135
len=    64, collisions=     1573(0.000001%), effective bits=26.243837
len=   128, collisions=      669(0.000001%), effective bits=27.477278
len=   256, collisions=      437(0.000000%), effective bits=28.091651
len=   512, collisions=      331(0.000000%), effective bits=28.492453
len=  1024, collisions=      219(0.000000%), effective bits=29.088353
----
crc32
len=     1, collisions=488296915(0.390637%), effective bits=7.999957
len=     2, collisions=  1903782(0.001523%), effective bits=16.002703
len=     4, collisions=       22(0.000000%), effective bits=32.403708
len=     8, collisions=       29(0.000000%), effective bits=32.005159
len=    16, collisions=       30(0.000000%), effective bits=31.956249
len=    32, collisions=       28(0.000000%), effective bits=32.055785
len=    64, collisions=       39(0.000000%), effective bits=31.577738
len=   128, collisions=       39(0.000000%), effective bits=31.577738
len=   256, collisions=       32(0.000000%), effective bits=31.863140
len=   512, collisions=       32(0.000000%), effective bits=31.863140
len=  1024, collisions=       42(0.000000%), effective bits=31.470823

Note, generated with: check_collision.c

In correcting-byte-and-burst-errors-with-crcs we have seen that the CRC-32 polynom 0x04C11DB7 can correct 1 byte error in ~1mbit not that correcting single byte errors in such huge blocks is good for anything but ive found a much better one specifically 0x0D438219 which can correct one byte error in 9747877 bits

Can CRCs be used to fix a whole messed up byte? Yes as long as the codeword (data bits + crc bits) is less then whats in this table under 8≤b:

table was created with crc_test_v2.c

To actually correct byte errors the code below could be used, a complete example (crc_test_byte.c) is available too.

static int get_error(unsigned int crc, unsigned int len, int *error){
    int i;

    for(i=0; i<len; i++){
        if(!(crc & ~255)){
            *error= crc;
            return i;
        }
        crc= (crc>>1) ^ (((G>>1)|0x80000000) & (-(crc&1)));
    }
    return -1;
}

1 and 2 bit errors can easily be corrected by using the following code snippet, a complete example is available too.

    unsigned int i,v=1;
    for(i=0; i<block_size ; i++){
        crctab[i][0]= i ? (v^1) : v;
        crctab[i][1]= i;
        v= (v<<1) ^ (G & (((int)v)>>31));
    }

    qsort(crctab, BLOCK_SIZE, 2*sizeof(int), cmp);

static int get_error(unsigned int crc, unsigned int len, int error[2]){
    int i;

    for(i=0; i<len ; i++){
        int *result= bsearch(&crc, crctab, BLOCK_SIZE, 2*sizeof(int), cmp);
        if(result){
            error[0]= i;
            error[1]= result[1] + i;
            return 1 + (result != crctab[0]);
        }
        crc= (crc>>1) ^ (((G>>1)|0x80000000) & (-(crc&1)));
    }
    return -1;
}

Note, if you want to use this in anything where speed matters, then you should replace the qsort/bsearch with some hash table, i didnt as the c stadard doesnt contain any useable hashtable implementation and i was lazy

Cyclic Redundancy Check codes are commonly used for detecting errors, but they can also be used to correct single and multibit errors. To be able to correct e errors per code word and detect code words with d errors, its needed for the minimum hamming distance of a code to be > 2e+d
So what is the relation between the code word length and the minimum hamming distances for crc codes?

These where found using crc_test.c
Actually correcting errors is pretty trivial, for a single bit error, feeding the code below with the calculated crc XOR the received crc, will give you the distance from the end where the error ocured, and yeah if they match (crc=0) thn theres no single bit error

int get_single_error(int crc, int len){
    int i, v=1;

    for(i=0; i<len ; i++){
        if(v == crc)
            return i;
        v= (v<<1) ^ (generator_polynom & (v>>31));
    }
    return -1;
}

ill post some code examples to fix multibit errors later …

Ok kids, today we will look at how to quickly calculate a crc checksum, the naive way is to xor the crc polynomial with various shifts into the data to remove all 1 bits except the last 32 (or whatever length our crc polynom has) which from a mathemathical point of view is the data_polynom modulo the crc_polynom over GF(2)
now noone does that except maybe a few very smart or very stupid people :-) everyone else uses a 8bit->32bit look up table which simply contains the 32bit crc for each 8bit data polynom, more precissely:
LUT[i]= (i<<|CRC_POLY|) GF2_MOD CRC_POLY where GF2_MOD is the modulo operation between 2 binary polynoms over GF(2)
the actual code which uses this LUT looks approximately like:

for (i = 0; i < length; i++)
    crc = LUT[(crc&0xFF) ^ *buffer++] ^ (crc >>8);

a much faster method is to use 4 LUTs so that they gives the crc checksum 0,1,2,3 bytes ahead:
LUT[j][i]= (i<<(|CRC_POLY| + j*8)) GF2_MOD CRC_POLY
with that we can calculate the crc then by:

while(buffer<end-3){
    crc ^= le2me_32(*(uint32_t*)buffer); buffer+=4;
    crc =  tab[3][ crc     &0xFF]
          ^tab[2][(crc>>8 )&0xFF]
          ^tab[1][(crc>>16)&0xFF]
          ^tab[0][(crc>>24)     ];
}
while(buffer<end)
    crc = tab[0][(crc&0xFF) ^ *buffer++] ^ (crc >>8);

actually working code should be in ffmpeg/libavutil soon, if not ill post my messy proof of concept code

Another week has passed in the ffmpeg universe.

• Mans added -Bsymbolic, everyone wonders why this isnt default and what the ELF designers were smoking. Shared libav* becomes smaller, faster and more secure due to this change.
• Mike fixes a security issue in the mov/mp4 demuxer. Noone writes a security advisory, like always.
• Dave Yeo restores OS/2 support
• RV30/40 work by kostya
• VC1 improvments by kostya
• removing globals used in API by me and mans (due to issues with -Bsymbolic)
• export sha1 implementation in libavutil to the world (actually we just forgot to install the header) by Diego Pettenò
• Various h264 fixes by jeff
• Make mov useable over http by elupus and baptiste
• Support overriding codec id for input files by me
• Generic global header support for mov by baptiste
• User adjustable dynamic range compression for AC3 by justin
• djgpp support by Michael Kostylev
• PC Paintbrush PCX image decoder by ivo
• Sun Rasterfile decoder by ivo
• Extract aspect ratio from ODML-avis by me
• TechnoTrend PVA Demuxer by ivo
• support removing elements from the AVL tree in libavutil and make it independant of malloc() by me
• improve CRC API and install crc.h (another forgotten header) by aurel
• various request_channels related fixes by justin
• Linux Media Labs MPEG-4 (LMLM4) demuxer by ivo
• support for libdc1394 v.2 by Alessandro Sappia
• Do not install rtp.h (which should have never been part of the public API) by luca#1
• User specifyable maximum amount of memory to use for the index. by paul kelly
• libav-user was created by root
• Add support for H.264 video in the RTP muxer by luca#1
• ugly hack to support multicodec stsd in mov by me
• subtitle support in mov improvmets by me and reimar
• support for Matroska attachments by eugeni stepanov
• ICC support by reimar
• SMPTE 421 Annex L format demuxer by kostya
• The monthly flames, accusations and insults, a vote about fixing warnings and me, baptiste and many others fixing many. Some gcc bugs in -Werror being found, all decoders being changed to have const input by me …
• support for ogg text subtitles by reimar
• mbaff spatial direct support by loren
• many optimizations by loren
• parallel regression tests by mans
• various nut fixes by oded
• support for speex in ogg by reimar
• The first parts of libavfilter hit svn by bobby and vitor
• MANY bugfixes, ive ignored most due to lazyness and i think its not that interresting for most readers anyway
• Lots of cleanup by various people
• myself loosing the ability to reliably capitalize words correctly as i move toward the end of this entry, also note, nothing has been spellchecked as its almost 6 in the morning here …

After the extreemly popular recent changes in ffmpeg blog post, here are the next news, precissely 1 well something ;) afterwards

Note, errors and ommissions are unintended and if you spot any tell me and ill fix them (except spelling and grammer i wont bother fixing these)

• More work and patches by ronald and luca to get the IPv6 related code closer to being functional
• diego removed Metrowerks Codewarrior support due to it being unmaintained, broken and making the code more ugly (also not a single person complained so there is likely no one using it)
• Altivec runtime detection fix/cleanup and messup
• The remaining H.264 PAFF patches from jeff downs hit svn, sadly this also caused a slowdown of the decoder, so this needs more work to prevent this slowdown
• reimar removed the extreemly broken SIGILL based cpu extension detection code, the SIGILL code should have never been commited in the first place …
• luca barbato added support for a user specifyable maximum number of frames per RTP packet
• a optimized VP3 IDCT for blackfin by marc hoffman
• mans changed configure to use pr instead of cat -n as later is not standard, this will likely cause some minor annoyance to some users of non standard systems well fix your system, dont expect every lib and application to workaround it!
• a DNxHD (SMPTE VC-3) encoder by baptiste
• DNxHD 10 bit depth and 36mbit decoding support by baptiste
• user specifyable zlib compression level for PNG by reimar
• ogg seeking simplification and bugfix by reimar
• a very small part of the MMS patch hit svn
• some minor h.264 optimization by jeff downs
• infinite loop and negtive memcpy in the ac3 and aac parser fix by myself
• RC4, DES and encrypted asf support by reimar
• VP6 with huffman encoded blocks support by aurel
• deblocking for H.264 PAFF fix by Martin Zlomek
• nellymoser ASAO decoder by a840bda5870ba11f19698ff6eb9581dfb0f95fa5, 539459aeb7d425140b62a3ec7dbf6dc8e408a306, 520e17cd55896441042b14df2566a6eb610ed444
  Loic Minier and Benjamin Larsson
• support for electronic arts demuxer and decoders by aurel and peter ross
• speling, gramer and warning fixed by diego
• streaming to XBox360 fix by patric stout
• a regression fix related to url_split() by ronald
• display and sample aspect ratios display by michel
• WMV3 FASTTX=0 fix by kostya
• AVProgram API to export mpeg ts program information to the user app by nico
• rm demuxer changed to output frames instead of slices by kostya and roberto, this simplifies alot of related code
• Beam Software SIFF demuxer and video decoder by kostya
• support for reading duration from Xing and VBRI tag in mp3 files by andreas
• more flac encoding optimizations by loren
• moving the framecrc muxer to its own file by aurel
• and theres a patch for a MLP/TrueHD decoder by Ian Caulfield on ffmpeg-dev which i should review
• many other things ive missed …