fork/slippc

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

Patrick Crainfixed rare memory leak in parser; updated changelog and readmes for version 0.8.0b79f91c

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