LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
L2 = len(LETTERS)**2

print("// This code has been generated by mkbigrams.py.")
print("// Bigram values are stored in a sorted array.")
print("// The index is 26×first character offset + second character offset.")
print("// Invalid bigrams are represented by -9.522878745280337")
print(f"const float BIGRAMS[{L2}] = {{")
with open("bigrams") as f:
    bigramdict = dict(ln.strip().split(",") for ln in f)
index = 0
for j in LETTERS:
    for k in LETTERS:
        key = j + k
        value = bigramdict.get(key, "-9.522878745280337")
        if key == "ZZ":
            print(f"{value} // [{index}] = {key}")
        else:
            print(f"{value}, // [{index}] = {key}")
        index += 1
print("};")

extern const float BIGRAMS[676];

float bigram_score(const char txt[]) {
int32_t n = strnlen(txt, 1024);
float total = 0.0;
for (int32_t j = 0; j < (n - 1); j++) {
    total += BIGRAMS[26 * (txt[j] - 65) + (txt[j + 1] - 65)];
}
return total;
}

LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
L4 = len(LETTERS)**4

print("// This code has been generated by mkquadgrams.py")
print("// Quadgram values are stored in a sorted array.")
print("// The index is 26⁴×first character offset + 26³×second character offset +")
print("//  26²×third character offset + fourth character offset.")
print("// Invalid quadgrams are represented by -9.522878745280337")
print(f"const float QUADGRAMS[{L4}] = {{")
with open("quadgrams") as f:
    quadgramdict = dict(ln.strip().split(",") for ln in f)
for j in LETTERS:
    for k in LETTERS:
        for m in LETTERS:
            for p in LETTERS:
                key = j + k + m + p
                value = quadgramdict.get(key, "-9.522878745280337")
                if key == "ZZZZ":
                    print(f"{value} // {key}")
                else:
                    print(f"{value}, // {key}")
print("};")

extern const float QUADGRAMS[456976];

float quadgram_score(const char txt[]) {
  int32_t n = strnlen(txt, 1024);
  float total = 0.0;
  for (int32_t j = 0; j < (n - 3); j++) {
    int32_t idx = 17576 * (txt[j] - 65) + 676 * (txt[j + 1] - 65) +
                  26 * (txt[j + 2] - 65) + (txt[j + 3] - 65);
    total += QUADGRAMS[idx];
  }
return total;
}

with open("quadgrams.sorted") as f:
    lines = f.readlines()
items = list(ln.strip().split(",") for ln in lines
quadkeys = tuple(j[0] for j in items)
quadvalues = tuple(j[1] for j in items)

def find_key(quad):
    left = 0
    right = len(quadkeys)-1
    mid = (left+right)//2
    count = 1
    while True:
        print(f"{count} left={left}, right={right}")
        v = quadkeys[mid]
        if quad < v:
            if quad > quadkeys[mid-1]:
               return -1
            right = mid
        elif quad > v:
            if quad < quadkeys[mid+1]:
               return -1
            left = mid
        elif quad == v:
            return mid
        mid = (left+right)//2
        count += 1

In [31]: sum((ord(c)-65)*26**n for n, c in enumerate("AAAA"[::-1], start=0))
Out[31]: 0

In [32]: sum((ord(c)-65)*26**n for n, c in enumerate("TION"[::-1], start=0))
Out[32]: 339729

In [33]: sum((ord(c)-65)*26**n for n, c in enumerate("ATIO"[::-1], start=0))
Out[33]: 13066

In [34]: sum((ord(c)-65)*26**n for n, c in enumerate("ZZZZ"[::-1], start=0))
Out[34]: 456975

In [35]: sum((ord(c)-65)*26**n for n, c in enumerate("OUGH"[::-1], start=0))
Out[35]: 259747

In [36]: sum((ord(c)-65)*26**n for n, c in enumerate("QING"[::-1], start=0))
Out[36]: 286968

LETTERS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

with open("quadgrams") as f:
    items = [ln.strip().split(",") for ln in f]
# Very important: sort by quadgrams!
items.sort(key=lambda x: x[0])
keys = [j[0] for j in items]
values = [j[1] for j in items]
L = len(keys)

print("// This code has been generated by mkquadgrams2.py")
print("// It contains two arrays, both sorted by the quadgrams")
print("// Quadgram keys are stored in QUADKEYS.")
print("// Quadgram values are stored in QUADVALUES.")
print("// The index is 26⁴×first character offset + 26³×second character offset +")
print("//  26²×third character offset + fourth character offset.")
print("#include <stdint.h>")
print()

print(f"const int32_t QUADKEYS[{L}] = " + "{")
for key in keys[:-1]:
    keyval = sum((ord(c)-65)*26**n for n, c in enumerate(key[::-1], start=0))
    print(f"  {keyval:6d}, // {key}")
# Last key has no “,” after the keyval!
keyval = sum((ord(c)-65)*26**n for n, c in enumerate(keys[-1][::-1], start=0))
print(f"  {keyval:6d}  // {keys[-1]}")
print("};")
print()

print(f"const float QUADVALUES[{L}] = " + "{")
for value in values[:-1]:
    print(f"  {value},")
print(f"  {values[-1]}")
print("};")

// Binary lookup in a *sorted* array of int32_t.
// Returns the index of “value”, or -1 if “value” is not in the array.
int32_t array_lookup(int32_t value, const int32_t array[], int32_t arraylen) {
    int32_t left = 0, right = arraylen - 1;
    int32_t mid = (left + right) / 2, midval = 0;
    while (true) {
        midval = array[mid];
        if (value == midval) {
            return mid;
        }
        if (value < midval) {
            if (value > array[mid - 1]) {
                // Value is not present in the array!
                return -1;
            }
            right = mid;
        } else if (value > midval) {
            if (value < array[mid + 1]) {
                // Value is not present in the array!
                return -1;
            }
            left = mid;
        }
        mid = (left + right) / 2;
    }
    // Should not be reached.
    return -1;
}

extern const int32_t QUADKEYS[42171];
extern const float QUADVALUES[42171];

float quadgram_score2(const char txt[]) {
    int32_t n = strnlen(txt, 1024);
    float total = 0.0;
    for (int32_t j = 0; j < (n - 3); j++) {
        int32_t val = 17576 * (txt[j] - 65) + 676 * (txt[j + 1] - 65) +
                    26 * (txt[j + 2] - 65) + (txt[j + 3] - 65);
        // 26³ = 17576, 26² = 676
        int32_t idx = array_lookup(val, QUADKEYS, 42171);
        if (idx != -1) {
            total += QUADVALUES[idx];
        }
    }
    return total;
}