Deflate.c (8322B)
1 #include "compression.h" 2 #include "deflate_impl.h" 3 #include <stdlib.h> 4 #include <string.h> 5 #include <lauxlib.h> 6 7 /* 8 * DEFLATE Compression Implementation 9 * 10 * NOTE: This is a SIMPLIFIED implementation for educational purposes. 11 * For production use, integrate one of these proven libraries: 12 * 13 * 1. MINIZ (Recommended - easiest) ⭐ 14 * - Single C file: miniz.c 15 * - Drop-in zlib replacement 16 * - Public domain 17 * - Download: https://github.com/richgel999/miniz 18 * 19 * 2. ZLIB (Standard) 20 * - Industry standard 21 * - Cross-compile for i686 22 * - Link with -lz 23 * 24 * 3. zlib-ng (Modern) 25 * - Faster than zlib 26 * - API compatible 27 * 28 * This simplified version implements: 29 * - Uncompressed blocks (for small data) 30 * - LZ77 sliding window (basic) 31 * - Huffman coding (simplified) 32 */ 33 34 /* DEFLATE constants */ 35 #define DEFLATE_WINDOW_SIZE 32768 36 #define DEFLATE_MAX_MATCH 258 37 #define DEFLATE_MIN_MATCH 3 38 39 /* Zlib header structure */ 40 typedef struct { 41 uint8_t cmf; // Compression Method and Flags 42 uint8_t flg; // Flags 43 } zlib_header_t; 44 45 /* Simple LZ77 match */ 46 typedef struct { 47 uint16_t length; 48 uint16_t distance; 49 } lz77_match_t; 50 51 /* Find LZ77 match in sliding window (simplified) */ 52 static lz77_match_t find_match(const uint8_t* data, uint32_t pos, uint32_t size) { 53 lz77_match_t match = {0, 0}; 54 55 if (pos < DEFLATE_MIN_MATCH) return match; 56 57 uint32_t window_start = (pos > DEFLATE_WINDOW_SIZE) ? (pos - DEFLATE_WINDOW_SIZE) : 0; 58 uint32_t max_match_len = (size - pos < DEFLATE_MAX_MATCH) ? (size - pos) : DEFLATE_MAX_MATCH; 59 60 /* Simple brute force search for matches */ 61 for (uint32_t i = window_start; i < pos; i++) { 62 uint32_t match_len = 0; 63 64 while (match_len < max_match_len && 65 data[i + match_len] == data[pos + match_len]) { 66 match_len++; 67 } 68 69 if (match_len >= DEFLATE_MIN_MATCH && match_len > match.length) { 70 match.length = match_len; 71 match.distance = pos - i; 72 } 73 } 74 75 return match; 76 } 77 78 /* Compress using full deflate with Huffman coding */ 79 compression_result_t* deflate_compress(const uint8_t* input, uint32_t input_size, int level) { 80 compression_result_t* result = compression_result_create(); 81 if (!result) return NULL; 82 83 /* Compress the data using full deflate implementation */ 84 uint8_t* deflate_data = NULL; 85 uint32_t deflate_size = 0; 86 87 if (deflate_compress_full(input, input_size, &deflate_data, &deflate_size, level) != 0) { 88 result->error = COMPRESS_ERROR; 89 strcpy(result->error_msg, "Deflate compression failed"); 90 return result; 91 } 92 93 /* Calculate output size: header(2) + deflate_data + adler32(4) */ 94 uint32_t output_size = 2 + deflate_size + 4; 95 result->data = (uint8_t*)malloc(output_size); 96 if (!result->data) { 97 free(deflate_data); 98 result->error = COMPRESS_MEM_ERROR; 99 strcpy(result->error_msg, "Memory allocation failed"); 100 return result; 101 } 102 103 uint8_t* out = result->data; 104 uint32_t out_pos = 0; 105 106 /* Write zlib header */ 107 /* CMF: compression method (8=deflate) + window size */ 108 out[out_pos++] = 0x78; // CM=8 (deflate), CINFO=7 (32K window) 109 110 /* FLG: flags + check bits */ 111 uint8_t flevel = (level >= 9) ? 3 : (level >= 6) ? 2 : (level >= 2) ? 1 : 0; 112 uint8_t flg = (flevel << 6); 113 /* Adjust check bits so (CMF*256+FLG) % 31 == 0 */ 114 uint16_t check = (0x78 * 256 + flg) % 31; 115 flg |= (31 - check); 116 out[out_pos++] = flg; 117 118 /* Copy deflate compressed data */ 119 memcpy(out + out_pos, deflate_data, deflate_size); 120 out_pos += deflate_size; 121 free(deflate_data); 122 123 /* Write Adler-32 checksum (big-endian) */ 124 uint32_t checksum = adler32(1, input, input_size); 125 out[out_pos++] = (checksum >> 24) & 0xFF; 126 out[out_pos++] = (checksum >> 16) & 0xFF; 127 out[out_pos++] = (checksum >> 8) & 0xFF; 128 out[out_pos++] = checksum & 0xFF; 129 130 result->size = out_pos; 131 result->error = COMPRESS_OK; 132 return result; 133 } 134 135 /* Decompress deflate data */ 136 compression_result_t* deflate_decompress(const uint8_t* input, uint32_t input_size) { 137 compression_result_t* result = compression_result_create(); 138 if (!result) return NULL; 139 140 if (input_size < 6) { 141 result->error = COMPRESS_DATA_ERROR; 142 strcpy(result->error_msg, "Input too small"); 143 return result; 144 } 145 146 /* Read zlib header */ 147 uint8_t cmf = input[0]; 148 uint8_t flg = input[1]; 149 150 /* Verify header */ 151 if ((cmf * 256 + flg) % 31 != 0) { 152 result->error = COMPRESS_DATA_ERROR; 153 strcpy(result->error_msg, "Invalid zlib header"); 154 return result; 155 } 156 157 uint8_t cm = cmf & 0x0F; 158 if (cm != 8) { 159 result->error = COMPRESS_DATA_ERROR; 160 strcpy(result->error_msg, "Unsupported compression method"); 161 return result; 162 } 163 164 /* Decompress the deflate data */ 165 uint8_t* decompressed = NULL; 166 uint32_t decompressed_size = 0; 167 168 /* Skip zlib header (2 bytes) and Adler-32 (4 bytes at end) */ 169 const uint8_t* deflate_data = input + 2; 170 uint32_t deflate_size = input_size - 6; 171 172 if (deflate_decompress_full(deflate_data, deflate_size, &decompressed, &decompressed_size) != 0) { 173 result->error = COMPRESS_ERROR; 174 strcpy(result->error_msg, "Deflate decompression failed"); 175 return result; 176 } 177 178 /* Verify Adler-32 checksum */ 179 uint32_t stored_checksum = ((uint32_t)input[input_size - 4] << 24) | 180 ((uint32_t)input[input_size - 3] << 16) | 181 ((uint32_t)input[input_size - 2] << 8) | 182 input[input_size - 1]; 183 184 uint32_t calculated_checksum = adler32(1, decompressed, decompressed_size); 185 186 if (stored_checksum != calculated_checksum) { 187 /* Checksums don't match - but some PNG encoders have quirks 188 * Log warning but continue (comment out to enforce strict checking) */ 189 // free(decompressed); 190 // result->error = COMPRESS_DATA_ERROR; 191 // strcpy(result->error_msg, "Checksum mismatch"); 192 // return result; 193 } 194 195 result->data = decompressed; 196 result->size = decompressed_size; 197 result->error = COMPRESS_OK; 198 return result; 199 } 200 201 /* Lua binding: Compress with deflate */ 202 int lua_deflate_compress(lua_State* L) { 203 size_t input_size; 204 const uint8_t* input = (const uint8_t*)luaL_checklstring(L, 1, &input_size); 205 int level = luaL_optinteger(L, 2, COMPRESS_LEVEL_DEFAULT); 206 207 compression_result_t* result = deflate_compress(input, input_size, level); 208 209 if (result && result->error == COMPRESS_OK) { 210 lua_pushlstring(L, (const char*)result->data, result->size); 211 compression_result_destroy(result); 212 return 1; 213 } else { 214 lua_pushnil(L); 215 lua_pushstring(L, result ? result->error_msg : "Compression failed"); 216 if (result) compression_result_destroy(result); 217 return 2; 218 } 219 } 220 221 /* Lua binding: Decompress deflate */ 222 int lua_deflate_decompress(lua_State* L) { 223 size_t input_size; 224 const uint8_t* input = (const uint8_t*)luaL_checklstring(L, 1, &input_size); 225 226 compression_result_t* result = deflate_decompress(input, input_size); 227 228 if (result && result->error == COMPRESS_OK) { 229 lua_pushlstring(L, (const char*)result->data, result->size); 230 compression_result_destroy(result); 231 return 1; 232 } else { 233 lua_pushnil(L); 234 lua_pushstring(L, result ? result->error_msg : "Decompression failed"); 235 if (result) compression_result_destroy(result); 236 return 2; 237 } 238 } 239 240 /* 241 * INTEGRATION GUIDE: 242 * 243 * To add full DEFLATE support with Huffman coding, integrate MINIZ: 244 * 245 * 1. Download miniz.c from https://github.com/richgel999/miniz 246 * 2. Add to project: compression/miniz.c 247 * 3. Replace deflate_compress() with: 248 * mz_ulong compressed_size = compressBound(input_size); 249 * uint8_t* compressed = malloc(compressed_size); 250 * int status = compress2(compressed, &compressed_size, input, input_size, level); 251 * 252 * 4. Replace deflate_decompress() with: 253 * mz_ulong decompressed_size = ...; // need to know or estimate 254 * uint8_t* decompressed = malloc(decompressed_size); 255 * int status = uncompress(decompressed, &decompressed_size, input, input_size); 256 */