| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * mpq-sparse.c -- Bounded MPQ zero-run compression and decompression. | ||
| 3 | * | ||
| 4 | * Copyright (c) 2026-2026 Maik Broemme <mbroemme@libmpq.org> | ||
| 5 | * | ||
| 6 | * This file is free software; you can redistribute it and/or modify | ||
| 7 | * it under the terms of the GNU Lesser General Public License as published by | ||
| 8 | * the Free Software Foundation; either version 2.1 of the License, or | ||
| 9 | * (at your option) any later version. | ||
| 10 | * | ||
| 11 | * This file is distributed in the hope that it will be useful, | ||
| 12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
| 13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
| 14 | * GNU Lesser General Public License for more details. | ||
| 15 | * | ||
| 16 | * You should have received a copy of the GNU Lesser General Public License | ||
| 17 | * along with this file; if not, see <https://www.gnu.org/licenses/>. | ||
| 18 | */ | ||
| 19 | |||
| 20 | #include "mpq-sparse.h" | ||
| 21 | #include "mpq-endian.h" | ||
| 22 | #include <libmpq/mpq.h> | ||
| 23 | |||
| 24 | #include <string.h> | ||
| 25 | |||
| 26 | /* SPARSE lengths are big-endian, unlike MPQ header and table fields. */ | ||
| 27 | int32_t | ||
| 28 | 7688 | libmpq__sparse_compress( | |
| 29 | const uint8_t *in_buf, uint32_t in_size, uint8_t *out_buf, uint32_t out_size | ||
| 30 | ) | ||
| 31 | { | ||
| 32 | 7688 | uint32_t input = 0; | |
| 33 | 7688 | uint32_t output = 4; | |
| 34 | |||
| 35 |
8/10✓ Branch 0 taken 7687 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 7687 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 7686 times.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 7685 times.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 7685 times.
|
7688 | if (in_buf == NULL || out_buf == NULL || in_size == 0 || in_size > INT32_MAX || out_size < 4) |
| 36 | 3 | return LIBMPQ_ERROR_UNPACK; | |
| 37 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 7685 times.
|
7685 | if (out_size > INT32_MAX) |
| 38 | ✗ | out_size = INT32_MAX; | |
| 39 | 7685 | libmpq__store_be32(out_buf, in_size); | |
| 40 |
2/2✓ Branch 0 taken 1295212 times.
✓ Branch 1 taken 5867 times.
|
1301079 | while (input < in_size) { |
| 41 | 1295212 | uint32_t count = 0; | |
| 42 | 1295212 | uint32_t start = input; | |
| 43 | |||
| 44 | /* A token represents 3..130 zeros; shorter runs remain literal data. */ | ||
| 45 |
6/6✓ Branch 0 taken 3932054 times.
✓ Branch 1 taken 2520 times.
✓ Branch 2 taken 3927377 times.
✓ Branch 3 taken 4677 times.
✓ Branch 4 taken 2639362 times.
✓ Branch 5 taken 1288015 times.
|
3934574 | while (count < 130 && count < in_size - input && in_buf[input + count] == 0) |
| 46 | 2639362 | count++; | |
| 47 |
2/2✓ Branch 0 taken 648465 times.
✓ Branch 1 taken 646747 times.
|
1295212 | if (count >= 3) { |
| 48 |
2/2✓ Branch 0 taken 775 times.
✓ Branch 1 taken 647690 times.
|
648465 | if (output == out_size) |
| 49 | 775 | return LIBMPQ_ERROR_UNPACK; | |
| 50 | 647690 | out_buf[output++] = (uint8_t)(count - 3); | |
| 51 | 647690 | input += count; | |
| 52 | } else { | ||
| 53 | |||
| 54 | /* Stop literals before the next zero run or after 128 bytes. */ | ||
| 55 | do { | ||
| 56 | 901282 | input++; | |
| 57 |
6/6✓ Branch 0 taken 893599 times.
✓ Branch 1 taken 7683 times.
✓ Branch 2 taken 644358 times.
✓ Branch 3 taken 249241 times.
✓ Branch 4 taken 643384 times.
✓ Branch 5 taken 974 times.
|
901282 | if (in_size - input >= 3 && in_buf[input] == 0 && in_buf[input + 1] == 0 && |
| 58 |
2/2✓ Branch 0 taken 642422 times.
✓ Branch 1 taken 962 times.
|
643384 | in_buf[input + 2] == 0) |
| 59 | 642422 | break; | |
| 60 |
4/4✓ Branch 0 taken 255831 times.
✓ Branch 1 taken 3029 times.
✓ Branch 2 taken 254535 times.
✓ Branch 3 taken 1296 times.
|
258860 | } while (input < in_size && input - start < 128); |
| 61 | 646747 | count = input - start; | |
| 62 |
3/4✓ Branch 0 taken 646747 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1043 times.
✓ Branch 3 taken 645704 times.
|
646747 | if (output == out_size || count > out_size - output - 1) |
| 63 | 1043 | return LIBMPQ_ERROR_UNPACK; | |
| 64 | 645704 | out_buf[output++] = (uint8_t)(0x80U | (count - 1)); | |
| 65 | 645704 | memcpy(out_buf + output, in_buf + start, count); | |
| 66 | 645704 | output += count; | |
| 67 | } | ||
| 68 | } | ||
| 69 | 5867 | return (int32_t)output; | |
| 70 | } | ||
| 71 | |||
| 72 | /* Accept clipped terminal runs, but never accept missing output or input bytes. */ | ||
| 73 | int32_t | ||
| 74 | 4333 | libmpq__sparse_decompress( | |
| 75 | const uint8_t *in_buf, uint32_t in_size, uint8_t *out_buf, uint32_t out_size | ||
| 76 | ) | ||
| 77 | { | ||
| 78 | 4333 | uint32_t input = 4; | |
| 79 | 4333 | uint32_t output = 0; | |
| 80 | uint32_t length; | ||
| 81 | |||
| 82 |
6/6✓ Branch 0 taken 4332 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 4331 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 5 times.
✓ Branch 5 taken 4326 times.
|
4333 | if (in_buf == NULL || out_buf == NULL || in_size < 5) |
| 83 | 7 | return LIBMPQ_ERROR_UNPACK; | |
| 84 | 4326 | length = libmpq__load_be32(in_buf); | |
| 85 |
5/6✓ Branch 0 taken 4325 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 4322 times.
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 4322 times.
|
4326 | if (length == 0 || length > out_size || length > INT32_MAX) |
| 86 | 4 | return LIBMPQ_ERROR_UNPACK; | |
| 87 |
4/4✓ Branch 0 taken 1368262 times.
✓ Branch 1 taken 4320 times.
✓ Branch 2 taken 1368261 times.
✓ Branch 3 taken 1 times.
|
1372582 | while (input < in_size && output < length) { |
| 88 | 1368261 | uint8_t token = in_buf[input++]; | |
| 89 |
2/2✓ Branch 0 taken 683919 times.
✓ Branch 1 taken 684342 times.
|
1368261 | uint32_t count = (uint32_t)(token & 0x7fU) + ((token & 0x80U) ? 1U : 3U); |
| 90 | |||
| 91 | /* | ||
| 92 | * Accept the short terminal literal form emitted by Storm-style compressors, | ||
| 93 | * even when the token nominally describes more bytes than remain in the | ||
| 94 | * declared output. The required literal bytes must be physically present. | ||
| 95 | */ | ||
| 96 |
2/2✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1368258 times.
|
1368261 | if (count > length - output) |
| 97 | 3 | count = length - output; | |
| 98 |
2/2✓ Branch 0 taken 683919 times.
✓ Branch 1 taken 684342 times.
|
1368261 | if (token & 0x80U) { |
| 99 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 683918 times.
|
683919 | if (count > in_size - input) |
| 100 | 1 | return LIBMPQ_ERROR_UNPACK; | |
| 101 | 683918 | memcpy(out_buf + output, in_buf + input, count); | |
| 102 | 683918 | input += count; | |
| 103 | } else { | ||
| 104 | 684342 | memset(out_buf + output, 0, count); | |
| 105 | } | ||
| 106 | 1368260 | output += count; | |
| 107 | } | ||
| 108 |
4/4✓ Branch 0 taken 4320 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 4319 times.
|
4321 | if (input != in_size || output != length) |
| 109 | 2 | return LIBMPQ_ERROR_UNPACK; | |
| 110 | 4319 | return (int32_t)output; | |
| 111 | } | ||
| 112 |