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