tests/test-csum.c

   1 /*
   2  * Copyright (c) 2009, 2010, 2011, 2014 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 #undef NDEBUG
  19 #include "csum.h"
  20 #include <assert.h>
  21 #include <inttypes.h>
  22 #include <netinet/in.h>
  23 #include <netinet/ip.h>
  24 #include <netinet/ip6.h>
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include "crc32c.h"
  29 #include "ovstest.h"
  30 #include "packets.h"
  31 #include "random.h"
  32 #include "unaligned.h"
  33 #include "util.h"
  34
  35 struct test_case {
  36     char *data;
  37     size_t size;                /* Test requires a multiple of 4. */
  38     uint16_t csum;
  39 };
  40
  41 #define TEST_CASE(DATA, CSUM) { DATA, (sizeof DATA) - 1, CSUM }
  42
  43 static const struct test_case test_cases[] = {
  44     /* RFC 1071 section 3. */
  45     TEST_CASE("\x00\x01\xf2\x03"
  46               "\xf4\xf5\xf6\xf7",
  47               0xffff - 0xddf2 /* ~0xddf2 */),
  48
  49     /* http://www.sbprojects.com/projects/tcpip/theory/theory14.htm */
  50     TEST_CASE("\x45\x00\x00\x28"
  51               "\x1F\xFD\x40\x00"
  52               "\x80\x06\x00\x00"
  53               "\xC0\xA8\x3B\x0A"
  54               "\xC0\xA8\x3B\x32",
  55               0xe345),
  56
  57     /* http://mathforum.org/library/drmath/view/54379.html */
  58     TEST_CASE("\x86\x5e\xac\x60"
  59               "\x71\x2a\x81\xb5",
  60               0xda60),
  61 };
  62
  63 static void
  64 mark(char c)
  65 {
  66     putchar(c);
  67     fflush(stdout);
  68 }
  69
  70 #if 0
  71 /* This code is useful for generating new test cases for RFC 1624 section 4. */
  72 static void
  73 generate_rfc1624_test_case(void)
  74 {
  75     int i;
  76
  77     for (i = 0; i < 10000000; i++) {
  78         uint32_t data[8];
  79         int j;
  80
  81         for (j = 0; j < 8; j++) {
  82             data[j] = random_uint32();
  83         }
  84         data[7] &= 0x0000ffff;
  85         data[7] |= 0x55550000;
  86         if (ntohs(~csum(data, sizeof data - 2)) == 0xcd7a) {
  87             ovs_hex_dump(stdout, data, sizeof data, 0, false);
  88             exit(0);
  89         }
  90     }
  91 }
  92 #endif
  93
  94
  95
  96 /* Make sure we get the calculation in RFC 1624 section 4 correct. */
  97 static void
  98 test_rfc1624(void)
  99 {
 100     /* "...an IP packet header in which a 16-bit field m = 0x5555..." */
 101     uint8_t data[32] = {
 102         0xfe, 0x8f, 0xc1, 0x14, 0x4b, 0x6f, 0x70, 0x2a,
 103         0x80, 0x29, 0x78, 0xc0, 0x58, 0x81, 0x77, 0xaa,
 104         0x66, 0x64, 0xfc, 0x96, 0x63, 0x97, 0x64, 0xee,
 105         0x12, 0x53, 0x1d, 0xa9, 0x2d, 0xa9, 0x55, 0x55
 106     };
 107
 108     /* "...the one's complement sum of all other header octets is 0xCD7A." */
 109     assert(ntohs(csum(data, sizeof data - 2)) == 0xffff - 0xcd7a);
 110
 111     /* "...the header checksum would be:
 112
 113           HC = ~(0xCD7A + 0x5555)
 114              = ~0x22D0
 115              =  0xDD2F"
 116     */
 117     assert(ntohs(csum(data, sizeof data)) == 0xdd2f);
 118
 119     /* "a 16-bit field m = 0x5555 changes to m' = 0x3285..." */
 120     data[30] = 0x32;
 121     data[31] = 0x85;
 122
 123     /* "The new checksum via recomputation is:
 124
 125           HC' = ~(0xCD7A + 0x3285)
 126               = ~0xFFFF
 127               =  0x0000"
 128     */
 129     assert(ntohs(csum(data, sizeof data)) == 0x0000);
 130
 131     /* "Applying [Eqn. 3] to the example above, we get the correct result:
 132
 133           HC' = ~(C + (-m) + m')
 134               = ~(0x22D0 + ~0x5555 + 0x3285)
 135               = ~0xFFFF
 136               =  0x0000" */
 137     assert(recalc_csum16(htons(0xdd2f), htons(0x5555), htons(0x3285))
 138            == htons(0x0000));
 139
 140     mark('#');
 141 }
 142
 143 /* CRC32C checksum tests, based on Intel IPPs, Chapter 13,
 144  * ippsCRC32C_8u() example, found at the following location:
 145  * http://software.intel.com/sites/products/documentation/hpc/ipp/ipps/ */
 146 static void
 147 test_crc32c(void)
 148 {
 149     int i;
 150     uint8_t data[48] = {
 151         0x01, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 152         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 153         0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00,
 154         0x00, 0x00, 0x00, 0x14, 0x00, 0x00, 0x00, 0x18,
 155         0x28, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
 156         0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
 157     };
 158
 159     /* iSCSI Read PDU */
 160     assert(ntohl(crc32c(data, 48)) == 0x563a96d9L);
 161
 162     /* 32 bytes of all zeroes */
 163     for (i = 0; i < 32; i++) data[i] = 0x00;
 164     assert(ntohl(crc32c(data, 32)) == 0xaa36918aL);
 165
 166     /* 32 bytes of all ones */
 167     for (i = 0; i < 32; i++) data[i] = 0xff;
 168     assert(ntohl(crc32c(data, 32)) == 0x43aba862L);
 169
 170     /* 32 bytes of incrementing 00..1f */
 171     for (i = 0; i < 32; i++) data[i] = i;
 172     assert(ntohl(crc32c(data, 32)) == 0x4e79dd46L);
 173
 174     /* 32 bytes of decrementing 1f..00 */
 175     for (i  = 0; i < 32; i++) data[i] = 31 - i;
 176     assert(ntohl(crc32c(data, 32)) == 0x5cdb3f11L);
 177
 178     mark('#');
 179 }
 180
 181 /* Check the IP pseudoheader calculation. */
 182 static void
 183 test_pseudo(void)
 184 {
 185     ovs_be16 csum;
 186     /* Try an IP header similar to one that the tunnel code
 187      * might generate. */
 188     struct ip_header ip = {
 189         .ip_ihl_ver = IP_IHL_VER(5, 4),
 190         .ip_tos = 0,
 191         .ip_tot_len = htons(134),
 192         .ip_id = 0,
 193         .ip_frag_off = htons(IP_DF),
 194         .ip_ttl = 64,
 195         .ip_proto = IPPROTO_UDP,
 196         .ip_csum = htons(0x1265),
 197         .ip_src = { .hi = htons(0x1400), .lo = htons(0x0002) },
 198         .ip_dst = { .hi = htons(0x1400), .lo = htons(0x0001) }
 199     };
 200
 201     csum = csum_finish(packet_csum_pseudoheader(&ip));
 202     assert(csum == htons(0xd779));
 203
 204     /* And also test something totally different to check for
 205      * corner cases. */
 206     memset(&ip, 0xff, sizeof ip);
 207     csum = csum_finish(packet_csum_pseudoheader(&ip));
 208     assert(csum == htons(0xff3c));
 209
 210     mark('#');
 211 }
 212
 213 /* Check the IPv6 pseudoheader calculation. */
 214 static void
 215 test_pseudov6(void)
 216 {
 217     ovs_be16 csum;
 218     /* Try an IPv6 header similar to one that the tunnel code
 219      * might generate. */
 220     struct ovs_16aligned_ip6_hdr ip6 = {
 221         .ip6_vfc = 0x60,
 222         .ip6_hlim = 64,
 223         .ip6_nxt = IPPROTO_UDP,
 224         .ip6_plen = htons(1410),
 225         .ip6_src = { .be16 = { htons(0x2001), htons(0xcafe), 0, 0, 0, 0, 0, htons(0x92) } },
 226         .ip6_dst = { .be16 = { htons(0x2001), htons(0xcafe), 0, 0, 0, 0, 0, htons(0x91) } }
 227     };
 228
 229     csum = csum_finish(packet_csum_pseudoheader6(&ip6, htonl(1410)));
 230     assert(csum == htons(0x234a));
 231
 232     /* And also test something totally different to check for
 233      * corner cases. */
 234     memset(&ip6, 0xff, sizeof ip6);
 235     csum = csum_finish(packet_csum_pseudoheader6(&ip6, htonl(0xffff)));
 236     assert(csum == htons(0xff00));
 237
 238     /* Test 0 sum */
 239     memset(&ip6, 0x00, sizeof ip6);
 240     csum = csum_finish(packet_csum_pseudoheader6(&ip6, htonl(0x0000)));
 241     assert(csum == htons(0xffff));
 242
 243     /* Test 0xffff sum */
 244     memset(&ip6, 0x00, sizeof ip6);
 245     csum = csum_finish(packet_csum_pseudoheader6(&ip6, htonl(0xffff)));
 246     assert(csum == htons(0x0000));
 247
 248     mark('#');
 249 }
 250
 251 static void
 252 test_csum_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 253 {
 254     const struct test_case *tc;
 255     int i;
 256
 257     for (tc = test_cases; tc < &test_cases[ARRAY_SIZE(test_cases)]; tc++) {
 258         const void *data = tc->data;
 259         const ovs_be16 *data16 = (OVS_FORCE const ovs_be16 *) data;
 260         const ovs_be32 *data32 = (OVS_FORCE const ovs_be32 *) data;
 261         uint32_t partial;
 262
 263         /* Test csum(). */
 264         assert(ntohs(csum(tc->data, tc->size)) == tc->csum);
 265         mark('.');
 266
 267         /* Test csum_add16(). */
 268         partial = 0;
 269         for (i = 0; i < tc->size / 2; i++) {
 270             partial = csum_add16(partial, get_unaligned_be16(&data16[i]));
 271         }
 272         assert(ntohs(csum_finish(partial)) == tc->csum);
 273         mark('.');
 274
 275         /* Test csum_add32(). */
 276         partial = 0;
 277         for (i = 0; i < tc->size / 4; i++) {
 278             partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 279         }
 280         assert(ntohs(csum_finish(partial)) == tc->csum);
 281         mark('.');
 282
 283         /* Test alternating csum_add16() and csum_add32(). */
 284         partial = 0;
 285         for (i = 0; i < tc->size / 4; i++) {
 286             if (i % 2) {
 287                 partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 288             } else {
 289                 ovs_be16 u0 = get_unaligned_be16(&data16[i * 2]);
 290                 ovs_be16 u1 = get_unaligned_be16(&data16[i * 2 + 1]);
 291                 partial = csum_add16(partial, u0);
 292                 partial = csum_add16(partial, u1);
 293             }
 294         }
 295         assert(ntohs(csum_finish(partial)) == tc->csum);
 296         mark('.');
 297
 298         /* Test csum_continue(). */
 299         partial = 0;
 300         for (i = 0; i < tc->size / 4; i++) {
 301             if (i) {
 302                 partial = csum_continue(partial, &data32[i], 4);
 303             } else {
 304                 partial = csum_continue(partial, &data16[i * 2], 2);
 305                 partial = csum_continue(partial, &data16[i * 2 + 1], 2);
 306             }
 307         }
 308         assert(ntohs(csum_finish(partial)) == tc->csum);
 309         mark('#');
 310     }
 311
 312     test_rfc1624();
 313     test_crc32c();
 314     test_pseudo();
 315     test_pseudov6();
 316
 317     /* Test recalc_csum16(). */
 318     for (i = 0; i < 32; i++) {
 319         ovs_be16 old_u16, new_u16;
 320         ovs_be16 old_csum;
 321         ovs_be16 data[16];
 322         int j, index;
 323
 324         for (j = 0; j < ARRAY_SIZE(data); j++) {
 325             data[j] = (OVS_FORCE ovs_be16) random_uint32();
 326         }
 327         old_csum = csum(data, sizeof data);
 328         index = random_range(ARRAY_SIZE(data));
 329         old_u16 = data[index];
 330         new_u16 = data[index] = (OVS_FORCE ovs_be16) random_uint32();
 331         assert(csum(data, sizeof data)
 332                == recalc_csum16(old_csum, old_u16, new_u16));
 333         mark('.');
 334     }
 335     mark('#');
 336
 337     /* Test recalc_csum32(). */
 338     for (i = 0; i < 32; i++) {
 339         ovs_be32 old_u32, new_u32;
 340         ovs_be16 old_csum;
 341         ovs_be32 data[16];
 342         int j, index;
 343
 344         for (j = 0; j < ARRAY_SIZE(data); j++) {
 345             data[j] = (OVS_FORCE ovs_be32) random_uint32();
 346         }
 347         old_csum = csum(data, sizeof data);
 348         index = random_range(ARRAY_SIZE(data));
 349         old_u32 = data[index];
 350         new_u32 = data[index] = (OVS_FORCE ovs_be32) random_uint32();
 351         assert(csum(data, sizeof data)
 352                == recalc_csum32(old_csum, old_u32, new_u32));
 353         mark('.');
 354     }
 355     mark('#');
 356
 357     putchar('\n');
 358 }
 359
 360 OVSTEST_REGISTER("test-csum", test_csum_main);