/*

This is a concept version of M1 decoder. It's fully functional, except for
clarity it doesn't handle cases where the data stream ends and you want to
keep reading - to add that functionality just move input buffer cursor to next
4-byte boundary and restart decoding (by re-reading dictionary again).

The source includes a brute-force exhaustive cracker (takes about an hour
for a decent CPU). Pattern compare with just 4 bytes might return some very
close but not correct XOR masks so I decided on 6. Due to the simplification
I explained above it's theoreticaly possible for the cracker to fail (if there
is EOS symbol in the first 6 decoded bytes), but that is highly unlikely.

D.

*/

#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define CRACKER

uint8_t ReadByte ();
void StoreByte (uint8_t b);
void ShiftIn ();
void Decode (uint32_t mask);

  //-------------------------------------------------------------------------
int s_in_len, s_in_pos;
uint8_t* s_input;
uint8_t s_xor [4];

uint8_t s_dict [111];
int s_subst;

int s_out_len, s_out_cnt;
uint8_t* s_output;

int s_shift, s_bits;

  //-------------------------------------------------------------------------
uint8_t ReadByte ()
  {
  uint8_t v;

  switch (s_in_pos & 3)
    {
    case 0:
      v = s_input [s_in_pos + 3];
      v ^= s_input [s_in_pos + 1];
      break;
    case 1:
      v = s_input [s_in_pos + 1];
      v ^= s_input [s_in_pos - 1];
      break;
    case 2:
      v = s_input [s_in_pos - 1];
      break;
    case 3:
      v = s_input [s_in_pos - 3];
      break;
    }
  v ^= s_xor [s_in_pos & 3];
  s_in_pos++;
  return v;
  }

  //-------------------------------------------------------------------------
void StoreByte (uint8_t b)
  {
  if (s_subst && s_out_cnt >= 2)
    b = s_output [s_out_cnt - 2] - b;
  s_output [s_out_cnt] = b;
  s_out_cnt++;
  }

  //-------------------------------------------------------------------------
void ShiftIn ()
  {
  s_shift <<= 8;
  s_shift |= ReadByte ();
  s_bits += 8;
  }

  //-------------------------------------------------------------------------
void Decode (uint32_t mask)
  {
  int i, eos;

  s_xor [0] = (uint8_t)mask;
  s_xor [1] = (uint8_t)(mask >> 8);
  s_xor [2] = (uint8_t)(mask >> 16);
  s_xor [3] = (uint8_t)(mask >> 24);

  // byte dictionary
  s_in_pos = 0;
  for (i = 0; i < 111; i++)
    s_dict [i] = ReadByte ();

  // control bits
  s_subst = (s_dict [0] & 64) ? 1 : 0;

  // command stream
  s_out_cnt = 0, eos = 0;
  s_shift = 0, s_bits = 0;    
  while (!eos && s_in_pos < s_in_len)
    {
    int code, addr, t;

    if (s_bits < 2)
      ShiftIn ();
    code = (s_shift >> (s_bits - 2)) & 3;
    switch (code)
      {
      case 0:
        // 00-aa
        if (s_bits < 4)
          ShiftIn ();
        addr = (s_shift >> (s_bits - 4)) & 3;
        s_bits -= 4;
        if (addr == 0)
          {
          // quotation
          if (s_bits < 8)
            ShiftIn ();
          t = (s_shift >> (s_bits - 8)) & 255;
          s_bits -= 8;
          StoreByte (t);
          break;
          }
        StoreByte (s_dict [addr]);
        break;

      case 1:
        if (s_bits < 5)
          ShiftIn ();
        t = (s_shift >> (s_bits - 3)) & 1;
        if (t == 0)
          {
          // 010-aa
          addr = (s_shift >> (s_bits - 5)) & 3;
          addr += 4;
          s_bits -= 5;
          }
        else
          {
          // 011-aaa
          if (s_bits < 6)
            ShiftIn ();
          addr = (s_shift >> (s_bits - 6)) & 7;
          addr += 8;
          s_bits -= 6;
          }
        StoreByte (s_dict [addr]);
        break;

      case 2:
        if (s_bits < 7)
          ShiftIn ();
        // 10-aaaaa
        addr = (s_shift >> (s_bits - 7)) & 31;
        addr += 16;
        s_bits -= 7;
        StoreByte (s_dict [addr]);
        break;

      case 3:
        if (s_bits < 8)
          ShiftIn ();
        // 11-aaaaaa
        addr = (s_shift >> (s_bits - 8)) & 63;
        addr += 48;
        s_bits -= 8;
        if (addr == 111)
          // end of stream
          eos = 1;
        else
          StoreByte (s_dict [addr]);
        break;
      }
    }
  }
 
  //-------------------------------------------------------------------------
int main (int ia, char *ta [])
  {
  char* name;
  FILE* f;
  uint32_t m, x;
  time_t t1, t2;
  uint8_t pattern [6];
  int t;

  name = (ia < 2) ? (char*)"input.bin" : ta [1]; 
  f = fopen (name, "rb");
  if (f == NULL)
    {
    printf ("File open error: %s\n", name);
    return 1;
    }

  fseek (f, 0, SEEK_END);
  s_in_len = ftell (f);
  if (s_in_len < 112)
    {
    printf ("File too short: %s\n", name);
    return 1;
    }
  s_input = new uint8_t [s_in_len];
  fseek (f, 0, SEEK_SET);
  fread (s_input, 1, s_in_len, f);
  fclose (f);

  s_out_len = (s_in_len - 111) * 2;
  s_output = new uint8_t [s_out_len];

  name = (ia < 3) ? (char*)"pattern.bin" : ta [2]; 
  f = fopen (name, "rb");
  if (f == NULL)
    {
    printf ("File open error: %s\n", name);
    return 1;
    }
  if (fread (pattern, 1, 6, f) < 6)
    {
    printf ("File too short: %s\n", name);
    return 1;
    }
  fclose (f);

  // 840-0030 / AH! MY GODDESS QUIZ GAME: 0xCD9B4896
  // 840-0039 / Giant Gram 2000: 0x7F805C3F
  // 840-0084 / Virtua Tennis 2: 0x2D2D4743
  // 840-0098 / Shootout Pool: 0xA0F37CA7
  // 840-0106 / Virtua Fighter 4 Evolution: 0x1E5BB0CD
  // 840-0128 / Shootout Pool Prize: 0x9DBDE9CD
  // 840-0136 / Shootout Pool Medal: 0x9DBDE9CD
  // 840-0140 / Kick'4'Cash: 0x820857C9
  // 840-0150 / MKG TKOB 2K3 2ND VER1.003-: 0x3892FB3A
  // 841-0007 / Marvel vs. Capcom 2: 0xC18B6E7C

#ifdef CRACKER
  x = 0, time (&t1);
  t = s_in_len;
  s_in_len = 0x88;
  for (m = ~0; m != 0; m--)
#else
  m = 0xCD9B4896;
#endif
    {
    Decode (m);

#ifdef CRACKER
    if (memcmp (s_output, pattern, 6) == 0)
      {
      printf ("XOR mask: 0x%08X\n", m);
      break;
      }

    if (x - m > 1024)
      {
      x = m;
      time (&t2);
      if (t1 != t2)
        {
        t1 = t2;
        printf ("0x%08X...\n", m);
        fflush (stdout);
        }
      }
#endif
    }

#ifdef CRACKER
  s_in_len = t;
  Decode (m);
#endif

  f = fopen ("output.bin", "wb");
  if (f == NULL)
    return 1;
  fwrite (s_output, 1, s_out_cnt, f);
  fclose (f);
  return 0;
  }