path: root/compiler/misc.c

/*

  misc.c -- Miscellaneous internal utility functons.

  Copyright © 2011-2017 Samuel Lidén Borell <samuel@kodafritt.se>

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  THE SOFTWARE.

*/

#include <errno.h>
#include <string.h>

#include "misc.h"
#include "platform.h"

static void linprobset_expand(LinProbSet *lps);


/**
 * Like realloc(), but frees the pointer on error.
 */
void *try_realloc(void *p, size_t size)
{
    char *np = realloc(p, size);
    if (np) return np;
    
    /* Error */
    free(p);
    return NULL;
}

/* Standard implementation of strndup, which is from C99 */
char *lrl_strndup(const char *s, size_t len)
{
    char *dup = malloc(len+1);
    
    if (!dup) return NULL;
    
    memcpy(dup, s, len);
    dup[len] = '\0';
    return dup;
}

/* Standard implementation of strdup, which is from C99 */
char *lrl_strdup(const char *s)
{
    size_t len = strlen(s);
    return lrl_strndup(s, len);
}

/**
 * Hashes sequence of bytes. Intended to be fast, but NOT secure against
 * pre-image attacks etc.
 */
LRLHashCode hash_bytes(const unsigned char *bytes, size_t length)
{
#if LRL_HASH_BITS == 64
#define LRL_HASH_INIT  0xFEDCBA9876543210UL
#define LRL_HASH_A     53
#define LRL_HASH_B     0x31415UL
#define LRL_HASH_C     13
#define LRL_HASH_D     57
#define LRL_HASH_E     27
#define LRL_HASH_F     17

#elif LRL_HASH_BITS == 32
#define LRL_HASH_INIT  0xFDB97531UL
#define LRL_HASH_A     25
#define LRL_HASH_B     0x31415UL
#define LRL_HASH_C     7
#define LRL_HASH_D     27
#define LRL_HASH_E     13
#define LRL_HASH_F     9

#else
#error Unsupported value of LRL_HASH_BITS
#endif
    /* TODO replace with some proven hash function */
    LRLHashCode h = LRL_HASH_INIT;
    int i;
    for (i = 0; i < 2; i++) {
        size_t l = length;
        const unsigned char *byte = bytes;
        while (l--) {
            LRLHashCode b = *(byte++);
            b ^= (b-1) << LRL_HASH_A;
            h -= LRL_HASH_B;
            h += b;
            h += h >> LRL_HASH_C;
            h ^= b << LRL_HASH_D;
            b += h;
            h += b >> LRL_HASH_E;
        }
        h += h << LRL_HASH_F;
    }
    return h;
}

/**
 * Hashes a string. See hash_bytes()
 */
LRLHashCode hash_name(const char *name, size_t length)
{
    return hash_bytes((const unsigned char*)name, length);
}

/**
 * Combines two hashes by concatenating them and hashing the result.
 */
LRLHashCode hash_merge(LRLHashCode a, LRLHashCode b)
{
#if LRL_HASH_BITS == 64
    unsigned char bytes[16];
    bytes[0] = a & 0xff;
    bytes[1] = (a >> 8) & 0xff;
    bytes[2] = (a >> 16) & 0xff;
    bytes[3] = (a >> 24) & 0xff;
    bytes[4] = (a >> 32) & 0xff;
    bytes[5] = (a >> 40) & 0xff;
    bytes[6] = (a >> 48) & 0xff;
    bytes[7] = (a >> 56) & 0xff;
    
    bytes[8] = b & 0xff;
    bytes[9] = (b >> 8) & 0xff;
    bytes[10] = (b >> 16) & 0xff;
    bytes[11] = (b >> 24) & 0xff;
    bytes[12] = (b >> 32) & 0xff;
    bytes[13] = (b >> 40) & 0xff;
    bytes[14] = (b >> 48) & 0xff;
    bytes[15] = (b >> 56) & 0xff;
#else
    unsigned char bytes[8];
    bytes[0] = a & 0xff;
    bytes[1] = (a >> 8) & 0xff;
    bytes[2] = (a >> 16) & 0xff;
    bytes[3] = (a >> 24) & 0xff;
    
    bytes[4] = b & 0xff;
    bytes[5] = (b >> 8) & 0xff;
    bytes[6] = (b >> 16) & 0xff;
    bytes[7] = (b >> 24) & 0xff;
#endif
    return hash_bytes(bytes, sizeof(bytes));
}

/**
 * Forces initialization of a linearly probed set. The "bits" parameter
 * specify how many bits are used for addressing initially, and also controls
 * the size of the set (size = 2^bits).
 *
 * The "bits" parameter must be at least 1.
 *
 * Note that if the structure has been memset/calloc'ed, the initialization is
 * done automatically on the first linprobset_add_hashcode() call.
 */
void linprobset_init(LinProbSet *lps, size_t bits)
{
    lps->size = bits;
    lps->set = calloc(1<<bits, sizeof(LRLHashCode));
}

/**
 * Adds a hashcode to a set of hashcodes. Linear probing is used.
 * Returns 1 if the item existed before the call, and 0 otherwise.
 *
 * Note that 0 is not a valid value to be added.
 */
int linprobset_add_hashcode(LinProbSet *lps, LRLHashCode hashcode)
{
    size_t max, steps;
    LRLHashCode *p, *last;
    
    if (!lps->set) {
        linprobset_init(lps, 2);
    }
    
  restart:
    max = ((1 << lps->size) - 1);
    p = &lps->set[hashcode & max];
    last = &lps->set[max];
    steps = 0;
    for (;;) {
        LRLHashCode cell = *p;
        if (cell == hashcode) return 1; /* Already exists */
        if (cell == 0) {
            /* Add */
            *p = hashcode;
            if (steps >> (lps->size-1)) {
                linprobset_expand(lps);
            }
            return 0;
        }
        if (++p > last) {
            p = lps->set; /* Wrap around */
            if (steps > max) {
                linprobset_expand(lps);
                goto restart;
            }
        }
        steps++;
    }
}

/**
 * Expands the set to twice its size. Then reorganizes
 * the set according to the new size.
 */
static void linprobset_expand(LinProbSet *lps)
{
    size_t max, oldsize;
    short limit;
    LRLHashCode *p, *last;
    
    oldsize = (1<<lps->size);
    lps->size++;
    lps->set = realloc(lps->set, (1<<lps->size)*sizeof(LRLHashCode));
    memset(&lps->set[oldsize], 0, oldsize*sizeof(LRLHashCode));
    
    max = ((1 << lps->size) - 1);
    last = &lps->set[max];
    limit = 10;
    for (p = lps->set; p <= last;) {
        LRLHashCode a;
        
        a = *p;
        if (a) {
            LRLHashCode *q = &lps->set[a & max];
          try_next:
            if (p != q) {
                LRLHashCode b = *q;
                if ((a & max) != (b & max)) {
                    /* Possible to switch here */
                    *q = a;
                    *p = b;
                    if (b && --limit) {
                        continue; /* Check this one again */
                    }
                } else {
                    if (++q > last) q = lps->set; /* Wrap around */
                    goto try_next;
                }
            }
        }
        limit = 10;
        p++;
    }
}

/**
 * Moves the given string pointer past all path separators.
 */
void skip_path_sep(const char **path)
{
    *path += strspn(*path, "/\\");
}

/**
 * Returns the end of the first path element in the given string.
 */
const char *end_of_path_elem(const char *path)
{
    return path + strcspn(path, "/\\");
}

/**
 * Creates the output filename based on the source filename, and an optional
 * output directory. The is_exec parameter controls whether the object file
 * or executable filename is returned.
 */
char *get_output_filename(const char *source_filename, const char *outdir,
                          int is_exec)
{
    const char *end;
    const char *ext;
    size_t dirlen = (outdir ? strlen(outdir)+1 : 0);
    size_t extlen, baselen;
    char *output;
    
    /* Determine start of the name of the file */
    const char *basename = strrchr(source_filename, '/');
    const char *basename_win = strrchr(source_filename, '\\');
    if ((uintptr_t)basename_win > (uintptr_t)basename) {
        basename = basename_win;
    } else if (!basename) {
        basename = source_filename;
    }
    
    /* The "name" of the input ends at the first dot */
    end = strchr(basename, '.');
    if (!end) end = basename + strlen(basename);
    
    if (is_exec) {
        /* TODO should .exe be added on Windows, and where in the code? */
        ext = "";
        extlen = 0;
    } else {
        ext = ".o";
        extlen = 2;
    }
    
    baselen = end-source_filename;
    output = malloc(dirlen+baselen+extlen+1);
    if (outdir) {
        memcpy(output, outdir, dirlen-1);
        output[dirlen-1] = PATHSEP[0];
    }
    memcpy(output+dirlen, source_filename, baselen);
    memcpy(output+dirlen+baselen, ext, extlen);
    output[dirlen+baselen+extlen] = '\0';
    return output;
}

/**
 * Reads from a file until EOF, and then null-terminates the result.
 * On error (or if the file is a directory), it returns NULL.
 */
char *file_get_contents(FILE *file)
{
    size_t capacity, size;
    char *contents;
    
    if (!check_not_dir(file)) return NULL;
    
    size = 0;
    capacity = 4096;
    contents = malloc(capacity+1);
    if (!contents) return NULL;
    
    for (;;) {
        /* Fill the buffer with data */
        size_t chunk_size = capacity-size;
        size_t numread = fread(&contents[size], 1, chunk_size, file);
        
        size += numread;
        
        /* If wasn't filled, then we reached then end */
        if (numread != chunk_size) break;
        
        /* Double the buffer size */
        if (capacity*2 < capacity) {
            /* Don't try to allocate more than 50% of the address space */
            free(contents);
            errno = EOVERFLOW;
            return NULL;
        }
        capacity *= 2;
        contents = try_realloc(contents, capacity);
        if (!contents) goto end;
    }
    
    contents[size] = '\0';
    contents = realloc(contents, size+1);
  end:
    return contents;
}

/**
 * Reads a file or from stdin if filename is "-". The file contents are
 * null-terminated. On error (or if the file is a directory), it returns NULL.
 */
char *read_input(const char *filename)
{
    if (!strcmp(filename, "-")) {
        /* Read from standard in */
        return file_get_contents(stdin);
    } else {
        /* Read from a file */
        FILE *f = fopen(filename, "rb");
        if (f) {
            char *contents = file_get_contents(f);
            fclose(f);
            return contents;
        } else {
            return NULL;
        }
    }
}

/**
 * Aborts the program with an error message.
 * Use only for "impossible" errors.
 */
NORETURN void fail(const char *error_id)
{
    volatile short *c = (short*)0xabc;
    
    fprintf(stderr, "lrlc: internal error (this is a bug!): %s\n", error_id);
    
    /* Unlike abort(), this is regarded as a crash, which means we get nice
       debugging things like stack traces and core dumps. */
    *c;
    
    /* If we fail to crash */
    abort();
}