initial commit

9 files changed, 564 insertions, 0 deletions

diff --git a/.gitattributes b/.gitattributes
new file mode 100644
index 0000000..5d123f0
--- /dev/null
+++ b/.gitattributes
@@ -0,0 +1,5 @@
+* text=auto
+
+*.c text
+*.h text
+*.txt text
diff --git a/COPYING b/COPYING
new file mode 100644
index 0000000..26b72ee
--- /dev/null
+++ b/COPYING
@@ -0,0 +1,17 @@
+Copyright (C) 2015 Oskari Timperi
+
+This software is provided 'as-is', without any express or implied
+warranty. In no event will the authors be held liable for any damages
+arising from the use of this software.
+
+Permission is granted to anyone to use this software for any purpose,
+including commercial applications, and to alter it and redistribute it
+freely, subject to the following restrictions:
+
+1. The origin of this software must not be misrepresented; you must not
+   claim that you wrote the original software. If you use this software
+   in a product, an acknowledgment in the product documentation would be
+   appreciated but is not required.
+2. Altered source versions must be plainly marked as such, and must not be
+   misrepresented as being the original software.
+3. This notice may not be removed or altered from any source distribution.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..89431e5
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,35 @@
+# Specify HOST to cross compile
+# HOST = i686-w64-mingw32
+
+CC = $(HOST)-gcc
+LD = $(HOST)-gcc
+
+CFLAGS += -std=c99 -Wall -g
+
+SOURCES = main.c htable.c
+
+ifneq ($(findstring Windows,$(OS)),)
+BUILD_WIN32 = 1
+RM = del
+else ifneq ($(findstring mingw,$(HOST)),)
+BUILD_WIN32 = 1
+RM = rm -f
+endif
+
+ifneq ($(BUILD_WIN32),)
+E = .exe
+SOURCES += randgen_win32.c
+else
+E =
+SOURCES += randgen_unix.c
+endif
+
+OBJECTS = $(SOURCES:%.c=%.o)
+
+diceware$(E): $(OBJECTS)
+	$(LINK.c) -o $@ $^
+
+.PHONY: clean
+clean:
+	$(RM) $(OBJECTS)
+	$(RM) diceware$(E)
diff --git a/htable.c b/htable.c
new file mode 100644
index 0000000..b8ccdec
--- /dev/null
+++ b/htable.c
@@ -0,0 +1,132 @@
+#include "htable.h"
+
+#include <assert.h>
+#include <string.h>
+
+/*
+
+    Simple hash table implementation. Uses the numeric id of the words as the
+    key.
+
+*/
+
+void htable_grow(struct htable *htable, size_t newmax);
+
+int htable_put(struct htable *htable, struct htable_entry *entry)
+{
+    unsigned long i, key;
+
+    assert(htable != NULL);
+    assert(entry != NULL);
+    assert(htable->max > 0);
+
+    if ((htable->size * 100) / (htable->max) >= 70)
+    {
+        htable_grow(htable, htable->max * 1.5);
+    }
+
+    key = strtol(entry->id, NULL, 10);
+
+    for (i = 0; 1; ++i)
+    {
+        unsigned long hash = (key + i) % htable->max;
+
+        if (!htable->elems[hash])
+        {
+            htable->elems[hash] = entry;
+            ++htable->size;
+            return 0;
+        }
+    }
+
+    return -1;
+}
+
+struct htable_entry *htable_get(struct htable *htable, const char *id)
+{
+    unsigned long i, key;
+
+    assert(htable != NULL);
+    assert(id != NULL);
+
+    if (htable->size == 0)
+        return NULL;
+
+    key = strtol(id, NULL, 10);
+
+    for (i = 0; 1; ++i)
+    {
+        unsigned long hash = (key + i) % htable->max;
+
+        if (!htable->elems[hash])
+            return NULL;
+
+        if (strcmp(htable->elems[hash]->id, id) == 0)
+            return htable->elems[hash];
+    }
+
+    return NULL;
+}
+
+void htable_init(struct htable *htable, size_t max)
+{
+    assert(htable != NULL);
+    assert(max > 0);
+
+    htable->size = 0;
+    htable->max = max;
+    htable->elems = (struct htable_entry **) malloc(sizeof(struct htable_entry *) * max);
+    memset(htable->elems, 0, sizeof(struct htable_entry *) * max);
+}
+
+void htable_deinit(struct htable *htable)
+{
+    assert(htable != NULL);
+
+    if (htable->size > 0)
+    {
+        size_t i;
+
+        for (i = 0; i < htable->max; ++i)
+        {
+            if (htable->elems[i])
+            {
+                free(htable->elems[i]->id);
+                free(htable->elems[i]->word);
+                free(htable->elems[i]);
+            }
+        }
+    }
+
+    htable->size = 0;
+    htable->max = 0;
+
+    free(htable->elems);
+}
+
+void htable_grow(struct htable *htable, size_t newmax)
+{
+    struct htable tmp;
+    size_t i;
+
+    assert(htable != NULL);
+    assert(htable->max > 0);
+    assert(newmax > htable->max);
+
+    htable_init(&tmp, newmax);
+
+    for (i = 0; i < htable->max; ++i)
+    {
+        if (htable->elems[i])
+        {
+            htable_put(&tmp, htable->elems[i]);
+        }
+    }
+
+    htable->size = 0;
+    htable_deinit(htable);
+
+    htable->size = tmp.size;
+    htable->max = tmp.max;
+    htable->elems = tmp.elems;
+}
diff --git a/htable.h b/htable.h
new file mode 100644
index 0000000..e3a75ff
--- /dev/null
+++ b/htable.h
@@ -0,0 +1,25 @@
+#ifndef HTABLE_H
+#define HTABLE_H
+
+#include <stdlib.h>
+
+struct htable_entry
+{
+    char *id;
+    char *word;
+};
+
+struct htable
+{
+    size_t size;
+    size_t max;
+    struct htable_entry **elems;
+};
+
+
+int htable_put(struct htable *htable, struct htable_entry *entry);
+struct htable_entry *htable_get(struct htable *htable, const char *id);
+void htable_init(struct htable *htable, size_t max);
+void htable_deinit(struct htable *htable);
+
+#endif
diff --git a/main.c b/main.c
new file mode 100644
index 0000000..e0f7a99
--- /dev/null
+++ b/main.c
@@ -0,0 +1,254 @@
+#include "randgen.h"
+#include "htable.h"
+
+#include <assert.h>
+#include <stdio.h>
+#include <errno.h>
+#include <string.h>
+
+/*
+    Generates a random id of length `size-1` consisting of characters in the set
+    [1-6] and places it in the buffer pointed to by `id`. The buffer is NULL
+    terminated.
+*/
+int get_random_id(struct randgen *randgen, char *id, size_t size)
+{
+    size_t n = 0;
+    unsigned char buf[512];
+    size_t i;
+
+    assert(randgen != NULL);
+    assert(id != NULL);
+    assert(size > 0);
+
+    while (n < size-1)
+    {
+        if (randgen_generate(randgen, buf, sizeof(buf)) == -1)
+            return -1;
+
+        for (i = 0; i < sizeof(buf) && n < size-1; ++i)
+        {
+            if (buf[i] >= '1' && buf[i] <= '6')
+            {
+                id[n++] = buf[i];
+            }
+        }
+    }
+
+    id[size-1] = '\0';
+
+    return 0;
+}
+
+/*
+    Makes a copy of the supplied string. If `len` is < 0, strlen() is used to
+    calculate the string length. The resulting string is always NULL terminated.
+*/
+char *my_strdup(const char *s, int len)
+{
+    char *result;
+    assert(s != NULL);
+    if (len < 0)
+        len = strlen(s);
+    result = (char *) malloc(sizeof(char) * (len+1));
+    memcpy(result, s, len);
+    result[len] = '\0';
+    return result;
+}
+
+/*
+    Parse a line from a diceware dictionary file. An acceptable line is of the
+    form:
+
+        11111 aaabbbccc
+
+    where 11111 is the word id in decimal digits and aaabbbccc is a word
+    stopping at first whitespace.
+
+    Returns a pointer to a htable_entry on success, NULL otherwise. Calls
+    exit() if memory could not be allocated.
+*/
+struct htable_entry *parse_line(const char *line)
+{
+    struct htable_entry *entry;
+    char id[32];
+    char word[256];
+
+    assert(line != NULL);
+
+    if (sscanf(line, "%31[1-6] %255s", id, word) != 2)
+    {
+        return NULL;
+    }
+
+    entry = (struct htable_entry *) malloc(sizeof(*entry));
+    if (!entry)
+    {
+        fprintf(stderr, "%s\n", strerror(errno));
+        exit(EXIT_FAILURE);
+    }
+
+    entry->id = my_strdup(id, -1);
+    entry->word = my_strdup(word, -1);
+
+    return entry;
+}
+
+/*
+    Loads a diceware dictionary file. Returns 0 on success and -1 on error.
+*/
+int load_dictionary(const char *filename, struct htable *dict)
+{
+    FILE *fp;
+    int rc = -1;
+    struct htable_entry *entry;
+    char line[256];
+
+    if ((fp = fopen(filename, "r")) == NULL)
+    {
+        fprintf(stderr, "could not open %s: %s\n", filename, strerror(errno));
+        goto cleanup;
+    }
+
+    while (1)
+    {
+        if (!fgets(line, sizeof(line), fp))
+            break;
+
+        if ((entry = parse_line(line)) == NULL)
+            continue;
+
+        htable_put(dict, entry);
+    }
+
+    rc = 0;
+
+cleanup:
+
+    if (fp)
+        fclose(fp);
+
+    return rc;
+}
+
+/*
+    Returns a random word from a dictionary.
+*/
+char *get_random_word(struct randgen *randgen, struct htable *dict)
+{
+    struct htable_entry *entry;
+    char id[6];
+
+    assert(randgen != NULL);
+    assert(dict != NULL);
+
+    if (get_random_id(randgen, id, sizeof(id)) == -1)
+    {
+        fprintf(stderr, "%s\n", "get_random_id failed");
+        return NULL;
+    }
+
+    entry = htable_get(dict, id);
+
+    if (!entry)
+    {
+        fprintf(stderr, "no such word: %s\n", id);
+        return NULL;
+    }
+
+    return entry->word;
+}
+
+void usage(const char *prog)
+{
+    static const char *usagestr =
+        "%s [-d DICTIONARY] [-n COUNT]"
+#ifndef _WIN32
+        " [-r DEVICE]"
+#endif
+        "\n\n"
+        "\t-d use DICTIONARY as the dictionary file\n"
+        "\t-n output COUNT words\n"
+#ifndef _WIN32
+        "\t-r read random bytes from DEVICE\n"
+#endif
+        "\n";
+
+    fprintf(stderr, usagestr, prog);
+
+    exit(EXIT_FAILURE);
+}
+
+int main(int argc, char **argv)
+{
+    const char *dictfilename = "diceware.txt";
+    const char *randomdevice = NULL;
+
+    int words = 6;
+    int i = 0;
+    struct htable dict;
+    struct randgen *randgen = NULL;
+    int rc = 0;
+
+    memset(&dict, 0, sizeof(dict));
+
+    for (i = 1; i < argc; ++i)
+    {
+        if (!strcmp(argv[i], "-d") && i+1 < argc)
+        {
+            dictfilename = argv[++i];
+        }
+        else if (!strcmp(argv[i], "-n") && i+1 < argc)
+        {
+            words = atoi(argv[++i]);
+        }
+#ifndef _WIN32
+        else if (!strcmp(argv[i], "-r") && i+1 < argc)
+        {
+            randomdevice = argv[++i];
+        }
+#endif
+        else if (!strcmp(argv[i], "-h"))
+        {
+            usage(argv[0]);
+        }
+        else
+        {
+            usage(argv[0]);
+        }
+    }
+
+    if ((randgen = randgen_open(randomdevice)) == NULL)
+        goto error;
+
+    htable_init(&dict, 11000);
+
+    if (load_dictionary(dictfilename, &dict) == -1)
+        goto error;
+
+    for (i = 0; i < words; ++i)
+    {
+        char *word = get_random_word(randgen, &dict);
+        if (!word)
+        {
+            goto error;
+        }
+        printf("%s%s", i ? " " : "", word);
+    }
+
+    printf("\n");
+
+    goto finally;
+
+error:
+
+    rc = 1;
+
+finally:
+
+    randgen_close(randgen);
+
+    htable_deinit(&dict);
+
+    return rc;
+}
diff --git a/randgen.h b/randgen.h
new file mode 100644
index 0000000..dd2596a
--- /dev/null
+++ b/randgen.h
@@ -0,0 +1,12 @@
+#ifndef RANDGEN_H
+#define RANDGEN_H
+
+#include <stdlib.h>
+
+struct randgen;
+
+struct randgen *randgen_open(const char *device);
+int randgen_close(struct randgen *randgen);
+int randgen_generate(struct randgen *randgen, void *buf, size_t size);
+
+#endif
diff --git a/randgen_unix.c b/randgen_unix.c
new file mode 100644
index 0000000..f7d12bb
--- /dev/null
+++ b/randgen_unix.c
@@ -0,0 +1,42 @@
+#include "randgen.h"
+
+#include <stdio.h>
+#include <string.h>
+#include <errno.h>
+#include <assert.h>
+
+struct randgen *randgen_open(const char *device)
+{
+    const char *filename = "/dev/urandom";
+    FILE *fp;
+
+    if (device)
+        filename = device;
+
+    if ((fp = fopen(filename, "r")) == NULL)
+    {
+        fprintf(stderr, "failed to open random generator (%s): %s\n", filename, strerror(errno));
+        return NULL;
+    }
+
+    return (struct randgen *) fp;
+}
+
+int randgen_close(struct randgen *randgen)
+{
+    assert(randgen != NULL);
+    fclose((FILE *) randgen);
+    return 0;
+}
+
+int randgen_generate(struct randgen *randgen, void *buf, size_t size)
+{
+    assert(randgen != NULL);
+    assert(buf != NULL);
+    assert(size > 0);
+
+    if (fread(buf, 1, size, (FILE *) randgen) != size)
+        return -1;
+
+    return 0;
+}
diff --git a/randgen_win32.c b/randgen_win32.c
new file mode 100644
index 0000000..d0b4123
--- /dev/null
+++ b/randgen_win32.c
@@ -0,0 +1,42 @@
+#include "randgen.h"
+
+#include <windows.h>
+#include <wincrypt.h>
+
+#include <stdio.h>
+#include <assert.h>
+
+struct randgen *randgen_open(const char *device)
+{
+    HCRYPTPROV prov;
+
+    (void) device;
+
+    if (!CryptAcquireContextW(&prov, 0, 0, PROV_RSA_FULL,
+        CRYPT_VERIFYCONTEXT | CRYPT_SILENT))
+    {
+        fprintf(stderr, "failed to open random generator: CryptAcquireContextW failed\n");
+        return NULL;
+    }
+
+    return (struct randgen *) prov;
+}
+
+int randgen_close(struct randgen *randgen)
+{
+    assert(randgen != NULL);
+    CryptReleaseContext((HCRYPTPROV) randgen, 0);
+    return 0;
+}
+
+int randgen_generate(struct randgen *randgen, void *buf, size_t size)
+{
+    assert(randgen != NULL);
+    assert(buf != NULL);
+    assert(size > 0);
+
+    if (!CryptGenRandom((HCRYPTPROV) randgen, size, buf))
+        return -1;
+
+    return 0;
+}