crypto_crc.c 5.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  1. /*
  2. This file is part of GNUnet.
  3. Copyright (C) 2001, 2002, 2003, 2004, 2006 GNUnet e.V.
  4. GNUnet is free software: you can redistribute it and/or modify it
  5. under the terms of the GNU Affero General Public License as published
  6. by the Free Software Foundation, either version 3 of the License,
  7. or (at your option) any later version.
  8. GNUnet is distributed in the hope that it will be useful, but
  9. WITHOUT ANY WARRANTY; without even the implied warranty of
  10. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. Affero General Public License for more details.
  12. You should have received a copy of the GNU Affero General Public License
  13. along with this program. If not, see <http://www.gnu.org/licenses/>.
  14. SPDX-License-Identifier: AGPL3.0-or-later
  15. For the actual CRC-32 code:
  16. Copyright abandoned; this code is in the public domain.
  17. Provided to GNUnet by peter@horizon.com
  18. */
  19. /**
  20. * @file util/crypto_crc.c
  21. * @brief implementation of CRC16 and CRC32
  22. * @author Christian Grothoff
  23. */
  24. #include "platform.h"
  25. #include "gnunet_crypto_lib.h"
  26. #define LOG(kind, ...) GNUNET_log_from (kind, "util-crypto-crc", __VA_ARGS__)
  27. /* Avoid wasting space on 8-byte longs. */
  28. #if UINT_MAX >= 0xffffffff
  29. typedef unsigned int GNUNET_uLong;
  30. #elif ULONG_MAX >= 0xffffffff
  31. typedef unsigned long GNUNET_uLong;
  32. #else
  33. #error This compiler is not ANSI-compliant!
  34. #endif
  35. #define Z_NULL 0
  36. #define POLYNOMIAL (GNUNET_uLong) 0xedb88320
  37. static GNUNET_uLong crc_table[256];
  38. /*
  39. * This routine writes each crc_table entry exactly once,
  40. * with the correct final value. Thus, it is safe to call
  41. * even on a table that someone else is using concurrently.
  42. */
  43. static void
  44. crc_init ()
  45. {
  46. static int once;
  47. unsigned int i, j;
  48. GNUNET_uLong h = 1;
  49. if (once)
  50. return;
  51. once = 1;
  52. crc_table[0] = 0;
  53. for (i = 128; i; i >>= 1)
  54. {
  55. h = (h >> 1) ^ ((h & 1) ? POLYNOMIAL : 0);
  56. /* h is now crc_table[i] */
  57. for (j = 0; j < 256; j += 2 * i)
  58. crc_table[i + j] = crc_table[j] ^ h;
  59. }
  60. }
  61. /*
  62. * This computes the standard preset and inverted CRC, as used
  63. * by most networking standards. Start by passing in an initial
  64. * chaining value of 0, and then pass in the return value from the
  65. * previous crc32() call. The final return value is the CRC.
  66. * Note that this is a little-endian CRC, which is best used with
  67. * data transmitted lsbit-first, and it should, itself, be appended
  68. * to data in little-endian byte and bit order to preserve the
  69. * property of detecting all burst errors of length 32 bits or less.
  70. */
  71. static GNUNET_uLong
  72. crc32 (GNUNET_uLong crc, const char *buf, size_t len)
  73. {
  74. crc_init ();
  75. GNUNET_assert (crc_table[255] != 0);
  76. crc ^= 0xffffffff;
  77. while (len--)
  78. crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
  79. return crc ^ 0xffffffff;
  80. }
  81. /**
  82. * Compute the CRC32 checksum for the first len bytes of the buffer.
  83. *
  84. * @param buf the data over which we're taking the CRC
  85. * @param len the length of the buffer
  86. * @return the resulting CRC32 checksum
  87. */
  88. int32_t
  89. GNUNET_CRYPTO_crc32_n (const void *buf, size_t len)
  90. {
  91. GNUNET_uLong crc;
  92. crc = crc32 (0L, Z_NULL, 0);
  93. crc = crc32 (crc, (char *) buf, len);
  94. return crc;
  95. }
  96. /**
  97. * Perform an incremental step in a CRC16 (for TCP/IP) calculation.
  98. *
  99. * @param sum current sum, initially 0
  100. * @param buf buffer to calculate CRC over (must be 16-bit aligned)
  101. * @param len number of bytes in hdr, must be multiple of 2
  102. * @return updated crc sum (must be subjected to #GNUNET_CRYPTO_crc16_finish() to get actual crc16)
  103. */
  104. uint32_t
  105. GNUNET_CRYPTO_crc16_step (uint32_t sum, const void *buf, size_t len)
  106. {
  107. const uint16_t *hdr = buf;
  108. for (; len >= 2; len -= 2)
  109. sum += *(hdr++);
  110. if (len == 1)
  111. sum += (*hdr) & ntohs (0xFF00);
  112. return sum;
  113. }
  114. /**
  115. * Convert results from #GNUNET_CRYPTO_crc16_step() to final crc16.
  116. *
  117. * @param sum cummulative sum
  118. * @return crc16 value
  119. */
  120. uint16_t
  121. GNUNET_CRYPTO_crc16_finish (uint32_t sum)
  122. {
  123. sum = (sum >> 16) + (sum & 0xFFFF);
  124. sum += (sum >> 16);
  125. return ~sum;
  126. }
  127. /**
  128. * Calculate the checksum of a buffer in one step.
  129. *
  130. * @param buf buffer to calculate CRC over (must be 16-bit aligned)
  131. * @param len number of bytes in hdr, must be multiple of 2
  132. * @return crc16 value
  133. */
  134. uint16_t
  135. GNUNET_CRYPTO_crc16_n (const void *buf, size_t len)
  136. {
  137. const uint16_t *hdr = buf;
  138. uint32_t sum = GNUNET_CRYPTO_crc16_step (0, hdr, len);
  139. return GNUNET_CRYPTO_crc16_finish (sum);
  140. }
  141. /**
  142. * @ingroup hash
  143. * Calculate the checksum of a buffer in one step.
  144. *
  145. * @param buf buffer to calculate CRC over
  146. * @param len number of bytes in @a buf
  147. * @return crc8 value
  148. */
  149. uint8_t
  150. GNUNET_CRYPTO_crc8_n (const void *buf,
  151. size_t len)
  152. {
  153. const uint8_t *data = buf;
  154. unsigned int crc = 0;
  155. int i;
  156. int j;
  157. for (j = len; 0 != j; j--)
  158. {
  159. crc ^= (*data++ << 8);
  160. for (i = 8; 0 != i; i--)
  161. {
  162. if (0 != (crc & 0x8000))
  163. crc ^= (0x1070 << 3);
  164. crc <<= 1;
  165. }
  166. }
  167. return (uint8_t) (crc >> 8);
  168. }
  169. /* end of crypto_crc.c */