1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
46 #define BS_DEF_BLOCK_SIZE (1<<15)
48 typedef unsigned long ulong;
50 ulong bs_bits_masks[] = {
52 0x00000001, 0x00000003, 0x00000007, 0x0000000F,
53 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
54 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
55 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
56 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
57 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
58 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF,
59 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF
62 #define BSWAP(v) ((v<<24)|((v&0xff00)<<8)|((v>>8)&0xff00)|(v>>24))
64 void bs_bswap_block( uchar *start, uchar *end )
66 ulong* data = (ulong*)start;
67 int i, size = (end - start+3)/4;
69 for( i = 0; i < size; i++ )
78 ///////////////////////// RBaseStream ////////////////////////////
80 bool RBaseStream::IsOpened()
85 void RBaseStream::Allocate()
89 m_start = new uchar[m_block_size + m_unGetsize];
90 m_start+= m_unGetsize;
92 m_end = m_start + m_block_size;
97 RBaseStream::RBaseStream()
99 m_start = m_end = m_current = 0;
101 m_block_size = BS_DEF_BLOCK_SIZE;
102 m_unGetsize = 4; // 32 bits
107 RBaseStream::~RBaseStream()
109 Close(); // Close files
110 Release(); // free buffers
114 void RBaseStream::ReadBlock()
117 assert( m_file != 0 );
122 memcpy( m_start - m_unGetsize, m_end - m_unGetsize, m_unGetsize );
125 SetPos( GetPos() ); // normalize position
127 fseek( m_file, m_block_pos, SEEK_SET );
128 readed = fread( m_start, 1, m_block_size, m_file );
129 m_end = m_start + readed;
130 m_current -= m_block_size;
131 m_block_pos += m_block_size;
133 if( readed == 0 || m_current >= m_end ) throw RBS_THROW_EOS;
137 bool RBaseStream::Open( const char* filename )
142 m_file = fopen( filename, "rb" );
152 void RBaseStream::Close()
163 void RBaseStream::Release()
167 delete (m_start - m_unGetsize);
169 m_start = m_end = m_current = 0;
173 void RBaseStream::SetBlockSize( int block_size, int unGetsize )
175 assert( unGetsize >= 0 && block_size > 0 &&
176 (block_size & (block_size-1)) == 0 );
178 if( m_start && block_size == m_block_size && unGetsize == m_unGetsize ) return;
180 m_block_size = block_size;
181 m_unGetsize = unGetsize;
186 void RBaseStream::SetPos( int pos )
188 int offset = pos & (m_block_size - 1);
189 int block_pos = pos - offset;
191 assert( IsOpened() && pos >= 0 );
193 if( m_current < m_end && block_pos == m_block_pos - m_block_size )
195 m_current = m_start + offset;
199 m_block_pos = block_pos;
200 m_current = m_start + m_block_size + offset;
205 int RBaseStream::GetPos()
207 assert( IsOpened() );
208 return m_block_pos - m_block_size + (m_current - m_start);
211 void RBaseStream::Skip( int bytes )
213 assert( bytes >= 0 );
217 ///////////////////////// RLByteStream ////////////////////////////
219 int RLByteStream::GetByte()
221 uchar *current = m_current;
224 if( current >= m_end )
230 val = *((uchar*)current);
231 m_current = current + 1;
236 void RLByteStream::GetBytes( void* buffer, int length, int* readed )
238 uchar* data = (uchar*)buffer;
239 assert( length >= 0 );
241 if( readed) *readed = 0;
249 l = m_end - m_current;
250 if( l > length ) l = length;
254 memcpy( data, m_current, l );
258 if( readed ) *readed += l;
263 //////////// RLByteStream & RMByteStream <Get[d]word>s ////////////////
273 uchar *current = m_current;
276 if( current+1 < m_end )
278 val = *((unsigned short*)current);
279 m_current = current + 2;
284 val|= GetByte() << 8;
298 uchar *current = m_current;
301 if( current+1 < m_end )
303 val = *((unsigned short*)current);
304 m_current = current + 2;
305 val = (val >> 8)|((val & 255) << 8);
309 val = GetByte() << 8;
324 uchar *current = m_current;
327 if( current+3 < m_end )
329 val = *((int*)current);
330 m_current = current + 4;
347 uchar *current = m_current;
350 if( current+3 < m_end )
352 val = *((int*)current);
353 m_current = current + 4;
363 ///////////////////////// RLBitStream ////////////////////////////
365 void RLBitStream::ReadBlock()
367 RBaseStream::ReadBlock();
369 bs_bswap_block( m_start, m_end );
374 void RLBitStream::SetPos( int pos )
376 RBaseStream::SetPos(pos);
377 int offset = m_current - m_end;
378 m_current = m_end + (offset & -4);
379 m_bit_idx = (offset&3)*8;
383 int RLBitStream::GetPos()
385 return RBaseStream::GetPos() + (m_bit_idx >> 3);
389 int RLBitStream::Get( int bits )
391 int bit_idx = m_bit_idx;
392 int new_bit_idx = bit_idx + bits;
393 int mask = new_bit_idx >= 32 ? -1 : 0;
394 ulong* current = (ulong*)m_current;
396 if( (m_current = (uchar*)(current - mask)) >= m_end )
399 current = ((ulong*)m_current) + mask;
401 m_bit_idx = new_bit_idx & 31;
402 return ((current[0] >> bit_idx) |
403 ((current[1] <<-bit_idx) & mask)) & bs_bits_masks[bits];
406 int RLBitStream::Show( int bits )
408 int bit_idx = m_bit_idx;
409 int new_bit_idx = bit_idx + bits;
410 int mask = new_bit_idx >= 32 ? -1 : 0;
411 ulong* current = (ulong*)m_current;
413 if( (uchar*)(current - mask) >= m_end )
416 current = ((ulong*)m_current) + mask;
417 m_current = (uchar*)current;
419 return ((current[0] >> bit_idx) |
420 ((current[1] <<-bit_idx) & mask)) & bs_bits_masks[bits];
424 void RLBitStream::Move( int shift )
426 int new_bit_idx = m_bit_idx + shift;
427 m_current += (new_bit_idx >> 5) << 2;
428 m_bit_idx = new_bit_idx & 31;
432 int RLBitStream::GetHuff( const short* table )
439 int table_bits = table[0];
440 val = table[Show(table_bits) + 2];
441 code_bits = val & 15;
444 if( code_bits != 0 ) break;
450 if( val == RBS_HUFF_FORB ) throw RBS_THROW_FORB;
455 void RLBitStream::Skip( int bytes )
460 ///////////////////////// RMBitStream ////////////////////////////
462 void RMBitStream::ReadBlock()
464 RBaseStream::ReadBlock();
466 bs_bswap_block( m_start, m_end );
471 void RMBitStream::SetPos( int pos )
473 RBaseStream::SetPos(pos);
474 int offset = m_current - m_end;
475 m_current = m_end + ((offset - 1) & -4);
476 m_bit_idx = (32 - (offset&3)*8) & 31;
480 int RMBitStream::GetPos()
482 return RBaseStream::GetPos() + ((32 - m_bit_idx) >> 3);
486 int RMBitStream::Get( int bits )
488 int bit_idx = m_bit_idx - bits;
489 int mask = bit_idx >> 31;
490 ulong* current = ((ulong*)m_current) - mask;
492 if( (m_current = (uchar*)current) >= m_end )
495 current = (ulong*)m_current;
497 m_bit_idx = bit_idx &= 31;
498 return (((current[-1] << -bit_idx) & mask)|
499 (current[0] >> bit_idx)) & bs_bits_masks[bits];
503 int RMBitStream::Show( int bits )
505 int bit_idx = m_bit_idx - bits;
506 int mask = bit_idx >> 31;
507 ulong* current = ((ulong*)m_current) - mask;
509 if( ((uchar*)current) >= m_end )
511 m_current = (uchar*)current;
513 current = (ulong*)m_current;
516 return (((current[-1]<<-bit_idx) & mask)|
517 (current[0] >> bit_idx)) & bs_bits_masks[bits];
521 int RMBitStream::GetHuff( const short* table )
528 int table_bits = table[0];
529 val = table[Show(table_bits) + 1];
530 code_bits = val & 15;
533 if( code_bits != 0 ) break;
539 if( val == RBS_HUFF_FORB )
540 throw RBS_THROW_FORB;
546 void RMBitStream::Move( int shift )
548 int new_bit_idx = m_bit_idx - shift;
549 m_current -= (new_bit_idx >> 5)<<2;
550 m_bit_idx = new_bit_idx & 31;
554 void RMBitStream::Skip( int bytes )
560 static const int huff_val_shift = 20, huff_code_mask = (1 << huff_val_shift) - 1;
562 bool bs_create_decode_huffman_table( const int* src, short* table, int max_size )
564 const int forbidden_entry = (RBS_HUFF_FORB << 4)|1;
565 int first_bits = src[0];
572 int size = (1 << first_bits) + 1;
575 /* calc bit depths of sub tables */
576 memset( sub_tables, 0, (1 << first_bits)*sizeof(sub_tables[0]) );
577 for( i = 1, k = 1; src[k] >= 0; i++ )
579 int code_count = src[k++];
580 int sb = i - first_bits;
585 for( code_count += k; k < code_count; k++ )
587 int code = src[k] & huff_code_mask;
588 sub_tables[code >> sb].bits = sb;
592 /* calc offsets of sub tables and whole size of table */
593 for( i = 0; i < (1 << first_bits); i++ )
595 int b = sub_tables[i].bits;
599 sub_tables[i].offset = size;
604 if( size > max_size )
610 /* fill first table and subtables with forbidden values */
611 for( i = 0; i < size; i++ )
613 table[i] = (short)forbidden_entry;
616 /* write header of first table */
617 table[0] = (short)first_bits;
619 /* fill first table and sub tables */
620 for( i = 1, k = 1; src[k] >= 0; i++ )
622 int code_count = src[k++];
623 for( code_count += k; k < code_count; k++ )
625 int table_bits= first_bits;
627 int code = src[k] & huff_code_mask;
628 int val = src[k] >>huff_val_shift;
631 if( code_bits > table_bits )
633 int idx = code >> (code_bits -= table_bits);
634 code &= (1 << code_bits) - 1;
635 offset = sub_tables[idx].offset;
636 table_bits= sub_tables[idx].bits;
637 /* write header of subtable */
638 table[offset] = (short)table_bits;
639 /* write jump to subtable */
640 table[idx + 1]= (short)(offset << 4);
643 table_bits -= code_bits;
644 assert( table_bits >= 0 );
645 val = (val << 4) | code_bits;
646 offset += (code << table_bits) + 1;
648 for( j = 0; j < (1 << table_bits); j++ )
650 assert( table[offset + j] == forbidden_entry );
651 table[ offset + j ] = (short)val;
658 int* bs_create_source_huffman_table( const uchar* src, int* dst,
659 int max_bits, int first_bits )
661 int i, val_idx, code = 0;
664 for( i = 1, val_idx = max_bits; i <= max_bits; i++ )
666 int code_count = src[i - 1];
669 for( int k = 0; k < code_count; k++ )
671 dst[k + 1] = (src[val_idx + k] << huff_val_shift)|(code + k);
674 dst += code_count + 1;
675 val_idx += code_count;