Debian Codegraph @

nall/beat/delta.hpp

raw
1 #ifndef NALL_BEAT_DELTA_HPP
2 #define NALL_BEAT_DELTA_HPP
3
4 #include <nall/crc32.hpp>
5 #include <nall/file.hpp>
6 #include <nall/filemap.hpp>
7 #include <nall/stdint.hpp>
8 #include <nall/string.hpp>
9
10 namespace nall {
11
12 struct bpsdelta {
13 inline void source(const uint8_t* data, unsigned size);
14 inline void target(const uint8_t* data, unsigned size);
15
16 inline bool source(const string& filename);
17 inline bool target(const string& filename);
18 inline bool create(const string& filename, const string& metadata = "");
19
20 protected:
21 enum : unsigned { SourceRead, TargetRead, SourceCopy, TargetCopy };
22 enum : unsigned { Granularity = 1 };
23
24 struct Node {
25 unsigned offset = 0;
26 Node* next = nullptr;
27 Node() = default;
28 ~Node() { if(next) delete next; }
29 };
30
31 filemap sourceFile;
32 const uint8_t* sourceData;
33 unsigned sourceSize;
34
35 filemap targetFile;
36 const uint8_t* targetData;
37 unsigned targetSize;
38 };
39
40 void bpsdelta::source(const uint8_t* data, unsigned size) {
41 sourceData = data;
42 sourceSize = size;
43 }
44
45 void bpsdelta::target(const uint8_t* data, unsigned size) {
46 targetData = data;
47 targetSize = size;
48 }
49
50 bool bpsdelta::source(const string& filename) {
51 if(sourceFile.open(filename, filemap::mode::read) == false) return false;
52 source(sourceFile.data(), sourceFile.size());
53 return true;
54 }
55
56 bool bpsdelta::target(const string& filename) {
57 if(targetFile.open(filename, filemap::mode::read) == false) return false;
58 target(targetFile.data(), targetFile.size());
59 return true;
60 }
61
62 bool bpsdelta::create(const string& filename, const string& metadata) {
63 file modifyFile;
64 if(modifyFile.open(filename, file::mode::write) == false) return false;
65
66 uint32_t sourceChecksum = ~0, modifyChecksum = ~0;
67 unsigned sourceRelativeOffset = 0, targetRelativeOffset = 0, outputOffset = 0;
68
69 auto write = [&](uint8_t data) {
70 modifyFile.write(data);
71 modifyChecksum = crc32_adjust(modifyChecksum, data);
72 };
73
74 auto encode = [&](uint64_t data) {
75 while(true) {
76 uint64_t x = data & 0x7f;
77 data >>= 7;
78 if(data == 0) {
79 write(0x80 | x);
80 break;
81 }
82 write(x);
83 data--;
84 }
85 };
86
87 write('B');
88 write('P');
89 write('S');
90 write('1');
91
92 encode(sourceSize);
93 encode(targetSize);
94
95 unsigned markupSize = metadata.length();
96 encode(markupSize);
97 for(unsigned n = 0; n < markupSize; n++) write(metadata[n]);
98
99 Node* sourceTree[65536];
100 Node* targetTree[65536];
101 for(unsigned n = 0; n < 65536; n++) sourceTree[n] = nullptr, targetTree[n] = nullptr;
102
103 //source tree creation
104 for(unsigned offset = 0; offset < sourceSize; offset++) {
105 uint16_t symbol = sourceData[offset + 0];
106 sourceChecksum = crc32_adjust(sourceChecksum, symbol);
107 if(offset < sourceSize - 1) symbol |= sourceData[offset + 1] << 8;
108 Node *node = new Node;
109 node->offset = offset;
110 node->next = sourceTree[symbol];
111 sourceTree[symbol] = node;
112 }
113
114 unsigned targetReadLength = 0;
115
116 auto targetReadFlush = [&]() {
117 if(targetReadLength) {
118 encode(TargetRead | ((targetReadLength - 1) << 2));
119 unsigned offset = outputOffset - targetReadLength;
120 while(targetReadLength) write(targetData[offset++]), targetReadLength--;
121 }
122 };
123
124 while(outputOffset < targetSize) {
125 unsigned maxLength = 0, maxOffset = 0, mode = TargetRead;
126
127 uint16_t symbol = targetData[outputOffset + 0];
128 if(outputOffset < targetSize - 1) symbol |= targetData[outputOffset + 1] << 8;
129
130 { //source read
131 unsigned length = 0, offset = outputOffset;
132 while(offset < sourceSize && offset < targetSize && sourceData[offset] == targetData[offset]) {
133 length++;
134 offset++;
135 }
136 if(length > maxLength) maxLength = length, mode = SourceRead;
137 }
138
139 { //source copy
140 Node* node = sourceTree[symbol];
141 while(node) {
142 unsigned length = 0, x = node->offset, y = outputOffset;
143 while(x < sourceSize && y < targetSize && sourceData[x++] == targetData[y++]) length++;
144 if(length > maxLength) maxLength = length, maxOffset = node->offset, mode = SourceCopy;
145 node = node->next;
146 }
147 }
148
149 { //target copy
150 Node* node = targetTree[symbol];
151 while(node) {
152 unsigned length = 0, x = node->offset, y = outputOffset;
153 while(y < targetSize && targetData[x++] == targetData[y++]) length++;
154 if(length > maxLength) maxLength = length, maxOffset = node->offset, mode = TargetCopy;
155 node = node->next;
156 }
157
158 //target tree append
159 node = new Node;
160 node->offset = outputOffset;
161 node->next = targetTree[symbol];
162 targetTree[symbol] = node;
163 }
164
165 { //target read
166 if(maxLength < 4) {
167 maxLength = min((unsigned)Granularity, targetSize - outputOffset);
168 mode = TargetRead;
169 }
170 }
171
172 if(mode != TargetRead) targetReadFlush();
173
174 switch(mode) {
175 case SourceRead:
176 encode(SourceRead | ((maxLength - 1) << 2));
177 break;
178 case TargetRead:
179 //delay write to group sequential TargetRead commands into one
180 targetReadLength += maxLength;
181 break;
182 case SourceCopy:
183 case TargetCopy:
184 encode(mode | ((maxLength - 1) << 2));
185 signed relativeOffset;
186 if(mode == SourceCopy) {
187 relativeOffset = maxOffset - sourceRelativeOffset;
188 sourceRelativeOffset = maxOffset + maxLength;
189 } else {
190 relativeOffset = maxOffset - targetRelativeOffset;
191 targetRelativeOffset = maxOffset + maxLength;
192 }
193 encode((relativeOffset < 0) | (abs(relativeOffset) << 1));
194 break;
195 }
196
197 outputOffset += maxLength;
198 }
199
200 targetReadFlush();
201
202 sourceChecksum = ~sourceChecksum;
203 for(unsigned n = 0; n < 32; n += 8) write(sourceChecksum >> n);
204 uint32_t targetChecksum = crc32_calculate(targetData, targetSize);
205 for(unsigned n = 0; n < 32; n += 8) write(targetChecksum >> n);
206 uint32_t outputChecksum = ~modifyChecksum;
207 for(unsigned n = 0; n < 32; n += 8) write(outputChecksum >> n);
208
209 modifyFile.close();
210 return true;
211 }
212
213 }
214
215 #endif