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

typedef struct s_result
{
  long sqsize;
  long sqx;
  long sqy;
  long sqline;
} t_result;

typedef struct s_filereader
{
  int fd;
  char * fbuf;
  char * filename;
  long fsize;
  long lines;
  long linelen;
  long firstcrpos;
  char * linebuf;
  long bytesread;
  char cobs;
  char cfree;
  char cfill;
} t_filereader;

typedef struct s_square_finder
{
  long pos;
  long is_square;
  long size;
} t_finder;

int print_error (void) {
  write(1, "map error\n", 10);
  return -1;
}

inline long pw(long number, int pw)
{
  long newnumber;
  int count;
  newnumber = 1;
  if (pw == 0)
    return 1;
  count = 0;
  while (count < pw)
  {
    newnumber *= number;
    count++;
  }
  return newnumber;
}

long filesize_cr(char * filename, long *crpos)
{
  char buf[300000];
  int fd;
  long c;
  unsigned long fs;
  unsigned long size;
  fs = 0;
  size = 1;
  *crpos = -1;
  if ((fd = open(filename, O_RDONLY)) == -1)
    return (-1);
  while (size > 0)
  {
    size = read(fd, &buf, sizeof(buf));
    if (*crpos == -1)
    {
      c = 0;
      while (c < size)
      {
        if ((buf[c] == '\n') && (*crpos == -1))
          *crpos = (long)fs + c;
        c++;
      }
    }
    fs += size;
  }
  close(fd);
  return fs;
}

int dump_stdin(char * filename)
{
  char buf[300000];
  int fd;
  int fo;
  long size;
  fd = 0;
  size = 1;
  if ((fo = open(filename, O_CREAT | O_TRUNC | O_WRONLY, 0777)) == -1)
    return (-1);
  while ((size = read(0, &buf, sizeof(buf))) > 0) {
    write(fo, &buf, size);
  }
  close(fo);
}

inline void find_largest_square(long *histo, t_result *t, long len, long nlen)
{
  long i;
  t_finder f;
  f.pos = 0;
  while (f.pos < len)
  {
    f.size = histo[f.pos];
    while (f.size > t->sqy)
    {
      f.is_square = nlen - (f.pos + f.size);
      i = f.pos;
      while ((f.is_square >= 0) && (i < f.pos + f.size))
      {
        f.is_square = histo[i] - f.size;
        i++;
      }
      if ((f.is_square >= 0) && (f.size > t->sqy))
      {
        t->sqx = f.pos;
        t->sqy = f.size;
      }
      f.size--;
    }
    f.pos++;
  }
  t->sqsize = t->sqy * t->sqy;
}

int count_line_length(t_filereader *file, long offset)
{
  long cpow = 0;
  long i;
  cpow = 0;
  i = offset;
  file->lines = 0;
  while (i >= 0) /* atoi */
  {
    if (file->fbuf[i] > '9' || file->fbuf[i] < '0')
      return -1;
    file->lines += (file->fbuf[i] - '0') * pw(10, cpow);
    cpow++;
    i--;
  }
  return 0;
}

int process_header(t_filereader *file)
{
  char temp;
  file->fbuf = (char *)malloc(file->firstcrpos * sizeof(char) + 1);
  file->bytesread = read(file->fd, file->fbuf, file->firstcrpos * sizeof(char));
  if ((file->bytesread != file->firstcrpos * sizeof(char)) || (file->bytesread < 4))
    return print_error();
  file->fbuf[file->bytesread] = '\0';
  file->cfill = file->fbuf[file->bytesread - 1];
  file->cobs = file->fbuf[file->bytesread - 2];
  file->cfree = file->fbuf[file->bytesread - 3];
  file->fbuf[file->bytesread - 3] = '\0';
  if (count_line_length(file, file->bytesread - 4) == -1)
    return print_error();
  file->linelen = ((file->fsize - file->bytesread) / file->lines) - 1;
  free(file->fbuf);
  file->bytesread = read(file->fd, &temp, sizeof(char));
  if (temp != '\n')
    return print_error();
}
int file_open(t_filereader * file, char * filename)
{
  file->filename = filename;
  file->firstcrpos = 0;
  file->fsize = filesize_cr(file->filename, &file->firstcrpos);
  if (file->fsize == -1)
    return print_error();
  if ((file->fd = open(file->filename, O_RDONLY)) == -1)
    return print_error();
}

int file_open_stdin(t_filereader * file, char * filename)
{
  if (dump_stdin(filename) == -1)
    return print_error();
  file->filename = filename;
  file->firstcrpos = 0;
  file->fsize = filesize_cr(filename, &file->firstcrpos);
  if (file->fsize == -1)
    return print_error();
  if ((file->fd = open(file->filename, O_RDONLY)) == -1)
    return print_error();
}

inline void assign_result(t_result *res, t_result *temp_res, long line)
{
  if (res->sqsize < temp_res->sqsize)
  {
    res->sqsize = temp_res->sqsize;
    res->sqx = temp_res->sqx;
    res->sqy = temp_res->sqy;
    res->sqline = line;
  }
}

inline void prepare_temp_result(t_result *tres, long initvalue) {
  tres->sqsize = 0;
  tres->sqx = 0;
  tres->sqy = initvalue;
  return;
}

inline void clear_result(t_result *res)
{
  res->sqx = 0;
  res->sqy = 0;
  res->sqsize = 0;
  res->sqline = 0;
}

int buffer_line (t_filereader *file)
{
  file->bytesread = read(file->fd, file->fbuf, file->linelen + 1);
  if ((file->fbuf[file->linelen] != '\n') || (file->bytesread != file->linelen + 1))
    return print_error();
  return 0;
}

void clear_histogram(long * h, long length)
{
  long i;
  i = 0;
  while (i < length)
  {
    h[i] = 0;
    i++;
  }
}

inline int fill_histogram(t_filereader *file, long *histo, long *lasthisto)
{
  long i;
  i = 0;
  while (i < file->linelen)
  {
    if ((file->fbuf[i] != file->cobs) && (file->fbuf[i] != file->cfree))
      return print_error();
    if (file->fbuf[i] == file->cobs)
      histo[i] = 0;
    if (file->fbuf[i] == file->cfree)
      histo[i] = lasthisto[i] + 1;
    lasthisto[i] = histo[i];
    i++;
  }
  return 0;
}

inline int process_map(t_filereader *file, t_result * res)
{
  long *histo;
  long *lasthisto;
  t_result tres;
  long i;
  i = 0;
  lasthisto = (long *)malloc(file->linelen * sizeof(long));
  clear_histogram(lasthisto, file->linelen);
  while (i < file->lines)
  {
    file->fbuf = (char *)malloc(file->linelen + 1);
    if (buffer_line(file) == -1)
      return print_error();
    file->fbuf[file->linelen] = '\0';
    histo = (long *)malloc(file->linelen * sizeof(long));
    if (fill_histogram(file, histo, lasthisto) == -1)
      return print_error();
    free(file->fbuf);
    prepare_temp_result(&tres, res->sqy);
    find_largest_square(histo, &tres, file->linelen - tres.sqy, file->linelen);
    free(histo);
    assign_result(res, &tres, i);
    i++;
  }
  free(lasthisto);
  return 0;
}

void skip_header (t_filereader *file)
{
  file->fbuf = (char *)malloc(file->firstcrpos * sizeof(char) + 1);
  file->bytesread = read(file->fd, file->fbuf, file->firstcrpos * sizeof(char) + 1);
  free(file->fbuf);
}

int print_result (t_filereader *file, t_result *res) {
  long i;
  long j;
  if ((file->fd = open(file->filename, O_RDONLY)) == -1)
    return print_error();
  skip_header(file);
  i = 0;
  while (i < file->lines)
  {
    file->fbuf = (char *)malloc((file->linelen + 1) * sizeof(char));
    file->bytesread = read(file->fd, file->fbuf, file->linelen + 1);
    if ((file->fbuf[file->linelen] != '\n') || (file->bytesread != file->linelen + 1))
      return print_error();
    j = 0;
    while (j < file->linelen)
    {
      if ((i > res->sqline - res->sqy) && (i <= res->sqline) && (j >= res->sqx) && (j < res->sqx + res->sqy))
        file->fbuf[j] = file->cfill;
      j++;
    }
    write(1, file->fbuf, file->linelen + 1);
    free(file->fbuf);
    i++;
  }
  close(file->fd);
  return 0;
}

void run_stdin(t_filereader * file, t_result * res, char * filename)
{
  if (file_open_stdin(file, filename) != -1)
    if (process_header(file) != -1)
    {
      clear_result(res);
      if (process_map(file, res) != -1)
      {
        close(file->fd);
        print_result(file, res);
      }
    }
  write(1, "\n", 1);
}
void run_files(t_filereader * file, t_result * res, char ** av, int ac)
{
  int i;
  i = 1;
  while (i < ac) {
    if (file_open(file, av[i]) != -1)
    {
      if (process_header(file) != -1)
      {
        clear_result(res);
        if (process_map(file, res) != -1)
        {
          close(file->fd);
          print_result(file, res);
        }
      }
    }
    write(1, "\n", 1);
    i++;
  }
}

int main(int argc, char **argv)
{
  t_result res;
  t_filereader file;
  if (argc <= 1)
    run_stdin(&file, &res, "bsq.tmp");
  else
    run_files(&file, &res, argv, argc);
}