#define _XOPEN_SOURCE 700
#define _POSIX_C_SOURCE 200809L
#include <sys/stat.h>
#include <dirent.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pwd.h>
#include <grp.h>
#include <time.h>

struct entry {
    char *name;
    struct stat st;
};

static int dflag, lflag, nflag, pflag, rflag, sflag, tflag, uflag, Fflag;

static int
compar(const void *a, const void *b)
{
    const struct entry *left = a, *right = b;
    int result;
    if (tflag) {
        time_t x = uflag ? left->st.st_atime : left->st.st_mtime;
        time_t y = uflag ? right->st.st_atime : right->st.st_mtime;
        result = x > y ? -1 : x < y ? 1 : strcmp(left->name, right->name);
    } else result = strcmp(left->name, right->name);
    return rflag ? -result : result;
}

static void
format(const struct stat *st, const char *name, const char *prefix)
{
    if (sflag) printf("%ju ", (uintmax_t)st->st_size / 1024 + (st->st_size % 1024 != 0));
    if (lflag) {
        char mode[] = "----------", date[64] = "?";
        const char *bits = "rwxrwxrwx";
        struct passwd *user = getpwuid(st->st_uid);
        struct group *group = getgrgid(st->st_gid);
        time_t stamp = uflag ? st->st_atime : st->st_mtime;
        struct tm *tm = localtime(&stamp);
        int i;
        if (S_ISDIR(st->st_mode)) mode[0] = 'd';
        else if (S_ISLNK(st->st_mode)) mode[0] = 'l';
        else if (S_ISFIFO(st->st_mode)) mode[0] = 'p';
        else if (S_ISCHR(st->st_mode)) mode[0] = 'c';
        else if (S_ISBLK(st->st_mode)) mode[0] = 'b';
        else if (S_ISSOCK(st->st_mode)) mode[0] = 's';
        for (i = 0; i < 9; ++i) if (st->st_mode & (0400 >> i)) mode[i+1] = bits[i];
        if (st->st_mode & S_ISUID) mode[3] = mode[3] == 'x' ? 's' : 'S';
        if (st->st_mode & S_ISGID) mode[6] = mode[6] == 'x' ? 's' : 'S';
        if (st->st_mode & S_ISVTX) mode[9] = mode[9] == 'x' ? 't' : 'T';
        if (tm) (void)strftime(date, sizeof(date), "%b %e %H:%M", tm);
        printf("%s %ju ", mode, (uintmax_t)st->st_nlink);
        if (user) printf("%s ", user->pw_name); else printf("%ju ", (uintmax_t)st->st_uid);
        if (group) printf("%s ", group->gr_name); else printf("%ju ", (uintmax_t)st->st_gid);
        printf("%jd %s ", (intmax_t)st->st_size, date);
    }
    if (prefix) printf("%s%s", prefix, prefix[strlen(prefix)-1] == '/' ? "" : "/");
    printf("%s%s\n", name, Fflag ? (S_ISDIR(st->st_mode) ? "/" :
           (st->st_mode & 0111) ? "*" : "") : "");
}

static int
ls(const char *path, int prefix)
{
    struct stat st;
    struct entry *entries = NULL;
    struct dirent *entry;
    DIR *dir;
    size_t count = 0, i;
    int status = 0;
    if (lstat(path, &st) < 0) { perror(path); return 1; }
    if (!S_ISDIR(st.st_mode) || dflag) { format(&st, path, NULL); return 0; }
    dir = opendir(path);
    if (dir == NULL) { perror(path); return 1; }
    for (;;) {
        struct entry *newentries;
        errno = 0;
        entry = readdir(dir);
        if (entry == NULL) { if (errno) { perror(path); status = 1; } break; }
        if (strcmp(entry->d_name, ".") == 0 || strcmp(entry->d_name, "..") == 0) continue;
        if (fstatat(dirfd(dir), entry->d_name, &st, AT_SYMLINK_NOFOLLOW) < 0) {
            perror(entry->d_name); status = 1; continue;
        }
        if (count >= SIZE_MAX / sizeof(*entries)) { errno = ENOMEM; perror("ls"); status = 1; break; }
        newentries = realloc(entries, (count + 1) * sizeof(*entries));
        if (newentries == NULL) { perror("ls: realloc"); status = 1; break; }
        entries = newentries;
        entries[count].name = strdup(entry->d_name);
        if (entries[count].name == NULL) { perror("ls: strdup"); status = 1; break; }
        entries[count].st = st;
        ++count;
    }
    if (!nflag && count > 1) qsort(entries, count, sizeof(*entries), compar);
    for (i = 0; i < count; ++i) {
        format(&entries[i].st, entries[i].name, prefix && !pflag ? path : NULL);
        free(entries[i].name);
    }
    free(entries);
    if (closedir(dir) < 0) { perror(path); status = 1; }
    return status;
}

int
main(int argc, char **argv)
{
    int option, status = 0;
    while ((option = getopt(argc, argv, "dlnprstuF")) != -1) {
        switch (option) {
        case 'd': dflag = 1; break;
        case 'l': lflag = 1; break;
        case 'n': nflag = 1; break;
        case 'p': pflag = 1; break;
        case 'r': rflag = 1; break;
        case 's': sflag = 1; break;
        case 't': tflag = 1; break;
        case 'u': uflag = 1; break;
        case 'F': Fflag = 1; break;
        default: fprintf(stderr, "usage: %s [-dlnprstuF] [file...]\n", argv[0]); return 1;
        }
    }
    if (optind == argc) status = ls(".", 0);
    for (; optind < argc; ++optind) status |= ls(argv[optind], 1);
    if (fflush(stdout) == EOF || ferror(stdout)) { perror("ls: stdout"); status = 1; }
    return status;
}