1190203Srpaulo/* 2190203Srpaulo * Copyright (c) 1998-2006 The TCPDUMP project 3190203Srpaulo * 4190203Srpaulo * Redistribution and use in source and binary forms, with or without 5190203Srpaulo * modification, are permitted provided that: (1) source code 6190203Srpaulo * distributions retain the above copyright notice and this paragraph 7190203Srpaulo * in its entirety, and (2) distributions including binary code include 8190203Srpaulo * the above copyright notice and this paragraph in its entirety in 9190203Srpaulo * the documentation or other materials provided with the distribution. 10190203Srpaulo * THIS SOFTWARE IS PROVIDED ``AS IS'' AND 11190203Srpaulo * WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT 12190203Srpaulo * LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 13190203Srpaulo * FOR A PARTICULAR PURPOSE. 14190203Srpaulo * 15190203Srpaulo * miscellaneous checksumming routines 16190203Srpaulo * 17190203Srpaulo * Original code by Hannes Gredler (hannes@juniper.net) 18190203Srpaulo */ 19190203Srpaulo 20190203Srpaulo#ifndef lint 21190203Srpaulostatic const char rcsid[] _U_ = 22190203Srpaulo "@(#) $Header: /tcpdump/master/tcpdump/checksum.c,v 1.4 2006-09-25 09:23:32 hannes Exp $"; 23190203Srpaulo#endif 24190203Srpaulo 25190203Srpaulo#ifdef HAVE_CONFIG_H 26190203Srpaulo#include "config.h" 27190203Srpaulo#endif 28190203Srpaulo 29190203Srpaulo#include <tcpdump-stdinc.h> 30190203Srpaulo 31190203Srpaulo#include <stdio.h> 32190203Srpaulo#include <stdlib.h> 33190203Srpaulo#include <string.h> 34214478Srpaulo#include <assert.h> 35190203Srpaulo 36190203Srpaulo#include "interface.h" 37190203Srpaulo 38214478Srpaulo/* 39214478Srpaulo * CRC-10 table generated using the following Python snippet: 40190203Srpaulo 41214478Srpauloimport sys 42214478Srpaulo 43214478Srpaulocrc_table = [] 44214478Srpaulofor i in range(256): 45214478Srpaulo accum = i << 2 46214478Srpaulo for j in range(8): 47214478Srpaulo accum <<= 1 48214478Srpaulo if accum & 0x400: 49214478Srpaulo accum ^= 0x633 50214478Srpaulo crc_table.append(accum) 51214478Srpaulo 52214478Srpaulofor i in range(len(crc_table)/8): 53214478Srpaulo for j in range(8): 54214478Srpaulo sys.stdout.write("0x%04x, " % crc_table[i*8+j]) 55214478Srpaulo sys.stdout.write("\n") 56214478Srpaulo 57214478Srpaulo */ 58214478Srpaulostatic const u_int16_t crc10_table[256] = 59214478Srpaulo{ 60214478Srpaulo 0x0000, 0x0233, 0x0255, 0x0066, 0x0299, 0x00aa, 0x00cc, 0x02ff, 61214478Srpaulo 0x0301, 0x0132, 0x0154, 0x0367, 0x0198, 0x03ab, 0x03cd, 0x01fe, 62214478Srpaulo 0x0031, 0x0202, 0x0264, 0x0057, 0x02a8, 0x009b, 0x00fd, 0x02ce, 63214478Srpaulo 0x0330, 0x0103, 0x0165, 0x0356, 0x01a9, 0x039a, 0x03fc, 0x01cf, 64214478Srpaulo 0x0062, 0x0251, 0x0237, 0x0004, 0x02fb, 0x00c8, 0x00ae, 0x029d, 65214478Srpaulo 0x0363, 0x0150, 0x0136, 0x0305, 0x01fa, 0x03c9, 0x03af, 0x019c, 66214478Srpaulo 0x0053, 0x0260, 0x0206, 0x0035, 0x02ca, 0x00f9, 0x009f, 0x02ac, 67214478Srpaulo 0x0352, 0x0161, 0x0107, 0x0334, 0x01cb, 0x03f8, 0x039e, 0x01ad, 68214478Srpaulo 0x00c4, 0x02f7, 0x0291, 0x00a2, 0x025d, 0x006e, 0x0008, 0x023b, 69214478Srpaulo 0x03c5, 0x01f6, 0x0190, 0x03a3, 0x015c, 0x036f, 0x0309, 0x013a, 70214478Srpaulo 0x00f5, 0x02c6, 0x02a0, 0x0093, 0x026c, 0x005f, 0x0039, 0x020a, 71214478Srpaulo 0x03f4, 0x01c7, 0x01a1, 0x0392, 0x016d, 0x035e, 0x0338, 0x010b, 72214478Srpaulo 0x00a6, 0x0295, 0x02f3, 0x00c0, 0x023f, 0x000c, 0x006a, 0x0259, 73214478Srpaulo 0x03a7, 0x0194, 0x01f2, 0x03c1, 0x013e, 0x030d, 0x036b, 0x0158, 74214478Srpaulo 0x0097, 0x02a4, 0x02c2, 0x00f1, 0x020e, 0x003d, 0x005b, 0x0268, 75214478Srpaulo 0x0396, 0x01a5, 0x01c3, 0x03f0, 0x010f, 0x033c, 0x035a, 0x0169, 76214478Srpaulo 0x0188, 0x03bb, 0x03dd, 0x01ee, 0x0311, 0x0122, 0x0144, 0x0377, 77214478Srpaulo 0x0289, 0x00ba, 0x00dc, 0x02ef, 0x0010, 0x0223, 0x0245, 0x0076, 78214478Srpaulo 0x01b9, 0x038a, 0x03ec, 0x01df, 0x0320, 0x0113, 0x0175, 0x0346, 79214478Srpaulo 0x02b8, 0x008b, 0x00ed, 0x02de, 0x0021, 0x0212, 0x0274, 0x0047, 80214478Srpaulo 0x01ea, 0x03d9, 0x03bf, 0x018c, 0x0373, 0x0140, 0x0126, 0x0315, 81214478Srpaulo 0x02eb, 0x00d8, 0x00be, 0x028d, 0x0072, 0x0241, 0x0227, 0x0014, 82214478Srpaulo 0x01db, 0x03e8, 0x038e, 0x01bd, 0x0342, 0x0171, 0x0117, 0x0324, 83214478Srpaulo 0x02da, 0x00e9, 0x008f, 0x02bc, 0x0043, 0x0270, 0x0216, 0x0025, 84214478Srpaulo 0x014c, 0x037f, 0x0319, 0x012a, 0x03d5, 0x01e6, 0x0180, 0x03b3, 85214478Srpaulo 0x024d, 0x007e, 0x0018, 0x022b, 0x00d4, 0x02e7, 0x0281, 0x00b2, 86214478Srpaulo 0x017d, 0x034e, 0x0328, 0x011b, 0x03e4, 0x01d7, 0x01b1, 0x0382, 87214478Srpaulo 0x027c, 0x004f, 0x0029, 0x021a, 0x00e5, 0x02d6, 0x02b0, 0x0083, 88214478Srpaulo 0x012e, 0x031d, 0x037b, 0x0148, 0x03b7, 0x0184, 0x01e2, 0x03d1, 89214478Srpaulo 0x022f, 0x001c, 0x007a, 0x0249, 0x00b6, 0x0285, 0x02e3, 0x00d0, 90214478Srpaulo 0x011f, 0x032c, 0x034a, 0x0179, 0x0386, 0x01b5, 0x01d3, 0x03e0, 91214478Srpaulo 0x021e, 0x002d, 0x004b, 0x0278, 0x0087, 0x02b4, 0x02d2, 0x00e1 92214478Srpaulo}; 93214478Srpaulo 94190203Srpaulostatic void 95190203Srpauloinit_crc10_table(void) 96190203Srpaulo{ 97214478Srpaulo#define CRC10_POLYNOMIAL 0x633 98190203Srpaulo register int i, j; 99190203Srpaulo register u_int16_t accum; 100214478Srpaulo u_int16_t verify_crc10_table[256]; 101190203Srpaulo 102190203Srpaulo for ( i = 0; i < 256; i++ ) 103190203Srpaulo { 104190203Srpaulo accum = ((unsigned short) i << 2); 105190203Srpaulo for ( j = 0; j < 8; j++ ) 106190203Srpaulo { 107190203Srpaulo if ((accum <<= 1) & 0x400) accum ^= CRC10_POLYNOMIAL; 108190203Srpaulo } 109214478Srpaulo verify_crc10_table[i] = accum; 110190203Srpaulo } 111214478Srpaulo assert(memcmp(verify_crc10_table, 112214478Srpaulo crc10_table, 113214478Srpaulo sizeof(verify_crc10_table)) == 0); 114214478Srpaulo#undef CRC10_POLYNOMIAL 115190203Srpaulo} 116190203Srpaulo 117190203Srpaulou_int16_t 118190203Srpauloverify_crc10_cksum(u_int16_t accum, const u_char *p, int length) 119190203Srpaulo{ 120190203Srpaulo register int i; 121190203Srpaulo 122190203Srpaulo for ( i = 0; i < length; i++ ) 123190203Srpaulo { 124190203Srpaulo accum = ((accum << 8) & 0x3ff) 125190203Srpaulo ^ crc10_table[( accum >> 2) & 0xff] 126190203Srpaulo ^ *p++; 127190203Srpaulo } 128190203Srpaulo return accum; 129190203Srpaulo} 130190203Srpaulo 131190203Srpaulo/* precompute checksum tables */ 132190203Srpaulovoid 133190203Srpauloinit_checksum(void) { 134190203Srpaulo 135190203Srpaulo init_crc10_table(); 136190203Srpaulo 137190203Srpaulo} 138190203Srpaulo 139190203Srpaulo/* 140190203Srpaulo * Creates the OSI Fletcher checksum. See 8473-1, Appendix C, section C.3. 141190203Srpaulo * The checksum field of the passed PDU does not need to be reset to zero. 142190203Srpaulo */ 143190203Srpaulou_int16_t 144190203Srpaulocreate_osi_cksum (const u_int8_t *pptr, int checksum_offset, int length) 145190203Srpaulo{ 146190203Srpaulo 147190203Srpaulo int x; 148190203Srpaulo int y; 149190203Srpaulo u_int32_t mul; 150190203Srpaulo u_int32_t c0; 151190203Srpaulo u_int32_t c1; 152190203Srpaulo u_int16_t checksum; 153190203Srpaulo int index; 154190203Srpaulo 155190203Srpaulo c0 = 0; 156190203Srpaulo c1 = 0; 157190203Srpaulo 158190203Srpaulo for (index = 0; index < length; index++) { 159190203Srpaulo /* 160190203Srpaulo * Ignore the contents of the checksum field. 161190203Srpaulo */ 162190203Srpaulo if (index == checksum_offset || 163190203Srpaulo index == checksum_offset+1) { 164190203Srpaulo c1 += c0; 165190203Srpaulo pptr++; 166190203Srpaulo } else { 167190203Srpaulo c0 = c0 + *(pptr++); 168190203Srpaulo c1 += c0; 169190203Srpaulo } 170190203Srpaulo } 171190203Srpaulo 172190203Srpaulo c0 = c0 % 255; 173190203Srpaulo c1 = c1 % 255; 174190203Srpaulo 175190203Srpaulo mul = (length - checksum_offset)*(c0); 176190203Srpaulo 177190203Srpaulo x = mul - c0 - c1; 178190203Srpaulo y = c1 - mul - 1; 179190203Srpaulo 180190203Srpaulo if ( y >= 0 ) y++; 181190203Srpaulo if ( x < 0 ) x--; 182190203Srpaulo 183190203Srpaulo x %= 255; 184190203Srpaulo y %= 255; 185190203Srpaulo 186190203Srpaulo 187190203Srpaulo if (x == 0) x = 255; 188190203Srpaulo if (y == 0) y = 255; 189190203Srpaulo 190190203Srpaulo y &= 0x00FF; 191190203Srpaulo checksum = ((x << 8) | y); 192190203Srpaulo 193190203Srpaulo return checksum; 194190203Srpaulo} 195