housel@en.ecn.purdue.edu (Peter S. Housel) (03/04/89)
In article <61288@pyramid.pyramid.com>, csg@pyramid (Carl S. Gutekunst) writes: >Note that reverse-engineering the 'g' protocol is *damn* hard. Few have done >so without making grave sacrifices; UUPC and uuslave, for example, came out >supporting only a window size of 1, and gave up under almost any error con- >dition that the AT&T 'g' implementation would plow right through. Indeed, the >'g' protocol is by far the biggest stumbling block to producing a PD UUCP. > ><csg> It is? In that case... :-) Here is mine, written by reading Chesson's protocol description article until I understood it completely. Then again, and again, and again. Then I wrote the code, and rewrote it, and rewrote it. Then it was plugged into UUPC and run over and over and over again at debuglevel 13 until everything worked. Currently, it runs inside a heavily hacked version of UUPC running under Minix 1.3d. It streams the channel at 1200 baud window=3 between my AT compatible and a Dual VAX. My modem won't go any faster than that; anything beyond this is up to you. No guarantees of perfection, but it "looks right." A few notes: - sread2() is just a call to read() with fd=tty in raw mode - swrite() is just a call to write() with fd=tty in raw mode - onintr() just sets the timedout flag and re-installs itself. It is originally installed by the port i/o init routine. - visib() returns a "printable copy" of the given buffer - many of the constants are from my hacked dcp.h. Note especially the heirarchy of debuglevels. DLE is the ASCII ^P character, '\020'. It is probably best used as an example or a framework. Sorry about posting sources to a discussion group but it seems like the best place. -Peter S. Housel- housel@ecn.purdue.edu ...!pur-ee!housel echo 'x - newgpkt.c' sed 's/^X//' <<'**-newgpkt.c-EOF-**' >newgpkt.c X/* file: newgpkt.c X * author: Peter S. Housel X * X * The |cksum()| routine is taken from UUPC, Copyright 1985, 1986, 1987 by X * Richard H. Lamb, with (possible) changes Copyright 1987 by Stuart Lynne X * X * All other code is Copyright 1989 by Peter S. Housel. X * Redistribution for any purpose is permitted provided this message X * is included intact. No warranty of any sort is provided. X * X * newgpkt version 1.0 1/5/89 X */ X X/* This program was written based on the original UUPC 'g' driver, X * John Gilmore's version of uuslave, and Greg Chesson's protocol X * description article. The last was especially helpful. X * X * This code was written around a severely hacked version of UUPC. X * The call interface is almost identical to the original, but X * the internal implementation is quite different. Also, many X * functions are called that were not available in the original X * UUPC support functions. It should serve as an adequate framework. X * X * The framing strategy requires that a |read()| be interruptable X * by a |SIGALRM|. No "busy wait" or nonblocking read is required. X */ X X#include "dcp.h" X X#define MAXPKT 64 /* incredibly conservative... actually 4096 */ X#define SWINDOW 3 /* initial send window size */ X#define RWINDOW 3 /* window size we want to recieve */ X#define SPKTSIZE 64 /* initial send packet size */ X#define RPKTSIZE 64 /* window size we want to recieve */ X X#define MAXLOST 5 /* max lost packets (closes or such) */ X#define TIMEOUT 5 /* max seconds of before timeout */ X X#define LOSTPKT -1 /* packet lost, got timeout */ X#define BADPKT -2 /* bad checksum, or data read timed out */ X X#define ENV_DLE 0 /* framing char at start of envelope */ X#define ENV_K 1 /* packet length specifier */ X#define ENV_C0 2 /* low-order checksum */ X#define ENV_C1 3 /* high-order checksum */ X#define ENV_C 4 /* control byte */ X#define ENV_X 5 /* xor check byte */ X#define ENV_LEN 6 /* overall envelope length */ X X#define TT_CTRL 0 /* control packet */ X#define TT_DATA 2 /* data packet */ X#define TT_SDATA 3 /* short data packet */ X#define TT_ALTCHAN 1 /* 'alternate channel' - invalid */ X X#define X_CLOSE 1 /* close down protocol */ X#define X_RJ 2 /* reject recieved packet */ X#define X_SRJ 3 /* selectively reject packet - invalid */ X#define X_RR 4 /* reciever ready */ X#define X_INITC 5 /* third init packet */ X#define X_INITB 6 /* second init packet */ X#define X_INITA 7 /* first init packet */ X X#define OP_OPEN 1 /* request to open/init protocol */ X#define OP_CLOSE 2 /* request to close protocol */ X#define OP_WRITE 3 /* request to send packet */ X#define OP_READ 4 /* request to read packet */ X X#define MAGIC (unsigned) 0xAAAA /* checksum magic value */ X X/* from original dcp - determinie if a <= b < c, for mod 8 seq numbers */ X#define between(a,b,c) (((a)<=(b) && (b)<(c)) \ X || ((c)<(a) && (a)<=(b)) \ X || ((b)<(c) && (c)<(a))) X Xunsigned cksum(/* unsigned char *data, int len */); Xextern char *visib(/* unsigned char *data, int len */); X Xstruct { X short sdata; /* 'is this a short data packet' flag */ X unsigned length; /* length of this packet */ X unsigned char *bufloc; /* location of this data pkt's buffer */ X } X inpbufs[8], outbufs[8]; /* input/output queues */ X Xstatic int needack; /* do we need to acknowledge a rcv'd pkt? */ Xstatic int neednack; /* do we need to reject a recieved pkt? */ Xstatic int recv; /* seq. number of last correctly rcv'd pkt */ Xstatic int lastread; /* seq. number of last pkt ret. to caller */ Xstatic int send; /* first packet in output window */ Xstatic int next; /* next pkt to send send <= next < nstuff */ Xstatic int nstuff; /* next loc. to stuff a pkt in output queue */ X /* (last pkt in output window) + 1 */ Xstatic int initpk; /* current init sequence send packet */ Xstatic int skipping; /* skipping out-of-seq packets after RJ */ Xstatic int spktsize; /* send data size (requested by other end) */ Xstatic int swindow; /* send output window size (ditto) */ Xstatic int nlost; /* number of consecutive timeouts */ Xstatic int chanopen = 0; /* 'channel open' flag */ X Xstatic unsigned char buf[ENV_LEN + RPKTSIZE]; /* packet framing buffer */ Xstatic unsigned char *low, *high; /* framing buffer limits */ X Xstatic unsigned char *ibufset, *obufset; /* i/o packet buffer sets */ X X/* |gopenpk()| opens the 'g' packet protocol on the serial line. It X * initializes its state variables, allocates buffers, etc., then calls X * |gmachine()| to do the actual protocol negotiation/initialization. X */ Xgopenpk() X{ X int i; /* index */ X unsigned char *p, *q; /* pointers into buffer set */ X X high = low = buf; /* empty input buffer */ X needack = neednack = 0; /* don't need to accept or reject anything */ X initpk = X_INITA; /* send INITA during initialization */ X recv = lastread = 0; /* initial empty read queue, seq=0 */ X send = next = nstuff = 1; /* first in output queue, seq=1 */ X skipping = nlost = 0; /* nothing lost yet, not skipping */ X X if(gmachine(OP_OPEN) < 0) /* do the open */ X return -1; X X /* allocate send and recieve buffers */ X if(NULL == (p = ibufset = (unsigned char *)malloc(8 * RPKTSIZE))) X return -1; X if(NULL == (q = obufset = (unsigned char *)malloc(8 * spktsize))) X return -1; X X for(i = 0; i < 8; ++i) X { X inpbufs[i].bufloc = p; X p += RPKTSIZE; X outbufs[i].bufloc = q; X q += spktsize; X } X X pktsize = spktsize; /* for dcp compatibility */ X X return 0; X} X X/* |gclosepk()| closes down the packet protocol using the |OP_CLOSE| operation X * of |gmachine()|. X */ Xgclosepk() X{ X return gmachine(OP_CLOSE); X} X X/* |ggetpkt()| reads one packet and returns it. The data is stored in X * the buffer pointed to by |cdata|, and the length is stored in |*lenp|. X * It calls |gmachine()| to get the data, and copies it from the proper input X * buffer to the user's buffer area. "Short data" packets are handled here, X * as opposed to within |gmachine()|. X */ Xint ggetpkt(cdata, lenp) Xunsigned char *cdata; int *lenp; X{ X int nextread; X unsigned char *bufp; X X if(!chanopen) X return -1; X X nextread = (lastread + 1) & 7; X printmsg(M_HIGHPROTO, "waiting for input pkt seq=%d", nextread); X X if(gmachine(OP_READ) < 0) X return -1; X X *lenp = inpbufs[nextread].length; X bufp = inpbufs[nextread].bufloc; X if(inpbufs[nextread].sdata) X { X if(*bufp < 128) /* less than 128 bytes shorter than packet length */ X *lenp -= *bufp++; X else /* more than 128 bytes shorter */ X { X *lenp -= (*bufp++ & 127) * 256; X *lenp -= *bufp++; X } X } X memcpy(cdata, bufp, *lenp); X lastread = nextread; X return 0; X} X X/* |gsendpkt()| queues the packet pointed to by |cdata| of length |len| X * into the packet driver output buffer, and calls |gmachine()| to send X * it. (|gmachine()| will return when the packet has been transmitted but X * not necessarily acknowledged, with window size greater than 1.) If X * |flag| is nonzero, |cdata| is considered a null-terminated string X * which will be null-padded to the packet size and transmitted. X */ Xint gsendpkt(cdata, len, flag) Xunsigned char *cdata; int len, flag; X{ X unsigned char *destp; X unsigned diff; X X if(!chanopen) X return -1; X X destp = outbufs[nstuff].bufloc; X if(flag && len < spktsize) X { X printmsg(M_HIGHPROTO, "Padded message packet |%s|", cdata); X strncpy(destp, cdata, spktsize); X } X else X { X if((diff = spktsize - len) > 127) /* really short packet? */ X { X *destp++ = (diff >> 8) | 128; X *destp++ = diff & 255; X outbufs[nstuff].sdata = 1; X } X else if(diff > 0) /* short packet */ X { X *destp++ = diff; X outbufs[nstuff].sdata = 1; X } X else X outbufs[nstuff].sdata = 0; X memcpy(destp, cdata, len); /* copy into buffer */ X } X printmsg(M_HIGHPROTO, "queued data packet seq=%d len=%d", nstuff, len); X outbufs[nstuff].length = spktsize; X nstuff = (nstuff + 1) & 7; X X return gmachine(OP_WRITE); X} X X/* |gmachine()| is the heart of the 'g' packet driver. Its basic strategy X * is: X * - transmit a packet if necessary X * - return if possible, X * - else read a packet and act on it X * - repeat X * X * |OP_OPEN| requests that the channel be opened, and |OP_CLOSE| requests that X * it be closed. If |why| is |OP_WRITE|, |gmachine()| will return when the X * last packet in the output queue has been transmitted (but not necessarily X * acknowledged). |OP_READ| requests will return as soon as a new packet X * arrives. X */ Xint gmachine(why) Xint why; X{ X int xxx, yyy, len; X unsigned char *bufp; X int shortdat; X int i; X X while(1) X { X if(OP_CLOSE == why) X { X gspack(TT_CTRL, X_CLOSE, 0, (unsigned char *)NULL, 0); X chanopen = 0; X printmsg(M_MEDPROTO, "Sending CLOSE request..."); X } X else if(neednack) X { X gspack(TT_CTRL, X_RJ, recv, (unsigned char *)NULL, 0); X neednack = 0; X printmsg(M_MEDPROTO, "Sending RJ... recv=%d", recv); X } X else if(send != nstuff /* nonzero output queue? */ X && between(send, next, nstuff) /* 'next' in queue? */ X && between(send, next, (send + SWINDOW) & 7)) /* in out win. */ X { X printmsg(M_MEDPROTO, "Sending data packet %d", next); X gspack(outbufs[next].sdata ? TT_SDATA : TT_DATA, X next, recv, outbufs[next].bufloc, outbufs[next].length); X needack = 0; X next = (next + 1) & 7; X if(OP_WRITE == why && next == nstuff) /* go back for more */ X return 0; X } X else if(needack) X { X gspack(TT_CTRL, X_RR, recv, (unsigned char *)NULL, 0); X needack = 0; X printmsg(M_MEDPROTO, "Sending RR... recv=%d", recv); X } X else if(OP_OPEN == why) X { X if(X_INITB == initpk) X i = ilog2(RPKTSIZE) - 5; /* INITB contains packet size, */ X else X i = RWINDOW; /* INITA, INITC contain window size */ X gspack(TT_CTRL, initpk, i, (unsigned char *)NULL, 0); X } X X if(OP_READ == why && recv != lastread) X return 0; X X shortdat = 0; X bufp = buf + ENV_LEN; X switch(grpack(&xxx, &yyy, &len)) X { X case LOSTPKT: X printmsg(M_MEDPROTO, "Lost packet..."); X if(nlost > MAXLOST) X return -1; X next = send; /* retransmit last un-ack'ed pkt, */ X if(OP_READ == why) /* request retransmit */ X neednack = 1; X skipping = 0; X break; X case BADPKT: X printmsg(M_MEDPROTO, "Bad packet..."); X neednack = 1; /* reject! */ X skipping = 1; /* ignore the rest of the 'window' */ X break; X case TT_SDATA: X shortdat = 1; X /* fall through */ X case TT_DATA: X send = (yyy + 1) & 7; /* recieve acknowledgement */ X if(xxx != ((recv + 1) & 7)) X { X printmsg(M_MEDPROTO, X "Recieved data out of sequence (%d != %d)", X xxx, (recv + 1) & 7); X if(!skipping) X { X neednack = 1; /* we must have missed one */ X skipping = 1; X } X else X printmsg(M_MEDPROTO, "(Ignoring)"); X } X else X { X recv = xxx; /* this is most recent correct pkt */ X needack = 1; /* we will ack it */ X skipping = 0; X inpbufs[xxx].length = len; X inpbufs[xxx].sdata = shortdat; X memcpy(inpbufs[xxx].bufloc, bufp, len); X } X break; X case TT_CTRL: X skipping = 0; X switch(xxx) X { X case X_CLOSE: X printmsg(M_MEDPROTO, "* CLOSE *"); X gsendpk(TT_CTRL, X_CLOSE, 0, NULL, 0); X chanopen = 0; X if(OP_CLOSE == why) X return 0; /* expected? */ X else X return -1; /* nope */ X case X_RJ: X printmsg(M_MEDPROTO, "got RJ yyy=%d", yyy); X next = send = (yyy + 1) & 7; X break; X case X_RR: X printmsg(M_MEDPROTO, "got RR yyy=%d", yyy); X send = (yyy + 1) & 7; X break; X case X_INITC: X printmsg(M_MEDPROTO, "* INITC *"); X swindow = yyy; X if(X_INITC == initpk) X { X chanopen = 1; X return 0; X } X break; X case X_INITB: X printmsg(M_MEDPROTO, "* INITB *"); X spktsize = 32 << yyy; X if(X_INITB == initpk) X initpk = X_INITC; X break; X case X_INITA: X printmsg(M_MEDPROTO, "* INITA *"); X swindow = yyy; X initpk = X_INITB; X break; X default: X printmsg(M_MEDPROTO, "bad control packet: xxx=%d", xxx); X } X break; X default: X printmsg(M_MEDPROTO, "bad packet type"); X break; X } X } X} X X/* X * |grpack()| is responsible for reading one 'g'-protocol packet from the X * input communications channel. This includes framing, detecting timeouts, X * and checksum validation. X * The basic strategy is to keep a count of how many bytes have currently X * been read and how many are needed. When enough bytes for a packet header X * ("envelope") have been read, it is validated. If it is valid, and it X * has a nonzero data segment, the data portion is read. When it has X * everything, it does a checksum test and returns, with the control X * information stored in |*xxxp|, |*yyyp|, and the data segment length stored X * in |*lenp|. X */ Xint grpack(xxxp, yyyp, lenp) Xint *xxxp, *yyyp; int *lenp; X{ X int need; /* need how many bytes? */ X int env; /* 'have pkt envelope' flag */ X int gotdle; /* do we have envelope hdr? */ X int tt; /* packet type */ X unsigned sum; /* checksum */ X int remain; /* bytes which we stil need */ X int i; X X env = gotdle = 0; X need = ENV_LEN; /* initially, need a header */ X X alarm(TIMEOUT); /* time out if we don't have a packet */ X timedout = 0; X X while(1) X { X if(low == high) /* prevent framebuffer overruns */ X low = high = buf; X printmsg(M_LOWPROTO, "=> l=%d h=%d g=%d", low - buf, high - buf, X gotdle); X X while((remain = need - (high - low)) > 0) X { X if(timedout || (i = sread2(high, remain)) < 0) X { X alarm(0); X ++nlost; X low = high = buf; /* empty out partial packet, if any */ X return env ? BADPKT : LOSTPKT; X } X high += i; /* got some data - move upper limit up */ X } X if(!gotdle) X { X while(low < high) /* look for header 'DLE' prefix */ X { X if(DLE == *low) X { X gotdle = 1; X break; X } X else X ++low; X } X continue; X } X else if(!env) /* found DLE, but haven't found header yet */ X { X if(low > buf) /* move envelope to buf beginning */ X { X register unsigned char *dst = buf; X while(low < high) X *dst++ = *low++; X low = buf; X high = dst; X } X if(buf[ENV_X] != (buf[ENV_K]^buf[ENV_C0]^buf[ENV_C1]^buf[ENV_C]) X || buf[ENV_K] < 1 || buf[ENV_K] > 9) /* valid? */ X { X ++low; X gotdle = 0; X printmsg(M_LOWPROTO, "grpack: rejecting an envelope"); X continue; X } X env = 1; /* we have an envelope */ X tt = (buf[ENV_C] >> 6) & 3; /* store away control info */ X *xxxp = (buf[ENV_C] >> 3) & 7; X *yyyp = (buf[ENV_C] ) & 7; X if(buf[ENV_K] == 9) /* does it have data? */ X *lenp = 0; X else X *lenp = 16 << buf[ENV_K]; /* size = 32 * 2^(k-1) */ X need += *lenp; /* now need that many more */ X printmsg(M_LOWPROTO, "grpack: tt=%d, xxx=%d, yyy=%d, need=%d", X tt, *xxxp, *yyyp, need); X continue; X } X else X { /* have everything we need */ X if(*lenp) X sum = MAGIC - (cksum(buf + ENV_LEN, *lenp) ^ buf[ENV_C]); X else X sum = MAGIC - buf[ENV_C]; X if(((sum >> 8) & 0xFF) != buf[ENV_C1] X || (sum & 0xFF) != buf[ENV_C0]) X { X alarm(0); X nlost = 0; X printmsg(M_LOWPROTO, "grpack: bad checksum"); X low += ENV_LEN; /* we will search bad data seg for a header */ X return BADPKT; X } X else X { X alarm(0); /* got it all... return */ X nlost = 0; X low += need; X if(*lenp) X printmsg(M_DATA, "|%s|", visib(buf + ENV_LEN, *lenp)); X return tt; X } X } X } X} X X/* X * gspack simply sends out a packet, by assembling an envelope and writing X * it, and the data segment, to the communications channel. X */ Xgspack(tt, xxx, yyy, data, size) Xint tt, xxx, yyy; unsigned char *data; int size; X{ X unsigned char envelope[ENV_LEN]; /* packet envelope */ X unsigned sum; /* checksum */ X unsigned char ctrl; /* header control byte */ X int k; /* size = 32 * 2^(k-1) */ X X ctrl = ((tt & 3) << 6) | ((xxx & 7) << 3) | (yyy & 7); X X if(0 == size) X { X k = 9; /* no data seg */ X sum = MAGIC - ctrl; X } X else X { X int tmp = size; X for(k = -5; tmp != 0; ++k) /* find k */ X tmp >>= 1; X sum = MAGIC - (cksum(data, size) ^ ctrl); X } X envelope[ENV_DLE] = DLE; X envelope[ENV_K] = k; X envelope[ENV_C1] = (sum >> 8) & 0xFF; X envelope[ENV_C0] = sum & 0xFF; X envelope[ENV_C] = ctrl; X envelope[ENV_X] = k ^ envelope[ENV_C0] ^ envelope[ENV_C1] ^ ctrl; X swrite(envelope, ENV_LEN); /* send envelope */ X if(0 != size) X swrite(data, size); /* send data segment */ X printmsg(M_LOWPROTO, "gspack: tt=%d xxx=%d yyy=%d k=%d sum=%d", X tt, xxx, yyy, k, sum); X if(0 != size) X printmsg(M_DATA, "|%s|", visib(data, size)); X} X X/* X * chksum(data, len) came directly from dcp. It checksums the given data X * area using the g protocol algorithm. X */ Xunsigned cksum(data, len) Xint len; unsigned char *data; X{ X unsigned int i, j, tmp, chk1, chk2; X X chk1 = 0xffff; X chk2 = 0; X j = len; X for (i = 0; i < len; i++) X { X if(chk1 & 0x8000) X { X chk1 <<= 1; X chk1++; X } X else X { X chk1 <<= 1; X } X tmp = chk1; X chk1 += (data[i] & 0xff); X chk2 += chk1 ^ j; X if((chk1 & 0xffff) <= (tmp & 0xffff)) X chk1 ^= chk2; X j--; X } X return (chk1 & 0xffff); X} X X/* |ilog2(value)| returns (int)floor(log2(value)). X */ Xint ilog2(value) Xunsigned value; X{ X int i; X X if(value == 0) X return -1; X for(i = 0; value > 1; ++i) X value >>= 1; X X return i; X} **-newgpkt.c-EOF-**