src/emulation/sky/lzs.cpp

   1 #include "lzs.hpp"
   2 #include <cassert>
   3 #include <climits>
   4 #include <vector>
   5
   6 namespace sky
   7 {
   8         data_error::data_error(const char* errmsg) : std::runtime_error(errmsg) {}
   9
  10         input_stream::~input_stream()
  11         {
  12         }
  13
  14         inline void reload(input_stream& in, unsigned char& byte, unsigned char& bits)
  15         {
  16                 assert(bits <= 8);
  17                 if(bits == 0) {
  18                         int r = in.read("Unexpected end of compressed data");
  19                         byte = r;
  20                         bits = 8;
  21                 }
  22                 assert(bits <= 8);
  23         }
  24
  25         inline bool read1(input_stream& in, unsigned char& byte, unsigned char& bits)
  26         {
  27                 assert(bits <= 8);
  28                 reload(in, byte, bits);
  29                 bool ret = ((byte & 0x80) != 0);
  30                 byte <<= 1;
  31                 bits--;
  32                 assert(bits <= 8);
  33                 return ret;
  34         }
  35
  36         inline size_t read_n(input_stream& in, unsigned char& byte, unsigned char& bits, unsigned count)
  37         {
  38                 assert(bits <= 8);
  39                 if(count == 0)
  40                         return 0;
  41                 if(count <= bits) {
  42                         //Satisfiable immediately.
  43                         size_t ret = byte >> (8 - count);
  44                         bits -= count;
  45                         byte <<= count;
  46                         return ret;
  47                 }
  48                 size_t readc = 0;
  49                 size_t ret = 0;
  50                 //Read the first incomplete byte if any.
  51                 if(bits > 0) {
  52                         ret = byte >> (8 - bits);
  53                         readc = bits;
  54                         bits = 0;
  55                 }
  56                 //Read complete bytes.
  57                 while(readc + 8 <= count) {
  58                         int r = in.read("Unexpected end of compressed data");
  59                         ret = (ret << 8) | (r & 0xFF);
  60                         readc += 8;
  61                 }
  62                 size_t tailbits = count - readc;
  63                 if(tailbits > 0) {
  64                         //Read the tail bits.
  65                         reload(in, byte, bits);
  66                         ret = (ret << tailbits) | (byte >> (8 - tailbits));
  67                         byte <<= tailbits;
  68                         bits -= tailbits;
  69                 }
  70                 return ret;
  71         }
  72
  73         void lzs_decompress(input_stream& in, output_stream& out, size_t size)
  74         {
  75                 unsigned char cbits = in.read("Incomplete compression header");
  76                 unsigned char sbits = in.read("Incomplete compression header");
  77                 unsigned char lbits = in.read("Incomplete compression header");
  78                 size_t maxbits = sizeof(size_t) * CHAR_BIT;
  79                 if((sbits >= maxbits || lbits >= maxbits) || (sbits == maxbits - 1 && lbits == maxbits - 1))
  80                         throw data_error("Can't handle the backward offset space");
  81                 if(cbits >= maxbits)
  82                         throw data_error("Can't handle the copy length space");
  83
  84                 size_t maxoffset = 2 + (size_t(1) << sbits) + (size_t(1) << lbits);
  85                 size_t shortbias = 2;
  86                 size_t longbias = 2 + (size_t(1) << sbits);
  87                 maxoffset = (size < maxoffset) ? size : maxoffset;
  88                 std::vector<unsigned char> tmp;
  89                 tmp.resize(maxoffset);
  90
  91                 uint8_t pending_byte = 0;
  92                 uint8_t pending_bits = 0;
  93                 size_t output = 0;
  94                 size_t copy_remaining = 0;
  95                 size_t copy_backward = 0;
  96                 size_t cyclic_pointer = 0;
  97                 while(output < size) {
  98                         assert(pending_bits <= 8);
  99                         if(copy_remaining) {
 100                                 size_t cindex;
 101                                 if(copy_backward <= cyclic_pointer)
 102                                         cindex = cyclic_pointer - copy_backward;
 103                                 else
 104                                         cindex = maxoffset + cyclic_pointer - copy_backward;
 105                                 copy_remaining--;
 106                                 out.put(tmp[cyclic_pointer++] = tmp[cindex]);
 107                                 if(cyclic_pointer == maxoffset)
 108                                         cyclic_pointer = 0;
 109                                 output++;
 110                                 continue;
 111                         }
 112                         if(read1(in, pending_byte, pending_bits)) {
 113                                 if(read1(in, pending_byte, pending_bits)) {
 114                                         //Literial insert.
 115                                         out.put(tmp[cyclic_pointer++] = static_cast<unsigned char>(read_n(in,
 116                                                 pending_byte, pending_bits, 8)));
 117                                         if(cyclic_pointer == maxoffset)
 118                                                 cyclic_pointer = 0;
 119                                         output++;
 120                                 } else {
 121                                         //Long copy.
 122                                         copy_backward = longbias + read_n(in, pending_byte, pending_bits, lbits);
 123                                         copy_remaining = 2 + read_n(in, pending_byte, pending_bits, cbits);
 124                                         if(copy_backward > output)
 125                                         throw data_error("Backward copy offset too large");
 126                                 }
 127                         } else {
 128                                 //Short copy.
 129                                 copy_backward = shortbias + read_n(in, pending_byte, pending_bits, sbits);
 130                                 copy_remaining = 2 + read_n(in, pending_byte, pending_bits, cbits);
 131                                 if(copy_backward > output)
 132                                         throw data_error("Backward copy offset too large");
 133                         }
 134                 }
 135         }
 136 }