test-checksum.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550
  1. /*
  2. * Copyright (C) 2008 Sun Microsystems, Inc.
  3. *
  4. * This file is part of Quagga.
  5. *
  6. * Quagga is free software; you can redistribute it and/or modify it
  7. * under the terms of the GNU General Public License as published by the
  8. * Free Software Foundation; either version 2, or (at your option) any
  9. * later version.
  10. *
  11. * Quagga is distributed in the hope that it will be useful, but
  12. * WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14. * General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with Quagga; see the file COPYING. If not, write to the Free
  18. * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19. * 02111-1307, USA.
  20. */
  21. #include <zebra.h>
  22. #include <stdlib.h>
  23. #include <time.h>
  24. #include "checksum.h"
  25. struct thread_master *master;
  26. struct acc_vals {
  27. int c0;
  28. int c1;
  29. };
  30. struct csum_vals {
  31. struct acc_vals a;
  32. int x;
  33. int y;
  34. };
  35. static struct csum_vals ospfd_vals, isisd_vals;
  36. typedef size_t testsz_t;
  37. typedef uint16_t testoff_t;
  38. /* Fletcher Checksum -- Refer to RFC1008. */
  39. #define MODX 4102
  40. /* The final reduction phase.
  41. * This one should be the original ospfd version
  42. */
  43. static u_int16_t
  44. reduce_ospfd (struct csum_vals *vals, testsz_t len, testoff_t off)
  45. {
  46. #define x vals->x
  47. #define y vals->y
  48. #define c0 vals->a.c0
  49. #define c1 vals->a.c1
  50. x = ((len - off - 1) * c0 - c1) % 255;
  51. if (x <= 0)
  52. x += 255;
  53. y = 510 - c0 - x;
  54. if (y > 255)
  55. y -= 255;
  56. /* take care endian issue. */
  57. return htons ((x << 8) + y);
  58. #undef x
  59. #undef y
  60. #undef c0
  61. #undef c1
  62. }
  63. /* slightly different concatenation */
  64. static u_int16_t
  65. reduce_ospfd1 (struct csum_vals *vals, testsz_t len, testoff_t off)
  66. {
  67. #define x vals->x
  68. #define y vals->y
  69. #define c0 vals->a.c0
  70. #define c1 vals->a.c1
  71. x = ((len - off - 1) * c0 - c1) % 255;
  72. if (x <= 0)
  73. x += 255;
  74. y = 510 - c0 - x;
  75. if (y > 255)
  76. y -= 255;
  77. /* take care endian issue. */
  78. return htons ((x << 8) | (y & 0xff));
  79. #undef x
  80. #undef y
  81. #undef c0
  82. #undef c1
  83. }
  84. /* original isisd version */
  85. static u_int16_t
  86. reduce_isisd (struct csum_vals *vals, testsz_t len, testoff_t off)
  87. {
  88. #define x vals->x
  89. #define y vals->y
  90. #define c0 vals->a.c0
  91. #define c1 vals->a.c1
  92. u_int32_t mul;
  93. mul = (len - off)*(c0);
  94. x = mul - c0 - c1;
  95. y = c1 - mul - 1;
  96. if (y > 0)
  97. y++;
  98. if (x < 0)
  99. x--;
  100. x %= 255;
  101. y %= 255;
  102. if (x == 0)
  103. x = 255;
  104. if (y == 0)
  105. y = 1;
  106. return htons ((x << 8) | (y & 0xff));
  107. #undef x
  108. #undef y
  109. #undef c0
  110. #undef c1
  111. }
  112. /* Is the -1 in y wrong perhaps? */
  113. static u_int16_t
  114. reduce_isisd_yfix (struct csum_vals *vals, testsz_t len, testoff_t off)
  115. {
  116. #define x vals->x
  117. #define y vals->y
  118. #define c0 vals->a.c0
  119. #define c1 vals->a.c1
  120. u_int32_t mul;
  121. mul = (len - off)*(c0);
  122. x = mul - c0 - c1;
  123. y = c1 - mul;
  124. if (y > 0)
  125. y++;
  126. if (x < 0)
  127. x--;
  128. x %= 255;
  129. y %= 255;
  130. if (x == 0)
  131. x = 255;
  132. if (y == 0)
  133. y = 1;
  134. return htons ((x << 8) | (y & 0xff));
  135. #undef x
  136. #undef y
  137. #undef c0
  138. #undef c1
  139. }
  140. /* Move the mods yp */
  141. static u_int16_t
  142. reduce_isisd_mod (struct csum_vals *vals, testsz_t len, testoff_t off)
  143. {
  144. #define x vals->x
  145. #define y vals->y
  146. #define c0 vals->a.c0
  147. #define c1 vals->a.c1
  148. u_int32_t mul;
  149. mul = (len - off)*(c0);
  150. x = mul - c1 - c0;
  151. y = c1 - mul - 1;
  152. x %= 255;
  153. y %= 255;
  154. if (y > 0)
  155. y++;
  156. if (x < 0)
  157. x--;
  158. if (x == 0)
  159. x = 255;
  160. if (y == 0)
  161. y = 1;
  162. return htons ((x << 8) | (y & 0xff));
  163. #undef x
  164. #undef y
  165. #undef c0
  166. #undef c1
  167. }
  168. /* Move the mods up + fix y */
  169. static u_int16_t
  170. reduce_isisd_mody (struct csum_vals *vals, testsz_t len, testoff_t off)
  171. {
  172. #define x vals->x
  173. #define y vals->y
  174. #define c0 vals->a.c0
  175. #define c1 vals->a.c1
  176. u_int32_t mul;
  177. mul = (len - off)*(c0);
  178. x = mul - c0 - c1;
  179. y = c1 - mul;
  180. x %= 255;
  181. y %= 255;
  182. if (y > 0)
  183. y++;
  184. if (x < 0)
  185. x--;
  186. if (x == 0)
  187. x = 255;
  188. if (y == 0)
  189. y = 1;
  190. return htons ((x << 8) | (y & 0xff));
  191. #undef x
  192. #undef y
  193. #undef c0
  194. #undef c1
  195. }
  196. struct reductions_t {
  197. const char *name;
  198. u_int16_t (*f) (struct csum_vals *, testsz_t, testoff_t);
  199. } reducts[] = {
  200. { .name = "ospfd", .f = reduce_ospfd },
  201. { .name = "ospfd-1", .f = reduce_ospfd1 },
  202. { .name = "isisd", .f = reduce_isisd },
  203. { .name = "isisd-yfix", .f = reduce_isisd_yfix },
  204. { .name = "isisd-mod", .f = reduce_isisd_mod },
  205. { .name = "isisd-mody", .f = reduce_isisd_mody },
  206. { NULL, NULL },
  207. };
  208. /* The original ospfd checksum */
  209. static u_int16_t
  210. ospfd_checksum (u_char *buffer, testsz_t len, testoff_t off)
  211. {
  212. u_char *sp, *ep, *p, *q;
  213. int c0 = 0, c1 = 0;
  214. int x, y;
  215. u_int16_t checksum, *csum;
  216. csum = (u_int16_t *) (buffer + off);
  217. *(csum) = 0;
  218. sp = buffer;
  219. for (ep = sp + len; sp < ep; sp = q)
  220. {
  221. q = sp + MODX;
  222. if (q > ep)
  223. q = ep;
  224. for (p = sp; p < q; p++)
  225. {
  226. c0 += *p;
  227. c1 += c0;
  228. }
  229. c0 %= 255;
  230. c1 %= 255;
  231. }
  232. ospfd_vals.a.c0 = c0;
  233. ospfd_vals.a.c1 = c1;
  234. //printf ("%s: len %u, off %u, c0 %d, c1 %d\n",
  235. // __func__, len, off, c0, c1);
  236. x = ((int)(len - off - 1) * (int)c0 - (int)c1) % 255;
  237. if (x <= 0)
  238. x += 255;
  239. y = 510 - c0 - x;
  240. if (y > 255)
  241. y -= 255;
  242. ospfd_vals.x = x;
  243. ospfd_vals.y = y;
  244. buffer[off] = x;
  245. buffer[off + 1] = y;
  246. /* take care endian issue. */
  247. checksum = htons ((x << 8) | (y & 0xff));
  248. return (checksum);
  249. }
  250. /* the original, broken isisd checksum */
  251. static u_int16_t
  252. iso_csum_create (u_char * buffer, testsz_t len, testoff_t off)
  253. {
  254. u_int8_t *p;
  255. int x;
  256. int y;
  257. u_int32_t mul;
  258. u_int32_t c0;
  259. u_int32_t c1;
  260. u_int16_t checksum, *csum;
  261. int i, init_len, partial_len;
  262. checksum = 0;
  263. csum = (u_int16_t *) (buffer + off);
  264. *(csum) = checksum;
  265. p = buffer;
  266. c0 = 0;
  267. c1 = 0;
  268. init_len = len;
  269. while (len != 0)
  270. {
  271. partial_len = MIN(len, MODX);
  272. for (i = 0; i < partial_len; i++)
  273. {
  274. c0 = c0 + *(p++);
  275. c1 += c0;
  276. }
  277. c0 = c0 % 255;
  278. c1 = c1 % 255;
  279. len -= partial_len;
  280. }
  281. isisd_vals.a.c0 = c0;
  282. isisd_vals.a.c1 = c1;
  283. mul = (init_len - off) * c0;
  284. x = mul - c1 - c0;
  285. y = c1 - mul - 1;
  286. if (y > 0)
  287. y++;
  288. if (x < 0)
  289. x--;
  290. x %= 255;
  291. y %= 255;
  292. if (x == 0)
  293. x = 255;
  294. if (y == 0)
  295. y = 1;
  296. isisd_vals.x = x;
  297. isisd_vals.y = y;
  298. checksum = htons((x << 8) | (y & 0xFF));
  299. *(csum) = checksum;
  300. /* return the checksum for user usage */
  301. return checksum;
  302. }
  303. static int
  304. verify (u_char * buffer, testsz_t len)
  305. {
  306. u_int8_t *p;
  307. u_int32_t c0;
  308. u_int32_t c1;
  309. int i, partial_len;
  310. p = buffer;
  311. c0 = 0;
  312. c1 = 0;
  313. while (len)
  314. {
  315. partial_len = MIN(len, 5803);
  316. for (i = 0; i < partial_len; i++)
  317. {
  318. c0 = c0 + *(p++);
  319. c1 += c0;
  320. }
  321. c0 = c0 % 255;
  322. c1 = c1 % 255;
  323. len -= partial_len;
  324. }
  325. if (c0 == 0 && c1 == 0)
  326. return 0;
  327. return 1;
  328. }
  329. static int /* return checksum in low-order 16 bits */
  330. in_cksum_optimized(void *parg, int nbytes)
  331. {
  332. u_short *ptr = parg;
  333. register long sum; /* assumes long == 32 bits */
  334. register u_short answer; /* assumes u_short == 16 bits */
  335. register int count;
  336. /*
  337. * Our algorithm is simple, using a 32-bit accumulator (sum),
  338. * we add sequential 16-bit words to it, and at the end, fold back
  339. * all the carry bits from the top 16 bits into the lower 16 bits.
  340. */
  341. sum = 0;
  342. count = nbytes >> 1; /* div by 2 */
  343. for(ptr--; count; --count)
  344. sum += *++ptr;
  345. if (nbytes & 1) /* Odd */
  346. sum += *(u_char *)(++ptr); /* one byte only */
  347. /*
  348. * Add back carry outs from top 16 bits to low 16 bits.
  349. */
  350. sum = (sum >> 16) + (sum & 0xffff); /* add high-16 to low-16 */
  351. sum += (sum >> 16); /* add carry */
  352. answer = ~sum; /* ones-complement, then truncate to 16 bits */
  353. return(answer);
  354. }
  355. static int /* return checksum in low-order 16 bits */
  356. in_cksum_rfc(void *parg, int count)
  357. /* from RFC 1071 */
  358. {
  359. u_short *addr = parg;
  360. /* Compute Internet Checksum for "count" bytes
  361. * beginning at location "addr".
  362. */
  363. register long sum = 0;
  364. while (count > 1) {
  365. /* This is the inner loop */
  366. sum += *addr++;
  367. count -= 2;
  368. }
  369. /* Add left-over byte, if any */
  370. if (count > 0) {
  371. sum += *(u_char *)addr;
  372. }
  373. /* Fold 32-bit sum to 16 bits */
  374. while (sum>>16)
  375. sum = (sum & 0xffff) + (sum >> 16);
  376. return ~sum;
  377. }
  378. int
  379. main(int argc, char **argv)
  380. {
  381. /* 60017 65629 702179 */
  382. #define MAXDATALEN 60017
  383. #define BUFSIZE MAXDATALEN + sizeof(u_int16_t)
  384. u_char buffer[BUFSIZE];
  385. int exercise = 0;
  386. #define EXERCISESTEP 257
  387. srandom (time (NULL));
  388. while (1) {
  389. u_int16_t ospfd, isisd, lib, in_csum, in_csum_res, in_csum_rfc;
  390. int i,j;
  391. exercise += EXERCISESTEP;
  392. exercise %= MAXDATALEN;
  393. for (i = 0; i < exercise; i += sizeof (long int)) {
  394. long int rand = random ();
  395. for (j = sizeof (long int); j > 0; j--)
  396. buffer[i + (sizeof (long int) - j)] = (rand >> (j * 8)) & 0xff;
  397. }
  398. in_csum = in_cksum(buffer, exercise);
  399. in_csum_res = in_cksum_optimized(buffer, exercise);
  400. in_csum_rfc = in_cksum_rfc(buffer, exercise);
  401. if (in_csum_res != in_csum || in_csum != in_csum_rfc)
  402. printf ("verify: in_chksum failed in_csum:%x, in_csum_res:%x,"
  403. "in_csum_rfc %x, len:%d\n",
  404. in_csum, in_csum_res, in_csum_rfc, exercise);
  405. ospfd = ospfd_checksum (buffer, exercise + sizeof(u_int16_t), exercise);
  406. if (verify (buffer, exercise + sizeof(u_int16_t)))
  407. printf ("verify: ospfd failed\n");
  408. isisd = iso_csum_create (buffer, exercise + sizeof(u_int16_t), exercise);
  409. if (verify (buffer, exercise + sizeof(u_int16_t)))
  410. printf ("verify: isisd failed\n");
  411. lib = fletcher_checksum (buffer, exercise + sizeof(u_int16_t), exercise);
  412. if (verify (buffer, exercise + sizeof(u_int16_t)))
  413. printf ("verify: lib failed\n");
  414. if (ospfd != lib) {
  415. printf ("Mismatch in values at size %u\n"
  416. "ospfd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
  417. "isisd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
  418. "lib: 0x%04x\n",
  419. exercise,
  420. ospfd, ospfd_vals.a.c0, ospfd_vals.a.c1, ospfd_vals.x, ospfd_vals.y,
  421. isisd, isisd_vals.a.c0, isisd_vals.a.c1, isisd_vals.x, isisd_vals.y,
  422. lib
  423. );
  424. /* Investigate reduction phase discrepencies */
  425. if (ospfd_vals.a.c0 == isisd_vals.a.c0
  426. && ospfd_vals.a.c1 == isisd_vals.a.c1) {
  427. printf ("\n");
  428. for (i = 0; reducts[i].name != NULL; i++) {
  429. ospfd = reducts[i].f (&ospfd_vals,
  430. exercise + sizeof (u_int16_t),
  431. exercise);
  432. printf ("%20s: x: %02x, y %02x, checksum 0x%04x\n",
  433. reducts[i].name, ospfd_vals.x & 0xff, ospfd_vals.y & 0xff, ospfd);
  434. }
  435. }
  436. printf ("\n u_char testdata [] = {\n ");
  437. for (i = 0; i < exercise; i++) {
  438. printf ("0x%02x,%s",
  439. buffer[i],
  440. (i + 1) % 8 ? " " : "\n ");
  441. }
  442. printf ("\n}\n");
  443. exit (1);
  444. }
  445. }
  446. }