Debian Codegraph @

extra/BruteForceRNC1Encoder.cpp

raw
1 /* Copyright (C) Teemu Suutari */
2
3 // This is really quick and dirty. Works though
4
5 #include <memory>
6
7 #include <cstdint>
8 #include <cstring>
9
10 #include <fstream>
11 #include <vector>
12 #include <string>
13 #include <algorithm>
14 #include <functional>
15
16 #include <cstdio>
17 #include <dirent.h>
18 #include <sys/stat.h>
19
20 #include "common/Buffer.hpp"
21 #include "common/SubBuffer.hpp"
22
23 #define FUZZY_BLOCK_CUT_THRESHOLD (256)
24
25 namespace ancient::internal
26 {
27
28 class VectorBuffer : public Buffer
29 {
30 public:
31 VectorBuffer();
32
33 virtual ~VectorBuffer() override final;
34
35 virtual const uint8_t *data() const noexcept override final;
36 virtual uint8_t *data() override final;
37 virtual size_t size() const noexcept override final;
38
39 virtual bool isResizable() const noexcept override final;
40 virtual void resize(size_t newSize) override final;
41
42 private:
43 std::vector<uint8_t> _data;
44 };
45
46 VectorBuffer::VectorBuffer()
47 {
48 // nothing needed
49 }
50
51 VectorBuffer::~VectorBuffer()
52 {
53 // nothing needed
54 }
55
56 const uint8_t *VectorBuffer::data() const noexcept
57 {
58 return _data.data();
59 }
60
61 uint8_t *VectorBuffer::data()
62 {
63 return _data.data();
64 }
65
66 size_t VectorBuffer::size() const noexcept
67 {
68 return _data.size();
69 }
70
71 bool VectorBuffer::isResizable() const noexcept
72 {
73 return true;
74 }
75
76 void VectorBuffer::resize(size_t newSize)
77 {
78 return _data.resize(newSize);
79 }
80
81 std::unique_ptr<Buffer> readFile(const std::string &fileName)
82 {
83
84 std::unique_ptr<Buffer> ret=std::make_unique<VectorBuffer>();
85 std::ifstream file(fileName.c_str(),std::ios::in|std::ios::binary);
86 bool success=false;
87 if (file.is_open())
88 {
89 file.seekg(0,std::ios::end);
90 size_t length=size_t(file.tellg());
91 file.seekg(0,std::ios::beg);
92 ret->resize(length);
93 file.read(reinterpret_cast<char*>(ret->data()),length);
94 success=bool(file);
95 if (!success) ret->resize(0);
96 file.close();
97 }
98 if (!success)
99 {
100 fprintf(stderr,"Could not read file %s\n",fileName.c_str());
101 }
102 return ret;
103 }
104
105 bool writeFile(const std::string &fileName,const Buffer &content)
106 {
107 bool ret=false;
108 std::ofstream file(fileName.c_str(),std::ios::out|std::ios::binary|std::ios::trunc);
109 if (file.is_open()) {
110 file.write(reinterpret_cast<const char*>(content.data()),content.size());
111 ret=bool(file);
112 file.close();
113 }
114 if (!ret)
115 {
116 fprintf(stderr,"Could not write file %s\n",fileName.c_str());
117 }
118 return ret;
119 }
120
121 uint16_t RNCCRC(const uint8_t *buffer,size_t len)
122 {
123 // bit reversed 16bit CRC with 0x8005 polynomial
124 static const uint16_t CRCTable[256]={
125 0x0000,0xc0c1,0xc181,0x0140,0xc301,0x03c0,0x0280,0xc241,0xc601,0x06c0,0x0780,0xc741,0x0500,0xc5c1,0xc481,0x0440,
126 0xcc01,0x0cc0,0x0d80,0xcd41,0x0f00,0xcfc1,0xce81,0x0e40,0x0a00,0xcac1,0xcb81,0x0b40,0xc901,0x09c0,0x0880,0xc841,
127 0xd801,0x18c0,0x1980,0xd941,0x1b00,0xdbc1,0xda81,0x1a40,0x1e00,0xdec1,0xdf81,0x1f40,0xdd01,0x1dc0,0x1c80,0xdc41,
128 0x1400,0xd4c1,0xd581,0x1540,0xd701,0x17c0,0x1680,0xd641,0xd201,0x12c0,0x1380,0xd341,0x1100,0xd1c1,0xd081,0x1040,
129 0xf001,0x30c0,0x3180,0xf141,0x3300,0xf3c1,0xf281,0x3240,0x3600,0xf6c1,0xf781,0x3740,0xf501,0x35c0,0x3480,0xf441,
130 0x3c00,0xfcc1,0xfd81,0x3d40,0xff01,0x3fc0,0x3e80,0xfe41,0xfa01,0x3ac0,0x3b80,0xfb41,0x3900,0xf9c1,0xf881,0x3840,
131 0x2800,0xe8c1,0xe981,0x2940,0xeb01,0x2bc0,0x2a80,0xea41,0xee01,0x2ec0,0x2f80,0xef41,0x2d00,0xedc1,0xec81,0x2c40,
132 0xe401,0x24c0,0x2580,0xe541,0x2700,0xe7c1,0xe681,0x2640,0x2200,0xe2c1,0xe381,0x2340,0xe101,0x21c0,0x2080,0xe041,
133 0xa001,0x60c0,0x6180,0xa141,0x6300,0xa3c1,0xa281,0x6240,0x6600,0xa6c1,0xa781,0x6740,0xa501,0x65c0,0x6480,0xa441,
134 0x6c00,0xacc1,0xad81,0x6d40,0xaf01,0x6fc0,0x6e80,0xae41,0xaa01,0x6ac0,0x6b80,0xab41,0x6900,0xa9c1,0xa881,0x6840,
135 0x7800,0xb8c1,0xb981,0x7940,0xbb01,0x7bc0,0x7a80,0xba41,0xbe01,0x7ec0,0x7f80,0xbf41,0x7d00,0xbdc1,0xbc81,0x7c40,
136 0xb401,0x74c0,0x7580,0xb541,0x7700,0xb7c1,0xb681,0x7640,0x7200,0xb2c1,0xb381,0x7340,0xb101,0x71c0,0x7080,0xb041,
137 0x5000,0x90c1,0x9181,0x5140,0x9301,0x53c0,0x5280,0x9241,0x9601,0x56c0,0x5780,0x9741,0x5500,0x95c1,0x9481,0x5440,
138 0x9c01,0x5cc0,0x5d80,0x9d41,0x5f00,0x9fc1,0x9e81,0x5e40,0x5a00,0x9ac1,0x9b81,0x5b40,0x9901,0x59c0,0x5880,0x9841,
139 0x8801,0x48c0,0x4980,0x8941,0x4b00,0x8bc1,0x8a81,0x4a40,0x4e00,0x8ec1,0x8f81,0x4f40,0x8d01,0x4dc0,0x4c80,0x8c41,
140 0x4400,0x84c1,0x8581,0x4540,0x8701,0x47c0,0x4680,0x8641,0x8201,0x42c0,0x4380,0x8341,0x4100,0x81c1,0x8081,0x4040};
141
142 uint16_t retValue=0;
143 for (size_t i=0;i<len;i++)
144 retValue=(retValue>>8)^CRCTable[(retValue&0xff)^buffer[i]];
145 return retValue;
146 }
147
148 // this is really really quick 'n dirty
149 // leeway is suspicious. I can't see it from the official RNC ProPack, but seems to be present elsewhere...
150 void packRNC(Buffer &dest,const Buffer &source,uint32_t chunkSize)
151 {
152 if (!chunkSize) chunkSize=32768; // seems to be a good default
153 if (chunkSize>65536) chunkSize=65536;
154 if (chunkSize<4096) chunkSize=4096;
155
156 std::vector<uint8_t> stream(20);
157 stream[0]='R';
158 stream[1]='N';
159 stream[2]='C';
160 stream[3]=1;
161
162 stream[4]=uint8_t(source.size()>>24);
163 stream[5]=uint8_t(source.size()>>16);
164 stream[6]=uint8_t(source.size()>>8);
165 stream[7]=uint8_t(source.size());
166
167 stream[8]=stream[9]=stream[10]=stream[11]=0;
168
169 uint16_t rawCrc=RNCCRC(source.data(),source.size());
170 stream[12]=uint8_t(rawCrc>>8);
171 stream[13]=uint8_t(rawCrc);
172
173 stream[14]=stream[15]=stream[16]=stream[17]=0;
174
175 stream[18]=stream[19]=0;
176 uint32_t bitStreamPosition=18;
177 uint32_t bitAccumContent=0;
178 uint32_t bitAccumCount=2;
179
180
181 uint32_t offset=0;
182 uint32_t chunkCount=0;
183 uint32_t leeway=0;
184 while (offset!=source.size())
185 {
186 auto bitLength=[](uint32_t value)->uint32_t
187 {
188 uint32_t ret=0;
189 while (value)
190 {
191 value>>=1;
192 ret++;
193 }
194 return ret;
195 };
196
197 // returns code, extra bits, value
198 auto packValue=[&](uint32_t value)->std::tuple<uint32_t,uint32_t,uint32_t>
199 {
200 if (value<2)
201 return std::tuple<uint32_t,uint32_t,uint32_t>{value,0,0};
202 uint32_t bits=bitLength(value)-1;
203 value&=(1<<bits)-1;
204 return std::tuple<uint32_t,uint32_t,uint32_t>{bits+1,bits,value};
205 };
206
207 // bruteforce!!!
208 // returns length,offset
209 auto findLongestRepeat=[&](const uint8_t *buf,uint32_t offset,uint32_t length)->std::pair<uint32_t,uint32_t>
210 {
211 auto comparablePackedSize=[&](uint32_t value)->uint32_t
212 {
213 if (value<2) return 1;
214 // fuzzy cost addition for longer codes
215 return bitLength(value)+(bitLength(bitLength(value))<<1U);
216 };
217
218 std::pair<uint32_t,uint32_t> best{0,0};
219
220 uint32_t distance=1;
221 while (distance<=offset && distance<=chunkSize)
222 {
223 uint32_t i=0;
224 while (offset+i<length && buf[offset+i]==buf[offset+i-distance])
225 i++;
226 if (i>=2 && (comparablePackedSize(i-2)+comparablePackedSize(distance-1)+best.first*8<comparablePackedSize(best.first-2)+comparablePackedSize(best.second-1)+i*8)
227 // fuzzy cost addition for shorter blocks (extra literal turnaround)
228 && (comparablePackedSize(i-2)+comparablePackedSize(distance-1))+5<i*8 )
229 {
230 best=std::make_pair(i,distance);
231 }
232 distance+=1;
233 }
234 return best;
235 };
236
237 std::vector<uint32_t> litFrequencies(32,0);
238 std::vector<uint32_t> distanceFrequencies(32,0);
239 std::vector<uint32_t> lengthFrequencies(32,0);
240
241 // this is what makes this implementation even more bruteforce
242 // table index (lit=0,distance=1,length=2,byte=3,bits=4), code, extra bits, value
243 std::vector<std::tuple<uint32_t,uint32_t,uint32_t,uint32_t>> rawChunk;
244
245 uint32_t litCountOffset=0;
246 bool litActive=false;
247
248 // sub count
249 rawChunk.push_back(std::tuple<uint32_t,uint32_t,uint32_t,uint32_t>{4,0,16,0});
250
251 auto packLit=[&]()
252 {
253 auto pack=packValue(std::get<3>(rawChunk[litCountOffset]));
254 std::get<1>(rawChunk[litCountOffset])=std::get<0>(pack);
255 std::get<2>(rawChunk[litCountOffset])=std::get<1>(pack);
256 std::get<3>(rawChunk[litCountOffset])=std::get<2>(pack);
257 litFrequencies[std::get<0>(pack)]+=1;
258 };
259
260 uint32_t foundLength=1;
261 uint32_t currentChunkSize=std::min(uint32_t(source.size())-offset,chunkSize);
262 for (uint32_t i=offset;i<currentChunkSize+offset;i+=foundLength)
263 {
264 auto fuzzyBreak=[&]()->bool
265 {
266 if (i+FUZZY_BLOCK_CUT_THRESHOLD>=currentChunkSize+offset)
267 {
268 currentChunkSize=i+foundLength-offset;
269 return true;
270 }
271 return false;
272 };
273
274 if (!litActive)
275 {
276 // literal count
277 litCountOffset=uint32_t(rawChunk.size());
278 rawChunk.push_back(std::tuple<uint32_t,uint32_t,uint32_t,uint32_t>{0,0,0,0});
279 litActive=true;
280
281 std::get<3>(rawChunk[0])+=1;
282 }
283
284 auto repeat=findLongestRepeat(source.data(),i,currentChunkSize+offset);
285 if (repeat.first)
286 {
287 packLit();
288 litActive=false;
289 auto dist=packValue(repeat.second-1);
290 rawChunk.push_back(std::tuple<uint32_t,uint32_t,uint32_t,uint32_t>{1,std::get<0>(dist),std::get<1>(dist),std::get<2>(dist)});
291 distanceFrequencies[std::get<0>(dist)]+=1;
292 auto count=packValue(repeat.first-2);
293 rawChunk.push_back(std::tuple<uint32_t,uint32_t,uint32_t,uint32_t>{2,std::get<0>(count),std::get<1>(count),std::get<2>(count)});
294 lengthFrequencies[std::get<0>(count)]+=1;
295 foundLength=repeat.first;
296 } else {
297 rawChunk.push_back(std::tuple<uint32_t,uint32_t,uint32_t,uint32_t>{3,source.data()[i],0,0});
298 std::get<3>(rawChunk[litCountOffset])+=1;
299 foundLength=1;
300 if (/*std::get<3>(rawChunk[litCountOffset])==1 &&*/ fuzzyBreak()) break;
301 }
302 }
303 if (litActive)
304 {
305 packLit();
306 } else {
307 litCountOffset=uint32_t(rawChunk.size());
308 rawChunk.push_back(std::tuple<uint32_t,uint32_t,uint32_t,uint32_t>{0,0,0,0});
309 packLit();
310
311 std::get<3>(rawChunk[0])+=1;
312 }
313 offset+=currentChunkSize;
314 chunkCount++;
315
316 std::function<void(uint32_t,uint32_t)> writeBits=[&](uint32_t bitCount,uint32_t bits)
317 {
318 if (!bitCount) return;
319 if (bitCount+bitAccumCount>16)
320 {
321 uint32_t bitsToWrite=16-bitAccumCount;
322 writeBits(bitsToWrite,bits&((1<<bitsToWrite)-1));
323 bits>>=bitsToWrite;
324 bitCount-=bitsToWrite;
325 }
326 if (!bitAccumCount)
327 {
328 bitStreamPosition=uint32_t(stream.size());
329 stream.push_back(0);
330 stream.push_back(0);
331 }
332 bitAccumContent|=bits<<bitAccumCount;
333 bitAccumCount+=bitCount;
334 if (bitAccumCount==16)
335 {
336 stream[bitStreamPosition]=bitAccumContent;
337 stream[bitStreamPosition+1]=bitAccumContent>>8;
338 bitAccumContent=0;
339 bitAccumCount=0;
340 }
341 };
342
343 auto writeByte=[&](uint8_t byte)
344 {
345 stream.push_back(byte);
346 };
347
348 // also writes table to stream
349 // result vector is code, length pairs
350 auto createHuffmanCodeTable=[&](std::vector<std::pair<uint32_t,uint32_t>> &codes,const std::vector<uint32_t> &frequencies)
351 {
352 std::vector<std::pair<uint32_t,uint32_t>> sortedList;
353 uint32_t totalCount=0;
354 uint32_t totalFreq=0;
355 for (uint32_t i=0;i<frequencies.size();i++)
356 {
357 totalFreq+=frequencies[i];
358 if (frequencies[i])
359 {
360 totalCount=i+1;
361 sortedList.push_back(std::make_pair(i,frequencies[i]));
362 }
363 }
364 writeBits(5,totalCount);
365 if (!totalCount) return;
366 std::sort(sortedList.begin(),sortedList.end(),[&](const auto &a,const auto &b){return a.second>b.second||(a.second==b.second&&a.first<b.first);});
367
368 // convert frequencies to bit length
369 const uint32_t initialNorm=1<<30;
370 uint32_t totalUsed=0;
371 uint32_t sortedFrequencies[totalCount];
372 for (uint32_t i=0;i<sortedList.size();i++)
373 {
374 uint32_t bitCount=1; // extra +1 for later tuning
375 uint32_t tmp=sortedList[i].second;
376 sortedFrequencies[i]=tmp;
377 while (tmp<totalFreq)
378 {
379 tmp<<=1;
380 bitCount++;
381 }
382 sortedList[i].second=bitCount;
383 totalUsed+=initialNorm>>bitCount;
384 }
385
386 // use the full range
387 while (totalUsed!=initialNorm)
388 {
389 uint32_t bestIndex=totalCount;
390 uint32_t bestImprovement=0;
391
392 for (uint32_t i=0;i<sortedList.size();i++)
393 {
394 if (totalUsed+(initialNorm>>sortedList[i].second)<=initialNorm)
395 {
396 // adding cost factor here too
397 uint32_t improvement=sortedFrequencies[i]<<sortedList[i].second;
398 if (improvement>bestImprovement)
399 {
400 bestIndex=i;
401 bestImprovement=improvement;
402 }
403 }
404 }
405 if (bestIndex==totalCount) break;
406 totalUsed+=initialNorm>>sortedList[bestIndex].second;
407 sortedList[bestIndex].second-=1;
408 }
409
410 // using the full range will sometimes result out-of-order indexes
411 std::sort(sortedList.begin(),sortedList.end(),[&](const auto &a,const auto &b){return a.second<b.second||(a.second==b.second&&a.first<b.first);});
412
413 uint32_t maxDepth=0;
414 for (uint32_t i=0;i<sortedList.size();i++)
415 maxDepth=std::max(maxDepth,sortedList[i].second);
416
417 uint32_t value=0;
418 for (uint32_t i=0;i<sortedList.size();i++)
419 {
420 auto reverseBits=[](uint32_t bitCount,uint32_t bits)->uint32_t
421 {
422 uint32_t ret=0;
423 while (bitCount--)
424 {
425 ret<<=1;
426 ret|=bits&1;
427 bits>>=1;
428 }
429 return ret;
430 };
431
432 uint32_t code=sortedList[i].first;
433 codes[code].first=reverseBits(maxDepth,value);
434 codes[code].second=sortedList[i].second;
435 value+=1<<(maxDepth-sortedList[i].second);
436 }
437 for (uint32_t i=0;i<totalCount;i++) writeBits(4,codes[i].second);
438 };
439
440 // code, length pairs
441 std::vector<std::pair<uint32_t,uint32_t>> litCodes(32,std::make_pair(0,0));
442 std::vector<std::pair<uint32_t,uint32_t>> distanceCodes(32,std::make_pair(0,0));
443 std::vector<std::pair<uint32_t,uint32_t>> lengthCodes(32,std::make_pair(0,0));
444
445 uint32_t streamStart=uint32_t(stream.size());
446 createHuffmanCodeTable(litCodes,litFrequencies);
447 createHuffmanCodeTable(distanceCodes,distanceFrequencies);
448 createHuffmanCodeTable(lengthCodes,lengthFrequencies);
449
450 for (uint32_t i=0;i<uint32_t(rawChunk.size());i++)
451 {
452 switch (std::get<0>(rawChunk[i]))
453 {
454 // literal
455 case 0:
456 writeBits(litCodes[std::get<1>(rawChunk[i])].second,litCodes[std::get<1>(rawChunk[i])].first);
457 writeBits(std::get<2>(rawChunk[i]),std::get<3>(rawChunk[i]));
458 break;
459
460 // distance
461 case 1:
462 writeBits(distanceCodes[std::get<1>(rawChunk[i])].second,distanceCodes[std::get<1>(rawChunk[i])].first);
463 writeBits(std::get<2>(rawChunk[i]),std::get<3>(rawChunk[i]));
464 break;
465
466 // length
467 case 2:
468 writeBits(lengthCodes[std::get<1>(rawChunk[i])].second,lengthCodes[std::get<1>(rawChunk[i])].first);
469 writeBits(std::get<2>(rawChunk[i]),std::get<3>(rawChunk[i]));
470 break;
471
472 // bytes
473 case 3:
474 writeByte(std::get<1>(rawChunk[i]));
475 break;
476
477 // bits
478 case 4:
479 writeBits(std::get<2>(rawChunk[i]),std::get<3>(rawChunk[i]));
480 break;
481
482 default:
483 break;
484 }
485 }
486 uint32_t outputLength=uint32_t(stream.size())-streamStart;
487 if (currentChunkSize>outputLength && outputLength-outputLength>leeway)
488 leeway=outputLength-outputLength;
489 }
490
491 if (bitAccumCount)
492 {
493 stream[bitStreamPosition]=bitAccumContent;
494 stream[bitStreamPosition+1]=bitAccumContent>>8;
495 if (bitStreamPosition==stream.size()-2 && bitAccumCount<=8)
496 stream.pop_back();
497 }
498
499 uint32_t packedSize=uint32_t(stream.size()-18);
500 stream[8]=uint8_t(packedSize>>24);
501 stream[9]=uint8_t(packedSize>>16);
502 stream[10]=uint8_t(packedSize>>8);
503 stream[11]=uint8_t(packedSize);
504
505 uint16_t packedCrc=RNCCRC(stream.data()+18,packedSize);
506 stream[14]=uint8_t(packedCrc>>8);
507 stream[15]=uint8_t(packedCrc);
508
509 if (leeway>255)
510 {
511 fprintf(stderr,"Leeway larger than 255\n");
512 exit(-1);
513 }
514
515 stream[16]=leeway;
516 stream[17]=chunkCount;
517
518 dest.resize(stream.size());
519 std::memcpy(dest.data(),stream.data(),stream.size());
520 }
521
522 int main(int argc,char **argv)
523 {
524 auto usage=[]()
525 {
526 fprintf(stderr,"Usage: <prog> input_raw output_packed [chunk_size]\n");
527 };
528
529 if (argc<3)
530 {
531 usage();
532 return -1;
533 }
534
535 auto raw{readFile(argv[1])};
536
537 VectorBuffer packed;
538 packRNC(packed,*raw,(argc>=4)?atoi(argv[3]):0);
539
540 writeFile(argv[2],packed);
541 return 0;
542 }
543
544 }
545
546 int main(int argc,char **argv)
547 {
548 return ancient::internal::main(argc,argv);
549 }