git.maemo.org Git - opencv/blob - otherlibs/VlGrFmts/bitstrm.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
   4 //
   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.
   8 //
   9 //
  10 //                        Intel License Agreement
  11 //                For Open Source Computer Vision Library
  12 //
  13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  14 // Third party copyrights are property of their respective owners.
  15 //
  16 // Redistribution and use in source and binary forms, with or without modification,
  17 // are permitted provided that the following conditions are met:
  18 //
  19 //   * Redistribution's of source code must retain the above copyright notice,
  20 //     this list of conditions and the following disclaimer.
  21 //
  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.
  25 //
  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.
  28 //
  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.
  39 //
  40 //M*/
  41
  42 #include <assert.h>
  43 #include <string.h>
  44 #include "bitstrm.h"
  45
  46 #define  BS_DEF_BLOCK_SIZE   (1<<15)
  47
  48 typedef unsigned long ulong;
  49
  50 ulong bs_bits_masks[] = {
  51     0,
  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
  60 };
  61
  62 #define BSWAP(v)     ((v<<24)|((v&0xff00)<<8)|((v>>8)&0xff00)|(v>>24))
  63
  64 void bs_bswap_block( uchar *start, uchar *end )
  65 {
  66     ulong* data = (ulong*)start;
  67     int    i, size = (end - start+3)/4;
  68
  69     for( i = 0; i < size; i++ )
  70     {
  71         ulong temp = data[i];
  72         temp = BSWAP( temp );
  73         data[i] = temp;
  74     }
  75 }
  76
  77
  78 /////////////////////////  RBaseStream ////////////////////////////
  79
  80 bool  RBaseStream::IsOpened()
  81 {
  82     return m_is_opened;
  83 }
  84
  85 void  RBaseStream::Allocate()
  86 {
  87     if( !m_start )
  88     {
  89         m_start = new uchar[m_block_size + m_unGetsize];
  90         m_start+= m_unGetsize;
  91     }
  92     m_end = m_start + m_block_size;
  93     m_current = m_end;
  94 }
  95
  96
  97 RBaseStream::RBaseStream()
  98 {
  99     m_start  = m_end = m_current = 0;
 100     m_file   = 0;
 101     m_block_size = BS_DEF_BLOCK_SIZE;
 102     m_unGetsize = 4; // 32 bits
 103     m_is_opened  = false;
 104 }
 105
 106
 107 RBaseStream::~RBaseStream()
 108 {
 109     Close();    // Close files
 110     Release();  // free  buffers
 111 }
 112
 113
 114 void  RBaseStream::ReadBlock()
 115 {
 116     int readed;
 117     assert( m_file != 0 );
 118
 119     // copy unget buffer
 120     if( m_start )
 121     {
 122         memcpy( m_start - m_unGetsize, m_end - m_unGetsize, m_unGetsize );
 123     }
 124
 125     SetPos( GetPos() ); // normalize position
 126
 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;
 132
 133     if( readed == 0 || m_current >= m_end ) throw RBS_THROW_EOS;
 134 }
 135
 136
 137 bool  RBaseStream::Open( const char* filename )
 138 {
 139     Close();
 140     Allocate();
 141
 142     m_file = fopen( filename, "rb" );
 143
 144     if( m_file )
 145     {
 146         m_is_opened = true;
 147         SetPos(0);
 148     }
 149     return m_file != 0;
 150 }
 151
 152 void  RBaseStream::Close()
 153 {
 154     if( m_file )
 155     {
 156         fclose( m_file );
 157         m_file = 0;
 158     }
 159     m_is_opened = false;
 160 }
 161
 162
 163 void  RBaseStream::Release()
 164 {
 165     if( m_start )
 166     {
 167         delete (m_start - m_unGetsize);
 168     }
 169     m_start = m_end = m_current = 0;
 170 }
 171
 172
 173 void  RBaseStream::SetBlockSize( int block_size, int unGetsize )
 174 {
 175     assert( unGetsize >= 0 && block_size > 0 &&
 176            (block_size & (block_size-1)) == 0 );
 177
 178     if( m_start && block_size == m_block_size && unGetsize == m_unGetsize ) return;
 179     Release();
 180     m_block_size = block_size;
 181     m_unGetsize = unGetsize;
 182     Allocate();
 183 }
 184
 185
 186 void  RBaseStream::SetPos( int pos )
 187 {
 188     int offset = pos & (m_block_size - 1);
 189     int block_pos = pos - offset;
 190
 191     assert( IsOpened() && pos >= 0 );
 192
 193     if( m_current < m_end && block_pos == m_block_pos - m_block_size )
 194     {
 195         m_current = m_start + offset;
 196     }
 197     else
 198     {
 199         m_block_pos = block_pos;
 200         m_current = m_start + m_block_size + offset;
 201     }
 202 }
 203
 204
 205 int  RBaseStream::GetPos()
 206 {
 207     assert( IsOpened() );
 208     return m_block_pos - m_block_size + (m_current - m_start);
 209 }
 210
 211 void  RBaseStream::Skip( int bytes )
 212 {
 213     assert( bytes >= 0 );
 214     m_current += bytes;
 215 }
 216
 217 /////////////////////////  RLByteStream ////////////////////////////
 218
 219 int  RLByteStream::GetByte()
 220 {
 221     uchar *current = m_current;
 222     int   val;
 223
 224     if( current >= m_end )
 225     {
 226         ReadBlock();
 227         current = m_current;
 228     }
 229
 230     val = *((uchar*)current);
 231     m_current = current + 1;
 232     return val;
 233 }
 234
 235
 236 void  RLByteStream::GetBytes( void* buffer, int length, int* readed )
 237 {
 238     uchar*  data = (uchar*)buffer;
 239     assert( length >= 0 );
 240
 241     if( readed) *readed = 0;
 242
 243     while( length > 0 )
 244     {
 245         int l;
 246
 247         for(;;)
 248         {
 249             l = m_end - m_current;
 250             if( l > length ) l = length;
 251             if( l > 0 ) break;
 252             ReadBlock();
 253         }
 254         memcpy( data, m_current, l );
 255         m_current += l;
 256         length -= l;
 257         data += l;
 258         if( readed ) *readed += l;
 259     }
 260 }
 261
 262
 263 ////////////  RLByteStream & RMByteStream <Get[d]word>s ////////////////
 264
 265 int
 266 #ifdef LITTLE_ENDIAN
 267     RLByteStream
 268 #else
 269     RMByteStream
 270 #endif
 271 ::GetWord()
 272 {
 273     uchar *current = m_current;
 274     int   val;
 275
 276     if( current+1 < m_end )
 277     {
 278         val = *((unsigned short*)current);
 279         m_current = current + 2;
 280     }
 281     else
 282     {
 283         val = GetByte();
 284         val|= GetByte() << 8;
 285     }
 286     return val;
 287 }
 288
 289
 290 int
 291 #ifdef BIG_ENDIAN
 292     RLByteStream
 293 #else
 294     RMByteStream
 295 #endif
 296 ::GetWord()
 297 {
 298     uchar *current = m_current;
 299     int   val;
 300
 301     if( current+1 < m_end )
 302     {
 303         val = *((unsigned short*)current);
 304         m_current = current + 2;
 305         val = (val >> 8)|((val & 255) << 8);
 306     }
 307     else
 308     {
 309         val = GetByte() << 8;
 310         val|= GetByte();
 311     }
 312     return val;
 313 }
 314
 315
 316 int
 317 #ifdef LITTLE_ENDIAN
 318     RLByteStream
 319 #else
 320     RMByteStream
 321 #endif
 322 ::GetDWord()
 323 {
 324     uchar *current = m_current;
 325     int   val;
 326
 327     if( current+3 < m_end )
 328     {
 329         val = *((int*)current);
 330         m_current = current + 4;
 331     }
 332     else
 333     {
 334         GetBytes( &val, 4 );
 335     }
 336     return val;
 337 }
 338
 339 int
 340 #ifdef BIG_ENDIAN
 341     RLByteStream
 342 #else
 343     RMByteStream
 344 #endif
 345 ::GetDWord()
 346 {
 347     uchar *current = m_current;
 348     int   val;
 349
 350     if( current+3 < m_end )
 351     {
 352         val = *((int*)current);
 353         m_current = current + 4;
 354     }
 355     else
 356     {
 357         GetBytes( &val, 4 );
 358     }
 359     return BSWAP(val);
 360 }
 361
 362
 363 /////////////////////////  RLBitStream ////////////////////////////
 364
 365 void  RLBitStream::ReadBlock()
 366 {
 367     RBaseStream::ReadBlock();
 368 #ifdef  BIG_ENDIAN
 369     bs_bswap_block( m_start, m_end );
 370 #endif
 371 }
 372
 373
 374 void  RLBitStream::SetPos( int pos )
 375 {
 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;
 380 }
 381
 382
 383 int  RLBitStream::GetPos()
 384 {
 385     return RBaseStream::GetPos() + (m_bit_idx >> 3);
 386 }
 387
 388
 389 int  RLBitStream::Get( int bits )
 390 {
 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;
 395
 396     if( (m_current = (uchar*)(current - mask)) >= m_end )
 397     {
 398         ReadBlock();
 399         current = ((ulong*)m_current) + mask;
 400     }
 401     m_bit_idx = new_bit_idx & 31;
 402     return ((current[0] >> bit_idx) |
 403            ((current[1] <<-bit_idx) & mask)) & bs_bits_masks[bits];
 404 }
 405
 406 int  RLBitStream::Show( int bits )
 407 {
 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;
 412
 413     if( (uchar*)(current - mask) >= m_end )
 414     {
 415         ReadBlock();
 416         current = ((ulong*)m_current) + mask;
 417         m_current = (uchar*)current;
 418     }
 419     return ((current[0] >> bit_idx) |
 420            ((current[1] <<-bit_idx) & mask)) & bs_bits_masks[bits];
 421 }
 422
 423
 424 void  RLBitStream::Move( int shift )
 425 {
 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;
 429 }
 430
 431
 432 int  RLBitStream::GetHuff( const short* table )
 433 {
 434     int  val;
 435     int  code_bits;
 436
 437     for(;;)
 438     {
 439         int table_bits = table[0];
 440         val = table[Show(table_bits) + 2];
 441         code_bits = val & 15;
 442         val >>= 4;
 443
 444         if( code_bits != 0 ) break;
 445         table += val*2;
 446         Move( table_bits );
 447     }
 448
 449     Move( code_bits );
 450     if( val == RBS_HUFF_FORB ) throw RBS_THROW_FORB;
 451
 452     return val;
 453 }
 454
 455 void  RLBitStream::Skip( int bytes )
 456 {
 457     Move( bytes*8 );
 458 }
 459
 460 /////////////////////////  RMBitStream ////////////////////////////
 461
 462 void  RMBitStream::ReadBlock()
 463 {
 464     RBaseStream::ReadBlock();
 465 #ifdef  LITTLE_ENDIAN
 466     bs_bswap_block( m_start, m_end );
 467 #endif
 468 }
 469
 470
 471 void  RMBitStream::SetPos( int pos )
 472 {
 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;
 477 }
 478
 479
 480 int  RMBitStream::GetPos()
 481 {
 482     return RBaseStream::GetPos() + ((32 - m_bit_idx) >> 3);
 483 }
 484
 485
 486 int  RMBitStream::Get( int bits )
 487 {
 488     int    bit_idx = m_bit_idx - bits;
 489     int    mask    = bit_idx >> 31;
 490     ulong* current = ((ulong*)m_current) - mask;
 491
 492     if( (m_current = (uchar*)current) >= m_end )
 493     {
 494         ReadBlock();
 495         current = (ulong*)m_current;
 496     }
 497     m_bit_idx = bit_idx &= 31;
 498     return (((current[-1] << -bit_idx) & mask)|
 499              (current[0] >> bit_idx)) & bs_bits_masks[bits];
 500 }
 501
 502
 503 int  RMBitStream::Show( int bits )
 504 {
 505     int    bit_idx = m_bit_idx - bits;
 506     int    mask    = bit_idx >> 31;
 507     ulong* current = ((ulong*)m_current) - mask;
 508
 509     if( ((uchar*)current) >= m_end )
 510     {
 511         m_current = (uchar*)current;
 512         ReadBlock();
 513         current = (ulong*)m_current;
 514         m_current -= 4;
 515     }
 516     return (((current[-1]<<-bit_idx) & mask)|
 517              (current[0] >> bit_idx)) & bs_bits_masks[bits];
 518 }
 519
 520
 521 int  RMBitStream::GetHuff( const short* table )
 522 {
 523     int  val;
 524     int  code_bits;
 525
 526     for(;;)
 527     {
 528         int table_bits = table[0];
 529         val = table[Show(table_bits) + 1];
 530         code_bits = val & 15;
 531         val >>= 4;
 532
 533         if( code_bits != 0 ) break;
 534         table += val;
 535         Move( table_bits );
 536     }
 537
 538     Move( code_bits );
 539     if( val == RBS_HUFF_FORB )
 540         throw RBS_THROW_FORB;
 541
 542     return val;
 543 }
 544
 545
 546 void  RMBitStream::Move( int shift )
 547 {
 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;
 551 }
 552
 553
 554 void  RMBitStream::Skip( int bytes )
 555 {
 556     Move( bytes*8 );
 557 }
 558
 559
 560 static const int huff_val_shift = 20, huff_code_mask = (1 << huff_val_shift) - 1;
 561
 562 bool bs_create_decode_huffman_table( const int* src, short* table, int max_size )
 563 {
 564     const int forbidden_entry = (RBS_HUFF_FORB << 4)|1;
 565     int       first_bits = src[0];
 566     struct
 567     {
 568         int bits;
 569         int offset;
 570     }
 571     sub_tables[1 << 11];
 572     int  size = (1 << first_bits) + 1;
 573     int  i, k;
 574
 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++ )
 578     {
 579         int code_count = src[k++];
 580         int sb = i - first_bits;
 581
 582         if( sb <= 0 )
 583             k += code_count;
 584         else
 585             for( code_count += k; k < code_count; k++ )
 586             {
 587                 int  code = src[k] & huff_code_mask;
 588                 sub_tables[code >> sb].bits = sb;
 589             }
 590     }
 591
 592     /* calc offsets of sub tables and whole size of table */
 593     for( i = 0; i < (1 << first_bits); i++ )
 594     {
 595         int b = sub_tables[i].bits;
 596         if( b > 0 )
 597         {
 598             b = 1 << b;
 599             sub_tables[i].offset = size;
 600             size += b + 1;
 601         }
 602     }
 603
 604     if( size > max_size )
 605     {
 606         assert(0);
 607         return false;
 608     }
 609
 610     /* fill first table and subtables with forbidden values */
 611     for( i = 0; i < size; i++ )
 612     {
 613         table[i] = (short)forbidden_entry;
 614     }
 615
 616     /* write header of first table */
 617     table[0] = (short)first_bits;
 618
 619     /* fill first table and sub tables */
 620     for( i = 1, k = 1; src[k] >= 0; i++ )
 621     {
 622         int code_count = src[k++];
 623         for( code_count += k; k < code_count; k++ )
 624         {
 625             int  table_bits= first_bits;
 626             int  code_bits = i;
 627             int  code = src[k] & huff_code_mask;
 628             int  val  = src[k] >>huff_val_shift;
 629             int  j, offset = 0;
 630
 631             if( code_bits > table_bits )
 632             {
 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);
 641             }
 642
 643             table_bits -= code_bits;
 644             assert( table_bits >= 0 );
 645             val = (val << 4) | code_bits;
 646             offset += (code << table_bits) + 1;
 647
 648             for( j = 0; j < (1 << table_bits); j++ )
 649             {
 650                 assert( table[offset + j] == forbidden_entry );
 651                 table[ offset + j ] = (short)val;
 652             }
 653         }
 654     }
 655     return true;
 656 }
 657
 658 int*  bs_create_source_huffman_table( const uchar* src, int* dst,
 659                                       int max_bits, int first_bits )
 660 {
 661     int   i, val_idx, code = 0;
 662     int*  table = dst;
 663     *dst++ = first_bits;
 664     for( i = 1, val_idx = max_bits; i <= max_bits; i++ )
 665     {
 666         int code_count = src[i - 1];
 667         dst[0] = code_count;
 668         code <<= 1;
 669         for( int k = 0; k < code_count; k++ )
 670         {
 671             dst[k + 1] = (src[val_idx + k] << huff_val_shift)|(code + k);
 672         }
 673         code += code_count;
 674         dst += code_count + 1;
 675         val_idx += code_count;
 676     }
 677     dst[0] = -1;
 678     return  table;
 679 }