source: svn/trunk/newcon3bcm2_21bu/BSEAV/lib/bcmplayer/src/bvlc.c @ 2

/***************************************************************************
 *     Copyright (c) 2005-2009, Broadcom Corporation
 *     All Rights Reserved
 *     Confidential Property of Broadcom Corporation
 *
 *  THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE
 *  AGREEMENT  BETWEEN THE USER AND BROADCOM.  YOU HAVE NO RIGHT TO USE OR
 *  EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.
 *
 * $brcm_Workfile: bvlc.c $
 * $brcm_Revision: 8 $
 * $brcm_Date: 6/5/09 1:42p $
 *
 * Module Description: Converts startcode index to bcmplayer index
 *
 * Revision History:
 *
 * $brcm_Log: /BSEAV/lib/utils/bvlc.c $
 * 
 * 8   6/5/09 1:42p vsilyaev
 * PR 55759: Fixed hanlding of rogue data when parsing VLC codes
 * 
 * 7   3/6/09 11:21a vsilyaev
 * PR 52903: Fixed use of initialized variable
 * 
 * 6   9/1/05 3:36p erickson
 * PR16964: added const to parameter
 * 
 * 5   7/8/05 10:05a erickson
 * PR16155: modified b_vlc_decode to require current_index instead of
 * always starting from data[0]. This makes keeping track of where you
 * are in the buffer much easier for the application. Also changed and
 * expanded the examples.
 * 
 * 4   4/4/05 1:28p erickson
 * PR12728: fix warnings
 * 
 * 3   3/23/05 9:02a erickson
 * PR14451: use std debug interface
 * 
 * 2   3/22/05 5:21p erickson
 * PR14451: added optimizations
 * 
 * 1   3/21/05 3:43p erickson
 * PR14451: added generic vlc decode algorithm
 * 
 ************************************************************/
#include "bvlc.h"

#ifndef USE_LEGACY_KERNAL_INTERFACE
/* Magnum debug interface */
#include "bstd.h"
BDBG_MODULE(bvlc);
#else
/* Simplistic debug interface based on stdio */
#include <stdio.h>
#define BDBG_ERR(X) /* do {printf X; printf("\n"); } while(0) */
#define BDBG_WRN(X) BDBG_ERR(X)
#define BDBG_MSG(X) BDBG_ERR(X)
#endif

/**
Advance both bit and index by one through the byte array
**/
#define ADVANCE(bit, index, size) \
        do {if (bit) {(bit)--;} else {(bit)=7;if(++(index)>=size) {goto err_eof;}} } while (0)

/* set next_index and next_bit so any function call then would return EOF */
static int b_vlc_mark_eof(unsigned size, unsigned *next_index, unsigned *next_bit)
{
    *next_bit = 0;
    if(size>0) {
        *next_index = size-1;
    } else {
        *next_index = 0;
    }
    return -1;
}

static int b_vlc_measure_prefix(const uint8_t *data,unsigned size,unsigned index,unsigned current_bit, 
        unsigned *next_index,unsigned *next_bit,unsigned *prefix_length)
{
        int bit = current_bit;
        int done = 0;

    *next_bit = current_bit; /* always initialize result */
        if (bit > 7) {
                BDBG_ERR(("Invalid bit. Must be 0..7."));
                return -1;
        }
        
        *prefix_length = 0;
        
        /* count 0's to determine prefix_length */
        for (;;) {
                while (bit >= 0 && !done) {
                        if (data[index] & (0x1 << bit))
                                done = 1;
                        else {
                                (*prefix_length)++;
                                bit--;
                        }
                }
                if (done)  {
                        break;
        }
        index++;
        if(index<size) {
                    bit = 7;
        } else {
            bit = 0;
            if(size>0) {
                index = size-1;
            } else {
                index = 0;
            }
            goto err_eof;
        }
        }
        /* make sure we have enough data */
        if (*prefix_length > (size * 8)/2-1) {
                BDBG_ERR(("not enough data sent for this vlc value"));
        goto err_eof;
        }
        
        *next_index = index;
        *next_bit = bit;
        return 0;
err_eof:
    return b_vlc_mark_eof(size, next_index, next_bit);
}

int b_vlc_skip(const uint8_t *data, unsigned size, unsigned current_index, unsigned current_bit, 
        unsigned *next_index,unsigned *next_bit)
{
        unsigned prefix_length;
        
        if (b_vlc_measure_prefix(data, size, current_index, current_bit, next_index, next_bit, &prefix_length)) {
        goto err_eof;
    }

#if 1
        /* Optimization: use integer math to advance by prefix_length + 1 */
        prefix_length++; /* take into account the middle 1 */
        if (prefix_length <= *next_bit)
                *next_bit -= prefix_length;
        else {
        unsigned index;
        prefix_length -= *next_bit + 1;
        index = *next_index +  1 + prefix_length/8;
        if(index<size) {
            *next_index = index;
            *next_bit = 7 - (prefix_length % 8);
        } else {
            goto err_eof;
        }
        }
#else
        /* advance one bit at a time */
        /* skip the middle 1 */
        ADVANCE(*next_bit, *next_index, size);
        
        /* skip the suffix - measure_prefix has already guaranteed we have enough data */
        while (prefix_length--)
                ADVANCE(*next_bit, *next_index, size);
#endif
                
        return 0;
err_eof:
    return b_vlc_mark_eof(size, next_index, next_bit);
}

int b_vlc_decode(const uint8_t *data,unsigned size,unsigned current_index,unsigned current_bit, 
        unsigned *next_index,unsigned *next_bit)
{
        unsigned index;
        int bit;
        unsigned suffix_length, prefix_length;
        unsigned value;
        uint64_t suffix;
                
        BDBG_MSG(("vlc: %02x%02x %d, bit %d", data[current_index], (size>current_index+1)?data[current_index+1]:0, size, current_bit));

        /* find the first 1, which determines prefix_length */
        if (b_vlc_measure_prefix(data, size, current_index, current_bit, &index, (unsigned*)&bit, &prefix_length)) {
        goto err_eof;
    }
        
        if (prefix_length > 64) {
                BDBG_ERR(("vlc value too large for this algorithm"));
                /* If you hit this, rework the algorithm. I'm assuming I can load the
                entire suffix into a primitive datatype. */
        goto err_eof;
        }
        
        /* advance past middle 1 */
        ADVANCE(bit, index, size);
        
        /* get suffix based on prefix_length */
        
        /* Optimization: no prefix, no suffix, value is 0 */
        if (!prefix_length) {
                value = 0;
                BDBG_MSG(("  prefix len 0, done"));
        }
        else {
                /* Optimization: if the suffix is completely contained in this byte, we 
                don't have to operate bitwise */
                if (prefix_length <= 8 && (int)prefix_length <= bit+1) {
                        static unsigned char mask[] = {0x0,0x01,0x03,0x07,0x0F,0x1F,0x3F,0x7F,0xFF};
                        suffix = (data[index] >> (bit-(prefix_length-1))) & mask[prefix_length];
                        BDBG_MSG(("  prefix len %d, suffix (in byte) val %x", prefix_length, (int)suffix));
                        bit -= prefix_length;
                        if (bit == -1) {
                                bit = 7;
                                index++;
                if(index>=size) { goto err_eof; }
                        }
                }
                else {
                        /* step through it bit by bit. this is the most general way and will
                        work with any value. */
                        suffix = 0;
                        BDBG_MSG(("  prefix len %d, index %d bit %d", prefix_length, index, bit));
                        for (suffix_length = 0; suffix_length < prefix_length; suffix_length++) {
                                suffix <<= 1;
                                if (data[index] & (0x1 << bit))
                                        suffix |= 1;
                                ADVANCE(bit, index, size);
                        }
                        BDBG_MSG(("  prefix len %d, suffix val %x", prefix_length, (int)suffix));
                }
        
                /* now do the final calculation: 2^prefix_length - 1 + suffix */
                value = 1;
                while (prefix_length--) value *= 2;
                value = value - 1 + suffix;
        }

        /* move to the next bit so that subsequent calls to b_vld_decode are easy
        to make for adjacent values. */
        if (next_index) *next_index = index;
        if (next_bit) *next_bit = bit;
                
        BDBG_MSG(("  result = %d (%d, %d)", value, index, bit));
        return value;
err_eof:
    return b_vlc_mark_eof(size, next_index, next_bit);
}

#if 0
/* The VLC algorithm is complicated, and probably should be optimized in the
future. This routine helps test it. Please leave it in the code for reference. */
#define BDBG_ASSERT assert
#include <assert.h>

#define ERROR() do{BDBG_ERR(("Error on line %d", __LINE__)); return -1;}while (0)

int test(unsigned char byte0, unsigned char byte1, unsigned char byte2,
        int size, int test_val, int test_next_index, int test_next_bit)
{
        char buf[3] = {byte0, byte1, byte2};
        int val;
        unsigned next_index, next_bit;
        
        next_index = 0; next_bit = 7;
        val = b_vlc_decode(buf, size, next_index, next_bit, &next_index, &next_bit);
        if (val != test_val) ERROR();
        if (next_index != test_next_index) ERROR();
        if (next_bit != test_next_bit) ERROR();

        next_index = 0; next_bit = 7;
        b_vlc_skip(buf, size, next_index, next_bit, &next_index, &next_bit);
        if (next_index != test_next_index) ERROR();
        if (next_bit != test_next_bit) ERROR();
        
        return 0;
}

int main()
{
        char buf[10];
        int val;
        unsigned next_index, next_bit;

        test(0x80, 0x00, 0x00, 1,               0, 0, 6);
        test(0x40, 0x00, 0x00, 1,               1, 4, 0);
        test(0x60, 0x00, 0x00, 1,               2, 0, 4);
        test(0x20, 0x00, 0x00, 1,               3, 0, 2);
        test(0x28, 0x00, 0x00, 1,               4, 0, 2);
        test(0x14, 0x00, 0x00, 1,               9, 0, 0);
        test(0x05, 0x40, 0x00, 2,               41, 1, 4);
        test(0x01, 0x40, 0x00, 2,               158, 1, 1);
        test(0x01, 0xFF, 0x00, 2,               254, 1, 0);
        test(0x00, 0x20, 0x00, 3,               1023, 2, 2);
        
        buf[0] = 0xf4; /* skip,skip,skip,skip, 010 */
        next_index = 0; next_bit = 7;
        b_vlc_skip(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(next_bit == 6);
        b_vlc_skip(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(next_bit == 5);
        b_vlc_skip(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(next_bit == 4);
        b_vlc_skip(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(next_bit == 3);
        val = b_vlc_decode(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(val == 1);
        BDBG_ASSERT(next_index == 0);
        BDBG_ASSERT(next_bit == 0);

        buf[0] = 0xf0; /* 0, 0, 0, 0 */
        next_index = 0; next_bit = 7;
        val = b_vlc_decode(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(val == 0);
        val = b_vlc_decode(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(val == 0);
        val = b_vlc_decode(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(val == 0);
        val = b_vlc_decode(buf, 1, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(val == 0);
        BDBG_ASSERT(next_index == 0);
        BDBG_ASSERT(next_bit == 3);
        
        buf[0] = 0x00;
        buf[1] = 0xf0;
        buf[2] = 0xe0;
        next_index = 0; next_bit = 7;
        val = b_vlc_decode(buf, 3, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(val == 480);
        val = b_vlc_decode(buf, 3, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(val == 0);
        val = b_vlc_decode(buf, 3, next_index, next_bit, &next_index, &next_bit);
        BDBG_ASSERT(val == 0);
        BDBG_ASSERT(next_index == 2);
        BDBG_ASSERT(next_bit == 4);
        
        return 0;
}
#endif