tests/test-csum.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011 Nicira, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "csum.h"
  19 #include <inttypes.h>
  20 #include <netinet/in.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include "random.h"
  25 #include "unaligned.h"
  26 #include "util.h"
  27
  28 #undef NDEBUG
  29 #include <assert.h>
  30
  31 struct test_case {
  32     char *data;
  33     size_t size;                /* Test requires a multiple of 4. */
  34     uint16_t csum;
  35 };
  36
  37 #define TEST_CASE(DATA, CSUM) { DATA, (sizeof DATA) - 1, CSUM }
  38
  39 static const struct test_case test_cases[] = {
  40     /* RFC 1071 section 3. */
  41     TEST_CASE("\x00\x01\xf2\x03"
  42               "\xf4\xf5\xf6\xf7",
  43               0xffff - 0xddf2 /* ~0xddf2 */),
  44
  45     /* http://www.sbprojects.com/projects/tcpip/theory/theory14.htm */
  46     TEST_CASE("\x45\x00\x00\x28"
  47               "\x1F\xFD\x40\x00"
  48               "\x80\x06\x00\x00"
  49               "\xC0\xA8\x3B\x0A"
  50               "\xC0\xA8\x3B\x32",
  51               0xe345),
  52
  53     /* http://mathforum.org/library/drmath/view/54379.html */
  54     TEST_CASE("\x86\x5e\xac\x60"
  55               "\x71\x2a\x81\xb5",
  56               0xda60),
  57 };
  58
  59 static void
  60 mark(char c)
  61 {
  62     putchar(c);
  63     fflush(stdout);
  64 }
  65
  66 #if 0
  67 /* This code is useful for generating new test cases for RFC 1624 section 4. */
  68 static void
  69 generate_rfc1624_test_case(void)
  70 {
  71     int i;
  72
  73     for (i = 0; i < 10000000; i++) {
  74         uint32_t data[8];
  75         int j;
  76
  77         for (j = 0; j < 8; j++) {
  78             data[j] = random_uint32();
  79         }
  80         data[7] &= 0x0000ffff;
  81         data[7] |= 0x55550000;
  82         if (ntohs(~csum(data, sizeof data - 2)) == 0xcd7a) {
  83             ovs_hex_dump(stdout, data, sizeof data, 0, false);
  84             exit(0);
  85         }
  86     }
  87 }
  88 #endif
  89
  90
  91
  92 /* Make sure we get the calculation in RFC 1624 section 4 correct. */
  93 static void
  94 test_rfc1624(void)
  95 {
  96     /* "...an IP packet header in which a 16-bit field m = 0x5555..." */
  97     uint8_t data[32] = {
  98         0xfe, 0x8f, 0xc1, 0x14, 0x4b, 0x6f, 0x70, 0x2a,
  99         0x80, 0x29, 0x78, 0xc0, 0x58, 0x81, 0x77, 0xaa,
 100         0x66, 0x64, 0xfc, 0x96, 0x63, 0x97, 0x64, 0xee,
 101         0x12, 0x53, 0x1d, 0xa9, 0x2d, 0xa9, 0x55, 0x55
 102     };
 103
 104     /* "...the one's complement sum of all other header octets is 0xCD7A." */
 105     assert(ntohs(csum(data, sizeof data - 2)) == 0xffff - 0xcd7a);
 106
 107     /* "...the header checksum would be:
 108
 109           HC = ~(0xCD7A + 0x5555)
 110              = ~0x22D0
 111              =  0xDD2F"
 112     */
 113     assert(ntohs(csum(data, sizeof data)) == 0xdd2f);
 114
 115     /* "a 16-bit field m = 0x5555 changes to m' = 0x3285..." */
 116     data[30] = 0x32;
 117     data[31] = 0x85;
 118
 119     /* "The new checksum via recomputation is:
 120
 121           HC' = ~(0xCD7A + 0x3285)
 122               = ~0xFFFF
 123               =  0x0000"
 124     */
 125     assert(ntohs(csum(data, sizeof data)) == 0x0000);
 126
 127     /* "Applying [Eqn. 3] to the example above, we get the correct result:
 128
 129           HC' = ~(C + (-m) + m')
 130               = ~(0x22D0 + ~0x5555 + 0x3285)
 131               = ~0xFFFF
 132               =  0x0000" */
 133     assert(recalc_csum16(htons(0xdd2f), htons(0x5555), htons(0x3285))
 134            == htons(0x0000));
 135
 136     mark('#');
 137 }
 138
 139 int
 140 main(void)
 141 {
 142     const struct test_case *tc;
 143     int i;
 144
 145     for (tc = test_cases; tc < &test_cases[ARRAY_SIZE(test_cases)]; tc++) {
 146         const void *data = tc->data;
 147         const ovs_be16 *data16 = (OVS_FORCE const ovs_be16 *) data;
 148         const ovs_be32 *data32 = (OVS_FORCE const ovs_be32 *) data;
 149         uint32_t partial;
 150
 151         /* Test csum(). */
 152         assert(ntohs(csum(tc->data, tc->size)) == tc->csum);
 153         mark('.');
 154
 155         /* Test csum_add16(). */
 156         partial = 0;
 157         for (i = 0; i < tc->size / 2; i++) {
 158             partial = csum_add16(partial, get_unaligned_be16(&data16[i]));
 159         }
 160         assert(ntohs(csum_finish(partial)) == tc->csum);
 161         mark('.');
 162
 163         /* Test csum_add32(). */
 164         partial = 0;
 165         for (i = 0; i < tc->size / 4; i++) {
 166             partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 167         }
 168         assert(ntohs(csum_finish(partial)) == tc->csum);
 169         mark('.');
 170
 171         /* Test alternating csum_add16() and csum_add32(). */
 172         partial = 0;
 173         for (i = 0; i < tc->size / 4; i++) {
 174             if (i % 2) {
 175                 partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 176             } else {
 177                 ovs_be16 u0 = get_unaligned_be16(&data16[i * 2]);
 178                 ovs_be16 u1 = get_unaligned_be16(&data16[i * 2 + 1]);
 179                 partial = csum_add16(partial, u0);
 180                 partial = csum_add16(partial, u1);
 181             }
 182         }
 183         assert(ntohs(csum_finish(partial)) == tc->csum);
 184         mark('.');
 185
 186         /* Test csum_continue(). */
 187         partial = 0;
 188         for (i = 0; i < tc->size / 4; i++) {
 189             if (i) {
 190                 partial = csum_continue(partial, &data32[i], 4);
 191             } else {
 192                 partial = csum_continue(partial, &data16[i * 2], 2);
 193                 partial = csum_continue(partial, &data16[i * 2 + 1], 2);
 194             }
 195         }
 196         assert(ntohs(csum_finish(partial)) == tc->csum);
 197         mark('#');
 198     }
 199
 200     test_rfc1624();
 201
 202     /* Test recalc_csum16(). */
 203     for (i = 0; i < 32; i++) {
 204         ovs_be16 old_u16, new_u16;
 205         ovs_be16 old_csum;
 206         ovs_be16 data[16];
 207         int j, index;
 208
 209         for (j = 0; j < ARRAY_SIZE(data); j++) {
 210             data[j] = (OVS_FORCE ovs_be16) random_uint32();
 211         }
 212         old_csum = csum(data, sizeof data);
 213         index = random_range(ARRAY_SIZE(data));
 214         old_u16 = data[index];
 215         new_u16 = data[index] = (OVS_FORCE ovs_be16) random_uint32();
 216         assert(csum(data, sizeof data)
 217                == recalc_csum16(old_csum, old_u16, new_u16));
 218         mark('.');
 219     }
 220     mark('#');
 221
 222     /* Test recalc_csum32(). */
 223     for (i = 0; i < 32; i++) {
 224         ovs_be32 old_u32, new_u32;
 225         ovs_be16 old_csum;
 226         ovs_be32 data[16];
 227         int j, index;
 228
 229         for (j = 0; j < ARRAY_SIZE(data); j++) {
 230             data[j] = (OVS_FORCE ovs_be32) random_uint32();
 231         }
 232         old_csum = csum(data, sizeof data);
 233         index = random_range(ARRAY_SIZE(data));
 234         old_u32 = data[index];
 235         new_u32 = data[index] = (OVS_FORCE ovs_be32) random_uint32();
 236         assert(csum(data, sizeof data)
 237                == recalc_csum32(old_csum, old_u32, new_u32));
 238         mark('.');
 239     }
 240     mark('#');
 241
 242     putchar('\n');
 243
 244     return 0;
 245 }