#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include <string.h>
#include <limits.h>

#pragma pack(push, 1)

#define CW_OK 0
#define CW_ERROR 40

enum {
    EXCHANGE_UNKNOWN = -1,
    EXCHANGE_CLOCKWISE = 0,
    EXCHANGE_COUNTERCLOCKWISE,
    EXCHANGE_DIAGONALS
};

typedef struct {
    unsigned short signature;
    unsigned int filesize;
    unsigned short reserved1;
    unsigned short reserved2;
    unsigned int data_offset;
} bmpfile_header_t;

typedef struct {
    unsigned int header_size;
    unsigned int width;
    unsigned int height;
    unsigned short planes;
    unsigned short bits_per_pixel;
    unsigned int compression;
    unsigned int image_size;
    unsigned int xresolution;
    unsigned int yresolution;
    unsigned int n_colors;
    unsigned int n_important_colors;
} bmpfile_info_t;

typedef struct {
    unsigned char b;
    unsigned char g;
    unsigned char r;
} rgb_t;

#pragma pack(pop)

typedef struct {
    int x, y;
} point_t;

typedef struct {
    bmpfile_header_t header;
    bmpfile_info_t   info;
    rgb_t**          data;
} bmp_t;

int load_bmp(bmp_t *bmp, char *filename)
{
    FILE *fp = fopen(filename, "rb");
    if (fp == NULL) {
        fputs("Cannot open input file\n", stderr);
        return CW_ERROR;
    }

    fread(&bmp->header, 1, sizeof(bmpfile_header_t), fp);
    fread(&bmp->info, 1, sizeof(bmpfile_info_t), fp);

    if (bmp->header.signature!= 0x4D42) {
        fputs("Invalid file signature\n", stderr);
        fclose(fp);
        return CW_ERROR;
    }

    if (bmp->info.bits_per_pixel != 24 || bmp->info.compression != 0 || bmp->info.planes != 1) {
        fputs("Unsupported BMP format\n", stderr);
        fclose(fp);
        return CW_ERROR;
    }

    bmp->data = (rgb_t**)malloc(bmp->info.height * sizeof(rgb_t*));
    if (bmp->data == NULL) {
        fputs("Memory allocation error\n", stderr);
        fclose(fp);
        return CW_ERROR;
    }

    size_t padding = (4 - (sizeof(rgb_t) * bmp->info.width) % 4) % 4;

    for (int i = bmp->info.height - 1; i >= 0; i--) {
        bmp->data[i] = (rgb_t*)malloc(bmp->info.width * sizeof(rgb_t) + padding);
        if (bmp->data[i] == NULL) {
            fputs("Memory allocation error\n", stderr);
            fclose(fp);

            for (int j = bmp->info.height - 1; j > i; j--)
                free(bmp->data[j]);
            free(bmp->data);
            return CW_ERROR;
        }

        fread(bmp->data[i], 1, bmp->info.width * sizeof(rgb_t) + padding, fp);
    }

    fclose(fp);
    return CW_OK;
}

int save_bmp(bmp_t *bmp, char *filename)
{
    FILE *fp = fopen(filename, "wb");
    if (fp == NULL) {
        fputs("Cannot open output file\n", stderr);
        return CW_ERROR;
    }

    fwrite(&bmp->header, 1, sizeof(bmpfile_header_t), fp);
    fwrite(&bmp->info, 1, sizeof(bmpfile_info_t), fp);
    fseek(fp, bmp->header.data_offset, SEEK_SET);

    int padding = (4 - (sizeof(rgb_t) * bmp->info.width) % 4) % 4;
    for (int i = bmp->info.height - 1; i >= 0; i--) {
        fwrite(bmp->data[i], 1, bmp->info.width * sizeof(rgb_t) + padding, fp);
    }

    fclose(fp);
    return CW_OK;
}

void free_bmp(bmp_t *bmp)
{
    for (size_t i = 0; i < bmp->info.height; i++) {
        free(bmp->data[i]);
    }
    free(bmp->data);
}

const char shortopts[] = "hil:s:t:c:fF:r:x:I:O:";

enum {
    FUNCTION_SQUARE = 1,
    FUNCTION_EXCHANGE,
    FUNCTION_FREQ_COLOR
};

struct option longopts[] = {
    { "help", 0, NULL, 'h' },
    { "info", 0, NULL, 'i' },
    { "square", 0, NULL, FUNCTION_SQUARE },
    { "exchange", 0, NULL, FUNCTION_EXCHANGE },
    { "freq_color", 0, NULL, FUNCTION_FREQ_COLOR },

    { "left_up", 1, NULL, 'l' },
    { "side_size", 1, NULL,'s' },
    { "thickness", 1, NULL, 't' },
    { "color", 1, NULL, 'c'},
    { "fill", 0, NULL, 'f' },
    { "fill_color", 1, NULL, 'F' },

    { "right_down", 1, NULL, 'r' },
    { "exchange_type", 1, NULL, 'x' },

    { "input", 1, NULL, 'I' },
    { "output", 1, NULL, 'O' },

    { NULL, 0, NULL, 0 }
};

typedef struct {
    point_t left_up;
    int side_size;
    int thickness;
    rgb_t color;
    char is_color_set;
    char fill;
    rgb_t fill_color;
    char is_fill_color_set;
    point_t right_down;
    int exchange_type;
    char *input;
    char *output;
} args_t;

void init_args(args_t *args)
{
    args->left_up = (point_t) { INT_MAX, INT_MAX };
    args->side_size = INT_MAX;
    args->thickness = INT_MAX;
    args->color = (rgb_t) { 0, 0, 0 };
    args->is_color_set = 0;
    args->fill = 0;
    args->right_down = (point_t) { INT_MAX, INT_MAX };
    args->exchange_type = EXCHANGE_UNKNOWN;
    args->input = NULL;
    args->output = "out.bmp";
}

int read_color(rgb_t *rgb, char *str)
{
    int r, g, b;
    int n = sscanf(str, "%d.%d.%d", &r, &g, &b);

    if (n != 3) {
        fputs("Invalid color format\n", stderr);
        return CW_ERROR;
    }

    if (r < 0 || g < 0 || b < 0 || r > 255 || g > 255 || b > 255) {
        fputs("Invalid color value\n", stderr);
        return CW_ERROR;
    }

    rgb->r = r;
    rgb->g = g;
    rgb->b = b;
    return CW_OK;
}

int read_int(int *val, char *str)
{
    int n = sscanf(str, "%d", val);

    if (n != 1) {
        fputs("Invalid integer\n", stderr);
        return CW_ERROR;
    }

    return CW_OK;
}

int read_point(point_t *pt, char *str)
{
    int n = sscanf(str, "%d.%d", &pt->x, &pt->y);

    if (n!= 2) {
        fputs("Invalid point format\n", stderr);
        return CW_ERROR;
    }

    return CW_OK;
}

int read_exchange_type(int *exchange_type, char *str)
{
    if (strcmp(str, "clockwise") == 0) {
        *exchange_type = EXCHANGE_CLOCKWISE;
        return CW_OK;
    }
    if (strcmp(str, "counterclockwise") == 0) {
        *exchange_type = EXCHANGE_COUNTERCLOCKWISE;
        return CW_OK;
    }
    if (strcmp(str, "diagonals") == 0) {
        *exchange_type = EXCHANGE_DIAGONALS;
        return CW_OK;
    }

    fputs("Invalid exchange type\n", stderr);
    return CW_ERROR;
}

void print_help()
{
    puts(
        "./cw <function> [options]\n"
        "Functions:\n"
        " -h, --help\n"
        " -i, --info     print info about image\n"
        " --square       draw square\n"
        " --exchange     exchange four pieces of the image\n"
        " --freq_color   replace most frequent color\n"
        "Options:\n"
        " -I, --input <file>\n"
        " -O, --output <file>\n"
        "Options for square:\n"
        " -l, --left_up X.Y\n"
        " -s, --side_size X\n"
        " -t, --thickness X\n"
        " -c, --color R.G.B\n"
        " -f, --fill (flag to fill the square)\n"
        " -F, --fill_color R.G.B\n"
        "Options for exchange:\n"
        "  -x, --exchange_type (clockwise, counterclockwise, diagonals)\n"
        "  -l, --left_up X.Y\n"
        "  -r, --right_down X.Y\n"
        "Options for freq_color:\n"
        "  -c, --color R.G.B"
    );
}

rgb_t get_pixel(bmp_t *bmp, int x, int y)
{
    if (x < 0 || y < 0 || x >= (int)bmp->info.width || y >= (int)bmp->info.height) {
        return (rgb_t) { 0, 0, 0 };
    }
    return bmp->data[y][x];
}

void set_pixel(bmp_t *bmp, int x, int y, rgb_t rgb)
{
    if (x < 0 || y < 0 || x >= (int)bmp->info.width || y >= (int)bmp->info.height)
        return;
    bmp->data[y][x] = rgb;
}

int print_image_info_option(bmp_t *bmp)
{
    printf("Width: %d\n", (int)bmp->info.width);
    printf("Height: %d\n", (int)bmp->info.height);
    printf("Planes: %d\n", (int)bmp->info.planes);
    printf("Bits per pixel: %d\n", (int)bmp->info.bits_per_pixel);
    printf("Compression: %d\n", (int)bmp->info.compression);
    printf("Image size: %d\n", (int)bmp->info.image_size);
    printf("X resolution: %d\n", (int)bmp->info.xresolution);
    printf("Y resolution: %d\n", (int)bmp->info.yresolution);
    printf("Number of colors: %d\n", (int)bmp->info.n_colors);
    printf("Number of important colors: %d\n", (int)bmp->info.n_important_colors);

    return CW_OK;
}

int draw_square_option(bmp_t *bmp, args_t *args)
{
    if (args->left_up.x == INT_MAX && args->left_up.y == INT_MAX) {
        fputs("Left up corner not specified\n", stderr);
        return CW_ERROR;
    }
    if (args->side_size == INT_MAX) {
        fputs("Side size not specified\n", stderr);
        return CW_ERROR;
    }
    if (args->thickness == INT_MAX) {
        fputs("Thickness not specified\n", stderr);
        return CW_ERROR;
    }
    if (args->is_color_set == 0) {
        fputs("Color not specified\n", stderr);
        return CW_ERROR;
    }
    if (args->fill == 1 && args->is_fill_color_set == 0) {
        fputs("Fill color not specified\n", stderr);
        return CW_ERROR;
    }

    int x0 = args->left_up.x;
    int y0 = args->left_up.y;
    int x1 = args->left_up.x + args->side_size;
    int y1 = args->left_up.y + args->side_size;

    args->thickness = (args->thickness + 1) / 2;

    if (args->fill) {
        int fx0 = (x0 < 0) ? 0 : x0;
        int fy0 = (y0 < 0) ? 0 : y0;
        int fx1 = (x1 > (int)bmp->info.width) ? (int)bmp->info.width : x1;
        int fy1 = (y1 > (int)bmp->info.height) ? (int)bmp->info.height : y1;

        for (int x = fx0; x < fx1; x++) {
            for (int y = fy0; y < fy1; y++) {
                set_pixel(bmp, x, y, args->fill_color);
            }
        }
    }

    for (int s = -args->thickness+1; s < args->side_size + args->thickness; s++) {
        for (int t = 0; t < args->thickness; t++) {
            set_pixel(bmp, x0 + s, y0 + t, args->color);
            set_pixel(bmp, x0 + s, y0 - t, args->color);
            set_pixel(bmp, x0 + t, y0 + s, args->color);
            set_pixel(bmp, x0 - t, y0 + s, args->color);
            set_pixel(bmp, x0 + s, y1 + t, args->color);
            set_pixel(bmp, x0 + s, y1 - t, args->color);
            set_pixel(bmp, x1 + t, y0 + s, args->color);
            set_pixel(bmp, x1 - t, y0 + s, args->color);
        }
    }

    return CW_OK;
}

void swap_regions(bmp_t *bmp, int x0, int y0, int x1, int y1, int dx, int dy)
{
    for (int x = 0; x < dx; x++) {
        for (int y = 0; y < dy; y++) {
            rgb_t tmp = get_pixel(bmp, x0 + x, y0 + y);
            set_pixel(bmp, x0 + x, y0 + y, get_pixel(bmp, x1 + x, y1 + y));
            set_pixel(bmp, x1 + x, y1 + y, tmp);
        }
    }
}

int exchange_opion(bmp_t *bmp, args_t *args)
{
    if (args->exchange_type == EXCHANGE_UNKNOWN) {
        fputs("Exchange type is not specified\n", stderr);
        return CW_ERROR;
    }
    if (args->left_up.x == INT_MAX && args->left_up.y == INT_MAX) {
        fputs("Left up point is not specified\n", stderr);
        return CW_ERROR;
    }
    if (args->right_down.x == INT_MAX && args->right_down.y == INT_MAX) {
        fputs("Right down point is not specified\n", stderr);
        return CW_ERROR;
    }

    int x0 = args->left_up.x;
    int y0 = args->left_up.y;
    int x1 = args->right_down.x;
    int y1 = args->right_down.y;
    int dx = (x1 - x0) / 2;
    int dy = (y1 - y0) / 2;

    if (args->exchange_type == EXCHANGE_DIAGONALS) {
        swap_regions(bmp, x0, y0, x0 + dx, y0 + dy, dx, dy);
        swap_regions(bmp, x0 + dx, y0, x0, y0 + dy, dx, dy);
    }
    else if (args->exchange_type == EXCHANGE_CLOCKWISE) {
        swap_regions(bmp, x0, y0, x0, y0 + dy, dx, dy);
        swap_regions(bmp, x0 + dx, y0, x0, y0 + dy, dx, dy);
        swap_regions(bmp, x0 + dx, y0 + dy, x0, y0 + dy, dx, dy);
    }
    else {
        swap_regions(bmp, x0, y0, x0 + dx, y0, dx, dy);
        swap_regions(bmp, x0 + dx, y0, x0 + dx, y0 + dy, dx, dy);
        swap_regions(bmp, x0 + dx, y0 + dy, x0, y0 + dy, dx, dy);
    }

    return CW_OK;
}

typedef struct {
    rgb_t color;
    size_t freq;
} colorinfo_t;

#define BASE_SIZE 256
#define MAX_SEARCH 10

int find_color(colorinfo_t *colors, size_t size, rgb_t color)
{
    for (size_t i = 0; i < size; i++) {
        if (colors[i].color.r == color.r &&
            colors[i].color.g == color.g &&
            colors[i].color.b == color.b) {
            return i;
        }
    }
    return -1;
}

int cantor_pairing(int a, int b)
{
   return (a + b + 1) * (a + b) / 2 + b;
}

int hash_color(rgb_t color)
{
   return cantor_pairing(color.r, cantor_pairing(color.g, color.b));
}

int colors_equal(rgb_t a, rgb_t b)
{
    return a.r == b.r && a.g == b.g && a.b == b.b;
}

int increment_color(colorinfo_t *colors, size_t size, rgb_t color, int amount)
{
    int start_index = hash_color(color) % size;

    for (int i = 0; i < MAX_SEARCH; i++) {
        int index = (start_index + i) % size;

        if (colors[index].freq > 0 && colors_equal(colors[index].color, color)) {
            colors[index].freq += amount;
            return 1;
        }
    }

    // try to insert
    for (int i = 0; i < MAX_SEARCH; i++) {
        int index = (start_index + i) % size;

        if (colors[index].freq == 0) {
            colors[index].freq = 1;
            colors[index].color = color;
            return 1;
        }
    }

    return 0;
}

colorinfo_t *grow_colors(colorinfo_t *old_colors, size_t old_size, size_t new_size, size_t *out_size)
{
    colorinfo_t *new_colors = (colorinfo_t*)malloc(sizeof(colorinfo_t) * new_size);
    if (new_colors == NULL) {
        fputs("Memory allocation failed\n", stderr);
        free(old_colors);
        return NULL;
    }

    memset(new_colors, 0, sizeof(colorinfo_t) * new_size);

    for (size_t i = 0; i < old_size; i++) {
        if (old_colors[i].freq > 0) {
            if (!increment_color(new_colors, new_size, old_colors[i].color, old_colors[i].freq)) {
                free(new_colors);
                return grow_colors(old_colors, old_size, new_size * 2, out_size);
            }
        }
    }

    *out_size = new_size;
    free(old_colors);
    return new_colors;
}

int freq_color_option(bmp_t *bmp, args_t *args)
{
    if (!args->is_color_set) {
        fputs("Color is not specified\n", stderr);
        return CW_ERROR;
    }

    colorinfo_t *colors = malloc(sizeof(colorinfo_t) * BASE_SIZE);

    if (colors == NULL) {
        fputs("Memory allocation failed\n", stderr);
        return CW_ERROR;
    }

    size_t size = BASE_SIZE;
    memset(colors, 0, sizeof(colorinfo_t) * BASE_SIZE);

    for (int y = 0; y < (int)bmp->info.height; y++) {
        for (int x = 0; x < (int)bmp->info.width; x++) {
            int ret = increment_color(colors, size, get_pixel(bmp, x, y), 1);
            while (!ret) {
                size_t new_size;
                colors = grow_colors(colors, size, size * 2, &new_size);
                if (colors == NULL)
                    return CW_ERROR;

                size = new_size;
                ret = increment_color(colors, size, get_pixel(bmp, x, y), 1);
            }
        }
    }

    int best_i = 0;
    for (size_t i = 0; i < size; i++) {
        if (colors[i].freq > colors[best_i].freq)
            best_i = i;
    }

    rgb_t color = colors[best_i].color;
    for (int y = 0; y < (int)bmp->info.height; y++) {
        for (int x = 0; x < (int)bmp->info.width; x++) {
            if (bmp->data[y][x].r == color.r &&
                bmp->data[y][x].g == color.g &&
                bmp->data[y][x].b == color.b) {
                bmp->data[y][x] = args->color;
            }
        }
    }

    free(colors);
    return CW_OK;
}

int main(int argc, char **argv)
{
    puts("Course work for option 4.4, created by Kulach Daniil");

    args_t args;
    int function = '\0';

    init_args(&args);

    int opt = getopt_long(argc, argv, shortopts, longopts, NULL);
    while (opt!= -1) {
        if (opt == '?') {
            fputs("Invalid option\n", stderr);
            return CW_ERROR;
        }

        int ret = CW_OK;
        switch (opt) {
            case 'h':
                print_help();
                return CW_OK;
            case 'i':
            case FUNCTION_SQUARE:
            case FUNCTION_EXCHANGE:
            case FUNCTION_FREQ_COLOR:
                function = opt;
                break;
            case 'l':
                ret = read_point(&args.left_up, optarg);
                break;
            case 's':
                ret = read_int(&args.side_size, optarg);
                break;
            case 't':
                ret = read_int(&args.thickness, optarg);
                break;
            case 'c':
                ret = read_color(&args.color, optarg);
                args.is_color_set = 1;
                break;
            case 'f':
                args.fill = 1;
                break;
            case 'F':
                ret = read_color(&args.fill_color, optarg);
                args.is_fill_color_set = 1;
            case 'r':
                ret = read_point(&args.right_down, optarg);
                break;
            case 'x':
                ret = read_exchange_type(&args.exchange_type, optarg);
                break;
            case 'I':
                args.input = optarg;
                break;
            case 'O':
                args.output = optarg;
                break;
        }

        if (ret != CW_OK) {
            return CW_ERROR;
        }

        opt = getopt_long(argc, argv, shortopts, longopts, NULL);
    }

    if (function == '\0') {
        fputs("No function specified\n", stderr);
        return CW_ERROR;
    }

    if (args.input == NULL) {
        if (optind >= argc) {
            fputs("No image specified\n", stderr);
            return CW_ERROR;
        }
        args.input = argv[optind];
    }

    bmp_t bmp;
    if (load_bmp(&bmp, args.input) != CW_OK) {
        return CW_ERROR;
    }

    int ret = CW_OK;
    switch (function) {
        case 'i':
            ret = print_image_info_option(&bmp);
            break;
        case FUNCTION_SQUARE:
            ret = draw_square_option(&bmp, &args);
            break;
        case FUNCTION_EXCHANGE:
            ret = exchange_opion(&bmp, &args);
            break;
        case FUNCTION_FREQ_COLOR:
            ret = freq_color_option(&bmp, &args);
            break;
    }

    if (ret != CW_OK) {
        free_bmp(&bmp);
        return CW_ERROR;
    }

    if (function != 'i') {
        int ret = save_bmp(&bmp, args.output);
        if (ret != CW_OK) {
            return CW_ERROR;
        }
    }

    free_bmp(&bmp);
}