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