morse.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4 #include <ctype.h>
   5
   6 #define MAXLEN 256
   7
   8 static unsigned char decode[] = "**etianmsurwdkgohvf*l*pjbxcyzq*";
   9 static unsigned char encode[256];
  10
  11 static void init(void)
  12 {
  13   for (unsigned i=2; i<sizeof(decode); i++)
  14     {
  15       int x = i;
  16       int y = 1;
  17       while (x > 1)
  18         {
  19           y = 2*y + x%2;
  20           x /= 2;
  21         }
  22       encode[decode[i]] = y;
  23       encode[toupper(decode[i])] = y;
  24     }
  25 }
  26
  27 static void strencode(unsigned char *dest, unsigned char *src, int spaces)
  28 {
  29   while (*src)
  30     {
  31       int c = encode[*src++];
  32       if (c <= 0)
  33         *dest++ = '?';
  34       else while (c > 1)
  35         {
  36           *dest++ = ".-"[c%2];
  37           c /= 2;
  38         }
  39       if (spaces && *src)
  40         *dest++ = '/';
  41     }
  42   *dest = 0;
  43 }
  44
  45 static void strdecode(unsigned char *dest, unsigned char *src)
  46 {
  47   while (*src)
  48     {
  49       if (*src != '.' && *src != '-')
  50         {
  51           src++;
  52           continue;
  53         }
  54       int c = 1;
  55       while (*src == '.' || *src == '-')
  56         c = 2*c + (*src++ == '-');
  57       *dest++ = decode[c];
  58     }
  59   *dest = 0;
  60 }
  61
  62 struct w {
  63   struct w *next;
  64   char c[1];
  65 };
  66
  67 struct t {
  68   struct t *son[2];
  69   struct w *words;
  70 };
  71
  72 static struct t root;
  73
  74 static void die(char *msg)
  75 {
  76   fprintf(stderr, "%s\n", msg);
  77   exit(1);
  78 }
  79
  80 static void *xmalloc(unsigned int s)
  81 {
  82   void *d = malloc(s);
  83   if (!d)
  84     die("Out of memory. All memory.");
  85   return d;
  86 }
  87
  88 static void load(char *name)
  89 {
  90   FILE *fi = fopen(name, "r");
  91   if (!fi)
  92     die("Cannot open dictionary");
  93   char buf[256], m[256];
  94   int cnt = 0;
  95   int treesize = 1;
  96   while (fgets(buf, sizeof(buf), fi))
  97     {
  98       char *c = strchr(buf, '\n');
  99       if (c)
 100         *c = 0;
 101       strencode(m, buf, 0);
 102       struct t *t = &root;
 103       for (c=m; *c; c++)
 104         {
 105           int i = (*c == '-');
 106           if (!t->son[i])
 107             {
 108               t->son[i] = xmalloc(sizeof(struct t));
 109               memset(t->son[i], 0, sizeof(struct t));
 110               treesize++;
 111             }
 112           t = t->son[i];
 113         }
 114       struct w *w = xmalloc(sizeof(*w) + strlen(buf));
 115       w->next = t->words;
 116       t->words = w;
 117       strcpy(w->c, buf);
 118       cnt++;
 119     }
 120   fclose(fi);
 121   printf("Loaded %d words, built %d nodes\n", cnt, treesize);
 122 }
 123
 124 static char M[MAXLEN+1][MAXLEN+1];      /* M[i][j]==1 if it's possible to cover in[i...N-1] with exactly j words */
 125
 126 static void map(char *in, int N)
 127 {
 128   M[N][0] = 1;
 129   for (int i=N-1; i>=0; i--)
 130     {
 131       struct t *t = &root;
 132       int j = i;
 133       while (t && j < N)
 134         {
 135           t = t->son[in[j++] == '-'];
 136           if (t && t->words)
 137             for (int k=0; k<N; k++)
 138               if (M[j][k])
 139                 M[i][k+1] = 1;
 140         }
 141     }
 142 }
 143
 144 static void print(char *buf, char *p, char *in, int i, int N, int j)    /* cover in[i...N-1] with exactly j words */
 145 {
 146   if (i >= N)
 147     {
 148       *p = 0;
 149       puts(buf);
 150       return;
 151     }
 152
 153   struct t *t = &root;
 154   *p++ = ' ';
 155   while (t && i < N)
 156     {
 157       t = t->son[in[i++] == '-'];
 158       if (t && t->words && M[i][j-1])
 159         for (struct w *w = t->words; w; w=w->next)
 160           {
 161             int l = strlen(w->c);
 162             memcpy(p, w->c, l);
 163             print(buf, p+l, in, i, N, j-1);
 164           }
 165     }
 166 }
 167
 168 int main(int argc, char **argv)
 169 {
 170   if (argc != 3)
 171     die("Usage: morse <dict> <string>");
 172   init();
 173   load(argv[1]);
 174
 175   char *in, mbuf[MAXLEN+1];
 176   if (argv[2][0] == '.' || argv[2][0] == '-')
 177     in = argv[2];
 178   else
 179     {
 180       strencode(mbuf, argv[2], 0);
 181       puts(mbuf);
 182       if (strchr(mbuf, '?'))
 183         die("Unable to encode");
 184       in = mbuf;
 185     }
 186
 187   int N = strlen(in);
 188   if (N > MAXLEN)
 189     die("Oops, too long for my memory!");
 190   map(in, N);
 191
 192   char buf[MAXLEN+1];
 193   for (int j=1; j<=N; j++)
 194     if (M[0][j])
 195       print(buf+1, buf, in, 0, N, j);
 196
 197   return 0;
 198 }