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 "crc32c.h"
  20 #include <inttypes.h>
  21 #include <netinet/in.h>
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include "random.h"
  26 #include "unaligned.h"
  27 #include "util.h"
  28
  29 #undef NDEBUG
  30 #include <assert.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 int
 179 main(void)
 180 {
 181     const struct test_case *tc;
 182     int i;
 183
 184     for (tc = test_cases; tc < &test_cases[ARRAY_SIZE(test_cases)]; tc++) {
 185         const void *data = tc->data;
 186         const ovs_be16 *data16 = (OVS_FORCE const ovs_be16 *) data;
 187         const ovs_be32 *data32 = (OVS_FORCE const ovs_be32 *) data;
 188         uint32_t partial;
 189
 190         /* Test csum(). */
 191         assert(ntohs(csum(tc->data, tc->size)) == tc->csum);
 192         mark('.');
 193
 194         /* Test csum_add16(). */
 195         partial = 0;
 196         for (i = 0; i < tc->size / 2; i++) {
 197             partial = csum_add16(partial, get_unaligned_be16(&data16[i]));
 198         }
 199         assert(ntohs(csum_finish(partial)) == tc->csum);
 200         mark('.');
 201
 202         /* Test csum_add32(). */
 203         partial = 0;
 204         for (i = 0; i < tc->size / 4; i++) {
 205             partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 206         }
 207         assert(ntohs(csum_finish(partial)) == tc->csum);
 208         mark('.');
 209
 210         /* Test alternating csum_add16() and csum_add32(). */
 211         partial = 0;
 212         for (i = 0; i < tc->size / 4; i++) {
 213             if (i % 2) {
 214                 partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 215             } else {
 216                 ovs_be16 u0 = get_unaligned_be16(&data16[i * 2]);
 217                 ovs_be16 u1 = get_unaligned_be16(&data16[i * 2 + 1]);
 218                 partial = csum_add16(partial, u0);
 219                 partial = csum_add16(partial, u1);
 220             }
 221         }
 222         assert(ntohs(csum_finish(partial)) == tc->csum);
 223         mark('.');
 224
 225         /* Test csum_continue(). */
 226         partial = 0;
 227         for (i = 0; i < tc->size / 4; i++) {
 228             if (i) {
 229                 partial = csum_continue(partial, &data32[i], 4);
 230             } else {
 231                 partial = csum_continue(partial, &data16[i * 2], 2);
 232                 partial = csum_continue(partial, &data16[i * 2 + 1], 2);
 233             }
 234         }
 235         assert(ntohs(csum_finish(partial)) == tc->csum);
 236         mark('#');
 237     }
 238
 239     test_rfc1624();
 240     test_crc32c();
 241
 242     /* Test recalc_csum16(). */
 243     for (i = 0; i < 32; i++) {
 244         ovs_be16 old_u16, new_u16;
 245         ovs_be16 old_csum;
 246         ovs_be16 data[16];
 247         int j, index;
 248
 249         for (j = 0; j < ARRAY_SIZE(data); j++) {
 250             data[j] = (OVS_FORCE ovs_be16) random_uint32();
 251         }
 252         old_csum = csum(data, sizeof data);
 253         index = random_range(ARRAY_SIZE(data));
 254         old_u16 = data[index];
 255         new_u16 = data[index] = (OVS_FORCE ovs_be16) random_uint32();
 256         assert(csum(data, sizeof data)
 257                == recalc_csum16(old_csum, old_u16, new_u16));
 258         mark('.');
 259     }
 260     mark('#');
 261
 262     /* Test recalc_csum32(). */
 263     for (i = 0; i < 32; i++) {
 264         ovs_be32 old_u32, new_u32;
 265         ovs_be16 old_csum;
 266         ovs_be32 data[16];
 267         int j, index;
 268
 269         for (j = 0; j < ARRAY_SIZE(data); j++) {
 270             data[j] = (OVS_FORCE ovs_be32) random_uint32();
 271         }
 272         old_csum = csum(data, sizeof data);
 273         index = random_range(ARRAY_SIZE(data));
 274         old_u32 = data[index];
 275         new_u32 = data[index] = (OVS_FORCE ovs_be32) random_uint32();
 276         assert(csum(data, sizeof data)
 277                == recalc_csum32(old_csum, old_u32, new_u32));
 278         mark('.');
 279     }
 280     mark('#');
 281
 282     putchar('\n');
 283
 284     return 0;
 285 }