CPP/7zip/Compress/ArjDecoder1.cpp

   1 // ArjDecoder1.cpp\r
   2 \r
   3 #include "StdAfx.h"\r
   4 \r
   5 #include "ArjDecoder1.h"\r
   6 \r
   7 namespace NCompress{\r
   8 namespace NArj {\r
   9 namespace NDecoder1 {\r
  10 \r
  11 static const UInt32 kHistorySize = 26624;\r
  12 static const UInt32 kMatchMinLen = 3;\r
  13 static const UInt32 kMatchMaxLen = 256;\r
  14 \r
  15 // static const UInt32 kNC = 255 + kMatchMaxLen + 2 - kMatchMinLen;\r
  16 \r
  17 void CCoder::MakeTable(int nchar, Byte *bitlen, int tablebits,\r
  18     UInt32 *table, int tablesize)\r
  19 {\r
  20   UInt32 count[17], weight[17], start[18], *p;\r
  21   UInt32 i, k, len, ch, jutbits, avail, nextcode, mask;\r
  22   \r
  23   for (i = 1; i <= 16; i++)\r
  24     count[i] = 0;\r
  25   for (i = 0; (int)i < nchar; i++)\r
  26     count[bitlen[i]]++;\r
  27   \r
  28   start[1] = 0;\r
  29   for (i = 1; i <= 16; i++)\r
  30     start[i + 1] = start[i] + (count[i] << (16 - i));\r
  31   if (start[17] != (UInt32) (1 << 16))\r
  32     throw "Data error";\r
  33   \r
  34   jutbits = 16 - tablebits;\r
  35   for (i = 1; (int)i <= tablebits; i++)\r
  36   {\r
  37     start[i] >>= jutbits;\r
  38     weight[i] = 1 << (tablebits - i);\r
  39   }\r
  40   while (i <= 16)\r
  41   {\r
  42     weight[i] = 1 << (16 - i);\r
  43     i++;\r
  44   }\r
  45   \r
  46   i = start[tablebits + 1] >> jutbits;\r
  47   if (i != (UInt32) (1 << 16))\r
  48   {\r
  49     k = 1 << tablebits;\r
  50     while (i != k)\r
  51       table[i++] = 0;\r
  52   }\r
  53   \r
  54   avail = nchar;\r
  55   mask = 1 << (15 - tablebits);\r
  56   for (ch = 0; (int)ch < nchar; ch++)\r
  57   {\r
  58     if ((len = bitlen[ch]) == 0)\r
  59       continue;\r
  60     k = start[len];\r
  61     nextcode = k + weight[len];\r
  62     if ((int)len <= tablebits)\r
  63     {\r
  64       if (nextcode > (UInt32)tablesize)\r
  65         throw "Data error";\r
  66       for (i = start[len]; i < nextcode; i++)\r
  67         table[i] = ch;\r
  68     }\r
  69     else\r
  70     {\r
  71       p = &table[k >> jutbits];\r
  72       i = len - tablebits;\r
  73       while (i != 0)\r
  74       {\r
  75         if (*p == 0)\r
  76         {\r
  77           right[avail] = left[avail] = 0;\r
  78           *p = avail++;\r
  79         }\r
  80         if (k & mask)\r
  81           p = &right[*p];\r
  82         else\r
  83           p = &left[*p];\r
  84         k <<= 1;\r
  85         i--;\r
  86       }\r
  87       *p = ch;\r
  88     }\r
  89     start[len] = nextcode;\r
  90   }\r
  91 }\r
  92 \r
  93 void CCoder::read_pt_len(int nn, int nbit, int i_special)\r
  94 {\r
  95   UInt32 n = m_InBitStream.ReadBits(nbit);\r
  96   if (n == 0)\r
  97   {\r
  98     UInt32 c = m_InBitStream.ReadBits(nbit);\r
  99     int i;\r
 100     for (i = 0; i < nn; i++)\r
 101       pt_len[i] = 0;\r
 102     for (i = 0; i < 256; i++)\r
 103       pt_table[i] = c;\r
 104   }\r
 105   else\r
 106   {\r
 107     UInt32 i = 0;\r
 108     while (i < n)\r
 109     {\r
 110       UInt32 bitBuf = m_InBitStream.GetValue(16);\r
 111       int c = bitBuf >> 13;\r
 112       if (c == 7)\r
 113       {\r
 114         UInt32 mask = 1 << (12);\r
 115         while (mask & bitBuf)\r
 116         {\r
 117           mask >>= 1;\r
 118           c++;\r
 119         }\r
 120       }\r
 121       m_InBitStream.MovePos((c < 7) ? 3 : (int)(c - 3));\r
 122       pt_len[i++] = (Byte)c;\r
 123       if (i == (UInt32)i_special)\r
 124       {\r
 125         c = m_InBitStream.ReadBits(2);\r
 126         while (--c >= 0)\r
 127           pt_len[i++] = 0;\r
 128       }\r
 129     }\r
 130     while (i < (UInt32)nn)\r
 131       pt_len[i++] = 0;\r
 132     MakeTable(nn, pt_len, 8, pt_table, PTABLESIZE);\r
 133   }\r
 134 }\r
 135 \r
 136 void CCoder::read_c_len()\r
 137 {\r
 138   int i, c, n;\r
 139   UInt32 mask;\r
 140   \r
 141   n = m_InBitStream.ReadBits(CBIT);\r
 142   if (n == 0)\r
 143   {\r
 144     c = m_InBitStream.ReadBits(CBIT);\r
 145     for (i = 0; i < NC; i++)\r
 146       c_len[i] = 0;\r
 147     for (i = 0; i < CTABLESIZE; i++)\r
 148       c_table[i] = c;\r
 149   }\r
 150   else\r
 151   {\r
 152     i = 0;\r
 153     while (i < n)\r
 154     {\r
 155       UInt32 bitBuf = m_InBitStream.GetValue(16);\r
 156       c = pt_table[bitBuf >> (8)];\r
 157       if (c >= NT)\r
 158       {\r
 159         mask = 1 << (7);\r
 160         do\r
 161         {\r
 162           if (bitBuf & mask)\r
 163             c = right[c];\r
 164           else\r
 165             c = left[c];\r
 166           mask >>= 1;\r
 167         } while (c >= NT);\r
 168       }\r
 169       m_InBitStream.MovePos((int)(pt_len[c]));\r
 170       if (c <= 2)\r
 171       {\r
 172         if (c == 0)\r
 173           c = 1;\r
 174         else if (c == 1)\r
 175           c = m_InBitStream.ReadBits(4) + 3;\r
 176         else\r
 177           c = m_InBitStream.ReadBits(CBIT) + 20;\r
 178         while (--c >= 0)\r
 179           c_len[i++] = 0;\r
 180       }\r
 181       else\r
 182         c_len[i++] = (Byte)(c - 2);\r
 183     }\r
 184     while (i < NC)\r
 185       c_len[i++] = 0;\r
 186     MakeTable(NC, c_len, 12, c_table, CTABLESIZE);\r
 187   }\r
 188 }\r
 189 \r
 190 UInt32 CCoder::decode_c()\r
 191 {\r
 192   UInt32 j, mask;\r
 193   UInt32 bitbuf = m_InBitStream.GetValue(16);\r
 194   j = c_table[bitbuf >> 4];\r
 195   if (j >= NC)\r
 196   {\r
 197     mask = 1 << (3);\r
 198     do\r
 199     {\r
 200       if (bitbuf & mask)\r
 201         j = right[j];\r
 202       else\r
 203         j = left[j];\r
 204       mask >>= 1;\r
 205     } while (j >= NC);\r
 206   }\r
 207   m_InBitStream.MovePos((int)(c_len[j]));\r
 208   return j;\r
 209 }\r
 210 \r
 211 UInt32 CCoder::decode_p()\r
 212 {\r
 213   UInt32 j, mask;\r
 214   UInt32 bitbuf = m_InBitStream.GetValue(16);\r
 215   j = pt_table[bitbuf >> (8)];\r
 216   if (j >= NP)\r
 217   {\r
 218     mask = 1 << (7);\r
 219     do\r
 220     {\r
 221       if (bitbuf & mask)\r
 222         j = right[j];\r
 223       else\r
 224         j = left[j];\r
 225       mask >>= 1;\r
 226     } while (j >= NP);\r
 227   }\r
 228   m_InBitStream.MovePos((int)(pt_len[j]));\r
 229   if (j != 0)\r
 230   {\r
 231     j--;\r
 232     j = (1 << j) + m_InBitStream.ReadBits((int)j);\r
 233   }\r
 234   return j;\r
 235 }\r
 236 \r
 237 \r
 238 HRESULT CCoder::CodeReal(ISequentialInStream *inStream, ISequentialOutStream *outStream,\r
 239     const UInt64 * /* inSize */, const UInt64 *outSize, ICompressProgressInfo *progress)\r
 240 {\r
 241   if (outSize == NULL)\r
 242     return E_INVALIDARG;\r
 243 \r
 244   if (!m_OutWindowStream.Create(kHistorySize))\r
 245     return E_OUTOFMEMORY;\r
 246   if (!m_InBitStream.Create(1 << 20))\r
 247     return E_OUTOFMEMORY;\r
 248 \r
 249   // check it\r
 250   for (int i = 0; i < CTABLESIZE; i++)\r
 251     c_table[i] = 0;\r
 252 \r
 253   UInt64 pos = 0;\r
 254   m_OutWindowStream.SetStream(outStream);\r
 255   m_OutWindowStream.Init(false);\r
 256   m_InBitStream.SetStream(inStream);\r
 257   m_InBitStream.Init();\r
 258   \r
 259   CCoderReleaser coderReleaser(this);\r
 260 \r
 261   UInt32 blockSize = 0;\r
 262 \r
 263   while(pos < *outSize)\r
 264   {\r
 265     if (blockSize == 0)\r
 266     {\r
 267       if (progress != NULL)\r
 268       {\r
 269         UInt64 packSize = m_InBitStream.GetProcessedSize();\r
 270         RINOK(progress->SetRatioInfo(&packSize, &pos));\r
 271       }\r
 272       blockSize = m_InBitStream.ReadBits(16);\r
 273       read_pt_len(NT, TBIT, 3);\r
 274       read_c_len();\r
 275       read_pt_len(NP, PBIT, -1);\r
 276     }\r
 277     blockSize--;\r
 278 \r
 279     UInt32 number = decode_c();\r
 280     if (number < 256)\r
 281     {\r
 282       m_OutWindowStream.PutByte((Byte)number);\r
 283       pos++;\r
 284       continue;\r
 285     }\r
 286     else\r
 287     {\r
 288       UInt32 len = number - 256 + kMatchMinLen;\r
 289       UInt32 distance = decode_p();\r
 290       if (distance >= pos)\r
 291         return S_FALSE;\r
 292       m_OutWindowStream.CopyBlock(distance, len);\r
 293         pos += len;\r
 294     }\r
 295   }\r
 296   coderReleaser.NeedFlush = false;\r
 297   return m_OutWindowStream.Flush();\r
 298 }\r
 299 \r
 300 STDMETHODIMP CCoder::Code(ISequentialInStream *inStream, ISequentialOutStream *outStream,\r
 301     const UInt64 *inSize, const UInt64 *outSize, ICompressProgressInfo *progress)\r
 302 {\r
 303   try { return CodeReal(inStream, outStream, inSize, outSize, progress);}\r
 304   catch(const CInBufferException &e) { return e.ErrorCode; }\r
 305   catch(const CLzOutWindowException &e) { return e.ErrorCode; }\r
 306   catch(...) { return S_FALSE; }\r
 307 }\r
 308 \r
 309 }}}\r