fcs_calc.c 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123
  1. //
  2. // This file is part of Dire Wolf, an amateur radio packet TNC.
  3. //
  4. // Copyright (C) 2011 John Langner, WB2OSZ
  5. //
  6. // This program is free software: you can redistribute it and/or modify
  7. // it under the terms of the GNU General Public License as published by
  8. // the Free Software Foundation, either version 2 of the License, or
  9. // (at your option) any later version.
  10. //
  11. // This program is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. // GNU General Public License for more details.
  15. //
  16. // You should have received a copy of the GNU General Public License
  17. // along with this program. If not, see <http://www.gnu.org/licenses/>.
  18. //
  19. #include <stdio.h>
  20. /*
  21. * Calculate the FCS for an AX.25 frame.
  22. */
  23. #include "fcs_calc.h"
  24. static const unsigned short ccitt_table[256] = {
  25. // from http://www.ietf.org/rfc/rfc1549.txt
  26. 0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf,
  27. 0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xe97e, 0xf8f7,
  28. 0x1081, 0x0108, 0x3393, 0x221a, 0x56a5, 0x472c, 0x75b7, 0x643e,
  29. 0x9cc9, 0x8d40, 0xbfdb, 0xae52, 0xdaed, 0xcb64, 0xf9ff, 0xe876,
  30. 0x2102, 0x308b, 0x0210, 0x1399, 0x6726, 0x76af, 0x4434, 0x55bd,
  31. 0xad4a, 0xbcc3, 0x8e58, 0x9fd1, 0xeb6e, 0xfae7, 0xc87c, 0xd9f5,
  32. 0x3183, 0x200a, 0x1291, 0x0318, 0x77a7, 0x662e, 0x54b5, 0x453c,
  33. 0xbdcb, 0xac42, 0x9ed9, 0x8f50, 0xfbef, 0xea66, 0xd8fd, 0xc974,
  34. 0x4204, 0x538d, 0x6116, 0x709f, 0x0420, 0x15a9, 0x2732, 0x36bb,
  35. 0xce4c, 0xdfc5, 0xed5e, 0xfcd7, 0x8868, 0x99e1, 0xab7a, 0xbaf3,
  36. 0x5285, 0x430c, 0x7197, 0x601e, 0x14a1, 0x0528, 0x37b3, 0x263a,
  37. 0xdecd, 0xcf44, 0xfddf, 0xec56, 0x98e9, 0x8960, 0xbbfb, 0xaa72,
  38. 0x6306, 0x728f, 0x4014, 0x519d, 0x2522, 0x34ab, 0x0630, 0x17b9,
  39. 0xef4e, 0xfec7, 0xcc5c, 0xddd5, 0xa96a, 0xb8e3, 0x8a78, 0x9bf1,
  40. 0x7387, 0x620e, 0x5095, 0x411c, 0x35a3, 0x242a, 0x16b1, 0x0738,
  41. 0xffcf, 0xee46, 0xdcdd, 0xcd54, 0xb9eb, 0xa862, 0x9af9, 0x8b70,
  42. 0x8408, 0x9581, 0xa71a, 0xb693, 0xc22c, 0xd3a5, 0xe13e, 0xf0b7,
  43. 0x0840, 0x19c9, 0x2b52, 0x3adb, 0x4e64, 0x5fed, 0x6d76, 0x7cff,
  44. 0x9489, 0x8500, 0xb79b, 0xa612, 0xd2ad, 0xc324, 0xf1bf, 0xe036,
  45. 0x18c1, 0x0948, 0x3bd3, 0x2a5a, 0x5ee5, 0x4f6c, 0x7df7, 0x6c7e,
  46. 0xa50a, 0xb483, 0x8618, 0x9791, 0xe32e, 0xf2a7, 0xc03c, 0xd1b5,
  47. 0x2942, 0x38cb, 0x0a50, 0x1bd9, 0x6f66, 0x7eef, 0x4c74, 0x5dfd,
  48. 0xb58b, 0xa402, 0x9699, 0x8710, 0xf3af, 0xe226, 0xd0bd, 0xc134,
  49. 0x39c3, 0x284a, 0x1ad1, 0x0b58, 0x7fe7, 0x6e6e, 0x5cf5, 0x4d7c,
  50. 0xc60c, 0xd785, 0xe51e, 0xf497, 0x8028, 0x91a1, 0xa33a, 0xb2b3,
  51. 0x4a44, 0x5bcd, 0x6956, 0x78df, 0x0c60, 0x1de9, 0x2f72, 0x3efb,
  52. 0xd68d, 0xc704, 0xf59f, 0xe416, 0x90a9, 0x8120, 0xb3bb, 0xa232,
  53. 0x5ac5, 0x4b4c, 0x79d7, 0x685e, 0x1ce1, 0x0d68, 0x3ff3, 0x2e7a,
  54. 0xe70e, 0xf687, 0xc41c, 0xd595, 0xa12a, 0xb0a3, 0x8238, 0x93b1,
  55. 0x6b46, 0x7acf, 0x4854, 0x59dd, 0x2d62, 0x3ceb, 0x0e70, 0x1ff9,
  56. 0xf78f, 0xe606, 0xd49d, 0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330,
  57. 0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78
  58. };
  59. /*
  60. * Use this for an AX.25 frame.
  61. */
  62. unsigned short fcs_calc (unsigned char *data, int len)
  63. {
  64. unsigned short crc = 0xffff;
  65. int j;
  66. for (j=0; j<len; j++) {
  67. crc = ((crc) >> 8) ^ ccitt_table[((crc) ^ data[j]) & 0xff];
  68. }
  69. return ( crc ^ 0xffff );
  70. }
  71. /*
  72. * CRC is also used for duplicate checking for the digipeater and IGate.
  73. * A packet is considered a duplicate if the source, destination, and
  74. * information parts match. In other words, we ignore the via path
  75. * which changes along the way.
  76. * Rather than keeping a variable length string we just keep a 16 bit
  77. * CRC which takes less memory and processing to compare.
  78. *
  79. * This can result in occasional false matches. If we had a random
  80. * 16 bit number, there is a 1/65536 ( = 0.0015 % ) chance that it will
  81. * match and we will drop something that should be passed along.
  82. *
  83. * Looking at it another way, there is a 0.9999847412109375 (out of 1)
  84. * probability of doing the right thing.
  85. */
  86. /*
  87. * This can be used when we want to calculate a single CRC over disjoint data.
  88. *
  89. * crc = crc16 (region1, sizeof(region1), 0xffff);
  90. * crc = crc16 (region2, sizeof(region2), crc);
  91. * crc = crc16 (region3, sizeof(region3), crc);
  92. */
  93. unsigned short crc16 (unsigned char *data, int len, unsigned short seed)
  94. {
  95. unsigned short crc = seed;
  96. int j;
  97. for (j=0; j<len; j++) {
  98. crc = ((crc) >> 8) ^ ccitt_table[((crc) ^ data[j]) & 0xff];
  99. }
  100. return ( crc ^ 0xffff );
  101. }