Assign determisitic Orcish names for debugging

Question

Orcish

Large volumes of unlabelled data are hard to visualize when debugging; I find it difficult to keep track of the pointers in memory. I have used this code to assign Orcish names, (it's a name because I capitalized the first letter.) I use it initialized in the data type itself (orcish), or based on a pointer value (orcify).

orcish.h

#include <stddef.h> /* size_t */
void orcish(char *, size_t);
void orcish_ptr(char *, const size_t, const void *);
const char *orcify(const void *);

orcish.c

/** @license 2014, 2021 Neil Edelman, distributed under the terms of the
 [MIT License](https://opensource.org/licenses/MIT). Contains some syllables
 from [SMAUG](http://www.smaug.org/), which is a derivative of
 [Merc](http://dikumud.com/Children/merc2.asp), and
 [DikuMud](http://dikumud.com/); used under fair-use. Contains
 [MurmurHash](https://github.com/aappleby/smhasher)-derived code, placed in
 public domain by Austin Appleby.

 @subtitle Name Generator

 Orcish names originate or are inspired by [JRR Tolkien's Orcish
 ](http://en.wikipedia.org/wiki/Languages_constructed_by_J._R._R._Tolkien).

 @std C89 */

#include <stdlib.h> /* rand */
#include <stdio.h>  /* strlen */
#include <ctype.h>  /* toupper */
#include <string.h> /* memcpy */
#include <assert.h> /* assert */
#include "orcish.h"

static const char *syllables[] = {
    "ub", "ul", "uk", "um", "uu", "oo", "ee", "uuk", "uru", "ick", "gn", "ch",
    "ar", "eth", "ith", "ath", "uth", "yth", "ur", "uk", "ug", "sna", "or",
    "ko", "uks", "ug", "lur", "sha", "grat", "mau", "eom", "lug", "uru", "mur",
    "ash", "goth", "sha", "cir", "un", "mor", "ann", "sna", "gor", "dru", "az",
    "azan", "nul", "biz", "balc", "balc", "tuo", "gon", "dol", "bol", "dor",
    "luth", "bolg", "beo", "vak", "bat", "buy", "kham", "kzam", "lg", "bo",
    "thi", "ia", "es", "en", "ion", "mok", "muk", "tuk", "gol", "fim", "ette",
    "moor", "goth", "gri", "shn", "nak", "ash", "bag", "ronk", "ask", "mal",
    "ome", "hi", "sek", "aah", "ove", "arg", "ohk", "to", "lag", "muzg", "ash",
    "mit", "rad", "sha", "saru", "ufth", "warg", "sin", "dar", "ann", "mor",
    "dab", "val", "dur", "dug", "bar", "ash", "krul", "gakh", "kraa", "rut",
    "udu", "ski", "kri", "gal", "nash", "naz", "hai", "mau", "sha", "akh",
    "dum", "olog", "lab", "lat"
};
static const unsigned syllables_size = sizeof syllables / sizeof *syllables;
static const unsigned syllables_max_length = 4;

static const char *suffixes[] = {
    "at", "ob", "agh", "uk", "uuk", "um", "uurz", "hai", "ishi", "ub", "ull",
    "ug", "an", "hai", "gae", "-hai", "luk", "tz", "hur", "dush", "ks", "mog",
    "grat", "gash", "th", "on", "gul", "gae", "gun", "dan", "og", "ar", "meg",
    "or", "lin", "dog", "ath", "ien", "rn", "bul", "bag", "ungol", "mog",
    "nakh", "gorg", "-dug", "duf", "ril", "bug", "snaga", "naz", "gul", "ak",
    "kil", "ku", "on", "ritz", "bad", "nya", "durbat", "durb", "kish", "olog",
    "-atul", "burz", "puga", "shar", "snar", "hai", "ishi", "uruk", "durb",
    "krimp", "krimpat", "zum", "gimb", "-gimb", "glob", "-glob", "sharku",
    "sha", "-izub", "-izish", "izg", "-izg", "ishi", "ghash", "thrakat",
    "thrak", "golug", "mokum", "ufum", "bubhosh", "gimbat", "shai", "khalok",
    "kurta", "ness", "funda"
};
static const unsigned suffixes_size = sizeof suffixes / sizeof *suffixes;
static const unsigned suffixes_max_length = 7;

static const unsigned max_name_size = 256;

/** Fills `name` with a random Orcish name. Potentially up to `name_size` - 1,
 (if zero, does nothing) then puts a null terminator. Uses `r` plugged into
 `recur` to generate random values in the range of `RAND_MAX`. */
static void orcish_recur(char *const name, size_t name_size,
    unsigned long r, unsigned (*recur)(unsigned long *)) {
    char *n = name;
    const char *part;
    size_t part_len;
    assert(name);
    if(!name_size) { return; }
    else if(name_size == 1) { *n = '\0'; return; }
    else if(name_size > max_name_size) { name_size = max_name_size; }
    /* Now `name_size \in [2, max_name_size]`. */
    if(name_size <= syllables_max_length + suffixes_max_length) {
        part = syllables[recur(&r) / (RAND_MAX / syllables_size + 1)];
        part_len = strlen(part);
        if(part_len >= name_size) part_len = name_size - 1;
        memcpy(n, part, part_len), n += part_len, name_size -= part_len;
        if(name_size > suffixes_max_length) {
            part = suffixes[recur(&r) / (RAND_MAX / suffixes_size + 1)];
            part_len = strlen(part);
            memcpy(n, part, part_len), n += part_len, name_size -= part_len;
        }
    } else {
        unsigned no_syllables = ((unsigned)name_size - 1 - suffixes_max_length)
            / syllables_max_length;
        while(no_syllables) {
            part = syllables[recur(&r) / (RAND_MAX / syllables_size +1)];
            part_len = strlen(part);
            memcpy(n, part, part_len), n += part_len, name_size -= part_len;
            no_syllables--;
        }
        part = suffixes[recur(&r) / (RAND_MAX / suffixes_size + 1)];
        part_len = strlen(part);
        memcpy(n, part, part_len), n += part_len, name_size -= part_len;
    }
    *n = '\0';
    *name = (char)toupper(*name);
}

/** <https://github.com/aappleby/smhasher> `src/MurmurHash3.cpp fmix64`.
 @return Recurrence on `k`. */
static unsigned long fmix_long(unsigned long k) {
    k ^= k >> 33;
    k *= 0xff51afd7ed558ccd;
    k ^= k >> 33;
    k *= 0xc4ceb9fe1a85ec53;
    k ^= k >> 33;
    return k;
}

/* Advances `r`.
 @return Number in `[0, RAND_MAX]`. @implements `orcish_recur` */
static unsigned murmur_recur(unsigned long *const r)
    { return (*r = fmix_long(*r)) % (1lu + RAND_MAX); }

/** Uses `rand`; ignores `r` and uses a global variable set by `srand`.
 @return Number in `[0, RAND_MAX]`. @implements `orcish_recur` */
static unsigned rand_recur(unsigned long *const r)
    { (void)r; return (unsigned)rand(); }

/** Fills `name` with a random Orcish name. Potentially up to `name_size` - 1,
 then puts a null terminator. Uses `rand` from `stdlib.h`.
 @param[name_size] If zero, does nothing. */
void orcish(char *const name, const size_t name_size)
    { orcish_recur(name, name_size, 0, &rand_recur); }

/** Fills `name` with a deterministic Orcish name based on `p`. Potentially up
 to `name_size` - 1, then puts a null terminator.
 @param[name_size] If zero, does nothing. */
void orcish_ptr(char *const name, const size_t name_size,
    const void *const p) {
    assert(name);
    if(!p) {
        if(!name_size) return;
        switch(name_size) {
        default:
        case 5: name[3] = 'l';
        case 4: name[2] = 'l';
        case 3: name[1] = 'u';
        case 2: name[0] = 'n';
        case 1: break;
        }
        name[name_size < 5 ? name_size - 1 : 4] = '\0';
    } else {
        orcish_recur(name, name_size, (unsigned long)p, &murmur_recur);
    }
}

/** A convenient way to call <fn:orcish_ptr> with `p`.
 @return A string in a small temporary buffer that can handle four names at a
 time. */
const char *orcify(const void *const p) {
    static char strs[4][12];
    static unsigned str;
    str %= sizeof strs / sizeof *strs;
    orcish_ptr(strs[str], sizeof *strs, p);
    return strs[str++];
}

Using a MurmerHash3 64-bit mixer has been good on all the computers I've tested it on; I don't know what happens if size_t is smaller; I don't want to include the C99 stdint.h. How hard would multi-threaded support be? I'm also wondering about the copyright: can I take out a portion of GPL code and say that it's now covered in a more permissive MIT license? (The syllables are mostly GPL, as far as I could tell, but they probably came from Tolkien; is it fair use as I have claimed?)

main

I wrote up main that shows orcify in a real situation. Linking it gives a whole program, but it's example code. It outputs in GraphViz which has an on-line editor: ./orc > orc.gv.

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "orcish.h"

enum order { PRE, POST };

struct tree { struct node *root; };
struct node { size_t edges; struct node *edge[3]; };
struct visit { void (*f)(struct node *); enum order order; };

/** Non-zero parameter set by the `node.edge` count, and number of nodes. */
static const size_t max_edges
    = sizeof ((struct node *)0)->edge / sizeof *((struct node *)0)->edge,
    max_nodes = max_edges * 5;
/** Inverse bushiness, `[0, RAND_MAX]`. */
static int straightness = (int)(RAND_MAX * 0.08);

static struct node *node(void) {
    struct node *n = malloc(sizeof *n);
    if(!n) return 0;
    n->edges = 0;
    return n;
}

/** One must set the order to `POST`, otherwise undefined.
 @implements `visit` */
static void node_(struct node *const n) { assert(n); free(n); }

/** @implements `visit` */
static void out(struct node *const n) {
    size_t e = 0;
    assert(n);
    printf("\tn%p [label=\"%s\"];\n", (void *)n, orcify(n));
    while(e < n->edges)
        printf("\tn%p -> n%p;\n", (void *)n, (void *)n->edge[e++]);
}

static void node_edge(struct node *const n, struct node *const edge) {
    assert(n && edge && n->edges < max_edges);
    n->edge[n->edges++] = edge;
}

static struct node *node_rand_edge(const struct node *const n) {
    assert(n);
    return n->edges ? n->edge[(size_t)rand() / (RAND_MAX / n->edges + 1)] : 0;
}

static void visit_node(struct node *const n,
    const struct visit *const v) {
    size_t e;
    assert(v && v->f);
    if(!n) return;
    if(v->order == PRE) v->f(n);
    for(e = 0; e < n->edges; e++) visit_node(n->edge[e], v);
    if(v->order == POST) v->f(n);
}

static void visit(struct tree *const g,
    const enum order order, void (*const f)(struct node *)) {
    struct visit v;
    assert(g && f);
    v.f = f;
    v.order = order;
    visit_node(g->root, &v);
}

int main(void) {
    struct tree t = { 0 };
    struct node *n, *m;
    size_t i;
    int success = 0;
    for(i = 0; i < max_nodes; i++) {
        size_t e;
        int acc;
        if(!(n = node())) goto catch;
        if(!t.root) { t.root = n; continue; }
        m = t.root;
        /* Knuth's Poisson distribution with fixed point, RAND_MAX ~ 1. */
        for(acc = rand(); e = m->edges; m = node_rand_edge(m)) {
            if(e == max_edges) continue;
            if(acc <= straightness) break;
            acc = (int)((long)rand() * acc / (1l + RAND_MAX));
        }
        node_edge(m, n);
    }
    printf("digraph {\n"
        "\tnode [shape=box, style=filled, fillcolor=Grey95];\n");
    visit(&t, PRE, &out);
    printf("}\n");
    fprintf(stderr, "Random path from the root: { ");
    for(n = t.root; n; n = node_rand_edge(n))
        fprintf(stderr, "%s%s", n == t.root ? "" : ", ", orcify(n));
    fprintf(stderr, " }.\n");
    { success = 1; goto finally; }
catch:
    perror("graph");
finally:
    visit(&t, POST, &node_);
    return success;
}

Answer 1

Header needs an include guard.

---

orcish_ptr() is defined with a const size_t argument, but the const plays no part in the signature, so omit that.

---

It's a good practice for orcish.c to include "orcish.h" as its very first header. This helps detect any inadvertent dependencies, and ensures that the header is self-sufficient.

---

    switch(name_size) {
    default:
    case 5: name[3] = 'l';
    case 4: name[2] = 'l';
    case 3: name[1] = 'u';
    case 2: name[0] = 'n';
    case 1: break;
    }

We probably want to label the fall-through at the end of each case here, to prevent someone "fixing" it (and to suppress compiler warnings).

Actually, the switch might be better replaced with a call to strncpy():

if (p) {
    orcish_recur(name, name_size, (unsigned long)p, &murmur_recur);
} else if (name_size) {
    strncpy(name, "null", name_size-1);
    name[name_size-1] = '\0';
}
/* else there's nothing we can do here */

If we targeted C99 or later, snprintf(name, name_size, "null") would be better, as that writes the necessary terminating null char, unlike strncpy().

---

Other than that, I got no compiler warnings, and Valgrind gives full marks for the test program.

---

    { success = 1; goto finally; }

I think we have success and failure the wrong way around here - we should return zero to indicate successful execution. More clearly, use EXIT_SUCCESS here, and EXIT_FAILURE otherwise.

---

The helper functions in orcify.c (that are not mentioned in the header) are all declared with static linkage so they don't pollute the program's namespace. That's good.

There's no need to write static for the file-scope variable names (since that's the default), but it does no harm and is arguably helpful to readers.

---

I keep getting distracted by the function names ending in _recur. That suggests recursion, but the functions are not recursive - they are just alternative implementations.

---

    *name = (char)toupper(*name);

Best practice is to always convert the argument to toupper() into unsigned char, even if you believe that it can only ever be positive (I don't know of EBCDIC systems with signed char, but it's at least theoretically possible):

    *name = (char)toupper((unsigned char)*name);

---

static void orcish_recur(char *const name, … {
    ⋮
    assert(name);

I don't think that assertion is correct, because name comes unchecked from the user code, via

void orcish(char *const name, const size_t name_size)
    { orcish_recur(name, name_size, 0, &rand_recur); }

Similarly, orcish_ptr cannot assert name either - that has come from outside our code.

---

There is a lot of repetition of this pattern:

    part = syllables[recur(&r) / (RAND_MAX / syllables_size + 1)];

Consider abstracting that into a function or perhaps a macro:

#define RANDOM_MEMBER(set)\
    set[recur(&r) / (RAND_MAX / set ## _size + 1)];

static void orcish_recur(char *const name, size_t name_size,
    ⋮
}

#undef RANDOM_MEMBER

Answer 2

in addition to Toby Speight's answer:

C89 compliance / platform independence:

static unsigned long fmix_long(unsigned long k)
{
  k ^= k >> 33;
  k *= 0xff51afd7ed558ccd;
  k ^= k >> 33;
  k *= 0xc4ceb9fe1a85ec53;
  k ^= k >> 33;
  return k;
}

An unsigned long is only guaranteed to be at least 32 bits (e.g. the 64-bit MSVC compiler has only 32 bit unsigned longs), so shifting by 33 may be undefined behavior. The constants may also be truncated to 32 bits.

We should use a 32 bit hash and/or add platform-dependent typedefs for integer types that we expect to be a specific size (a union can be used to check type sizes as at the bottom of this article).

(Or we could just use stdint.h).

---

static const size_t max_edges
    = sizeof ((struct node *)0)->edge / sizeof *((struct node *)0)->edge,
    max_nodes = max_edges * 5;

Technically max_edges isn't a "constant" (in C89), so max_nodes can't be initialized like this.

We need to use a #define or an enum.

---

algorithm:

if(name_size <= syllables_max_length + suffixes_max_length) {
        ... add syllable
        if(name_size > suffixes_max_length) {
            ... add suffix
        }
    } else {
        unsigned no_syllables = ((unsigned)name_size - 1 - suffixes_max_length)
            / syllables_max_length;
        while(no_syllables) {
            ... add syllable
            no_syllables--;
        }
        ... add suffix
    }

Besides abstracting the "add foo" parts to a separate function, I think we can simplify the logic a bit here by calculating the number of syllables first, roughly:

num_syllables = ... (has space for suffix) ? (subtract and divide, min value 1) : 1;

for (; num_syllables; --num_syllables)
    ... add syllable

if (still has space for suffix)
    ... add suffix

---

documentation:

It would probably be a good idea to document locally how the algorithm works, instead of only referring people to other sources (links can die). This could include pointing out the effects of a small or large name_size on the number of syllables and suffix.

(It looks like people passing in a large name_size will always get long(er) names, whether they want them or not... which isn't necessarily intuitive).