Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Huffman algo -> decompression


Hurraa - Mo 09.02.09 14:49
Titel: Huffman algo -> decompression
Hallo.
Ich denke einige von euch werden den Huffman algorithmus kennen und grob wissen was er macht etc. RunUO (wenn ihr dieses Programm kennt) kompirmiert seine Pakete und schickt sie dann über das Netzwerk. Jedoch möchte ich diese Pakete wieder dekompirmieren... Das RunUO programm macht folgendes:


C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
 
    public unsafe static byte[] Compress( byte[] input, int offset, int count, ref int length ) {
      if ( input == null ) {
        throw new ArgumentNullException( "input" );
      } else if ( offset < 0 || offset >= input.Length ) {
        throw new ArgumentOutOfRangeException( "offset" );
      } else if ( count < 0 || count > input.Length ) {
        throw new ArgumentOutOfRangeException( "count" );
      } else if ( ( input.Length - offset ) < count ) {
        throw new ArgumentException();
      }

      length = 0;

      if ( count > DefiniteOverflow ) {
        return null;
      }

      lock ( _syncRoot ) {
        int bitCount = 0;
        int bitValue = 0;

        fixed ( int* pTable = _huffmanTable ) {
          int* pEntry;

          fixed ( byte* pInputBuffer = input ) {
            byte* pInput = pInputBuffer + offset, pInputEnd = pInput + count;

            fixed ( byte* pOutputBuffer = _outputBuffer ) {
              byte* pOutput = pOutputBuffer, pOutputEnd = pOutput + BufferSize;

              while ( pInput < pInputEnd ) {
                pEntry = &pTable[*pInput++ << 1];

                bitCount += pEntry[CountIndex];

                bitValue <<= pEntry[CountIndex];
                bitValue |= pEntry[ValueIndex];

                while ( bitCount >= 8 ) {
                  bitCount -= 8;

                  if ( pOutput < pOutputEnd ) {
                    *pOutput++ = ( byte ) ( bitValue >> bitCount );
                  } else {
                    return null;
                  }
                }
              }

              // terminal code
              pEntry = &pTable[0x200];

              bitCount += pEntry[CountIndex];

              bitValue <<= pEntry[CountIndex];
              bitValue |= pEntry[ValueIndex];

              // align on byte boundary
              if ( ( bitCount & 7 ) != 0 ) {
                bitValue <<= ( 8 - ( bitCount & 7 ) );
                bitCount += ( 8 - ( bitCount & 7 ) );
              }

              while ( bitCount >= 8 ) {
                bitCount -= 8;

                if ( pOutput < pOutputEnd ) {
                  *pOutput++ = ( byte ) ( bitValue >> bitCount );
                } else {
                  return null;
                }
              }

              length = ( int ) ( pOutput - pOutputBuffer );
              return _outputBuffer;
            }
          }
        }
      }
    }


RunUO hat dafür einen HuffmanTable erstellt der folgender Maßen aussieht:

C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
 
    private static int[] _huffmanTable = new int[514]
    {
      0x2, 0x000,  0x5, 0x01F,  0x6, 0x022,  0x7, 0x034,  0x7, 0x075,  0x6, 0x028,  0x6, 0x03B,  0x7, 0x032,
      0x8, 0x0E0,  0x8, 0x062,  0x7, 0x056,  0x8, 0x079,  0x9, 0x19D,  0x8, 0x097,  0x6, 0x02A,  0x7, 0x057,
      0x8, 0x071,  0x8, 0x05B,  0x9, 0x1CC,  0x8, 0x0A7,  0x7, 0x025,  0x7, 0x04F,  0x8, 0x066,  0x8, 0x07D,
      0x9, 0x191,  0x9, 0x1CE,  0x7, 0x03F,  0x9, 0x090,  0x8, 0x059,  0x8, 0x07B,  0x8, 0x091,  0x8, 0x0C6,
      0x6, 0x02D,  0x9, 0x186,  0x8, 0x06F,  0x9, 0x093,  0xA, 0x1CC,  0x8, 0x05A,  0xA, 0x1AE,  0xA, 0x1C0,
      0x9, 0x148,  0x9, 0x14A,  0x9, 0x082,  0xA, 0x19F,  0x9, 0x171,  0x9, 0x120,  0x9, 0x0E7,  0xA, 0x1F3,
      0x9, 0x14B,  0x9, 0x100,  0x9, 0x190,  0x6, 0x013,  0x9, 0x161,  0x9, 0x125,  0x9, 0x133,  0x9, 0x195,
      0x9, 0x173,  0x9, 0x1CA,  0x9, 0x086,  0x9, 0x1E9,  0x9, 0x0DB,  0x9, 0x1EC,  0x9, 0x08B,  0x9, 0x085,
      0x5, 0x00A,  0x8, 0x096,  0x8, 0x09C,  0x9, 0x1C3,  0x9, 0x19C,  0x9, 0x08F,  0x9, 0x18F,  0x9, 0x091,
      0x9, 0x087,  0x9, 0x0C6,  0x9, 0x177,  0x9, 0x089,  0x9, 0x0D6,  0x9, 0x08C,  0x9, 0x1EE,  0x9, 0x1EB,
      0x9, 0x084,  0x9, 0x164,  0x9, 0x175,  0x9, 0x1CD,  0x8, 0x05E,  0x9, 0x088,  0x9, 0x12B,  0x9, 0x172,
      0x9, 0x10A,  0x9, 0x08D,  0x9, 0x13A,  0x9, 0x11C,  0xA, 0x1E1,  0xA, 0x1E0,  0x9, 0x187,  0xA, 0x1DC,
      0xA, 0x1DF,  0x7, 0x074,  0x9, 0x19F,  0x8, 0x08D,  0x8, 0x0E4,  0x7, 0x079,  0x9, 0x0EA,  0x9, 0x0E1,
      0x8, 0x040,  0x7, 0x041,  0x9, 0x10B,  0x9, 0x0B0,  0x8, 0x06A,  0x8, 0x0C1,  0x7, 0x071,  0x7, 0x078,
      0x8, 0x0B1,  0x9, 0x14C,  0x7, 0x043,  0x8, 0x076,  0x7, 0x066,  0x7, 0x04D,  0x9, 0x08A,  0x6, 0x02F,
      0x8, 0x0C9,  0x9, 0x0CE,  0x9, 0x149,  0x9, 0x160,  0xA, 0x1BA,  0xA, 0x19E,  0xA, 0x39F,  0x9, 0x0E5,
      0x9, 0x194,  0x9, 0x184,  0x9, 0x126,  0x7, 0x030,  0x8, 0x06C,  0x9, 0x121,  0x9, 0x1E8,  0xA, 0x1C1,
      0xA, 0x11D,  0xA, 0x163,  0xA, 0x385,  0xA, 0x3DB,  0xA, 0x17D,  0xA, 0x106,  0xA, 0x397,  0xA, 0x24E,
      0x7, 0x02E,  0x8, 0x098,  0xA, 0x33C,  0xA, 0x32E,  0xA, 0x1E9,  0x9, 0x0BF,  0xA, 0x3DF,  0xA, 0x1DD,
      0xA, 0x32D,  0xA, 0x2ED,  0xA, 0x30B,  0xA, 0x107,  0xA, 0x2E8,  0xA, 0x3DE,  0xA, 0x125,  0xA, 0x1E8,
      0x9, 0x0E9,  0xA, 0x1CD,  0xA, 0x1B5,  0x9, 0x165,  0xA, 0x232,  0xA, 0x2E1,  0xB, 0x3AE,  0xB, 0x3C6,
      0xB, 0x3E2,  0xA, 0x205,  0xA, 0x29A,  0xA, 0x248,  0xA, 0x2CD,  0xA, 0x23B,  0xB, 0x3C5,  0xA, 0x251,
      0xA, 0x2E9,  0xA, 0x252,  0x9, 0x1EA,  0xB, 0x3A0,  0xB, 0x391,  0xA, 0x23C,  0xB, 0x392,  0xB, 0x3D5,
      0xA, 0x233,  0xA, 0x2CC,  0xB, 0x390,  0xA, 0x1BB,  0xB, 0x3A1,  0xB, 0x3C4,  0xA, 0x211,  0xA, 0x203,
      0x9, 0x12A,  0xA, 0x231,  0xB, 0x3E0,  0xA, 0x29B,  0xB, 0x3D7,  0xA, 0x202,  0xB, 0x3AD,  0xA, 0x213,
      0xA, 0x253,  0xA, 0x32C,  0xA, 0x23D,  0xA, 0x23F,  0xA, 0x32F,  0xA, 0x11C,  0xA, 0x384,  0xA, 0x31C,
      0xA, 0x17C,  0xA, 0x30A,  0xA, 0x2E0,  0xA, 0x276,  0xA, 0x250,  0xB, 0x3E3,  0xA, 0x396,  0xA, 0x18F,
      0xA, 0x204,  0xA, 0x206,  0xA, 0x230,  0xA, 0x265,  0xA, 0x212,  0xA, 0x23E,  0xB, 0x3AC,  0xB, 0x393,
      0xB, 0x3E1,  0xA, 0x1DE,  0xB, 0x3D6,  0xA, 0x31D,  0xB, 0x3E5,  0xB, 0x3E4,  0xA, 0x207,  0xB, 0x3C7,
      0xA, 0x277,  0xB, 0x3D4,  0x8, 0x0C0,  0xA, 0x162,  0xA, 0x3DA,  0xA, 0x124,  0xA, 0x1B4,  0xA, 0x264,
      0xA, 0x33D,  0xA, 0x1D1,  0xA, 0x1AF,  0xA, 0x39E,  0xA, 0x24F,  0xB, 0x373,  0xA, 0x249,  0xB, 0x372,
      0x9, 0x167,  0xA, 0x210,  0xA, 0x23A,  0xA, 0x1B8,  0xB, 0x3AF,  0xA, 0x18E,  0xA, 0x2EC,  0x7, 0x062,
      0x4, 0x00D
    };


Ich habe nun c++ code gefunden der GENAU diese Daten dekomprimiert:


C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
 
void DecompressingCopier::operator () (char * dest, const char * src,
    int & dest_size, int & src_size)
{
    unsigned char * pdest = reinterpret_cast<unsigned char *>(dest);
    const unsigned char * src2 = reinterpret_cast<const unsigned char *>(src);
    const unsigned char * psrc = src2;
    int len = src_size; // len will decrease
    int dest_index = 0;

    while(true)
    {
        if(bit_num == 8)
        {
            // End of input.
            if(len == 0)
            {
                dest_size = dest_index;
                // src_size is unchanged
                return;
            }
            len--;
            value = *psrc++;
            bit_num = 0;
            mask = 0x80;
        }
        if(value & mask)
            treepos = tree[treepos * 2];
        else
            treepos = tree[treepos * 2 + 1];
        mask >>= 1; // shift on reck
        bit_num++;

        if(treepos <= 0) // this is a leaf.
        {
            if(treepos == -256) // special flush character
            {
                bit_num = 8; // flush rest of byte
                treepos = 0; // start on tree top again
                continue;
            }
            if(dest_index == dest_size) // Buffer full
            {
                dest_size = dest_index;
                src_size = psrc - src2;
                return;
            }
            pdest[dest_index++] = -treepos;   // data is negative value
            treepos = 0;      // start on tree top again
        }
    }
}


Dafür gibt es auch einen komplementären c++ huffmantable:

C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
 
int DecompressingCopier::tree[] =
{
    /*   0*/     1, 2,
    /*   1*/     3, 4,
    /*   2*/     5, 0,
    /*   3*/     6, 7,
    /*   4*/     8, 9,
    /*   5*/    10,   11,
    /*   6*/    12,   13,
    /*   7*/  -256,   14,
    /*   8*/    15,   16,
    /*   9*/    17,   18,
    /*  10*/    19,   20,
    /*  11*/    21,   22,
    /*  12*/    -1,   23,
    /*  13*/    24,   25,
    /*  14*/    26,   27,
    /*  15*/    28,   29,
    /*  16*/    30,   31,
    /*  17*/    32,   33,
    /*  18*/    34,   35,
    /*  19*/    36,   37,
    /*  20*/    38,   39,
    /*  21*/    40,  -64,
    /*  22*/    41,   42,
    /*  23*/    43,   44,
    /*  24*/    -6,   45,
    /*  25*/    46,   47,
    /*  26*/    48,   49,
    /*  27*/    50,   51,
    /*  28*/  -119,   52,
    /*  29*/   -32,   53,
    /*  30*/    54,  -14,
    /*  31*/    55,   -5,
    /*  32*/    56,   57,
    /*  33*/    58,   59,
    /*  34*/    60,   -2,
    /*  35*/    61,   62,
    /*  36*/    63,   64,
    /*  37*/    65,   66,
    /*  38*/    67,   68,
    /*  39*/    69,   70,
    /*  40*/    71,   72,
    /*  41*/   -51,   73,
    /*  42*/    74,   75,
    /*  43*/    76,   77,
    /*  44*/  -101, -111,
    /*  45*/    -4,  -97,
    /*  46*/    78,   79,
    /*  47*/  -110,   80,
    /*  48*/    81, -116,
    /*  49*/    82,   83,
    /*  50*/    84, -255,
    /*  51*/    85,   86,
    /*  52*/    87,   88,
    /*  53*/    89,   90,
    /*  54*/   -15,  -10,
    /*  55*/    91,   92,
    /*  56*/   -21,   93,
    /*  57*/  -117,   94,
    /*  58*/    95,   96,
    /*  59*/    97,   98,
    /*  60*/    99,  100,
    /*  61*/  -114,  101,
    /*  62*/  -105,  102,
    /*  63*/   -26,  103,
    /*  64*/   104,  105,
    /*  65*/   106,  107,
    /*  66*/   108,  109,
    /*  67*/   110,  111,
    /*  68*/   112,   -3,
    /*  69*/   113,   -7,
    /*  70*/   114, -131,
    /*  71*/   115, -144,
    /*  72*/   116,  117,
    /*  73*/   -20,  118,
    /*  74*/   119,  120,
    /*  75*/   121,  122,
    /*  76*/   123,  124,
    /*  77*/   125,  126,
    /*  78*/   127,  128,
    /*  79*/   129, -100 ,
    /*  80*/   130,   -8,
    /*  81*/   131,  132,
    /*  82*/   133,  134,
    /*  83*/  -120,  135,
    /*  84*/   136,  -31,
    /*  85*/   137,  138,
    /*  86*/  -109, -234,
    /*  87*/   139,  140,
    /*  88*/   141,  142,
    /*  89*/   143,  144,
    /*  90*/  -112,  145,
    /*  91*/   -19,  146,
    /*  92*/   147,  148,
    /*  93*/   149,  -66,
    /*  94*/   150, -145,
    /*  95*/   -13,  -65,
    /*  96*/   151,  152,
    /*  97*/   153,  154,
    /*  98*/   -30,  155,
    /*  99*/   156,  157,
    /* 100*/   -99,  158,
    /* 101*/   159,  160,
    /* 102*/   161,  162,
    /* 103*/   -23,  163,
    /* 104*/   -29,  164,
    /* 105*/   -11,  165,
    /* 106*/   166, -115,
    /* 107*/   167,  168,
    /* 108*/   169,  170,
    /* 109*/   -16,  171,
    /* 110*/   -34,  172,
    /* 111*/   173, -132,
    /* 112*/   174, -108,
    /* 113*/   175,  -22,
    /* 114*/   176,   -9,
    /* 115*/   177,  -84,
    /* 116*/   -17,  -37,
    /* 117*/   -28,  178,
    /* 118*/   179,  180,
    /* 119*/   181,  182,
    /* 120*/   183,  184,
    /* 121*/   185,  186,
    /* 122*/   187, -104,
    /* 123*/   188,  -78,
    /* 124*/   189,  -61,
    /* 125*/   -79, -178,
    /* 126*/   -59, -134,
    /* 127*/   190,  -25,
    /* 128*/   -83,  -18,
    /* 129*/   191,  -57,
    /* 130*/   -67,  192,
    /* 131*/   -98,  193,
    /* 132*/   -12,  -68,
    /* 133*/   194,  195,
    /* 134*/   -55, -128,
    /* 135*/   -24,  -50,
    /* 136*/   -70,  196,
    /* 137*/   -94,  -33,
    /* 138*/   197, -129,
    /* 139*/   -74,  198,
    /* 140*/   -82,  199,
    /* 141*/   -56,  -87,
    /* 142*/   -44,  200,
    /* 143*/  -248,  201,
    /* 144*/  -163,  -81,
    /* 145*/   -52, -123,
    /* 146*/   202, -113,
    /* 147*/   -48,  -41,
    /* 148*/  -122,  -40,
    /* 149*/   203,  -90,
    /* 150*/   -54,  204,
    /* 151*/   -86, -192,
    /* 152*/   205,  206,
    /* 153*/   207, -130,
    /* 154*/   -53,  208,
    /* 155*/  -133,  -45,
    /* 156*/   209,  210,
    /* 157*/   211,  -91,
    /* 158*/   212,  213,
    /* 159*/  -106,  -88,
    /* 160*/   214,  215,
    /* 161*/   216,  217,
    /* 162*/   218,  -49,
    /* 163*/   219,  220,
    /* 164*/   221,  222,
    /* 165*/   223,  224,
    /* 166*/   225,  226,
    /* 167*/   227, -102,
    /* 168*/  -160,  228,
    /* 169*/   -46,  229,
    /* 170*/  -127,  230,
    /* 171*/  -103,  231,
    /* 172*/   232,  233,
    /* 173*/   -60,  234,
    /* 174*/   235,  -76,
    /* 175*/   236, -121,
    /* 176*/   237,  -73,
    /* 177*/  -149,  238,
    /* 178*/   239, -107,
    /* 179*/   -35,  240,
    /* 180*/   -71,  -27,
    /* 181*/   -69,  241,
    /* 182*/   -89,  -77,
    /* 183*/   -62, -118,
    /* 184*/   -75,  -85,
    /* 185*/   -72,  -58,
    /* 186*/   -63,  -80,
    /* 187*/   242,  -42,
    /* 188*/  -150, -157,
    /* 189*/  -139, -236,
    /* 190*/  -126, -243,
    /* 191*/  -142, -214,
    /* 192*/  -138, -206,
    /* 193*/  -240, -146,
    /* 194*/  -204, -147,
    /* 195*/  -152, -201,
    /* 196*/  -227, -207,
    /* 197*/  -154, -209,
    /* 198*/  -153, -254,
    /* 199*/  -176, -156,
    /* 200*/  -165, -210,
    /* 201*/  -172, -185,
    /* 202*/  -195, -170,
    /* 203*/  -232, -211,
    /* 204*/  -219, -239,
    /* 205*/  -200, -177,
    /* 206*/  -175, -212,
    /* 207*/  -244, -143,
    /* 208*/  -246, -171,
    /* 209*/  -203, -221,
    /* 210*/  -202, -181,
    /* 211*/  -173, -250,
    /* 212*/  -184, -164,
    /* 213*/  -193, -218,
    /* 214*/  -199, -220,
    /* 215*/  -190, -249,
    /* 216*/  -230, -217,
    /* 217*/  -169, -216,
    /* 218*/  -191, -197,
    /* 219*/   -47,  243,
    /* 220*/   244,  245,
    /* 221*/   246,  247,
    /* 222*/  -148, -159,
    /* 223*/   248,  249,
    /* 224*/   -92,  -93,
    /* 225*/   -96, -225,
    /* 226*/  -151,  -95,
    /* 227*/   250,  251,
    /* 228*/  -241,  252,
    /* 229*/  -161,  -36,
    /* 230*/   253,  254,
    /* 231*/  -135,  -39,
    /* 232*/  -187, -124,
    /* 233*/   255, -251,
    /* 234*/  -162, -238,
    /* 235*/  -242,  -38,
    /* 236*/   -43, -125,
    /* 237*/  -215, -253,
    /* 238*/  -140, -208,
    /* 239*/  -137, -235,
    /* 240*/  -158, -237,
    /* 241*/  -136, -205,
    /* 242*/  -155, -141,
    /* 243*/  -228, -229,
    /* 244*/  -213, -168,
    /* 245*/  -224, -194,
    /* 246*/  -196, -226,
    /* 247*/  -183, -233,
    /* 248*/  -231, -167,
    /* 249*/  -174, -189,
    /* 250*/  -252, -166,
    /* 251*/  -198, -222,
    /* 252*/  -188, -179,
    /* 253*/  -223, -182,
    /* 254*/  -180, -186,
    /* 255*/  -245, -247,
};


Meine Frage ist: Wie kann ich den C++ code in C# umwandeln? Ich habe schon einige Versuche gestartet, jedoch funktionieren diese nicht richtig...

Hier mein Versuch:


C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        //diese bytes sind verpackt
        static byte[] _crypt = new byte[] { 179, 36, 206, 79, 64 };

        //diese unverpackt
        static byte[] _real = new byte[] { 185, 130, 223 };

        //der huffmantable wird zum entschlüsseln verwendet...
        private static readonly short[] _duffmanTable = new short[]
        {
            /*   0*/     1, 2,
            /*   1*/     3, 4,
            /*   2*/     5, 0,
            /*   3*/     6, 7,
            /*   4*/     8, 9,
            /*   5*/    10,   11,
            /*   6*/    12,   13,
            /*   7*/  -256,   14,
            /*   8*/    15,   16,
            /*   9*/    17,   18,
            /*  10*/    19,   20,
            /*  11*/    21,   22,
            /*  12*/    -1,   23,
            /*  13*/    24,   25,
            /*  14*/    26,   27,
            /*  15*/    28,   29,
            /*  16*/    30,   31,
            /*  17*/    32,   33,
            /*  18*/    34,   35,
            /*  19*/    36,   37,
            /*  20*/    38,   39,
            /*  21*/    40,  -64,
            /*  22*/    41,   42,
            /*  23*/    43,   44,
            /*  24*/    -6,   45,
            /*  25*/    46,   47,
            /*  26*/    48,   49,
            /*  27*/    50,   51,
            /*  28*/  -119,   52,
            /*  29*/   -32,   53,
            /*  30*/    54,  -14,
            /*  31*/    55,   -5,
            /*  32*/    56,   57,
            /*  33*/    58,   59,
            /*  34*/    60,   -2,
            /*  35*/    61,   62,
            /*  36*/    63,   64,
            /*  37*/    65,   66,
            /*  38*/    67,   68,
            /*  39*/    69,   70,
            /*  40*/    71,   72,
            /*  41*/   -51,   73,
            /*  42*/    74,   75,
            /*  43*/    76,   77,
            /*  44*/  -101, -111,
            /*  45*/    -4,  -97,
            /*  46*/    78,   79,
            /*  47*/  -110,   80,
            /*  48*/    81, -116,
            /*  49*/    82,   83,
            /*  50*/    84, -255,
            /*  51*/    85,   86,
            /*  52*/    87,   88,
            /*  53*/    89,   90,
            /*  54*/   -15,  -10,
            /*  55*/    91,   92,
            /*  56*/   -21,   93,
            /*  57*/  -117,   94,
            /*  58*/    95,   96,
            /*  59*/    97,   98,
            /*  60*/    99,  100,
            /*  61*/  -114,  101,
            /*  62*/  -105,  102,
            /*  63*/   -26,  103,
            /*  64*/   104,  105,
            /*  65*/   106,  107,
            /*  66*/   108,  109,
            /*  67*/   110,  111,
            /*  68*/   112,   -3,
            /*  69*/   113,   -7,
            /*  70*/   114, -131,
            /*  71*/   115, -144,
            /*  72*/   116,  117,
            /*  73*/   -20,  118,
            /*  74*/   119,  120,
            /*  75*/   121,  122,
            /*  76*/   123,  124,
            /*  77*/   125,  126,
            /*  78*/   127,  128,
            /*  79*/   129, -100 ,
            /*  80*/   130,   -8,
            /*  81*/   131,  132,
            /*  82*/   133,  134,
            /*  83*/  -120,  135,
            /*  84*/   136,  -31,
            /*  85*/   137,  138,
            /*  86*/  -109, -234,
            /*  87*/   139,  140,
            /*  88*/   141,  142,
            /*  89*/   143,  144,
            /*  90*/  -112,  145,
            /*  91*/   -19,  146,
            /*  92*/   147,  148,
            /*  93*/   149,  -66,
            /*  94*/   150, -145,
            /*  95*/   -13,  -65,
            /*  96*/   151,  152,
            /*  97*/   153,  154,
            /*  98*/   -30,  155,
            /*  99*/   156,  157,
            /* 100*/   -99,  158,
            /* 101*/   159,  160,
            /* 102*/   161,  162,
            /* 103*/   -23,  163,
            /* 104*/   -29,  164,
            /* 105*/   -11,  165,
            /* 106*/   166, -115,
            /* 107*/   167,  168,
            /* 108*/   169,  170,
            /* 109*/   -16,  171,
            /* 110*/   -34,  172,
            /* 111*/   173, -132,
            /* 112*/   174, -108,
            /* 113*/   175,  -22,
            /* 114*/   176,   -9,
            /* 115*/   177,  -84,
            /* 116*/   -17,  -37,
            /* 117*/   -28,  178,
            /* 118*/   179,  180,
            /* 119*/   181,  182,
            /* 120*/   183,  184,
            /* 121*/   185,  186,
            /* 122*/   187, -104,
            /* 123*/   188,  -78,
            /* 124*/   189,  -61,
            /* 125*/   -79, -178,
            /* 126*/   -59, -134,
            /* 127*/   190,  -25,
            /* 128*/   -83,  -18,
            /* 129*/   191,  -57,
            /* 130*/   -67,  192,
            /* 131*/   -98,  193,
            /* 132*/   -12,  -68,
            /* 133*/   194,  195,
            /* 134*/   -55, -128,
            /* 135*/   -24,  -50,
            /* 136*/   -70,  196,
            /* 137*/   -94,  -33,
            /* 138*/   197, -129,
            /* 139*/   -74,  198,
            /* 140*/   -82,  199,
            /* 141*/   -56,  -87,
            /* 142*/   -44,  200,
            /* 143*/  -248,  201,
            /* 144*/  -163,  -81,
            /* 145*/   -52, -123,
            /* 146*/   202, -113,
            /* 147*/   -48,  -41,
            /* 148*/  -122,  -40,
            /* 149*/   203,  -90,
            /* 150*/   -54,  204,
            /* 151*/   -86, -192,
            /* 152*/   205,  206,
            /* 153*/   207, -130,
            /* 154*/   -53,  208,
            /* 155*/  -133,  -45,
            /* 156*/   209,  210,
            /* 157*/   211,  -91,
            /* 158*/   212,  213,
            /* 159*/  -106,  -88,
            /* 160*/   214,  215,
            /* 161*/   216,  217,
            /* 162*/   218,  -49,
            /* 163*/   219,  220,
            /* 164*/   221,  222,
            /* 165*/   223,  224,
            /* 166*/   225,  226,
            /* 167*/   227, -102,
            /* 168*/  -160,  228,
            /* 169*/   -46,  229,
            /* 170*/  -127,  230,
            /* 171*/  -103,  231,
            /* 172*/   232,  233,
            /* 173*/   -60,  234,
            /* 174*/   235,  -76,
            /* 175*/   236, -121,
            /* 176*/   237,  -73,
            /* 177*/  -149,  238,
            /* 178*/   239, -107,
            /* 179*/   -35,  240,
            /* 180*/   -71,  -27,
            /* 181*/   -69,  241,
            /* 182*/   -89,  -77,
            /* 183*/   -62, -118,
            /* 184*/   -75,  -85,
            /* 185*/   -72,  -58,
            /* 186*/   -63,  -80,
            /* 187*/   242,  -42,
            /* 188*/  -150, -157,
            /* 189*/  -139, -236,
            /* 190*/  -126, -243,
            /* 191*/  -142, -214,
            /* 192*/  -138, -206,
            /* 193*/  -240, -146,
            /* 194*/  -204, -147,
            /* 195*/  -152, -201,
            /* 196*/  -227, -207,
            /* 197*/  -154, -209,
            /* 198*/  -153, -254,
            /* 199*/  -176, -156,
            /* 200*/  -165, -210,
            /* 201*/  -172, -185,
            /* 202*/  -195, -170,
            /* 203*/  -232, -211,
            /* 204*/  -219, -239,
            /* 205*/  -200, -177,
            /* 206*/  -175, -212,
            /* 207*/  -244, -143,
            /* 208*/  -246, -171,
            /* 209*/  -203, -221,
            /* 210*/  -202, -181,
            /* 211*/  -173, -250,
            /* 212*/  -184, -164,
            /* 213*/  -193, -218,
            /* 214*/  -199, -220,
            /* 215*/  -190, -249,
            /* 216*/  -230, -217,
            /* 217*/  -169, -216,
            /* 218*/  -191, -197,
            /* 219*/   -47,  243,
            /* 220*/   244,  245,
            /* 221*/   246,  247,
            /* 222*/  -148, -159,
            /* 223*/   248,  249,
            /* 224*/   -92,  -93,
            /* 225*/   -96, -225,
            /* 226*/  -151,  -95,
            /* 227*/   250,  251,
            /* 228*/  -241,  252,
            /* 229*/  -161,  -36,
            /* 230*/   253,  254,
            /* 231*/  -135,  -39,
            /* 232*/  -187, -124,
            /* 233*/   255, -251,
            /* 234*/  -162, -238,
            /* 235*/  -242,  -38,
            /* 236*/   -43, -125,
            /* 237*/  -215, -253,
            /* 238*/  -140, -208,
            /* 239*/  -137, -235,
            /* 240*/  -158, -237,
            /* 241*/  -136, -205,
            /* 242*/  -155, -141,
            /* 243*/  -228, -229,
            /* 244*/  -213, -168,
            /* 245*/  -224, -194,
            /* 246*/  -196, -226,
            /* 247*/  -183, -233,
            /* 248*/  -231, -167,
            /* 249*/  -174, -189,
            /* 250*/  -252, -166,
            /* 251*/  -198, -222,
            /* 252*/  -188, -179,
            /* 253*/  -223, -182,
            /* 254*/  -180, -186,
            /* 255*/  -245, -247,
        };


        static void Main(string[] args)
        {
            int len = 0;
            byte[] back = Unpack(_crypt, 0, _crypt.Length, ref len);

            Console.WriteLine("Rückgabe von unserer Methode:");
            for (int i = 0; i < back.Length; i++)
            {
                Console.WriteLine(back[i]);
            }

            Console.WriteLine("So sollte das aussehen:");
            for (int i = 0; i < _real.Length; i++)
            {
                Console.WriteLine(_real[i]);
            }

            Console.ReadLine();
        }

        public unsafe static byte[] Unpack(byte[] input, int offset, int count, ref int length)
        {
            if (input.Length == 0)
                return null;

            //laut api soll der output byte[] genau input länge * 4 plus 4 sein
            byte[] output = new byte[input.Length * 4 + 4];

            int bit_num = 8;
            int treepos = 0;
            int value = 0;
            int mask = 0;
            int len = input.Length;
            int dest_index = 0;


            fixed (byte* pIntput = input)
            {
                byte* pStart = pIntput;
                while (true)
                {
                    if (bit_num == 8)
                    {
                        // End of input.
                        if (len == 0)
                        {
                            return output;
                        }
                        len--;
                        //HIER ist meiner Meinung das Problem... bei value =*pStart++
                        value = *pStart++;
                        bit_num = 0;
                        mask = 0x80;
                    }
                    if ((value & mask) == 0)
                        treepos = _duffmanTable[treepos * 2];
                    else
                        treepos = _duffmanTable[treepos * 2 + 1];
                    mask >>= 1; // shift on reck
                    bit_num++;

                    if (treepos <= 0) // this is a leaf.
                    {
                        if (treepos == -256) // special flush character
                        {
                            bit_num = 8; // flush rest of byte
                            treepos = 0; // start on tree top again
                            continue;
                        }
                        output[dest_index++] = (byte)-treepos;   // data is negative value
                        treepos = 0;      // start on tree top again
                    }
                }
            }
        }
    }
}


Ich wäre sehr dankbar wenn mir jemand unter die Arme greifen könnte...

mfg hurraa


Kha - Mo 09.02.09 16:16

C#-Quelltext 
1:
 
//HIER ist meiner Meinung das Problem... bei value =*pStart++

"'pStart' ist 'fixed-Variable', daher ist die Zuordnung nicht möglich", nehme ich an? Könntest du das dann nicht einfach dazuschreiben, bevor man überall nach Übersetzungsfehlern sucht :| ? Der einfachste Fix dürfte sein, alle Pointer wegzulassen und das Array wie in C# üblich per Index zu befüllen.


Hurraa - Mo 09.02.09 18:15
Einen Fehler erzeugt dieser code nicht... (pStart++)
Natürlich wäre es ohne pointer leserlicher, jedoch ist das nciht das problem.
Beim Algorithmus selbst stimmt etwas nicht...
Ich habe ein kleines Beispiel:

1) Mein array der NICHT comprimiert ist hat die 3 Werte { 185 , 130 , 223 }

2)Dann KOMPRIMIERT der Server den array und er wird zu { 179 , 36 ,206 , 79, 64 } (natürlich wird er länger weil der nicht comprimierte array viel zu kurz ist um den huffman algorithmus zu nützen)

3)Wenn ich alles decomprimiere bekomme ich NIE den Wert von dem ich ausgegangen bin...

mfg Hurraa


Kha - Mo 09.02.09 18:25
Mea culpa, so funktioniert es natürlich. Einen Übersetzungsfehler sehe ich nicht; als nächstes würde ich versuchen, beide Codes parallel zu debuggen, das sollte den Fehler auf jeden Fall entlarven.


Hurraa - Mo 09.02.09 20:05
Ok werde ich auf jeden Fall versuchen...
Ich habe da aber noch eine Frage zum Verständnis:
RunUO benutzt ja seinen eigenen huffmanTable. Wie stehen die compressions tabelle und decompressions table im zusammenhang? Könnte da ein Fehler sein?

mfg Hurraa


Hurraa - Di 10.02.09 18:12
Dein Tipp alles paralell zu debuggen war eine sehr gute Idee... Außerdem hab ich zuvor den unsafe code vom Server in leserliches c# übersetzt. Das hat mir auch geholfen.
Recht herzlichen Dank!

mfg Hurraa


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!