sdk/lib/rtl/compress.c

   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 */