1 /* 2 * COPYRIGHT: See COPYING in the top level directory 3 * PROJECT: ReactOS system libraries 4 * PURPOSE: Compression and decompression functions 5 * FILE: lib/rtl/compress.c 6 * PROGRAMER: Eric Kohl 7 Sebastian Lackner 8 Michael Müller 9 */ 10 11 /* INCLUDES *****************************************************************/ 12 13 #include <rtl.h> 14 15 #define NDEBUG 16 #include <debug.h> 17 18 /* MACROS *******************************************************************/ 19 20 #define COMPRESSION_FORMAT_MASK 0x00FF 21 #define COMPRESSION_ENGINE_MASK 0xFF00 22 23 24 25 26 /* FUNCTIONS ****************************************************************/ 27 28 /* Based on Wine Staging */ 29 30 /* decompress a single LZNT1 chunk */ 31 static PUCHAR lznt1_decompress_chunk(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size) 32 { 33 UCHAR *src_cur, *src_end, *dst_cur, *dst_end; 34 ULONG displacement_bits, length_bits; 35 ULONG code_displacement, code_length; 36 WORD flags, code; 37 38 src_cur = src; 39 src_end = src + src_size; 40 dst_cur = dst; 41 dst_end = dst + dst_size; 42 43 /* Partial decompression is no error on Windows. */ 44 while (src_cur < src_end && dst_cur < dst_end) 45 { 46 /* read flags header */ 47 flags = 0x8000 | *src_cur++; 48 49 /* parse following 8 entities, either uncompressed data or backwards reference */ 50 while ((flags & 0xFF00) && src_cur < src_end) 51 { 52 if (flags & 1) 53 { 54 /* backwards reference */ 55 if (src_cur + sizeof(WORD) > src_end) 56 return NULL; 57 code = *(WORD *)src_cur; 58 src_cur += sizeof(WORD); 59 60 /* find length / displacement bits */ 61 for (displacement_bits = 12; displacement_bits > 4; displacement_bits--) 62 if ((1 << (displacement_bits - 1)) < dst_cur - dst) break; 63 length_bits = 16 - displacement_bits; 64 code_length = (code & ((1 << length_bits) - 1)) + 3; 65 code_displacement = (code >> length_bits) + 1; 66 67 /* ensure reference is valid */ 68 if (dst_cur < dst + code_displacement) 69 return NULL; 70 71 /* copy bytes of chunk - we can't use memcpy() 72 * since source and dest can be overlapping */ 73 while (code_length--) 74 { 75 if (dst_cur >= dst_end) return dst_cur; 76 *dst_cur = *(dst_cur - code_displacement); 77 dst_cur++; 78 } 79 } 80 else 81 { 82 /* uncompressed data */ 83 if (dst_cur >= dst_end) return dst_cur; 84 *dst_cur++ = *src_cur++; 85 } 86 flags >>= 1; 87 } 88 89 } 90 91 return dst_cur; 92 } 93 94 /* decompress data encoded with LZNT1 */ 95 static NTSTATUS lznt1_decompress(UCHAR *dst, ULONG dst_size, UCHAR *src, ULONG src_size, 96 ULONG offset, ULONG *final_size, UCHAR *workspace) 97 { 98 UCHAR *src_cur = src, *src_end = src + src_size; 99 UCHAR *dst_cur = dst, *dst_end = dst + dst_size; 100 ULONG chunk_size, block_size; 101 WORD chunk_header; 102 UCHAR *ptr; 103 104 if (src_cur + sizeof(WORD) > src_end) 105 return STATUS_BAD_COMPRESSION_BUFFER; 106 107 /* skip over chunks which have a big distance (>= 0x1000) to the destination offset */ 108 while (offset >= 0x1000 && src_cur + sizeof(WORD) <= src_end) 109 { 110 /* read chunk header and extract size */ 111 chunk_header = *(WORD *)src_cur; 112 src_cur += sizeof(WORD); 113 if (!chunk_header) goto out; 114 chunk_size = (chunk_header & 0xFFF) + 1; 115 116 /* ensure we have enough buffer to process chunk */ 117 if (src_cur + chunk_size > src_end) 118 return STATUS_BAD_COMPRESSION_BUFFER; 119 120 src_cur += chunk_size; 121 offset -= 0x1000; 122 } 123 124 /* this chunk is can be included partially */ 125 if (offset && src_cur + sizeof(WORD) <= src_end) 126 { 127 /* read chunk header and extract size */ 128 chunk_header = *(WORD *)src_cur; 129 src_cur += sizeof(WORD); 130 if (!chunk_header) goto out; 131 chunk_size = (chunk_header & 0xFFF) + 1; 132 133 /* ensure we have enough buffer to process chunk */ 134 if (src_cur + chunk_size > src_end) 135 return STATUS_BAD_COMPRESSION_BUFFER; 136 137 if (dst_cur >= dst_end) 138 goto out; 139 140 if (chunk_header & 0x8000) 141 { 142 /* compressed chunk */ 143 if (!workspace) return STATUS_ACCESS_VIOLATION; 144 ptr = lznt1_decompress_chunk(workspace, 0x1000, src_cur, chunk_size); 145 if (!ptr) return STATUS_BAD_COMPRESSION_BUFFER; 146 if (ptr - workspace > offset) 147 { 148 block_size = min((ptr - workspace) - offset, dst_end - dst_cur); 149 memcpy(dst_cur, workspace + offset, block_size); 150 dst_cur += block_size; 151 } 152 } 153 else 154 { 155 /* uncompressed chunk */ 156 if (chunk_size > offset) 157 { 158 block_size = min(chunk_size - offset, dst_end - dst_cur); 159 memcpy(dst_cur, src_cur + offset, block_size); 160 dst_cur += block_size; 161 } 162 } 163 164 src_cur += chunk_size; 165 } 166 167 /* handle remaining chunks */ 168 while (src_cur + sizeof(WORD) <= src_end) 169 { 170 /* read chunk header and extract size */ 171 chunk_header = *(WORD *)src_cur; 172 src_cur += sizeof(WORD); 173 if (!chunk_header) goto out; 174 chunk_size = (chunk_header & 0xFFF) + 1; 175 176 if (src_cur + chunk_size > src_end) 177 return STATUS_BAD_COMPRESSION_BUFFER; 178 179 /* add padding if required */ 180 block_size = ((dst_cur - dst) + offset) & 0xFFF; 181 if (block_size) 182 { 183 block_size = 0x1000 - block_size; 184 if (dst_cur + block_size >= dst_end) 185 goto out; 186 memset(dst_cur, 0, block_size); 187 dst_cur += block_size; 188 } 189 190 if (dst_cur >= dst_end) 191 goto out; 192 193 if (chunk_header & 0x8000) 194 { 195 /* compressed chunk */ 196 dst_cur = lznt1_decompress_chunk(dst_cur, dst_end - dst_cur, src_cur, chunk_size); 197 if (!dst_cur) return STATUS_BAD_COMPRESSION_BUFFER; 198 } 199 else 200 { 201 /* uncompressed chunk */ 202 block_size = min(chunk_size, dst_end - dst_cur); 203 memcpy(dst_cur, src_cur, block_size); 204 dst_cur += block_size; 205 } 206 207 src_cur += chunk_size; 208 } 209 210 out: 211 if (final_size) 212 *final_size = dst_cur - dst; 213 214 return STATUS_SUCCESS; 215 216 } 217 218 219 static NTSTATUS 220 RtlpCompressBufferLZNT1(UCHAR *src, ULONG src_size, UCHAR *dst, ULONG dst_size, 221 ULONG chunk_size, ULONG *final_size, UCHAR *workspace) 222 { 223 UCHAR *src_cur = src, *src_end = src + src_size; 224 UCHAR *dst_cur = dst, *dst_end = dst + dst_size; 225 ULONG block_size; 226 227 while (src_cur < src_end) 228 { 229 /* determine size of current chunk */ 230 block_size = min(0x1000, src_end - src_cur); 231 if (dst_cur + sizeof(WORD) + block_size > dst_end) 232 return STATUS_BUFFER_TOO_SMALL; 233 234 /* write (uncompressed) chunk header */ 235 *(WORD *)dst_cur = 0x3000 | (block_size - 1); 236 dst_cur += sizeof(WORD); 237 238 /* write chunk content */ 239 memcpy(dst_cur, src_cur, block_size); 240 dst_cur += block_size; 241 src_cur += block_size; 242 } 243 244 if (final_size) 245 *final_size = dst_cur - dst; 246 247 return STATUS_SUCCESS; 248 } 249 250 251 static NTSTATUS 252 RtlpWorkSpaceSizeLZNT1(USHORT Engine, 253 PULONG BufferAndWorkSpaceSize, 254 PULONG FragmentWorkSpaceSize) 255 { 256 if (Engine == COMPRESSION_ENGINE_STANDARD) 257 { 258 *BufferAndWorkSpaceSize = 0x8010; 259 *FragmentWorkSpaceSize = 0x1000; 260 return(STATUS_SUCCESS); 261 } 262 else if (Engine == COMPRESSION_ENGINE_MAXIMUM) 263 { 264 *BufferAndWorkSpaceSize = 0x10; 265 *FragmentWorkSpaceSize = 0x1000; 266 return(STATUS_SUCCESS); 267 } 268 269 return(STATUS_NOT_SUPPORTED); 270 } 271 272 273 /* 274 * @implemented 275 */ 276 NTSTATUS NTAPI 277 RtlCompressBuffer(IN USHORT CompressionFormatAndEngine, 278 IN PUCHAR UncompressedBuffer, 279 IN ULONG UncompressedBufferSize, 280 OUT PUCHAR CompressedBuffer, 281 IN ULONG CompressedBufferSize, 282 IN ULONG UncompressedChunkSize, 283 OUT PULONG FinalCompressedSize, 284 IN PVOID WorkSpace) 285 { 286 USHORT Format = CompressionFormatAndEngine & COMPRESSION_FORMAT_MASK; 287 /* USHORT Engine = CompressionFormatAndEngine & COMPRESSION_ENGINE_MASK; */ 288 289 if ((Format == COMPRESSION_FORMAT_NONE) || 290 (Format == COMPRESSION_FORMAT_DEFAULT)) 291 return(STATUS_INVALID_PARAMETER); 292 293 if (Format == COMPRESSION_FORMAT_LZNT1) 294 return(RtlpCompressBufferLZNT1(UncompressedBuffer, 295 UncompressedBufferSize, 296 CompressedBuffer, 297 CompressedBufferSize, 298 UncompressedChunkSize, 299 FinalCompressedSize, 300 WorkSpace)); 301 302 return(STATUS_UNSUPPORTED_COMPRESSION); 303 } 304 305 306 /* 307 * @unimplemented 308 */ 309 NTSTATUS NTAPI 310 RtlCompressChunks(IN PUCHAR UncompressedBuffer, 311 IN ULONG UncompressedBufferSize, 312 OUT PUCHAR CompressedBuffer, 313 IN ULONG CompressedBufferSize, 314 IN OUT PCOMPRESSED_DATA_INFO CompressedDataInfo, 315 IN ULONG CompressedDataInfoLength, 316 IN PVOID WorkSpace) 317 { 318 UNIMPLEMENTED; 319 return STATUS_NOT_IMPLEMENTED; 320 } 321 322 /* 323 * @unimplemented 324 */ 325 NTSTATUS NTAPI 326 RtlDecompressChunks(OUT PUCHAR UncompressedBuffer, 327 IN ULONG UncompressedBufferSize, 328 IN PUCHAR CompressedBuffer, 329 IN ULONG CompressedBufferSize, 330 IN PUCHAR CompressedTail, 331 IN ULONG CompressedTailSize, 332 IN PCOMPRESSED_DATA_INFO CompressedDataInfo) 333 { 334 UNIMPLEMENTED; 335 return STATUS_NOT_IMPLEMENTED; 336 } 337 338 /* 339 * @implemented 340 */ 341 NTSTATUS NTAPI 342 RtlDecompressFragment(IN USHORT format, 343 OUT PUCHAR uncompressed, 344 IN ULONG uncompressed_size, 345 IN PUCHAR compressed, 346 IN ULONG compressed_size, 347 IN ULONG offset, 348 OUT PULONG final_size, 349 IN PVOID workspace) 350 { 351 DPRINT("0x%04x, %p, %u, %p, %u, %u, %p, %p :stub\n", format, uncompressed, 352 uncompressed_size, compressed, compressed_size, offset, final_size, workspace); 353 354 switch (format & ~COMPRESSION_ENGINE_MAXIMUM) 355 { 356 case COMPRESSION_FORMAT_LZNT1: 357 return lznt1_decompress(uncompressed, uncompressed_size, compressed, 358 compressed_size, offset, final_size, workspace); 359 360 case COMPRESSION_FORMAT_NONE: 361 case COMPRESSION_FORMAT_DEFAULT: 362 return STATUS_INVALID_PARAMETER; 363 364 default: 365 DPRINT1("format %d not implemented\n", format); 366 return STATUS_UNSUPPORTED_COMPRESSION; 367 } 368 } 369 370 /* 371 * @implemented 372 */ 373 NTSTATUS NTAPI 374 RtlDecompressBuffer(IN USHORT CompressionFormat, 375 OUT PUCHAR UncompressedBuffer, 376 IN ULONG UncompressedBufferSize, 377 IN PUCHAR CompressedBuffer, 378 IN ULONG CompressedBufferSize, 379 OUT PULONG FinalUncompressedSize) 380 { 381 return RtlDecompressFragment(CompressionFormat, UncompressedBuffer, UncompressedBufferSize, 382 CompressedBuffer, CompressedBufferSize, 0, FinalUncompressedSize, NULL); 383 } 384 385 /* 386 * @unimplemented 387 */ 388 NTSTATUS NTAPI 389 RtlDescribeChunk(IN USHORT CompressionFormat, 390 IN OUT PUCHAR *CompressedBuffer, 391 IN PUCHAR EndOfCompressedBufferPlus1, 392 OUT PUCHAR *ChunkBuffer, 393 OUT PULONG ChunkSize) 394 { 395 UNIMPLEMENTED; 396 return STATUS_NOT_IMPLEMENTED; 397 } 398 399 400 /* 401 * @unimplemented 402 */ 403 NTSTATUS NTAPI 404 RtlGetCompressionWorkSpaceSize(IN USHORT CompressionFormatAndEngine, 405 OUT PULONG CompressBufferAndWorkSpaceSize, 406 OUT PULONG CompressFragmentWorkSpaceSize) 407 { 408 USHORT Format = CompressionFormatAndEngine & COMPRESSION_FORMAT_MASK; 409 USHORT Engine = CompressionFormatAndEngine & COMPRESSION_ENGINE_MASK; 410 411 if ((Format == COMPRESSION_FORMAT_NONE) || 412 (Format == COMPRESSION_FORMAT_DEFAULT)) 413 return(STATUS_INVALID_PARAMETER); 414 415 if (Format == COMPRESSION_FORMAT_LZNT1) 416 return(RtlpWorkSpaceSizeLZNT1(Engine, 417 CompressBufferAndWorkSpaceSize, 418 CompressFragmentWorkSpaceSize)); 419 420 return(STATUS_UNSUPPORTED_COMPRESSION); 421 } 422 423 424 425 /* 426 * @unimplemented 427 */ 428 NTSTATUS NTAPI 429 RtlReserveChunk(IN USHORT CompressionFormat, 430 IN OUT PUCHAR *CompressedBuffer, 431 IN PUCHAR EndOfCompressedBufferPlus1, 432 OUT PUCHAR *ChunkBuffer, 433 IN ULONG ChunkSize) 434 { 435 UNIMPLEMENTED; 436 return STATUS_NOT_IMPLEMENTED; 437 } 438 439 /* EOF */ 440