}

    Move( code_bits );
    if( val == RBS_HUFF_FORB )
        throw RBS_THROW_FORB;

    return val;
}


void  RMBitStream::Move( int shift )
{
    int new_bit_idx = m_bit_idx - shift;
    m_current -= (new_bit_idx >> 5)<<2;
    m_bit_idx  = new_bit_idx & 31;
}


void  RMBitStream::Skip( int bytes )
{
    Move( bytes*8 );
}


static const int huff_val_shift = 20, huff_code_mask = (1 << huff_val_shift) - 1;

bool bsCreateDecodeHuffmanTable( const int* src, short* table, int max_size )
{   
    const int forbidden_entry = (RBS_HUFF_FORB << 4)|1;
    int       first_bits = src[0];
    struct
    {
        int bits;
        int offset;
    }
    sub_tables[1 << 11];
    int  size = (1 << first_bits) + 1;
    int  i, k;
    
    /* calc bit depths of sub tables */
    memset( sub_tables, 0, (1 << first_bits)*sizeof(sub_tables[0]) );
    for( i = 1, k = 1; src[k] >= 0; i++ )
    {
        int code_count = src[k++];
        int sb = i - first_bits;
        
        if( sb <= 0 )
            k += code_count;
        else
            for( code_count += k; k < code_count; k++ )
            {
                int  code = src[k] & huff_code_mask;
                sub_tables[code >> sb].bits = sb;
            }
    }

    /* calc offsets of sub tables and whole size of table */
    for( i = 0; i < (1 << first_bits); i++ )
    {
        int b = sub_tables[i].bits;
        if( b > 0 )
        {
            b = 1 << b;
            sub_tables[i].offset = size;
            size += b + 1;
        }
    }

    if( size > max_size )
    {
        assert(0);
        return false;
    }

    /* fill first table and subtables with forbidden values */
    for( i = 0; i < size; i++ )
    {
        table[i] = (short)forbidden_entry;
    }

    /* write header of first table */
    table[0] = (short)first_bits;

    /* fill first table and sub tables */ 
    for( i = 1, k = 1; src[k] >= 0; i++ )
    {
        int code_count = src[k++];
        for( code_count += k; k < code_count; k++ )
        {
            int  table_bits= first_bits;
            int  code_bits = i;
            int  code = src[k] & huff_code_mask;
            int  val  = src[k] >>huff_val_shift;
            int  j, offset = 0;

            if( code_bits > table_bits )
            {
                int idx = code >> (code_bits -= table_bits);
                code &= (1 << code_bits) - 1;
                offset   = sub_tables[idx].offset;
                table_bits= sub_tables[idx].bits;
                /* write header of subtable */
                table[offset]  = (short)table_bits;
                /* write jump to subtable */
                table[idx + 1]= (short)(offset << 4);
            }
        
            table_bits -= code_bits;
            assert( table_bits >= 0 );
            val = (val << 4) | code_bits;
            offset += (code << table_bits) + 1;
        
            for( j = 0; j < (1 << table_bits); j++ )
            {
                assert( table[offset + j] == forbidden_entry );
                table[ offset + j ] = (short)val;
            }
        }
    }
    return true;
}


int*  bsCreateSourceHuffmanTable( const uchar* src, int* dst,
                                  int max_bits, int first_bits )
{
    int   i, val_idx, code = 0;
    int*  table = dst;
    *dst++ = first_bits;
    for( i = 1, val_idx = max_bits; i <= max_bits; i++ )
    {
        int code_count = src[i - 1];
        dst[0] = code_count;
        code <<= 1;
        for( int k = 0; k < code_count; k++ )
        {
            dst[k + 1] = (src[val_idx + k] << huff_val_shift)|(code + k);
        }
        code += code_count;
        dst += code_count + 1;
        val_idx += code_count;
    }
    dst[0] = -1;
    return  table;
}


/////////////////////////// WBaseStream /////////////////////////////////

// WBaseStream - base class for output streams
WBaseStream::WBaseStream()
{
    m_start = m_end = m_current = 0;
    m_file = 0;
    m_block_size = BS_DEF_BLOCK_SIZE;
    m_is_opened = false;
}


WBaseStream::~WBaseStream()
{
    Close();    // Close files
    Release();  // free  buffers
}


bool  WBaseStream::IsOpened()
{ 
    return m_is_opened;
}


void  WBaseStream::Allocate()
{
    if( !m_start )
        m_start = new uchar[m_block_size];

    m_end = m_start + m_block_size;
    m_current = m_start;
}


void  WBaseStream::WriteBlock()
{
    int written, size = m_current - m_start;
    assert( m_file != 0 );

    //fseek( m_file, m_block_pos, SEEK_SET );
    written = fwrite( m_start, 1, size, m_file );
    m_current = m_start;

    if( written < size ) throw RBS_THROW_EOS;
    
    m_block_pos += size;
}


bool  WBaseStream::Open( const char* filename )
{
    Close();
    Allocate();
    
    m_file = fopen( filename, "wb" );
    
    if( m_file )
    {
        m_is_opened = true;
        m_block_pos = 0;
        m_current = m_start;
    }
    return m_file != 0;
}


void  WBaseStream::Close()
{
    if( m_file )
    {
        WriteBlock();
        fclose( m_file );
        m_file = 0;
    }
    m_is_opened = false;
}


void  WBaseStream::Release()
{
    if( m_start )
    {
        delete m_start;
    }
    m_start = m_end = m_current = 0;
}


void  WBaseStream::SetBlockSize( int block_size )
{
    assert( block_size > 0 && (block_size & (block_size-1)) == 0 );

    if( m_start && block_size == m_block_size ) return;
    Release();
    m_block_size = block_size;
    Allocate();
}


int  WBaseStream::GetPos()
{
    assert( IsOpened() );
    return m_block_pos + (m_current - m_start);
}


///////////////////////////// WLByteStream /////////////////////////////////// 

WLByteStream::~WLByteStream()
{
}

void WLByteStream::PutByte( int val )
{
    *m_current++ = (uchar)val;
    if( m_current >= m_end )
        WriteBlock();
}


void WLByteStream::PutBytes( const void* buffer, int count )
{
    uchar* data = (uchar*)buffer;
    
    assert( data && m_current && count >= 0 );

    while( count )
    {
        int l = m_end - m_current;
        
        if( l > count )
            l = count;
        
        if( l > 0 )
        {
            memcpy( m_current, data, l );
            m_current += l;
            data += l;
            count -= l;
        }
        if( m_current == m_end )
            WriteBlock();
    }
}


void WLByteStream::PutWord( int val )
{
    uchar *current = m_current;

    if( current+1 < m_end )
    {
        current[0] = (uchar)val;
        current[1] = (uchar)(val >> 8);
        m_current = current + 2;
        if( m_current == m_end )
            WriteBlock();
    }
    else
    {
        PutByte(val);
        PutByte(val >> 8);
    }
}


void WLByteStream::PutDWord( int val )
{
    uchar *current = m_current;

    if( current+3 < m_end )
    {
        current[0] = (uchar)val;
        current[1] = (uchar)(val >> 8);
        current[2] = (uchar)(val >> 16);
        current[3] = (uchar)(val >> 24);
        m_current = current + 4;
        if( m_current == m_end )
            WriteBlock();
    }
    else
    {
        PutByte(val);
        PutByte(val >> 8);
        PutByte(val >> 16);
        PutByte(val >> 24);
    }
}


///////////////////////////// WMByteStream /////////////////////////////////// 

WMByteStream::~WMByteStream()
{
}


void WMByteStream::PutWord( int val )
{
    uchar *current = m_current;

    if( current+1 < m_end )
    {
        current[1] = (uchar)val;
        current[0] = (uchar)(val >> 8);
        m_current = current + 2;
        if( m_current == m_end )
            WriteBlock();
    }
    else
    {
        PutByte(val >> 8);
        PutByte(val);
    }
}


void WMByteStream::PutDWord( int val )
{
    uchar *current = m_current;

    if( current+3 < m_end )
    {
        current[3] = (uchar)(val >> 24);
        current[2] = (uchar)(val >> 16);
        current[1] = (uchar)(val >> 8);
        current[0] = (uchar)val;
        m_current = current + 4;
        if( m_current == m_end )
            WriteBlock();
    }
    else
    {
        PutByte(val >> 24);
        PutByte(val >> 16);
        PutByte(val >> 8);
        PutByte(val);
    }
}


///////////////////////////// WMBitStream /////////////////////////////////// 

WMBitStream::WMBitStream()
{
    m_pad_val = 0;
    ResetBuffer();
}


WMBitStream::~WMBitStream()
{
}


bool  WMBitStream::Open( const char* filename )
{
    ResetBuffer();
    return WBaseStream::Open( filename );
}


void  WMBitStream::ResetBuffer()
{
    m_val = 0;
    m_bit_idx = 32;
    m_current = m_start;
}

void  WMBitStream::Flush()
{
    if( m_bit_idx < 32 )
    {
        Put( m_pad_val, m_bit_idx & 7 );
        *((ulong*&)m_current)++ = m_val;
    }
}


void  WMBitStream::Close()
{
    if( m_is_opened )
    {
        Flush();
        WBaseStream::Close();
    }
}


void  WMBitStream::WriteBlock()
{
#ifdef  LITTLE_ENDIAN
    bsBSwapBlock( m_start, m_current );
#endif
    WBaseStream::WriteBlock();
}


int  WMBitStream::GetPos()
{
    return WBaseStream::GetPos() + ((32 - m_bit_idx) >> 3);
}


void  WMBitStream::Put( int val, int bits )
{
    int  bit_idx = m_bit_idx - bits;
    ulong  curval = m_val;

    assert( 0 <= bits && bits < 32 );

    val &= bs_bit_mask[bits];

    if( bit_idx >= 0 )
    {
        curval |= val << bit_idx;
    }
    else
    {
        *((ulong*&)m_current)++ = curval | ((unsigned)val >> -bit_idx);
        if( m_current >= m_end )
        {
            WriteBlock();
        }
        bit_idx += 32;
        curval = val << bit_idx;
    }

    m_val = curval;
    m_bit_idx = bit_idx;
}


void  WMBitStream::PutHuff( int val, const ulong* table )
{
    int min_val = (int)table[0];
    val -= min_val;
    
    assert( (unsigned)val < table[1] );

    ulong code = table[val + 2];
    assert( code != 0 );
    
    Put( code >> 8, code & 255 );
}


bool bsCreateEncodeHuffmanTable( const int* src, ulong* table, int max_size )
{   
    int  i, k;
    int  min_val = INT_MAX, max_val = INT_MIN;
    int  size;
    
    /* calc min and max values in the table */
    for( i = 1, k = 1; src[k] >= 0; i++ )
    {
        int code_count = src[k++];

        for( code_count += k; k < code_count; k++ )
        {
            int  val = src[k] >> huff_val_shift;
            if( val < min_val )
                min_val = val;
            if( val > max_val )
                max_val = val;
        }
    }

    size = max_val - min_val + 3;

    if( size > max_size )
    {
        assert(0);
        return false;
    }

    memset( table, 0, size*sizeof(table[0]));

    table[0] = min_val;
    table[1] = size - 2;

    for( i = 1, k = 1; src[k] >= 0; i++ )
    {
        int code_count = src[k++];

        for( code_count += k; k < code_count; k++ )
        {
            int  val = src[k] >> huff_val_shift;
            int  code = src[k] & huff_code_mask;

            table[val - min_val + 2] = (code << 8) | i;
        }
    }
    return true;
}