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