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

long pw(long n, int p) {
  long nn = 1;
  if (p == 0) return 1;
  int c = 0;
  while (c < p) {
    nn *= n;
    c++;
  }
  return nn;
}

long filesizecr(char filename[], long *crpos)
{
  char buf[32768];
  unsigned long fs = 0, size = 1;
  *crpos = -1;
  FILE *fp;
  if ((fp = fopen(filename, "rb")) == NULL) return -1;

  while (size > 0) {
    size = fread(&buf, 1, sizeof(buf), fp);
    if (*crpos == -1) {
      long c = 0;
      while (c < size) {
        if ((buf[c] == '\n') && (*crpos == -1)) *crpos = (long) fs + c;
        c++;
      }
    }
    fs += size;
  }
  fclose(fp);
  return fs;
}

void findLargestSquareHere(long * h, long * sz, long * x, long * y, long len, long minsize) {
  long maxs = 0;
  long maxp = 0, maxh = 0, maxl = 0;
  long pos = 0;

  while (pos < len) {
    long tosize = h[pos];
    long size = tosize;
    if (tosize >= minsize) {
      while (size > 0) {
        if (size > minsize) {
          int isSquare = 1;
          if (pos + size <= len) {
            long i = pos;
            while (i < pos + size) {
              if (h[i] < size) {
                isSquare = 0;
                i = len;
              } else i++;
            }
            if ((isSquare == 1) && (size * size > maxs)) {
              maxs =  size * size;
              maxp = pos;
              maxl = size;
              maxh = size;
              size = 0;
            }
          }
          size--;
        } else size = 0;
      }
    }
    pos++;
  }
  *sz = maxs;
  *x = maxp;
  *y = maxh;
}

void main(void) {
  long i;
  char cobs, cfree, cfill;
  long firstcrpos = 0;
  char fname[] = "testmap.bsq";
  long fsize = filesizecr(fname, &firstcrpos);
  if (fsize != -1) printf("File size = %lu\n", fsize);
  else {
    printf("Error while opening file!\n");
    exit(0);
  }
  printf("First \\n in file is %ld\n", firstcrpos);

  char *fbuf;
  FILE *fp;
  if ((fp = fopen(fname, "rb")) == NULL) {
    printf("Error while opening file!\n");
    exit(0);
  }

  printf("Mallocing %ld bytes\n", firstcrpos * sizeof(char) + 1);
  fbuf = (char*) malloc(firstcrpos * sizeof(char) + 1);
  long bytesread = fread(fbuf, 1, firstcrpos * sizeof(char), fp);
  printf("Bytes read: %ld\n", bytesread);

  if ((bytesread != firstcrpos * sizeof(char)) || (bytesread < 4)) {
    printf("Error while reading file!\n");
    exit(0);
  }

  fbuf[bytesread] = '\0';
  printf("Header read: %s\n", fbuf);
  cfill = fbuf[bytesread - 1];
  cobs = fbuf[bytesread - 2];
  cfree = fbuf[bytesread - 3];
  fbuf[bytesread - 3] = '\0';
  i = bytesread - 4;
  long cpow = 0;
  long clines = 0;
  char temp;
  fread(&temp, 1, sizeof(char), fp);
  if (temp != '\n') {
    printf("Error while reading file!\n");
    exit(0);
  }

  while (i >= 0) { // atoi
    if (fbuf[i] > '9' || fbuf[i] < '0') {
      printf("Wrong symbols in lines count");
      exit(0);
    }
    clines +=  (fbuf[i] - '0') * pw(10, cpow);
    cpow++;
    i--;
  }
  printf("Fill [%c], free [%c], obstacle[%c], Lines: %ld\n", cfill, cfree, cobs, clines);

  long linelen = ((fsize - bytesread) / clines) - 1;
  free(fbuf);

  i = 0;
  long * hysto;
  long * lasthysto;
  lasthysto = malloc(linelen * sizeof(long));
  long j = 0;
  while (j < linelen) {
    lasthysto[j] = 0;
    j++;
  }
  j = 0;
  long sqsize = 0, sqx = 0, sqy = 0, sqline = 0;
  while (i < clines) {
    fbuf = malloc(linelen + 1);
    bytesread = fread(fbuf, 1, linelen + 1, fp);
    if ((fbuf[linelen] != '\n') || (bytesread != linelen + 1)) {
      printf("Error while reading file (%x, %x, %ld)!\n", fbuf[linelen], '\n', bytesread);
      exit(0);
    }
    fbuf[linelen] = '\0';
    hysto = malloc(linelen * sizeof(long));
    j = 0;
    while (j < linelen) {
      if ((fbuf[j] != cobs) && (fbuf[j] != cfree)) {
        printf("Error (%ld, %x)\n", j, fbuf[j]);
        exit(0);
      }
      if (fbuf[j] == cobs) hysto[j] = 0;
      if (fbuf[j] == cfree) hysto[j] = lasthysto[j] + 1;
      lasthysto[j] = hysto[j];
      j++;
    }
    long tsqsize = 0, tsqx = 0, tsqy = 0;
    findLargestSquareHere(hysto, &tsqsize, &tsqx, &tsqy, linelen, sqy);
    if (sqsize < tsqsize) {
      sqsize = tsqsize;
      sqx = tsqx;
      sqy = tsqy;
      sqline = i;
    }
    free(hysto);
    free(fbuf);
    i++;
  }
  free(lasthysto);
  fclose(fp);

  if ((fp = fopen(fname, "rb")) == NULL) {
    printf("Error while opening file!\n");
    exit(0);
  }

  fbuf = (char*) malloc(firstcrpos * sizeof(char) + 1);
  bytesread = fread(fbuf, 1, firstcrpos * sizeof(char) + 1, fp);
  i = 0;
  while (i < clines) {
    fbuf = malloc(linelen + 1);
    bytesread = fread(fbuf, 1, linelen + 1, fp);
    if ((fbuf[linelen] != '\n') || (bytesread != linelen + 1)) {
      printf("Error while reading file (%x, %x, %ld)!\n", fbuf[linelen], '\n', bytesread);
      exit(0);
    }
    fbuf[linelen] = '\0';
    j = 0;
    while (j < linelen) {
      if ((i > sqline - sqy) && (i <= sqline) && (j >= sqx) && (j < sqx + sqy))
        printf("%c", cfill);
      else printf("%c", fbuf[j]);
      j++;
    }
    printf("\n");
    i++;
  }
  fclose(fp);
}