fork/slippc

git clone https://git.julia.blue/fork/slippc

Patrick CrainUnify version strings between parser, analyzer, and compressor into SLIPPC_VERSION46ef8c0

0.8.1
42.8 KiB1086 linesraw
1#ifndef COMPRESSOR_H_
2#define COMPRESSOR_H_
3
4#include <iostream>
5#include <fstream>
6#include <sstream>
7#include <regex>
8#include <map>
9#include <cmath>
10#include <limits>
11#include <cstdio>
12#include <filesystem>
13
14#include "util.h"
15#include "enums.h"
16#include "schema.h"
17#include "gecko-legacy.h"
18
19// Replay File (.slp) Spec: https://github.com/project-slippi/slippi-wiki/blob/master/SPEC.md
20
21const uint8_t  COMPRETZ_VERSION      = 2;           //Internal version of this compressor
22
23const uint32_t RAW_RNG_MASK          = 0x40000000;  //Second bit of unsigned int
24const uint32_t MAGIC_FLOAT           = 0xFF000000;  //First 8 bits of float
25const uint32_t EXPONENT_BITS         = 0x7F800000;  //Exponent bits 2-9 of a float
26const uint32_t DEFER_ITEM_BITS       = 0xC000;      //Bitmask for storing deferred writes of items
27
28const uint32_t ITEM_SLOTS            = 256;         //Max number of items we expect to track at once
29const uint32_t MESSAGE_SIZE          = 517;         //Size of Message Splitter event
30const uint32_t MAX_ITEMS_C           = 2048;        //Max number of items to track initially
31const uint32_t MAX_ROLLBACK          = 128;         //Max number of frames game can roll back
32const int      RB_SIZE               = 4;           //Size of circular queue for tracking repeated frames
33
34const int      FRAME_ENC_DELTA       = 1;           //Delta when predicting and encoding next frame
35const int      ALLOC_EVENTS          = 100000;      //Number of events to initially allocate space for shuffling
36
37namespace slip {
38
39class Compressor {
40private:
41
42  int             _debug;                         //Current debug level
43  uint16_t        _payload_sizes[256] = {0};      //Size of payload for each event
44  uint8_t         _slippi_maj         =  0;       //Major version number of replay being parsed
45  uint8_t         _slippi_min         =  0;       //Minor version number of replay being parsed
46  uint8_t         _slippi_rev         =  0;       //Revision number of replay being parsed
47  uint8_t         _encode_ver         =  0;       //Encryption status of replay being parsed
48  int32_t         _max_frames         =  0;       //Maximum number of frames that there will be in the replay file
49  std::string*    _outfilename        =  nullptr; //Name of the file to write
50  std::string*    _outgeckofilename   =  nullptr; //Name of gecko file to write
51
52  //Variables needed for mapping floats to ints and vice versa
53  std::map<unsigned,unsigned> float_to_int;  //Map of floats to ints
54  std::map<unsigned,unsigned> int_to_float;  //Reverse map of ints back to floats
55  std::map<unsigned,unsigned> int_to_float_c;//Counter for reverse map of ints back to floats
56  unsigned            num_floats = 0;        //Total number of floats in float map
57
58  uint32_t        _preds = 0;
59  uint32_t        _fails = 0;
60
61  const char*     _infilename = "";
62
63  uint32_t        _rng;                                //Current RNG seed we're working with
64  uint32_t        _rng_start;                          //Starting RNG seed
65  char            _x_pre_frame[8][256]       = {0};    //Delta for pre-frames
66  char            _x_pre_frame_2[8][256]     = {0};    //Delta for 2 pre-frames ago
67  char            _x_post_frame[8][256]      = {0};    //Delta for post-frames
68  char            _x_post_frame_2[8][256]    = {0};    //Delta for 2 post-frames ago
69  char            _x_post_frame_3[8][256]    = {0};    //Delta for 3 post-frames ago
70  char            _x_item[ITEM_SLOTS][256]   = {0};    //Delta for item updates
71  char            _x_item_2[ITEM_SLOTS][256] = {0};    //Delta for item updates 2 frames ago
72  char            _x_item_3[ITEM_SLOTS][256] = {0};    //Delta for item updates 3 frames ago
73  char            _x_item_4[ITEM_SLOTS][256] = {0};    //Delta for item updates 4 frames ago
74  char            _x_item_p[ITEM_SLOTS][256] = {0};    //Delta for item position updates
75  int32_t         laststartframe             = -123;   //Last frame used in frame start event, encoding
76  int32_t         lastitemstartframe         = -123;   //Last frame used in item event, encoding
77  int32_t         lastshuffleframe           = -123;   //Last frame used in frame start event, shuffling
78  int32_t         lastitemshuffleframe       = -123;   //Last frame used in item event, shuffling
79  int32_t         lastpreframe[8]            = {-123}; //Last frame used in pre frame event, encoding
80  int32_t         lastshufflepreframe[8]     = {-123}; //Last frame used in pre frame event, shuffling
81  int32_t         lastpostframe[8]           = {-123}; //Last frame used in post frame event, encoding
82  int32_t         lastshufflepostframe[8]    = {-123}; //Last frame used in post frame event, shuffling
83
84  char*           _rb                        = nullptr; //Read buffer
85  char*           _wb                        = nullptr; //Write buffer
86  unsigned        _bp                        = 0;       //Current position in buffer
87  uint32_t        _length_raw                = 0;       //Remaining length of raw payload
88  uint32_t        _length_raw_start          = 0;       //Total length of raw payload
89  uint32_t        _game_loop_start           = 0;       //First byte AFTER game start event
90  uint32_t        _game_loop_end             = 0;       //First byte OF game end event
91  uint32_t        _file_size                 = 0;       //Total size of the replay file on disk
92  uint32_t        _message_count             = 0;       //Number of gecko messages we've parsed thus far
93  bool            _game_end_found            = false;   //Whether we've found the game end event
94
95  // Frame event column byte widths (negative numbers denote bit shuffling)
96  int32_t         _cw_start[5] = {1,4,4,4,0};
97  int32_t         _cw_mesg[6]  = {1,512,2,1,1,0};
98  int32_t         _cw_pre[21]  = {1,4,1,1,4,2,4,4,4,4,4,4,4,4,4,2,4,4,1,4,0};
99  int32_t         _cw_item[21] = {1,4,2,1,4,4,4,4,4,2,4, 1,1,1,1 ,1,1,1,1,1,0}; // Shuffle bytes of item id
100  int32_t         _cw_post[35] = {1,4,1,1,1,2,4,4,4,4,4,1,1,1,1,4,1,1,1,1,1,4,1,2,1,1,1,4,4,4,4,4,4,4,0};
101  int32_t         _cw_end[4]   = {1,4,4,0};
102
103  // Debug Frame event column byte widths (negative numbers denote bit shuffling)
104  int32_t         _dw_start[5] = {1,4,4,4,0};
105  int32_t         _dw_mesg[6]  = {1,512,2,1,1,0};
106  int32_t         _dw_pre[21]  = {1,4,1,1,4,2,4,4,4,4,4,4,4,4,4,2,4,4,1,4,0};
107  int32_t         _dw_item[21] = {1,4,2,1,4,4,4,4,4,2,4, 1,1,1,1 ,1,1,1,1,1,0}; // Shuffle bytes of item id
108  int32_t         _dw_post[35] = {1,4,1,1,1,2,4,4,4,4,4,1,1,1,1,4,1,1,1,1,1,4,1,2,1,1,1,4,4,4,4,4,4,4,0};
109  int32_t         _dw_end[4]   = {1,4,4,0};
110
111  bool            _parse();             //Internal main parsing funnction
112  bool            _parseHeader();
113  bool            _parseEventDescriptions();
114  bool            _parseEvents();
115  bool            _parseGameStart();
116  bool            _parseGeckoCodes();
117  bool            _parsePreFrame();
118  bool            _parsePostFrame();
119  bool            _parseFrameStart();
120  bool            _parseItemUpdate();
121  bool            _parseBookend();
122  bool            _shuffleEvents(bool unshuffle = false);
123  bool            _unshuffleEvents();
124
125public:
126  Compressor(int debug_level);                     //Instantiate the parser (possibly in debug mode)
127  ~Compressor();                                   //Destroy the parser
128  bool loadFromFile(const char* replayfilename);   //Load a replay file
129  void saveToFile(bool rawencode);              //Save an encoded replay file
130  bool setOutputFilename(const char* fname);       //Set output file name
131  bool setGeckoOutputFilename(const char* fname);  //Set gecko code output filename
132  bool loadFromBuff(char** buffer, unsigned size); //Load a replay from a buffer
133  unsigned saveToBuff(char** buffer);              //Save an encoded replay buffer
134  bool validate();                                 //Validate the encoding
135
136  //https://www.reddit.com/r/SSBM/comments/71gn1d/the_basics_of_rng_in_melee/
137  inline int32_t rollRNGLegacy(int32_t seed) const {
138    int64_t bigseed = seed;  //Cast from 32-bit to 64-bit int
139    return ((bigseed * 214013) + 2531011) % 4294967296;
140  }
141
142  //Given the current frame's RNG value, just add 65536 to get the next frame's
143  inline int32_t rollRNGRollback(int32_t seed) const {
144    return (seed + 65536) % 4294967296;
145  }
146
147  //Per Fizzi and Nikki, RNG is just the starting RNG + 65536*<0-indexed frame>
148  inline int32_t computeRNGRollback(int32_t framenum) const {
149    return (((framenum+123) * 65536) + _rng_start) % 4294967296;
150  }
151
152  //Check the RAW_RNG_MASK bit from a frame, and return whether that bit was flipped
153  inline bool checkRawRNG(int32_t &frame) const {
154    //If first and second bits of frame are different, rng is stored raw
155    uint8_t bit1 = (frame >> 31) & 0x01;
156    uint8_t bit2 = (frame >> 30) & 0x01;
157    uint8_t rng_is_raw = bit1 ^ bit2;
158    return rng_is_raw > 0;
159  }
160
161  //Predict the next frame given a reference frame and delta encode the difference
162  inline int32_t predictFrame(int32_t frame, int32_t ref_frame, char* write_addr = nullptr) const {
163    //Remove RNG bit from frame
164    bool rng_is_raw  = checkRawRNG(frame);
165    if (rng_is_raw) {
166      frame ^= RAW_RNG_MASK;
167    }
168    //Flip 2nd bit in _wb output if raw RNG flag is set
169    uint32_t bitmask = rng_is_raw ? RAW_RNG_MASK : 0x00000000;
170
171    int32_t frame_delta_pred;
172    if (_encode_ver) { //Decode
173      frame_delta_pred = frame + (ref_frame + FRAME_ENC_DELTA);
174      if (write_addr) {
175        writeBE4S(frame_delta_pred ^ bitmask,write_addr);
176      }
177    } else {           //Encode
178      frame_delta_pred = frame - (ref_frame + FRAME_ENC_DELTA);
179      if (write_addr) {
180        writeBE4S(frame_delta_pred,write_addr);
181      }
182    }
183    return frame_delta_pred;
184  }
185
186  //Version of predictFrame used for _unshuffleEvents
187  inline int32_t decodeFrame(int32_t frame, int32_t ref_frame) const {
188    return predictFrame(frame, ref_frame, nullptr);
189  }
190
191  //Create a mapping of floats we've already seen by treating them as unsigned integer indices
192  //  to an index build on-the-fly
193  inline void buildFloatMap(unsigned off) {
194    uint32_t enc_float = readBE4U(&_rb[_bp+off]);
195    if (_encode_ver) {                  //Decode
196      if ((enc_float & MAGIC_FLOAT) != MAGIC_FLOAT) {
197        //If it's our first encounter with a float, add it to our maps
198        float_to_int[enc_float]  = num_floats;
199        int_to_float[num_floats] = enc_float;
200        ++num_floats;
201      } else {
202        //Decode our int back to a float
203        unsigned as_unsigned = int_to_float[enc_float & (MAGIC_FLOAT ^ 0xFFFFFFFF)];
204        writeBE4U(as_unsigned, &_wb[_bp+off]);
205      }
206    } else {                            //Encode
207      if (float_to_int.find(enc_float) == float_to_int.end()) {
208        //If it's our first encounter with a float, add it to our maps
209        float_to_int[enc_float]    = num_floats;
210        int_to_float[num_floats]   = enc_float;
211        int_to_float_c[num_floats] = 1;
212        ++num_floats;
213      } else {
214        //Set the 2nd and 3rd bit, since they will never be set simultaneously in real floats
215        ++int_to_float_c[float_to_int[enc_float]];
216        writeBE4U(float_to_int[enc_float] | MAGIC_FLOAT, &_wb[_bp+off]);
217      }
218    }
219  }
220
221  //Compress analog float values by converting them to ints
222  inline void encodeAnalog(unsigned off, float mult) {
223    union { float f; uint32_t u; uint8_t c[4]; int8_t i[4]; } float_true, float_pred, float_rest;
224
225    // If any of exponent bits are set, we still have a float
226    char* main_buf = _encode_ver ? _wb : _rb;
227    float_true.u   = readBE4U(&main_buf[_bp+off]);
228    if ((float_true.u & EXPONENT_BITS) && _encode_ver) {
229      return;  //If we have a float in the encoded state, nothing to do
230    }
231
232    float_pred.u = 0;  //Initialize all bytes to zero
233    if (_encode_ver) {
234      if (mult > 127) {
235        float_pred.f = float(float_true.c[0])/mult;
236      } else {
237        float_pred.f = float(float_true.i[0])/mult;
238      }
239      writeBE4F(float_pred.f,&_wb[_bp+off]);  //Write our decoded float
240    } else {
241      if (mult > 127) {
242        float_pred.c[0] = uint8_t(round(float(float_true.f*mult)));
243        float_rest.f = float(float_pred.c[0])/mult;
244      } else {
245        float_pred.i[0] = int8_t(round(float(float_true.f*mult)));
246        float_rest.f = float(float_pred.i[0])/mult;
247      }
248      if (float_rest.u == float_true.u) {  //Verify we can properly decode
249        writeBE4U(float_pred.u,&_wb[_bp+off]);  //Write our encoded int
250      }
251    }
252  }
253
254  //General purpose function for encoding the difference
255  //  between floats in two buffers, using a magic float value
256  //  to flag whether such an encoded value is present
257  //  (useful for computing item velocities in terms of positions)
258  inline void predictAsDifference(unsigned off, unsigned buffoff, char* buff) {
259    union { float f; uint32_t u; } float_true, float_pred, float_temp;
260    //If our prediction is accurate to at least the last 10 bits, it's close enough
261    uint32_t MAXDIFF = 0x03FF;
262
263    char* main_buf = _encode_ver ? _wb : _rb;
264
265    float_true.f = readBE4F(&main_buf[_bp+off]);
266    float_pred.f = readBE4F(&main_buf[_bp+buffoff]) - readBE4F(&buff[buffoff]);
267    float_temp.u = float_pred.u ^ float_true.u;
268
269    if (_encode_ver) {
270      uint32_t diff = float_true.u ^ MAGIC_FLOAT;
271      if (diff <= MAXDIFF) {  //If our prediction was accurate to at least the last few bits
272        float_pred.u ^= diff;
273        writeBE4F(float_pred.f,&_wb[_bp+off]);  //Write our predicted float
274      }
275    } else {
276      //If at most the last few bits are off, we succeeded
277      if (float_temp.u <= MAXDIFF) {
278        writeBE4U(MAGIC_FLOAT ^ float_temp.u,&_wb[_bp+off]);  //Write an impossible float
279      } else {
280        // std::cout << "DIFF =" << float_temp.u << std::endl;
281      }
282    }
283
284    memcpy(&buff[buffoff],&main_buf[_bp+buffoff],4);
285  }
286
287  //General purpose function for predicting jolt based
288  //  on float data in four buffers, using a magic float value
289  //  to flag whether such an encoded value is present
290  inline void predictJolt(unsigned p, unsigned off, char* buff1, char* buff2, char* buff3, char* buff4, bool verbose = false) {
291    union { float f; uint32_t u; } float_true, float_pred, float_temp;
292    //If our prediction is accurate to at least the last 8 bits, it's close enough
293    const uint32_t MAXDIFF = 0xFF;
294
295    float_true.f = readBE4F(&_rb[_bp+off]);
296    float pos1   = readBE4F(&buff1[off]);
297    float pos2   = readBE4F(&buff2[off]);
298    float pos3   = readBE4F(&buff3[off]);
299    float pos4   = readBE4F(&buff4[off]);
300    float vel1   = pos1 - pos2;
301    float vel2   = pos2 - pos3;
302    float vel3   = pos3 - pos4;
303    float acc1   = vel1 - vel2;
304    float acc2   = vel2 - vel3;
305    float jlt1   = acc1 - acc2;
306    float_pred.f = pos1 + vel1 + acc1 + jlt1;
307
308    if (_encode_ver) {
309      uint32_t diff = float_true.u ^ MAGIC_FLOAT;
310      if (diff <= MAXDIFF) {  //If our prediction was accurate to at least the last few bits
311        float_pred.u ^= diff;
312        writeBE4F(float_pred.f,&_wb[_bp+off]);  //Write our predicted float
313      }
314    } else {
315      //If at most the last few bits are off, we succeeded
316      if (verbose) {
317        if (float_pred.u==float_true.u) {
318          std::cout << " predicted " << float_pred.f << ", exact" << std::endl;
319        } else {
320          std::streamsize ss = std::cout.precision();
321          std::cout << std::setprecision(30);
322          std::cout << " predicted " << float_pred.f << ", error = " << (float_pred.f-float_true.f) << std::endl;
323          std::cout << "   pos1 " << pos1 << std::endl;
324          std::cout << "   vel1 " << vel1 << std::endl;
325          std::cout << "   acc1 " << acc1 << std::endl;
326          std::cout << "   jlt1 " << jlt1 << std::endl;
327          std::cout << "   pos2 " << pos2 << std::endl;
328          std::cout << "   vel2 " << vel2 << std::endl;
329          std::cout << "   acc2 " << acc2 << std::endl;
330          std::cout << "   pos3 " << pos3 << std::endl;
331          std::cout << "   vel3 " << vel3 << std::endl;
332          std::cout << "   pos4 " << pos4 << std::endl;
333          std::cout << std::setprecision(ss);
334        }
335      }
336      float_temp.u = float_pred.u ^ float_true.u;
337      if (float_temp.u <= MAXDIFF) {
338        if (verbose) {
339          std::cout << "    we compress those " << pos3 << std::endl;
340        }
341        writeBE4U(MAGIC_FLOAT ^ float_temp.u,&_wb[_bp+off]);  //Write an impossible float
342      }
343    }
344
345    memcpy(&buff4[off], &buff3[off],4);
346    memcpy(&buff3[off], &buff2[off],4);
347    memcpy(&buff2[off], &buff1[off],4);
348    memcpy(&buff1[off],_encode_ver ? &_wb[_bp+off] : &_rb[_bp+off],4);
349  }
350
351  //General purpose function for predicting acceleration based
352  //  on float data in three buffers, using a magic float value
353  //  to flag whether such an encoded value is present
354  inline void predictAccel(unsigned p, unsigned off, char* buff1, char* buff2, char* buff3, bool verbose = false) {
355    union { float f; uint32_t u; } float_true, float_pred, float_temp;
356    //If our prediction is accurate to at least the last 8 bits, it's close enough
357    const uint32_t MAXDIFF = 0xFF;
358
359    float_true.f = readBE4F(&_rb[_bp+off]);
360    float pos1   = readBE4F(&buff1[off]);
361    float pos2   = readBE4F(&buff2[off]);
362    float pos3   = readBE4F(&buff3[off]);
363    float vel1   = pos1 - pos2;
364    float vel2   = pos2 - pos3;
365    float acc1   = vel1 - vel2;
366    float_pred.f = pos1 + vel1 + acc1;
367
368    if (_encode_ver) {
369      uint32_t diff = float_true.u ^ MAGIC_FLOAT;
370      if (diff <= MAXDIFF) {  //If our prediction was accurate to at least the last few bits
371        float_pred.u ^= diff;
372        writeBE4F(float_pred.f,&_wb[_bp+off]);  //Write our predicted float
373      }
374    } else {
375      //If at most the last few bits are off, we succeeded
376      if (verbose) {
377        if (float_pred.u==float_true.u) {
378          std::cout << " predicted " << float_pred.f << ", exact" << std::endl;
379        } else {
380          std::streamsize ss = std::cout.precision();
381          std::cout << std::setprecision(30);
382          std::cout << " predicted " << float_pred.f << ", error = " << (float_pred.f-float_true.f) << std::endl;
383          std::cout << "   pos1 " << pos1 << std::endl;
384          std::cout << "   vel1 " << vel1 << std::endl;
385          std::cout << "   acc1 " << acc1 << std::endl;
386          std::cout << "   pos2 " << pos2 << std::endl;
387          std::cout << "   vel2 " << vel2 << std::endl;
388          std::cout << "   pos3 " << pos3 << std::endl;
389          std::cout << std::setprecision(ss);
390        }
391      }
392      float_temp.u = float_pred.u ^ float_true.u;
393      if (float_temp.u <= MAXDIFF) {
394        writeBE4U(MAGIC_FLOAT ^ float_temp.u,&_wb[_bp+off]);  //Write an impossible float
395      }
396    }
397
398    memcpy(&buff3[off], &buff2[off],4);
399    memcpy(&buff2[off], &buff1[off],4);
400    memcpy(&buff1[off],_encode_ver ? &_wb[_bp+off] : &_rb[_bp+off],4);
401  }
402
403  //General purpose function for predicting velocity based
404  //  on float data in two buffers, using a magic float value
405  //  to flag whether such an encoded value is present
406  inline void predictVeloc(unsigned p, unsigned off, char* buff1, char* buff2) {
407    union { float f; uint32_t u; } float_true, float_pred, float_temp;
408
409    float_true.f = readBE4F(&_rb[_bp+off]);
410    float_pred.f = 2*readBE4F(&buff1[off]) - readBE4F(&buff2[off]);
411    float_temp.u = float_pred.u ^ float_true.u;
412    if (_encode_ver) {
413      if (float_true.u == MAGIC_FLOAT) {  //If our prediction was exactly accurate
414        writeBE4F(float_pred.f,&_wb[_bp+off]);  //Write our predicted float
415      }
416    } else {
417      if (float_temp.u == 0) {  //If our prediction was exactly accurate
418        writeBE4U(MAGIC_FLOAT,&_wb[_bp+off]);  //Write an impossible float
419      }
420    }
421
422    memcpy(&buff2[off], &buff1[off],4);
423    memcpy(&buff1[off],_encode_ver ? &_wb[_bp+off] : &_rb[_bp+off],4);
424  }
425
426  //Using the previous four item events as reference, predict a floating point value, and store
427  //  an otherwise-impossible float if our prediction was correct
428  inline void predictJoltItem(unsigned p, unsigned off, bool verbose = false) {
429    predictJolt(p,off,_x_item[p],_x_item_2[p],_x_item_3[p],_x_item_4[p],verbose);
430  }
431
432  //Using the previous three post-frame events as reference, predict a floating point value, and store
433  //  an otherwise-impossible float if our prediction was correct
434  inline void predictAccelPost(unsigned p, unsigned off) {
435    predictAccel(p,off,_x_post_frame[p],_x_post_frame_2[p],_x_post_frame_3[p]);
436  }
437
438  //Using the previous three item events as reference, predict a floating point value, and store
439  //  an otherwise-impossible float if our prediction was correct
440  inline void predictAccelItem(unsigned p, unsigned off, bool verbose = false) {
441    predictAccel(p,off,_x_item[p],_x_item_2[p],_x_item_3[p],verbose);
442  }
443
444  //Using the previous two pre-frame events as reference, predict a floating point value, and store
445  //  an otherwise-impossible float if our prediction was correct
446  inline void predictVelocPre(unsigned p, unsigned off) {
447    predictVeloc(p,off,_x_pre_frame[p],_x_pre_frame_2[p]);
448  }
449
450  //Using the previous two post-frame events as reference, predict a floating point value, and store
451  //  an otherwise-impossible float if our prediction was correct
452  inline void predictVelocPost(unsigned p, unsigned off) {
453    predictVeloc(p,off,_x_post_frame[p],_x_post_frame_2[p]);
454  }
455
456  //Using the previous two item events with slot id as reference, predict a floating point value, and store
457  //  an otherwise-impossible float if our prediction was correct
458  inline void predictVelocItem(unsigned p, unsigned off) {
459    predictVeloc(p,off,_x_item[p],_x_item_2[p]);
460  }
461
462  //Predict the RNG by reading a full (not delta-encoded) frame and
463  //  counting the number of rolls it takes to arrive at the correct seed
464  inline void predictRNG(unsigned frameoff, unsigned rngoff) {
465    const uint32_t MAX_ROLLS = 128;  //must be a power of 2
466
467    //Read true frame from write buffer
468    int32_t frame;
469    if (_encode_ver) {  //Read from write buffer
470      frame = readBE4S(&_wb[_bp+frameoff]);
471    } else {            //Read from read buffer
472      frame = readBE4S(&_rb[_bp+frameoff]);
473    }
474    bool rng_is_raw = checkRawRNG(frame);
475    if (rng_is_raw) {
476      frame ^= RAW_RNG_MASK;
477    }
478
479    //Get RNG seed and record number of rolls it takes to get to that point
480    if (MIN_VERSION(3,6,0)) {  //New RNG
481      _rng = computeRNGRollback(frame);
482      if (_encode_ver) {  //Decode
483        if (rng_is_raw == 0) { //Roll RNG a few times until we get to the desired value
484          unsigned rolls = readBE4U(&_rb[_bp+rngoff]);
485          if (rolls < MAX_ROLLS) {
486            for(unsigned i = 0; i < rolls; ++i) {
487              _rng = rollRNGRollback(_rng);
488            }
489          } else {  //Fallback on old RNG rolling method
490            for(unsigned i = MAX_ROLLS; i < rolls; ++i) {
491              _rng = rollRNGLegacy(_rng);
492            }
493          }
494          writeBE4U(_rng,&_wb[_bp+rngoff]);
495        } else {
496          writeBE4U(frame,&_wb[_bp+frameoff]);
497        }
498      } else {  //Encode
499        unsigned rolls  = 0;
500        unsigned target = readBE4U(&_rb[_bp+rngoff]);
501        for(uint32_t start_rng = _rng; (start_rng != target) && (rolls < MAX_ROLLS); ++rolls) {
502          start_rng = rollRNGRollback(start_rng);
503        }
504        if (rolls < MAX_ROLLS) {  //If we can encode RNG as < 256 rolls, do it
505          // std::cout << "Rollback rolled " << rolls << " at byte " << _bp << " frame " << frame << std::endl;
506          writeBE4U(rolls,&_wb[_bp+rngoff]);
507          _rng = target;
508        } else {
509          rolls  = 0;
510          for(uint32_t start_rng = _rng; (start_rng != target) && (rolls < MAX_ROLLS); ++rolls) {
511            start_rng = rollRNGLegacy(start_rng);
512          }
513          if (rolls < MAX_ROLLS) {
514            // std::cout << "Legacy rolled " << rolls << " at byte " << _bp << " frame " << frame << std::endl;
515            writeBE4U(rolls+MAX_ROLLS,&_wb[_bp+rngoff]);
516          } else { //Store the raw RNG value
517            // std::cout << "Legacy failed at byte " << _bp << " frame " << frame << std::endl;
518            //Load the predicted frame value
519            int32_t predicted_frame = readBE4S(&_wb[_bp+frameoff]);
520            //Flip second bit of cached frame number to signal raw rng
521            writeBE4S(predicted_frame ^ RAW_RNG_MASK,&_wb[_bp+frameoff]);
522          }
523        }
524      }
525    } else { //Old RNG
526      if (_encode_ver) {
527        unsigned rolls = readBE4U(&_rb[_bp+rngoff]);
528        for(unsigned i = 0; i < rolls; ++i) {
529          _rng = rollRNGLegacy(_rng);
530        }
531        writeBE4U(_rng,&_wb[_bp+rngoff]);
532      } else { //Roll RNG until we hit the target, write the # of rolls
533        unsigned rolls, seed = readBE4U(&_rb[_bp+rngoff]);
534        for(rolls = 0; _rng != seed; ++rolls) {
535          _rng = rollRNGLegacy(_rng);
536        }
537        writeBE4U(rolls,&_wb[_bp+rngoff]);
538      }
539    }
540  }
541
542  //XOR bytes in the current read buffer with bytes from another buffer
543  inline void xorEncodeRange(unsigned start, unsigned stop, char* buffer) {
544    for(unsigned i = start; i < stop; ++i) {
545      _wb[_bp+i] = _rb[_bp+i] ^ buffer[i];
546      buffer[i]  = _encode_ver ? _wb[_bp+i] : _rb[_bp+i];
547    }
548  }
549
550  inline bool _shuffleItems(char* iblock_start, unsigned iblock_len, bool shuffle=true) {
551    // allocate temporary buffers for shuffling
552    // TODO: dynamically reallocate this array later
553    unsigned ps         = _payload_sizes[Event::ITEM_UPDATE];
554    unsigned* icount    = new unsigned[MAX_ITEMS_C]{0};
555    unsigned* ilast     = new unsigned[MAX_ITEMS_C]{0};
556    char** ibuffs       = new char*[MAX_ITEMS_C];
557    for(unsigned i = 0; i < MAX_ITEMS_C; ++i) {
558      ibuffs[i] = nullptr;
559    }
560
561    // bin item payloads by item ID
562    bool success      = true;
563    bool first_item   = true;  //apparently the first item isn't always id 0
564    unsigned wait     = 0;
565    unsigned ev_total = 0;
566    unsigned cur_id   = 0;
567    unsigned max_item = 0;
568    for (unsigned i = 0; i < iblock_len; i += ps) {
569      // read the raw (possibly encoded) item id
570      uint32_t ouid   = readBE4U(&iblock_start[i+O_ITEM_ID]);
571      // parse out the frame modulus from the item id
572      uint32_t uid    = encodeFrameIntoItemId(ouid,getFrameModFromItemId(ouid));
573
574      // if we're shuffling, we need to do some counting
575      if(shuffle) {
576        unsigned encid;
577        if(icount[uid] == 0) {
578          // get the number of elapsed item events since the last new item,
579          encid = encodeWaitIntoItemId(ouid,wait);
580          // if this isn't item 0, flag this as a new item
581          if(!first_item) {
582            // ids aren't always consecutive, so count the item id delta since last item
583            unsigned skip = 0;
584            while(icount[uid-skip] == 0) {
585              ++skip;
586            }
587            encid = encodeNewItemIntoId(encid,skip);
588          } else {
589            // if our first item isn't id 0, encode its uid as the skip value
590            encid = encodeNewItemIntoId(encid,uid);
591            // set first item status to false
592            first_item = false;
593          }
594
595          // set the wait since last new item to 1
596          wait = 0;
597        } else {
598          // get the number of elapsed item events since the last time we saw this item
599          encid = encodeWaitIntoItemId(ouid,ev_total-ilast[uid]);
600        }
601
602        // increment the waiting counter
603        wait += 1;
604
605        // update the last time we saw this item with ev_total
606        ilast[uid] = ev_total;
607
608        // increment the total events
609        ev_total += 1;
610
611        // write the new encoded item back to the block to be copied
612        writeBE4U(encid,&iblock_start[i+O_ITEM_ID]);
613      } else {  // otherwise, we need to do some unpacking
614        // if we've found a new item, increment our cur_id and copy as appropriate into the block
615        unsigned skip = getIsNewItem(ouid);
616        if(skip) {
617          cur_id += skip;
618          writeBE4U(encodeNewItemIntoId(ouid,skip),&iblock_start[i+O_ITEM_ID]);
619        }
620        // set uid to the current item
621        uid = cur_id;
622      }
623
624      // allocate a buffer for this item if we don't have one already
625      if(ibuffs[uid] == nullptr) {
626        ibuffs[uid] = new char[iblock_len];
627      }
628
629      // copy an item payload into each item's individual buffer
630      memcpy(&(ibuffs[uid][ps*icount[uid]]),&iblock_start[i],ps);
631
632      // increment number of payloads for this item
633      icount[uid] += 1;
634
635      // keep track of the highest item id we've encountered so far
636      if (uid >= max_item) {
637        max_item = uid+1;
638      }
639    }
640
641    // if we're shuffling, copy these payloads in item order back into main memory
642    if(shuffle) {
643      unsigned ind    = 0;
644      for (unsigned n = 0; ind != iblock_len; ++n) {
645        if (icount[n] == 0) {
646          continue;
647        }
648        memcpy(&iblock_start[ind],&(ibuffs[n][0]),icount[n]*ps);
649        ind += icount[n]*ps;
650      }
651    } else { // otherwise, gotta do lots of math to unshuffle everything
652      ev_total        = 0;
653      unsigned start  = 0;
654      unsigned waited = 0;
655      unsigned ind    = 0;
656      unsigned* ipos  = new unsigned[max_item]{0};
657      // until we've copied every block
658      while(ind < iblock_len) {
659        bool written = false;
660        // from the first active item until the last one
661        for (unsigned n = start; n < max_item; ++n) {
662          // if this item doesn't acutally exist, we're done with this iteration
663          if (icount[n] == 0) {
664            continue;
665          }
666          // if we've already copied all of this item over, go on to the next one
667          if (ipos[n] == icount[n]) {
668            // if this item is the start, move our start forward
669            if (n == start) {
670              ++start;
671            }
672            continue;
673          }
674
675          // determine whether we've spent an appropriate amount time waiting for previous item events
676          bool donewaiting;
677          unsigned ouid = readBE4U(&(ibuffs[n][ipos[n]*ps+O_ITEM_ID]));
678          unsigned wait = getWaitFromItemId(ouid);
679          // if this is the first time this item appears, wait time is based off item events since last new item
680          if (ipos[n] == 0) {
681            donewaiting = (wait == waited);
682          } else {  //otherwise, wait time is based on item events since this item last appeared
683            donewaiting = (wait == (ev_total-ilast[n]));
684          }
685
686          // if we're done waiting, it's time to copy this item back into the buffer
687          if (donewaiting) {
688            if (ipos[n] == 0) {
689              // if this is the first time this item has appeared, reset new item wait timer
690              waited = 0;
691            }
692            ilast[n] = ev_total;
693            // decode the actual item ID without the wait time and put it back into memory
694            writeBE4U(encodeWaitIntoItemId(ouid,n),&ibuffs[n][ipos[n]*ps+O_ITEM_ID]);
695            // copy over to main memory
696            memcpy(&iblock_start[ind],&(ibuffs[n][ipos[n]*ps]),ps);
697            // update counters as appropriate
698            ind      += ps;
699            ipos[n]  += 1;
700            waited   += 1;
701            ev_total += 1;
702            written = true;
703            continue;
704          }
705
706          // if we've never actually written this item before, we haven't written any items after it
707          //   either, so we're done here
708          if (ipos[n] == 0) {
709            break;
710          } else {  //otherwise, maybe we got rollbacked into this item, so we can continue looking
711            continue;
712          }
713        }
714        if(!written) {
715          YIKES("  Got stuck writing item data");
716          success = false;
717          break;
718        }
719      }
720      delete[] ipos;  //delete position buffer
721    }
722
723    // delete all the temporary buffers
724    for(unsigned i = 0; i < MAX_ITEMS_C; ++i) {
725      if (ibuffs[i] != nullptr) {
726        delete[] ibuffs[i];
727      }
728    }
729    delete[] ibuffs;
730    delete[] icount;
731    delete[] ilast;
732    return success;
733  }
734
735  inline bool _unshuffleItems(char* iblock_start, unsigned iblock_len) {
736    return _shuffleItems(iblock_start, iblock_len, false);
737  }
738
739  inline bool _shuffleColumns(unsigned *offset) {
740      truncateColumnWidthsToVersion();
741      char* main_buf = _wb;
742
743      // Track the starting position of the buffer
744      unsigned s         = _game_loop_start;
745      unsigned *mem_size = new unsigned[1];
746
747      // Shuffle message columns
748      if (main_buf[s] == Event::SPLIT_MSG) {
749        *mem_size = offset[19];
750        _transposeEventColumns(main_buf,s,mem_size,_debug ? this->_dw_mesg : this->_cw_mesg,false);
751        s += *mem_size;
752      }
753
754      // Shuffle frame start columns
755      if (main_buf[s] == Event::FRAME_START) {
756        *mem_size = offset[0];
757        _transposeEventColumns(main_buf,s,mem_size,_debug ? this->_dw_start : this->_cw_start,false);
758        s += *mem_size;
759      }
760
761      // Shuffle pre frame columns
762      for(unsigned p = 0; p < 8; ++p) {
763          // True player order: 0,4,1,5,2,6,3,7
764          unsigned i = (4*(p%2)) + unsigned(p/2);
765          if (main_buf[s] != Event::PRE_FRAME) {
766              break;
767          }
768          *mem_size = offset[1+i];
769          if (*mem_size == 0) {
770            continue;
771          }
772          _transposeEventColumns(main_buf,s,mem_size,_debug ? this->_dw_pre : this->_cw_pre,false);
773          s += *mem_size;
774      }
775
776
777      // Shuffle item columns
778      if (main_buf[s] == Event::ITEM_UPDATE) {
779        *mem_size = offset[9];
780        if(ENCODE_VERSION_MIN(2)) {
781          _shuffleItems(&main_buf[s],*mem_size);
782        }
783        _transposeEventColumns(main_buf,s,mem_size,_debug ? this->_dw_item : this->_cw_item,false);
784        s += *mem_size;
785      }
786
787      // Shuffle post frame columns
788      for(unsigned p = 0; p < 8; ++p) {
789          // True player order: 0,4,1,5,2,6,3,7
790          unsigned i = (4*(p%2)) + unsigned(p/2);
791          if (main_buf[s] != Event::POST_FRAME) {
792              break;
793          }
794          *mem_size = offset[10+i];
795          if (*mem_size == 0) {
796            continue;
797          }
798          _transposeEventColumns(main_buf,s,mem_size,_debug ? this->_dw_post : this->_cw_post,false);
799          s += *mem_size;
800      }
801
802      // Shuffle frame end columns
803      if (main_buf[s] == Event::BOOKEND) {
804        *mem_size = offset[18];
805        _transposeEventColumns(main_buf,s,mem_size,_debug ? this->_dw_end : this->_cw_end,false);
806        s += *mem_size;
807      }
808
809      delete[] mem_size;
810
811      return true;
812  }
813
814  inline bool _unshuffleColumns(char* main_buf) {
815      truncateColumnWidthsToVersion();
816      // We need to unshuffle event columns before doing anything else
817      // Track the starting position of the buffer
818      unsigned s         = _game_loop_start;
819      unsigned *mem_size = new unsigned[1]{0};
820
821      // Unshuffle message columns
822      if (main_buf[s] == Event::SPLIT_MSG) {
823        _revertEventColumns(main_buf,s,mem_size,_debug ? this->_dw_mesg : this->_cw_mesg);
824        s += *mem_size;
825      }
826
827      // Unshuffle frame start columns
828      if (main_buf[s] == Event::FRAME_START) {
829        _revertEventColumns(main_buf,s,mem_size,_debug ? this->_dw_start : this->_cw_start);
830        s += *mem_size;
831      }
832
833      // Unshuffle pre frame columns
834      for(unsigned i = 0; i < 8; ++i) {
835          if (main_buf[s] != Event::PRE_FRAME) {
836              break;
837          }
838          _revertEventColumns(main_buf,s,mem_size,_debug ? this->_dw_pre : this->_cw_pre);
839          s += *mem_size;
840      }
841
842      // Unshuffle item columns
843      if (main_buf[s] == Event::ITEM_UPDATE) {
844        _revertEventColumns(main_buf,s,mem_size,_debug ? this->_dw_item : this->_cw_item);
845        if(ENCODE_VERSION_MIN(2)) {
846          _unshuffleItems(&main_buf[s],*mem_size);
847        }
848        s += *mem_size;
849      }
850
851      // Unshuffle post frame columns
852      for(unsigned i = 0; i < 8; ++i) {
853          if (main_buf[s] != Event::POST_FRAME) {
854              break;
855          }
856          _revertEventColumns(main_buf,s,mem_size,_debug ? this->_dw_post : this->_cw_post);
857          s += *mem_size;
858      }
859
860      // Unshuffle frame end columns
861      if (main_buf[s] == Event::BOOKEND) {
862        _revertEventColumns(main_buf,s,mem_size,_debug ? this->_dw_end : this->_cw_end);
863        s += *mem_size;
864      }
865
866      // Reset _game_loop_start
867      delete[] mem_size;
868
869      // All done!
870      return true;
871  }
872
873  inline bool _transposeEventColumns(char* mem_buf, unsigned mem_off, unsigned* mem_size, const int col_widths[], bool unshuffle=false) {
874    bool shuffle    = !unshuffle;        //Convenience reference to whether we're shuffled
875    char* mem_start = &mem_buf[mem_off]; //Convenience reference to proper memory offset
876    uint8_t ev_code = mem_start[0];      //Always an event code regardless of shuffling
877
878    // Compute the total size of all columns in the event struct
879    unsigned struct_size       = 0;
880    unsigned col_offsets[1024] = {0};
881    for(unsigned i = 0; col_widths[i] != 0; ++i) {
882        col_offsets[i] = struct_size;
883        if (col_widths[i] > 0) {
884          struct_size += col_widths[i];
885        } else {  //Bit shuffling columns are always one byte
886          struct_size += 1;
887        }
888    }
889
890    // (Unshuffle only) Compute mem_size from consecutive event codes if necessary
891    if (unshuffle) {
892      // Ignore the existing mem_size, since it's invalid anyway
893      *mem_size = 0;
894      // While the current byte is still the event code, increment the memory size
895      while(mem_start[*mem_size] == ev_code) {
896        ++(*mem_size);
897      }
898      // Multiple the memory size by the size of the struct to get the true memory size
899      *mem_size *= struct_size;
900    }
901
902    // Create a new buffer for storing all intermediate data
903    char* buff = new char[*mem_size];
904
905    // Use struct size to get the total number of entries in the event array
906    unsigned num_entries = (*mem_size) / struct_size;
907    DOUT3("Shuffling " << num_entries << " entries");
908
909    // Transpose the columns!
910    unsigned b = 0;
911    for(unsigned i = 0; col_widths[i] != 0; ++i) {
912      unsigned block_start = mem_off+b;
913      if (col_widths[i] > 0) {  //Normal column shuffling
914        for (unsigned e = 0; e < num_entries; ++e) {
915          unsigned mempos = (e*struct_size+col_offsets[i]);
916          memcpy(
917              &buff[     unshuffle ? mempos : b],
918              &mem_start[unshuffle ? b : mempos],
919              col_widths[i]
920              );
921          b += col_widths[i];
922        }
923      } else {  //If col_widths[i] < 0, then use bitwise column shuffling
924        for (int bit = 7, ib = 7; ib >= 0; --ib) {
925          for (unsigned e = 0; e < num_entries; ++e) {
926            unsigned mempos = (e*struct_size+col_offsets[i]);
927            char r_byte     = mem_start[shuffle ? mempos : b];
928            char r_bit      = (r_byte >> (shuffle ? ib : bit)) & 0x01;
929            char w_bit      = r_bit << (shuffle ? bit : ib);
930            buff[shuffle ? b : mempos] ^= w_bit;
931            if ((--bit) < 0) {
932              bit   = 7;
933              b    += 1;
934            }
935          }
936        }
937      }
938      DOUT3("SHUFFLE " << hex(ev_code) << " column " << i << " at " << block_start << " to " << mem_off+b);
939    }
940
941    // Copy back the shuffled columns
942    memcpy(&mem_start[0], &buff[0], *mem_size);
943
944    // Clear the memory buffer
945    delete[] buff;
946
947    // All done!
948    return true;
949  }
950
951  inline bool _revertEventColumns(char* mem_buf, unsigned mem_off, unsigned* mem_size, const int col_widths[]) {
952    return _transposeEventColumns(mem_buf,mem_off,mem_size,col_widths,true);
953  }
954
955  inline unsigned encodeFrameIntoItemId(unsigned item_id, int32_t frame) const {
956    return item_id ^ (((frame+256) % 256) << 24);
957  }
958
959  inline unsigned getFrameModFromItemId(unsigned item_id) const {
960    return (item_id >> 24);
961  }
962
963  // first two bytes from right
964  inline unsigned encodeWaitIntoItemId(unsigned item_id, unsigned wait) const {
965    return (item_id & 0xFFFF0000) ^ ((wait+65536) % 65536);
966  }
967
968  inline unsigned getWaitFromItemId(unsigned item_id) const {
969    return item_id % 65536;
970  }
971
972  // 3rd byte from right
973  inline unsigned encodeNewItemIntoId(unsigned item_id, unsigned skip) const {
974    return (item_id ^ (skip << 16));
975  }
976
977  inline unsigned getIsNewItem(unsigned item_id) const {
978    return ((item_id << 8) >> 24);
979  }
980
981  inline unsigned encodeDeferInfo(unsigned u16, unsigned defer) const {
982    return u16 | (defer << 14);
983  }
984
985  inline unsigned getDeferInfo(unsigned u16) const {
986    return (u16&DEFER_ITEM_BITS) >> 14;
987  }
988
989  inline unsigned decodeDeferInfo(unsigned u16) const {
990    return u16 & (~DEFER_ITEM_BITS);
991  }
992
993  inline int32_t lookAheadToFinalizedFrame(char* mem_start, int32_t ref_frame=0) const {
994    unsigned mem_off = 0;
995    while(mem_start[mem_off] != Event::BOOKEND) {
996      mem_off += _payload_sizes[uint8_t(mem_start[mem_off])];
997    }
998    return readBE4S(&mem_start[mem_off+O_ROLLBACK_FRAME]);
999  }
1000
1001  inline bool ensureAppropriateFilename() {
1002    const char* ext = (_encode_ver > 0) ? ".slp" : ".zlp";
1003    if (_outfilename == nullptr) {
1004      std::string fname = std::string(_infilename);
1005      _outfilename = new std::string(
1006        fname.substr(0,
1007          fname.find_last_of("."))+
1008          std::string(ext));
1009      if (fileExists(*_outfilename)) {
1010        FAIL("    File " << *_outfilename << " already exists or is invalid");
1011        return false;
1012      }
1013    } else {
1014      if (!ensureExt(ext,_outfilename->c_str())) {
1015        FAIL("    File " << *_outfilename << " does not have required extension " << ext);
1016        return false;
1017      }
1018    }
1019    return true;
1020  }
1021
1022  static inline const char* readLegacyGeckoCodes() {
1023    static bool _legacy_codes_codes_read = false;
1024    static char _legacy_gecko_codes[32571];  //exact magic number of decompressed bytes
1025    if (! _legacy_codes_codes_read) {
1026      _legacy_codes_codes_read = true;
1027      // decompress the legacy gecko code data
1028      std::string decomp = decompressWithLzma(GECKO_LZMA,GECKO_LZMA_LEN);
1029      // Copy buffer from the decompressed string
1030      memcpy(_legacy_gecko_codes,decomp.c_str(),decomp.size());
1031    }
1032    return _legacy_gecko_codes;
1033  }
1034
1035  inline void truncateColumnWidthsToVersion() {
1036    if (MAX_VERSION(3,11,0)) {
1037      this->_cw_post[33] = 0; //Animation index is invalid
1038      this->_dw_post[33] = 0;
1039    }
1040    if (MAX_VERSION(3,10,0)) {
1041      this->_cw_start[3] = 0; //Scene frame counter is invalid
1042      this->_dw_start[3] = 0;
1043    }
1044    if (MAX_VERSION(3,8,0)) {
1045      this->_cw_post[32] = 0; //Hitlag and onward is invalid
1046      this->_dw_post[32] = 0;
1047    }
1048    if (MAX_VERSION(3,7,0)) {
1049      this->_cw_end[2] = 0; //Rollback frame is invalid
1050      this->_dw_end[2] = 0;
1051    }
1052    if (MAX_VERSION(3,6,0)) {
1053      this->_cw_item[19] = 0; //Item owner is invalid
1054      this->_dw_item[19] = 0;
1055    }
1056    if (MAX_VERSION(3,5,0)) {
1057      this->_cw_post[27] = 0; //Self-induced Air x Speed and onward are invalid
1058      this->_dw_post[27] = 0;
1059    }
1060    if (MAX_VERSION(3,2,0)) {
1061      this->_cw_item[15] = 0; //Item state bits are invalid
1062      this->_dw_item[15] = 0;
1063    }
1064    if (MAX_VERSION(2,1,0)) {
1065      this->_cw_post[26] = 0; //Hurtbox Collision State and onward are invalid
1066      this->_dw_post[26] = 0;
1067    }
1068    if (MAX_VERSION(2,0,0)) {
1069      this->_cw_post[16] = 0; //State bit flags 1 and onward are invalid
1070      this->_dw_post[16] = 0;
1071    }
1072    if (MAX_VERSION(1,4,0)) {
1073      this->_cw_pre[19] = 0; //Pre-frame damage percent is invalid
1074      this->_dw_pre[19] = 0;
1075    }
1076    if (MAX_VERSION(1,2,0)) {
1077      this->_cw_pre[18] = 0; //UCF X-analog is invalid
1078      this->_dw_pre[18] = 0;
1079    }
1080  }
1081
1082};
1083
1084}
1085
1086#endif /* COMPRESSOR_H_ */