test-checksum.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585
  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. /* Accumulator phase of checksum */
  41. static
  42. struct acc_vals
  43. accumulate (u_char *buffer, testsz_t len, testoff_t off)
  44. {
  45. u_int8_t *p;
  46. u_int16_t *csum;
  47. int i, partial_len;
  48. struct acc_vals ret;
  49. csum = (u_int16_t *) (buffer + off);
  50. *(csum) = 0;
  51. p = buffer;
  52. ret.c0 = 0;
  53. ret.c1 = 0;
  54. while (len != 0)
  55. {
  56. partial_len = MIN(len, MODX);
  57. for (i = 0; i < partial_len; i++)
  58. {
  59. ret.c0 = ret.c0 + *(p++);
  60. ret.c1 += ret.c0;
  61. }
  62. ret.c0 = ret.c0 % 255;
  63. ret.c1 = ret.c1 % 255;
  64. len -= partial_len;
  65. }
  66. return ret;
  67. }
  68. /* The final reduction phase.
  69. * This one should be the original ospfd version
  70. */
  71. static u_int16_t
  72. reduce_ospfd (struct csum_vals *vals, testsz_t len, testoff_t off)
  73. {
  74. #define x vals->x
  75. #define y vals->y
  76. #define c0 vals->a.c0
  77. #define c1 vals->a.c1
  78. x = ((len - off - 1) * c0 - c1) % 255;
  79. if (x <= 0)
  80. x += 255;
  81. y = 510 - c0 - x;
  82. if (y > 255)
  83. y -= 255;
  84. /* take care endian issue. */
  85. return htons ((x << 8) + y);
  86. #undef x
  87. #undef y
  88. #undef c0
  89. #undef c1
  90. }
  91. /* slightly different concatenation */
  92. static u_int16_t
  93. reduce_ospfd1 (struct csum_vals *vals, testsz_t len, testoff_t off)
  94. {
  95. #define x vals->x
  96. #define y vals->y
  97. #define c0 vals->a.c0
  98. #define c1 vals->a.c1
  99. x = ((len - off - 1) * c0 - c1) % 255;
  100. if (x <= 0)
  101. x += 255;
  102. y = 510 - c0 - x;
  103. if (y > 255)
  104. y -= 255;
  105. /* take care endian issue. */
  106. return htons ((x << 8) | (y & 0xff));
  107. #undef x
  108. #undef y
  109. #undef c0
  110. #undef c1
  111. }
  112. /* original isisd version */
  113. static u_int16_t
  114. reduce_isisd (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 - 1;
  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. /* Is the -1 in y wrong perhaps? */
  141. static u_int16_t
  142. reduce_isisd_yfix (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 - c0 - c1;
  151. y = c1 - mul;
  152. if (y > 0)
  153. y++;
  154. if (x < 0)
  155. x--;
  156. x %= 255;
  157. y %= 255;
  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 yp */
  169. static u_int16_t
  170. reduce_isisd_mod (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 - c1 - c0;
  179. y = c1 - mul - 1;
  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. /* Move the mods up + fix y */
  197. static u_int16_t
  198. reduce_isisd_mody (struct csum_vals *vals, testsz_t len, testoff_t off)
  199. {
  200. #define x vals->x
  201. #define y vals->y
  202. #define c0 vals->a.c0
  203. #define c1 vals->a.c1
  204. u_int32_t mul;
  205. mul = (len - off)*(c0);
  206. x = mul - c0 - c1;
  207. y = c1 - mul;
  208. x %= 255;
  209. y %= 255;
  210. if (y > 0)
  211. y++;
  212. if (x < 0)
  213. x--;
  214. if (x == 0)
  215. x = 255;
  216. if (y == 0)
  217. y = 1;
  218. return htons ((x << 8) | (y & 0xff));
  219. #undef x
  220. #undef y
  221. #undef c0
  222. #undef c1
  223. }
  224. struct reductions_t {
  225. const char *name;
  226. u_int16_t (*f) (struct csum_vals *, testsz_t, testoff_t);
  227. } reducts[] = {
  228. { .name = "ospfd", .f = reduce_ospfd },
  229. { .name = "ospfd-1", .f = reduce_ospfd1 },
  230. { .name = "isisd", .f = reduce_isisd },
  231. { .name = "isisd-yfix", .f = reduce_isisd_yfix },
  232. { .name = "isisd-mod", .f = reduce_isisd_mod },
  233. { .name = "isisd-mody", .f = reduce_isisd_mody },
  234. { NULL, NULL },
  235. };
  236. /* The original ospfd checksum */
  237. static u_int16_t
  238. ospfd_checksum (u_char *buffer, testsz_t len, testoff_t off)
  239. {
  240. u_char *sp, *ep, *p, *q;
  241. int c0 = 0, c1 = 0;
  242. int x, y;
  243. u_int16_t checksum, *csum;
  244. csum = (u_int16_t *) (buffer + off);
  245. *(csum) = 0;
  246. sp = buffer;
  247. for (ep = sp + len; sp < ep; sp = q)
  248. {
  249. q = sp + MODX;
  250. if (q > ep)
  251. q = ep;
  252. for (p = sp; p < q; p++)
  253. {
  254. c0 += *p;
  255. c1 += c0;
  256. }
  257. c0 %= 255;
  258. c1 %= 255;
  259. }
  260. ospfd_vals.a.c0 = c0;
  261. ospfd_vals.a.c1 = c1;
  262. //printf ("%s: len %u, off %u, c0 %d, c1 %d\n",
  263. // __func__, len, off, c0, c1);
  264. x = ((int)(len - off - 1) * (int)c0 - (int)c1) % 255;
  265. if (x <= 0)
  266. x += 255;
  267. y = 510 - c0 - x;
  268. if (y > 255)
  269. y -= 255;
  270. ospfd_vals.x = x;
  271. ospfd_vals.y = y;
  272. buffer[off] = x;
  273. buffer[off + 1] = y;
  274. /* take care endian issue. */
  275. checksum = htons ((x << 8) | (y & 0xff));
  276. return (checksum);
  277. }
  278. /* the original, broken isisd checksum */
  279. static u_int16_t
  280. iso_csum_create (u_char * buffer, testsz_t len, testoff_t off)
  281. {
  282. u_int8_t *p;
  283. int x;
  284. int y;
  285. u_int32_t mul;
  286. u_int32_t c0;
  287. u_int32_t c1;
  288. u_int16_t checksum, *csum;
  289. int i, init_len, partial_len;
  290. checksum = 0;
  291. csum = (u_int16_t *) (buffer + off);
  292. *(csum) = checksum;
  293. p = buffer;
  294. c0 = 0;
  295. c1 = 0;
  296. init_len = len;
  297. while (len != 0)
  298. {
  299. partial_len = MIN(len, MODX);
  300. for (i = 0; i < partial_len; i++)
  301. {
  302. c0 = c0 + *(p++);
  303. c1 += c0;
  304. }
  305. c0 = c0 % 255;
  306. c1 = c1 % 255;
  307. len -= partial_len;
  308. }
  309. isisd_vals.a.c0 = c0;
  310. isisd_vals.a.c1 = c1;
  311. mul = (init_len - off) * c0;
  312. x = mul - c1 - c0;
  313. y = c1 - mul - 1;
  314. if (y > 0)
  315. y++;
  316. if (x < 0)
  317. x--;
  318. x %= 255;
  319. y %= 255;
  320. if (x == 0)
  321. x = 255;
  322. if (y == 0)
  323. y = 1;
  324. isisd_vals.x = x;
  325. isisd_vals.y = y;
  326. checksum = htons((x << 8) | (y & 0xFF));
  327. *(csum) = checksum;
  328. /* return the checksum for user usage */
  329. return checksum;
  330. }
  331. static int
  332. verify (u_char * buffer, testsz_t len)
  333. {
  334. u_int8_t *p;
  335. u_int32_t c0;
  336. u_int32_t c1;
  337. int i, partial_len;
  338. p = buffer;
  339. c0 = 0;
  340. c1 = 0;
  341. while (len)
  342. {
  343. partial_len = MIN(len, 5803);
  344. for (i = 0; i < partial_len; i++)
  345. {
  346. c0 = c0 + *(p++);
  347. c1 += c0;
  348. }
  349. c0 = c0 % 255;
  350. c1 = c1 % 255;
  351. len -= partial_len;
  352. }
  353. if (c0 == 0 && c1 == 0)
  354. return 0;
  355. return 1;
  356. }
  357. static int /* return checksum in low-order 16 bits */
  358. in_cksum_optimized(void *parg, int nbytes)
  359. {
  360. u_short *ptr = parg;
  361. register long sum; /* assumes long == 32 bits */
  362. register u_short answer; /* assumes u_short == 16 bits */
  363. register int count;
  364. /*
  365. * Our algorithm is simple, using a 32-bit accumulator (sum),
  366. * we add sequential 16-bit words to it, and at the end, fold back
  367. * all the carry bits from the top 16 bits into the lower 16 bits.
  368. */
  369. sum = 0;
  370. count = nbytes >> 1; /* div by 2 */
  371. for(ptr--; count; --count)
  372. sum += *++ptr;
  373. if (nbytes & 1) /* Odd */
  374. sum += *(u_char *)(++ptr); /* one byte only */
  375. /*
  376. * Add back carry outs from top 16 bits to low 16 bits.
  377. */
  378. sum = (sum >> 16) + (sum & 0xffff); /* add high-16 to low-16 */
  379. sum += (sum >> 16); /* add carry */
  380. answer = ~sum; /* ones-complement, then truncate to 16 bits */
  381. return(answer);
  382. }
  383. static int /* return checksum in low-order 16 bits */
  384. in_cksum_rfc(void *parg, int count)
  385. /* from RFC 1071 */
  386. {
  387. u_short *addr = parg;
  388. /* Compute Internet Checksum for "count" bytes
  389. * beginning at location "addr".
  390. */
  391. register long sum = 0;
  392. while (count > 1) {
  393. /* This is the inner loop */
  394. sum += *addr++;
  395. count -= 2;
  396. }
  397. /* Add left-over byte, if any */
  398. if (count > 0) {
  399. sum += *(u_char *)addr;
  400. }
  401. /* Fold 32-bit sum to 16 bits */
  402. while (sum>>16)
  403. sum = (sum & 0xffff) + (sum >> 16);
  404. return ~sum;
  405. }
  406. int
  407. main(int argc, char **argv)
  408. {
  409. /* 60017 65629 702179 */
  410. #define MAXDATALEN 60017
  411. #define BUFSIZE MAXDATALEN + sizeof(u_int16_t)
  412. u_char buffer[BUFSIZE];
  413. int exercise = 0;
  414. #define EXERCISESTEP 257
  415. srandom (time (NULL));
  416. while (1) {
  417. u_int16_t ospfd, isisd, lib, in_csum, in_csum_res, in_csum_rfc;
  418. int i,j;
  419. exercise += EXERCISESTEP;
  420. exercise %= MAXDATALEN;
  421. for (i = 0; i < exercise; i += sizeof (long int)) {
  422. long int rand = random ();
  423. for (j = sizeof (long int); j > 0; j--)
  424. buffer[i + (sizeof (long int) - j)] = (rand >> (j * 8)) & 0xff;
  425. }
  426. in_csum = in_cksum(buffer, exercise);
  427. in_csum_res = in_cksum_optimized(buffer, exercise);
  428. in_csum_rfc = in_cksum_rfc(buffer, exercise);
  429. if (in_csum_res != in_csum || in_csum != in_csum_rfc)
  430. printf ("verify: in_chksum failed in_csum:%x, in_csum_res:%x,"
  431. "in_csum_rfc %x, len:%d\n",
  432. in_csum, in_csum_res, in_csum_rfc, exercise);
  433. ospfd = ospfd_checksum (buffer, exercise + sizeof(u_int16_t), exercise);
  434. if (verify (buffer, exercise + sizeof(u_int16_t)))
  435. printf ("verify: ospfd failed\n");
  436. isisd = iso_csum_create (buffer, exercise + sizeof(u_int16_t), exercise);
  437. if (verify (buffer, exercise + sizeof(u_int16_t)))
  438. printf ("verify: isisd failed\n");
  439. lib = fletcher_checksum (buffer, exercise + sizeof(u_int16_t), exercise);
  440. if (verify (buffer, exercise + sizeof(u_int16_t)))
  441. printf ("verify: lib failed\n");
  442. if (ospfd != lib) {
  443. printf ("Mismatch in values at size %u\n"
  444. "ospfd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
  445. "isisd: 0x%04x\tc0: %d\tc1: %d\tx: %d\ty: %d\n"
  446. "lib: 0x%04x\n",
  447. exercise,
  448. ospfd, ospfd_vals.a.c0, ospfd_vals.a.c1, ospfd_vals.x, ospfd_vals.y,
  449. isisd, isisd_vals.a.c0, isisd_vals.a.c1, isisd_vals.x, isisd_vals.y,
  450. lib
  451. );
  452. /* Investigate reduction phase discrepencies */
  453. if (ospfd_vals.a.c0 == isisd_vals.a.c0
  454. && ospfd_vals.a.c1 == isisd_vals.a.c1) {
  455. printf ("\n");
  456. for (i = 0; reducts[i].name != NULL; i++) {
  457. ospfd = reducts[i].f (&ospfd_vals,
  458. exercise + sizeof (u_int16_t),
  459. exercise);
  460. printf ("%20s: x: %02x, y %02x, checksum 0x%04x\n",
  461. reducts[i].name, ospfd_vals.x & 0xff, ospfd_vals.y & 0xff, ospfd);
  462. }
  463. }
  464. printf ("\n u_char testdata [] = {\n ");
  465. for (i = 0; i < exercise; i++) {
  466. printf ("0x%02x,%s",
  467. buffer[i],
  468. (i + 1) % 8 ? " " : "\n ");
  469. }
  470. printf ("\n}\n");
  471. exit (1);
  472. }
  473. }
  474. }