Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

zinflate.cpp

00001 // zinflate.cpp - written and placed in the public domain by Wei Dai
00002 
00003 // This is a complete reimplementation of the DEFLATE decompression algorithm.
00004 // It should not be affected by any security vulnerabilities in the zlib 
00005 // compression library. In particular it is not affected by the double free bug
00006 // (http://www.kb.cert.org/vuls/id/368819).
00007 
00008 #include "pch.h"
00009 #include "zinflate.h"
00010 
00011 NAMESPACE_BEGIN(CryptoPP)
00012 
00013 struct CodeLessThan
00014 {
00015         inline bool operator()(const CryptoPP::HuffmanDecoder::code_t lhs, const CryptoPP::HuffmanDecoder::CodeInfo &rhs)
00016                 {return lhs < rhs.code;}
00017 };
00018 
00019 inline bool LowFirstBitReader::FillBuffer(unsigned int length)
00020 {
00021         while (m_bitsBuffered < length)
00022         {
00023                 byte b;
00024                 if (!m_store.Get(b))
00025                         return false;
00026                 m_buffer |= (unsigned long)b << m_bitsBuffered;
00027                 m_bitsBuffered += 8;
00028         }
00029         assert(m_bitsBuffered <= sizeof(unsigned long)*8);
00030         return true;
00031 }
00032 
00033 inline unsigned long LowFirstBitReader::PeekBits(unsigned int length)
00034 {
00035         bool result = FillBuffer(length);
00036         assert(result);
00037         return m_buffer & (((unsigned long)1 << length) - 1);
00038 }
00039 
00040 inline void LowFirstBitReader::SkipBits(unsigned int length)
00041 {
00042         assert(m_bitsBuffered >= length);
00043         m_buffer >>= length;
00044         m_bitsBuffered -= length;
00045 }
00046 
00047 inline unsigned long LowFirstBitReader::GetBits(unsigned int length)
00048 {
00049         unsigned long result = PeekBits(length);
00050         SkipBits(length);
00051         return result;
00052 }
00053 
00054 inline HuffmanDecoder::code_t HuffmanDecoder::NormalizeCode(HuffmanDecoder::code_t code, unsigned int codeBits)
00055 {
00056         return code << (MAX_CODE_BITS - codeBits);
00057 }
00058 
00059 void HuffmanDecoder::Initialize(const unsigned int *codeBits, unsigned int nCodes)
00060 {
00061         // the Huffman codes are represented in 3 ways in this code:
00062         //
00063         // 1. most significant code bit (i.e. top of code tree) in the least significant bit position
00064         // 2. most significant code bit (i.e. top of code tree) in the most significant bit position
00065         // 3. most significant code bit (i.e. top of code tree) in n-th least significant bit position,
00066         //    where n is the maximum code length for this code tree
00067         //
00068         // (1) is the way the codes come in from the deflate stream
00069         // (2) is used to sort codes so they can be binary searched
00070         // (3) is used in this function to compute codes from code lengths
00071         //
00072         // a code in representation (2) is called "normalized" here
00073         // The BitReverse() function is used to convert between (1) and (2)
00074         // The NormalizeCode() function is used to convert from (3) to (2)
00075 
00076         if (nCodes == 0)
00077                 throw Err("null code");
00078 
00079         m_maxCodeBits = *std::max_element(codeBits, codeBits+nCodes);
00080 
00081         if (m_maxCodeBits > MAX_CODE_BITS)
00082                 throw Err("code length exceeds maximum");
00083 
00084         if (m_maxCodeBits == 0)
00085                 throw Err("null code");
00086 
00087         // count number of codes of each length
00088         SecBlockWithHint<unsigned int, 15+1> blCount(m_maxCodeBits+1);
00089         std::fill(blCount.begin(), blCount.end(), 0);
00090         unsigned int i;
00091         for (i=0; i<nCodes; i++)
00092                 blCount[codeBits[i]]++;
00093 
00094         // compute the starting code of each length
00095         code_t code = 0;
00096         SecBlockWithHint<code_t, 15+1> nextCode(m_maxCodeBits+1);
00097         nextCode[1] = 0;
00098         for (i=2; i<=m_maxCodeBits; i++)
00099         {
00100                 // compute this while checking for overflow: code = (code + blCount[i-1]) << 1
00101                 if (code > code + blCount[i-1])
00102                         throw Err("codes oversubscribed");
00103                 code += blCount[i-1];
00104                 if (code > (code << 1))
00105                         throw Err("codes oversubscribed");
00106                 code <<= 1;
00107                 nextCode[i] = code;
00108         }
00109 
00110         if (code > (1 << m_maxCodeBits) - blCount[m_maxCodeBits])
00111                 throw Err("codes oversubscribed");
00112         else if (m_maxCodeBits != 1 && code < (1 << m_maxCodeBits) - blCount[m_maxCodeBits])
00113                 throw Err("codes incomplete");
00114 
00115         // compute a vector of <code, length, value> triples sorted by code
00116         m_codeToValue.resize(nCodes - blCount[0]);
00117         unsigned int j=0;
00118         for (i=0; i<nCodes; i++) 
00119         {
00120                 unsigned int len = codeBits[i];
00121                 if (len != 0)
00122                 {
00123                         code = NormalizeCode(nextCode[len]++, len);
00124                         m_codeToValue[j].code = code;
00125                         m_codeToValue[j].len = len;
00126                         m_codeToValue[j].value = i;
00127                         j++;
00128                 }
00129         }
00130         std::sort(m_codeToValue.begin(), m_codeToValue.end());
00131 
00132         // initialize the decoding cache
00133         m_cacheBits = STDMIN(9U, m_maxCodeBits);
00134         m_cacheMask = (1 << m_cacheBits) - 1;
00135         m_normalizedCacheMask = NormalizeCode(m_cacheMask, m_cacheBits);
00136         assert(m_normalizedCacheMask == BitReverse(m_cacheMask));
00137 
00138         if (m_cache.size() != 1 << m_cacheBits)
00139                 m_cache.resize(1 << m_cacheBits);
00140 
00141         for (i=0; i<m_cache.size(); i++)
00142                 m_cache[i].type = 0;
00143 }
00144 
00145 void HuffmanDecoder::FillCacheEntry(LookupEntry &entry, code_t normalizedCode) const
00146 {
00147         normalizedCode &= m_normalizedCacheMask;
00148         const CodeInfo &codeInfo = *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode, CodeLessThan())-1);
00149         if (codeInfo.len <= m_cacheBits)
00150         {
00151                 entry.type = 1;
00152                 entry.value = codeInfo.value;
00153                 entry.len = codeInfo.len;
00154         }
00155         else
00156         {
00157                 entry.begin = &codeInfo;
00158                 const CodeInfo *last = & *(std::upper_bound(m_codeToValue.begin(), m_codeToValue.end(), normalizedCode + ~m_normalizedCacheMask, CodeLessThan())-1);
00159                 if (codeInfo.len == last->len)
00160                 {
00161                         entry.type = 2;
00162                         entry.len = codeInfo.len;
00163                 }
00164                 else
00165                 {
00166                         entry.type = 3;
00167                         entry.end = last+1;
00168                 }
00169         }
00170 }
00171 
00172 inline unsigned int HuffmanDecoder::Decode(code_t code, /* out */ value_t &value) const
00173 {
00174         assert(m_codeToValue.size() > 0);
00175         LookupEntry &entry = m_cache[code & m_cacheMask];
00176 
00177         code_t normalizedCode;
00178         if (entry.type != 1)
00179                 normalizedCode = BitReverse(code);
00180 
00181         if (entry.type == 0)
00182                 FillCacheEntry(entry, normalizedCode);
00183 
00184         if (entry.type == 1)
00185         {
00186                 value = entry.value;
00187                 return entry.len;
00188         }
00189         else
00190         {
00191                 const CodeInfo &codeInfo = (entry.type == 2)
00192                         ? entry.begin[(normalizedCode << m_cacheBits) >> (MAX_CODE_BITS - (entry.len - m_cacheBits))]
00193                         : *(std::upper_bound(entry.begin, entry.end, normalizedCode, CodeLessThan())-1);
00194                 value = codeInfo.value;
00195                 return codeInfo.len;
00196         }
00197 }
00198 
00199 bool HuffmanDecoder::Decode(LowFirstBitReader &reader, value_t &value) const
00200 {
00201         reader.FillBuffer(m_maxCodeBits);
00202         unsigned int codeBits = Decode(reader.PeekBuffer(), value);
00203         if (codeBits > reader.BitsBuffered())
00204                 return false;
00205         reader.SkipBits(codeBits);
00206         return true;
00207 }
00208 
00209 // *************************************************************
00210 
00211 Inflator::Inflator(BufferedTransformation *attachment, bool repeat, int propagation)
00212         : AutoSignaling<Filter>(propagation)
00213         , m_state(PRE_STREAM), m_repeat(repeat), m_reader(m_inQueue)
00214 {
00215         Detach(attachment);
00216 }
00217 
00218 void Inflator::IsolatedInitialize(const NameValuePairs &parameters)
00219 {
00220         m_state = PRE_STREAM;
00221         parameters.GetValue("Repeat", m_repeat);
00222         m_inQueue.Clear();
00223         m_reader.SkipBits(m_reader.BitsBuffered());
00224 }
00225 
00226 void Inflator::OutputByte(byte b)
00227 {
00228         m_window[m_current++] = b;
00229         if (m_current == m_window.size())
00230         {
00231                 ProcessDecompressedData(m_window + m_lastFlush, m_window.size() - m_lastFlush);
00232                 m_lastFlush = 0;
00233                 m_current = 0;
00234                 m_wrappedAround = true;
00235         }
00236 }
00237 
00238 void Inflator::OutputString(const byte *string, unsigned int length)
00239 {
00240         while (length)
00241         {
00242                 unsigned int len = STDMIN(length, (unsigned int)(m_window.size() - m_current));
00243                 memcpy(m_window + m_current, string, len);
00244                 m_current += len;
00245                 if (m_current == m_window.size())
00246                 {
00247                         ProcessDecompressedData(m_window + m_lastFlush, m_window.size() - m_lastFlush);
00248                         m_lastFlush = 0;
00249                         m_current = 0;
00250                         m_wrappedAround = true;
00251                 }
00252                 string += len;
00253                 length -= len;
00254         }               
00255 }
00256 
00257 void Inflator::OutputPast(unsigned int length, unsigned int distance)
00258 {
00259         unsigned int start;
00260         if (distance <= m_current)
00261                 start = m_current - distance;
00262         else if (m_wrappedAround && distance <= m_window.size())
00263                 start = m_current + m_window.size() - distance;
00264         else
00265                 throw BadBlockErr();
00266 
00267         if (start + length > m_window.size())
00268         {
00269                 for (; start < m_window.size(); start++, length--)
00270                         OutputByte(m_window[start]);
00271                 start = 0;
00272         }
00273 
00274         if (start + length > m_current || m_current + length >= m_window.size())
00275         {
00276                 while (length--)
00277                         OutputByte(m_window[start++]);
00278         }
00279         else
00280         {
00281                 memcpy(m_window + m_current, m_window + start, length);
00282                 m_current += length;
00283         }
00284 }
00285 
00286 unsigned int Inflator::Put2(const byte *inString, unsigned int length, int messageEnd, bool blocking)
00287 {
00288         if (!blocking)
00289                 throw BlockingInputOnly("Inflator");
00290 
00291         LazyPutter lp(m_inQueue, inString, length);
00292         ProcessInput(messageEnd != 0);
00293 
00294         if (messageEnd)
00295                 if (!(m_state == PRE_STREAM || m_state == AFTER_END))
00296                         throw UnexpectedEndErr();
00297 
00298         Output(0, NULL, 0, messageEnd, blocking);
00299         return 0;
00300 }
00301 
00302 bool Inflator::IsolatedFlush(bool hardFlush, bool blocking)
00303 {
00304         if (!blocking)
00305                 throw BlockingInputOnly("Inflator");
00306 
00307         if (hardFlush)
00308                 ProcessInput(true);
00309         FlushOutput();
00310 
00311         return false;
00312 }
00313 
00314 void Inflator::ProcessInput(bool flush)
00315 {
00316         while (true)
00317         {
00318                 switch (m_state)
00319                 {
00320                 case PRE_STREAM:
00321                         if (!flush && m_inQueue.CurrentSize() < MaxPrestreamHeaderSize())
00322                                 return;
00323                         ProcessPrestreamHeader();
00324                         m_state = WAIT_HEADER;
00325                         m_wrappedAround = false;
00326                         m_current = 0;
00327                         m_lastFlush = 0;
00328                         m_window.New(1 << GetLog2WindowSize());
00329                         break;
00330                 case WAIT_HEADER:
00331                         {
00332                         // maximum number of bytes before actual compressed data starts
00333                         const unsigned int MAX_HEADER_SIZE = BitsToBytes(3+5+5+4+19*7+286*15+19*15);
00334                         if (m_inQueue.CurrentSize() < (flush ? 1 : MAX_HEADER_SIZE))
00335                                 return;
00336                         DecodeHeader();
00337                         break;
00338                         }
00339                 case DECODING_BODY:
00340                         if (!DecodeBody())
00341                                 return;
00342                         break;
00343                 case POST_STREAM:
00344                         if (!flush && m_inQueue.CurrentSize() < MaxPoststreamTailSize())
00345                                 return;
00346                         ProcessPoststreamTail();
00347                         m_state = m_repeat ? PRE_STREAM : AFTER_END;
00348                         Output(0, NULL, 0, GetAutoSignalPropagation(), true);   // TODO: non-blocking
00349                         if (m_inQueue.IsEmpty())
00350                                 return;
00351                         break;
00352                 case AFTER_END:
00353                         m_inQueue.TransferTo(*AttachedTransformation());
00354                         return;
00355                 }
00356         }
00357 }
00358 
00359 void Inflator::DecodeHeader()
00360 {
00361         if (!m_reader.FillBuffer(3))
00362                 throw UnexpectedEndErr();
00363         m_eof = m_reader.GetBits(1) != 0;
00364         m_blockType = (byte)m_reader.GetBits(2);
00365         switch (m_blockType)
00366         {
00367         case 0: // stored
00368                 {
00369                 m_reader.SkipBits(m_reader.BitsBuffered() % 8);
00370                 if (!m_reader.FillBuffer(32))
00371                         throw UnexpectedEndErr();
00372                 m_storedLen = (word16)m_reader.GetBits(16);
00373                 word16 nlen = (word16)m_reader.GetBits(16);
00374                 if (nlen != (word16)~m_storedLen)
00375                         throw BadBlockErr();
00376                 break;
00377                 }
00378         case 1: // fixed codes
00379                 m_nextDecode = LITERAL;
00380                 break;
00381         case 2: // dynamic codes
00382                 {
00383                 if (!m_reader.FillBuffer(5+5+4))
00384                         throw UnexpectedEndErr();
00385                 unsigned int hlit = m_reader.GetBits(5);
00386                 unsigned int hdist = m_reader.GetBits(5);
00387                 unsigned int hclen = m_reader.GetBits(4);
00388 
00389                 FixedSizeSecBlock<unsigned int, 286+32> codeLengths;
00390                 unsigned int i;
00391                 static const unsigned int border[] = {    // Order of the bit length code lengths
00392                         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
00393                 std::fill(codeLengths.begin(), codeLengths+19, 0);
00394                 for (i=0; i<hclen+4; i++)
00395                         codeLengths[border[i]] = m_reader.GetBits(3);
00396 
00397                 try
00398                 {
00399                         HuffmanDecoder codeLengthDecoder(codeLengths, 19);
00400                         for (i = 0; i < hlit+257+hdist+1; )
00401                         {
00402                                 unsigned int k, count, repeater;
00403                                 bool result = codeLengthDecoder.Decode(m_reader, k);
00404                                 if (!result)
00405                                         throw UnexpectedEndErr();
00406                                 if (k <= 15)
00407                                 {
00408                                         count = 1;
00409                                         repeater = k;
00410                                 }
00411                                 else switch (k)
00412                                 {
00413                                 case 16:
00414                                         if (!m_reader.FillBuffer(2))
00415                                                 throw UnexpectedEndErr();
00416                                         count = 3 + m_reader.GetBits(2);
00417                                         if (i == 0)
00418                                                 throw BadBlockErr();
00419                                         repeater = codeLengths[i-1];
00420                                         break;
00421                                 case 17:
00422                                         if (!m_reader.FillBuffer(3))
00423                                                 throw UnexpectedEndErr();
00424                                         count = 3 + m_reader.GetBits(3);
00425                                         repeater = 0;
00426                                         break;
00427                                 case 18:
00428                                         if (!m_reader.FillBuffer(7))
00429                                                 throw UnexpectedEndErr();
00430                                         count = 11 + m_reader.GetBits(7);
00431                                         repeater = 0;
00432                                         break;
00433                                 }
00434                                 if (i + count > hlit+257+hdist+1)
00435                                         throw BadBlockErr();
00436                                 std::fill(codeLengths + i, codeLengths + i + count, repeater);
00437                                 i += count;
00438                         }
00439                         m_dynamicLiteralDecoder.Initialize(codeLengths, hlit+257);
00440                         if (hdist == 0 && codeLengths[hlit+257] == 0)
00441                         {
00442                                 if (hlit != 0)  // a single zero distance code length means all literals
00443                                         throw BadBlockErr();
00444                         }
00445                         else
00446                                 m_dynamicDistanceDecoder.Initialize(codeLengths+hlit+257, hdist+1);
00447                         m_nextDecode = LITERAL;
00448                 }
00449                 catch (HuffmanDecoder::Err &)
00450                 {
00451                         throw BadBlockErr();
00452                 }
00453                 break;
00454                 }
00455         default:
00456                 throw BadBlockErr();    // reserved block type
00457         }
00458         m_state = DECODING_BODY;
00459 }
00460 
00461 bool Inflator::DecodeBody()
00462 {
00463         bool blockEnd = false;
00464         switch (m_blockType)
00465         {
00466         case 0: // stored
00467                 assert(m_reader.BitsBuffered() == 0);
00468                 while (!m_inQueue.IsEmpty() && !blockEnd)
00469                 {
00470                         unsigned int size;
00471                         const byte *block = m_inQueue.Spy(size);
00472                         size = STDMIN(size, (unsigned int)m_storedLen);
00473                         OutputString(block, size);
00474                         m_inQueue.Skip(size);
00475                         m_storedLen -= size;
00476                         if (m_storedLen == 0)
00477                                 blockEnd = true;
00478                 }
00479                 break;
00480         case 1: // fixed codes
00481         case 2: // dynamic codes
00482                 static const unsigned int lengthStarts[] = {
00483                         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
00484                         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
00485                 static const unsigned int lengthExtraBits[] = {
00486                         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
00487                         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
00488                 static const unsigned int distanceStarts[] = {
00489                         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
00490                         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
00491                         8193, 12289, 16385, 24577};
00492                 static const unsigned int distanceExtraBits[] = {
00493                         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
00494                         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
00495                         12, 12, 13, 13};
00496 
00497                 const HuffmanDecoder& literalDecoder = GetLiteralDecoder();
00498                 const HuffmanDecoder& distanceDecoder = GetDistanceDecoder();
00499 
00500                 switch (m_nextDecode)
00501                 {
00502                 case LITERAL:
00503                         while (true)
00504                         {
00505                                 if (!literalDecoder.Decode(m_reader, m_literal))
00506                                 {
00507                                         m_nextDecode = LITERAL;
00508                                         break;
00509                                 }
00510                                 if (m_literal < 256)
00511                                         OutputByte((byte)m_literal);
00512                                 else if (m_literal == 256)      // end of block
00513                                 {
00514                                         blockEnd = true;
00515                                         break;
00516                                 }
00517                                 else
00518                                 {
00519                                         if (m_literal > 285)
00520                                                 throw BadBlockErr();
00521                                         unsigned int bits;
00522                 case LENGTH_BITS:
00523                                         bits = lengthExtraBits[m_literal-257];
00524                                         if (!m_reader.FillBuffer(bits))
00525                                         {
00526                                                 m_nextDecode = LENGTH_BITS;
00527                                                 break;
00528                                         }
00529                                         m_literal = m_reader.GetBits(bits) + lengthStarts[m_literal-257];
00530                 case DISTANCE:
00531                                         if (!distanceDecoder.Decode(m_reader, m_distance))
00532                                         {
00533                                                 m_nextDecode = DISTANCE;
00534                                                 break;
00535                                         }
00536                 case DISTANCE_BITS:
00537                                         bits = distanceExtraBits[m_distance];
00538                                         if (!m_reader.FillBuffer(bits))
00539                                         {
00540                                                 m_nextDecode = DISTANCE_BITS;
00541                                                 break;
00542                                         }
00543                                         m_distance = m_reader.GetBits(bits) + distanceStarts[m_distance];
00544                                         OutputPast(m_literal, m_distance);
00545                                 }
00546                         }
00547                 }
00548         }
00549         if (blockEnd)
00550         {
00551                 if (m_eof)
00552                 {
00553                         FlushOutput();
00554                         m_reader.SkipBits(m_reader.BitsBuffered()%8);
00555                         if (m_reader.BitsBuffered())
00556                         {
00557                                 // undo too much lookahead
00558                                 SecBlockWithHint<byte, 4> buffer(m_reader.BitsBuffered() / 8);
00559                                 for (unsigned int i=0; i<buffer.size(); i++)
00560                                         buffer[i] = (byte)m_reader.GetBits(8);
00561                                 m_inQueue.Unget(buffer, buffer.size());
00562                         }
00563                         m_state = POST_STREAM;
00564                 }
00565                 else
00566                         m_state = WAIT_HEADER;
00567         }
00568         return blockEnd;
00569 }
00570 
00571 void Inflator::FlushOutput()
00572 {
00573         if (m_state != PRE_STREAM)
00574         {
00575                 assert(m_current >= m_lastFlush);
00576                 ProcessDecompressedData(m_window + m_lastFlush, m_current - m_lastFlush);
00577                 m_lastFlush = m_current;
00578         }
00579 }
00580 
00581 struct NewFixedLiteralDecoder
00582 {
00583         HuffmanDecoder * operator()() const
00584         {
00585                 unsigned int codeLengths[288];
00586                 std::fill(codeLengths + 0, codeLengths + 144, 8);
00587                 std::fill(codeLengths + 144, codeLengths + 256, 9);
00588                 std::fill(codeLengths + 256, codeLengths + 280, 7);
00589                 std::fill(codeLengths + 280, codeLengths + 288, 8);
00590                 std::auto_ptr<HuffmanDecoder> pDecoder(new HuffmanDecoder);
00591                 pDecoder->Initialize(codeLengths, 288);
00592                 return pDecoder.release();
00593         }
00594 };
00595 
00596 struct NewFixedDistanceDecoder
00597 {
00598         HuffmanDecoder * operator()() const
00599         {
00600                 unsigned int codeLengths[32];
00601                 std::fill(codeLengths + 0, codeLengths + 32, 5);
00602                 std::auto_ptr<HuffmanDecoder> pDecoder(new HuffmanDecoder);
00603                 pDecoder->Initialize(codeLengths, 32);
00604                 return pDecoder.release();
00605         }
00606 };
00607 
00608 const HuffmanDecoder& Inflator::GetLiteralDecoder() const
00609 {
00610         return m_blockType == 1 ? Singleton<HuffmanDecoder, NewFixedLiteralDecoder>().Ref() : m_dynamicLiteralDecoder;
00611 }
00612 
00613 const HuffmanDecoder& Inflator::GetDistanceDecoder() const
00614 {
00615         return m_blockType == 1 ? Singleton<HuffmanDecoder, NewFixedDistanceDecoder>().Ref() : m_dynamicDistanceDecoder;
00616 }
00617 
00618 NAMESPACE_END

Generated on Thu Oct 28 03:02:12 2004 for Crypto++ by  doxygen 1.3.9.1