src/typo.c

   1 // Copyright © Tavian Barnes <tavianator@tavianator.com>
   2 // SPDX-License-Identifier: 0BSD
   3
   4 #include "typo.h"
   5 #include <limits.h>
   6 #include <stdint.h>
   7 #include <stdlib.h>
   8 #include <string.h>
   9
  10 // Assume QWERTY layout for now
  11 static const int8_t key_coords[UCHAR_MAX + 1][3] = {
  12         ['`']  = { 0,  0, 0},
  13         ['~']  = { 0,  0, 1},
  14         ['1']  = { 3,  0, 0},
  15         ['!']  = { 3,  0, 1},
  16         ['2']  = { 6,  0, 0},
  17         ['@']  = { 6,  0, 1},
  18         ['3']  = { 9,  0, 0},
  19         ['#']  = { 9,  0, 1},
  20         ['4']  = {12,  0, 0},
  21         ['$']  = {12,  0, 1},
  22         ['5']  = {15,  0, 0},
  23         ['%']  = {15,  0, 1},
  24         ['6']  = {18,  0, 0},
  25         ['^']  = {18,  0, 1},
  26         ['7']  = {21,  0, 0},
  27         ['&']  = {21,  0, 1},
  28         ['8']  = {24,  0, 0},
  29         ['*']  = {24,  0, 1},
  30         ['9']  = {27,  0, 0},
  31         ['(']  = {27,  0, 1},
  32         ['0']  = {30,  0, 0},
  33         [')']  = {30,  0, 1},
  34         ['-']  = {33,  0, 0},
  35         ['_']  = {33,  0, 1},
  36         ['=']  = {36,  0, 0},
  37         ['+']  = {36,  0, 1},
  38
  39         ['\t'] = { 1,  3, 0},
  40         ['q']  = { 4,  3, 0},
  41         ['Q']  = { 4,  3, 1},
  42         ['w']  = { 7,  3, 0},
  43         ['W']  = { 7,  3, 1},
  44         ['e']  = {10,  3, 0},
  45         ['E']  = {10,  3, 1},
  46         ['r']  = {13,  3, 0},
  47         ['R']  = {13,  3, 1},
  48         ['t']  = {16,  3, 0},
  49         ['T']  = {16,  3, 1},
  50         ['y']  = {19,  3, 0},
  51         ['Y']  = {19,  3, 1},
  52         ['u']  = {22,  3, 0},
  53         ['U']  = {22,  3, 1},
  54         ['i']  = {25,  3, 0},
  55         ['I']  = {25,  3, 1},
  56         ['o']  = {28,  3, 0},
  57         ['O']  = {28,  3, 1},
  58         ['p']  = {31,  3, 0},
  59         ['P']  = {31,  3, 1},
  60         ['[']  = {34,  3, 0},
  61         ['{']  = {34,  3, 1},
  62         [']']  = {37,  3, 0},
  63         ['}']  = {37,  3, 1},
  64         ['\\'] = {40,  3, 0},
  65         ['|']  = {40,  3, 1},
  66
  67         ['a']  = { 5,  6, 0},
  68         ['A']  = { 5,  6, 1},
  69         ['s']  = { 8,  6, 0},
  70         ['S']  = { 8,  6, 1},
  71         ['d']  = {11,  6, 0},
  72         ['D']  = {11,  6, 1},
  73         ['f']  = {14,  6, 0},
  74         ['F']  = {14,  6, 1},
  75         ['g']  = {17,  6, 0},
  76         ['G']  = {17,  6, 1},
  77         ['h']  = {20,  6, 0},
  78         ['H']  = {20,  6, 1},
  79         ['j']  = {23,  6, 0},
  80         ['J']  = {23,  6, 1},
  81         ['k']  = {26,  6, 0},
  82         ['K']  = {26,  6, 1},
  83         ['l']  = {29,  6, 0},
  84         ['L']  = {29,  6, 1},
  85         [';']  = {32,  6, 0},
  86         [':']  = {32,  6, 1},
  87         ['\''] = {35,  6, 0},
  88         ['"']  = {35,  6, 1},
  89         ['\n'] = {38,  6, 0},
  90
  91         ['z']  = { 6,  9, 0},
  92         ['Z']  = { 6,  9, 1},
  93         ['x']  = { 9,  9, 0},
  94         ['X']  = { 9,  9, 1},
  95         ['c']  = {12,  9, 0},
  96         ['C']  = {12,  9, 1},
  97         ['v']  = {15,  9, 0},
  98         ['V']  = {15,  9, 1},
  99         ['b']  = {18,  9, 0},
 100         ['B']  = {18,  9, 1},
 101         ['n']  = {21,  9, 0},
 102         ['N']  = {21,  9, 1},
 103         ['m']  = {24,  9, 0},
 104         ['M']  = {24,  9, 1},
 105         [',']  = {27,  9, 0},
 106         ['<']  = {27,  9, 1},
 107         ['.']  = {30,  9, 0},
 108         ['>']  = {30,  9, 1},
 109         ['/']  = {33,  9, 0},
 110         ['?']  = {33,  9, 1},
 111
 112         [' ']  = {18, 12, 0},
 113 };
 114
 115 static int char_distance(char a, char b) {
 116         const int8_t *ac = key_coords[(unsigned char)a], *bc = key_coords[(unsigned char)b];
 117         int ret = 0;
 118         for (int i = 0; i < 3; ++i) {
 119                 ret += abs(ac[i] - bc[i]);
 120         }
 121         return ret;
 122 }
 123
 124 int typo_distance(const char *actual, const char *expected) {
 125         // This is the Wagner-Fischer algorithm for Levenshtein distance, using
 126         // Manhattan distance on the keyboard for individual characters.
 127
 128         const int insert_cost = 12;
 129
 130         size_t rows = strlen(actual) + 1;
 131         size_t cols = strlen(expected) + 1;
 132
 133         int arr0[cols], arr1[cols];
 134         int *row0 = arr0, *row1 = arr1;
 135
 136         for (size_t j = 0; j < cols; ++j) {
 137                 row0[j] = insert_cost * j;
 138         }
 139
 140         for (size_t i = 1; i < rows; ++i) {
 141                 row1[0] = row0[0] + insert_cost;
 142
 143                 char a = actual[i - 1];
 144                 for (size_t j = 1; j < cols; ++j) {
 145                         char b = expected[j - 1];
 146                         int cost = row0[j - 1] + char_distance(a, b);
 147                         int del_cost = row0[j] + insert_cost;
 148                         if (del_cost < cost) {
 149                                 cost = del_cost;
 150                         }
 151                         int ins_cost = row1[j - 1] + insert_cost;
 152                         if (ins_cost < cost) {
 153                                 cost = ins_cost;
 154                         }
 155                         row1[j] = cost;
 156                 }
 157
 158                 int *tmp = row0;
 159                 row0 = row1;
 160                 row1 = tmp;
 161         }
 162
 163         return row0[cols - 1];
 164 }