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 <sys/types.h>
  23 #include <netinet/in.h>
  24 #include <netinet/ip.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 static void
 214 test_csum_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
 215 {
 216     const struct test_case *tc;
 217     int i;
 218
 219     for (tc = test_cases; tc < &test_cases[ARRAY_SIZE(test_cases)]; tc++) {
 220         const void *data = tc->data;
 221         const ovs_be16 *data16 = (OVS_FORCE const ovs_be16 *) data;
 222         const ovs_be32 *data32 = (OVS_FORCE const ovs_be32 *) data;
 223         uint32_t partial;
 224
 225         /* Test csum(). */
 226         assert(ntohs(csum(tc->data, tc->size)) == tc->csum);
 227         mark('.');
 228
 229         /* Test csum_add16(). */
 230         partial = 0;
 231         for (i = 0; i < tc->size / 2; i++) {
 232             partial = csum_add16(partial, get_unaligned_be16(&data16[i]));
 233         }
 234         assert(ntohs(csum_finish(partial)) == tc->csum);
 235         mark('.');
 236
 237         /* Test csum_add32(). */
 238         partial = 0;
 239         for (i = 0; i < tc->size / 4; i++) {
 240             partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 241         }
 242         assert(ntohs(csum_finish(partial)) == tc->csum);
 243         mark('.');
 244
 245         /* Test alternating csum_add16() and csum_add32(). */
 246         partial = 0;
 247         for (i = 0; i < tc->size / 4; i++) {
 248             if (i % 2) {
 249                 partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 250             } else {
 251                 ovs_be16 u0 = get_unaligned_be16(&data16[i * 2]);
 252                 ovs_be16 u1 = get_unaligned_be16(&data16[i * 2 + 1]);
 253                 partial = csum_add16(partial, u0);
 254                 partial = csum_add16(partial, u1);
 255             }
 256         }
 257         assert(ntohs(csum_finish(partial)) == tc->csum);
 258         mark('.');
 259
 260         /* Test csum_continue(). */
 261         partial = 0;
 262         for (i = 0; i < tc->size / 4; i++) {
 263             if (i) {
 264                 partial = csum_continue(partial, &data32[i], 4);
 265             } else {
 266                 partial = csum_continue(partial, &data16[i * 2], 2);
 267                 partial = csum_continue(partial, &data16[i * 2 + 1], 2);
 268             }
 269         }
 270         assert(ntohs(csum_finish(partial)) == tc->csum);
 271         mark('#');
 272     }
 273
 274     test_rfc1624();
 275     test_crc32c();
 276     test_pseudo();
 277
 278     /* Test recalc_csum16(). */
 279     for (i = 0; i < 32; i++) {
 280         ovs_be16 old_u16, new_u16;
 281         ovs_be16 old_csum;
 282         ovs_be16 data[16];
 283         int j, index;
 284
 285         for (j = 0; j < ARRAY_SIZE(data); j++) {
 286             data[j] = (OVS_FORCE ovs_be16) random_uint32();
 287         }
 288         old_csum = csum(data, sizeof data);
 289         index = random_range(ARRAY_SIZE(data));
 290         old_u16 = data[index];
 291         new_u16 = data[index] = (OVS_FORCE ovs_be16) random_uint32();
 292         assert(csum(data, sizeof data)
 293                == recalc_csum16(old_csum, old_u16, new_u16));
 294         mark('.');
 295     }
 296     mark('#');
 297
 298     /* Test recalc_csum32(). */
 299     for (i = 0; i < 32; i++) {
 300         ovs_be32 old_u32, new_u32;
 301         ovs_be16 old_csum;
 302         ovs_be32 data[16];
 303         int j, index;
 304
 305         for (j = 0; j < ARRAY_SIZE(data); j++) {
 306             data[j] = (OVS_FORCE ovs_be32) random_uint32();
 307         }
 308         old_csum = csum(data, sizeof data);
 309         index = random_range(ARRAY_SIZE(data));
 310         old_u32 = data[index];
 311         new_u32 = data[index] = (OVS_FORCE ovs_be32) random_uint32();
 312         assert(csum(data, sizeof data)
 313                == recalc_csum32(old_csum, old_u32, new_u32));
 314         mark('.');
 315     }
 316     mark('#');
 317
 318     putchar('\n');
 319 }
 320
 321 OVSTEST_REGISTER("test-csum", test_csum_main);