File: /usr/src/linux/drivers/isdn/hisax/rawhdlc.c
1 /* $Id: rawhdlc.c,v 1.5.6.1 2001/02/16 16:43:28 kai Exp $
2 *
3 * rawhdlc.c support routines for cards that don't support HDLC
4 *
5 * Author Karsten Keil (keil@isdn4linux.de)
6 * Brent Baccala <baccala@FreeSoft.org>
7 *
8 * This file is (c) under GNU General Public License
9 *
10 * Some passive ISDN cards, such as the Traverse NETJet and the AMD 7930,
11 * don't perform HDLC encapsulation over the B channel. Drivers for
12 * such cards use support routines in this file to perform B channel HDLC.
13 *
14 * Bit-synchronous HDLC encapsulation is a means of encapsulating packets
15 * over a continuously transmitting serial communications link.
16 * It looks like this:
17 *
18 * 11111111101111110...........0111111011111111111
19 * iiiiiiiiiffffffffdddddddddddffffffffiiiiiiiiiii
20 *
21 * i = idle f = flag d = data
22 *
23 * When idle, the channel sends a continuous string of ones (mark
24 * idle; illustrated), or a continuous string of flag characters (flag
25 * idle). The beginning of a data frame is marked by a flag character
26 * (01111110), then comes the actual data, followed by another flag
27 * character, after which another frame may be sent immediately (a
28 * single flag may serve as both the end of one frame and the start of
29 * the next), or the link may return to idle. Obviously, the flag
30 * character can not appear anywhere in the data (or a false
31 * end-of-frame would occur), so the transmitter performs
32 * "bit-stuffing" - inserting a zero bit after every five one bits,
33 * irregardless of the original bit after the five ones. Byte
34 * ordering is irrelevent at this point - the data is treated as a
35 * string of bits, not bytes. Since no more than 5 ones may now occur
36 * in a row, the flag sequence, with its 6 ones, is unique.
37 *
38 * Upon reception, a zero bit that occur after 5 one bits is simply
39 * discarded. A series of 6 one bits is end-of-frame, and a series of
40 * 7 one bits is an abort. Once bit-stuffing has been corrected for,
41 * an integer number of bytes should now be present. The last two
42 * of these bytes form the Frame Check Sequence, a CRC that is verified
43 * and then discarded. Note that bit-stuffing is performed on the FCS
44 * just as if it were regular data.
45 *
46 *
47 *
48 * int make_raw_hdlc_data(u_char *src, u_int slen,
49 * u_char *dst, u_int dsize)
50 *
51 * Used for transmission. Copies slen bytes from src to dst, performing
52 * HDLC encapsulation (flag bytes, bit-stuffing, CRC) in the process.
53 * dsize is size of destination buffer, and should be at least
54 * ((6*slen)/5)+5 bytes to ensure adequate space will be available.
55 * Function returns length (in bytes) of valid destination buffer, or
56 * 0 upon destination overflow.
57 *
58 * void init_hdlc_state(struct hdlc_state *stateptr, int mode)
59 *
60 * Initializes hdlc_state structure before first call to read_raw_hdlc_data
61 *
62 * mode = 0: Sane mode
63 * mode = 1/2:
64 * Insane mode; NETJet use a shared unsigned int memory block (
65 * with busmaster DMA), the bit pattern of every word is
66 * <8 B1> <8 B2> <8 Mon> <2 D> <4 C/I> <MX> <MR>
67 * according to Siemens IOM-2 interface, so we have to handle
68 * the src buffer as unsigned int and have to shift/mask the
69 * B-channel bytes.
70 * mode 1 -> B1 mode 2 -> B2 data is used
71 *
72 * int read_raw_hdlc_data(struct hdlc_state *saved_state,
73 * u_char *src, u_int slen,
74 * u_char *dst, u_int dsize)
75 *
76 * Used for reception. Scans source buffer bit-by-bit looking for
77 * valid HDLC frames, which are copied to destination buffer. HDLC
78 * state information is stored in a structure, which allows this
79 * function to process frames spread across several blocks of raw
80 * HDLC data. Part of the state information is bit offsets into
81 * the source and destination buffers.
82 *
83 * A return value >0 indicates the length of a valid frame, now
84 * stored in the destination buffer. In this case, the source
85 * buffer might not be completely processed, so this function should
86 * be called again with the same source buffer, possibly with a
87 * different destination buffer.
88 *
89 * A return value of zero indicates that the source buffer was
90 * completely processed without finding a valid end-of-packet;
91 * however, we might be in the middle of packet reception, so
92 * the function should be called again with the next block of
93 * raw HDLC data and the same destination buffer. It is NOT
94 * permitted to change the destination buffer in this case,
95 * since data may already have begun to be stored there.
96 *
97 * A return value of -1 indicates some kind of error - destination
98 * buffer overflow, CRC check failed, frame not a multiple of 8
99 * bits. Destination buffer probably contains invalid data, which
100 * should be discarded. Call function again with same source buffer
101 * and a new (or same) destination buffer.
102 *
103 * Suggested calling sequence:
104 *
105 * init_hdlc_state(...);
106 * for (EACH_RAW_DATA_BLOCK) {
107 * while (len = read_raw_hdlc_data(...)) {
108 * if (len == -1) DISCARD_FRAME;
109 * else PROCESS_FRAME;
110 * }
111 * }
112 *
113 *
114 * Test the code in this file as follows:
115 * gcc -DDEBUGME -o rawhdlctest rawhdlc.c
116 * ./rawhdlctest < rawdata
117 *
118 * The file "rawdata" can be easily generated from a HISAX B-channel
119 * hex dump (CF CF CF 02 ...) using the following perl script:
120 *
121 * while(<>) {
122 * @hexlist = split ' ';
123 * while ($hexstr = shift(@hexlist)) {
124 * printf "%c", hex($hexstr);
125 * }
126 * }
127 *
128 */
129
130 #ifdef DEBUGME
131 #include <stdio.h>
132 #endif
133
134 #include <linux/types.h>
135 #include <linux/ppp_defs.h>
136 #include "rawhdlc.h"
137
138 /* There's actually an identical copy of this table in the PPP code
139 * (ppp_crc16_table), but I don't want this code dependent on PPP
140 */
141
142 // static
143 __u16 fcstab[256] =
144 {
145 0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
146 0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
147 0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
148 0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
149 0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
150 0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
151 0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
152 0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
153 0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
154 0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
155 0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
156 0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
157 0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
158 0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
159 0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
160 0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
161 0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
162 0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
163 0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
164 0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
165 0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
166 0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
167 0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
168 0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
169 0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
170 0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
171 0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
172 0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
173 0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
174 0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
175 0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
176 0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
177 };
178
179 #define HDLC_ZERO_SEARCH 0
180 #define HDLC_FLAG_SEARCH 1
181 #define HDLC_FLAG_FOUND 2
182 #define HDLC_FRAME_FOUND 3
183 #define HDLC_NULL 4
184 #define HDLC_PART 5
185 #define HDLC_FULL 6
186
187 #define HDLC_FLAG_VALUE 0x7e
188
189
190 #define MAKE_RAW_BYTE for (j=0; j<8; j++) { \
191 bitcnt++;\
192 out_val >>= 1;\
193 if (val & 1) {\
194 s_one++;\
195 out_val |= 0x80;\
196 } else {\
197 s_one = 0;\
198 out_val &= 0x7f;\
199 }\
200 if (bitcnt==8) {\
201 if (d_cnt == dsize) return 0;\
202 dst[d_cnt++] = out_val;\
203 bitcnt = 0;\
204 }\
205 if (s_one == 5) {\
206 out_val >>= 1;\
207 out_val &= 0x7f;\
208 bitcnt++;\
209 s_one = 0;\
210 }\
211 if (bitcnt==8) {\
212 if (d_cnt == dsize) return 0;\
213 dst[d_cnt++] = out_val;\
214 bitcnt = 0;\
215 }\
216 val >>= 1;\
217 }
218
219 /* Optimization suggestion: If needed, this function could be
220 * dramatically sped up using a state machine. Each state would
221 * correspond to having seen N one bits, and being offset M bits into
222 * the current output byte. N ranges from 0 to 4, M from 0 to 7, so
223 * we need 5*8 = 35 states. Each state would have a table with 256
224 * entries, one for each input character. Each entry would contain
225 * three output characters, an output state, an a byte increment
226 * that's either 1 or 2. All this could fit in four bytes; so we need
227 * 4 bytes * 256 characters = 1 KB for each state (35 KB total). Zero
228 * the output buffer before you start. For each character in your
229 * input, you look it up in the current state's table and get three
230 * bytes to be or'ed into the output at the current byte offset, and
231 * an byte increment to move your pointer forward. A simple Perl
232 * script could generate the tables. Given HDLC semantics, probably
233 * would be better to set output to all 1s, then use ands instead of ors.
234 * A smaller state machine could operate on nibbles instead of bytes.
235 * A state machine for 32-bit architectures could use word offsets
236 * instead of byte offsets, requiring 5*32 = 160 states; probably
237 * best to work on nibbles in such a case.
238 */
239
240
241 int make_raw_hdlc_data(u_char *src, u_int slen, u_char *dst, u_int dsize)
242 {
243 register u_int i,d_cnt=0;
244 register u_char j;
245 register u_char val;
246 register u_char s_one = 0;
247 register u_char out_val = 0;
248 register u_char bitcnt = 0;
249 u_int fcs;
250
251
252 dst[d_cnt++] = HDLC_FLAG_VALUE;
253 fcs = PPP_INITFCS;
254 for (i=0; i<slen; i++) {
255 val = src[i];
256 fcs = PPP_FCS (fcs, val);
257 MAKE_RAW_BYTE;
258 }
259 fcs ^= 0xffff;
260 val = fcs & 0xff;
261 MAKE_RAW_BYTE;
262 val = (fcs>>8) & 0xff;
263 MAKE_RAW_BYTE;
264 val = HDLC_FLAG_VALUE;
265 for (j=0; j<8; j++) {
266 bitcnt++;
267 out_val >>= 1;
268 if (val & 1)
269 out_val |= 0x80;
270 else
271 out_val &= 0x7f;
272 if (bitcnt==8) {
273 if (d_cnt == dsize) return 0;
274 dst[d_cnt++] = out_val;
275 bitcnt = 0;
276 }
277 val >>= 1;
278 }
279 if (bitcnt) {
280 while (8>bitcnt++) {
281 out_val >>= 1;
282 out_val |= 0x80;
283 }
284 if (d_cnt == dsize) return 0;
285 dst[d_cnt++] = out_val;
286 }
287
288 return d_cnt;
289 }
290
291 void init_hdlc_state(struct hdlc_state *stateptr, int mode)
292 {
293 stateptr->state = HDLC_ZERO_SEARCH;
294 stateptr->r_one = 0;
295 stateptr->r_val = 0;
296 stateptr->o_bitcnt = 0;
297 stateptr->i_bitcnt = 0;
298 stateptr->insane_mode = mode;
299 }
300
301 /* Optimization suggestion: A similar state machine could surely
302 * be developed for this function as well.
303 */
304
305 int read_raw_hdlc_data(struct hdlc_state *saved_state,
306 u_char *src, u_int slen, u_char *dst, u_int dsize)
307 {
308 int retval=0;
309 register u_char val;
310 register u_char state = saved_state->state;
311 register u_char r_one = saved_state->r_one;
312 register u_char r_val = saved_state->r_val;
313 register u_int o_bitcnt = saved_state->o_bitcnt;
314 register u_int i_bitcnt = saved_state->i_bitcnt;
315 register u_int fcs = saved_state->fcs;
316 register u_int *isrc = (u_int *) src;
317
318 /* Use i_bitcnt (bit offset into source buffer) to reload "val"
319 * in case we're starting up again partway through a source buffer
320 */
321
322 if ((i_bitcnt >> 3) < slen) {
323 if (saved_state->insane_mode==1) {
324 val = isrc[(i_bitcnt >> 3)] & 0xff;
325 } else if (saved_state->insane_mode==2) {
326 val = (isrc[i_bitcnt >> 3] >>8) & 0xff;
327 } else {
328 val = src[i_bitcnt >> 3];
329 }
330 val >>= i_bitcnt & 7;
331 }
332
333 /* One bit per loop. Keep going until we've got something to
334 * report (retval != 0), or we exhaust the source buffer
335 */
336
337 while ((retval == 0) && ((i_bitcnt >> 3) < slen)) {
338 if ((i_bitcnt & 7) == 0) {
339 if (saved_state->insane_mode==1) {
340 val = isrc[(i_bitcnt >> 3)] & 0xff;
341 } else if (saved_state->insane_mode==2) {
342 val = (isrc[i_bitcnt >> 3] >>8) & 0xff;
343 } else {
344 val = src[i_bitcnt >> 3];
345 }
346 #ifdef DEBUGME
347 printf("Input byte %d: 0x%2x\n", i_bitcnt>>3, val);
348 #endif
349 if (val == 0xff) {
350 state = HDLC_ZERO_SEARCH;
351 o_bitcnt = 0;
352 r_one = 0;
353 i_bitcnt += 8;
354 continue;
355 }
356 }
357
358 #ifdef DEBUGME
359 /* printf("Data bit=%d (%d/%d)\n", val&1, i_bitcnt>>3, i_bitcnt&7);*/
360 #endif
361
362 if (state == HDLC_ZERO_SEARCH) {
363 if (val & 1) {
364 r_one++;
365 } else {
366 r_one=0;
367 state= HDLC_FLAG_SEARCH;
368 }
369 } else if (state == HDLC_FLAG_SEARCH) {
370 if (val & 1) {
371 r_one++;
372 if (r_one>6) {
373 state=HDLC_ZERO_SEARCH;
374 }
375 } else {
376 if (r_one==6) {
377 o_bitcnt=0;
378 r_val=0;
379 state=HDLC_FLAG_FOUND;
380 }
381 r_one=0;
382 }
383 } else if (state == HDLC_FLAG_FOUND) {
384 if (val & 1) {
385 r_one++;
386 if (r_one>6) {
387 state=HDLC_ZERO_SEARCH;
388 } else {
389 r_val >>= 1;
390 r_val |= 0x80;
391 o_bitcnt++;
392 }
393 } else {
394 if (r_one==6) {
395 o_bitcnt=0;
396 r_val=0;
397 r_one=0;
398 i_bitcnt++;
399 val >>= 1;
400 continue;
401 } else if (r_one!=5) {
402 r_val >>= 1;
403 r_val &= 0x7f;
404 o_bitcnt++;
405 }
406 r_one=0;
407 }
408 if ((state != HDLC_ZERO_SEARCH) &&
409 !(o_bitcnt & 7)) {
410 #ifdef DEBUGME
411 printf("HDLC_FRAME_FOUND at i_bitcnt:%d\n",i_bitcnt);
412 #endif
413 state=HDLC_FRAME_FOUND;
414 fcs = PPP_INITFCS;
415 dst[0] = r_val;
416 fcs = PPP_FCS (fcs, r_val);
417 }
418 } else if (state == HDLC_FRAME_FOUND) {
419 if (val & 1) {
420 r_one++;
421 if (r_one>6) {
422 state=HDLC_ZERO_SEARCH;
423 o_bitcnt=0;
424 } else {
425 r_val >>= 1;
426 r_val |= 0x80;
427 o_bitcnt++;
428 }
429 } else {
430 if (r_one==6) {
431 r_val=0;
432 r_one=0;
433 o_bitcnt++;
434 if (o_bitcnt & 7) {
435 /* Alignment error */
436 #ifdef DEBUGME
437 printf("Alignment error\n");
438 #endif
439 state=HDLC_FLAG_SEARCH;
440 retval = -1;
441 } else if (fcs==PPP_GOODFCS) {
442 /* Valid frame */
443 state=HDLC_FLAG_FOUND;
444 retval = (o_bitcnt>>3)-3;
445 } else {
446 /* CRC error */
447 #ifdef DEBUGME
448 printf("CRC error; fcs was 0x%x, should have been 0x%x\n", fcs, PPP_GOODFCS);
449 #endif
450 state=HDLC_FLAG_FOUND;
451 retval = -1;
452 }
453 } else if (r_one==5) {
454 r_one=0;
455 i_bitcnt++;
456 val >>= 1;
457 continue;
458 } else {
459 r_val >>= 1;
460 r_val &= 0x7f;
461 o_bitcnt++;
462 }
463 r_one=0;
464 }
465 if ((state == HDLC_FRAME_FOUND) &&
466 !(o_bitcnt & 7)) {
467 if ((o_bitcnt>>3)>=dsize) {
468 /* Buffer overflow error */
469 #ifdef DEBUGME
470 printf("Buffer overflow error\n");
471 #endif
472 r_val=0;
473 state=HDLC_FLAG_SEARCH;
474 retval = -1;
475 } else {
476 dst[(o_bitcnt>>3)-1] = r_val;
477 fcs = PPP_FCS (fcs, r_val);
478 #ifdef DEBUGME
479 printf("Output byte %d: 0x%02x; FCS 0x%04x\n", (o_bitcnt>>3)-1, r_val, fcs);
480 #endif
481 }
482 }
483 }
484 i_bitcnt ++;
485 val >>= 1;
486 }
487
488 /* We exhausted the source buffer before anything else happened
489 * (retval==0). Reset i_bitcnt in expectation of a new source
490 * buffer. Other, we either had an error or a valid frame, so
491 * reset o_bitcnt in expectation of a new destination buffer.
492 */
493
494 if (retval == 0) {
495 i_bitcnt = 0;
496 } else {
497 o_bitcnt = 0;
498 }
499
500 saved_state->state = state;
501 saved_state->r_one = r_one;
502 saved_state->r_val = r_val;
503 saved_state->fcs = fcs;
504 saved_state->o_bitcnt = o_bitcnt;
505 saved_state->i_bitcnt = i_bitcnt;
506
507 return (retval);
508 }
509
510
511
512 #ifdef DEBUGME
513
514 char buffer[1024];
515 char obuffer[1024];
516
517 main()
518 {
519 int buflen=0;
520 int len;
521 struct hdlc_state hdlc_state;
522
523 while((buffer[buflen] = getc(stdin)) != EOF && buflen<1024) buflen++;
524
525 printf("buflen = %d\n", buflen);
526
527 init_hdlc_state(&hdlc_state, 0);
528
529 while (len = read_raw_hdlc_data(&hdlc_state,buffer,buflen,obuffer,1024)) {
530 if (len == -1) printf("Error @ byte %d/bit %d\n",
531 hdlc_state.i_bitcnt>>3, hdlc_state.i_bitcnt & 7);
532 else {
533 printf("Frame received: len %d\n", len);
534 }
535 }
536
537 printf("Done\n");
538 }
539
540 #endif
541