<|start_filename|>groupby.c<|end_filename|>
/* group series of tab-separated values by their first column,
outputting the first field and the total of a configurable count field */

#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
    size_t bufsize = 256;
    char* buf = malloc(bufsize);
    char last[512];
    long long total = 0;
    int count_field;
    if (argc != 2)
        errx(1, "usage: %s <count_field>", argv[0]);
    if ((count_field = atoi(argv[1])) < 2)
        errx(1, "count_field must be at least 2");

    while (!feof(stdin)) {
        int field_index = 0;
        getline(&buf, &bufsize, stdin);

        char *tab = buf;
        while (++field_index != count_field && *tab) {
            while (*tab && *tab != '\t')
                tab++;
            *tab++ = 0;
        }
        if (field_index != count_field)
            continue;

        if (strcmp(buf, last)) {
            if (total)
                printf("%s\t%lld\n", last, total);
            strncpy(last, buf, sizeof(last)-1);
            total = 0;
        }

        total += atoll(tab);
    }

    if (total)
        printf("%s\t%lld\n", last, total);
}


<|start_filename|>Makefile<|end_filename|>
all: abbrase wordlist_bigrams.txt wordgen

PREFIX?=/usr/local
datadir?=${PREFIX}/share/abbrase
CFLAGS=-Wall -Wextra -Os -DDATADIR=${datadir}

CORPUS_EXEMPLAR=googlebooks-eng-1M-2gram-20090715-99.csv.zip

data/${CORPUS_EXEMPLAR}:
	mkdir -p data
	cd data
	gsutil && gsutil -m cp -n gs://books/ngrams/books/googlebooks-eng-1M-1gram-20090715-* . \
		&& gsutil -m cp -n gs://books/ngrams/books/googlebooks-eng-1M-2gram-20090715-* .
	gsutil || (curl -O -C - 'http://storage.googleapis.com/books/ngrams/books/googlebooks-eng-1M-1gram-20090715-[0-9].csv.zip' \
		&& curl -O -C - 'http://storage.googleapis.com/books/ngrams/books/googlebooks-eng-1M-2gram-20090715-[0-99].csv.zip')


# the ngrams data is 'mostly sorted' -- lines tend to be in order, but it occasionally restarts
# do a groupby (join records from different years into one) to reduce the data volume, then final sort+groupby
data/1gram.csv.gz: | data/${CORPUS_EXEMPLAR} groupby
	zcat data/googlebooks-eng-1M-1gram-*.csv.zip | pv | ./groupby 3 | LC_ALL=c sort | ./groupby 2 | gzip -9 > $@

data/2gram.csv.gz: | data/${CORPUS_EXEMPLAR} groupby
	zcat data/googlebooks-eng-1M-2gram-*.csv.zip | pv | ./groupby 3 | LC_ALL=c sort | ./groupby 2 | gzip -9 > $@

# extract the 100,000 most common words
data/1gram_common.csv: data/1gram.csv.gz
	zcat $< | sort -rgk2 | head -n 100000 > $@

data/prefixes.txt: data/1gram_common.csv
	cat $< | sed 's/^\(...\).*\t/\1\t/' | grep '^[a-z]\{3\}' | LC_ALL=c sort | ./groupby 2 | sort -rgk2 | grep -v iii | head -n 1024 > $@

wordlist_bigrams.txt:
	# relies on data/prefixes.txt data/2gram.csv.gz,
	# but I don't know how to tell Make to only generate those if
	# this target is missing
	pypy3 digest.py

clean:
	rm -f abbrase wordgen

install: all
	install -d $(DESTDIR)$(PREFIX)/bin $(DESTDIR)$(datadir)/
	install abbrase $(DESTDIR)$(PREFIX)/bin
	install wordgen $(DESTDIR)$(PREFIX)/bin
	install wordlist_bigrams.txt $(DESTDIR)$(datadir)/


<|start_filename|>index.html<|end_filename|>
<!DOCTYPE html>
<html>
<head>
	<title>Abbrase.js</title>
	<script src="abbrase.js"></script>
	<style type="text/css">
	body { background-color: #222; color: #ccc; font-family: sans-serif; }
	pre { border: 1px solid #888; padding: 10px; overflow-x: auto; }
	a { color: #44f; }
	#content { width: 800px; margin: auto;}
	#wordcount { width: 3em; }
	</style>
</head>
<body>
<a href="https://github.com/rmmh/abbrase"><img style="position: absolute; top: 0; left: 0; border: 0;" src="forkme.png"></a>

<div id="content">

<h1>Abbrase</h1>
Password generation using abbreviated phrases<br><br>


<input type="button" onclick="newbatch();" value="Generate"> passwords using
<input id="wordcount" type="number" min="1" max="100" value="5" onchange="newbatch();"> word phrases.

<pre id="output"></pre>


<h2>How does this work?</h2>
First, <span id="explain_count"></span> secure random numbers are generated. Each number ranges from 0-1023, giving 10 bits of entropy.
<pre id="explain_numbers"></pre>
Each number is converted into a three letter abbreviation. The password is made by joining them together. Abbreviations are taken from a pool of the 1024 most common English word prefixes.
<pre id="explain_password"></pre>
Finally, a phrase is found that abbreviates to the password. Words that are normally found together are chosen to make the phrase more memorable.
<pre id="explain_mnemonic"></pre>
The mnemonic is much easier to remember than the input numbers, but equally secure!<br>
<br>
All steps are performed locally in your browser, and not sent to any other server. For more security, try the Python or C versions in the Abbrase <a href="https://github.com/rmmh/abbrase">github repository</a>.

</div>

<script type="text/javascript">
var graph = new WordGraph("wordlist_bigrams.txt");
var generator = new PassphraseGenerator(graph);

function setTextContent(id, text) {
	document.getElementById(id).textContent = text;
}

graph.onprogress = function(perc) {
	if (perc < 0)
		setTextContent("output", "Error downloading: HTTP Error " + -perc);
	else
		setTextContent("output", "Downloading 20MB word list... " + perc + "% done");
}
graph.onprogress(0);

function newbatch() {
	var length = parseInt(document.getElementById("wordcount").value) || 5;

	var example_password = generator.gen_password(length);
	setTextContent("explain_count", length);
	setTextContent("explain_numbers", pretty_arraybuffer(example_password.numbers));
	setTextContent("explain_password", <PASSWORD>);
	setTextContent("explain_mnemonic", example_password.mnemonic);

	setTextContent("output", generator.make_table(length, 32));
}

graph.onready = newbatch;
graph.load();
</script>
</body>
</html>


<|start_filename|>abbrase.c<|end_filename|>
#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <fcntl.h>
#include <libgen.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define MAX_PREFIXES 1024
#define PREFIX_LEN 3

struct IntVec {
  int len;
  int cap;
  int *data;
};

struct IntVec *intvec_alloc() {
  struct IntVec *vec = malloc(sizeof *vec);
  vec->len = 0;
  vec->cap = 1;
  vec->data = malloc(sizeof(int) * vec->cap);
  return vec;
}

void intvec_free(struct IntVec *vec) {
  free(vec->data);
  free(vec);
}

void intvec_append(struct IntVec *vec, int val) {
  if (vec->len == vec->cap) {
    vec->cap *= 2;
    vec->data = realloc(vec->data, sizeof(int) * vec->cap);
  }
  vec->data[vec->len++] = val;
}

int intvec_get(struct IntVec *vec, int pos) {
  if (pos < 0 || pos >= vec->len)
    err(10, "invalid vector index %d not in [0, %d)", pos, vec->len);
  return vec->data[pos];
}

struct IntVec *intvec_copy(struct IntVec *vec) {
  /* could be faster, but no need to optimize */
  struct IntVec *ret = intvec_alloc();
  int i;
  for (i = 0; i < vec->len; i++)
    intvec_append(ret, vec->data[i]);
  return ret;
}

void intvec_print(struct IntVec *vec) {
  int i;
  printf("[");
  for (i = 0; i < vec->len; i++) {
    if (i != 0)
      printf(", ");
    printf("%d", vec->data[i]);
  }
  printf("]");
}

/* return a new IntVec with the elements in common between a and b.
   Requires a and b to be sorted. */
struct IntVec *intvec_intersect(struct IntVec *a, struct IntVec *b) {
  struct IntVec *ret = intvec_alloc();
  int ai = 0, bi = 0;
  while (ai < a->len && bi < b->len) {
    int diff = a->data[ai] - b->data[bi];
    if (diff == 0) {
      intvec_append(ret, a->data[ai]);
      ai++, bi++;
    } else if (diff < 0) {
      ai++;
    } else if (diff > 0) {
      bi++;
    }
  }
  return ret;
}

struct Prefix {
  char prefix[PREFIX_LEN];
  struct IntVec *words;
};

int prefix_cmp(const void *a, const void *b) {
  return memcmp(((const struct Prefix*)a)->prefix,
                ((const struct Prefix*)b)->prefix, PREFIX_LEN);
}

struct WordGraph {
  int n_words;
  int n_prefixes;
  char **words;
  char **followers_compressed;
  struct Prefix prefixes[MAX_PREFIXES];
};

void getline_trimmed(char **target, FILE *stream) {
  size_t n, len;
  n = 0;
  *target = NULL;
  if (getline(target, &n, stream) == -1)
    err(1, "corrupted wordgraph file");
  len = strlen(*target);
  if ((*target)[len - 1] == '\n')
    (*target)[len - 1] = 0;
}

struct WordGraph *wordgraph_init(FILE *graph_file) {
  int i, j;
  struct WordGraph *g = malloc(sizeof *g);
  if (fscanf(graph_file, "%d ", &g->n_words) != 1)
    err(1, "corrupted wordgraph file");
  g->n_prefixes = 0;
  g->words = calloc(g->n_words, sizeof g->words[0]);
  g->followers_compressed = calloc(g->n_words, sizeof g->words[0]);
  for (i = 1; i < g->n_words; i++) {
    getline_trimmed(&g->words[i], graph_file);
    /* extract lowercase prefix */
    char prefix[PREFIX_LEN];
    for (j = 0; j < PREFIX_LEN; j++)
        prefix[j] = tolower(g->words[i][j]);
    /* add word to a prefix group */
    for (j = 0; j <= g->n_prefixes; ++j) {
      if (j == g->n_prefixes) {
        /* none found, need to insert */
        if (g->n_prefixes == MAX_PREFIXES)
          errx(2, "corrupted wordgraph file: too many prefixes");
        g->n_prefixes++;
        memcpy(g->prefixes[j].prefix, prefix, PREFIX_LEN);
        g->prefixes[j].words = intvec_alloc();
      }
      if (!memcmp(g->prefixes[j].prefix, prefix, PREFIX_LEN)) {
        intvec_append(g->prefixes[j].words, i);
        break;
      }
    }
  }
  /* sort prefixes (so passwords can be enumerated in order) */
  qsort(g->prefixes, g->n_prefixes, sizeof(struct Prefix), prefix_cmp);

  if (g->n_prefixes != MAX_PREFIXES)
    errx(3, "corrupted wordgraph file: not enough prefixes");
  for (i = 0; i < g->n_words; i++)
    getline_trimmed(&g->followers_compressed[i], graph_file);
  return g;
}

void wordgraph_free(struct WordGraph *g) {
  int i;
  for (i = 0; i < g->n_words; i++) {
    free(g->words[i]);
    free(g->followers_compressed[i]);
  }
  for (i = 0; i < g->n_prefixes; i++) {
    intvec_free(g->prefixes[i].words);
  }
  free(g->words);
  free(g->followers_compressed);
  free(g);
}

/* decode an adjacency list encoded as a string */
struct IntVec *decode(char *enc) {
  /*
  general encoding steps:
  input: [1, 2, 3, 5, 80]
  subtract previous value: [1, 1, 1, 2, 75]
  subtract 1: [0, 0, 0, 1, 74]
  contract runs of zeros: [0x3, 1, 74]
  printably encode numbers as base-32 varints,
  and runs of zeros as the 31 leftover characters:
  output: "bA*B"

  this function reverses the steps.

  Cf. decode in digest.py
  */
  int enc_ind = 0;
  struct IntVec *dec = intvec_alloc();
  int last_num = 0;
  int zero_run = 0;
  while (enc[enc_ind] || zero_run) {
    int delta = 0;
    int delta_ind = 0;
    if (zero_run)
      zero_run--;
    else {
      unsigned char val = enc[enc_ind];
      if (val >= 0x60) {
        zero_run = enc[enc_ind] & 0x1f;
        delta_ind++;
      } else {
        /* decode base-32 varint */
        do {
          val = enc[enc_ind + delta_ind];
          delta |= (val & 0x1f) << (5 * delta_ind);
          delta_ind++;
        } while (val & 0x20);
      }
    }
    enc_ind += delta_ind;
    last_num += delta + 1;
    intvec_append(dec, last_num);
  }
  return dec;
}

void wordgraph_dump(struct WordGraph *g, int a, int b) {
  int i;
  for (i = a; i < b; i++) {
    printf("#%d: %s: %.30s ", i, g->words[i], g->followers_compressed[i]);
    struct IntVec *followers = decode(g->followers_compressed[i]);
    intvec_print(followers);
    intvec_free(followers);
    printf("\n");
  }
}

static int min(int a, int b) {
  if (a <= b)
    return a;
  return b;
}

int edit_distance(const char *a, const char *b) {
  // code based off http://hetland.org/coding/python/levenshtein.py

  int n = strlen(a), m = strlen(b);

  if (n > m) {
    // ensure n <= m, to use O(min(n,m)) space
    const char *tmp_s = a;
    a = b;
    b = tmp_s;
    int tmp_i = n;
    n = m;
    m = tmp_i;
  }

  int cost[n + 1];

  int i, j;
  int ins, del, sub;
  int prevdiag; // lets us store only one row + one cell at a time

  const int insert_cost = 1;
  const int gap_cost = 1;
  const int mismatch_cost = 1;

  for (i = 0; i < n + 1; ++i)
    cost[i] = i * insert_cost;

  for (i = 1; i < m + 1; ++i) {
    prevdiag = cost[0];
    cost[0] = i * gap_cost;

    for (j = 1; j < n + 1; ++j) {
      ins = cost[j] + gap_cost;
      del = cost[j - 1] + gap_cost;
      sub = prevdiag;
      if (a[j - 1] != b[i - 1])
        sub += mismatch_cost;
      prevdiag = cost[j];
      cost[j] = min(ins, min(del, sub));
    }
  }

  return cost[n];
}

/* find the closest word to the input */
int wordgraph_find_word(struct WordGraph *g, const char *word) {
  int i, best_word = 0, best_dist = 10000;
  for (i = 1; i < g->n_words; i++) {
    int dist = edit_distance(word, g->words[i]);
    if (dist < best_dist) {
      best_dist = dist;
      best_word = i;
    }
  }
  return best_word;
}

/* pick series of prefixes that will make up the passwords */
void generate_prefixes(int *prefix_indices_out, int length) {
  int fd_crypto, i;
  if ((fd_crypto = open("/dev/urandom", O_RDONLY)) < 0)
    err(5, "unable to get secure random numbers");

  int read_len = sizeof(*prefix_indices_out) * length;
  if (read(fd_crypto, prefix_indices_out, read_len) != read_len)
    err(6, "unable to read random numbers");

  for (i = 0; i < length; i++) {
    prefix_indices_out[i] &= MAX_PREFIXES - 1;
  }

  close(fd_crypto);
}

/* generate a reasonably memorable phrase for the prefixes */
int generate_mnemonic(
  struct WordGraph *g, int *prefix_indices, int *word_indices_out, int length) {
  /* find possible words for each of the chosen prefixes */
  int i, j;

  struct IntVec *word_sets[length];
  for (i = 0; i < length; i++) {
    word_sets[i] = intvec_copy(g->prefixes[prefix_indices[i]].words);
  }

  /* working backwards, reduce possible words for each prefix to only
     those words that have a link to a word in the next set of possible words
   */
  int mismatch = 0; /* track how many links were impossible */
  struct IntVec *next_words, *new_words, *followers, *words, *intersect;
  next_words = NULL;
  for (i = length - 1; i >= 0; i--) {
    words = word_sets[i];
    new_words = intvec_alloc();
    if (next_words) {
      for (j = 0; j < words->len; j++) {
        int word = intvec_get(words, j);
        followers = decode(g->followers_compressed[word]);
        intersect = intvec_intersect(next_words, followers);
        if (intersect->len)
          intvec_append(new_words, word);
        intvec_free(intersect);
        intvec_free(followers);
      }
    }
    if (new_words->len) {
      intvec_free(word_sets[i]);
      word_sets[i] = new_words;
    } else {
      intvec_free(new_words);
      mismatch++;
    }

    next_words = word_sets[i];
  }

  /* working forwards, pick a word for each prefix */
  int last_word = word_indices_out[0];
  for (i = 0; i < length; i++) {
    followers = decode(g->followers_compressed[last_word]);
    intersect = intvec_intersect(word_sets[i], followers);
    /* Picking the first word available biases the phrase towards more
     * common words, and produces generally satisfactory results.
     * N.B.: to save space, adjacency lists don't encode probabilities */
    last_word = intvec_get(intersect->len ? intersect : word_sets[i], 0);
    word_indices_out[i] = last_word;
    intvec_free(followers);
    intvec_free(intersect);
  }

  for (i = 0; i < length; i++) {
    intvec_free(word_sets[i]);
  }

  return mismatch;
}

void write_passphrase(
    struct Prefix *prefixes, int *prefix_indices, int length, char *buf) {
  int i;
  for (i = 0; i < length; i++)
    sprintf(buf + 3 * i, "%.3s", prefixes[prefix_indices[i]].prefix);
}

void run_tests(struct WordGraph *g) {
  /* enumerate passphrases, assert that there are as many as we expect */
  int i, length = 2;
  long expected = 1L << (length * 10L);
  long actual = 0;

  int prefix_indices[length];
  char passphrase[length * 3 + 1], last_passphrase[length * 3 + 1];

  last_passphrase[0] = 0;
  bzero(prefix_indices, sizeof(prefix_indices));
  while (1) {
    write_passphrase(g->prefixes, prefix_indices, length, passphrase);
    if (strcmp(passphrase, last_passphrase) > 0) {
      actual++;
    } else {
      errx(40, "passphrase out of order! %s -> %s",
        last_passphrase, passphrase);
    }
    memcpy(last_passphrase, passphrase, sizeof(last_passphrase));

    /* next passphrase */
    for (i = length - 1; i >= 0; --i) {
      prefix_indices[i]++;
      if (prefix_indices[i] != MAX_PREFIXES)
        break;
      prefix_indices[i] = 0;
    }
    if (i == -1)
      break;
  }

  if (actual != expected)
    errx(42, "test failed! expected: %ld != actual: %ld", expected, actual);
}

FILE *open_graph_file(char *executable, const char *graph_filename) {
  // #1 try cwd
  FILE *graph_file = fopen(graph_filename, "r");
  if (!graph_file) {
    // #2: try executable directory
    char *binary_dir = dirname(executable);
    char path[256];
    snprintf(path, 255, "%s/%s", binary_dir, graph_filename);
    graph_file = fopen(path, "r");
  }
#ifdef DATADIR
#define QUOTE(name) #name
#define STR(macro) QUOTE(macro)
  if (!graph_file) {
    // #3: datadir
    char path[256];
    snprintf(path, 255, STR(DATADIR) "/%s", graph_filename);
    graph_file = fopen(path, "r");
  }
#endif
  return graph_file;
}

int main(int argc, char *argv[]) {
  struct WordGraph *g ;
  const char *graph_filename = "wordlist_bigrams.txt";
  FILE *graph_file = open_graph_file(argv[0], graph_filename);

  if (!graph_file)
    err(1, "unable to find %s", graph_filename);

  g = wordgraph_init(graph_file);
  //wordgraph_dump(g, 0, 3000);


  long length = 0;
  long count = 0;
  int start_word = 0;
  int i, c;

  while ((c = getopt(argc, argv, "ht")) != -1) {
    switch (c) {
      case 't':
        run_tests(g);
        return 0;
      case 'h':
      default:
        errx(1, "usage: [-h]/[-t] [length] [count] [hook word]");
    }
  }

  for (i = 1; i < argc; i++) {
    errno = 0;
    if (length == 0) {
      length = strtol(argv[i], NULL, 10);
      if (!errno && length > 0)
        continue;
      length = 0;
    } else if (count == 0) {
      count = strtol(argv[i], NULL, 10);
      if (!errno && count > 0)
        continue;
      count = 0;
    }
    start_word = wordgraph_find_word(g, argv[i]);
  }

  if (!length)
    length = 5;

  if (!count)
    count = 32;

  printf("Generating %ld passwords with %ld bits of entropy\n", count,
         length * 10);

  if (start_word)
    printf("    hook: %s\n", g->words[start_word]);

  int pass_len = length * 3;
  printf("%-*s    %s\n", pass_len, "Password", "Mnemonic");
  for (i = 0; i < pass_len; i++)
    putchar('-');
  printf("    ");
  for (i = 0; i < length * 4; i++)
    putchar('-');
  printf("\n");

  while (count--) {
    int prefix_indices[length];
    int word_indices[length];
    char passphrase[3 * length + 1];
    word_indices[0] = start_word;
    generate_prefixes(prefix_indices, length);
    generate_mnemonic(g, prefix_indices, word_indices, length);

    write_passphrase(g->prefixes, prefix_indices, length, passphrase);
    printf("%s   ", passphrase);

    if (start_word)
      printf(" %s", g->words[start_word]);

    for (i = 0; i < length; i++)
      printf(" %s", g->words[word_indices[i]]);

    printf("\n");
  }

  wordgraph_free(g);

  return 0;
}


<|start_filename|>wordgen.c<|end_filename|>
#include <ctype.h>
#include <err.h>
#include <errno.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/random.h>
#include <unistd.h>

const uint32_t trigrams[] = {
    0,         33518332,  35951138,  35951394,  44335650,  58685182,  2396706,
    35967778,  35684898,  1896600,   2130466,   53794,     35684898,  35684898,
    2130466,   33387102,  36475682,  2097152,   2130722,   45349674,  44335906,
    1929216,   2130466,   295714,    0,         2130466,   33314,     0,
    0,         36492855,  37657387,  49133567,  794641,    1086051,   2945699,
    557091,    6058136,   32770,     34079267,  41794303,  36565543,  108714943,
    0,         37589799,  2097152,   48234495,  37468971,  104657775, 18706589,
    33314,     547447,    33315,     8958583,   67142178,  0,         45963932,
    33591842,  32770,     2097664,   48133115,  0,         0,         32768,
    6150399,   2097184,   0,         35684898,  544,       32800,     62780055,
    0,         0,         2130466,   3179049,   299042,    68973276,  32,
    0,         0,         1638401,   0,         0,         8222941,   0,
    2396962,   0,         10318455,  0,         0,         45937527,  73265407,
    0,         46003063,  2130466,   0,         0,         117306367, 0,
    2097152,   35684898,  1,         2945635,   1962620,   0,         0,
    0,         1048589,   0,         0,         117273309, 299010,    2097154,
    33853986,  31323135,  2130434,   8736,      32800,     75362558,  2129920,
    0,         33587746,  33314,     34,        100528825, 262658,    0,
    35684898,  1094441,   256,       913454,    546,       33314,     0,
    541217,    0,         0,         83720413,  2396710,   37526314,  36491959,
    98401117,  37524067,  2945699,   2130466,   6060248,   2129954,   528929,
    41529983,  2748967,   75364347,  4026520,   4035363,   2097152,   50200575,
    45853499,  45912943,  6119440,   33314,     824119,    3244843,   565797,
    67109408,  0,         16546444,  0,         0,         0,         3961403,
    36475427,  0,         0,         85741822,  0,         0,         35684898,
    0,         0,         28103306,  0,         0,         2130466,   1,
    34079265,  68972728,  0,         0,         0,         513,       0,
    0,         113078941, 32768,     0,         0,         43840307,  0,
    33853986,  10015271,  73199806,  0,         0,         35684898,  34,
    565795,    8180407,   0,         0,         2130466,   1048833,   256,
    1896994,   0,         2,         0,         286725,    0,         0,
    117275389, 32770,     0,         32768,     31322747,  2097152,   0,
    32768,     73267455,  0,         0,         33587744,  34,        33312,
    16644799,  512,       0,         2130466,   1048577,   34100067,  1863900,
    0,         32802,     0,         1650705,   0,         0,         1929373,
    2888231,   37526315,  44618419,  16535769,  36737632,  11334563,  512,
    0,         0,         546,       41466623,  2748967,   66846719,  4026521,
    4043555,   2097152,   45988543,  4177919,   104657771, 8192,      4227618,
    512,       1049123,   0,         67142178,  0,         44114572,  0,
    0,         0,         10227752,  0,         0,         0,         1065092,
    0,         0,         0,         0,         0,         36442764,  0,
    0,         0,         0,         0,         1860240,   0,         0,
    0,         0,         0,         0,         35393685,  33282,     0,
    32770,     43831349,  2097664,   0,         32770,     1929276,   0,
    0,         35684896,  2,         33314,     2146304,   33312,     0,
    32770,     1061123,   32768,     69632,     0,         32770,     0,
    4099,      0,         0,         134052541, 33314,     2130722,   823905,
    66974719,  2884129,   546,       32768,     73398527,  0,         524835,
    36299647,  557603,    32,        50328319,  1082146,   0,         33587712,
    1114915,   103580451, 18742014,  546,       2,         0,         77423531,
    0,         0,         121470909, 2920995,   0,         0,         10285247,
    2129920,   0,         0,         85750011,  0,         0,         33554976,
    35684898,  547,       16644767,  37524259,  0,         32768,     1049345,
    0,         1863896,   0,         0,         0,         1572865,   0,
    0,         16612093,  2392610,   36999970,  44954479,  67105535,  2396706,
    37540711,  2130466,   75233791,  2129952,   34361891,  33587746,  32802,
    35684898,  16642813,  299522,    2097152,   2130466,   11662315,  44888867,
    1962750,   2130466,   33538,     32,        8193,      514,       0,
    18708696,  7919143,   3447594,   44602043,  6046229,   3703395,   36500387,
    33314,     1855576,   32,        533027,    41466495,  34202215,  50331647,
    73235197,  37597987,  2097152,   46004991,  37331755,  37589807,  1921212,
    2130466,   1700663,   33554977,  533027,    33312,     0,         50295485,
    294912,    32768,     2,         10342651,  0,         0,         35426851,
    85850362,  0,         0,         35684898,  34,        32800,     33422008,
    35951138,  0,         2130466,   36733731,  2654755,   1929436,   0,
    2,         0,         262657,    0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         0,         0,         0,
    0,         0,         0,         0,         33314,     0,         0,
    0,         0,         0,         0,         117276669, 2920995,   2396962,
    2921251,   67108863,  2658851,   35951138,  33587746,  75233535,  2097186,
    528931,    34112051,  36213539,  2663011,   66977791,  2921251,   2097152,
    35685154,  3261227,   111997935, 1667838,   33314,     295202,    0,
    9040419,   0,         0,         50166493,  2129954,   2396962,   546,
    67073023,  2130466,   2392064,   45412911,  90042622,  2097152,   36176419,
    35684898,  2654755,   2130466,   12448511,  36475683,  2097152,   2129952,
    45216623,  44954471,  881406,    32,        33314,     0,         553481,
    0,         0,         66943709,  295458,    299266,    32768,     29225215,
    2130434,   262146,    44954231,  73398527,  2,         0,         33587746,
    32802,     544,       29227775,  299522,    0,         35684898,  3154729,
    36475427,  1962622,   0,         295458,    0,         340481,    545,
    0,         6050460,   4044607,   3443498,   34079411,  1855607,   4160,
    2642851,   0,         73224250,  0,         32,        7994107,   2744935,
    16776191,  3408384,   37589807,  0,         41810687,  37313327,  79557631,
    8192,      544,       0,         2097185,   0,         67108896,  0,
    4027037,   0,         0,         0,         52196019,  0,         0,
    0,         73191678,  0,         0,         0,         0,         0,
    45357576,  0,         0,         0,         0,         0,         4096,
    512,       0,         0,         1,         0,         0,         56392412,
    294946,    0,         266784,    1856054,   2097152,   0,         33314,
    6123768,   0,         512,       524833,    2,         524833,    10809344,
    0,         0,         33314,     66337,     33024,     0,         0,
    0,         0,         1,         0,         0,         1056904,   0,
    2396706,   0,         811032,    0,         0,         33282,     1634362,
    0,         0,         0,         0,         0,         278528,    2396706,
    0,         0,         0,         2392610,   262146,    0,         0,
    0,         1,         0,         0,         8681480,   32802,     37154,
    262658,    1839123,   2097152,   294914,    32768,     540704,    0,
    0,         37410,     123430,    1081898,   2375824,   1622818,   0,
    33282,     1057315,   800,       8,         0,         32802,     0,
    0,         32,        0,         1851393,   0,         0,         0,
    806931,    0,         0,         0,         86048,     0,         0,
    544,       0,         0,         49152,     0,         0,         0,
    0,         0,         0,         0,         0,         0,         1,
    33559075};

#define BIG_WORDS 16
typedef struct {
  uint32_t val[BIG_WORDS];
} big;

void big_iadd(big *dst, big *src) {
  int carry = 0;
  for (int i = 0; i < BIG_WORDS; i++) {
    uint64_t tmp =
        (uint64_t)dst->val[i] + (uint64_t)src->val[i] + +(uint64_t)carry;
    dst->val[i] = (uint32_t)tmp;
    carry = (tmp >> 32) & 1;
  }
  if (carry) errx(5, "addition overflowed");
}

void big_isub(big *dst, big *src) {
  int borrow = 0;
  for (int i = 0; i < BIG_WORDS; i++) {
    int64_t tmp = (int64_t)dst->val[i] - (int64_t)src->val[i] - borrow;
    if (tmp < 0) {
      borrow = 1;
      tmp += 1L << 32;
    } else {
      borrow = 0;
    }
    dst->val[i] = tmp;
  }
  if (borrow) errx(5, "subraction underflowed");
}

bool big_lte(big *a, big *b) {
  for (int i = BIG_WORDS - 1; i >= 0; i--) {
    if (a->val[i] != b->val[i]) {
      return a->val[i] <= b->val[i];
    }
  }
  return true;  // equal
}

void big_irand(big *dst, big *below) {
  while (1) {
    if (getrandom(dst, sizeof *dst, 0) < 0) err(6, "unable to get randomness");
    for (int i = BIG_WORDS - 1; i >= 0; i--) {
      if (below->val[i] == 0) {
        dst->val[i] = 0;
      } else {
        dst->val[i] &= (1L << (32L - __builtin_clz(below->val[i]))) - 1;
        break;
      }
    }
    if (big_lte(dst, below)) return;
  }
}

int big_idiv(big *dst, int divisor) {
  int remainder = 0;
  for (int i = BIG_WORDS - 1; i >= 0; i--) {
    int64_t tmp = (int64_t)dst->val[i] + ((int64_t)(remainder) << 32);
    dst->val[i] = tmp / divisor;
    remainder = tmp % divisor;
  }
  return remainder;
}

void big_print(big a) {
  int chunks[BIG_WORDS * 4];
  int c = 0;
  big zero = {};
  while (!big_lte(&a, &zero)) chunks[c++] = big_idiv(&a, 1000);
  for (int i = c - 1; i >= 0; i--)
    printf("%0*d%s", i == c - 1 ? 1 : 3, chunks[i], i > 0 ? "," : "");
}

big prepare_path_counts(big paths[][27 * 27], int length) {
  for (int i = 0; i < 27 * 27; i++)
    paths[length - 1][i] = (big){{trigrams[i] & 1}};

  for (int level = length - 2; level > 0; level--) {
    for (int i = 27; i < 27 * 27; i++) {
      big count = {};
      for (int j = 1; j < 27; j++) {
        if (trigrams[i] & (1 << j)) {
          big_iadd(&count, &paths[level + 1][(i % 27) * 27 + j]);
        }
      }
      paths[level][i] = count;
    }
  }

  big total_paths = {};
  for (int i = 0; i < 27; i++) {
    big count = {};
    for (int j = 1; j < 27; j++) {
      if (trigrams[i] & (1 << j)) {
        big_iadd(&count, &paths[1][(i % 27) * 27 + j]);
      }
    }
    paths[0][i] = count;
    big_iadd(&total_paths, &count);
  }

  return total_paths;
}

void generate(char *out, int length, big paths[][27 * 27], big chosen) {
  int grams[length];
  for (int i = 0; i < 27 * 27; i++) {
    if (big_lte(&paths[0][i], &chosen)) {
      big_isub(&chosen, &paths[0][i]);
    } else {
      grams[0] = i;
      break;
    }
  }
  for (int level = 1; level < length; level++) {
    int base = grams[level - 1] % 27 * 27;
    for (int i = 0; i < 27; i++) {
      if (trigrams[grams[level - 1]] & (1 << i)) {
        int n = base + i;
        if (big_lte(&paths[level][n], &chosen)) {
          big_isub(&chosen, &paths[level][n]);
        } else {
          grams[level] = n;
          break;
        }
      }
    }
  }
  for (int i = 0; i < length; i++) {
    out[i] = (grams[i] % 27) + '`';
  }
  out[length] = 0;
}

void usage(char *name) {
  errx(1, "usage: %s [-halv] [length] [count]\n", name);
}

int main(int argc, char **argv) {
  int c;
  bool all = false;
  bool columns = true;
  bool verbose = false;
  long length = 8;
  long count = 0;

  while ((c = getopt(argc, argv, "halv")) != -1) {
    switch (c) {
      case 'h':
        usage(argv[0]);
        break;
      case 'a':
        all = true;
        break;
      case 'l':
        columns = false;
        break;
      case 'v':
        verbose = true;
        break;
      case '?':
        return 1;
    }
  }

  char *tmp;
  if (optind < argc) {
    length = strtol(argv[optind], &tmp, 10);
    if (errno || *tmp != 0) errx(2, "invalid length %s", argv[optind]);
    optind++;
  }

  if (length > BIG_WORDS * 9)
    errx(3, "length %ld too large, max is %d", length, BIG_WORDS * 9);
  if (length < 3) errx(3, "length %ld too small, min is 3", length);

  if (optind < argc) {
    count = strtol(argv[optind], &tmp, 10);
    if (errno || *tmp != 0) errx(2, "invalid count %s", argv[optind]);
    optind++;
  }

  if (argv[optind] != NULL) usage(argv[0]);

  big paths[length][27 * 27];

  big total = prepare_path_counts(paths, length);
  int bits = 0;
  for (int i = BIG_WORDS - 1; i >= 0; i--) {
    if (total.val[i]) {
      bits = 32 * i + (31 - __builtin_clz(total.val[i]));
      break;
    }
  }

  int words_per_line = 1;
  if (columns) {
    words_per_line = 1 + (80 - length) / (2 + length);
  }
  if (count == 0) count = words_per_line * 8;
  int words = 0;
  char word[length + 1];
  big chosen = {};
  if (all) {
    if (verbose) {
      printf("Generating all ");
      big_print(total);
      printf(" %ld-letter words with %d bits of entropy\n", length, bits);
    }
    big one = {{1}};
    while (1) {
      generate(word, length, paths, chosen);
      fputs(word, stdout);
      if (++words == words_per_line) {
        words = 0;
        putchar('\n');
      } else {
        fputs("  ", stdout);
      }
      big_iadd(&chosen, &one);
      if (big_lte(&total, &chosen)) break;
    }
  } else {
    if (verbose) {
      printf("Generating %ld %ld-letter words with %d bits of entropy (", count,
             length, bits);
      big_print(total);
      printf(" possible)\n");
    }
    for (int i = 0; i < count; i++) {
      big_irand(&chosen, &total);
      generate(word, length, paths, chosen);
      fputs(word, stdout);
      if (++words == words_per_line) {
        words = 0;
        putchar('\n');
      } else if (i + 1 < count) {
        fputs("  ", stdout);
      }
    }
  }
  if (words) putchar('\n');
}


<|start_filename|>abbrase.js<|end_filename|>
function WordGraph(url) {
	this.state = "init";
	this.n_words = 0;
	this.words = [];
	this.prefixes = {};
	this.prefix_list = [];
	this.followers_compressed = [];
	this.url = url;
	this.onprogress = null;
	this.onready = null;
}

WordGraph.prototype.load = function() {
	if (this.state != "init")
		return;
	this.state = "downloading";
	var xhr = new XMLHttpRequest();
	xhr.open('GET', this.url, true);
	xhr.totalsize = 20670394;
	var self = this;
	xhr.onreadystatechange = function(evt) {
		if (xhr.status >= 400) {
			if (self.onprogress)
				self.onprogress(-xhr.status);
		}
		if (xhr.readyState === 3) {
			var perc = (100 * xhr.response.length / xhr.totalsize)|0;
			if (xhr.perc != perc) {
				xhr.perc = perc;
				if (self.onprogress) {
					self.onprogress(perc);
				}
			}
		} else if (xhr.readyState === 4) {
			console.log("Done");
			self.parse(xhr.responseText);
		}
	}
	xhr.send();
}

WordGraph.prototype.parse = function(text) {
	var lines = text.split("\n");
	lines.reverse();

	this.n_words = parseInt(lines.pop());
	this.words.push('');
	for (var n = 1; n < this.n_words; n++) {
		var word = lines.pop();
		var prefix = word.substr(0, 3).toLowerCase();
		this.words.push(word);
		this.prefixes[prefix] = this.prefixes[prefix] || [];
		this.prefixes[prefix].push(n);
	}

	this.prefix_list = Object.keys(this.prefixes);
	this.prefix_list.sort();

	for (var n = 1; n <= this.n_words; n++) {
		this.followers_compressed.push(lines.pop());
	}

	this.state = "ready";

	if (this.onready !== null) {
		this.onready(this);
	}
}

WordGraph.prototype.get_followers = function(word_number) {
	var enc = this.followers_compressed[word_number];
	/*
	general encoding steps:
	input: [1, 2, 3, 5, 80]
	subtract previous value: [1, 1, 1, 2, 75]
	subtract 1: [0, 0, 0, 1, 74]
	contract runs of zeros: [0x3, 1, 74]
	printably encode numbers as base-32 varints,
	and runs of zeros as the 31 leftover characters:
	output: "bA*B"

	this function reverses the steps.

	Cf. decode in digest.py
	*/
	var enc_ind = 0;
	var dec = [];
	var last_num = 0;
	var zero_run = 0;
	while (enc_ind < enc.length || zero_run) {
		var delta = 0;
		var delta_ind = 0;
		if (zero_run) {
			zero_run--;
		} else {
			var val = enc.charCodeAt(enc_ind);
			if (val >= 0x60) {
				zero_run = val & 0x1f
				delta_ind += 1
			} else {
				do {
					val = enc.charCodeAt(enc_ind + delta_ind);
					delta |= (val & 0x1f) << (5 * delta_ind);
					delta_ind++;
				} while (!(val & 0x40));
			}
		}
		enc_ind += delta_ind;
		num = last_num + delta + 1;
		last_num = num;
		dec.push(num);
	}
	return dec;
};

function intersect(a, b) {
	var ret = [];
	var ai = 0, bi = 0;
	while (ai < a.length && bi < b.length) {
		var diff = a[ai] - b[bi];
		if (diff == 0) {
			ret.push(a[ai]);
			ai++, bi++;
		} else if (diff < 0) {
			ai++;
		} else if (diff > 0) {
			bi++;
		}
	}
	return ret;
}

function PassphraseGenerator(graph) {
	this.graph = graph;
}

PassphraseGenerator.prototype.gen_password = function(length) {
	if (this.graph.state !== "ready")
		throw new Error("wordgraph isn't loaded yet");

	if (this.graph.prefix_list.length != 1024)
		throw new RangeError("unexpected number of prefixes");

	/* pick series of prefixes that will make up the passwords */
	var prefix_numbers = new Uint16Array(length);
	crypto.getRandomValues(prefix_numbers);
	var prefixes_chosen = [];

	var word_sets = [];
	var out_password = "";

	/* find possible words for each of the chosen prefixes */
	for (var i = 0; i < length; i++) {
		prefix_numbers[i] = prefix_numbers[i] % 1024;
		prefixes_chosen[i] = this.graph.prefix_list[prefix_numbers[i]];
		out_password += prefixes_chosen[i];
		word_sets.push(this.graph.prefixes[prefixes_chosen[i]]);
	}

	/* working backwards, reduce possible words for each prefix to only
	   those words that have a link to a word in the next set of possible words
	*/

	var mismatch = 0; /* track how many links were impossible */
	var next_words = [];
	for (var i = length - 1; i >= 0; i--) {
		var words = word_sets[i];
		var new_words = [];
		if (next_words.length > 0) {
			for (var j = 0; j < words.length; j++) {
				var word = words[j];
				var followers = this.graph.get_followers(word);
				if (intersect(next_words, followers).length)
					new_words.push(word);
			}
		}
		if (new_words.length > 0) {
			word_sets[i] = new_words;
		} else {
			mismatch++;
		}

		next_words = word_sets[i];
	}

	/* working forwards, pick a word for each prefix */
	var out_words = [];
	var phrase_rank = 0;
	var last_word = 0;
	for (var i = 0; i < length; i++) {
		var followers = this.graph.get_followers(last_word);
		var forward = intersect(word_sets[i], followers);
		/* Picking the first word available biases the phrase towards more
		* common words, and produces generally satisfactory results.
		* N.B.: to save space, adjacency lists don't encode probabilities */
		last_word = (forward.length > 0 ? forward : word_sets[i])[0];
		phrase_rank += last_word;
		out_words.push(this.graph.words[last_word]);
	}

	return {"password": <PASSWORD>,
		"mnemonic": out_words.join(" "),
		"phrase_rank": phrase_rank,
		"mismatch": mismatch,
		"numbers": prefix_numbers};
};

function ljust(inp, length, pad) {
	if (pad === undefined)
		pad = ' ';
	while (inp.length < length) {
		inp += pad;
	}
	return inp;
}

PassphraseGenerator.prototype.make_table = function(length, count) {
	var passwords = [];

	for (var i = 0; i < count; i++) {
		passwords.push(generator.gen_password(length));
	}

	// Sort by the sum of the word positions -- meaning phrases with more common
	// words come first.
	//
	// This tends to rank desirable passwords higher, but could aid an attacker
	// leveraging selection biases (maximum entropy loss is log2(count) bits).

	passwords.sort(function (a, b) {
		return a.phrase_rank - b.phrase_rank;
	});

	output = 'Generating ' + count + ' passwords with ';
	output += (length * 10) + ' bits of entropy\n';

	output += ljust("Password", 3 * length) + '    ' + 'Mnemonic\n';
	output += ljust('', 3 * length, '-') + '    ' + ljust('', 4 * length, '-') + '\n';

	for (var i = 0; i < count; i++) {
		var gen = passwords[i];
		output += gen.password + '    ' + gen.mnemonic;
		// output += ' ' + gen.phrase_rank + ' ' + gen.mismatch;
		output += '\n';
	}

	return output;
};

function pretty_arraybuffer(ab) {
	var ret = [];
	for (var i = 0; i < ab.length; i++)
		ret.push(ab[i]);
	return '[' + ret.join(', ') + ']';
}
