test-checksum.c 11 KB

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