pintos-os.org Git - openvswitch/blob - tests/test-csum.c

   1 /*
   2  * Copyright (c) 2009, 2010 Nicira Networks.
   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 <inttypes.h>
  20 #include <netinet/in.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include "random.h"
  25 #include "util.h"
  26
  27 #undef NDEBUG
  28 #include <assert.h>
  29
  30 struct test_case {
  31     char *data;
  32     size_t size;                /* Test requires a multiple of 4. */
  33     uint16_t csum;
  34 };
  35
  36 #define TEST_CASE(DATA, CSUM) { DATA, (sizeof DATA) - 1, CSUM }
  37
  38 static const struct test_case test_cases[] = {
  39     /* RFC 1071 section 3. */
  40     TEST_CASE("\x00\x01\xf2\x03"
  41               "\xf4\xf5\xf6\xf7",
  42               (uint16_t) ~0xddf2),
  43
  44     /* http://www.sbprojects.com/projects/tcpip/theory/theory14.htm */
  45     TEST_CASE("\x45\x00\x00\x28"
  46               "\x1F\xFD\x40\x00"
  47               "\x80\x06\x00\x00"
  48               "\xC0\xA8\x3B\x0A"
  49               "\xC0\xA8\x3B\x32",
  50               0xe345),
  51
  52     /* http://mathforum.org/library/drmath/view/54379.html */
  53     TEST_CASE("\x86\x5e\xac\x60"
  54               "\x71\x2a\x81\xb5",
  55               0xda60),
  56 };
  57
  58 static void
  59 mark(char c)
  60 {
  61     putchar(c);
  62     fflush(stdout);
  63 }
  64
  65 #if 0
  66 /* This code is useful for generating new test cases for RFC 1624 section 4. */
  67 static void
  68 generate_rfc1624_test_case(void)
  69 {
  70     int i;
  71
  72     for (i = 0; i < 10000000; i++) {
  73         uint32_t data[8];
  74         int j;
  75
  76         for (j = 0; j < 8; j++) {
  77             data[j] = random_uint32();
  78         }
  79         data[7] &= 0x0000ffff;
  80         data[7] |= 0x55550000;
  81         if (ntohs(~csum(data, sizeof data - 2)) == 0xcd7a) {
  82             ovs_hex_dump(stdout, data, sizeof data, 0, false);
  83             exit(0);
  84         }
  85     }
  86 }
  87 #endif
  88
  89
  90
  91 /* Make sure we get the calculation in RFC 1624 section 4 correct. */
  92 static void
  93 test_rfc1624(void)
  94 {
  95     /* "...an IP packet header in which a 16-bit field m = 0x5555..." */
  96     uint8_t data[32] =
  97         "\xfe\x8f\xc1\x14\x4b\x6f\x70\x2a\x80\x29\x78\xc0\x58\x81\x77\xaa"
  98         "\x66\x64\xfc\x96\x63\x97\x64\xee\x12\x53\x1d\xa9\x2d\xa9\x55\x55";
  99
 100     /* "...the one's complement sum of all other header octets is 0xCD7A." */
 101     assert(ntohs(csum(data, sizeof data - 2)) == (uint16_t) ~0xcd7a);
 102
 103     /* "...the header checksum would be:
 104
 105           HC = ~(0xCD7A + 0x5555)
 106              = ~0x22D0
 107              =  0xDD2F"
 108     */
 109     assert(ntohs(csum(data, sizeof data)) == 0xdd2f);
 110
 111     /* "a 16-bit field m = 0x5555 changes to m' = 0x3285..." */
 112     data[30] = 0x32;
 113     data[31] = 0x85;
 114
 115     /* "The new checksum via recomputation is:
 116
 117           HC' = ~(0xCD7A + 0x3285)
 118               = ~0xFFFF
 119               =  0x0000"
 120     */
 121     assert(ntohs(csum(data, sizeof data)) == 0x0000);
 122
 123     /* "Applying [Eqn. 3] to the example above, we get the correct result:
 124
 125           HC' = ~(C + (-m) + m')
 126               = ~(0x22D0 + ~0x5555 + 0x3285)
 127               = ~0xFFFF
 128               =  0x0000" */
 129     assert(recalc_csum16(0xdd2f, 0x5555, 0x3285) == 0x0000);
 130
 131     mark('#');
 132 }
 133
 134 int
 135 main(void)
 136 {
 137     const struct test_case *tc;
 138     int i;
 139
 140     for (tc = test_cases; tc < &test_cases[ARRAY_SIZE(test_cases)]; tc++) {
 141         const uint16_t *data16 = (const uint16_t *) tc->data;
 142         const uint32_t *data32 = (const uint32_t *) tc->data;
 143         uint32_t partial;
 144
 145         /* Test csum(). */
 146         assert(ntohs(csum(tc->data, tc->size)) == tc->csum);
 147         mark('.');
 148
 149         /* Test csum_add16(). */
 150         partial = 0;
 151         for (i = 0; i < tc->size / 2; i++) {
 152             partial = csum_add16(partial, data16[i]);
 153         }
 154         assert(ntohs(csum_finish(partial)) == tc->csum);
 155         mark('.');
 156
 157         /* Test csum_add32(). */
 158         partial = 0;
 159         for (i = 0; i < tc->size / 4; i++) {
 160             partial = csum_add32(partial, data32[i]);
 161         }
 162         assert(ntohs(csum_finish(partial)) == tc->csum);
 163         mark('.');
 164
 165         /* Test alternating csum_add16() and csum_add32(). */
 166         partial = 0;
 167         for (i = 0; i < tc->size / 4; i++) {
 168             if (i % 2) {
 169                 partial = csum_add32(partial, data32[i]);
 170             } else {
 171                 partial = csum_add16(partial, data16[i * 2]);
 172                 partial = csum_add16(partial, data16[i * 2 + 1]);
 173             }
 174         }
 175         assert(ntohs(csum_finish(partial)) == tc->csum);
 176         mark('.');
 177
 178         /* Test csum_continue(). */
 179         partial = 0;
 180         for (i = 0; i < tc->size / 4; i++) {
 181             if (i) {
 182                 partial = csum_continue(partial, &data32[i], 4);
 183             } else {
 184                 partial = csum_continue(partial, &data16[i * 2], 2);
 185                 partial = csum_continue(partial, &data16[i * 2 + 1], 2);
 186             }
 187         }
 188         assert(ntohs(csum_finish(partial)) == tc->csum);
 189         mark('#');
 190     }
 191
 192     test_rfc1624();
 193
 194     /* Test recalc_csum16(). */
 195     for (i = 0; i < 32; i++) {
 196         uint16_t old_u16, new_u16;
 197         uint16_t old_csum;
 198         uint16_t data[16];
 199         int j, index;
 200
 201         for (j = 0; j < ARRAY_SIZE(data); j++) {
 202             data[j] = random_uint32();
 203         }
 204         old_csum = csum(data, sizeof data);
 205         index = random_range(ARRAY_SIZE(data));
 206         old_u16 = data[index];
 207         new_u16 = data[index] = random_uint32();
 208         assert(csum(data, sizeof data)
 209                == recalc_csum16(old_csum, old_u16, new_u16));
 210         mark('.');
 211     }
 212     mark('#');
 213
 214     /* Test recalc_csum32(). */
 215     for (i = 0; i < 32; i++) {
 216         uint32_t old_u32, new_u32;
 217         uint16_t old_csum;
 218         uint32_t data[16];
 219         int j, index;
 220
 221         for (j = 0; j < ARRAY_SIZE(data); j++) {
 222             data[j] = random_uint32();
 223         }
 224         old_csum = csum(data, sizeof data);
 225         index = random_range(ARRAY_SIZE(data));
 226         old_u32 = data[index];
 227         new_u32 = data[index] = random_uint32();
 228         assert(csum(data, sizeof data)
 229                == recalc_csum32(old_csum, old_u32, new_u32));
 230         mark('.');
 231     }
 232     mark('#');
 233
 234     putchar('\n');
 235
 236     return 0;
 237 }