libpgf  6.11.42
PGF - Progressive Graphics File
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Encoder.cpp
Go to the documentation of this file.
1 /*
2  * The Progressive Graphics File; http://www.libpgf.org
3  *
4  * $Date: 2007-02-03 13:04:21 +0100 (Sa, 03 Feb 2007) $
5  * $Revision: 280 $
6  *
7  * This file Copyright (C) 2006 xeraina GmbH, Switzerland
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE
11  * as published by the Free Software Foundation; either version 2.1
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software
21  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22  */
23 
28 
29 #include "Encoder.h"
30 #ifdef TRACE
31  #include <stdio.h>
32 #endif
33 
35 // PGF: file structure
36 //
37 // PGFPreHeader PGFHeader PGFPostHeader LevelLengths Level_n-1 Level_n-2 ... Level_0
38 // PGFPostHeader ::= [ColorTable] [UserData]
39 // LevelLengths ::= UINT32[nLevels]
40 
42 // Encoding scheme
43 // input: wavelet coefficients stored in subbands
44 // output: binary file
45 //
46 // subband
47 // |
48 // m_value [BufferSize]
49 // | | |
50 // m_sign sigBits refBits [BufferSize, BufferLen, BufferLen]
51 // | | |
52 // m_codeBuffer (for each plane: RLcodeLength (16 bit), RLcoded sigBits + m_sign, refBits)
53 // |
54 // file (for each buffer: packedLength (16 bit), packed bits)
55 //
56 
57 // Constants
58 #define CodeBufferBitLen (BufferSize*WordWidth) // max number of bits in m_codeBuffer
59 #define MaxCodeLen ((1 << RLblockSizeLen) - 1) // max length of RL encoded block
60 
62 // Constructor
63 // Write pre-header, header, postHeader, and levelLength.
64 // It might throw an IOException.
65 // preHeader and header must not be references, because on BigEndian platforms they are modified
66 CEncoder::CEncoder(CPGFStream* stream, PGFPreHeader preHeader, PGFHeader header, const PGFPostHeader& postHeader, UINT32*& levelLength, bool useOMP /*= true*/) THROW_
67 : m_stream(stream)
68 , m_startPosition(0)
69 , m_currLevelIndex(0)
70 , m_nLevels(header.nLevels)
71 , m_favorSpeed(false)
72 , m_forceWriting(false)
73 #ifdef __PGFROISUPPORT__
74 , m_roi(false)
75 #endif
76 {
77  ASSERT(m_stream);
78 
79  int count;
80 
81  // set number of threads
82 #ifdef LIBPGF_USE_OPENMP
83  m_macroBlockLen = omp_get_num_procs();
84 #else
85  m_macroBlockLen = 1;
86 #endif
87 
88  if (useOMP && m_macroBlockLen > 1) {
89 #ifdef LIBPGF_USE_OPENMP
90  omp_set_num_threads(m_macroBlockLen);
91 #endif
92  // create macro block array
93  m_macroBlocks = new CMacroBlock*[m_macroBlockLen];
94  for (int i=0; i < m_macroBlockLen; i++) m_macroBlocks[i] = new CMacroBlock(this);
95  m_lastMacroBlock = 0;
96  m_currentBlock = m_macroBlocks[m_lastMacroBlock++];
97  } else {
98  m_macroBlocks = 0;
99  m_macroBlockLen = 1;
100  m_currentBlock = new CMacroBlock(this);
101  }
102 
103  // save file position
104  m_startPosition = m_stream->GetPos();
105 
106  // write preHeader
107  preHeader.hSize = __VAL(preHeader.hSize);
108  count = PreHeaderSize;
109  m_stream->Write(&count, &preHeader);
110 
111  // write file header
112  header.height = __VAL(header.height);
113  header.width = __VAL(header.width);
114  count = HeaderSize;
115  m_stream->Write(&count, &header);
116 
117  // write postHeader
118  if (header.mode == ImageModeIndexedColor) {
119  // write color table
120  count = ColorTableSize;
121  m_stream->Write(&count, (void *)postHeader.clut);
122  }
123  if (postHeader.userData && postHeader.userDataLen) {
124  // write user data
125  count = postHeader.userDataLen;
126  m_stream->Write(&count, postHeader.userData);
127  }
128 
129  // renew levelLength
130  delete[] levelLength;
131  levelLength = new UINT32[m_nLevels];
132  for (UINT8 l = 0; l < m_nLevels; l++) levelLength[l] = 0;
133  m_levelLength = levelLength;
134 
135  // write dummy levelLength
136  m_levelLengthPos = m_stream->GetPos();
137  count = m_nLevels*WordBytes;
138  m_stream->Write(&count, m_levelLength);
139 
140  // save current file position
141  SetBufferStartPos();
142 }
143 
145 // Destructor
147  delete m_currentBlock;
148  delete[] m_macroBlocks;
149 }
150 
161 void CEncoder::Partition(CSubband* band, int width, int height, int startPos, int pitch) THROW_ {
162  ASSERT(band);
163 
164  const div_t hh = div(height, LinBlockSize);
165  const div_t ww = div(width, LinBlockSize);
166  const int ws = pitch - LinBlockSize;
167  const int wr = pitch - ww.rem;
168  int pos, base = startPos, base2;
169 
170  // main height
171  for (int i=0; i < hh.quot; i++) {
172  // main width
173  base2 = base;
174  for (int j=0; j < ww.quot; j++) {
175  pos = base2;
176  for (int y=0; y < LinBlockSize; y++) {
177  for (int x=0; x < LinBlockSize; x++) {
178  WriteValue(band, pos);
179  pos++;
180  }
181  pos += ws;
182  }
183  base2 += LinBlockSize;
184  }
185  // rest of width
186  pos = base2;
187  for (int y=0; y < LinBlockSize; y++) {
188  for (int x=0; x < ww.rem; x++) {
189  WriteValue(band, pos);
190  pos++;
191  }
192  pos += wr;
193  base += pitch;
194  }
195  }
196  // main width
197  base2 = base;
198  for (int j=0; j < ww.quot; j++) {
199  // rest of height
200  pos = base2;
201  for (int y=0; y < hh.rem; y++) {
202  for (int x=0; x < LinBlockSize; x++) {
203  WriteValue(band, pos);
204  pos++;
205  }
206  pos += ws;
207  }
208  base2 += LinBlockSize;
209  }
210  // rest of height
211  pos = base2;
212  for (int y=0; y < hh.rem; y++) {
213  // rest of width
214  for (int x=0; x < ww.rem; x++) {
215  WriteValue(band, pos);
216  pos++;
217  }
218  pos += wr;
219  }
220 }
221 
225 void CEncoder::Flush() THROW_ {
226  // pad buffer with zeros
229 
230  // encode buffer
231  m_forceWriting = true; // makes sure that the following EncodeBuffer is really written into the stream
233 }
234 
239 UINT32 CEncoder::WriteLevelLength() THROW_ {
240  UINT64 curPos = m_stream->GetPos();
241  UINT32 retValue = UINT32(curPos - m_startPosition);
242 
243  if (m_levelLength) {
244  // append levelLength to file, directly after post-header
245  // set file pos to levelLength
246  m_stream->SetPos(FSFromStart, m_levelLengthPos);
247  #ifdef PGF_USE_BIG_ENDIAN
248  UINT32 levelLength;
249  int count = WordBytes;
250 
251  for (int i=0; i < m_currLevelIndex; i++) {
252  levelLength = __VAL(UINT32(m_levelLength[i]));
253  m_stream->Write(&count, &levelLength);
254  }
255  #else
256  int count = m_currLevelIndex*WordBytes;
257 
258  m_stream->Write(&count, m_levelLength);
259  #endif //PGF_USE_BIG_ENDIAN
260 
261  // restore file position
262  m_stream->SetPos(FSFromStart, curPos);
263  }
264 
265  return retValue;
266 }
267 
269 // Stores band value from given position bandPos into buffer m_value at position m_valuePos
270 // If buffer is full encode it to file
271 // It might throw an IOException.
272 void CEncoder::WriteValue(CSubband* band, int bandPos) THROW_ {
273  if (m_currentBlock->m_valuePos == BufferSize) {
274  EncodeBuffer(ROIBlockHeader(BufferSize, false));
275  }
276  DataT val = m_currentBlock->m_value[m_currentBlock->m_valuePos++] = band->GetData(bandPos);
277  UINT32 v = abs(val);
278  if (v > m_currentBlock->m_maxAbsValue) m_currentBlock->m_maxAbsValue = v;
279 }
280 
282 // Encode buffer and write data into stream.
283 // h contains buffer size and flag indicating end of tile.
284 // Encoding scheme: <wordLen>(16 bits) [ ROI ] data
285 // ROI ::= <bufferSize>(15 bits) <eofTile>(1 bit)
286 // It might throw an IOException.
288  ASSERT(m_currentBlock);
289 #ifdef __PGFROISUPPORT__
290  ASSERT(m_roi && h.rbh.bufferSize <= BufferSize || h.rbh.bufferSize == BufferSize);
291 #else
292  ASSERT(h.rbh.bufferSize == BufferSize);
293 #endif
294  m_currentBlock->m_header = h;
295 
296  // macro block management
297  if (m_macroBlockLen == 1) {
298  m_currentBlock->BitplaneEncode();
299  WriteMacroBlock(m_currentBlock);
300  } else {
301  // save last level index
302  int lastLevelIndex = m_currentBlock->m_lastLevelIndex;
303 
304  if (m_forceWriting || m_lastMacroBlock == m_macroBlockLen) {
305  // encode macro blocks
306  /*
307  volatile OSError error = NoError;
308  #pragma omp parallel for ordered default(shared)
309  for (int i=0; i < m_lastMacroBlock; i++) {
310  if (error == NoError) {
311  m_macroBlocks[i]->BitplaneEncode();
312  #pragma omp ordered
313  {
314  try {
315  WriteMacroBlock(m_macroBlocks[i]);
316  } catch (IOException& e) {
317  error = e.error;
318  }
319  delete m_macroBlocks[i]; m_macroBlocks[i] = 0;
320  }
321  }
322  }
323  if (error != NoError) ReturnWithError(error);
324  */
325  #pragma omp parallel for default(shared) //no declared exceptions in next block
326  for (int i=0; i < m_lastMacroBlock; i++) {
327  m_macroBlocks[i]->BitplaneEncode();
328  }
329  for (int i=0; i < m_lastMacroBlock; i++) {
330  WriteMacroBlock(m_macroBlocks[i]);
331  }
332 
333  // prepare for next round
334  m_forceWriting = false;
335  m_lastMacroBlock = 0;
336  }
337  // re-initialize macro block
338  m_currentBlock = m_macroBlocks[m_lastMacroBlock++];
339  m_currentBlock->Init(lastLevelIndex);
340  }
341 }
342 
344 // Write encoded macro block into stream.
345 // It might throw an IOException.
347  ASSERT(block);
348 
349  ROIBlockHeader h = block->m_header;
350  UINT16 wordLen = UINT16(NumberOfWords(block->m_codePos)); ASSERT(wordLen <= BufferSize);
351  int count = sizeof(UINT16);
352 
353 #ifdef TRACE
354  //UINT32 filePos = (UINT32)m_stream->GetPos();
355  //printf("EncodeBuffer: %d\n", filePos);
356 #endif
357 
358 #ifdef PGF_USE_BIG_ENDIAN
359  // write wordLen
360  UINT16 wl = __VAL(wordLen);
361  m_stream->Write(&count, &wl); ASSERT(count == sizeof(UINT16));
362 
363 #ifdef __PGFROISUPPORT__
364  // write ROIBlockHeader
365  if (m_roi) {
366  h.val = __VAL(h.val);
367  m_stream->Write(&count, &h.val); ASSERT(count == sizeof(UINT16));
368  }
369 #endif // __PGFROISUPPORT__
370 
371  // convert data
372  for (int i=0; i < wordLen; i++) {
373  block->m_codeBuffer[i] = __VAL(block->m_codeBuffer[i]);
374  }
375 #else
376  // write wordLen
377  m_stream->Write(&count, &wordLen); ASSERT(count == sizeof(UINT16));
378 
379 #ifdef __PGFROISUPPORT__
380  // write ROIBlockHeader
381  if (m_roi) {
382  m_stream->Write(&count, &h.val); ASSERT(count == sizeof(UINT16));
383  }
384 #endif // __PGFROISUPPORT__
385 #endif // PGF_USE_BIG_ENDIAN
386 
387  // write encoded data into stream
388  count = wordLen*WordBytes;
389  m_stream->Write(&count, block->m_codeBuffer);
390 
391  // store levelLength
392  if (m_levelLength) {
393  // store level length
394  // EncodeBuffer has been called after m_lastLevelIndex has been updated
395  m_levelLength[m_currLevelIndex] += ComputeBufferLength();
396  m_currLevelIndex = block->m_lastLevelIndex + 1;
397 
398  }
399 
400  // prepare for next buffer
401  SetBufferStartPos();
402 
403  // reset values
404  block->m_valuePos = 0;
405  block->m_maxAbsValue = 0;
406 }
407 
409 // Encode buffer of given size using bit plane coding.
410 // A buffer contains bufferLen UINT32 values, thus, bufferSize bits per bit plane.
411 // Following coding scheme is used:
412 // Buffer ::= <nPlanes>(5 bits) foreach(plane i): Plane[i]
413 // Plane[i] ::= [ Sig1 | Sig2 ] [DWORD alignment] refBits
414 // Sig1 ::= 1 <codeLen>(15 bits) codedSigAndSignBits
415 // Sig2 ::= 0 <sigLen>(15 bits) [Sign1 | Sign2 ] [DWORD alignment] sigBits
416 // Sign1 ::= 1 <codeLen>(15 bits) codedSignBits
417 // Sign2 ::= 0 <signLen>(15 bits) [DWORD alignment] signBits
419  UINT8 nPlanes;
420  UINT32 sigLen, codeLen = 0, wordPos, refLen, signLen;
421  UINT32 sigBits[BufferLen] = { 0 };
422  UINT32 refBits[BufferLen] = { 0 };
423  UINT32 signBits[BufferLen] = { 0 };
424  UINT32 planeMask;
425  UINT32 bufferSize = m_header.rbh.bufferSize; ASSERT(bufferSize <= BufferSize);
426  bool useRL;
427 
428 #ifdef TRACE
429  //printf("which thread: %d\n", omp_get_thread_num());
430 #endif
431 
432  // clear significance vector
433  for (UINT32 k=0; k < bufferSize; k++) {
434  m_sigFlagVector[k] = false;
435  }
436  m_sigFlagVector[bufferSize] = true; // sentinel
437 
438  // clear output buffer
439  for (UINT32 k=0; k < bufferSize; k++) {
440  m_codeBuffer[k] = 0;
441  }
442  m_codePos = 0;
443 
444  // compute number of bit planes and split buffer into separate bit planes
445  nPlanes = NumberOfBitplanes();
446 
447  // write number of bit planes to m_codeBuffer
448  // <nPlanes>
451 
452  // loop through all bit planes
453  if (nPlanes == 0) nPlanes = MaxBitPlanes + 1;
454  planeMask = 1 << (nPlanes - 1);
455 
456  for (int plane = nPlanes - 1; plane >= 0; plane--) {
457  // clear significant bitset
458  for (UINT32 k=0; k < BufferLen; k++) {
459  sigBits[k] = 0;
460  }
461 
462  // split bitplane in significant bitset and refinement bitset
463  sigLen = DecomposeBitplane(bufferSize, planeMask, m_codePos + RLblockSizeLen + 1, sigBits, refBits, signBits, signLen, codeLen);
464 
465  if (sigLen > 0 && codeLen <= MaxCodeLen && codeLen < AlignWordPos(sigLen) + AlignWordPos(signLen) + 2*RLblockSizeLen) {
466  // set RL code bit
467  // <1><codeLen>
469 
470  // write length codeLen to m_codeBuffer
472  m_codePos += RLblockSizeLen + codeLen;
473  } else {
474  #ifdef TRACE
475  //printf("new\n");
476  //for (UINT32 i=0; i < bufferSize; i++) {
477  // printf("%s", (GetBit(sigBits, i)) ? "1" : "_");
478  // if (i%120 == 119) printf("\n");
479  //}
480  //printf("\n");
481  #endif // TRACE
482 
483  // run-length coding wasn't efficient enough
484  // we don't use RL coding for sigBits
485  // <0><sigLen>
487 
488  // write length sigLen to m_codeBuffer
489  ASSERT(sigLen <= MaxCodeLen);
492 
493  if (m_encoder->m_favorSpeed || signLen == 0) {
494  useRL = false;
495  } else {
496  // overwrite m_codeBuffer
497  useRL = true;
498  // run-length encode m_sign and append them to the m_codeBuffer
499  codeLen = RLESigns(m_codePos + RLblockSizeLen + 1, signBits, signLen);
500  }
501 
502  if (useRL && codeLen <= MaxCodeLen && codeLen < signLen) {
503  // RL encoding of m_sign was efficient
504  // <1><codeLen><codedSignBits>_
505  // write RL code bit
507 
508  // write codeLen to m_codeBuffer
510 
511  // compute position of sigBits
512  wordPos = NumberOfWords(m_codePos + RLblockSizeLen + codeLen);
513  ASSERT(0 <= wordPos && wordPos < bufferSize);
514  } else {
515  // RL encoding of signBits wasn't efficient
516  // <0><signLen>_<signBits>_
517  // clear RL code bit
519 
520  // write signLen to m_codeBuffer
521  ASSERT(signLen <= MaxCodeLen);
523 
524  // write signBits to m_codeBuffer
526  ASSERT(0 <= wordPos && wordPos < bufferSize);
527  codeLen = NumberOfWords(signLen);
528 
529  for (UINT32 k=0; k < codeLen; k++) {
530  m_codeBuffer[wordPos++] = signBits[k];
531  }
532  }
533 
534  // write sigBits
535  // <sigBits>_
536  ASSERT(0 <= wordPos && wordPos < bufferSize);
537  refLen = NumberOfWords(sigLen);
538 
539  for (UINT32 k=0; k < refLen; k++) {
540  m_codeBuffer[wordPos++] = sigBits[k];
541  }
542  m_codePos = wordPos << WordWidthLog;
543  }
544 
545  // append refinement bitset (aligned to word boundary)
546  // _<refBits>
547  wordPos = NumberOfWords(m_codePos);
548  ASSERT(0 <= wordPos && wordPos < bufferSize);
549  refLen = NumberOfWords(bufferSize - sigLen);
550 
551  for (UINT32 k=0; k < refLen; k++) {
552  m_codeBuffer[wordPos++] = refBits[k];
553  }
554  m_codePos = wordPos << WordWidthLog;
555  planeMask >>= 1;
556  }
557  ASSERT(0 <= m_codePos && m_codePos <= CodeBufferBitLen);
558 }
559 
561 // Split bitplane of length bufferSize into significant and refinement bitset
562 // returns length [bits] of significant bits
563 // input: bufferSize, planeMask, codePos
564 // output: sigBits, refBits, signBits, signLen [bits], codeLen [bits]
565 // RLE
566 // - Encode run of 2^k zeros by a single 0.
567 // - Encode run of count 0's followed by a 1 with codeword: 1<count>x
568 // - x is 0: if a positive sign is stored, otherwise 1
569 // - Store each bit in m_codeBuffer[codePos] and increment codePos.
570 UINT32 CEncoder::CMacroBlock::DecomposeBitplane(UINT32 bufferSize, UINT32 planeMask, UINT32 codePos, UINT32* sigBits, UINT32* refBits, UINT32* signBits, UINT32& signLen, UINT32& codeLen) {
571  ASSERT(sigBits);
572  ASSERT(refBits);
573  ASSERT(signBits);
574  ASSERT(codePos < CodeBufferBitLen);
575 
576  UINT32 sigPos = 0;
577  UINT32 valuePos = 0, valueEnd;
578  UINT32 refPos = 0;
579 
580  // set output value
581  signLen = 0;
582 
583  // prepare RLE of Sigs and Signs
584  const UINT32 outStartPos = codePos;
585  UINT32 k = 3;
586  UINT32 runlen = 1 << k; // = 2^k
587  UINT32 count = 0;
588 
589  while (valuePos < bufferSize) {
590  // search next 1 in m_sigFlagVector using searching with sentinel
591  valueEnd = valuePos;
592  while(!m_sigFlagVector[valueEnd]) { valueEnd++; }
593 
594  // search 1's in m_value[plane][valuePos..valueEnd)
595  // these 1's are significant bits
596  while (valuePos < valueEnd) {
597  if (GetBitAtPos(valuePos, planeMask)) {
598  // RLE encoding
599  // encode run of count 0's followed by a 1
600  // with codeword: 1<count>(signBits[signPos])
601  SetBit(m_codeBuffer, codePos++);
602  if (k > 0) {
603  SetValueBlock(m_codeBuffer, codePos, count, k);
604  codePos += k;
605 
606  // adapt k (half the zero run-length)
607  k--;
608  runlen >>= 1;
609  }
610 
611  // copy and write sign bit
612  if (m_value[valuePos] < 0) {
613  SetBit(signBits, signLen++);
614  SetBit(m_codeBuffer, codePos++);
615  } else {
616  ClearBit(signBits, signLen++);
617  ClearBit(m_codeBuffer, codePos++);
618  }
619 
620  // write a 1 to sigBits
621  SetBit(sigBits, sigPos++);
622 
623  // update m_sigFlagVector
624  m_sigFlagVector[valuePos] = true;
625 
626  // prepare for next run
627  count = 0;
628  } else {
629  // RLE encoding
630  count++;
631  if (count == runlen) {
632  // encode run of 2^k zeros by a single 0
633  ClearBit(m_codeBuffer, codePos++);
634  // adapt k (double the zero run-length)
635  if (k < WordWidth) {
636  k++;
637  runlen <<= 1;
638  }
639 
640  // prepare for next run
641  count = 0;
642  }
643 
644  // write 0 to sigBits
645  sigPos++;
646  }
647  valuePos++;
648  }
649  // refinement bit
650  if (valuePos < bufferSize) {
651  // write one refinement bit
652  if (GetBitAtPos(valuePos++, planeMask)) {
653  SetBit(refBits, refPos);
654  } else {
655  ClearBit(refBits, refPos);
656  }
657  refPos++;
658  }
659  }
660  // RLE encoding of the rest of the plane
661  // encode run of count 0's followed by a 1
662  // with codeword: 1<count>(signBits[signPos])
663  SetBit(m_codeBuffer, codePos++);
664  if (k > 0) {
665  SetValueBlock(m_codeBuffer, codePos, count, k);
666  codePos += k;
667  }
668  // write dmmy sign bit
669  SetBit(m_codeBuffer, codePos++);
670 
671  // write word filler zeros
672 
673  ASSERT(sigPos <= bufferSize);
674  ASSERT(refPos <= bufferSize);
675  ASSERT(signLen <= bufferSize);
676  ASSERT(valuePos == bufferSize);
677  ASSERT(codePos >= outStartPos && codePos < CodeBufferBitLen);
678  codeLen = codePos - outStartPos;
679 
680  return sigPos;
681 }
682 
683 
685 // Compute number of bit planes needed
687  UINT8 cnt = 0;
688 
689  // determine number of bitplanes for max value
690  if (m_maxAbsValue > 0) {
691  while (m_maxAbsValue > 0) {
692  m_maxAbsValue >>= 1; cnt++;
693  }
694  if (cnt == MaxBitPlanes + 1) cnt = 0;
695  // end cs
696  ASSERT(cnt <= MaxBitPlanes);
697  ASSERT((cnt >> MaxBitPlanesLog) == 0);
698  return cnt;
699  } else {
700  return 1;
701  }
702 }
703 
705 // Adaptive Run-Length encoder for long sequences of ones.
706 // Returns length of output in bits.
707 // - Encode run of 2^k ones by a single 1.
708 // - Encode run of count 1's followed by a 0 with codeword: 0<count>.
709 // - Store each bit in m_codeBuffer[codePos] and increment codePos.
710 UINT32 CEncoder::CMacroBlock::RLESigns(UINT32 codePos, UINT32* signBits, UINT32 signLen) {
711  ASSERT(signBits);
712  ASSERT(0 <= codePos && codePos < CodeBufferBitLen);
713  ASSERT(0 < signLen && signLen <= BufferSize);
714 
715  const UINT32 outStartPos = codePos;
716  UINT32 k = 0;
717  UINT32 runlen = 1 << k; // = 2^k
718  UINT32 count = 0;
719  UINT32 signPos = 0;
720 
721  while (signPos < signLen) {
722  // search next 0 in signBits starting at position signPos
723  count = SeekBit1Range(signBits, signPos, __min(runlen, signLen - signPos));
724  // count 1's found
725  if (count == runlen) {
726  // encode run of 2^k ones by a single 1
727  signPos += count;
728  SetBit(m_codeBuffer, codePos++);
729  // adapt k (double the 1's run-length)
730  if (k < WordWidth) {
731  k++;
732  runlen <<= 1;
733  }
734  } else {
735  // encode run of count 1's followed by a 0
736  // with codeword: 0(count)
737  signPos += count + 1;
738  ClearBit(m_codeBuffer, codePos++);
739  if (k > 0) {
740  SetValueBlock(m_codeBuffer, codePos, count, k);
741  codePos += k;
742  }
743  // adapt k (half the 1's run-length)
744  if (k > 0) {
745  k--;
746  runlen >>= 1;
747  }
748  }
749  }
750  ASSERT(signPos == signLen || signPos == signLen + 1);
751  ASSERT(codePos >= outStartPos && codePos < CodeBufferBitLen);
752  return codePos - outStartPos;
753 }
754 
756 #ifdef TRACE
757 void CEncoder::DumpBuffer() const {
758  //printf("\nDump\n");
759  //for (UINT32 i=0; i < BufferSize; i++) {
760  // printf("%d", m_value[i]);
761  //}
762  //printf("\n");
763 }
764 #endif //TRACE
765 
766