implode.c

   1 /************************************************************************/\r
   2 /* File Name   : implode.c                                              */\r
   3 /* Creator     : ax.minaduki@gmail.com                                  */\r
   4 /* Create Time : May 23rd, 2010                                         */\r
   5 /* Module      : Lawine library                                         */\r
   6 /* Descript    : PKWare DCL implode compression API implementation      */\r
   7 /************************************************************************/\r
   8 \r
   9 #include "implode.h"\r
  10 \r
  11 /*\r
  12   Extended characters removed by Tony Lewis\r
  13 */\r
  14 \r
  15 /************************************************************************/\r
  16 \r
  17 /* Truncate value to a specified number of bits */\r
  18 #define TRUNCATE_VALUE(v, b)    ((v) & ((1 << (b)) - 1))\r
  19 \r
  20 /************************************************************************/\r
  21 \r
  22 /* Bit sequences used to represent literal bytes */\r
  23 static WORD s_ChCode[] = {\r
  24         0x0490, 0x0fe0, 0x07e0, 0x0be0, 0x03e0, 0x0de0, 0x05e0, 0x09e0,\r
  25         0x01e0, 0x00b8, 0x0062, 0x0ee0, 0x06e0, 0x0022, 0x0ae0, 0x02e0,\r
  26         0x0ce0, 0x04e0, 0x08e0, 0x00e0, 0x0f60, 0x0760, 0x0b60, 0x0360,\r
  27         0x0d60, 0x0560, 0x1240, 0x0960, 0x0160, 0x0e60, 0x0660, 0x0a60,\r
  28         0x000f, 0x0250, 0x0038, 0x0260, 0x0050, 0x0c60, 0x0390, 0x00d8,\r
  29         0x0042, 0x0002, 0x0058, 0x01b0, 0x007c, 0x0029, 0x003c, 0x0098,\r
  30         0x005c, 0x0009, 0x001c, 0x006c, 0x002c, 0x004c, 0x0018, 0x000c,\r
  31         0x0074, 0x00e8, 0x0068, 0x0460, 0x0090, 0x0034, 0x00b0, 0x0710,\r
  32         0x0860, 0x0031, 0x0054, 0x0011, 0x0021, 0x0017, 0x0014, 0x00a8,\r
  33         0x0028, 0x0001, 0x0310, 0x0130, 0x003e, 0x0064, 0x001e, 0x002e,\r
  34         0x0024, 0x0510, 0x000e, 0x0036, 0x0016, 0x0044, 0x0030, 0x00c8,\r
  35         0x01d0, 0x00d0, 0x0110, 0x0048, 0x0610, 0x0150, 0x0060, 0x0088,\r
  36         0x0fa0, 0x0007, 0x0026, 0x0006, 0x003a, 0x001b, 0x001a, 0x002a,\r
  37         0x000a, 0x000b, 0x0210, 0x0004, 0x0013, 0x0032, 0x0003, 0x001d,\r
  38         0x0012, 0x0190, 0x000d, 0x0015, 0x0005, 0x0019, 0x0008, 0x0078,\r
  39         0x00f0, 0x0070, 0x0290, 0x0410, 0x0010, 0x07a0, 0x0ba0, 0x03a0,\r
  40         0x0240, 0x1c40, 0x0c40, 0x1440, 0x0440, 0x1840, 0x0840, 0x1040,\r
  41         0x0040, 0x1f80, 0x0f80, 0x1780, 0x0780, 0x1b80, 0x0b80, 0x1380,\r
  42         0x0380, 0x1d80, 0x0d80, 0x1580, 0x0580, 0x1980, 0x0980, 0x1180,\r
  43         0x0180, 0x1e80, 0x0e80, 0x1680, 0x0680, 0x1a80, 0x0a80, 0x1280,\r
  44         0x0280, 0x1c80, 0x0c80, 0x1480, 0x0480, 0x1880, 0x0880, 0x1080,\r
  45         0x0080, 0x1f00, 0x0f00, 0x1700, 0x0700, 0x1b00, 0x0b00, 0x1300,\r
  46         0x0da0, 0x05a0, 0x09a0, 0x01a0, 0x0ea0, 0x06a0, 0x0aa0, 0x02a0,\r
  47         0x0ca0, 0x04a0, 0x08a0, 0x00a0, 0x0f20, 0x0720, 0x0b20, 0x0320,\r
  48         0x0d20, 0x0520, 0x0920, 0x0120, 0x0e20, 0x0620, 0x0a20, 0x0220,\r
  49         0x0c20, 0x0420, 0x0820, 0x0020, 0x0fc0, 0x07c0, 0x0bc0, 0x03c0,\r
  50         0x0dc0, 0x05c0, 0x09c0, 0x01c0, 0x0ec0, 0x06c0, 0x0ac0, 0x02c0,\r
  51         0x0cc0, 0x04c0, 0x08c0, 0x00c0, 0x0f40, 0x0740, 0x0b40, 0x0340,\r
  52         0x0300, 0x0d40, 0x1d00, 0x0d00, 0x1500, 0x0540, 0x0500, 0x1900,\r
  53         0x0900, 0x0940, 0x1100, 0x0100, 0x1e00, 0x0e00, 0x0140, 0x1600,\r
  54         0x0600, 0x1a00, 0x0e40, 0x0640, 0x0a40, 0x0a00, 0x1200, 0x0200,\r
  55         0x1c00, 0x0c00, 0x1400, 0x0400, 0x1800, 0x0800, 0x1000, 0x0000,\r
  56 };\r
  57 \r
  58 /* Lengths of bit sequences used to represent literal bytes */\r
  59 static BYTE s_ChBits[] = {\r
  60         0x0b, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x08, 0x07, 0x0c, 0x0c, 0x07, 0x0c, 0x0c,\r
  61         0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0d, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c,\r
  62         0x04, 0x0a, 0x08, 0x0c, 0x0a, 0x0c, 0x0a, 0x08, 0x07, 0x07, 0x08, 0x09, 0x07, 0x06, 0x07, 0x08,\r
  63         0x07, 0x06, 0x07, 0x07, 0x07, 0x07, 0x08, 0x07, 0x07, 0x08, 0x08, 0x0c, 0x0b, 0x07, 0x09, 0x0b,\r
  64         0x0c, 0x06, 0x07, 0x06, 0x06, 0x05, 0x07, 0x08, 0x08, 0x06, 0x0b, 0x09, 0x06, 0x07, 0x06, 0x06,\r
  65         0x07, 0x0b, 0x06, 0x06, 0x06, 0x07, 0x09, 0x08, 0x09, 0x09, 0x0b, 0x08, 0x0b, 0x09, 0x0c, 0x08,\r
  66         0x0c, 0x05, 0x06, 0x06, 0x06, 0x05, 0x06, 0x06, 0x06, 0x05, 0x0b, 0x07, 0x05, 0x06, 0x05, 0x05,\r
  67         0x06, 0x0a, 0x05, 0x05, 0x05, 0x05, 0x08, 0x07, 0x08, 0x08, 0x0a, 0x0b, 0x0b, 0x0c, 0x0c, 0x0c,\r
  68         0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d,\r
  69         0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d,\r
  70         0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d,\r
  71         0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c,\r
  72         0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c,\r
  73         0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c, 0x0c,\r
  74         0x0d, 0x0c, 0x0d, 0x0d, 0x0d, 0x0c, 0x0d, 0x0d, 0x0d, 0x0c, 0x0d, 0x0d, 0x0d, 0x0d, 0x0c, 0x0d,\r
  75         0x0d, 0x0d, 0x0c, 0x0c, 0x0c, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d, 0x0d,\r
  76 };\r
  77 \r
  78 /* Bit sequences used to represent the base values of the copy length */\r
  79 static BYTE s_LenCode[] = {\r
  80         0x05, 0x03, 0x01, 0x06, 0x0a, 0x02, 0x0c, 0x14, 0x04, 0x18, 0x08, 0x30, 0x10, 0x20, 0x40, 0x00,\r
  81 };\r
  82 \r
  83 /* Lengths of bit sequences used to represent the base values of the copy length */\r
  84 static BYTE s_LenBits[] = {\r
  85         0x03, 0x02, 0x03, 0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x07, 0x07,\r
  86 };\r
  87 \r
  88 /* Base values used for the copy length */\r
  89 static WORD s_LenBase[] = {\r
  90         0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008, 0x0009,\r
  91         0x000a, 0x000c, 0x0010, 0x0018, 0x0028, 0x0048, 0x0088, 0x0108,\r
  92 };\r
  93 \r
  94 /* Lengths of extra bits used to represent the copy length */\r
  95 static BYTE s_ExLenBits[] = {\r
  96         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08,\r
  97 };\r
  98 \r
  99 /* Bit sequences used to represent the most significant 6 bits of the copy offset */\r
 100 static BYTE s_OffsCode[] = {\r
 101         0x03, 0x0d, 0x05, 0x19, 0x09, 0x11, 0x01, 0x3e, 0x1e, 0x2e, 0x0e, 0x36, 0x16, 0x26, 0x06, 0x3a,\r
 102         0x1a, 0x2a, 0x0a, 0x32, 0x12, 0x22, 0x42, 0x02, 0x7c, 0x3c, 0x5c, 0x1c, 0x6c, 0x2c, 0x4c, 0x0c,\r
 103         0x74, 0x34, 0x54, 0x14, 0x64, 0x24, 0x44, 0x04, 0x78, 0x38, 0x58, 0x18, 0x68, 0x28, 0x48, 0x08,\r
 104         0xf0, 0x70, 0xb0, 0x30, 0xd0, 0x50, 0x90, 0x10, 0xe0, 0x60, 0xa0, 0x20, 0xc0, 0x40, 0x80, 0x00,\r
 105 };\r
 106 \r
 107 /* Lengths of bit sequences used to represent the most significant 6 bits of the copy offset */\r
 108 static BYTE s_OffsBits[] = {\r
 109         0x02, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,\r
 110         0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,\r
 111         0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,\r
 112         0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,\r
 113 };\r
 114 \r
 115 /************************************************************************/\r
 116 \r
 117 BOOL implode(INT type, INT dict, VCPTR src, UINT src_size, VPTR dest, UINT *dest_size)\r
 118 {\r
 119         INT i;                                  // Index into tables\r
 120         BYTE ch;                                // Byte from input buffer\r
 121         INT max_copy_len;               // Length of longest duplicate data in the dictionary\r
 122         BUFPTR max_copy_ptr;    // Pointer to longest duplicate data in the dictionary\r
 123         INT copy_len;                   // Length of duplicate data in the dictionary\r
 124         INT copy_off;                   // Offset used in actual compressed data\r
 125         INT new_copy_off;               // Secondary offset used in actual compressed data\r
 126         BUFPTR copy_ptr;                // Pointer to duplicate data in the dictionary\r
 127         BUFPTR bak_copy_ptr;    // Temporarily holds previous value of copy_ptr\r
 128         BUFCPTR new_rd_ptr;             // Secondary offset into input buffer\r
 129         BUFPTR new_dict_ptr;    // Secondary offset into dictionary\r
 130         BUFCPTR rd_ptr;                 // Current position in input buffer\r
 131         BUFPTR wrt_ptr;                 // Current position in output buffer\r
 132         BUFCPTR src_end_ptr;    // Pointer to the end of source buffer\r
 133         BUFPTR dest_end_ptr;    // Pointer to the end of dest buffer\r
 134         BYTE bit_num;                   // Number of bits in bit buffer\r
 135         DWORD bit_buf;                  // Stores bits until there are enough to output a byte of data\r
 136         BUFPTR dict_ptr;                // Position in dictionary\r
 137         UINT dict_size;                 // Maximum size of dictionary\r
 138         UINT cur_dict_size;             // Current size of dictionary\r
 139         BYTE dict_buf[4096];    // Sliding dictionary used for compression and decompression\r
 140 \r
 141         // Check for a valid compression type\r
 142         if (type != IMPLODE_BINARY && type != IMPLODE_ASCII)\r
 143                 return FALSE;\r
 144 \r
 145         // Only dictionary sizes of 1024, 2048, and 4096 are allowed.\r
 146         // The values 4, 5, and 6 correspond with those sizes\r
 147         switch (dict) {\r
 148         case IMPLODE_DICT_1K:\r
 149                 // Store actual dictionary size\r
 150                 dict_size = 1024;\r
 151                 break;\r
 152         case IMPLODE_DICT_2K:\r
 153                 // Store actual dictionary size\r
 154                 dict_size = 2048;\r
 155                 break;\r
 156         case IMPLODE_DICT_4K:\r
 157                 // Store actual dictionary size\r
 158                 dict_size = 4096;\r
 159                 break;\r
 160         default:\r
 161                 return FALSE;\r
 162         }\r
 163 \r
 164         // Initialize buffer positions\r
 165         rd_ptr = src;\r
 166         wrt_ptr = dest;\r
 167         src_end_ptr = rd_ptr + src_size;\r
 168         dest_end_ptr = wrt_ptr + *dest_size;\r
 169 \r
 170         // Initialize dictionary position\r
 171         dict_ptr = dict_buf;\r
 172 \r
 173         // Initialize current dictionary size to zero\r
 174         cur_dict_size = 0;\r
 175 \r
 176         // If the output buffer size is less than 4, there\r
 177         // is not enough room for the compressed data\r
 178         if (*dest_size < 4 && !(src_size == 0 && *dest_size == 4))\r
 179                 return FALSE;\r
 180 \r
 181         // Store compression type and dictionary size\r
 182         *wrt_ptr++ = type;\r
 183         *wrt_ptr++ = dict;\r
 184 \r
 185         // Initialize bit buffer\r
 186         bit_buf = 0;\r
 187         bit_num = 0;\r
 188 \r
 189         // Compress until input buffer is empty\r
 190         while (rd_ptr < src_end_ptr) {\r
 191 \r
 192                 // Get a byte from the input buffer\r
 193                 ch = *rd_ptr++;\r
 194                 max_copy_len = 0;\r
 195 \r
 196                 // If the dictionary is not empty, search for duplicate data in the dictionary\r
 197                 if (cur_dict_size > 1 && src_end_ptr - rd_ptr > 1) {\r
 198 \r
 199                         // Initialize offsets and lengths used in search\r
 200                         copy_ptr = dict_buf;\r
 201                         max_copy_ptr = copy_ptr;\r
 202                         max_copy_len = 0;\r
 203 \r
 204                         // Store position of last written dictionary byte\r
 205                         new_dict_ptr = dict_ptr - 1;\r
 206                         if (new_dict_ptr < dict_buf)\r
 207                                 new_dict_ptr = dict_buf + cur_dict_size - 1;\r
 208 \r
 209                         // Search dictionary for duplicate data\r
 210                         for (; copy_ptr < dict_buf + cur_dict_size; copy_ptr++) {\r
 211 \r
 212                                 // Check for a match with first byte\r
 213                                 if (ch != *copy_ptr)\r
 214                                         continue;\r
 215 \r
 216                                 bak_copy_ptr = copy_ptr;\r
 217                                 copy_len = 0;\r
 218                                 new_rd_ptr = rd_ptr - 1;\r
 219 \r
 220                                 // If there was a match, check for additional duplicate bytes\r
 221                                 do {\r
 222 \r
 223                                         // Increment pointers and length\r
 224                                         copy_len++;\r
 225                                         new_rd_ptr++;\r
 226                                         copy_ptr++;\r
 227 \r
 228                                         // Wrap around pointer to beginning of dictionary buffer if the end of the buffer was reached\r
 229                                         if (copy_ptr >= dict_buf + dict_size)\r
 230                                                 copy_ptr = dict_buf;\r
 231 \r
 232                                         // Wrap dictionary bytes if end of the dictionary was reached\r
 233                                         if (copy_ptr == dict_ptr)\r
 234                                                 copy_ptr = bak_copy_ptr;\r
 235 \r
 236                                         // Stop checking for additional bytes if there is no more input or maximum length was reached\r
 237                                         if (copy_len >= 518 || new_rd_ptr >= src_end_ptr)\r
 238                                                 break;\r
 239 \r
 240                                 } while (*new_rd_ptr == *copy_ptr);\r
 241 \r
 242                                 // Return the pointer to the beginning of the matching data\r
 243                                 copy_ptr = bak_copy_ptr;\r
 244 \r
 245                                 // Copying less than two bytes from dictionary wastes space, so don't do it ;)\r
 246                                 if (copy_len < 2 || copy_len < max_copy_len)\r
 247                                         continue;\r
 248 \r
 249                                 // Store the offset that will be outputted into the compressed data\r
 250                                 new_copy_off = (new_dict_ptr - (copy_ptr - cur_dict_size)) % cur_dict_size;\r
 251 \r
 252                                 // If the length is equal, check for a more efficient offset\r
 253                                 if (copy_len == max_copy_len) {\r
 254 \r
 255                                         // Use the most efficient offset\r
 256                                         if (new_copy_off < copy_off) {\r
 257                                                 copy_off = new_copy_off;\r
 258                                                 max_copy_ptr = copy_ptr;\r
 259                                                 max_copy_len = copy_len;\r
 260                                         }\r
 261                                 }\r
 262                                 // Only use the most efficient length and offset in dictionary\r
 263                                 else {\r
 264 \r
 265                                         // Store the offset that will be outputted into the compressed data\r
 266                                         copy_off = new_copy_off;\r
 267 \r
 268                                         // If the copy length is 2, check for a valid dictionary offset\r
 269                                         if (copy_len > 2 || copy_off <= 255) {\r
 270                                                 max_copy_ptr = copy_ptr;\r
 271                                                 max_copy_len = copy_len;\r
 272                                         }\r
 273                                 }\r
 274                         }\r
 275 \r
 276                         // If there were at least 2 matching bytes in the dictionary that were found, output the length/offset pair\r
 277                         if (max_copy_len >= 2) {\r
 278 \r
 279                                 // Reset the input pointers to the bytes that will be added to the dictionary\r
 280                                 rd_ptr--;\r
 281                                 new_rd_ptr = rd_ptr + max_copy_len;\r
 282 \r
 283                                 while (rd_ptr < new_rd_ptr) {\r
 284 \r
 285                                         // Add a byte to the dictionary\r
 286                                         *dict_ptr++ = ch;\r
 287 \r
 288                                         // If the dictionary is not full yet, increment the current dictionary size\r
 289                                         if (cur_dict_size < dict_size)\r
 290                                                 cur_dict_size++;\r
 291 \r
 292                                         // If the current end of the dictionary is past the end of the buffer,\r
 293                                         // wrap around back to the start\r
 294                                         if (dict_ptr >= dict_buf + dict_size)\r
 295                                                 dict_ptr = dict_buf;\r
 296 \r
 297                                         // Get the next byte to be added\r
 298                                         if (++rd_ptr < new_rd_ptr)\r
 299                                                 ch = *rd_ptr;\r
 300                                 }\r
 301 \r
 302                                 // Find bit code for the base value of the length from the table\r
 303                                 for (i = 0; i < 0x0F; i++) {\r
 304 \r
 305                                         if (s_LenBase[i] <= max_copy_len && max_copy_len < s_LenBase[i + 1])\r
 306                                                 break;\r
 307                                 }\r
 308 \r
 309                                 // Store the base value of the length\r
 310                                 bit_buf += (1 + (s_LenCode[i] << 1)) << bit_num;\r
 311                                 bit_num += 1 + s_LenBits[i];\r
 312 \r
 313                                 // Store the extra bits for the length\r
 314                                 bit_buf += (max_copy_len - s_LenBase[i]) << bit_num;\r
 315                                 bit_num += s_ExLenBits[i];\r
 316 \r
 317                                 // Output the data from the bit buffer\r
 318                                 while (bit_num >= 8) {\r
 319 \r
 320                                         // If output buffer has become full, stop immediately!\r
 321                                         if (wrt_ptr >= dest_end_ptr)\r
 322                                                 return FALSE;\r
 323 \r
 324                                         *wrt_ptr++ = (BYTE)bit_buf;\r
 325                                         bit_buf >>= 8;\r
 326                                         bit_num -= 8;\r
 327                                 }\r
 328 \r
 329                                 // The most significant 6 bits of the dictionary offset are encoded with a\r
 330                                 // bit sequence then the first 2 after that if the copy length is 2,\r
 331                                 // otherwise it is the first 4, 5, or 6 (based on the dictionary size)\r
 332                                 if (max_copy_len == 2) {\r
 333 \r
 334                                         // Store most significant 6 bits of offset using bit sequence\r
 335                                         bit_buf += s_OffsCode[copy_off >> 2] << bit_num;\r
 336                                         bit_num += s_OffsBits[copy_off >> 2];\r
 337 \r
 338                                         // Store the first 2 bits\r
 339                                         bit_buf += (copy_off & 0x03) << bit_num;\r
 340                                         bit_num += 2;\r
 341                                 }\r
 342                                 else {\r
 343 \r
 344                                         // Store most significant 6 bits of offset using bit sequence\r
 345                                         bit_buf += s_OffsCode[copy_off >> dict] << bit_num;\r
 346                                         bit_num += s_OffsBits[copy_off >> dict];\r
 347 \r
 348                                         // Store the first 4, 5, or 6 bits\r
 349                                         bit_buf += TRUNCATE_VALUE(copy_off, dict) << bit_num;\r
 350                                         bit_num += dict;\r
 351                                 }\r
 352                         }\r
 353                 }\r
 354 \r
 355                 // If the copy length was less than two, include the byte as a literal byte\r
 356                 if (max_copy_len < 2) {\r
 357 \r
 358                         if (type == IMPLODE_BINARY) {\r
 359 \r
 360                                 // Store a fixed size literal byte\r
 361                                 bit_buf += ch << (bit_num + 1);\r
 362                                 bit_num += 9;\r
 363                         }\r
 364                         else {\r
 365 \r
 366                                 // Store a variable size literal byte\r
 367                                 bit_buf += s_ChCode[ch] << (bit_num + 1);\r
 368                                 bit_num += 1 + s_ChBits[ch];\r
 369                         }\r
 370 \r
 371                         // Add the byte into the dictionary\r
 372                         *dict_ptr++ = ch;\r
 373 \r
 374                         // If the dictionary is not full yet, increment the current dictionary size\r
 375                         if (cur_dict_size < dict_size)\r
 376                                 cur_dict_size++;\r
 377 \r
 378                         // If the current end of the dictionary is past the end of the buffer,\r
 379                         // wrap around back to the start\r
 380                         if (dict_ptr >= dict_buf + dict_size)\r
 381                                 dict_ptr = dict_buf;\r
 382                 }\r
 383 \r
 384                 // Write any whole bytes from the bit buffer into the output buffer\r
 385                 while (bit_num >= 8) {\r
 386 \r
 387                         // If output buffer has become full, stop immediately!\r
 388                         if (wrt_ptr >= dest_end_ptr)\r
 389                                 return FALSE;\r
 390 \r
 391                         *wrt_ptr++ = (BYTE)bit_buf;\r
 392                         bit_buf >>= 8;\r
 393                         bit_num -= 8;\r
 394                 }\r
 395         }\r
 396 \r
 397         // Store the code for the end of the compressed data stream\r
 398         bit_buf += (1 + (s_LenCode[0x0f] << 1)) << bit_num;\r
 399         bit_num += 1 + s_LenBits[0x0f];\r
 400 \r
 401         bit_buf += 0xff << bit_num;\r
 402         bit_num += 8;\r
 403 \r
 404         // Write any remaining bits from the bit buffer into the output buffer\r
 405         while (bit_num > 0) {\r
 406 \r
 407                 // If output buffer has become full, stop immediately!\r
 408                 if (wrt_ptr >= dest_end_ptr)\r
 409                         return FALSE;\r
 410 \r
 411                 *wrt_ptr++ = (BYTE)bit_buf;\r
 412                 bit_buf >>= 8;\r
 413                 if (bit_num >= 8)\r
 414                         bit_num -= 8;\r
 415                 else\r
 416                         bit_num = 0;\r
 417         }\r
 418 \r
 419         // Store the compressed size\r
 420         *dest_size = wrt_ptr - (BUFPTR)dest;\r
 421 \r
 422         return TRUE;\r
 423 }\r
 424 \r
 425 BOOL explode(VCPTR src, UINT src_size, VPTR dest, UINT *dest_size)\r
 426 {\r
 427         INT i;                                  // Index into tables\r
 428         INT copy_len;                   // Length of data to copy from the dictionary\r
 429         BUFPTR copy_off;                // Offset to data to copy from the dictionary\r
 430         BYTE type;                              // Specifies whether to use fixed or variable size literal bytes\r
 431         BYTE dict;                              // Dictionary size; valid values are 4, 5, and 6 which represent 1024, 2048, and 4096 respectively\r
 432         BUFCPTR rd_ptr;                 // Current position in input buffer\r
 433         BUFPTR wrt_ptr;                 // Current position in output buffer\r
 434         BUFCPTR src_end_ptr;    // Pointer to the end of source buffer\r
 435         BUFPTR dest_end_ptr;    // Pointer to the end of dest buffer\r
 436         BYTE bit_num;                   // Number of bits in bit buffer\r
 437         DWORD bit_buf;                  // Stores bits until there are enough to output a byte of data\r
 438         BUFPTR dict_ptr;                // Position in dictionary\r
 439         UINT dict_size;                 // Maximum size of dictionary\r
 440         UINT cur_dict_size;             // Current size of dictionary\r
 441         BYTE dict_buf[0x1000];  // Sliding dictionary used for compression and decompression\r
 442 \r
 443         // Compressed data cannot be less than 4 bytes;\r
 444         // this is not possible in any case whatsoever\r
 445         if (src_size < 4) {\r
 446                 *dest_size = 0;\r
 447                 return FALSE;\r
 448         }\r
 449 \r
 450         // Initialize buffer positions\r
 451         rd_ptr = src;\r
 452         wrt_ptr = dest;\r
 453         src_end_ptr = rd_ptr + src_size;\r
 454         dest_end_ptr = wrt_ptr + *dest_size;\r
 455 \r
 456         // Get header from compressed data\r
 457         type = *rd_ptr++;\r
 458         dict = *rd_ptr++;\r
 459 \r
 460         // Check for a valid compression type\r
 461         if (type != IMPLODE_BINARY && type != IMPLODE_ASCII)\r
 462                 return FALSE;\r
 463 \r
 464         // Only dictionary sizes of 1024, 2048, and 4096 are allowed.\r
 465         // The values 4, 5, and 6 correspond with those sizes\r
 466         switch (dict) {\r
 467         case IMPLODE_DICT_1K:\r
 468                 // Store actual dictionary size\r
 469                 dict_size = 1024;\r
 470                 break;\r
 471         case IMPLODE_DICT_2K:\r
 472                 // Store actual dictionary size\r
 473                 dict_size = 2048;\r
 474                 break;\r
 475         case IMPLODE_DICT_4K:\r
 476                 // Store actual dictionary size\r
 477                 dict_size = 4096;\r
 478                 break;\r
 479         default:\r
 480                 return FALSE;\r
 481         }\r
 482 \r
 483         // Initialize dictionary position\r
 484         dict_ptr = dict_buf;\r
 485 \r
 486         // Initialize current dictionary size to zero\r
 487         cur_dict_size = 0;\r
 488 \r
 489         // Get first 16 bits\r
 490         bit_buf = *rd_ptr++;\r
 491         bit_buf += *rd_ptr++ << 8;\r
 492         bit_num = 16;\r
 493 \r
 494         // Decompress until output buffer is full\r
 495         while (wrt_ptr < dest_end_ptr) {\r
 496 \r
 497                 // Fill bit buffer with at least 16 bits\r
 498                 while (bit_num < 16) {\r
 499 \r
 500                         // If input buffer is empty before end of stream, buffer is incomplete\r
 501                         if (rd_ptr >= src_end_ptr) {\r
 502 \r
 503                                 // Store the current size of output\r
 504                                 *dest_size = wrt_ptr - (BUFPTR)dest;\r
 505                                 return FALSE;\r
 506                         }\r
 507 \r
 508                         bit_buf += *rd_ptr++ << bit_num;\r
 509                         bit_num += 8;\r
 510                 }\r
 511 \r
 512                 // First bit is 1; copy from dictionary\r
 513                 if (bit_buf & 1) {\r
 514 \r
 515                         // Remove first bit from bit buffer\r
 516                         bit_buf >>= 1;\r
 517                         bit_num--;\r
 518 \r
 519                         // Find the base value for the copy length\r
 520                         for (i = 0; i <= 0x0F; i++) {\r
 521 \r
 522                                 if (TRUNCATE_VALUE(bit_buf, s_LenBits[i]) == s_LenCode[i])\r
 523                                         break;\r
 524                         }\r
 525 \r
 526                         // Remove value from bit buffer\r
 527                         bit_buf >>= s_LenBits[i];\r
 528                         bit_num -= s_LenBits[i];\r
 529 \r
 530                         // Store the copy length\r
 531                         copy_len = s_LenBase[i] + TRUNCATE_VALUE(bit_buf, s_ExLenBits[i]);\r
 532 \r
 533                         // Remove the extra bits from the bit buffer\r
 534                         bit_buf >>= s_ExLenBits[i];\r
 535                         bit_num -= s_ExLenBits[i];\r
 536 \r
 537                         // If copy length is 519, the end of the stream has been reached\r
 538                         if (copy_len == 519)\r
 539                                 break;\r
 540 \r
 541                         // Fill bit buffer with at least 14 bits\r
 542                         while (bit_num < 14) {\r
 543 \r
 544                                 // If input buffer is empty before end of stream, buffer is incomplete\r
 545                                 if (rd_ptr >= src_end_ptr) {\r
 546 \r
 547                                         // Store the current size of output\r
 548                                         *dest_size = wrt_ptr - (BUFPTR)dest;\r
 549                                         return FALSE;\r
 550                                 }\r
 551 \r
 552                                 bit_buf += *rd_ptr++ << bit_num;\r
 553                                 bit_num += 8;\r
 554                         }\r
 555 \r
 556                         // Find most significant 6 bits of offset into the dictionary\r
 557                         for (i = 0; i <= 0x3f; i++) {\r
 558 \r
 559                                 if (TRUNCATE_VALUE(bit_buf, s_OffsBits[i]) == s_OffsCode[i])\r
 560                                         break;\r
 561                         }\r
 562 \r
 563                         // Remove value from bit buffer\r
 564                         bit_buf >>= s_OffsBits[i];\r
 565                         bit_num -= s_OffsBits[i];\r
 566 \r
 567                         // If the copy length is 2, there are only two more bits in the dictionary\r
 568                         // offset; otherwise, there are 4, 5, or 6 bits left, depending on what\r
 569                         // the dictionary size is\r
 570                         if (copy_len == 2) {\r
 571 \r
 572                                 // Store the exact offset to a byte in the dictionary\r
 573                                 copy_off = dict_ptr - 1 - ((i << 2) + (bit_buf & 0x03));\r
 574 \r
 575                                 // Remove the rest of the dictionary offset from the bit buffer\r
 576                                 bit_buf >>= 2;\r
 577                                 bit_num -= 2;\r
 578                         }\r
 579                         else {\r
 580 \r
 581                                 // Store the exact offset to a byte in the dictionary\r
 582                                 copy_off = dict_ptr - 1 - ((i << dict) + TRUNCATE_VALUE(bit_buf, dict));\r
 583 \r
 584                                 // Remove the rest of the dictionary offset from the bit buffer\r
 585                                 bit_buf >>= dict;\r
 586                                 bit_num -= dict;\r
 587                         }\r
 588 \r
 589                         // While there are still bytes left, copy bytes from the dictionary\r
 590                         while (copy_len-- > 0) {\r
 591 \r
 592                                 // If output buffer has become full, stop immediately!\r
 593                                 if (wrt_ptr >= dest_end_ptr) {\r
 594 \r
 595                                         // Store the current size of output\r
 596                                         *dest_size = wrt_ptr - (BUFPTR)dest;\r
 597                                         return FALSE;\r
 598                                 }\r
 599 \r
 600                                 // Check whether the offset is a valid one into the dictionary\r
 601                                 while (copy_off < dict_buf)\r
 602                                         copy_off += cur_dict_size;\r
 603                                 while (copy_off >= dict_buf + cur_dict_size)\r
 604                                         copy_off -= cur_dict_size;\r
 605 \r
 606                                 // Copy the byte from the dictionary and add it to the end of the dictionary\r
 607                                 *dict_ptr++ = *wrt_ptr++ = *copy_off++;\r
 608 \r
 609                                 // If the dictionary is not full yet, increment the current dictionary size\r
 610                                 if (cur_dict_size < dict_size)\r
 611                                         cur_dict_size++;\r
 612 \r
 613                                 // If the current end of the dictionary is past the end of the buffer,\r
 614                                 // wrap around back to the start\r
 615                                 if (dict_ptr >= dict_buf + dict_size)\r
 616                                         dict_ptr = dict_buf;\r
 617                         }\r
 618                 }\r
 619 \r
 620                 // First bit is 0; literal byte\r
 621                 else {\r
 622 \r
 623                         // Fixed size literal byte\r
 624                         if (type == IMPLODE_BINARY) {\r
 625 \r
 626                                 // Copy the byte and add it to the end of the dictionary\r
 627                                 *dict_ptr++ = (BYTE)(bit_buf >> 1);\r
 628                                 *wrt_ptr++ = (BYTE)(bit_buf >> 1);\r
 629 \r
 630                                 // Remove the byte from the bit buffer\r
 631                                 bit_buf >>= 9;\r
 632                                 bit_num -= 9;\r
 633                         }\r
 634 \r
 635                         // Variable size literal byte\r
 636                         else {\r
 637 \r
 638                                 // Remove the first bit from the bit buffer\r
 639                                 bit_buf >>= 1;\r
 640                                 bit_num--;\r
 641 \r
 642                                 // Find the actual byte from the bit sequence\r
 643                                 for (i = 0; i <= 0xff; i++) {\r
 644                                         if (TRUNCATE_VALUE(bit_buf, s_ChBits[i]) == s_ChCode[i])\r
 645                                                 break;\r
 646                                 }\r
 647 \r
 648                                 // Copy the byte and add it to the end of the dictionary\r
 649                                 *dict_ptr++ = i;\r
 650                                 *wrt_ptr++ = i;\r
 651 \r
 652                                 // Remove the byte from the bit buffer\r
 653                                 bit_buf >>= s_ChBits[i];\r
 654                                 bit_num -= s_ChBits[i];\r
 655                         }\r
 656 \r
 657                         // If the dictionary is not full yet, increment the current dictionary size\r
 658                         if (cur_dict_size < dict_size)\r
 659                                 cur_dict_size++;\r
 660 \r
 661                         // If the current end of the dictionary is past the end of the buffer,\r
 662                         // wrap around back to the start\r
 663                         if (dict_ptr >= dict_buf + dict_size)\r
 664                                 dict_ptr = dict_buf;\r
 665                 }\r
 666         }\r
 667 \r
 668         // Store the decompressed size\r
 669         *dest_size = wrt_ptr - (BUFPTR)dest;\r
 670 \r
 671         return TRUE;\r
 672 }\r
 673 \r
 674 /************************************************************************/\r