usr.bin/checknr/checknr.c

   1 /*      $NetBSD: checknr.c,v 1.19 2006/04/25 19:25:19 christos Exp $    */
   2
   3 /*
   4  * Copyright (c) 1980, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the University nor the names of its contributors
  16  *    may be used to endorse or promote products derived from this software
  17  *    without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  */
  31
  32 #include <sys/cdefs.h>
  33 #ifndef lint
  34 __COPYRIGHT("@(#) Copyright (c) 1980, 1993\
  35  The Regents of the University of California.  All rights reserved.");
  36 #endif /* not lint */
  37
  38 #ifndef lint
  39 #if 0
  40 static char sccsid[] = "@(#)checknr.c   8.1 (Berkeley) 6/6/93";
  41 #else
  42 __RCSID("$NetBSD: checknr.c,v 1.19 2006/04/25 19:25:19 christos Exp $");
  43 #endif
  44 #endif /* not lint */
  45
  46 /*
  47  * checknr: check an nroff/troff input file for matching macro calls.
  48  * we also attempt to match size and font changes, but only the embedded
  49  * kind.  These must end in \s0 and \fP resp.  Maybe more sophistication
  50  * later but for now think of these restrictions as contributions to
  51  * structured typesetting.
  52  */
  53 #include <ctype.h>
  54 #include <err.h>
  55 #include <stdio.h>
  56 #include <stdlib.h>
  57 #include <string.h>
  58
  59 #define MAXSTK  100     /* Stack size */
  60 #define MAXBR   100     /* Max number of bracket pairs known */
  61 #define MAXCMDS 500     /* Max number of commands known */
  62
  63 /*
  64  * The stack on which we remember what we've seen so far.
  65  */
  66 struct stkstr {
  67         int opno;       /* number of opening bracket */
  68         int pl;         /* '+', '-', ' ' for \s, 1 for \f, 0 for .ft */
  69         int parm;       /* parm to size, font, etc */
  70         int lno;        /* line number the thing came in in */
  71 } stk[MAXSTK];
  72 int stktop;
  73
  74 /*
  75  * The kinds of opening and closing brackets.
  76  */
  77 struct brstr {
  78         char *opbr;
  79         char *clbr;
  80 } br[MAXBR] = {
  81         /* A few bare bones troff commands */
  82 #define SZ      0
  83         { "sz", "sz"},  /* also \s */
  84 #define FT      1
  85         { "ft", "ft"},  /* also \f */
  86         /* the -mm package */
  87         {"AL",  "LE"},
  88         {"AS",  "AE"},
  89         {"BL",  "LE"},
  90         {"BS",  "BE"},
  91         {"DF",  "DE"},
  92         {"DL",  "LE"},
  93         {"DS",  "DE"},
  94         {"FS",  "FE"},
  95         {"ML",  "LE"},
  96         {"NS",  "NE"},
  97         {"RL",  "LE"},
  98         {"VL",  "LE"},
  99         /* the -ms package */
 100         {"AB",  "AE"},
 101         {"BD",  "DE"},
 102         {"CD",  "DE"},
 103         {"DS",  "DE"},
 104         {"FS",  "FE"},
 105         {"ID",  "DE"},
 106         {"KF",  "KE"},
 107         {"KS",  "KE"},
 108         {"LD",  "DE"},
 109         {"LG",  "NL"},
 110         {"QS",  "QE"},
 111         {"RS",  "RE"},
 112         {"SM",  "NL"},
 113         {"XA",  "XE"},
 114         {"XS",  "XE"},
 115         /* The -me package */
 116         {"(b",  ")b"},
 117         {"(c",  ")c"},
 118         {"(d",  ")d"},
 119         {"(f",  ")f"},
 120         {"(l",  ")l"},
 121         {"(q",  ")q"},
 122         {"(x",  ")x"},
 123         {"(z",  ")z"},
 124         /* The -mdoc package */
 125         {"Ao",  "Ac"},
 126         {"Bd",  "Ed"},
 127         {"Bk",  "Ek"},
 128         {"Bo",  "Bc"},
 129         {"Do",  "Dc"},
 130         {"Fo",  "Fc"},
 131         {"Oo",  "Oc"},
 132         {"Po",  "Pc"},
 133         {"Qo",  "Qc"},
 134         {"Rs",  "Re"},
 135         {"So",  "Sc"},
 136         {"Xo",  "Xc"},
 137         /* Things needed by preprocessors */
 138         {"EQ",  "EN"},
 139         {"TS",  "TE"},
 140         /* Refer */
 141         {"[",   "]"},
 142         {0,     0}
 143 };
 144
 145 /*
 146  * All commands known to nroff, plus macro packages.
 147  * Used so we can complain about unrecognized commands.
 148  */
 149 char *knowncmds[MAXCMDS] = {
 150 "$c", "$f", "$h", "$p", "$s", "%A", "%B", "%C", "%D", "%I", "%J", "%N",
 151 "%O", "%P", "%Q", "%R", "%T", "%V", "(b", "(c", "(d", "(f", "(l", "(q",
 152 "(t", "(x", "(z", ")b", ")c", ")d", ")f", ")l", ")q", ")t", ")x",
 153 ")z", "++", "+c", "1C", "1c", "2C", "2c", "@(", "@)", "@C", "@D",
 154 "@F", "@I", "@M", "@c", "@e", "@f", "@h", "@m", "@n", "@o", "@p",
 155 "@r", "@t", "@z", "AB", "AE", "AF", "AI", "AL", "AM", "AS", "AT",
 156 "AU", "AX", "Ac", "Ad", "An", "Ao", "Ap", "Aq", "Ar", "At", "B" ,  "B1",
 157 "B2", "BD", "BE", "BG", "BL", "BS", "BT", "BX", "Bc", "Bd", "Bf",
 158 "Bk", "Bl", "Bo", "Bq", "Bsx", "Bx", "C1", "C2", "CD", "CM", "CT",
 159 "Cd", "Cm", "D" , "D1", "DA", "DE", "DF", "DL", "DS", "DT", "Db", "Dc",
 160 "Dd", "Dl", "Do", "Dq", "Dt", "Dv", "EC", "EF", "EG", "EH", "EM",
 161 "EN", "EQ", "EX", "Ec", "Ed", "Ef", "Ek", "El", "Em", "Eo", "Er",
 162 "Ev", "FA", "FD", "FE", "FG", "FJ", "FK", "FL", "FN", "FO", "FQ",
 163 "FS", "FV", "FX", "Fa", "Fc", "Fd", "Fl", "Fn", "Fo", "Ft", "Fx",
 164 "H" , "HC", "HD", "HM", "HO", "HU", "I" , "ID", "IE", "IH", "IM",
 165 "IP", "IX", "IZ", "Ic", "In", "It", "KD", "KE", "KF", "KQ", "KS", "LB",
 166 "LC", "LD", "LE", "LG", "LI", "LP", "Lb", "Li", "MC", "ME", "MF",
 167 "MH", "ML", "MR", "MT", "ND", "NE", "NH", "NL", "NP", "NS", "Nd",
 168 "Nm", "No", "Ns", "Nx", "OF", "OH", "OK", "OP", "Oc", "Oo", "Op",
 169 "Os", "Ot", "Ox", "P" , "P1", "PF", "PH", "PP", "PT", "PX", "PY",
 170 "Pa", "Pc", "Pf", "Po", "Pp", "Pq", "QE", "QP", "QS", "Qc", "Ql",
 171 "Qo", "Qq", "R" , "RA", "RC", "RE", "RL", "RP", "RQ", "RS", "RT",
 172 "Re", "Rs", "S" , "S0", "S2", "S3", "SA", "SG", "SH", "SK", "SM",
 173 "SP", "SY", "Sc", "Sh", "Sm", "So", "Sq", "Ss", "St", "Sx", "Sy",
 174 "T&", "TA", "TB", "TC", "TD", "TE", "TH", "TL", "TM", "TP", "TQ",
 175 "TR", "TS", "TX", "Tn", "UL", "US", "UX", "Ud", "Ux", "VL", "Va", "Vt",
 176 "WC", "WH", "XA", "XD", "XE", "XF", "XK", "XP", "XS", "Xc", "Xo",
 177 "Xr", "[" , "[-", "[0", "[1", "[2", "[3", "[4", "[5", "[<", "[>",
 178 "[]", "\\{", "\\}", "]" , "]-", "]<", "]>", "][", "ab", "ac", "ad", "af", "am",
 179 "ar", "as", "b" , "ba", "bc", "bd", "bi", "bl", "bp", "br", "bx",
 180 "c.", "c2", "cc", "ce", "cf", "ch", "cs", "ct", "cu", "da", "de",
 181 "di", "dl", "dn", "ds", "dt", "dw", "dy", "ec", "ef", "eh", "el",
 182 "em", "eo", "ep", "ev", "ex", "fc", "fi", "fl", "fo", "fp", "ft",
 183 "fz", "hc", "he", "hl", "hp", "ht", "hw", "hx", "hy", "i" , "ie",
 184 "if", "ig", "in", "ip", "it", "ix", "lc", "lg", "li", "ll", "ln",
 185 "lo", "lp", "ls", "lt", "m1", "m2", "m3", "m4", "mc", "mk", "mo",
 186 "n1", "n2", "na", "ne", "nf", "nh", "nl", "nm", "nn", "np", "nr",
 187 "ns", "nx", "of", "oh", "os", "pa", "pc", "pi", "pl", "pm", "pn",
 188 "po", "pp", "ps", "q" , "r" , "rb", "rd", "re", "rm", "rn", "ro",
 189 "rr", "rs", "rt", "sb", "sc", "sh", "sk", "so", "sp", "ss", "st",
 190 "sv", "sz", "ta", "tc", "th", "ti", "tl", "tm", "tp", "tr", "u",
 191 "uf", "uh", "ul", "vs", "wh", "xp", "yr", 0
 192 };
 193
 194 int     lineno;         /* current line number in input file */
 195 char    *cfilename;     /* name of current file */
 196 int     nfiles;         /* number of files to process */
 197 int     fflag;          /* -f: ignore \f */
 198 int     sflag;          /* -s: ignore \s */
 199 int     ncmds;          /* size of knowncmds */
 200 int     slot;           /* slot in knowncmds found by binsrch */
 201
 202 void    addcmd(char *);
 203 void    addmac(char *);
 204 int     binsrch(char *);
 205 void    checkknown(char *);
 206 void    chkcmd(char *, char *);
 207 void    complain(int);
 208 int     eq(const void *, const void *);
 209 int     main(int, char **);
 210 void    nomatch(char *);
 211 void    pe(int);
 212 void    process(FILE *);
 213 void    prop(int);
 214 void    usage(void);
 215
 216 int
 217 main(int argc, char **argv)
 218 {
 219         FILE *f;
 220         int i;
 221         char *cp;
 222         char b1[4];
 223
 224         /* Figure out how many known commands there are */
 225         while (knowncmds[ncmds])
 226                 ncmds++;
 227         while (argc > 1 && argv[1][0] == '-') {
 228                 switch(argv[1][1]) {
 229
 230                 /* -a: add pairs of macros */
 231                 case 'a':
 232                         i = strlen(argv[1]) - 2;
 233                         if (i % 6 != 0)
 234                                 usage();
 235                         /* look for empty macro slots */
 236                         for (i=0; br[i].opbr; i++)
 237                                 ;
 238                         for (cp=argv[1]+3; cp[-1]; cp += 6) {
 239                                 if (i >= MAXBR)
 240                                         errx(1, "too many pairs");
 241                                 if ((br[i].opbr = malloc(3)) == NULL)
 242                                         err(1, "malloc");
 243                                 strlcpy(br[i].opbr, cp, 3);
 244                                 if ((br[i].clbr = malloc(3)) == NULL)
 245                                         err(1, "malloc");
 246                                 strlcpy(br[i].clbr, cp+3, 3);
 247                                 addmac(br[i].opbr);     /* knows pairs are also known cmds */
 248                                 addmac(br[i].clbr);
 249                                 i++;
 250                         }
 251                         break;
 252
 253                 /* -c: add known commands */
 254                 case 'c':
 255                         i = strlen(argv[1]) - 2;
 256                         if (i % 3 != 0)
 257                                 usage();
 258                         for (cp=argv[1]+3; cp[-1]; cp += 3) {
 259                                 if (cp[2] && cp[2] != '.')
 260                                         usage();
 261                                 strncpy(b1, cp, 2);
 262                                 addmac(b1);
 263                         }
 264                         break;
 265
 266                 /* -f: ignore font changes */
 267                 case 'f':
 268                         fflag = 1;
 269                         break;
 270
 271                 /* -s: ignore size changes */
 272                 case 's':
 273                         sflag = 1;
 274                         break;
 275                 default:
 276                         usage();
 277                 }
 278                 argc--; argv++;
 279         }
 280
 281         nfiles = argc - 1;
 282
 283         if (nfiles > 0) {
 284                 for (i=1; i<argc; i++) {
 285                         cfilename = argv[i];
 286                         f = fopen(cfilename, "r");
 287                         if (f == NULL)
 288                                 perror(cfilename);
 289                         else {
 290                                 process(f);
 291                                 fclose(f);
 292                         }
 293                 }
 294         } else {
 295                 cfilename = "stdin";
 296                 process(stdin);
 297         }
 298         exit(0);
 299 }
 300
 301 void
 302 usage(void)
 303 {
 304         (void)fprintf(stderr,
 305             "usage: %s [-fs] [-a.xx.yy.xx.yy...] [-c.xx.xx.xx...] file\n",
 306             getprogname());
 307         exit(1);
 308 }
 309
 310 void
 311 process(FILE *f)
 312 {
 313         int i, n;
 314         char line[256]; /* the current line */
 315         char mac[5];    /* The current macro or nroff command */
 316         int pl;
 317
 318         stktop = -1;
 319         for (lineno = 1; fgets(line, sizeof line, f); lineno++) {
 320                 if (line[0] == '.') {
 321                         /*
 322                          * find and isolate the macro/command name.
 323                          */
 324                         strncpy(mac, line+1, 4);
 325                         if (isspace((unsigned char)mac[0])) {
 326                                 pe(lineno);
 327                                 printf("Empty command\n");
 328                         } else if (isspace((unsigned char)mac[1])) {
 329                                 mac[1] = 0;
 330                         } else if (isspace((unsigned char)mac[2])) {
 331                                 mac[2] = 0;
 332                         } else if (mac[0] != '\\' || mac[1] != '\"') {
 333                                 pe(lineno);
 334                                 printf("Command too long\n");
 335                         }
 336
 337                         /*
 338                          * Is it a known command?
 339                          */
 340                         checkknown(mac);
 341
 342                         /*
 343                          * Should we add it?
 344                          */
 345                         if (eq(mac, "de"))
 346                                 addcmd(line);
 347
 348                         chkcmd(line, mac);
 349                 }
 350
 351                 /*
 352                  * At this point we process the line looking
 353                  * for \s and \f.
 354                  */
 355                 for (i=0; line[i]; i++)
 356                         if (line[i]=='\\' && (i==0 || line[i-1]!='\\')) {
 357                                 if (!sflag && line[++i]=='s') {
 358                                         pl = line[++i];
 359                                         if (isdigit((unsigned char)pl)) {
 360                                                 n = pl - '0';
 361                                                 pl = ' ';
 362                                         } else
 363                                                 n = 0;
 364                                         while (isdigit((unsigned char)line[++i]))
 365                                                 n = 10 * n + line[i] - '0';
 366                                         i--;
 367                                         if (n == 0) {
 368                                                 if (stktop >= 0 &&
 369                                                     stk[stktop].opno == SZ) {
 370                                                         stktop--;
 371                                                 } else {
 372                                                         pe(lineno);
 373                                                         printf("unmatched \\s0\n");
 374                                                 }
 375                                         } else {
 376                                                 stk[++stktop].opno = SZ;
 377                                                 stk[stktop].pl = pl;
 378                                                 stk[stktop].parm = n;
 379                                                 stk[stktop].lno = lineno;
 380                                         }
 381                                 } else if (!fflag && line[i]=='f') {
 382                                         n = line[++i];
 383                                         if (n == 'P') {
 384                                                 if (stktop >= 0 &&
 385                                                     stk[stktop].opno == FT) {
 386                                                         stktop--;
 387                                                 } else {
 388                                                         pe(lineno);
 389                                                         printf("unmatched \\fP\n");
 390                                                 }
 391                                         } else {
 392                                                 stk[++stktop].opno = FT;
 393                                                 stk[stktop].pl = 1;
 394                                                 stk[stktop].parm = n;
 395                                                 stk[stktop].lno = lineno;
 396                                         }
 397                                 }
 398                         }
 399         }
 400         /*
 401          * We've hit the end and look at all this stuff that hasn't been
 402          * matched yet!  Complain, complain.
 403          */
 404         for (i=stktop; i>=0; i--) {
 405                 complain(i);
 406         }
 407 }
 408
 409 void
 410 complain(int i)
 411 {
 412         pe(stk[i].lno);
 413         printf("Unmatched ");
 414         prop(i);
 415         printf("\n");
 416 }
 417
 418 void
 419 prop(int i)
 420 {
 421         if (stk[i].pl == 0)
 422                 printf(".%s", br[stk[i].opno].opbr);
 423         else switch(stk[i].opno) {
 424         case SZ:
 425                 printf("\\s%c%d", stk[i].pl, stk[i].parm);
 426                 break;
 427         case FT:
 428                 printf("\\f%c", stk[i].parm);
 429                 break;
 430         default:
 431                 printf("Bug: stk[%d].opno = %d = .%s, .%s",
 432                         i, stk[i].opno, br[stk[i].opno].opbr,
 433                         br[stk[i].opno].clbr);
 434         }
 435 }
 436
 437 void
 438 chkcmd(char *line, char *mac)
 439 {
 440         int i;
 441
 442         /*
 443          * Check to see if it matches top of stack.
 444          */
 445         if (stktop >= 0 && eq(mac, br[stk[stktop].opno].clbr))
 446                 stktop--;       /* OK. Pop & forget */
 447         else {
 448                 /* No. Maybe it's an opener */
 449                 for (i=0; br[i].opbr; i++) {
 450                         if (eq(mac, br[i].opbr)) {
 451                                 /* Found. Push it. */
 452                                 stktop++;
 453                                 stk[stktop].opno = i;
 454                                 stk[stktop].pl = 0;
 455                                 stk[stktop].parm = 0;
 456                                 stk[stktop].lno = lineno;
 457                                 break;
 458                         }
 459                         /*
 460                          * Maybe it's an unmatched closer.
 461                          * NOTE: this depends on the fact
 462                          * that none of the closers can be
 463                          * openers too.
 464                          */
 465                         if (eq(mac, br[i].clbr)) {
 466                                 nomatch(mac);
 467                                 break;
 468                         }
 469                 }
 470         }
 471 }
 472
 473 void
 474 nomatch(char *mac)
 475 {
 476         int i, j;
 477
 478         /*
 479          * Look for a match further down on stack
 480          * If we find one, it suggests that the stuff in
 481          * between is supposed to match itself.
 482          */
 483         for (j=stktop; j>=0; j--)
 484                 if (eq(mac,br[stk[j].opno].clbr)) {
 485                         /* Found.  Make a good diagnostic. */
 486                         if (j == stktop-2) {
 487                                 /*
 488                                  * Check for special case \fx..\fR and don't
 489                                  * complain.
 490                                  */
 491                                 if (stk[j+1].opno==FT && stk[j+1].parm!='R'
 492                                  && stk[j+2].opno==FT && stk[j+2].parm=='R') {
 493                                         stktop = j -1;
 494                                         return;
 495                                 }
 496                                 /*
 497                                  * We have two unmatched frobs.  Chances are
 498                                  * they were intended to match, so we mention
 499                                  * them together.
 500                                  */
 501                                 pe(stk[j+1].lno);
 502                                 prop(j+1);
 503                                 printf(" does not match %d: ", stk[j+2].lno);
 504                                 prop(j+2);
 505                                 printf("\n");
 506                         } else for (i=j+1; i <= stktop; i++) {
 507                                 complain(i);
 508                         }
 509                         stktop = j-1;
 510                         return;
 511                 }
 512         /* Didn't find one.  Throw this away. */
 513         pe(lineno);
 514         printf("Unmatched .%s\n", mac);
 515 }
 516
 517 /* eq: are two strings equal? */
 518 int
 519 eq(const void *s1, const void *s2)
 520 {
 521         return (strcmp((char *)s1, (char *)s2) == 0);
 522 }
 523
 524 /* print the first part of an error message, given the line number */
 525 void
 526 pe(int pelineno)
 527 {
 528         if (nfiles > 1)
 529                 printf("%s: ", cfilename);
 530         printf("%d: ", pelineno);
 531 }
 532
 533 void
 534 checkknown(char *mac)
 535 {
 536
 537         if (eq(mac, "."))
 538                 return;
 539         if (binsrch(mac) >= 0)
 540                 return;
 541         if (mac[0] == '\\' && mac[1] == '"')    /* comments */
 542                 return;
 543
 544         pe(lineno);
 545         printf("Unknown command: .%s\n", mac);
 546 }
 547
 548 /*
 549  * We have a .de xx line in "line".  Add xx to the list of known commands.
 550  */
 551 void
 552 addcmd(char *line)
 553 {
 554         char *mac;
 555
 556         /* grab the macro being defined */
 557         mac = line+4;
 558         while (isspace((unsigned char)*mac))
 559                 mac++;
 560         if (*mac == 0) {
 561                 pe(lineno);
 562                 printf("illegal define: %s\n", line);
 563                 return;
 564         }
 565         mac[2] = 0;
 566         if (isspace((unsigned char)mac[1]) || mac[1] == '\\')
 567                 mac[1] = 0;
 568         if (ncmds >= MAXCMDS) {
 569                 printf("Only %d known commands allowed\n", MAXCMDS);
 570                 exit(1);
 571         }
 572         addmac(mac);
 573 }
 574
 575 /*
 576  * Add mac to the list.  We should really have some kind of tree
 577  * structure here but this is a quick-and-dirty job and I just don't
 578  * have time to mess with it.  (I wonder if this will come back to haunt
 579  * me someday?)  Anyway, I claim that .de is fairly rare in user
 580  * nroff programs, and the register loop below is pretty fast.
 581  */
 582 void
 583 addmac(char *mac)
 584 {
 585         char **src, **dest, **loc;
 586
 587         if (binsrch(mac) >= 0){ /* it's OK to redefine something */
 588 #ifdef DEBUG
 589                 printf("binsrch(%s) -> already in table\n", mac);
 590 #endif /* DEBUG */
 591                 return;
 592         }
 593         /* binsrch sets slot as a side effect */
 594 #ifdef DEBUG
 595         printf("binsrch(%s) -> %d\n", mac, slot);
 596 #endif
 597         loc = &knowncmds[slot];
 598         src = &knowncmds[ncmds-1];
 599         dest = src+1;
 600         while (dest > loc)
 601                 *dest-- = *src--;
 602         if ((*loc = strdup(mac)) == NULL)
 603                 err(1, "strdup");
 604         ncmds++;
 605 #ifdef DEBUG
 606         printf("after: %s %s %s %s %s, %d cmds\n", knowncmds[slot-2],
 607             knowncmds[slot-1], knowncmds[slot], knowncmds[slot+1],
 608             knowncmds[slot+2], ncmds);
 609 #endif
 610 }
 611
 612 /*
 613  * Do a binary search in knowncmds for mac.
 614  * If found, return the index.  If not, return -1.
 615  */
 616 int
 617 binsrch(char *mac)
 618 {
 619         char *p;        /* pointer to current cmd in list */
 620         int d;          /* difference if any */
 621         int mid;        /* mid point in binary search */
 622         int top, bot;   /* boundaries of bin search, inclusive */
 623
 624         top = ncmds-1;
 625         bot = 0;
 626         while (top >= bot) {
 627                 mid = (top+bot)/2;
 628                 p = knowncmds[mid];
 629                 d = p[0] - mac[0];
 630                 if (d == 0)
 631                         d = p[1] - mac[1];
 632                 if (d == 0)
 633                         return mid;
 634                 if (d < 0)
 635                         bot = mid + 1;
 636                 else
 637                         top = mid - 1;
 638         }
 639         slot = bot;     /* place it would have gone */
 640         return -1;
 641 }