#include<stdio.h>
#include<stdlib.h>

#define BAG_SIZE 63
#define BUF_SIZE 25
#define NUM_DIFF_PIECES 7

typedef struct {
  u_int32_t next_idx;
  u_int32_t refill_idx;
  u_int32_t buf[BUF_SIZE];
  u_int16_t pieces_remaining;
  u_int8_t  bag[BAG_SIZE];
  u_int32_t seed;
} BagBuf_t;

void gen_game(u_int32_t *p_seed);
u_int32_t next_rand(u_int32_t seed);
void init_bag(BagBuf_t *p_bagBuf);
void refill_buf(BagBuf_t *p_bagBuf);
u_int32_t next_piece(BagBuf_t *p_bagBuf);
void init_bagbuf(BagBuf_t *p_bagBuf, u_int32_t *p_seed);

void gen_game(u_int32_t *p_seed) {
  BagBuf_t bagBuf;
  u_int32_t holdPiece, nextPiece;
  u_int32_t nextBagSeed;
  u_int32_t i;

  init_bagbuf(&bagBuf, p_seed);

  holdPiece = next_rand(*p_seed) % NUM_DIFF_PIECES;

  printf("%u ", holdPiece);

  // We split this loop in two, ...
  for (i = 0; i < BAG_SIZE - (BUF_SIZE - 1); i++) {
    nextPiece = next_piece(&bagBuf);
    printf("%u", nextPiece);
  }

  // ... so that we may record the seed that will be used to generate the next bag.
  nextBagSeed = bagBuf.seed;

  for (i = BAG_SIZE - (BUF_SIZE - 1); i < BAG_SIZE; i++) {
    nextPiece = next_piece(&bagBuf);
    printf("%u", nextPiece);
  }

  printf(" %08x\n", nextBagSeed);
}

u_int32_t next_rand(u_int32_t seed) {
  u_int32_t retVal;
  u_int32_t i;

  seed++;
  retVal = 0;
  i = 0;
  do {
    seed = (seed << 3 | seed >> 29) ^ 0x80500000;  // magic numbers
    retVal |= (seed & 1) << i;
  } while (++i < 32);

  return retVal;
}

/*
  Initializes bag-63
  9 copies of each piece
  0 1 2 3 4 5 6 0 1 2 ... 4 5 6
  resets decrementer counter to 63
*/
void init_bag(BagBuf_t *p_bagBuf) {
  u_int8_t *b;
  u_int8_t i, j;
  
  b = p_bagBuf->bag;
  i = 0;
  do {
    j = 0;
    do {
      *b = j;
      b++;
    } while (++j < NUM_DIFF_PIECES);
  } while (++i < BAG_SIZE / NUM_DIFF_PIECES);

  p_bagBuf->pieces_remaining = BAG_SIZE;
}

void refill_buf(BagBuf_t *p_bagBuf) {
  u_int32_t bag_idx;
  u_int8_t *b;
  u_int8_t piece;

  if (p_bagBuf->next_idx != p_bagBuf->refill_idx) {
    do {
      p_bagBuf->seed = next_rand(p_bagBuf->seed);
      bag_idx = p_bagBuf->seed % p_bagBuf->pieces_remaining;
      // Randomly pluck a piece from the bag.
      piece = p_bagBuf->bag[bag_idx];
      b = p_bagBuf->bag + bag_idx;
      // Fill the hole left by the plucked piece by shifting left every piece after it.
      while (bag_idx < BAG_SIZE - 1) {
        bag_idx++;
        *b = b[1];
        b++;
      }
      p_bagBuf->pieces_remaining--;
      if (p_bagBuf->pieces_remaining == 0) {
        init_bag(p_bagBuf);
      }
      // Place the plucked piece into the buf.
      p_bagBuf->buf[p_bagBuf->refill_idx] = piece;
      p_bagBuf->refill_idx = (p_bagBuf->refill_idx + 1) % BUF_SIZE;
    } while (p_bagBuf->next_idx != p_bagBuf->refill_idx);
  }
}

// Grab next piece from the buf.
u_int32_t next_piece(BagBuf_t *p_bagBuf) {
  u_int32_t piece;

  refill_buf(p_bagBuf);
  piece = p_bagBuf->buf[p_bagBuf->next_idx];
  p_bagBuf->next_idx = (p_bagBuf->next_idx + 1) % BUF_SIZE;

  return piece;
}

void init_bagbuf(BagBuf_t *p_bagBuf, u_int32_t *p_seed) {
  init_bag(p_bagBuf);
  p_bagBuf->seed = *p_seed;
  p_bagBuf->next_idx = 0;
  p_bagBuf->refill_idx = 1;
  // Fill up the buf with (BUF_SIZE - 1) pieces from the bag.
  refill_buf(p_bagBuf);
  p_bagBuf->next_idx = 1;
  *p_seed = p_bagBuf->seed;
}

int main(int argc, char* argv[]) {
  u_int64_t cycles;
  u_int64_t nsec;
  u_int32_t seed;

  /*
    The N64 has a CPU count register that increments at a period of 46.875 MHz,
    with 1 cycle equal to 64/3 nanoseconds.
    This cycle count is written to and read from the cart's sram,
    converted to nanoseconds, and used to seed the randomizer.
  */

  // Input is a 32 bit hexadecimal number.  For example, 0bff234a
  cycles = (u_int32_t)strtoul(argv[1], NULL, 16);

  // multiply by 64/3
  nsec = ((cycles / 3) << 6) + (((cycles % 3) << 6) / 3);

  seed = (u_int32_t)nsec;

  gen_game(&seed);

  /*
    Output is in the format of:
    holdPiece bag-63 nextBagSeed
    For example,
    6 001150146450116635656435023453415464605002253133462632321422012 a5b8b448
  */

  /*
    N64 New Tetris colors
    0  L  pink
    1  J  purple
    2  Z  red
    3  S  green
    4  T  yellow
    5  I  blue
    6  O  gray
  */

  return 0;
}