blob: 7669dab9aa3bda2094cb0a34f9f3cc6e39d362c9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
// Copyright (c) 2015 YamaArashi
#include <stdlib.h>
#include <stdbool.h>
#include "global.h"
#include "lz.h"
unsigned char *LZDecompress(unsigned char *src, int srcSize, int *uncompressedSize)
{
if (srcSize < 4)
return NULL;
int destSize = (src[3] << 16) | (src[2] << 8) | src[1];
unsigned char *dest = malloc(destSize);
if (dest == NULL)
return NULL;
int srcPos = 4;
int destPos = 0;
for (;;) {
if (srcPos >= srcSize)
return NULL;
unsigned char flags = src[srcPos++];
for (int i = 0; i < 8; i++) {
if (flags & 0x80) {
if (srcPos + 1 >= srcSize)
return NULL;
int blockSize = (src[srcPos] >> 4) + 3;
int blockDistance = (((src[srcPos] & 0xF) << 8) | src[srcPos + 1]) + 1;
srcPos += 2;
int blockPos = destPos - blockDistance;
if (destPos + blockSize > destSize || blockPos < 0)
return NULL;
for (int j = 0; j < blockSize; j++)
dest[destPos++] = dest[blockPos + j];
} else {
if (srcPos >= srcSize || destPos >= destSize)
return NULL;
dest[destPos++] = src[srcPos++];
}
if (destPos == destSize) {
*uncompressedSize = destSize;
return dest;
}
flags <<= 1;
}
}
}
unsigned char *LZCompress(unsigned char *src, int srcSize, int *compressedSize)
{
const int minDistance = 2; // for compatibility with LZ77UnCompVram()
if (srcSize <= 0)
return NULL;
int worstCaseDestSize = 4 + srcSize + ((srcSize + 7) / 8);
// Round up to the next multiple of four.
worstCaseDestSize = (worstCaseDestSize + 3) & ~3;
unsigned char *dest = malloc(worstCaseDestSize);
if (dest == NULL)
return NULL;
// header
dest[0] = 0x10; // LZ compression type
dest[1] = (unsigned char)srcSize;
dest[2] = (unsigned char)(srcSize >> 8);
dest[3] = (unsigned char)(srcSize >> 16);
int srcPos = 0;
int destPos = 4;
for (;;) {
unsigned char *flags = &dest[destPos++];
*flags = 0;
for (int i = 0; i < 8; i++) {
int bestBlockDistance = 0;
int bestBlockSize = 0;
int blockDistance = minDistance;
while (blockDistance <= srcPos && blockDistance <= 0x1000) {
int blockStart = srcPos - blockDistance;
int blockSize = 0;
while (blockSize < 18
&& srcPos + blockSize < srcSize
&& src[blockStart + blockSize] == src[srcPos + blockSize])
blockSize++;
if (blockSize > bestBlockSize) {
bestBlockDistance = blockDistance;
bestBlockSize = blockSize;
if (blockSize == 18)
break;
}
blockDistance++;
}
if (bestBlockSize >= 3) {
*flags |= (0x80 >> i);
srcPos += bestBlockSize;
bestBlockSize -= 3;
bestBlockDistance--;
dest[destPos++] = (bestBlockSize << 4) | ((unsigned int)bestBlockDistance >> 8);
dest[destPos++] = (unsigned char)bestBlockDistance;
} else {
dest[destPos++] = src[srcPos++];
}
if (srcPos == srcSize) {
// Pad to multiple of 4 bytes.
int remainder = destPos % 4;
if (remainder != 0) {
for (int i = 0; i < 4 - remainder; i++)
dest[destPos++] = 0;
}
*compressedSize = destPos;
return dest;
}
}
}
}
|
