1 /* $Id: rawhdlc.c,v 1.3 1998/06/17 19:51:21 he Exp $
3 * rawhdlc.c support routines for cards that don't support HDLC
5 * Author Karsten Keil (keil@temic-ech.spacenet.de)
6 * Brent Baccala <baccala@FreeSoft.org>
9 * Some passive ISDN cards, such as the Traverse NETJet and the AMD 7930,
10 * don't perform HDLC encapsulation over the B channel. Drivers for
11 * such cards use support routines in this file to perform B channel HDLC.
13 * Bit-synchronous HDLC encapsulation is a means of encapsulating packets
14 * over a continuously transmitting serial communications link.
17 * 11111111101111110...........0111111011111111111
18 * iiiiiiiiiffffffffdddddddddddffffffffiiiiiiiiiii
20 * i = idle f = flag d = data
22 * When idle, the channel sends a continuous string of ones (mark
23 * idle; illustrated), or a continuous string of flag characters (flag
24 * idle). The beginning of a data frame is marked by a flag character
25 * (01111110), then comes the actual data, followed by another flag
26 * character, after which another frame may be sent immediately (a
27 * single flag may serve as both the end of one frame and the start of
28 * the next), or the link may return to idle. Obviously, the flag
29 * character can not appear anywhere in the data (or a false
30 * end-of-frame would occur), so the transmitter performs
31 * "bit-stuffing" - inserting a zero bit after every five one bits,
32 * irregardless of the original bit after the five ones. Byte
33 * ordering is irrelevent at this point - the data is treated as a
34 * string of bits, not bytes. Since no more than 5 ones may now occur
35 * in a row, the flag sequence, with its 6 ones, is unique.
37 * Upon reception, a zero bit that occur after 5 one bits is simply
38 * discarded. A series of 6 one bits is end-of-frame, and a series of
39 * 7 one bits is an abort. Once bit-stuffing has been corrected for,
40 * an integer number of bytes should now be present. The last two
41 * of these bytes form the Frame Check Sequence, a CRC that is verified
42 * and then discarded. Note that bit-stuffing is performed on the FCS
43 * just as if it were regular data.
47 * int make_raw_hdlc_data(u_char *src, u_int slen,
48 * u_char *dst, u_int dsize)
50 * Used for transmission. Copies slen bytes from src to dst, performing
51 * HDLC encapsulation (flag bytes, bit-stuffing, CRC) in the process.
52 * dsize is size of destination buffer, and should be at least
53 * ((6*slen)/5)+5 bytes to ensure adequate space will be available.
54 * Function returns length (in bytes) of valid destination buffer, or
55 * 0 upon destination overflow.
57 * void init_hdlc_state(struct hdlc_state *stateptr, int mode)
59 * Initializes hdlc_state structure before first call to read_raw_hdlc_data
63 * Insane mode; NETJet use a shared unsigned int memory block (
64 * with busmaster DMA), the bit pattern of every word is
65 * <8 B1> <8 B2> <8 Mon> <2 D> <4 C/I> <MX> <MR>
66 * according to Siemens IOM-2 interface, so we have to handle
67 * the src buffer as unsigned int and have to shift/mask the
69 * mode 1 -> B1 mode 2 -> B2 data is used
71 * int read_raw_hdlc_data(struct hdlc_state *saved_state,
72 * u_char *src, u_int slen,
73 * u_char *dst, u_int dsize)
75 * Used for reception. Scans source buffer bit-by-bit looking for
76 * valid HDLC frames, which are copied to destination buffer. HDLC
77 * state information is stored in a structure, which allows this
78 * function to process frames spread across several blocks of raw
79 * HDLC data. Part of the state information is bit offsets into
80 * the source and destination buffers.
82 * A return value >0 indicates the length of a valid frame, now
83 * stored in the destination buffer. In this case, the source
84 * buffer might not be completely processed, so this function should
85 * be called again with the same source buffer, possibly with a
86 * different destination buffer.
88 * A return value of zero indicates that the source buffer was
89 * completely processed without finding a valid end-of-packet;
90 * however, we might be in the middle of packet reception, so
91 * the function should be called again with the next block of
92 * raw HDLC data and the same destination buffer. It is NOT
93 * permitted to change the destination buffer in this case,
94 * since data may already have begun to be stored there.
96 * A return value of -1 indicates some kind of error - destination
97 * buffer overflow, CRC check failed, frame not a multiple of 8
98 * bits. Destination buffer probably contains invalid data, which
99 * should be discarded. Call function again with same source buffer
100 * and a new (or same) destination buffer.
102 * Suggested calling sequence:
104 * init_hdlc_state(...);
105 * for (EACH_RAW_DATA_BLOCK) {
106 * while (len = read_raw_hdlc_data(...)) {
107 * if (len == -1) DISCARD_FRAME;
108 * else PROCESS_FRAME;
113 * Test the code in this file as follows:
114 * gcc -DDEBUGME -o rawhdlctest rawhdlc.c
115 * ./rawhdlctest < rawdata
117 * The file "rawdata" can be easily generated from a HISAX B-channel
118 * hex dump (CF CF CF 02 ...) using the following perl script:
121 * @hexlist = split ' ';
122 * while ($hexstr = shift(@hexlist)) {
123 * printf "%c", hex($hexstr);
133 #include <linux/types.h>
134 #include <linux/ppp_defs.h>
137 /* There's actually an identical copy of this table in the PPP code
138 * (ppp_crc16_table), but I don't want this code dependent on PPP
144 0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
145 0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
146 0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
147 0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
148 0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
149 0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
150 0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
151 0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
152 0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
153 0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
154 0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
155 0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
156 0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
157 0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
158 0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
159 0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
160 0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
161 0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
162 0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
163 0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
164 0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
165 0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
166 0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
167 0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
168 0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
169 0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
170 0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
171 0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
172 0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
173 0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
174 0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
175 0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
178 #define HDLC_ZERO_SEARCH 0
179 #define HDLC_FLAG_SEARCH 1
180 #define HDLC_FLAG_FOUND 2
181 #define HDLC_FRAME_FOUND 3
186 #define HDLC_FLAG_VALUE 0x7e
189 #define MAKE_RAW_BYTE for (j=0; j<8; j++) { \
200 if (d_cnt == dsize) return 0;\
201 dst[d_cnt++] = out_val;\
211 if (d_cnt == dsize) return 0;\
212 dst[d_cnt++] = out_val;\
218 /* Optimization suggestion: If needed, this function could be
219 * dramatically sped up using a state machine. Each state would
220 * correspond to having seen N one bits, and being offset M bits into
221 * the current output byte. N ranges from 0 to 4, M from 0 to 7, so
222 * we need 5*8 = 35 states. Each state would have a table with 256
223 * entries, one for each input character. Each entry would contain
224 * three output characters, an output state, an a byte increment
225 * that's either 1 or 2. All this could fit in four bytes; so we need
226 * 4 bytes * 256 characters = 1 KB for each state (35 KB total). Zero
227 * the output buffer before you start. For each character in your
228 * input, you look it up in the current state's table and get three
229 * bytes to be or'ed into the output at the current byte offset, and
230 * an byte increment to move your pointer forward. A simple Perl
231 * script could generate the tables. Given HDLC semantics, probably
232 * would be better to set output to all 1s, then use ands instead of ors.
233 * A smaller state machine could operate on nibbles instead of bytes.
234 * A state machine for 32-bit architectures could use word offsets
235 * instead of byte offsets, requiring 5*32 = 160 states; probably
236 * best to work on nibbles in such a case.
240 int make_raw_hdlc_data(u_char
*src
, u_int slen
, u_char
*dst
, u_int dsize
)
242 register u_int i
,d_cnt
=0;
245 register u_char s_one
= 0;
246 register u_char out_val
= 0;
247 register u_char bitcnt
= 0;
251 dst
[d_cnt
++] = HDLC_FLAG_VALUE
;
253 for (i
=0; i
<slen
; i
++) {
255 fcs
= PPP_FCS (fcs
, val
);
261 val
= (fcs
>>8) & 0xff;
263 val
= HDLC_FLAG_VALUE
;
264 for (j
=0; j
<8; j
++) {
272 if (d_cnt
== dsize
) return 0;
273 dst
[d_cnt
++] = out_val
;
283 if (d_cnt
== dsize
) return 0;
284 dst
[d_cnt
++] = out_val
;
290 void init_hdlc_state(struct hdlc_state
*stateptr
, int mode
)
292 stateptr
->state
= HDLC_ZERO_SEARCH
;
295 stateptr
->o_bitcnt
= 0;
296 stateptr
->i_bitcnt
= 0;
297 stateptr
->insane_mode
= mode
;
300 /* Optimization suggestion: A similar state machine could surely
301 * be developed for this function as well.
304 int read_raw_hdlc_data(struct hdlc_state
*saved_state
,
305 u_char
*src
, u_int slen
, u_char
*dst
, u_int dsize
)
309 register u_char state
= saved_state
->state
;
310 register u_char r_one
= saved_state
->r_one
;
311 register u_char r_val
= saved_state
->r_val
;
312 register u_int o_bitcnt
= saved_state
->o_bitcnt
;
313 register u_int i_bitcnt
= saved_state
->i_bitcnt
;
314 register u_int fcs
= saved_state
->fcs
;
315 register u_int
*isrc
= (u_int
*) src
;
317 /* Use i_bitcnt (bit offset into source buffer) to reload "val"
318 * in case we're starting up again partway through a source buffer
321 if ((i_bitcnt
>> 3) < slen
) {
322 if (saved_state
->insane_mode
==1) {
323 val
= isrc
[(i_bitcnt
>> 3)] & 0xff;
324 } else if (saved_state
->insane_mode
==2) {
325 val
= (isrc
[i_bitcnt
>> 3] >>8) & 0xff;
327 val
= src
[i_bitcnt
>> 3];
329 val
>>= i_bitcnt
& 7;
332 /* One bit per loop. Keep going until we've got something to
333 * report (retval != 0), or we exhaust the source buffer
336 while ((retval
== 0) && ((i_bitcnt
>> 3) < slen
)) {
337 if ((i_bitcnt
& 7) == 0) {
338 if (saved_state
->insane_mode
==1) {
339 val
= isrc
[(i_bitcnt
>> 3)] & 0xff;
340 } else if (saved_state
->insane_mode
==2) {
341 val
= (isrc
[i_bitcnt
>> 3] >>8) & 0xff;
343 val
= src
[i_bitcnt
>> 3];
346 printf("Input byte %d: 0x%2x\n", i_bitcnt
>>3, val
);
349 state
= HDLC_ZERO_SEARCH
;
358 /* printf("Data bit=%d (%d/%d)\n", val&1, i_bitcnt>>3, i_bitcnt&7);*/
361 if (state
== HDLC_ZERO_SEARCH
) {
366 state
= HDLC_FLAG_SEARCH
;
368 } else if (state
== HDLC_FLAG_SEARCH
) {
372 state
=HDLC_ZERO_SEARCH
;
378 state
=HDLC_FLAG_FOUND
;
382 } else if (state
== HDLC_FLAG_FOUND
) {
386 state
=HDLC_ZERO_SEARCH
;
400 } else if (r_one
!=5) {
407 if ((state
!= HDLC_ZERO_SEARCH
) &&
410 printf("HDLC_FRAME_FOUND at i_bitcnt:%d\n",i_bitcnt
);
412 state
=HDLC_FRAME_FOUND
;
415 fcs
= PPP_FCS (fcs
, r_val
);
417 } else if (state
== HDLC_FRAME_FOUND
) {
421 state
=HDLC_ZERO_SEARCH
;
434 /* Alignment error */
436 printf("Alignment error\n");
438 state
=HDLC_FLAG_SEARCH
;
440 } else if (fcs
==PPP_GOODFCS
) {
442 state
=HDLC_FLAG_FOUND
;
443 retval
= (o_bitcnt
>>3)-3;
447 printf("CRC error; fcs was 0x%x, should have been 0x%x\n", fcs
, PPP_GOODFCS
);
449 state
=HDLC_FLAG_FOUND
;
452 } else if (r_one
==5) {
464 if ((state
== HDLC_FRAME_FOUND
) &&
466 if ((o_bitcnt
>>3)>=dsize
) {
467 /* Buffer overflow error */
469 printf("Buffer overflow error\n");
472 state
=HDLC_FLAG_SEARCH
;
475 dst
[(o_bitcnt
>>3)-1] = r_val
;
476 fcs
= PPP_FCS (fcs
, r_val
);
478 printf("Output byte %d: 0x%02x; FCS 0x%04x\n", (o_bitcnt
>>3)-1, r_val
, fcs
);
487 /* We exhausted the source buffer before anything else happened
488 * (retval==0). Reset i_bitcnt in expectation of a new source
489 * buffer. Other, we either had an error or a valid frame, so
490 * reset o_bitcnt in expectation of a new destination buffer.
499 saved_state
->state
= state
;
500 saved_state
->r_one
= r_one
;
501 saved_state
->r_val
= r_val
;
502 saved_state
->fcs
= fcs
;
503 saved_state
->o_bitcnt
= o_bitcnt
;
504 saved_state
->i_bitcnt
= i_bitcnt
;
520 struct hdlc_state hdlc_state
;
522 while((buffer
[buflen
] = getc(stdin
)) != EOF
&& buflen
<1024) buflen
++;
524 printf("buflen = %d\n", buflen
);
526 init_hdlc_state(&hdlc_state
, 0);
528 while (len
= read_raw_hdlc_data(&hdlc_state
,buffer
,buflen
,obuffer
,1024)) {
529 if (len
== -1) printf("Error @ byte %d/bit %d\n",
530 hdlc_state
.i_bitcnt
>>3, hdlc_state
.i_bitcnt
& 7);
532 printf("Frame received: len %d\n", len
);